2010年10月02日 05:00 [Edit]

javascript - λ表記をDSLに

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

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

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


この記事へのトラックバックURL

この記事へのトラックバック
javascript - λ表記をDSLに おー〜すばらしい。  実はラムダ式はよくわかってないんだけどw ラムダ式って、確か今までの数式の書き方は一意な解釈ができない曖昧なものが多かったから、それを統一するために作ったのだったかなぁ??  だけど、結局無理なことがわかって
[プログラム][javascript]ラムダ式をそのまま実行【やわらかコード】at 2010年10月03日 22:45