SICP 読み (156) 4.1.2 式の表現

整理する必要あり、とは言え試験含め滅茶苦茶状態かも (を
とりあえず、eval と apply をきちんと理解するためのログを以下に。
まず eval ですが、現時点での実装が以下。

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
	((variable? exp) (lookup-variable-value exp env))
	((quoted? exp) (text-of-quotation exp))
	((assignment? exp) (eval-assignment exp env))
	((definition? exp) (eval-definition exp env))
	((if? exp) (eval-if exp env))
	((and? exp) (eval-and exp env))
	((or? exp) (eval-or exp env))
	((not? exp) (eval-not exp env))
	((lambda? exp)
	 (make-procedure (lambda-parameters exp)
			 (lambda-body exp)
			 env))
	((begin? exp)
	 (eval-sequence (begin-action exp) env))
	((cond? exp)
	 (eval (cond->if exp) env))
	((let? exp) (eval (let->combination exp) env))
	((let*? exp) (eval (let*->nested-let exp) env))
	((application? exp)
	 (apply (eval (operator exp) env)
		(list-of-values (operands exp) env)))
	(else
	 (error "Unknown expression type -- EVAL" exp))))

こーゆーの見てると短くできんかな、と思うな。等というヨタは置いといて整理を。
練習問題のソレを除くと試験で確認できてるのは単発の評価だけ。ただ、単発モノもきちんと理解できているか、というと微妙なので、まずそのあたりから始めてみる。
ざっくり大まかに分けるとすると

そのまんま (自己評価式、quote)
束縛 (define、set!、変数)
if (cond 含む)
and, or, not (真偽を戻す)
let
lambda
begin
手続き

という感じでしょうか。とりあえず上記について、どう評価されていくかを机上ベースで確認 (ちなみに一番てっぺんのヤツは略)。マシン確認できれば良いのでしょうが、これはこれで違う仕組みが必要なんでしょうか。

束縛 (variable)

