SICP問題4.27 - tmurataの日記

入力に対する応答内容を答える問題。
"← 応答"となっている部分が解答。

(define count 0)
(define (id x)
  (set! count (+ count 1))
  x)
(define w (id (id 10)))
;;; L-Eval input:
count
;;; L-Eval value:
1 ;; ← 応答
;;; L-Eval input:
w
;;; L-Eval value:
10 ;; ← 応答
;;; L-Eval input:
count
;;; L-Eval value:
2 ;; ← 応答

このままでは訳が分からないので、実行環境がどうなっているかを確認する。分かりやすくするため、thunkのメモ化は行っていない状態で確認する。
まずはcount, idの定義。

(define count 0)
(define (id x)
  (set! count (+ count 1))
  x)

the-global-environmentの内容は以下のとおり。

#0=(((id count false true car cdr cons null? = + - *) (procedure (x) ((set! count (+ count 1)) x) #0#) 0 #f #t (primitive #<subr car>) (primitive #<subr cdr>) (primitive #<subr cons>) (primitive #<subr null?>) (primitive #<subr =>) (primitive #<subr +>) (primitive #<subr ->) (primitive #<subr *>)))

id が

(procedure (x) ((set! count (+ count 1)) x) #0#)

countが

として登録されている。

次にwの定義。

(define w (id (id 10)))

the-global-environmentの内容は以下のとおり。

#0=(((w id count false true car cdr cons null? = + - *) (thunk (id 10) #0#) (procedure (x) ((set! count (+ count 1)) x) #0#) 1 #f #t (primitive #<subr car>) (primitive #<subr cdr>) (primitive #<subr cons>) (primitive #<subr null?>) (primitive #<subr =>) (primitive #<subr +>) (primitive #<subr ->) (primitive #<subr *>))
)

id が

(procedure (x) ((set! count (+ count 1)) x) #0#)

countが

wが

(thunk (id 10) #0#)

となっている。これは以下のような流れになっていると考えられる。

(define w (id (id 10)))

がevalに渡されると、definition?がtrueとなり

(eval-definition (define w (id (id 10))) env)

が実行される。eval-definitionでは

(define-variable! w
                  (eval (id (id 10)) env)
                  env)

が実行される。evalのcond節でapplication?がtrueとなるため

(define-variable! w
                  (apply (actual-value id env)
                         ((id 10))
                         env)

が実行される。actual-valueは更に

(define-variable! w
                  (apply (force-it (eval id env))
                         ((id 10))
                         env))

となる。ここで(eval id env)はvariable?がtrueとなりlookup-variable-valueで環境から検索され

(define-variable! w
                  (apply (force-it (procedure (x) ((set! count (+ count 1)) x) env))
                         ((id 10))
                         env))

となる。force-itの引数 (procedure〜はthunkではないので、force-itでそのまま返され

(define-variable! w
                  (apply (procedure (x) ((set! count (+ count 1)) x) env)
                         ((id 10))
                         env))

となる。
applyのcond節ではcompound-procedure?がtrueとなるため

(eval-sequence
  (procedure-body (procedure (x) ((set! count (+ count 1)) x)))
  (extend-environment
    (procedure-prameters (procedure (x) ((set! count (+ count 1)) x)))
    (list-of-delayed-args ((id 10)) env)
    (procedure-environment (procedure (x) ((set! count (+ count 1)) x)))))

が実行される。これは

(eval-sequence
  ((set! count (+ count 1)) x)
  (extend-environment
    (x)
    ((thunk (id 10) env))
    env))

となる。eva-sequenceでは

(eval (first-exp ((set! count (+ count 1)) x))
      (extend-environment (x) ((thunk (id 10) env)) env))
(eval-sequence (rest-exp ((set! count (+ count 1)) x))
               (extend-environment (x) ((thunk (id 10) env)) env))

が順番に実行される。最初のevalによってcountが+1される。
次のeval-sequenceはlast-exp?がtrueとなるため

(eval (first-exp (x))
      (extend-environment (x) ((thunk (id 10) env)) env))

となる。evalではvariable?がtrueとなるため、lookup-variable-valueが実行され、環境に登録された(thunk (id 10))が返され、これがeval-sequenceの結果となる。

長くなったけど、結論。
defineが実行された時点で(id (id 10))の外側のidが評価され、countの値が+1される。
内側の(id 10)についてはthunk化されるだけで実行されない。
よってwの定義時点でcountは1となる。

wを実行した際にはthunkが評価され、countが+1された後、引数の10を返す。よってこの後countを確認すると2が返って来る。

ちなみにメモ化していない版の場合、これ以降もwを実行する度にcountの値は+1されて変化し続けるが、メモ化している場合は最初のwを実行した後はthunkからevaluated-thunkに変換され、評価が行われなくなるため値は2から変化しなくなる。