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

Peter Norvig / 青木靖 訳

このページには2つの目的がある。コンピュータ言語の実装について一般的な記述をすることと、Lispの方言であるSchemeのサブセットをPythonで実装する具体的な方法を示すことである。私はこのインタプリタをLispy (lis.py)と呼ぶ。何年か前に私はJavaCommon LispでSchemeインタプリタを書く方法を示した。今回の目標は、アラン・ケイが「ソフトウェアのマクスウェル方程式」と呼んだところの簡潔さと取っつきやすさを可能な限り実現するということだ。
 

SchemeのサブセットLispy の構文と意味論

コンピュータ言語の多くは様々な構文的な決まり(キーワード、中置演算子、カッコ、演算子優先順、ドット記法、セミコロンなど)を持っているが、Lisp族言語の1つとして、Schemeの構文はすべてカッコ付きの前置記法であるリストを基本としている。そういうのはあまり見慣れていないかもしれないが、シンプルさと一貫性という点で大きなメリットがある。(“Lisp”というのは“Lots of Irritating Silly Parentheses”(たくさんの苛立たしい馬鹿げたカッコ)の略だとジョークを言った人がいる。私は“Lisp Is Syntactically Pure”(Lispは構文的に純粋)の略だと思っている。) これを見てほしい。
Java      Scheme
if (x.val() > 0) {
  z = f(a * x.val() + b);
}
  (if (> (val x) 0)
    (set! z (f (+ (* a (val x)) b))))
びっくりマークがSchemeでは特殊記号でないことに注意してほしい。これは単に“set!”という名前の一部だ。Schemeで特別なのはカッコだけだ。(set! x y)のように最初の位置に特別なキーワードがあるリストを、Schemeでは特殊形式と呼んでいる。この言語の美しいところは、6つの特殊形式と3つの構文的構成物(変数、定数、手続き呼出し)しか必要でないことだ。

形式構文意味論と例
変数参照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 はシンボル(xsquareのような識別子)、number は整数か浮動小数点数、その他のイタリックの語は任意の式である。exp... は0個以上の式の並びを意味する。

Schemeについてもっと詳しく学ぶには、優れた本(Friedman & FelleseinDybvigQueinnecHarvey & WrightSussman & Abelson)、ビデオ(Abelson & Sussman)、チュートリアル(DoraiPLTNeller)、リファレンスマニュアルなどに当たってほしい。[Dybvigの本 (プログラミング言語Scheme)とSussman & Abelsonの本 (計算機プログラムの構造と解釈)には日本語訳がある。]

言語インタプリタがすること

言語インタプリタは2つの部分からなる。
  1. 構文解析  構文解析コンポーネントはプログラムを文字の列として読み込み、言語の構文規則に照らしてチェックし、プログラムを内部表現へと変換する。シンプルなインタプリタでは、内部表現はプログラムの文や式の入れ子構造に密接に対応した木構造となっている。コンパイラと呼ばれる言語変換プログラムでは、内部表現はコンピュータによって直接実行可能な命令の列となる。スティーブ・イェギが言っているが、「コンパイラがどう機能するか知らなければ、コンピュータがどう機能するかもわからない」。イェギはコンパイラで解決できる8つの状況について解説している(これはインタプリタでも同様にでき、あるいはイェギのいつもの強烈な皮肉でも対処できる)。Lispyの構文解析器は関数parseで実装されている。
  2. 実行  プログラムの内部表現はその後言語の意味論規則に基づいて処理され計算が実行される。実行は関数evalで実装されている(これはPythonの組み込み関数を隠すことになるのに注意してほしい)。
以下は解釈プロセスを図示したものと、parseevalが短いプログラムをどう処理するか示す対話セッションの例だ。

>>> 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のリスト、数、文字列で表すことにする。

実行: eval

以下はevalの定義だ。上の表の9つのケースのそれぞれに対し、1行か2行か3行の処理が書いてある。evalの定義にはこの9つのケースしか必要ない。
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']]を、r3で、外の環境がグローバル環境である環境において評価することになる。そのため*は掛け算になる。

これで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)
Envdictのサブクラスなので、通常の辞書操作が使えることに注意してほしい。それに加えて2つの手続き、コンストラクタ__init__と、変数に対する適切な環境を見つけるfindがある。このクラスを理解する鍵になるのは(そして単にdictを使うのでなくクラスが必要だった理由は)、「外の環境」という概念だ。このプログラムを考えてほしい。

(define make-account
  (lambda (balance)
    (lambda (amt)
      (begin (set! balance (+ balance amt)) balance))))

(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())

構文解析: readとparse

次に関数parseに取り掛かろう。構文解析は伝統的に2つの部分に分けられている。字句解析で入力文字列をトークンの列に分解し、構文解析でトークンから内部表現を組み立てる。Lispyのトークンはカッコと、シンボル(set!xなど)と、数(2など)だ。以下のように動作する。
>>> 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で実装する。

readtokenize で得たトークンに対して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をいくつかの基準に照らして評価してみよう。

実際にあった話

インタプリタの仕組みを知っているととても役に立つことがあることの証明として、実際にあったことを話そう。1984年の昔、私は博士論文を書いていた。当時はLaTeXもなく、Microsoft Wordもなく、我々が使っていたのはtroffだった。あいにくとtroffはラベルを使って前方参照することができなかった。私は「@theoremxページで見るように」みたいに書いて、参照先に"@(set theoremx \n%)"と書いておけるとありがたかった(troffはレジスタ\n%にページ番号を保持していた)。同僚の院生のTony DeRoseも同じニーズを持っていたので、私たちは一緒にプリプロセッサとしてこれを行う簡単なLispプログラムを書いた。しかし私たちが当時使っていたLispは、Lispの式を読む分にはいいが、Lisp以外の式を1文字ずつ読み込むのが非常に遅かったため、このプログラムを使うのは煩わしかった。

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

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

プログラムの全体

まとめとして、ここにLispyの全体を挙げておく (ここからダウンロードできる: lis.py)
################ 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  

オリジナル: (How to Write a (Lisp) Interpreter (in Python))