SICP 読み (167) 4.1.6 内部定義

ええと、日曜日のエントリでも色々確認してるんですが、カブるのを恐れず再確認。もう少し色々確認する必要あり、ではないかと。
とりあえず机上トレースなソレとして以下の式をナニ。

(let ((env the-global-environment))
  (eval '(define (f x)
	   (define (even? n)
	     (if (= n 0)
		 true
		 (odd? (- n 1))))
	   (define (odd? n)
	     (if (= n 0)
		 false
		 (even? (- n 1))))
	   (even? n))
	env)
  (eval '(f 2) env)
  )

define

まず define なんですが、definition 認定で

(eval-definition '(define (f x)
		    (define (even? n)
		      (if (= n 0)
			  true
			  (odd? (- n 1))))
		    (define (odd? n)
		      (if (= n 0)
			  false
			  (even? (- n 1))))
		    (even? n))
		 env)

という形に。次に eval-definition にて

(define-variable 'f (eval '(lambda (x)
			     (define (even? n)
			       (if (= n 0)
				   true
				   (odd? (- n 1))))
			     (define (odd? n)
			       (if (= n 0)
				   false
				   (even? (- n 1))))
			     (even? n)) env) env)

という形に。ちなみに上記のナニは以下で確認。

    (let ((l '(define (f x)
		(define (even? n)
		  (if (= n 0)
		      true
		      (odd? (- n 1))))
		(define (odd? n)
		  (if (= n 0)
		      false
		      (even? (- n 1))))
		(even? n))))
      (assert-equal 'f (definition-variable l))
      (assert-equal '(lambda (x)
		       (define (even? n)
			 (if (= n 0)
			     true
			     (odd? (- n 1))))
		       (define (odd? n)
			 (if (= n 0)
			     false
			     (even? (- n 1))))
		       (even? n))
		    (definition-value l))

      )

で、define-variable! な引数の

(eval '(lambda (x)
	 (define (even? n)
	   (if (= n 0)
	       true
	       (odd? (- n 1))))
	 (define (odd? n)
	   (if (= n 0)
	       false
	       (even? (- n 1))))
	 (even? n)) env)

がどうなるか、というと eval 中で lambda 認定されて以下の手続きが適用される模様。

(make-procedure '(x)
		'((define (even? n)
		    (if (= n 0)
			true
			(odd? (- n 1))))
		  (define (odd? n)
		    (if (= n 0)
			false
			(even? (- n 1))))
		  (even? n))
		env)

この結果どうなるか、なソレが以下。

    (let ((l '(lambda (x)
		(define (even? n)
		  (if (= n 0)
		      true
		      (odd? (- n 1))))
		(define (odd? n)
		  (if (= n 0)
		      false
		      (even? (- n 1))))
		(even? n))))
      (assert-equal '(x) (lambda-parameters l))
      (assert-equal '((define (even? n)
			(if (= n 0)
			    true
			    (odd? (- n 1))))
		      (define (odd? n)
			(if (= n 0)
			    false
			    (even? (- n 1))))
		      (even? n))
		    (lambda-body l))
      (let ((l2 (make-procedure (lambda-parameters l)
				(lambda-body l)
				the-global-environment)))
	(assert-equal 'procedure (car l2))
	(assert-equal '(x) (cadr l2))
	(assert-equal (lambda-body l) (caddr l2))
	)
      )

(procedure (x) ((define (even? n) ....))) なリストができ上がる、と。
ちなみに scan-out-defines を make-procedure に組み込んだ場合、

	(assert-equal (lambda-body l) (caddr l2))

な assert は (scan-out-defines (lambda-body l)) になるはずなので失敗するはず。scan-out-defines が make-procedure に組込まれていた場合には、この時点で環境をはしょると以下のようなリストになっている模様。

(procedure (x) (let ((even? *unassigned*)
		     (odd? *unassigned*))
		 (set! even? (lambda (n)
			       (if (= n 0)
				   true
				   (odd? (- n 1)))))
		 (set! odd? (lambda (n)
			      (if (= n 0)
				  false
				  (even? (- n 1)))))
		 (even? n)) env)

一応確認しとくか。微妙に中略しております。

    (let ((l '(lambda (x)
		(define (even? n)
		  (if (= n 0)
		      true
		      (odd? (- n 1))))
		(define (odd? n)
		  (if (= n 0)
		      false
		      (even? (- n 1))))
		(even? x))))

      (let ((l3 '(let ((even? '*unassigned*)
		       (odd? '*unassigned*))
		   (set! even? (lambda (n)
				 (if (= n 0)
				     true
				     (odd? (- n 1)))))
		   (set! odd? (lambda (n)
				(if (= n 0)
				    false
				    (even? (- n 1)))))
		   (even? x))))

	(assert-equal l3 (scan-out-defines (lambda-body l)))
	)
      )

とりあえず procedure で始まるリストが f に束縛されて終わります。手続き本体についても上記の通り scan-out-defines が make-procedure に組込まれていれば let で始まるリスト (上記 l3) になるし、そうでなければ

