[ 目次, 前節, 次節, 索引 ]

1.1.5 手続き作用の置換えモデル



演算子が合成手続きの名前になっている組合せを評価するのに, 解釈系は1.1.3節で述べた演算子が基本的手続きになっている組合せの場合と殆んど同じプロセスを踏む. つまり, 解釈系は組合せの要素を評価し, (組合せの演算子の値である)手続きを(組合せの被演算子の値である)引数に作用させる.

   基本的手続きを引数に作用させる機構が解釈系に組み込まれていると仮定しよう. 合成手続きについて, 作用のプロセスは次のとおりである.

• 合成手続きを引数に作用させるには, 各仮パラメタを対応する引数で取り替え, 手続きの本体を評価する.

このプロセスを説明するのに, fを1.1.4節で定義した手続きとして, 組合せ

(f 5)
を評価してみよう. まずfの本体を取り出す:
(sum-of-squares (+ a 1) (* a 2))
次に仮パラメタaを引数5で取り替える:
(sum-of-squares (+ 5 1) (* 5 2))
これで問題は二つの被演算子と演算子sum-of-squaresを持つ組合せの評価に帰着した. この組合せの評価には, 三つの部分問題がある. 作用させるべき手続きを得るために演算子を評価しなければならず, また引数を得るために, 被演算子を評価しなければならない. さて, (+ 5 1)は6に, (* 5 2) は10になるから, 手続きsum-of-squaresを6と10とに作用させることになる. この値はsum-of-squaresの本体の仮パラメタxy とに置き換えられ, 式は
(+ (square 6) (square 10))
に帰着する. squareの定義を使えば
(+ (* 6 6) (* 10 10))
に帰着し, 乗算により
(+ 36 100)
そして最後に
136
になる.

   今述べたプロセスを手続き作用の置換えモデル(substitution model)という. これは, この章の手続きに関する限り, 手続き作用の「意味」を定めるモデルと考えてよい. しかし, 注意する点が二つある.

• 置換えの目的は, われわれが手続き作用を考える時の補助であって, 解釈系の実際の働きを述べるものではない. 解釈系は仮パラメタに値を置き換えて, 手続きの字面を操作しつつ手続き作用を評価するのではない. 実際には, 「置換え」は, 仮パラメタの局所環境を使って実現している. このことは解釈系の実装を詳しく調べる3章と4章で十分に論じよう.

• 本書の中では, 解釈系の働きについては, 5章の解釈系と翻訳系の完全な実装に向い, 次々と精巧なモデルを提示していく. 置換えモデルは, 評価プロセスを形式的に考える第一歩---これらモデルの最初のものに過ぎない. 一般に理工学の現象をモデル化する場合, 単純で不完全なモデルから始める. 対象を詳しく調べていくうちに, この単純なモデルは不適切になり, さらに洗練されたモデルで取り替っていく. 置換えモデルも例外ではない. 特に3 章で「可変データ」を持つ手続きを使うと, 置換えモデルは破綻し, 手続き作用のより複雑なモデルで取り替えられなければならないことが分る.15

作用的順序と正規順序
1.1.3節に示した評価の記述によれば, 解釈系はまず演算子と被演算子を評価し, 次に結果の手続きを結果の引数に作用させる. これだけが評価を行う方法ではない. 別の評価モデルでは, その値が必要になるまで, 被演算子を評価しない. 基本的演算子だけを持つ式が出てくるまで, パラメタへの被演算子の式の置換えを繰り返し, それから評価を行う. この方法を使えば,
(f 5)
の評価は次の式のように進行する.
(sum-of-squares (+ 5 1) (* 5 2))

(+    (square (+ 5 1))      (square (* 5 2))  )

(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))
さらに次のようになる.
(+         (* 6 6)             (* 10 10))

(+           36                   100)

                    136
前の評価モデルと同じ結果が得られるが, プロセスは異る. 特に(+ 5 1)(* 5 2)の評価はここでは二度ずつ行われたが, それは式
(* x x)
xをそれぞれ(+ 5 1)(* 5 2)に置き換えて簡約された.

   このもう一つの「完全に展開し, 簡約する」評価方法は 正規順序の評価 (normal-order evaluation)という. それに対し解釈系が実際に使っている「引数を評価し, 作用させる」方法を 作用的順序の評価(applicative-order evaluation)という. (本書の最初の二章の手続きを含め)置換えを使ってモデル化出来, 正しい値が得られる手続き作用については, 正規順序と作用的順序の評価は同じ値になることが示される. (正規順序と作用的順序の評価が同じ結果にならない「不当な」値の例は, 問題1.5を見て欲しい.)

   Lispは作用的順序の評価を使っているが, それは上の(+ 5 1)(* 5 2) で示したような式の多重評価を避けて得られる効率のためと, 更に重要なことに置換えでモデル化出来る手続きの範囲を抜けた途端に正規順序の評価が極めて複雑になるからである. 一方正規順序の評価も, 極めて有効な道具であり, この問題の一部を3章と4章で調べることにする.16


15 その単純さにも拘らず, 置換えプロセスに厳密な数学的定義を与えようとすると, 驚くほど複雑であることが分る. 問題は手続きの仮パラメタに使われた名前と, 手続きを作用させようとする式の中で使われている(同じかも知れぬ)名前の混乱の可能性から生じる. 実際, 論理学とプログラミングの意味論の文献には, 置換え (substitution)の過った定義の長い歴史があった. 置換えの精密な議論については Stoy 1977を参照のこと.

16 3章ではストリーム処理(stream processing)を紹介する. それは正規順序の評価を部分的に取り込むことで, 一見「無限」に見えるデータ構造を扱う手法である. 4.2節ではSchemeの解釈系を修正し, Schemeの正規順序版をこしらえて見る.

[ 目次, 前節, 次節, 索引 ]