僕の LISP 評価器が、順列生成を評価可能に

１１月１１日日曜日、晴れ

ようやく動くようになった……

文法解釈と実行までひととおり、そこそこの機能を備えた処理系をつくりあげたのはこれが初めてと言える、気がする。
（Brainf*ck でも順列生成くらいまでなら実行できるような気もする。とすればあれが初めてか？）

ツイッターで書いた「敗北感」は、僕が LISP の「評価」の仕組みを勘違いしていたこと。

＊　＊　＊

LISP の評価は、ある「環境」において、式がどのような値を取るかを計算することにある。「環境」とは「変数」とその「値」を結びつけた「辞書」のこと。例えば「Ｘ」は「２」、「Ａ」は「Ｘ＋８」みたいな関連付け。
こういった「環境」の上で「Ｘ＋３」という式を評価すると「５」という答えが出る。

そういうのが LISP の評価。

こういう評価システムで、たとえば先のツイートの添付画像のようなことができる。これは、与えられたリストに含まれる文字を並べ替えてできる全ての組み合わせを生成する「perm」にリスト「（１　２　３）」を与えて評価した結果。（組み込みの関数以外で必要になるすべての関数定義をした完全な例）

＊　＊　＊

なにを勘違いしていたか？

すべての評価は「式」と「環境」のペアを受け取り、結果の「式」と評価の結果（変化することもある）「環境」のペアを返すものだ、と考えたこと。

この「変化したかもしれない」環境をバトンリレーしていけば正しく評価できるものだと信じこんでいた。

でもそれではダメだった。

「lambda」式の評価では「環境」を閉じこむと言われるのだけれど、評価した瞬間の環境を覚えるのでなく、評価した時点の環境の「フレーム」を覚える必要があった。
もう少しいうと、 lambda を評価したあとで生じる環境の変化も追いかけられないといけない。

これは特に「再帰関数」を定義するときに重要。環境の変化を追いかけられないと、自分の定義を参照する「名前」が導入される「前」の環境を覚えることになる。つまり再帰しようとしても、自分の定義が環境の中にない。だから再帰しようにもできないということになる。

＊　＊　＊

もうひとつ、これは勘違いというか、理解ができていなかったこと。

関数適用は既存の環境の「上」に新たな「環境」をつくるものだった。

これは C 言語の関数呼び出しが、スタックの上にその関数用のスタックフレームを作ることに似ている。（ただし C 言語では、呼び出し元の関数内にある変数 ── レキシカルスコープ ── を参照することはできない）

変数を定義する「set」を除いて、すべての関数適用は純粋（ピュア）で、呼び出し元の環境を変化させない。

＊　＊　＊

この辺りの理解をもう一度咀嚼して、もう少し短く、わかりやすいコードを作りたいものだ。（今は完全に諦めて放置しているメモリー管理もあわせて）

＊　＊　＊

以下、まだ整理ができていないので master にマージしていない、先の「順列」生成を正しく評価できるようになったブランチ。（あ、でもこれ、マージしたら消すからリンクを書いたの拙かったかな……）

ryohji/ulisp

＊　＊　＊

冒頭の写真はレッスンの後、どんなフレーバーが残っているか楽しみにしながら行ったハグジードーナツに振られたときのものです。