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

6.2

 ラムダ計算の実装

199

=> -> n { -> p { -> x { p[n[p][x]] } } }

>>

add =

LCFunction.new(:m,

LCFunction.new(:n,

LCCall.new(LCCall.new(LCVariable.new(:n), increment), LCVariable.new(:m))

)

)

=> -> m { -> n { n[-> n { -> p { -> x { p[n[p][x]] } } }][m] } }

この言語には最小限の構文しかないので、任意のラムダ計算プログラムを表現するのにこれら3つ

のクラスで十分です。

6.2.2

　意味論

それぞれの構文クラスに

#reduce

メソッドを実装することによって、スモールステップ操作的意味

論を与えましょう。スモールステップ意味論を使うと良いことがあります。なぜなら、Rubyの式では

簡単にはできなかった、評価の各ステップを観察できるためです。

6.2.2.1

　変数の置き換え

#reduce

を実装する前に、まず

#replace

という操作が必要になります。これは式の中に登場する

特別な変数を見つけて、別の式に置き換えるメソッドです。

class LCVariable

def replace(name, replacement)

if self.name == name

replacement

else

self

end

end

end

class LCFunction

def replace(name, ...