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

162

6

章 無からのプログラミング

を書いてみます。これはただのRubyプログラミングにすぎませんが、架空の制約を課すことによっ

て、まったく新しい言語を学ばなくても簡単に制限された意味論を調べることができます。非常に限ら

れた機能セットでできることがわかったら、次にそれらの機能を使って、これまでの章で学んできたテ

クニックを活用しながら、パーサ、抽象構文、操作的意味論を備えた独立した言語として、ラムダ計

算を実装していきます。

6.1

　ラムダ計算をまねる

最小限の言語でプログラミングするのがどんなものか理解するため、たくさんある便利な機能を使

わずに、Ruby で問題を解いてみましょう。gemや標準ライブラリ、モジュール、メソッド、クラス、

オブジェクトなどを使わないのはもちろんのこと、できるだけ最小限になるよう、制御構造、代入、配

列、文字列、数値、ブール値も使わないようにします。

もちろん、Rubyにあるすべての機能を完全に使えなくすると、プログラムを書く余地のない言語に

なってしまいます。そこで、以下の機能については残しておくことにします。

●

変数の参照

●

procの生成

●

procの呼び出し

つまり、次のようなコードしか書けないということです。

-> x { -> y { x.call(y) } }

これは型なしラムダ計算の見え方に近く、私たちの目的に合っています。ラムダ計算そのも

のについては、「

6.2

 ラムダ計算の実装」で詳しく見ていきます。

コードを短かく読みやすくするため、省略形として定数を使う ...