このあたり、4.1.1 では完全スルーだったんですが、環境という概念が確立できてないとどうしようもない、という事だった模様。とりあえず symbol が eval された場合の処理から。
lookup-variable-value という手続きは環境の中で定義されている変数を走査する処理。最初のフレームに無ければ、その外側の環境から変数を探す。variable な試験は一つしか assert が無かったけれど、いくつか追加してみた。

   ("variable"
    (assert-equal #t (eval 'true the-global-environment))
;; add
    (assert-error (lambda () (eval 'x the-global-environment)))
    (let ((genv the-global-environment))
      (let ((new-env (extend-environment '(a b c)
					 '(1 2 3)
					 genv)))
	(let ((newest-env (extend-environment '(d e f)
					      '(4 5 6)
					      new-env)))
	  (assert-error (lambda () (eval 'a genv)))
	  (assert-error (lambda () (eval 'b genv)))
	  (assert-error (lambda () (eval 'c genv)))
	  (assert-error (lambda () (eval 'd genv)))
	  (assert-error (lambda () (eval 'e genv)))
	  (assert-error (lambda () (eval 'f genv)))
	  (assert-equal 1 (eval 'a new-env))
	  (assert-equal 2 (eval 'b new-env))
	  (assert-equal 3 (eval 'c new-env))
	  (assert-error (lambda () (eval 'd new-env)))
	  (assert-error (lambda () (eval 'e new-env)))
	  (assert-error (lambda () (eval 'f new-env)))
	  (assert-equal 1 (eval 'a newest-env))
	  (assert-equal 2 (eval 'b newest-env))
	  (assert-equal 3 (eval 'c newest-env))
	  (assert-equal 4 (eval 'd newest-env))
	  (assert-equal 5 (eval 'e newest-env))
	  (assert-equal 6 (eval 'f newest-env))
	  )
	)
      )
    )

環境というモノが階層関係になっている、と考えれば上位 (??) にある環境は探索できない、という事になりますが現在フレームがスタックのてっぺん、って考えれば上を見る必要はないのかな。

束縛 (assignment)

このあたりから合わせ技が出てくる模様。eval-assignment の手続きは以下。

(define (eval-assignment exp env)
  (set-variable-value! (assignment-variable exp)
		       (eval (assignment-value exp) env)
		       env))

既存の試験は define された変数に set! して値確認のみ。set-variable-value! は環境を順に見ていきつつ変数があれば値を設定、となっている。無ければ error。試験は新たに書こう。

   ("assignment (2)"
    (let ((genv the-global-environment))
      (let ((new-env (extend-environment '(a b c)
					 '(1 2 3)
					 genv)))
	(let ((newest-env (extend-environment '(d e f)
					      '(4 5 6)
					      new-env)))
	  (let f ((l '(a b c d e f)))
	    (cond ((null? l) 'ok)
		  (else
		   (let ((test (list 'set! (car l) '10)))
		     (assert-error (lambda () (eval test genv)))
		     (f (cdr l)))))
	    )

	  (let f ((l '(d e f)))
	    (cond ((null? l) 'ok)
		  (else
		   (let ((test (list 'set! (car l) '10)))
		     (assert-error (lambda () (eval test new-env)))
		     (f (cdr l)))))
	    )

	  (eval '(set! a 11) new-env)
	  (eval '(set! b 12) new-env)
	  (eval '(set! c 13) new-env)
	  (eval '(set! d 14) newest-env)
	  (eval '(set! e 15) newest-env)
	  (eval '(set! f 16) newest-env)

	  (assert-equal 11 (eval 'a new-env))
	  (assert-equal 12 (eval 'b new-env))
	  (assert-equal 13 (eval 'c new-env))
	  (assert-equal 11 (eval 'a newest-env))
	  (assert-equal 12 (eval 'b newest-env))
	  (assert-equal 13 (eval 'c newest-env))
	  (assert-equal 14 (eval 'd newest-env))
	  (assert-equal 15 (eval 'e newest-env))
	  (assert-equal 16 (eval 'f newest-env))
	  )
	)
      )
    )

しかし何故に環境一つあたり 3 つも変数定義するんだろうか。馬鹿みたい。書いた後で思う (正確には書いてる途中) あたり救いようが無い。
それは良いとして、スコープの外 (上の書き方で言えば上位の環境) で定義されている変数 (あるいは未定義な変数) に set! にいったらエラーになる。
で、ここで同名の変数が異る環境で定義されてるのもきちんと動くんだろうな、という事で試験。

   ("assignment (3)"
    (let ((genv the-global-environment))
      (let ((new-env (extend-environment '(a b c)
					 '(1 2 3)
					 genv)))
	(let ((newest-env (extend-environment '(c d e f)
					      '(4 5 6 7)
					      new-env)))
	  (eval '(set! c 44) newest-env)
	  (assert-equal 44 (eval 'c newest-env))
	  (assert-equal 3 (eval 'c new-env))

	  (eval '(set! c 10) new-env)
	  (assert-equal 44 (eval 'c newest-env))
	  (assert-equal 10 (eval 'c new-env))
	  )
	)
      )
    )

見事。動作としては当たり前なんですが、簡単に実現しちゃってるあたりが凄い。これ、gauche でも環境を手繰って変数がチェキできたら UT 楽なんだけどなぁ。多分ソース読めばリフレクション云々なあたりも理解できるのでは、と。
で、もう少し。eval-assignment では set-variable-value! の definition-value を eval してから渡している。set! の右辺値が値だけのはずはないですわな。例えば

(set! x (+ x 1))

なんて例は微妙かなぁ。これ、先に (+ x 1) が eval されて set-variable-value! に渡されるハズ。えーと (+ x 1) は application なので

(apply (eval (car '(+ x 1)) env)
       (list-of-values (cdr '(+ x 1)) env))

されて、まず最初の eval で the-global-environment に設定された基本手続きの手続きオブジェクトが戻る。これは

(primitive 手続きオブジェクト)

というリスト (4.1.4) になっている。
次に list-of-values で (x 1) の各要素がそれぞれ評価されてリストになる。x の値が 1 だったら (1 1) というリストになる、と。
で、これらが apply に渡されて、基本手続きなので apply-primitive-procedure により手続きが実行されて (以下略

   ("assignment (4)"
    (let ((genv the-global-environment))
      (let ((newenv (extend-environment '(x) '(1) genv)))
	(assert-true (primitive-procedure? (eval '+ newenv)))
	(assert-equal '(1 1) (list-of-values (cdr '(+ x 1)) newenv))
	(eval '(set! x (+ x 1)) newenv)
	(assert-equal 2 (eval 'x newenv))
	)
      )
    )

基本手続きではないナニが右辺にある場合の動作も見たい。例えば

(set! x ((lambda (x) (+ x 1)) x))

これ、しかも変数同じだけどスコープ違うってナニだな。体調微妙なので今日はここまで、なんですが、ちょっと微妙なソレに時間かけすぎな気もするなぁ。