SICP 読み (185) 4.2.2 遅延評価の解釈系

再帰、ってどうなんだろうか。例えば簡単な例で以下。

(define (f x)
  (if (= 0 x)
      0
      (+ x (f (- x 1)))))
(f 5)

最初の式は define 認定。こんな感じか。

(define-variable! f (procedure (x) ((if (= 0 x) 0 (+ x (f (- x 1)))))))

はしょり過ぎ。とりあえず f には手続きが束縛されている状態。(f 5) は apply の中で compound-procedure 認定。こんな感じになる。

(eval-sequence
 ((if (= 0 x) 0 (+ x (f (- x 1)))))
 (extend-environment '(x) '(thunk 5 env) env))

うーん。駄目っぽい。map はどうか。

(define (map p l)
  (if (null? l)
      '()
      (cons (p (car l))
	    (map p (cdr l)))))

(map (lambda (x) (* x x)) (list 1 2 3 4 5))

map に束縛される式は以下で良いか。

(procedure 
 (p l) 
 ((if (null? l) '() (cons (p (car l)) (map p (cdr l))))) 
 env)

で、次の式 (map (lambda (x) (* x x)) (list 1 2 3 4 5)) を評価。

(eval-sequence
 ((if (null? l) '() (cons (p (car l)) (map p (cdr l)))))
 (extend-environment
  (p l)
  ((thunk (lambda (x) (* x x)) env) (thunk (list 1 2 3 4 5) env))
  env))

これは面倒臭そう。(を

つづき (map)

上記の式を評価するんですが、評価する式は if 認定で

• p は (thunk (lambda (x) (* x x)) env) に束縛
• l は (thunk (list 1 2 3 4 5) env) に束縛

になる。あまり環境に注意を払わず確認してるんですが良いんだろうか。if 認定な式は eval-if に渡されて、条件部分が actual-value で評価。(null? l) は application 認定。以下の式で評価される。

(apply (actual-value null? env)
       (l)
       env)

null? は primitive-procedure 認定。以下の式が評価されて戻る。

(apply-primitive-procedure null?
			   (list-of-arg-values (l) env))

成程。ここで l に束縛されている thunk な式がきちんと評価される訳か。順番としては l が actual-value に渡されて

(actual-value l env)

l が eval されて (thunk (list 1 2 3 4 5) env) になったナニを force-it するんですが、メモ化版でない force-it の場合は thunk 認定したら再度 (list 1 2 3 4 5) と env を actual-value に渡します。
で、(list 1 2 3 4 5) が env な環境で評価されて '(1 2 3 4 5) が戻ってくる、という事で正しいはず。
で、(null? '(1 2 3 4 5)) が評価されて #f が戻る。eval-if では alternative なブロックのソレが評価されるので

(eval (if-alternative exp) env)

を評価する事になります。その式を置き換えると以下ですか。

(eval (cons (p (car l)) (map p (cdr l))) env)

ここでの env は l も p も解決できるナニ。だんだん面倒になってきましたが、我慢して続ける。
この式は application 認定でしかも primitive な手続き。引数は delay されない。eval された結果なソレが以下。

(apply-primitive-procedure
 cons
 (list-of-arg-values ((p (car l)) (map p (cdr l))) env))

で、cons に渡す前に list-of-arg-values が引数を処理。これは見るからに大変そう。先頭から順に actual-value に渡していきますので最初は以下。

(actual-value (p (car l)) env)

ちなみに env は p も l も解決可能。って thunk なリストなんだろうな。まず引数の式が env な環境で eval される。(p (car l)) は application 認定。

(apply (actual-value p env)
       ((car l))
       env)

p が eval されて force-it に渡されるので (lambda (x) (* x x)) が戻るな。あ、違うや。lambda 式を さらに eval したソレが戻る。

(procedure (x) ((* x x)) env)

みたいな感じが戻るのか。compound-procedure 認定なんで

(eval-sequence
 ((* x x))
 (extend-environment
  (x)
  (list-of-delayed-args ((car l)) env)
  env))

ッスか。なるほど、これは引数が delay されるんだな。l も delay されてるハズなんですが、大丈夫なんだろうか。以前にも l は force-it されてますが、あれは if の条件式なソレだったという事で再度、になる訳か。メモ化していればこの辺のナニが DRY なソレにのっとって (以下略
という事で、x は (thunk (car l) env) に束縛される、と。env は p とか l が解決可能な環境で良いはず。
次はその環境で (* x x) を eval しますが、これは application 認定の上に primitive-procedure 認定。微妙にスルーしてしまうんですが、以下。

(apply-primitive-procedure
 *
 (list-of-arg-values (x x) env))

繰り返しになりますが、ここでの env は p も l も x も解決可能。同じ変数を、なんですがメモ化でないソレでは yourself を repeat するはず。それは良いとして具体的にどなのか、が以下。リストの先頭を処理。

(actual-value x env)

まず x が eval されて force-it に渡される。x は (thunk (car l) env) に束縛されております。

(force-it (thunk (car l) env))

上記の env は少なくとも l の解決は可能なはず。とりあえず force-it でカワを一枚ムイで再度 actual-value される。

(actual-value (car l) env)

これは (car l) を eval したナニが戻るな。ただ、l が actual-value されて、最終的に '(1 2 3 4 5) が戻ってくるんですが、これは repeat yourself なソレ。で、このリストが car されて 1 が戻る、と。
を、これで (* 1 1) が戻るな。ようやく cons の最初の引数が値になった。まだまだ先は長いんですが、そろそろ限界 (何

もすこし頑張ってみる

cons に渡る二番目の引数は以下。

(actual-value (map p (cdr l)) env)

これが cons に、なんですが map は合成手続きだから delay されるハズ。違うかな。
あ、違うや、map の引数が delay されるんだ。とりあえず上記の actual-value に渡された手続きは primitive な手続きに渡されたナニなんで actual-value に渡されたのを遡って確認。
てーコトは、まず eval するのか。これは applicatin 認定だな。

(apply (actual-value map env)
       (p (cdr l))
       env)

map は遥か彼方の上の方で合成手続きが束縛されております。なので application な上に compount-procedure 認定。apply は以下のソレを適用。

(eval-sequence
 ((if (null? l) '() (cons (p (car l)) (map p (cdr l)))))
 (extend-environment
  (p l)
  (list-of-delayed-args ((lambda (x) (* x x)) (cdr l)) env)
  env))

げ。ここの l は (list 1 2 3 4 5) で良いのかなぁ。まだ大丈夫か。引数に束縛されるナニは delay されるのか。てコトは p とか l に束縛されるのを鑑みると以下か。

(eval-sequence
 ((if (null? l) '() (cons (p (car l)) (map p (cdr l)))))
 (extend-environment
  (p l)
  ((thunk (lambda (x) (* x x)) env) (thunk (cdr l) env)))
 env)

ははー。eval-if で条件式を actual-value するのは then 又は else のナニまで戻すという意図があるのか。上記の eval-sequence では

(cons (p (car l)) (map p (cdr l)))

が eval されて戻るな。cons は primitive なソレなので、引数は delay されない。

冷静に戻る

これって最後までトレイスしないとオワらんじゃねーか、という事に気づく。問題の主旨って_合成手続きの引数に thunk なソレ (これは合成手続きが apply された時に引数が delay される、という仕様に基く) があるからきちんと解決しなければならない_という事だったんだ。
本当かなぁ。これがダウトだったら微妙。ただ、ここまでだらだらトレイスを続けてきた中で答えが出ているはず。

補足

p を解決する部分ですか。もの凄くスルー気味な書き方しててヘコむなぁ。
一応次の問題の糸口も見えてはいるのでヨシとしたいんですが微妙。