Peter Norvig / 青木靖 訳
このページには2つの目的がある。コンピュータ言語の実装について一般的な記述をすることと、Lispの方言であるSchemeのサブセットをPythonで実装する具体的な方法を示すことである。私はこのインタプリタをLispy (lis.py)と呼ぶ。何年か前に私はJavaとCommon LispでSchemeインタプリタを書く方法を示した。今回の目標は、アラン・ケイが「ソフトウェアのマクスウェル方程式」と呼んだところの簡潔さと取っつきやすさを可能な限り実現するということだ。びっくりマークがSchemeでは特殊記号でないことに注意してほしい。これは単に“set!”という名前の一部だ。Schemeで特別なのはカッコだけだ。(set! x y)のように最初の位置に特別なキーワードがあるリストを、Schemeでは特殊形式と呼んでいる。この言語の美しいところは、6つの特殊形式と3つの構文的構成物(変数、定数、手続き呼出し)しか必要でないことだ。
Java Scheme if (x.val() > 0) {
z = f(a * x.val() + b);
}(if (> (val x) 0)
(set! z (f (+ (* a (val x)) b))))
形式 | 構文 | 意味論と例 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
変数参照 | var | 変数名として解釈されるシンボル。その値は変数の値となる。 例: x | ||||||||||||||||||
定数リテラル | number | 数はそれ自身へと評価される。 例: 12 や -3.45e+6 | ||||||||||||||||||
クォート | (quote exp)
exp を解釈せずにそのまま返す。 | 例: (quote (a b c)) ⇒ (a b c)
条件式 | (if test conseq
alt) | test を評価して、真の場合にはconseq を返し、偽の場合はをalt
返す。 | 例: (if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2
代入 | (set! var
exp) | exp
を評価してその値をvar に割り当てる。varはあらかじめ定義されている必要がある(defineによって、あるいはその代入を含む手続きの引数として)。 | 例: (set! x2 (* x x))
定義
| (define var exp)
| 最も内側の環境に新しい変数を定義し、式exp を評価した値を設定する。 | 例: (define r 3) あるいは (define square (lambda (x) (* x x)))
手続き | (lambda (var...)
exp) | var... を引数名、式exp を本体とする手続きを作る。 | 例: (lambda (r) (* 3.141592653 (* r r)))
逐次式 | (begin exp...) |
exp... のそれぞれの式を左から右へ評価していき、最後の値を返す。 | 例: (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4
手続き呼出し | (proc exp...) | proc がシンボルif, set!,
define, lambda, begin, quote
のいずれでもない場合、それは手続きとして扱われ、ここに定義するルールに従って評価される。exp... のすべての式が評価され、その式のリストを引数として手続きが呼び出される。 | 例: (square 12) ⇒ 144 |
この表で、var はシンボル(xやsquareのような識別子)、number は整数か浮動小数点数、その他のイタリックの語は任意の式である。exp... は0個以上の式の並びを意味する。
Schemeについてもっと詳しく学ぶには、優れた本(Friedman & Fellesein、Dybvig、Queinnec、Harvey & Wright、Sussman & Abelson)、ビデオ(Abelson & Sussman)、チュートリアル(Dorai、PLT、Neller)、リファレンスマニュアルなどに当たってほしい。[Dybvigの本 (プログラミング言語Scheme)とSussman & Abelsonの本 (計算機プログラムの構造と解釈)には日本語訳がある。]
>>> program = "(begin (define r 3) (* 3.141592653 (* r r)))" >>> parse(program) ['begin', ['define', 'r', 3], ['*', 3.141592653, ['*', 'r', 'r']]] >>> eval(parse(program)) 28.274333877我々はできるだけシンプルな内部表現を使うことにして、Schemeのリスト、数、シンボルを、それぞれPythonのリスト、数、文字列で表すことにする。
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) isa = isinstance Symbol = str
これがevalのすべてだ!…まあ、環境を別にすればだが。環境はシンボルからそれが保持する値への単なるマッピングだ。新しいシンボル/値のバインディングは、defineか、手続き(lamda式)によって追加される。
Schemeの手続きを定義してそれを呼出したとき、何が起きるのか例を見てみよう (プロンプト lis.py> は、PythonではなくLispインタプリタ相手に話していることを意味する)。
lis.py> (define area (lambda (r) (* 3.141592653 (* r r)))) lis.py> (area 3) 28.274333877(lambda (r) (* 3.141592653 (* r r)))を評価すると、evalにあるelif x[0] == 'lambda'の分岐をたどって、3つの変数(_, vars, exp)にリストxの対応する要素が代入される(xの長さが3でない場合にはエラーを出す)。それから新しい手続きが作られる。その手続きは呼ばれると式['*', 3.141592653 ['*', 'r', 'r']]を評価するが、その際の環境として、手続きの仮引数(今の場合rひとつだけ)と手続き呼出しで渡された引数のバインディングと、パラメタリストにない任意の変数(たとえば変数*)の現在の環境での値とを合わせたものを使用する。新しく作られた手続きは、global_envの中の変数areaの値として割り当てられる。
そうすると例えば(area 3)を評価したときどうなるか? areaは特殊シンボルではないので、手続き呼出しのはずであり(evalの最後のelse:の部分)、リスト中の各式が1つずつ評価される。areaを評価すると今作った手続きが得られ、3を評価すると3が得られる。それから(evalの最後の行に従って)新しく作られた手続きが引数リスト[3]に対して呼び出される。これはつまり、式['*', 3.141592653 ['*', 'r', 'r']]を、rが3で、外の環境がグローバル環境である環境において評価することになる。そのため*は掛け算になる。
これでEnvクラスについて詳しく説明する準備ができた。
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)Envはdictのサブクラスなので、通常の辞書操作が使えることに注意してほしい。それに加えて2つの手続き、コンストラクタ__init__と、変数に対する適切な環境を見つけるfindがある。このクラスを理解する鍵になるのは(そして単にdictを使うのでなくクラスが必要だった理由は)、「外の環境」という概念だ。このプログラムを考えてほしい。
(define make-account
(define a1 (make-account 100.00)) (a1 -20.00) |
それぞれの箱は環境を表し、箱の色は環境の中で新たに定義された変数の色に対応している。最後の2行では、a1を定義して(a1 -20.00)を呼出している。これは当初残高100ドルの銀行口座の作成し、20ドル引き出すことを表す。(a1 -20.00)の評価の過程で、黄色く色づけした式をevalする。この式には3つの変数が現れる。amtは一番内側(緑色)の環境ですぐに見つかる。しかしbalanceはそこでは定義されておらず、緑色の環境の外の環境である青色の環境を見る必要がある。最後に、変数 + はどちらの環境にも見当たらないので、さらにもう一段外に行って、グローバル(赤色)な環境を見る必要がある。このように、最初に内側の環境を見、それから順次外の環境を見ていくやり方は構文スコープと呼ばれている。手続きfindは、構文スコープのルールに従って適切な環境を見つける。
あと残っているのはグローバル環境を定義することだけだ。これには + と、その他Schemeの組み込み手続きをすべてを含める必要がある。ここではそのすべてを実装する手間はかけず、Pythonのmathモジュールをインポートし、それに良く使うものを20個ほど明示的に追加しておくことにしよう。
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())
>>> program = "(set! x*2 (* x 2))" >>> tokenize(program) ['(', 'set!', 'x*2', '(', '*', 'x', '2', ')', ')'] >>> parse(program) ['set!', 'x*2', ['*', 'x', 2]]字句解析のためのツールはたくさんある(Mike Lesk とEric Schmidtの lexなど)。しかし私たちはごくシンプルなツールを使うことにしよう。Pythonのstr.splitだ。カッコの前後にスペースを入れてからstr.splitでトークンのリストを得ることにする。
次は構文解析だ。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
bash$ grep "^\s*[^#\s]" lis.py | wc 90 398 3423
そこから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)
home rss |