((Pythonで) 書く (Lisp) インタプリタ)

構文解析: readとparse

>>> program = "(set! x*2 (* x 2))"
 >>> tokenize(program)
['(', 'set!', 'x*2', '(', '*', 'x', '2', ')', ')']
 >>> parse(program)
['set!', 'x*2', ['*', 'x', 2]]

次は構文解析だ。Lispの構文がごくシンプルなことを見たが、Lispのインタプリタの中には、リストを表す任意の文字列をプログラムとして受け入れることで、構文解析をさらに簡単にしているものがある。その場合文字列(set! 1 2)は構文的に正しいプログラムとなり、ただ実行した時にインタプリタがset!の最初の引数は数ではなくシンボルでなければならないと文句を言うことになる。JavaやPythonでは等値式1 = 2はコンパイル時にエラーとして認識される。一方で、JavaやPythonではコンパイル時にx/0という式をエラーとして検知する必要はなく、エラーをいつ見つけるべきかは必ずしも厳格に決められているわけではない。Lispyではparseを任意の式(数、シンボル、入れ子になったリスト)を読み込む関数readで実装する。

readはtokenize で得たトークンに対してread_fromを呼ぶことで処理を行う。トークンのリストに対し、最初のトークンから見ていく。それが')'なら構文エラーだ。'('なら対応する')'が見つかるまで、式のリストを構築していく。それ以外の場合はシンボルか数でなければならず、これはそれ自体として完全な式を構成する。あと必要となる仕掛けは、'2'は整数、2.0は浮動小数点数、xはシンボルだと見分ける方法だ。この識別はPythonにやらせることにしよう。カッコも引用符も付いていないトークンは、最初intと解釈しようと試み、それからfloat、最後にシンボルとして解釈する。これをコードにすると以下のようになる。

def read(s):
 "文字列からScheme式を読み込む。"
 return read_from(tokenize(s))
 
parse = read
 
def tokenize(s):
 "文字列をトークンのリストに変換する。"
 return s.replace('(',' ( ').replace(')',' ) ').split()
 
def read_from(tokens):
 "トークンの列から式を読み込む。"
 if len(tokens) == 0:
 raise SyntaxError('unexpected EOF while reading')
 token = tokens.pop(0)
 if '(' == token:
 L = []
 while tokens[0] != ')':
 L.append(read_from(tokens))
 tokens.pop(0) # pop off ')'
 return L
 elif ')' == token:
 raise SyntaxError('unexpected )')
 else:
 return atom(token)
 
def atom(token):
 "数は数にし、それ以外のトークンはシンボルにする。"
 try: return int(token)
 except ValueError:
 try: return float(token)
 except ValueError:
 return Symbol(token)

最後に、式をLispの読める文字列に変換する関数to_stringと、対話的Lispインタプリタとなるreplを追加する(replの名前はread-eval-print-loopから来ている)。

def to_string(exp):
 "PythonオブジェクトをLispの読める文字列に戻す。"
 return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)
 
def repl(prompt='lis.py> '):
 "read-eval-print-loopのプロンプト"
 while True:
 val = eval(parse(raw_input(prompt)))
 if val is not None: print to_string(val)

>>> repl()
lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (area 3)
28.274333877
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) lis.py> (fact 10)
3628800
lis.py> (fact 100)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000
lis.py> (area (fact 10))
4.1369087198e+13
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4

Lispyはどれほど小さい/速い/完全/良いか?

• 小さい Lispyはとても小さい。コメントや空行を除くと90行で、ソースコードは4Kバイト以下だ。(最初のバージョンは96行だったが、Eric Cooperの示唆により、Procedureのクラス定義をなくし、代わりにPythonのlambdaを使うことで短くなった。) 私がJavaで書いた最小のSchemeであるJschemeのソースは1664行で57Kバイトあった。Jschemeは当初SILK (Scheme in Fifty Kilobytes、50キロバイトのScheme)と呼んでいたが、この制限を満たしていたのはソースコードではなくバイトコードで数えたときだけだった。Lispyはずっと良くなっている。これはアラン・ケイが「世界で最も強力な言語」を「1ページのコード」で定義できると1972年に言った言葉に合っていると思う。
  

  bash$ grep "^\s*[^#\s]" lis.py | wc
   90 398 3423
  

• 速い Lispyは(fact 100)を0.004秒で計算する。これは私にとっては十分に速いものだ(他の多くの手段よりはるかに遅いにしても)。

