SICP 3.2 The Environment Model of Evaluation
Evaluationは評価だが要はプログラムの実行の事。なのでプログラム実行の為の環境モデル。実行と言っている時点で命令型な考え方だけど。置換モデルはあくまでそう解釈出来ると言う意味で概念的なので具体的にコンピュータがどう動作するのかをイメージしようとする人にはかえって理解しにくいかも知れない。一方、環境モデルは実際にコンパイラやインタープリタがプログラムを解釈・実行する状況を説明しているので、そう言った意味では分かりやすい。
ノート
1.1.5節で説明した『引数に手続きを適用する』と言う言葉の意味を置換モデルで解釈する事は、一度代入を導入すると適切ではなくなる。代入が存在する場合、変数は値につけた名前ではなく値を保存する場所につけた名前。今後このような値を保存する場所(の集合)を環境と呼ぶ。
環境は一連のフレームからなる。フレームは拘束、つまり名前とその値の対応の表。フレームはまたその外側の環境へのポインタを持つが、グローバルと呼ばれるフレームは例外。それ以上外側はないので。
C言語等だとスコープの様な考え方で、コンパイラは現にこの様なデータ構造を作って変数の参照先とかを決めているが、実行時にはこの様な仕組みは存在しない。唯一スタックにフレームに相当するものが置かれるが、その外側への参照とかはない。
変数の値は直近のフレームから順に探して最初に見つかったものを値として決める。
プログラムだけでは意味を持たず、それをある環境下で評価する事で初めて意味を持つ。
3.2.1 The Rules for Evaluation
代入が存在する場合プログラムの評価方法は置換モデルから環境下での評価に置き換わる。
代入が存在する場合、厳密には引数の評価する順番が結果に影響する。同じ手続きを複数回呼ぶ場合呼び出す順序によって結果が変わる可能性があるし、異なる手続きの場合でも状態が変化する変数を共有している場合、呼び出す順番によって結果は変化する。代入が存在しなければこのような可能性はない。
手続きは常にlambdaを評価する事によって作られる。その手続きの環境はlambda式が評された時の環境である。
ここで初めて
(define (square x) (* x x))
が
(define square (lambda (x) (* x x)))
の構文糖衣である事が明かされる。『Scheme手習い』『Scheme修行』では常にlambdaを使った表記だった様に思う。
図3.2ではlambda式はその本体への参照と環境への参照と解釈されて、それをglobal environmentのsquareと言うシンボルが参照している。
手続きを呼び出す時には
- 呼び出し側の環境を外部環境とし、
- 新しいフレームに仮引数に実引数の値を拘束する。
この環境下で手続きの本体が評価される。
脚注13にdefineは既に存在しているシンボルに対しては拘束しているものを変更してしまいset!を使わずに値を返られてし合うので問題だと書いてあるが、RSR5モードでは既に存在しているシンボルに対してはdefine出来ない模様。ただしRacketでは出来る。
> (+ 2 3) 5 > (define + (lambda (a b) (* a b))) > (+ 2 3) 6 >
set!の構文は(set!
3.2.2 Applying Simple Procedures
(f 5)が評価されると環境E1が作られ、その環境下でfの本体が評価される。ここで本当は+、*を呼び出す為の環境が作られて実行されるがそれは省略。その後sum-of-squareを呼び出す為の環境、squareを呼び出す為の環境が2回作られて、それぞれ評価されて値を得る。得た値が返って来る部分の仕組みについてはここでは触れていない。
Exercise 3.9
再帰版:
環境 | 変数 | 評価対象 | 外部環境 | 備考 |
global | factorial=(lambda ...) | (factorial 6) | なし | |
1 | n=6 | factorialの本体、(if ...) | global | ここでifが解釈が解釈されてelse側を評価する事になる |
2 | ?=6, ?=1 | 演算子-の本体 | global | 環境1ではなく演算子-が定義された環境が外部環境、6-1=5が確定 |
3 | n=5 | factorialの本体、(if ...) | global | elseを評価 |
4 | ?=5, ?=1 | 演算子-の本体 | global | 5-1=4が値として確定 |
5 | n=4 | factorialの本体、(if ...) | global | elseを評価 |
6 | ?=4, ?=1 | 演算子-の本体 | global | 4-1=3が値として確定 |
7 | n=3 | factorialの本体、(if ...) | global | elseを評価 |
8 | ?=3, ?=1 | 演算子-の本体 | global | 3-1=2が値として確定 |
9 | n=2 | factorialの本体、(if ...) | global | elseを評価 |
10 | ?=2, ?=1 | 演算子-の本体 | global | 2-1=1が値として確定 |
11 | n=1 | factorialの本体、(if ...) | global | ifの条件が成立し値1が確定 |
9 | n=2, (factorial 1)=1 | factorialの本体、(* n ...) | global | (* 2 1)を評価 |
12 | ?=2, ?=1 | 演算子*の本体 | global | 2×1=2が値として確定 |
9 | n=2, (factorial 1)=1 | factorialの本体、(* n ...) | global | 評価結果として2が確定 |
7 | n=3, (factorial 2)=2 | factorialの本体、(* n ...) | global | (* 3 2)を評価 |
13 | ?=3, ?=2 | 演算子*の本体 | global | 3×2=6が値として確定 |
7 | n=3, (factorial 2)=2 | factorialの本体、(* n ...) | global | 評価結果として6が確定 |
5 | n=4, (factorial 3)=6 | factorialの本体、(* n ...) | global | (* 4 6)を評価 |
14 | ?=4, ?=6 | 演算子*の本体 | global | 4×6=24が値として確定 |
5 | n=4, (factorial 3)=6 | factorialの本体、(* n ...) | global | 評価結果として24が確定 |
3 | n=5, (factorial 4)=24 | factorialの本体、(* n ...) | global | (* 5 24)を評価 |
15 | ?=5, ?=24 | 演算子*の本体 | global | 5×24=120が値として確定 |
3 | n=5, (factorial 4)=24 | factorialの本体、(* n ...) | global | 評価結果として120が確定 |
1 | n=6, (factorial 5)=120 | factorialの本体、(* n ...) | global | (* 6 120)を評価 |
16 | ?=6, ?=120 | 演算子*の本体 | global | 6×120=720が値として確定 |
1 | n=6, (factorial 5)=120 | factorialの本体、(* n ...) | global | 評価結果として720が確定 |
繰り返し版:
環境 | 変数 | 評価対象 | 外部環境 | 備考 |
global | factorial=(lambda ...) | (factorial 6) | なし | |
1 | n=6 | factorianの本体、(fact-iter ...) | global | |
2 | product=1, counter=1, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
3 | ?=1, ?=1 | 演算子*の本体 | global | 1×1=1が値として確定 |
4 | ?=1, ?=1 | 演算子+の本体 | global | 1+1=2が値として確定 |
2 | product=1, counter=1, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
5 | product=1, counter=2, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
6 | ?=2, ?=1 | 演算子*の本体 | global | 2×1=2が値として確定 |
7 | ?=2, ?=1 | 演算子+の本体 | global | 2+1=3が値として確定 |
5 | product=1, counter=2, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
8 | product=2, counter=3, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
9 | ?=3, ?=2 | 演算子*の本体 | global | 3×2=6が値として確定 |
10 | ?=3, ?=1 | 演算子+の本体 | global | 3+1=4が値として確定 |
8 | product=2, counter=3, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
11 | product=6, counter=4, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
12 | ?=4, ?=6 | 演算子*の本体 | global | 4×6=24が値として確定 |
13 | ?=4, ?=1 | 演算子+の本体 | global | 4+1=5が値として確定 |
11 | product=6, counter=4, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
14 | product=24, counter=5, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
15 | ?=5, ?=24 | 演算子*の本体 | global | 5×24=120が値として確定 |
16 | ?=5, ?=1 | 演算子+の本体 | global | 5+1=6が値として確定 |
14 | product=24, counter=4, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
17 | product=120, counter=6, max-count=6 | fact-iterの本体、(if ...) | global | elseを評価 |
18 | ?=6, ?=120 | 演算子*の本体 | global | 6×120=720が値として確定 |
19 | ?=6, ?=1 | 演算子+の本体 | global | 6+1=7が値として確定 |
17 | product=120, counter=6, max-count=6 | fact-iterの本体、(fact-iter ...) | global | |
20 | product=720, counter=7, max-count=6 | fact-iterの本体、(if ...) | global | ifの条件が成立。720が値として確定 |
17 | product=120, counter=6, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
14 | product=24, counter=4, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
11 | product=6, counter=4, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
8 | product=2, counter=3, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
5 | product=1, counter=2, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
2 | product=1, counter=1, max-count=6 | fact-iterの本体、(fact-iter ...) | global | 720が値として確定 |
1 | n=6 | factorianの本体、(fact-iter ...) | global | 720が値として確定 |