1.1.3 組み合わせの評価

この章の目標のひとつは、手続き的に考えるうえでの問題点を分解することです。とりあえず、組み合わせを評価するにあたって、インタプリタはそれ自身、手続きに従っているということを考えてみましょう。

組み合わせを評価するため、以下のことを行います。

1. 組み合わせの部分式を評価する
2. 部分式の左端(演算子)の値となっている手続きを、引数(被演算子)、つまり部分式の残り値に適用する

こんな単純な規則からも、手続き一般についてのいくつかの重要なポイントがわかります。一つ目のステップは、組み合わせに対する手続きを評価するには、組み合わせのそれぞれの要素に対する評価手続きを先にやらないといけないということを示しています。そのため、評価規則は本質的に再帰的(recursive)なものになります。これは、ステップのひとつとして、その規則自身を呼び出さないといけないということです。¹⁰

再帰という考えが、深くネストした複合式をどれだけ簡潔に表現できるかというところに注目してください。再帰がなければ、かなり複雑な手続きになるところです。例えば、次の式の評価する場合について考えます。

(* (+ 2 (* 4 6))
   (+ 3 5 7))

この式を評価するには、4つの異なる組み合わせに対して評価規則を適用する必要があります。この手続きは、図1.1のように組み合わせを木の形で表すことによってイメージできます。それぞれの組み合わせはノードとして表され、そこから組み合わせの演算子と被演算子に対応する枝が生えています。終端ノード(そこから生えている枝のないノード)は、演算子か数字を表しています。評価を木という形で見ることで、被演算子の値が終端ノードから始まってそれぞれのレベルで組み合わさりながら上に向かって伝わっていく様子がイメージできます。一般的に、階層的な木のようなオブジェクトを扱うためには、再帰はとても強力なテクニックです。この“値を上に向かって伝える”という形の評価規則は、木の集積(tree accumulation)として知られています。

図1.1: 部分組み合わせの値を示した木表現

次に、一つ目のステップを繰り返して適用することで、ある点で評価する対象が、組み合わせではなく数値や組み込み演算子やその他の名前といった基本式になるというところに注目してください。このような基本的な場合については、以下のように規定することによって扱います。

• 数字の値は、それが示す値である
• 組み込み演算子の値は機械語の列で、それに対応する操作を実行する
• その他の名前の値は、現在の環境でその名前に関連づけられたオブジェクトである

二つ目の規則は、三つ目の規則の特殊なケースと考えることができます。このことは、$\texttt{+}$と$\texttt{*}$といった記号もグローバル環境に含まれていて、一連の機械語命令がそれらの“値”として関係づけられていると規定することによって可能になります。ここでキーになるのは、式に出てくる記号の意味を決めるうえで環境の果たす役割です。Lispのような対話的な言語では、$\texttt{(+ x 1)}$という式の値について考えるのは、$\texttt{x}$という記号に意味を付与する環境についての情報がなければ意味がありません。$\texttt{+}$という記号に対しても、意味を付与するのは環境です。第3章で学ぶように、評価を行う文脈を提供する存在としての環境という一般的概念は、プログラムの実行について理解するうえで重要な役割を果たしています。

上に書いた評価規則は、定義については扱っていないということに注意してください。例えば、$\texttt{(define x 3)}$を評価する際には、記号$\texttt{x}$の値と3という二つの引数に$\texttt{define}$を適用するということはしません。$\texttt{define}$の目的は、まさに記号$\texttt{x}$と値を関連づけるということだからです(つまり、$\texttt{(define x 3)}$は複合式ではないということになります)。

このような、一般的評価規則に対する例外は、特殊形式(special form)と呼ばれます。ここまでの範囲では、$\texttt{define}$は特殊形式の唯一の例ですが、ほかのものももうすぐ見ていくことになります。それぞれの特殊形式は、固有の評価規則を持っています。それらのいろいろな種類の式(それぞれ関連づけられた評価規則を持つ)は、プログラミング言語の構文を構成します。ほかの多くのプログラミング言語と比べると、Lispはとても単純な構文を持っています。それは、式の評価規則はひとつの単純な一般規則と少数の特殊な形に対する特殊規則からなるということです。¹¹

¹⁰. 評価規則によると、一つ目のステップの一部として、組み合わせの左端の要素を評価しなければいけないことになります。このことを奇妙に思われるかもしれません。この時点では、左端の要素というと、$\texttt{+}$や$\texttt{*}$といった、足し算やかけ算のような組み込みの基本的な手続きを表す演算子でしかありえないからです。のちに、演算子がそれ自身複合式であるような組み合わせを使うことが便利だということを学びます。 ↩

¹¹. 統一された書き方でも書けるものに対して、便利さのために別の表面構造を持たせるような特殊な構文形式は、Peter Landinの造語を使ってシンタックスシュガー(syntactic sugar)と呼ばれることがあります。ほかの言語の使用者と比べると、Lispプログラマは一般に、構文の問題をあまり気にしていません(これと対照的なのがPascalです。何でもいいのでPascalのマニュアルを開いて、どれだけのページが構文の記述に充てられているか見てみてください)。このように構文を軽視しているのは、ひとつは表面的な構文を変えやすいLispの柔軟性のためです。もうひとつは、多くの“便利な”構文構造が言語の統一性を損ない、プログラムが大きく複雑になるにつれ利点よりも欠点のほうが多くなるという観察結果のためです。Alan Perilの言葉を借りると、“シンタックスシュガーはセミコロン(コロン(直腸)とかけている)の癌を引き起こす”ということです。 ↩