読者です 読者をやめる 読者になる 読者になる

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

article lambda javascript

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

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

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

http://labs.orezdnu.org/lambda/#js

動作確認と既知の問題

インタプリタの特徴

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

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

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

同様に, ラムダ計算における抽象は, JavaScriptの無名関数に相当します. すなわち, ラムダ計算λx.Mの項はJavaScriptfunction(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コンビネータを用いたループ(再帰呼出し)の例も追加しました.

インタプリタの制限

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

広告を非表示にする