LispKit Lisp処理系の実装 ３：インタプリタ〜条件分岐から関数適用まで
前回に続いてインタプリタの実装。今回はeval_の後半、IFによる条件分岐以降の項目を見ていく。
条件分岐のパターンマッチ
条件式を評価してその結果に対してパターンマッチ、分岐部分の式は片方しか評価されない。
case Cons(Alpha("IF"), Cons(e1, Cons(e2, Cons(e3, Alpha("NIL"))))): match eval_(e1, n, v): case Alpha("T"): return eval_(e2, n, v) case Alpha("F"): return eval_(e3, n, v) case v: raise ValueError(f"Non-boolean value {v} in if-condition")
条件式が真偽値じゃなければ実行時エラー。
無名関数
(LAMBDA ARG-LIST BODY-EXP)で無名関数が作れる。
case Cons(Alpha("LAMBDA"), Cons(e1, Cons(e2, Alpha("NIL")))): return Cons(Cons(e1, e2), Cons(n, v))
このインタプリタ内での関数の内部表現は((仮引数 . 本体の式) . (クロージャの名前部分 . クロージャの値部分))というネストしたドット付きリストになっている。関数オブジェクトとして特殊なデータタイプを用意するのではなく、あくまでシンボル、数値、Consセルの組み合わせで「評価済みの関数」を表現している。
ちなみにこの実装（Henderson本準拠）だとクロージャはCons(n, v)つまり「現在の名前空間すべて」になるので非常にメモリ効率が悪い。少し煩雑になるが本体の式の中の自由変数を検出してそれだけをクロージャとして捕捉する方が効率は良くなる。
LispKit LispにはSchemeのdefineのように名前付き関数を定義する構文はないので、関数を名前で呼び出したかったらLAMBDAで作った無名関数にLETなどで名前を束縛する必要がある。
変数束縛
前回も書いた通り、LispKit LispのLETでは、第二要素が本体の式、それ以降が変数と値のペアのリスト。
case Cons(Alpha("LET"), Cons(e1, e2)): n_ = Cons(vars_(e2), n) v_ = Cons(evlis(exprs(e2), n, v), v) return eval_(e1, n_, v_)
変数と値のペアのリストをヘルパ関数vars_とexprsを使って名前リストと値リストに分け、値リストの方はevlis関数でに評価してから名前空間に追加した上で本体の式を評価する。
def vars_(es): match es: case Alpha("NIL"): return Alpha("NIL") case Cons(Cons(n,v), es_): return Cons(n, vars_(es_)) case _: raise ValueError(f"Cannot get vars of {es}") def exprs(es): match es: case Alpha("NIL"): return Alpha("NIL") case Cons(Cons(n,v), es_): return Cons(v, exprs(es_)) case _: raise ValueError(f"Cannot get exprs of {es}") def evlis(es, n, v): match es: case Alpha("NIL"): return Alpha("NIL") case Cons(e, es_): return Cons(eval_(e, n, v), evlis(es_, n, v)) case _: raise ValueError(f"Cannot get evlis of {es}")
これらヘルパ関数はよくみると全部mapであることがわかる。Haskellっぽく書くとこんな感じ：
vars_ = map car exprs = map cdr evlis xs n v = map (\e -> eval_ e n v) xs
再帰的定義
LETRECはLETとあまり変わらない実装になっている：
case Cons(Alpha("LETREC"), Cons(e1, e2)): n_ = Cons(vars_(e2), n) v_ = Cons(Alpha("PENDING"), v) v_.car = evlis(exprs(e2), n_, v_) return eval_(e1, n_, v_)
やはり名前空間を適切に取り出すためにvar_とexprsを使って、evlisでexprsで取り出したものを評価している。
ただしLETに比べて、evlisで使う名前空間が拡張されている。名前のほうはvars_(e2)、値のほうはAlpha("PENDING")というダミー値を追加した上でevlisに渡している。そしてそのevlisの結果をv_のAlpha("Pending")部分を入れ替える形で破壊的代入している。
この「evlisに拡張した名前空間を渡す」「本体を評価する前に破壊的代入で名前空間を変更する」の二つが再帰を可能としているポイントとなる。
関数適用
LAMBDAの部分で書いた通り、関数部分であるe1を評価すると((仮引数 . 本体の式) . (クロージャの名前部分 . クロージャの値部分))という形になっているので、それをパターンマッチで解体して再帰的にeval_する。
case Cons(e1, e2):
match eval_(e1, n, v):
case Cons(Cons(args, e3), Cons(n_, v_)):
return eval_(e3, Cons(args, n_), Cons(evlis(e2, n, v), v_))
case e_:
raise ValueError(f"Non-function {e_} found at func position")
仮引数をクロージャの名前部分に追加、実引数のリストであるe2を評価した上でクロージャの値部分に追加、それらを名前空間として関数本体の式を評価して返す。
関数が再帰的かどうかは関係なく、まったく同じ処理で走る。再帰関数を作成するときに破壊的変更を使ってクロージャを再帰的にしてあることのメリットである。
ASTの文字列出力
llast.pyモジュールにto_string関数を追加しておく：
from dataclasses import dataclass @dataclass class Alpha: s : str @dataclass class Num: n : int @dataclass class Cons: car : any cdr : any def to_string(e): # 追加 match e: case Num(n): return str(n) case Alpha(s): return s case Cons(hd, tl): return f"({to_string(hd)}{to_string_tl(tl)})" def to_string_tl(tl): # 追加 match tl: case Alpha("NIL"): return "" case Cons(hd, tl1): return f" {to_string(hd)}{to_string_tl(tl1)}" case _: return f" . {to_string(tl)}"
やはりリストの取り扱いがちょっと特殊なのでその部分で相互再帰的になっている。
インタプリタを実行する
run関数で受け取る文字列をパース、空の名前空間で評価してから前述のto_string関数で文字列化している：
def run(s): return to_string(eval_(p.parse(s), Alpha("NIL"), Alpha("NIL")))
使ってみる
雑感
Pythonのパターンマッチ構文は便利なのだが、なんらかのオーバーロードとかマジックメソッド定義でConsセルをリストと見做してcase [Alpha("LAMBDA"), args, body]:と書けるようになったりしないだろうか。今回のコードに関して言えば可読性が相当向上する。
