SchemeR_3_2.md

つくって学ぶプログラミング言語 3.2を理解しよう

与えられた式

[:let,
 [[:fact,
   [:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]]]]],
 [:fact, 1]]

1. letとlambdaは等価なのでlambda化する

[
 [:lambda, [:fact], [:fact, 1]],
 [:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]]]
]

※ばらすとこんな感じ(逆にわかりにくいかも)

[
 [:lambda,                                # <- ここからcar
  [:fact],    # <-carのlambdaの仮引数
  [:fact, 1]  # <-carのlambdaのbody
 ], 　                                    # <- ここまでcar
 [:lambda,                                # <- ここからcdr
  [:n],      # <- cdrのlambdaの仮引数
  [:if,      # ここからcdrのlambdaのbody
   [:<, :n, 1],                  # <- if式の条件
   1,                            # <- TRUE節
   [:*, :n, [:fact, [:-, :n, 1]  # <- FALSE節
  ]          # <- ここまでcdrのlambdaのbody
 ]                                        # <- ここまでcdr
]

2. carを評価 -> これがfun

[:lambda, [:fact], [:fact, 1]]

↓

[:closure, [:fact], [:fact, 1], [$global_env]]

(carはlambdaなのでそのときの環境と併せてclosure化する)

3. cdrを評価 -> これがargs

[:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]]]

↓

[:closure, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]], [$global_env]]

(この式ではcdrもlambdaなのでclosure化する)

4. fun(carの評価)にargs(cdrの評価)をapply

closureへのapplyとはつまり..
carのparameter [:fact] に
cdr[:closure, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]]
を束縛した環境を新しく作って...

[{:fact => [:closure, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1], [$global_env]]]]}, 
 $global_env]

carのbodyを実行

[:fact, 1]

5. :fact の実行

[[:closure, 
  [:n],
  [:if, [:<, :n, 1], 1, [:*, :n, [:fact, [:-, :n, 1]]]]}, 
  [$global_env]],
1]

6. 再度closureへのapply

[{:n => 1},
 $global_env]

という環境をつくって

[:if, [:<, :n, 1], 1], [:*, :n, [:fact, [:-, :n, 1]]]]

の実行

7. if式の評価

[:<, :n, 1]

でnを環境に見に行くと、6で束縛した1なので,

[:<, 1, 1]

はfalse。

8. false節の評価

[:fact, [:-, :n, 1]]

このときの環境は、6で作った

[{:n => 1}, $global_env]

なので、:fact がいない！

-> よってエラー