1.1.5 手続き適用の置換モデル

演算子が複合手続きを指すような組み合わせをインタプリタが評価するとき、1.1.3節で説明したような、演算子が基本手続きを指す組み合わせを評価する場合とほぼ同じような手順をたどります。つまり、インタプリタは組み合わせの各要素を評価し、手続き(組み合わせの演算子の値)を引数(組み合わせの被演算子の値)に適用するということです。

基本手続きを引数に適用する仕組みは、インタプリタに組み込まれていると考えることができます。複合手続きについては、その適用手順は次のようになります。

複合手続きを引数に適用するには、手続きの本体に出てくる仮引数を対応する引数で置き換えて、それを評価する。

この手順の例として、次の組み合わせを評価してみましょう。

(f 5)

ここで、$\texttt{f}$は1.1.4節で定義した手続きです。 まず、$\texttt{f}$の本体を取得することから始めます。

(sum-of-squares (+ a 1) (* a 2))

次に、仮引数である$\texttt{a}$を、引数5で置き換えます。

(sum-of-squares (+ 5 1) (* 5 2))

これによって、問題は二つの被演算子と$\texttt{sum-of-squares}$という演算子の組み合わせの評価ということになります。この組み合わせの評価は、三つの部分問題を持っています。適用する手続きを得るためには演算子を評価する必要があり、引数を得るためには二つの被演算子を評価しなければなりません。ここで、$\texttt{(+ 5 1)}$の結果は6で、$\texttt{(* 5 2)}$の結果は10なので、$\texttt{sum-of-squares}$という手続きを6と10に適用することになります。これらの値によって$\texttt{sum-of-squares}$の本体に出てくる仮引数$\texttt{x}$と$\texttt{y}$を置き換えて、次の式を得ます。

(+ (square 6) (square 10))

$\texttt{square}$の定義を使うと、これは次の式になります。

(+ (* 6 6) (* 10 10))

かけ算によって、次のようになります。

(+ 36 100)

そして、最終的には次のようになります。

136

ここまでで説明した手順は、手続き適用の置換モデル(substitution model)と呼ばれます。これは、この章に出てくる手続きに限ると、手続き適用の“意味”を決めるモデルとして捉えることができます。しかし、二つ強調しておくことがあります。

• 置換の目的は、手続き適用について考えやすくするためのもので、インタプリタが実際にどのように動いているかについて記述したものではありません。インタプリタは普通、手続き適用の評価にあたって、手続きのテキストを操作して仮引数を値で置き換えるということはしません。実際には、この“置換”は仮引数のために局所環境を使うことによって実現します。このことについては、第3章と第4章で、インタプリタの実装について詳しく調べながら見ていきます。
• この本を通して、インタプリタの動作について、だんだん精巧になっていく一連のモデルを提示していきます。最終的には、第5章でインタプリタとコンパイラの完全な実装にまで到達します。置換モデルは、これらのモデルの最初のひとつ---評価手順について形式的に考えるための最初の一歩となるもの---に過ぎません。一般に、科学や工学で現象をモデル化するときには、単純化した不完全なモデルから始めます。物事を詳細に調べていくにつれ、これらの単純なモデルは不適切になり、より精密なモデルで置き換えなければならなくなります。置換モデルも例外ではありません。特に、第3章で“可変データ”を持つ手続きについて考える場合に、置換モデルが破綻してもっと複雑な手続き適用モデルによって置き換えなければならないことがわかります。¹⁵

適用順序と正規順序

1.1.3節での評価の記述によると、インタプリタはまず演算子と被演算子を評価し、評価結果として返される手続きを評価結果として返される引数に適用します。これは、評価を行うための唯一のやり方ではありません。考えられるほかの評価モデルとしては、値が必要になるまで被演算子を評価しないというものがあります。その代わりに、まず被演算子の式を基本演算子しか出てこない式になるまで置き換えてから評価を行います。この方法を使うと、$\texttt{(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

この方法でも前の評価モデルと同じ値が得られますが、手順が違います。特に、こちらでは$\texttt{(+ 5 1)}$と$\texttt{(* 5 2)}$の評価がそれぞれ二回行われます。これは、式$\texttt{(* x x)}$の$\texttt{x}$を、それぞれ$\texttt{(+ 5 1)}$と$\texttt{(* 5 2)}$で置き換えることに対応しています。

この“完全に展開してから簡約する”というもうひとつの評価方法は、正規順序評価(normal-order evaluation)として知られています。それに対して、インタプリタが実際に使っている“引数を評価してから適用する”という方法は、適用順序評価(applicative-order evaluation)と呼ばれます。置換によってモデル化でき(この本の最初の二章の手続きはすべてそうです)、かつ正当な値を返す手続き適用については、正規順序評価と適用順序評価は同じ値になるということが証明できます(正規順序評価と適用順序評価が同じ値にならない“不当な”値の例については、練習問題 1.5を参照してください)。

Lispは適用順序評価を使っています。理由のひとつは、上で見た$\texttt{(+ 5 1)}$ と $\texttt{(* 5 2)}$のような複数回の評価を避けることによる性能の向上です。そして、もっと大きな理由としては、置換によってモデル化できる手続きの範囲を超えると正規順序評価がとても複雑になるということがあります。一方で、正規順序評価は非常に価値のあるツールにもなりえます。そのことについては、第3章と第4章で一部見ていきます。¹⁶

¹⁵. 置換という考え方は単純なものですが、置換手順の厳密な数学的定義をしようとすると驚くほど複雑になるということがわかっています。この問題は、手続きの仮引数に使われる名前と、手続きを適用する式で使われている(同じである可能性のある)名前とを混同する可能性から来ています。実際に、論理学とプログラミング意味論の文献においては、置換(substitution)の間違った定義に関する長い歴史があります。置換に関する精密な考察については、Stoy 1977を参照してください。 ↩

¹⁶. 第3章ではストリーム処理(stream processing)を導入します。これは、限定された形の正規順序評価を組み入れることで、“無限”に見えるデータ構造を扱うという手法です。4.2節では、Schemeインタプリタに手を加え、Schemeの正規順序バージョンを作成します。 ↩