式がどのように評価されるかをモデル化することは、プログラムを検証する上で
重要なことです。
「すべて式である」の章で説明したように、Schemeではプログラムを構成するもの
全てが式です。式は値を持ち、評価によってその値を得ることができるという特徴
があります。このプログラムが全て式であることの利点はプログラムがどのように
評価されるかを置き換えモデルという単純なモデルで確かめることができると
いうことです。
置き換えモデル
置き換えモデルとは、手続き作用を別の式に置き換えてプログラムの評価
をシミュレートするモデルです。置き換える式が無くなれば計算終了です。
式を置き換える方法はいくつか存在します。
Schemeでは作用順序評価というモデルを採用しています。
作用順序評価
作用順序評価は、手続き作用式の手続きの引数から順に評価し、最後に手続きを評価するモデルです。例えば、以下のような手続きを定義します。
(define (add x y)
(+ x y))
この手続きを以下のように使うと、
作用順序評価で評価器はまず、(add 2 3)を評価します。
(add 2 3)
この時、評価器はこの式が以下のような形なので手続き作用の式だと判断します。
(手続き 引数１ ...)
次に評価するのは、式addと2と3です。初めに式2と3が評価されます。
2 => 2
3 => 3
式2と3はこれ以上置き換えることができない式（プリミティブ式）で、
それぞれ数値の2と3の値が返されます。
式addは手続きで手続きのボディに置き換えられます。
(add 2 3)
=> (+ 2 3)
同様に、式(+ 2 3)は手続き作用の式で式2と3の値はそれぞれ数値2と3です。
式+はプリミティブな手続きで以下のように置き換えられます。
(+ 2 3)
=> 5
addや+の引数2と3の評価順は決まっていません。2の
評価が先でも、3の評価が先でも返ってくる値はいつも同じなので評価の
順番は結果に影響を与えません。そのため、順番を気にせず引数を置き換える利点
が得られます（Schemeの処理系では引数の評価順は決められていません）。
このようにSchemeプログラムは、手続きを別の単純な式に置き換えることにより、
評価をシミュレートすることができます。
この置き換えモデルは操作が単純なため、プログラムの検証に役立ちます。
しかし、次に説明する副作用がプログラム中に入ってくると、この置き換えモデル
は使えなくなります。
副作用
実用的なプログラムは、ファイルの読み書きのような入出力操作や、変数の値を
別の値にするための代入操作が必要です。これらの操作の目的は、式を
評価してその値を取り出すという目的とは異なります。これらの操作は、文字
をコンソールに表示したり、オブジェクト内の状態を変更することが目的です。
入出力や代入に共通することは、評価する順番が重要だということです。
例えば、以下の式を評価したとしましょう。
(list (display 1) (display 2) (display 3))
おそらくgoshは以下のように評価するはずです。
gosh> (list (display 1) (display 2) (display 3))
123(#<undef> #<undef> #<undef>)
gosh>
1と2と3がこの順番で出力させるのが目的ならばこれで良いですが、Schemeの仕様書
では引数の評価順が決められていません。そのため、引数を右から左へ評価する
ような処理系では以下のような結果になるでしょう。
> (list (display 1) (display 2) (display 3))
321(#<undef> #<undef> #<undef>)
>
結果（印字される順番）が異なりますね。このように出力を行う式がある場合、
評価する順番を考えて置き換えを行う必要があります。出力の他にも入力や代入
も評価の順番が重要になります。これらは副作用と呼ばれています。Schemeの副作用は主に以下の３個で
す。
- 入出力
- 代入
- 継続(?)
一番下の継続はさておき、上のふたつの入出力や代入は実際に使えるプログラム
を書くには必要な機能です。では、これらの機能があるとなぜ置き換えモデルが
破綻するのでしょうか？簡単な例を見て置き換えモデルが破綻する様子を見てみ
ましょう。以下は、yにxとyの値を足したものを代入し、その結果を返す式です。
(((lambda (y)
(lambda (x)
(begin
(set! y (+ x y))
y)))
10)
1)
これを、置き換えモデルで動かしてみます。まずこの式は手続き適用の形なのでそれ
ぞれを評価します。1はそのままです。手続きの位置にある式は手続き適用の形なので
置き換えすることができます。
(((lambda (y)
(lambda (x)
(begin
(set! y (+ x y))
y)))
10)
1)
=> ((lambda (x)
(begin
(set! y (+ x 10))
10))
1)
置き換えて手続きが返ってきました。この手続きに1を渡して置き換えると以下のように
なります。
=> (begin
(set! y (+ 1 10))
10)
本来ならば初めにyにyとxを足した値を代入し、その後にyの値を返して欲しかったは
ずです。しかし、置き換えモデルではそれができませんでした。これは、置き換えモ
デルには時間という概念が存在しないからです。
環境フレームモデル
この問題を解決するモデルか環境フレームモデルです。環境フレームモデルは、置き
換えモデルでは扱えなかった時間というものが扱えるようになります。
環境フレームモデルでは以下のように、式を評価した時の名前と値との対応を表わした図で表現されます。
たとえば、以下の式を順に評価したとします。
gosh> (define book-name "Gaucheプログラミング")
book-name
gosh>
最後の手続きを評価したとき、環境フレームは以下のようにbook-nameという変数と
"Gaucheプログラミング"という値が登録されます。
ここで、前回の代入の問題を環境フレームモデルを用いて評価してみます。
(((lambda (y)
(lambda (x)
(begin
(set! y (+ x y))
y)))
10)
1)
まず、一番最初の環境フレームは以下のようになっています。
まず、この式は手続き適用の式です。
(手続き 引数)
1はそのままです。手続き部分の式を評価します。
((lambda (y)
(lambda (x)
(begin
(set! y (+ x y))
y)))
10)
この式も同様に手続き適用の式です。10はそのままで、手続き部分のlambda式は
手続きなので、10にこの手続きを適用します。元の式は環境フレームモデルでは以下のように
置き換えられます。yはまだ置き換えられていません。
((lambda (x)
(begin
(set! y (+ x y))
y))
1)
このときlambda式の中の環境フレームは以下のようになります。
lambda式の引数に10が束縛され、新たな環境フレームが作成されます。ここで作成された環境フレーム
は評価時の環境フレームを持っています。
次に1に残りのlambda式を適用させます。すると以下のような環境フレームが作成されます。
この環境フレームで以下の式が評価されます。
(begin
(set! y (+ x y))
y)
まず、set!の式の中の(+ x y)が評価されます。
+は一番昔の環境フレームに束縛が存在します（プリミティブな手続き）。
xは一番新しい環境フレームに束縛があり、値は1です。
yは２番目の環境フレームに束縛があり、値は10です。
そのため、yに代入される値は11になります。
このとき、環境フレームは以下のように変化します。set!は現在の環境フレームを変更する効果があります。
図を追加
この環境フレームでyを評価すると、値は11になり、
begin式の返り値は11になります。これはプログラムの意図した通りに動きます。
環境フレームモデルでは、手続きが適用されると、その手続き内に現在の環境フレームを含む新しい環境フレームが生成されます。また、set!のような代入により、現在の環境フレーム内の束縛を変更することができます。
そのため、評価の順番をシミュレートでき、代入や入出力などの副作用が存在するプログラムの評価を手で確かめることができます。
