以前書いた「ラムダ計算基礎文法最速マスター」(以下「最速マスター」)は, 予想以上に多くの人に興味を持ってもらえたようですが, 同時に難しくてわからなかったという人も多かったようです. 反響から察するに, 構文を見慣れていない(と錯覚してしまう)ことが理解の妨げになっていたように思います.
ラムダ計算の構文は, 実際には全く特殊なものではありません. このことがよくわかるように, 「最速マスター」のラムダ計算の簡約の例をすべて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 }の式に相当します.
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コンビネータを用いたループ(再帰呼出し)の例も追加しました.
