JavaScriptに近いラムダ計算系 - 檜山正幸のキマイラ飼育記 (はてなBlog)

机上のラムダ計算で何か考えてみて、それを動かしたいときはJavaScriptに翻訳する、という方法を僕はよく採用します。ラムダ計算は理論的にスッキリしていて扱いやすい計算体系です。が、そのままでは実行できません（そのままの実行系もあるでしょうが一般的ではない）。ラムダ計算とJavaScriptの構文はけっこう似ているので、翻訳は割と楽にできます。そのへんのところは「JavaScriptで学ぶ・プログラマのためのラムダ計算」を参照してください。

さて、ラムダ計算といっても色々な種類の計算体系があります。ラムダ計算の形式性や厳密性を壊さない範囲で、JavaScriptへの翻訳ができるだけ簡単になるようなラムダ計算を考えてみましょう。

型と基本データ

ラムダ計算に型が付いていても、今のJavaScriptは型の定義や型アノテーションができないので、「型なし」の計算となります。とはいえ、純粋な型なしラムダ計算はすごく使いにくいので、数値（Number）や文字列（String）などの普通のデータは使えるとします。型なしラムダ計算のなかで基本データを定義することは、よくあるラムダ計算の練習問題ですが、別に練習問題を解きたいわけじゃないので、最初から基本データ（のリテラル）は使えるとします。

基本データに対する基本的な関数／演算子（例えば足し算とか文字列の連接とか）も最初からサポートされているとしましょう。このような関数は、入力（引数）や出力（戻り値）に型を想定しています。ですから、やっぱり「型なし」なのではなくて、暗黙に（気持ちの上では）型がある計算体系です。「暗黙の型から明示的な型を引き出す」とか言い出すと、それは型推論の話になるので、ここはイイカゲンなままで済ませましょう。

引数と適用

ラムダ計算は通常、カリー化を前提に関数は単一引数ですが、これも使いにくいので、多変数（引数が任意個数）の関数を認めます。ラムダ抽象は、λ(x, y).E とか λ().E とかの形になります。

適用は、f・(1, 2) のように適用演算子「・」を使うのがオフィシャルな書き方とします。ただし、f(1, 2) と省略を許すので、常識的な適用でもOKです。また、適用演算子に対する関数（高階関数）版として、Applyが組み込みであるとしましょう。Apply(f, [1, 2]) のように使います。ApplyをJavaScriptで書くなら：

function Apply(fun, args) {
  return fun.apply(null, args);
}

複合データとマップ関数

Applyの第二引数に配列を使ってます。JavaScritの配列とオブジェクトに相当する複合データも認めるとします。これらの複合データを活用するために二種類のマップ関数も組み込みであるとします。fが二引数の関数として、EachItem(a, f) と EachProp(o, f) が配列とオブジェクトに関するマップ関数です。これらもJavaScriptで書くなら次のようです*1。

function EachItem(arr, fun) {
 var result = [];
 for (var i = 0; i < arr.length; i++) {
   result.push(fun(i, arr[i]));
 }
 return result;
}

function EachProp(obj, fun) {
 var result = {};
 for (var p in obj) {
   result[p] = fun(p, obj[p]);
 }
 return result;
}

フォールド

再帰的定義を減らすためにフォールド（foldl）も入れておきましょう。

function Fold(arr, init, fun) {
 var result = init;
 for (var i = 0; i < arr.length; i++) {
   result = fun(result, arr[i]);
 }
 return result;
}

例題

ちょっと例題をやってみます。aが配列で、pが述語（一引数でBoolean値の関数）だとして、「aの全ての項目が、pを満たす」ことを確認する関数（高階関数）は次のようです。



andAll := λ(a).Fold(a, true, λ(x, y).(x && y))
every := λ(a, p).andAll(EachItem(a. λ(i, v).p(v)))

JavaScriptに翻訳すると：

var andAll = function(a){return Fold(a, true, function(x, y){return x && y})};

var every = function(a, p){return andAll(EachItem(a, function(i, v){return p(v)}))};

let式とか

let式内で関数を定義して、それに具体的引数を渡すなら次のようです。



(let {

  andAll := λ(a).Fold(a, true, λ(x, y).(x && y))
  every := λ(a, p).andAll(EachItem(a. λ(i, v).p(v)))

} in every)([0, 2, 4], λ(n).(n%2 === 0))

同じことはJavaScriptでもできます。

(function() {
  var andAll = function(a){return Fold(a, true, function(x, y){return x && y})};

  var every = function(a, p){return andAll(EachItem(a, function(i, v){return p(v)}))};

  return every;
})()([0, 2, 4], function(n){return n%2 === 0})

return を毎度書くのが面倒ですが、それほどの負担なしに「ラムダ式 → JavaScript式」の翻訳ができますね。

まとめ

次のようなラムダ計算系なら、JavaScriptにすぐに翻訳できます。

暗黙には型を想定するが、明示的な型定義や型アノテーションはない。
基本データのリテラルは最初から使える。
複数の引数を許す。
複合データ構造としての配列とオブジェクトもある。
配列とオブジェクトの上のマップ関数が組み込みで用意されている。
適用やフォールドの関数も組み込みで用意されている。
let/letrec式が使える。

*1:[追記]標準関数のArray.mapがまさにマップ関数なので、これを使うとEachItemの代用になります。しかし、Object.mapはないようです。[/追記]