JavaScriptで読む「ラムダ計算基礎文法最速マスター」

以前書いた「ラムダ計算基礎文法最速マスター」(以下「最速マスター」)は, 予想以上に多くの人に興味を持ってもらえたようですが, 同時に難しくてわからなかったという人も多かったようです. 反響から察するに, 構文を見慣れていない(と錯覚してしまう)ことが理解の妨げになっていたように思います.

ラムダ計算の構文は, 実際には全く特殊なものではありません. このことがよくわかるように, 「最速マスター」のラムダ計算の簡約の例をすべてJavaScriptの構文で書いてみました.

......という内容になるはずでしたが, 気がついたらラムダ計算のインタプリタをJavaScriptで実装していました! 実際に動かせるものは下記URLにあります.

https://tarao.github.io/LambdaJS/#js

動作確認と既知の問題

• Firefox 3.6
• Google Chrome 4.1
• Internet Explorer 8.0
  • 最後の例の実行速度に難あり
• Opera 10.51
  • キー入力の一部に難あり
• Safari 4.0

インタプリタの特徴

• すべてJavaScriptで実装
• 簡約過程を表示できる
• 評価戦略を切り替え可能(手動にすることで次に簡約する部分項を選択可能)
• JavaScriptの構文, ラムダ計算の構文, 両方の混在で書ける

JavaScriptの構文によるラムダ計算の表現

ラムダ計算における関数の適用は, JavaScriptの関数呼出しに相当します. すなわち, ラムダ計算の((M) N)の項はJavaScriptの(M)(N)の式に相当します.

同様に, ラムダ計算における抽象は, JavaScriptの無名関数に相当します. すなわち, ラムダ計算のλx.Mの項はJavaScriptのfunction(x){ return M }の式に相当します.

JavaScriptでは

function(x,y,z){ return ... }

は3引数の無名関数を意味しますが, 今回のインタプリタでは, ラムダ計算の高階関数の略記に合わせて,

function(x){ return function(y){ return function(z){ return ... } } }

の略記と見なすようになっているので注意して下さい.

また, MozillaのJavaScript 1.8の新機能をサポートしているブラウザ上で実行する場合,

function(x){ return M }

の代わりに

function(x) M

と書けるようにしてあります.

具体例の実行

インタプリタの実演ページでは, 「最速マスター」に登場した例を実際にインタプリタで実行できます. ページ頭で出力形式を選択することで, ラムダ計算/JavaScript両方の構文で簡約過程を見られるようになっています. さらに, 簡約ステップが長いため「最速マスター」では省略されていたYコンビネータを用いたループ(再帰呼出し)の例も追加しました.

インタプリタの制限

構文解析・意味解析がかなりインチキなので, 書き間違えたときのエラーメッセージが不親切かもしれません.

ソースコード