LispKit Lisp処理系の実装 ２：インタプリタ〜変数から算術演算子まで
前回のパーサの出力するASTをそのまま実行するインタプリタを実装する。
インタプリタを実装する意義
「SECD抽象機械へのコンパイラ実装の前にインタプリタを作る」というのはHendersonのFunctional Programming Application & Implementationでの流れに従っている。
Python（やLispやOCaml）のような高レベルプログラミング言語でインタプリタを実装すると、言語の意味論を直感的に理解しやすい。ただしその直感は実装言語の意味論を直感的かつ正確に把握していることが前提となる。例えば関数適用時に実引数がどの順番で評価されるか、などが実装言語の仕様に依存しやすい（ちなみにPythonとOCamlではその順番が逆だ）
これがSECD抽象機械などの低レベルな実行システムだと、挙動が厳密に定義・把握しやすいが直感的な理解は難しく、一長一短といったところ。というわけでやはり両方やるのが良さそう。
eval_関数
インタプリタの本体となるのはeval_という再帰関数で、未評価のASTノードを受け取り評価済みASTノードを返す。評価前と後で同じデータ型のままなのがLispらしい。
eval_関数はパターンマッチ（しつこいようだがPython3.10の新機能）で実装している：
def eval_(e, n, v): match e: case Alpha("NIL"): ... # マッチ後の処理は後述 case Alpha(s): ... case Num(_): ... case Cons(Alpha("QUOTE"), Cons(e1, Alpha("NIL"))): ... case Cons(Alpha("ATOM"), Cons(e1, Alpha("NIL"))): ... case Cons(Alpha("CONS"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("CAR"), Cons(e1, Alpha("NIL"))): ... case Cons(Alpha("CDR"), Cons(e1, Alpha("NIL"))): ... case Cons(Alpha("EQ"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("LEQ"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("ADD"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("SUB"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("MUL"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("DIV"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("REM"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("IF"), Cons(e1, Cons(e2, Cons(e3, Alpha("NIL"))))): ... case Cons(Alpha("LAMBDA"), Cons(e1, Cons(e2, Alpha("NIL")))): ... case Cons(Alpha("LET"), Cons(e1, e2)): ... case Cons(Alpha("LETREC"), Cons(e1, e2)): ... case Cons(e1, e2): ...
eval_関数は評価するべき式e、名前空間の名前部分であるn、そして名前空間の値部分のvを引数にとって評価結果を返す。名前空間を(変数 . 値)のペアのリスト（association list）で表すのではなく、変数のリストのリストと値のリストのリストを別に保持している。（これはHenderson本に合わせた実装）
関数の中心は前述の通り式eに対するパターンマッチだ。
長くなるので今回の記事はREMまでの処理を解説する。IFによる条件分岐以降は次回に持ち越し。
シンボル
評価する式がシンボルだった場合、その内容がNILならそのままAlpha("NIL")というシンボルを返す（つまりNILは評価されてもNILのまま）。
case Alpha("NIL"): return e
NIL以外のシンボルは変数として、対応する値を名前空間から探して返す。名前空間の探索はassocというヘルパ関数に任せている。
case Alpha(s):
return assoc(e, n, v)
シンボル解決のヘルパ関数
assoc関数で変数を表すシンボルに対応する値を名前空間からとってくる：
def assoc(x, n, v): match n: case Alpha("NIL"): raise ValueError(f"Variable {x} not found") case Cons(n1, ns): if member(x, n1): return locate(x, n1, v.car) else: return assoc(x, ns, v.cdr) case _: raise ValueError(f"Invalid name list {n} passed to assoc")
nやvが名前や値の「リスト」ではなく「リストのリスト」であるのがポイント。LETや関数適用に入るたびにひとつ以上の変数束縛のある「環境」が名前空間に追加されていくので、assocもそれに対応する形でシンボル解決をする必要がある。
環境ひとつ分である「名前のリスト」にある変数が含まれているかを確認するmember関数と、変数に対応する値をとってくるlocate関数：
def member(x, n1): match n1: case Alpha("NIL"): return False case Cons(y, n2): return x == y or member(x, n2) def locate(x, n1, v1): if x == n1.car: return v1.car else: return locate(x, n1.cdr, v1.cdr)
数値
数値の場合は本シリーズの序でも書いた通り、タネ本から少し乖離して「評価されての数値のまま」という結果になるようにしてある。
case Num(_):
return e
QUOTE、ATOM
QUOTEは次の要素をそれ以上評価せずに結果として返す。
ATOMは次の要素が評価された結果がシンボルや数値であれば真、そうでなければ（Consなので）偽となる。
case Cons(Alpha("QUOTE"), Cons(e1, Alpha("NIL"))): return e1 case Cons(Alpha("ATOM"), Cons(e1, Alpha("NIL"))): match eval_(e1, n, v): case Alpha(_): return Alpha("T") case Num(_): return Alpha("T") case _: return Alpha("F")
ここでうっかりCons(Alpha("ATOM"), e1)としてしまうと(ATOM . e1)のようなドット付きリストに対するマッチになってしまうので注意。
ATOMの場合、引数であるe1をまず再帰的に評価（eval_(e1, n, v)）してその結果に対しパターンマッチしている。
リスト関係
リストを作るCONS、リストの先頭とそれ以外を取り出すCARとCDR：
case Cons(Alpha("CONS"), Cons(e1, Cons(e2, Alpha("NIL")))): return Cons(eval_(e1, n, v), eval_(e2, n, v)) case Cons(Alpha("CAR"), Cons(e1, Alpha("NIL"))): match eval_(e1, n, v): case Cons(e2, _): return e2 case e_: raise ValueError(f"Cannot take CAR of non-cons {e_}") case Cons(Alpha("CDR"), Cons(e1, Alpha("NIL"))): match eval_(e1, n, v): case Cons(_, e2): return e2 case e_: raise ValueError(f"Cannot take CDR of non-cons {e_}")
CONSは簡単だが、CARとCDRはそもそも対象がConsセルでなければエラーなので各ケースの中でさらにパターンマッチしている。
すべてのケースで、まずは引数を再帰的にeval_に渡しているのもポイント。
比較・算術演算子
比較用のEQ、LEQ、算術演算子のADD、SUB、MUL、DIV、REM：
case Cons(Alpha("EQ"), Cons(e1, Cons(e2, Alpha("NIL")))): return eq(eval_(e1, n, v), eval_(e2, n, v)) case Cons(Alpha("LEQ"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Alpha("T") if x <= y else Alpha("F")) case Cons(Alpha("ADD"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x+y)) case Cons(Alpha("SUB"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x-y)) case Cons(Alpha("MUL"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x*y)) case Cons(Alpha("DIV"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x//y)) case Cons(Alpha("REM"), Cons(e1, Cons(e2, Alpha("NIL")))): return numop(eval_(e1, n, v), eval_(e2, n, v), lambda x,y: Num(x%y))
比較も算術演算子もヘルパ関数を使って実装。
比較・算術演算子のヘルパ関数
EQだけは数値以外の要素も比較できるので、独自のヘルパ関数内で直接パターンマッチしている：
def eq(x, y): match x, y: case Num(n), Num(m): res = n == m case Alpha(s), Alpha(t): res = s == t case _: res = False return Alpha("T" if res else "F")
めんどくさいのでEQで比較して同値だと分かるのは数値とシンボルだけにしてある。Consセルに拡張するのもそう難しくはないが・・・（再帰するだけ）
LEQやADDなどの算術演算子は引数が両方Numであることを確認する必要があるのでnumopというヘルパ関数を使っている：
def numop(x, y, f): match x, y: case Num(n), Num(m): return f(n, m) case _: raise ValueError(f"Numeric op on non-numeric values {x} and {y}")
Numに対するパターンマッチだけnumopで抽象化して、実際の演算や結果はPythonの無名関数を引数として受け取っている。
今回（と次回）のコード
次回
次の記事ではIF、LET、LAMBDA、LETREC、関数適用の実装の紹介と、インタプリタが動いて「序」で紹介したユニットテストが通るところまで話す。
