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

6.2

 ラムダ計算の実装

197

（

m

から

n

の範囲は必ず

m - n + 1

個の要素になります）、最終的なペアから結果としてのリストを取

り出します。

RANGE = -> m { -> n { LEFT[INCREMENT[SUBTRACT[n][m]][COUNTDOWN][PAIR[EMPTY][n]]] } }

このコンビネータを使わないバージョンもうまく動きます。

>>

to_array(RANGE[FIVE][TEN]).map { |p| to_integer(p) }

=> [5, 6, 7, 8, 9, 10]

条件が真になるまで任意のループを実行する代わりに、所定の回数だけ反復を実行すること

によって、

MOD

と

RANGE

を実装することができました。これらは原始再帰関数（primitive

recursive function）であるためです。詳しくは「

7.2

 部分再帰関数」を参照。

6.2

　ラムダ計算の実装

FizzBuzz問題を通して、型なしラムダ計算でプログラムを書くということがどんな感じになるかを

学びました。制約を課すことによって、言語の機能に頼らずにゼロからたくさんの基本的な機能を実

装していき、最終的に与えられた問題を解くのに必要なデータ構造とアルゴリズムをすべて構築できま

した。

もちろん、私たちは本当にラムダ計算プログラムを書いたわけではありません。このような最小限の

言語が実際どのように動くのか、その感じをつかむために、ラムダ計算のスタイルでRubyプログラム

を書いたにす ...