((define (even? n) ... )
 (define (odd? n) ... )
 (even x))

というリストになっている、と。

apply

次は define したソレを動かしてみる場合のソレ。まず、(f 2) というナニは application 認定されますので以下の手続きが適用される模様。

(apply (eval 'f env) '(2) env)

根拠は以下。

   ("trace (apply)"
    (let ((env (extend-environment '(f)
				   (list
				    (eval '(lambda (x)
					     (define (even? n)
					       (if (= n 0)
						   true
						   (odd? (- n 1))))
					     (define (odd? n)
					       (if (= n 0)
						   false
						   (even? (- n 1))))
					     (even? x))
					  the-global-environment))
				   the-global-environment)))
      (let ((exp '(f 2)))
	(assert-equal 'f (operator exp))
	(assert-equal '(2) (list-of-values (operands exp) env))
	)
      )
    )

で、(eval 'f env) したら procedure で始まるリストが戻るはず。

      (assert-equal 'procedure (car (eval 'f env)))

ってこの試験微妙だな。再作成。

   ("trace (apply-R)"
    (let ((env (extend-environment '(tmp) '(0) the-global-environment)))
      (eval '(define (f x)
	       (define (even? n)
		 (if (= n 0)
		     true
		     (odd? (- n 1))))
	       (define (odd? n)
		 (if (= n 0)
		     false
		     (even? (- n 1))))
	       (even? x)) env)
      (let ((exp '(f 2)))
	(assert-equal 'f (operator exp))
	(assert-equal '(2) (list-of-values (operands exp) env))
	)
      (assert-equal 'procedure (car (eval 'f env)))
      )
    )

この方が信頼性高そげ。で apply に渡った後のソレを動作確認。

      (assert-true (compound-procedure? (eval 'f env)))
      (assert-equal '((define (even? n)
			(if (= n 0)
			    true
			    (odd? (- n 1))))
		      (define (odd? n)
			(if (= n 0)
			    false
			    (even? (- n 1))))
		      (even? x))
		    (procedure-body (eval 'f env)))
      (assert-equal '(x) (procedure-parameters (eval 'f env)))

先の試験の直後に上記を追加し、確認。とりあえず (apply '(f 2) env) は compound-procedure 認定され、

(eval-sequence '((define (even? n)
		   (if (= n 0)
		       true
		       (odd? (- n 1))))
		 (define (odd? n)
		   (if (= n 0)
		       false
		       (even? (- n 1))))
		 (even? x))
	       (extend-environment '(x) '(2) env))

が適用されるんですが、ここで手続きを取り出すために使用されているのが procedure-body です。scan-out-defines が組込まれていればここで let なソレに変換されて eval-sequence に渡される、と。

む

なんかカン違いしてないか??

((define (even? n) 
   (if (= n 0) true (odd? (- n 1)))) 
 (define (odd? n) 
   (if (= n 0) false (even? (- n 1))))
 (even? x))

なリストが

(let ((even? '*unassigned*)
      (odd? '*unassigned*))
  (set! even? (lambda (n)
		(if (= n 0) true (odd? (- n 1)))))
  (set! odd? (lambda (n)
	       (if (= n 0) false (even? (- n 1)))))
  (even? x))

に変換されて良いのかなぁ。eval-sequence に渡った時に大変なコトになりそう。

再開

上記はビンゴと見ても、どっちでどう、というのが明確にイメージできん。踏み込みが足りないのかなぁ。面倒臭いから組み込んで試験した方が良さげ。

む

ちょっと確認。

   ("lambda-body?"
    (let ((l '(lambda (x)
		(define (even? n)
		  (if (= n 0)
		      true
		      (odd? (- n 1))))
		(define (odd? n)
		  (if (= n 0)
		      false
		      (even? (- n 1))))
		(even? x))))
      (assert-equal '((define (even? n)
			(if (= n 0)
			    true
			    (odd? (- n 1))))
		      (define (odd? n)
			(if (= n 0)
			    false
			    (even? (- n 1))))
		      (even? x))
		    (lambda-body l)) 
      )
    (let ((l '(lambda (x)
		(let ((even? '*unassigned*)
		      (odd? '*unassigned*))
		  (set! even? (lambda (n)
				(if (= n 0)
				    true
				    (odd? (- n 1)))))
		  (set! odd? (lambda (n)
			       (if (= n 0)
				   false
				   (even? (- n 1)))))
		  (even? x)))))
      (assert-equal '((let ((even? '*unassigned*)
			    (odd? '*unassigned*))
			(set! even? (lambda (n)
				      (if (= n 0)
					  true
					  (odd? (- n 1)))))
			(set! odd? (lambda (n)
				     (if (= n 0)
					 false
					 (even? (- n 1)))))
			(even? x)))
		    (lambda-body l))
       )
    )

うーん。だんだんワケワカになりつつある。酒呑んでヤッちゃ駄目だ。
ちょっと違う意味でツカれてます。

って、やっぱり現状の scan-out-defines が微妙なんだろうか。糸口がこのあたりにあれば嬉しいんですが、そうでなかったら降参かも。