[SICP] 4 超言語的抽象 - 1 - - 新千葉ガーベージ・コレクション

ここのポイントは scheme を scheme でつくること。その中心が eval だ。折角なので lisp で再度（２度目、、、）作ってみる。scheme を scheme でつくると SICP にあるように

(define (eval exp env)
    (cond ((self-evaluating? exp) exp)
          ....

と続くことになる。scheme ではキーワードにシンボルを使い例えば 'lambda で始まるものを lambda 式だと定義している。

仕様：ある特別な内部状態がある場合、それを 'lambda などシンボルで始まる式とする。
例：例えば (set! var value) なら、それは 'set! ではじまる。わかりづらいが、lisp ではそもそも '(set! a b) とかけば最初の set! はシンボルだ。(symbolp (car '(set! a b))) は T だ。

すごくわかりづらいが、、、(setf line (read)) と S 式を読み込み、(a 3 4) とうちこめば、'(a 3 4) が line に入る。そして、(symbolp (car line)) とすれば、T だ。しかし 3 は数字なので (symbolp (cadr line)) は NIL だ。

これだとかなりわかりづらくなる。例えば cl-who では HTML を S 式で表すのに : をつかっている。例えば (:H1 "タイトル") みたいにしてつかう（うろおぼえ）。ここでは実験的に : を使って意味をわかりやすくする。例えば (set! v 3) は (:set! v 3) だ。これで、なんとなくわかりやすくなったが、余計な : がつく。:set! もシンボルだから基本的には変わらない。

で、その先にいけるかというと env という環境の仕様をちゃんと決めないと、その先にいけない。環境は入れ子になる。したがって、とある env は (env-n .... env-2 env-1 env-0) となる。env-n から一つ一つ環境を見る。各 env-n は線形に scan しやすいように

((key0 key1 key2) (v0 v1 v2))

という構造をとっている。つまり key0 と v0 が対応している。ある環境に (set! x 3) とすれば

((x key0 key1 key2) (3 v0 v1 v2))

となるわけだ。これは要は key と value の組み合わせテーブルだ。

仕様：環境はリストになっている。先頭から検索される。各環境は map を実現するために

((x key0 key1 key2) (3 v0 v1 v2))

という構造になっている。

これを互いに呼び出す内部関数で検索するには次のようにすればよい。

(defun lookup-variable-value (var env)
  (labels ((env-loop (env)
                     ;(debug-trace (format t "lvv env-loop ~a~%" env))
                     (if (eq env the-empty-environment)
                       (format t "Unbound variable ~a~%" var)
                       (let ((frame (first-frame env)))
                         (scan (frame-variables frame) (frame-values frame) env
                               ))))
           (scan (vars vals env)
                 ;(debug-trace (format t "scan ~a ~a~%" vars vals))
                 (cond ((null vars)
                        (env-loop (enclosing-environment env)))
                       ((eq var (car vars))
                        (car vals))
                       (t (scan (cdr vars) (cdr vals) env)))))
    (env-loop env)))

env-loop が各環境をひとつずつひも解いていく。そして、scan でひとつひとつ線形検索をする。(scan '(a b c) '(1 2 3) env) で、検索対象が b なら scan は２度目の呼び出しで (scan '(b c) '(2 3) env) になり b にヒットしてその値である 2 がかえる。もし検索対象が x ならこの環境には無いので env をつかって、env-loop を呼び出す。env-loop は環境がまだあれば再び scan を呼び出す。

lisp で作るときに"わざわざ" SICP の実装をそのまま持ってくる必要もないし、そうすることでの可読性も下がるのでハッシュテーブルを使うというのも手だ。

(defun lookup-variable-value (key env)
  (if (null env) (format "Unbound variable ~a" key)
    (multiple-value-bind (value present) (gethash key (car env))
      (if present value
        (lookup-variable-value key (cdr env))))))