続・LISP インタープリター
９月１７日月曜日、曇り時々小雨
なんとか評価器を作り上げるところまで、こぎつけました。
((lambda (x y) (cons y (cons x))) (quote world) (quote hello))こんな S 式を「評価」すると、
(hello world)
とリストを返してくれる。
どこかに間違いは残っているとおもうし、シンボルにマッピングした lambda 式の評価が動くかは未テストのため、怖さしかない。
けれど、まあよし。
＊ ＊ ＊
あとは構文解析器をつくって、標準入出力につないでループにすれば REPL の完成。
いやあ、まだ道は遠い。
＊ ＊ ＊
構文解析といえば。
そもそも、元の「小さな LISP インタープリター」の対象としていた LISP は、すべてのアトムが一文字であるというものだった。
講演は通しで見ていないので大きなことは言えないんだけれど、一文字に限定するならもっと攻められるとおもうんだよね。後知恵、後知恵。
講演全編は以下の再生リストから見られる。（準備はしたけれど、未見）
この講演の #1 ８分終わりごろに文法が出てくる。
=: set, ': quote, #: lambda, ?: cond, @: atom, +: cons, <: car, >: cdr
これら特殊形式もすべて一文字なので、あとは nil を示す記号を一文字で定めると、 LISP の特徴である () が不要になるのではないか？ という妄想。
＊ ＊ ＊
スライドでは以下のコードが示されている。
(=('A)(#(XY)(?((@X)Y)(T(+(<X)(A(>X)Y))))))すべてが一文字という縛りがあるので、空白なしに記号の区切りを解釈できるのである。つまり（ＡＢＣ）は、ＡとＢとＣ、三つの記号からなるリストですよと、誤解なく解釈できる。
LISP の別の約束として、リストはリスト終端を示す記号（）に、記号を一つずつ左に足したもの、というものがある。つまり（ＡＢＣ）は単なる略記法で、正式には（Ａ（Ｂ（Ｃ（））））と書くものである。
「組」を作る操作を cons （construct）と呼んでいて、 cons(Ｃ, （）)が（Ｃ（））に等しい。
だから（Ｂ（Ｃ（）））は cons(Ｂ, cons(Ｃ,（）)) ということになる。同様に（Ａ（Ｂ（Ｃ（））））は cons(Ａ, cons(Ｂ, cons(Ｃ,（）))) になる。
さて、一文字という文法と cons は + だということを思いだすと cons(Ａ, cons(Ｂ, cons(Ｃ,（）))) は +A+B+C（）となる。そして終端（）を $ と表すことにしてみると +A+B+C$ が（ＡＢＣ）だ。
この方式で先のスライドのコードを書き直してみると、……
+=++'+A$++#++X+Y$++?++@+X$Y$+T+++<+X$+A+>+X$Y$$$$$$こうなる。
いや、読めない！ 読めないね！（笑）
＊ ＊ ＊
知っている人は知っている、これは「逆ポーランド記法」と呼ばれるものだ。
LISP は、すべてがバイナリーオペレーターで組みたてられた世界で、操作が前置される逆ポーランド文法だということ。
＊ ＊ ＊
逆ポーランド記法を使うと、操作が最初に確定するので処理効率がよいと教えられた、おぼろげな記憶がある。
けれど実際のところ、世界はバイナリーオペレーターであると確定しているなら、インフィックスだろうがポストフィックスだろうが、構文解析の難しさは変わらない ……かもしれない。（「すべての記号が一文字である」のように、すべての形態素解析が終了している前提で）
これは後日、ちゃんと時間をとって考えてみたい。