続・LISP インタープリター

９月１７日月曜日、曇り時々小雨

なんとか評価器を作り上げるところまで、こぎつけました。

((lambda (x y) (cons y (cons x))) (quote world) (quote hello))

こんな S 式を「評価」すると、

(hello world)

とリストを返してくれる。

Merge branch 'feature/evaluation' 揃 ryohji/ulisp@aae43cb

どこかに間違いは残っているとおもうし、シンボルにマッピングした lambda 式の評価が動くかは未テストのため、怖さしかない。
けれど、まあよし。

＊　＊　＊

あとは構文解析器をつくって、標準入出力につないでループにすれば REPL の完成。

いやあ、まだ道は遠い。

＊　＊　＊

構文解析といえば。

そもそも、元の「小さな LISP インタープリター」の対象としていた LISP は、すべてのアトムが一文字であるというものだった。

小さな Lisp インタープリタ - Qiita

講演は通しで見ていないので大きなことは言えないんだけれど、一文字に限定するならもっと攻められるとおもうんだよね。後知恵、後知恵。

講演全編は以下の再生リストから見られる。（準備はしたけれど、未見）

1980年前後のLisp事情とUtiLisp - YouTube

この講演の #1 ８分終わりごろに文法が出てくる。

1980年前後のLisp事情とUtiLisp (1/11)

=: 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 は、すべてがバイナリーオペレーターで組みたてられた世界で、操作が前置される逆ポーランド文法だということ。

＊　＊　＊

逆ポーランド記法を使うと、操作が最初に確定するので処理効率がよいと教えられた、おぼろげな記憶がある。

けれど実際のところ、世界はバイナリーオペレーターであると確定しているなら、インフィックスだろうがポストフィックスだろうが、構文解析の難しさは変わらない　……かもしれない。（「すべての記号が一文字である」のように、すべての形態素解析が終了している前提で）

これは後日、ちゃんと時間をとって考えてみたい。