• 完全 LispyはScheme標準と比べるとあまり完全ではない。大きな欠点を挙げると
  • 構文 コメント、クォート/準クォート記法、#リテラル、派生式型、ドットリスト記法を欠いている。
  • 意味論 call/ccと末尾再帰を欠いている。
  • データ型 文字列、文字、論理型、ポート、ベクタ、数の正確/不正確を欠いている。Pythonのリストは、ここでそれを使って実装したSchemeのリストやペアよりは、Schemeのベクタに近い。
  • 手続き 100個以上のプリミティブな手続きを欠いている。欠いているデータ型のためのものと、その他のものがある(set-car! やset-cdr!のような。Pythonのリストでset-cdr! を完全に実装することはできないからだ)。
  • エラー回復 Lispyはエラーに対して、検出、相応の報告、回復を試みない。Lispyはプログラマが完璧であるものと期待している。
• 良い これは読者が判断することだ。私としては、Lispインタプリタについて解説するという目的のために良いものであることがわかった。

実際にあった話

そこからTonyと私は別な道を歩んだ。彼は式のインタプリタが難しい部分だと考えた。そのためにLispが必要だったが、彼にはLispでない文字列を返す小さなCのルーチンを書いて、それをLispプログラムにリンクする方法が分かった。私はリンクのやり方を知らなかったが、この単純な言語のインタプリタを書くのは簡単だと思ったので(変数の設定、変数の取得、文字列の連接しかなかった)、インタプリタ自体をCで書くことにした。だから皮肉にも、TonyはCプログラマであったためにLispプログラムを書き、私はLispプログラマだったためにCプログラムを書くことになったのだ。

最終的には2人とも論文を仕上げることができた。

プログラムの全体

################ Lispy: Scheme Interpreter in Python
## (c) Peter Norvig, 2010; See http://norvig.com/lispy.html
################ Symbol、Procedure、Envクラス
from __future__ import division
Symbol = str
class Env(dict):
 "環境: ペア{'var':val}のdictで、外部環境(outer)を持つ。"
 def __init__(self, parms=(), args=(), outer=None):
 self.update(zip(parms,args))
 self.outer = outer
 def find(self, var):
 "var が現れる一番内側のEnvを見つける。"
 return self if var in self else self.outer.find(var)
def add_globals(env):
 "環境にScheme標準の手続きをいくつか追加する"
 import math, operator as op
 env.update(vars(math)) # sin, sqrt, ...
 env.update(
 {'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,
 '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+y, 'car':lambda x:x[0],'cdr':lambda x:x[1:], 'append':op.add, 'list':lambda *x:list(x), 'list?': lambda x:isa(x,list), 'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol)}) return env global_env = add_globals(Env()) isa = isinstance ################ eval def eval(x, env=global_env): "環境の中で式を評価する。" if isa(x, Symbol): # 変数参照 return env.find(x)[x] elif not isa(x, list): # 定数リテラル return x elif x[0] == 'quote': # (quote exp) (_, exp) = x return exp elif x[0] == 'if': # (if test conseq alt) (_, test, conseq, alt) = x return eval((conseq if eval(test, env) else alt), env) elif x[0] == 'set!': # (set! var exp) (_, var, exp) = x env.find(var)[var] = eval(exp, env) elif x[0] == 'define': # (define var exp) (_, var, exp) = x env[var] = eval(exp, env) elif x[0] == 'lambda': # (lambda (var*) exp) (_, vars, exp) = x return lambda *args: eval(exp, Env(vars, args, env)) elif x[0] == 'begin': # (begin exp*) for exp in x[1:]: val = eval(exp, env) return val else: # (proc exp*) exps = [eval(exp, env) for exp in x] proc = exps.pop(0) return proc(*exps) ################ parse、read、ユーザ対話 def read(s): "文字列からScheme式を読み込む。" return read_from(tokenize(s)) parse = read def tokenize(s): "文字列をトークンのリストに変換する。" return s.replace('(',' ( ').replace(')',' ) ').split() def read_from(tokens): "トークンの列から式を読み込む。" if len(tokens) == 0: raise SyntaxError('unexpected EOF while reading') token = tokens.pop(0) if '(' == token: L = [] while tokens[0] != ')': L.append(read_from(tokens)) tokens.pop(0) # pop off ')' return L elif ')' == token: raise SyntaxError('unexpected )') else: return atom(token) def atom(token): "数は数にし、それ以外のトークンはシンボルにする。" try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token) def to_string(exp): "PythonオブジェクトをLispの読める文字列に戻す。" return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp) def repl(prompt='lis.py> '):
 "read-eval-print-loopのプロンプト"
 while True:
 val = eval(parse(raw_input(prompt)))
 if val is not None: print to_string(val)