アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

46

2

章 プログラムの意味

これはスモールステップ意味論で得られた結果と同じなので、

While#evaluate

は正しく動いて

いるようです。

2.3.2.3

　応用

スモールステップ意味論の実装では、Rubyのコールスタックは少ししか使われません。大きなプロ

グラムに対して

#reduce

を呼び出すと、メッセージが抽象構文木を伝わって簡約可能なコードに到達

するまで、

#reduce

はいくらか入れ子に呼び出されます

†

。しかし、仮想機械は小さな簡約を繰り返し

実行しながら、現在のプログラムと環境を保持することによって、計算全体の進行を記録します。具

体的に言うと、コールスタックの深さはプログラムの構文木の深さに制限されます。呼び出しの入れ子

は、簡約そのものを実行しているわけではなく、次に簡約すべきものを探すための構文木の走査に使

われているだけです。

これに対し、ビッグステップ意味論の実装はもっとスタックを多用します。計算全体のどこにいるの

かを覚えること、大きな計算の一部として小さな計算を実行すること、評価すべきものがどれくらい

残っているかを記録すること、といった作業はすべて、スタックを頼りにしています。

#evaluate

を

1回呼び出しているだけに見えても、実際には、構文木の奥深くにあるサブプログラムを評価していく

一連の再帰呼び出しになるのです。

この違いは、それぞれのアプローチの目的を際立たせます。スモールステップ意味論は、小さな操

作を実行できる単純な抽象機械を想定しています。したがって、そこには役