asin:4764901846
計算論
計算可能性とラムダ計算
高橋正子

クロージャーがある言語には、λ演算がすでに含まれています。

が、たいていの場合、その言語の流儀で書かねばなりません。たとえばこんな風に。

var Z = function(f) {
  return (function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })(function(g) {
    return function(m) {
      return f(g(g))(m);
    };
  })
};

ふつーに

Z := λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

と書けたらよいと思いませんか?

λscript(笑)

できるようにしてみました。

λ = function(str){
    var head = function(s){
        return new Function(s.charAt(0), 
                            'return ' + (
                                s.charAt(1) == '.' ? body(s.substr(2))
                                                   : head(s.substr(1))));
    },
    body = function(s){
        if (! s.match(/\S/) ) return '';
        var a = [], i, l, t;
        while(s.length) {
            if (s.charAt(0) === '('){
                for (i = d = 1, l = s.length; i < l; i++){
                    if      (s.charAt(i) === '(') d++;
                    else if (s.charAt(i) === ')') d--;
                    if (!d) break;
                };
                if (i === l) throw 'syntax error: () mismatch'
                t = s.substr(1, i-1);
                a.push( t.match(/\./) ? head(t) : body(t) );
                s = s.substr(i+1);
            } else if (s.match(/^\w/)) {
                s = s.replace(/^\w+/, function(m){ a.push(m); return '' });
            } else {
                s = s.substr(1);
            }
        }
        return a.map(function(s){return '('+s+')'}).join('');
    };
    return head( str.replace(/[^\x20-\x7e]/g,'') )
};

λscript = function(str){
    return str.replace(/\/\*.*?\*\//g, '')
        .replace(/(\w+)\s*:=\s*(λ.*?)[;\n\r]/g, function(m,m0,m1){
            return m0 + '=' + λ(m1) + ';' 
        });
};

見ての通り、JavaScriptに翻訳しているだけです。が、以下のコードがそのまま動きます。Wikipediaなどからコピペしたものもそのまま動いちゃいます。

T       := λxy.x
F       := λxy.y
AND     := λpq.p q p
OR      := λpq.p p q
NOT     := λpab.p b a
IF      := λpab.p a b

SUCC    := λnfx.f (n f x)
ZERO    := λfx.x
ADD     := λmn.m SUCC n
MUL     := λmn.m (ADD n) ZERO
POW     := λbe.e b
ISZERO  := λn.n (λx.F) T

CONS    := λxyf.f x y
CAR     := λp.p T
CDR     := λp.p F
NIL     := λx.T
NILP    := λp.p (λxy.F)

PHI     := λx.CONS (CDR x) (SUCC (CDR x))
PRED    := λn.CAR (n PHI (CONS ZERO ZERO))
SUB     := λmn.n PRED m

/* Y    := λg.(λx.g (x x)) (λx.g (x x)) */
Z       := λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

で、こんな風に使う、と。

eval(λscript($('#prelude').text())); /* まとめて */
cb2bool = function(f){ return f(true)(false) };
cn2num  = function(f){ return f(function(n){ return n+1 })(0) };

あるいはこんな風に。

DSLのくせに、チューリング完全です。その意味では正規表現の上を行きます(笑)

似たようなものは誰か作ってそうな気がするのですが、見当たらなかったので。

Enjoy!

Dan the λ calculator