問題4-27〜28

SICP

｢4.2.2 遅延評価の解釈系｣では、合成手続きの引数は実際に必要とされるまで評価しない、ノンストリクトな正規順序的処理を行なうように自前評価器を改良します。applyの中で、procedureが合成手続きだったならば、渡された実引数にdelay-itしてthunk?というタグをつけてやります。そして、primitiveまで解析し終えた後、この時点では評価されていないprimitive-procedureに渡す引数をforce-itを呼び出して、引数の評価を行ないます。
問題4-27では、以下の対話がどのように行なわれているのかを解析します。

;;; L-Eval input:
(define count 0)

;;; L-Eval value:
ok

;;; L-Eval input:
(define (id x) (set! count (+ count 1)) x)

;;; L-Eval value:
ok

;;; L-Eval input:
(define w (id (id 10)))

;;; L-Eval value:
ok

;;; L-Eval input:
count

;;; L-Eval value:
1

;;; L-Eval input:
w

;;; L-Eval value:
10

;;; L-Eval input:
count

;;; L-Eval value:
2

まず、wをdefineする時に、以下の手続きを通ります。今回の場合だと、expは(define w (id (id 10)))になります。

(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (eval (definition-value exp) env)
                    env)
  'ok)

まずは、wをdefineした時の動きを時系列に書き出します。

  • (definition-variable exp)の結果はwで、(definition-varue exp)の結果は(id (id 10))となる。
    • この(id (id 10))が、まずはevalされる。
  • eval内の(application? exp)に引っかかり、applyが実行される。
    • applyの第一引数はidのforce-it/eval結果である(lambda (x) ( (set! count (+ count 1)) x))、第二引数は( (id 10))となる。
  • apply内では合成手続きなので、eval-sequenceが行なわれる。
    • eval-sequenceの第一引数expsには、( (set! count (+ count 1)) x)が渡される。また、第二引数であるenvには、extend-environmentされた環境が渡される。この時点で、delay-itされた( (id 10))が、lambda式の仮パラメータに割り当てられる。遅延処理しているので、評価自体は行なわれない。
    • eval-sequenceの実処理で、第一引数のexpsが一つずつevalされる。最初は、(set! count (+ count 1))がevalされる。set!はeval内で(assignment? exp)に引っかかり、(eval-assignment exp env)が呼び出され、countの値が更新される。(ここで、countが1になる)
    • expsの次の式はxで、次はこれがevalされる。xはdelay-itされた(id 10)なので、force-itされない限り評価は実行されない。だから、ここでは何も起こらない。(作用的順序で評価される場合は、この(id 10)もここで評価が実行されて、countが2に更新されると思われる)
  • これで、eval-definitionの処理が完了する。wには、(thunk (id 10))が束縛されていることになる。

次は、wを作用させた時の動きです。

  • 評価器の入力値としてwを与えると、まずは、(actual-value exp env)が行なわれ、このexpにwが引き当てられる。
    • actual-valueの実体は、(force-it (eval exp env))なので、まずはexpであるwがevalされ、lookup-variable-valueによって、(thunk (id 10))が返ってくる。
    • 次に、(thunk (id 10))がforce-itされる。すると、thunkタグが外された結果である(id 10)がacutual-valueに渡され、ここでevalが行なわれる。このeval処理で、countが2に更新される。

最後に、もう一度wを作用させてみました。

  • もう一度wを入力してみると、countが3に更新される。これは、wが(thunk (id 10))に束縛されたままであり、wを作用されるたびに、(id 10)が呼び出されるからだと思われる。(作用的順序の場合は、wは10に束縛されるから、何度wを作用させても、countが更新されることはない)

ここまでじっくりと自前評価器の動きをトレースしたことはなかったので、とても良い勉強になりました。
問題4-28。本文では、applyの第一引数で、式の演算子を渡すわけですが、それを行なう前にevalではなくactual-valueを実行しています。問題4-27のようなケースだと、ここに到達している処理でthunkタグがついていることはなかったのですが、そうではないケースもあるということなのでしょう。しかし、それがどういうケースなのかという点までは考えられていません。