SICPを読む(98) 問題 3.9 - 評価モデル

どうもSICPの評価モデルの解説が曖昧だ。返された値がどうなるかについて解説されていないので、おかしな図になってる。

Scheme実装中なので、僕の実装で書いてみよう。

問題 3.9

階乗の再帰と反復を環境モデルで表せ。という問題。

(factional 3)で先に反復を。

大域環境  +--------------------------
          |factional (lambda (n) ...
          |factiter (lambda (product counter max-count) ...
          +--------------------------
            V
          +-------+                                                 6
factional | n : 3 |
          +-------+                                                 A
            V                                                       |
          +-------------+   +-------------+   +-------------+   +-------------+
          |product  : 1 |   |product  : 3 |   |product  : 6 |   |product  : 6 |
factiter  |counter  : 1 | > |counter  : 2 | > |counter  : 3 | > |counter  : 4 |
          |maxcount : 3 |   |maxcount : 3 |   |maxcount : 3 |   |maxcount : 3 |
          +-------------+   +-------------+   +-------------+   +-------------+

となる。ポイントはreturnせず継続してるって所。

再帰のほうは、継続が無いとうまく説明出来ない。右に継続を出しておく。

大域環境  +--------------------------
          |factional (lambda (n) ...
          +--------------------------
             V
          +-------+
factional | n : 3 |
          +-------+
             V
          +-------+
factional | n : 2 | (lambda (a) (* 3 a))
          +-------+
             V
          +-------+
factional | n : 1 | (lambda (b) ((lambda (a) (* 3 a)) (* 2 b)))
          +-------+
             V
          +-------+
cont      | b : 1 | (lambda (b) ((lambda (a) (* 3 a)) (* 2 b)))
          +-------+
             V
          +-------+
cont      | a : 2 | (lambda (a) (* 3 a))
          +-------+
             V
大域環境     6

継続を実行するのは閉じ括弧が来たとき。

(* 3 (* 2 1...

となってて、閉じ括弧が

(* 3 (* 2 1)

お、継続を見よう。と思うわけ。

これでスッキリうまくいく。

ここに辿りつくまでが長かった・・・まだまだ先がありそうなんだよね。