lamdba.js

////////////
// lamdba
////////////
// x | t t | λx.t

////////////
// 图灵机
////////////
N  = x=>x?++x:1
P  = x=>console.info('1')

////////////
// 自然数
////////////
ZERO  = f=>x=>x
ONE   = f=>x=>f(x)
TWO   = f=>x=>f(f(x))
THREE = f=>x=>f(f(f(x)))
FOUR  = f=>x=>f(f(f(f(x))))
FIVE  = f=>x=>f(f(f(f(f(x)))))

// 后继
SUCC = (n)=>f=>x=>(f)(n(f)(x))
// 前驱
PRED = (n)=>f=>x=>n(g=>h=>h(g(f)))(u=>x)(u=>u)

/////////////
// 算数运算
/////////////
PLUS = (x,y)=>x(SUCC)(y)
SUB  = (x,y)=>y(PRED)(x)
MULT = (x,y)=>f=>x(y(f))

/////////////
// 逻辑运算
/////////////
TRUE  = x=>y=>x
FALSE = x=>y=>y

AND   = (x,y)=>x(y)(FALSE)
OR    = (x,y)=>x(TRUE)(y)
NOT   = (x)=>x(FALSE)(TRUE)

IS_ZERO = x=>x(FALSE)(NOT)(FALSE)
EQUAL = (x,y)=>IS_ZERO(SUB(x,y))

/////////////
// 数据结构
/////////////
PAIR = (x,y)=>f=>f(x)(y)
FST  = (x)=>x(TRUE)
SED  = (x)=>x(FALSE)

// 后继
NEXT  = (p)=>PAIR(SED(p),SUCC(SED(p)))
// 前驱
PRED  = (x)=>FST(x(NEXT)(PAIR(ZERO,ZERO)))

/////////////
// 分支判断
/////////////
IF  = (z,x,y)=>z(x)(y)

/////////////
// 递归循环
/////////////

WHILE = (n,f)=>n(f)

Y = y=>(x =>y(x(x)))(x=>y(n=>x(x)(n)));

// 阶乘计算
fact1 = f=>n=>n?n*f(n-1):1;
fact2 =f=>n=>IF(EQUAL(n,ONE),ONE,MULT(n,x=>f(PRED(n))(x)));

// 5的阶乘
Y(fact1)(5);
Y(fact2)(FIVE)(N)();



/////////////
// 测试
/////////////
Assert = (x,y)=>{
   // lamdba表达式 转 阿拉伯数字
    var trans=x=>x instanceof Function?( num=x(N)()||0):x;
    x=trans(x);
    y=trans(y);
    var color=(x==y)?'color:blue':'color:red';
    var normal='color:#000';
    console.log('λ: %c%s %cequal %c%s %c= %c%s',color,x,normal,color,y,normal,color,(x==y));
};

console.info('---------自然数---------')
Assert(ZERO,ZERO)
Assert(ONE,ONE)
Assert(TWO,TWO)
Assert(THREE,THREE)

Assert(0,ZERO)
Assert(1,ONE)
Assert(2,TWO)
Assert(3,THREE)

console.info('后继函数')
Assert(1,SUCC(ZERO))
Assert(2,SUCC(ONE))
Assert(3,SUCC(TWO))
Assert(4,SUCC(THREE))

console.info('前继函数')
Assert(0,PRED(ONE))
Assert(1,PRED(TWO))
Assert(2,PRED(THREE))
Assert(3,PRED(FOUR))

console.info('---------算数运算---------')
Assert(3,PLUS(ONE,TWO))
Assert(5,PLUS(THREE,TWO))

Assert(1,SUB(THREE,TWO))
Assert(2,SUB(THREE,ONE))

Assert(2,MULT(ONE,TWO))
Assert(6,MULT(THREE,TWO))

console.info('---------逻辑运算---------')
Assert(1,TRUE(1)(0))
Assert(0,FALSE(1)(0))

Assert(0,NOT(TRUE)(1)(0))
Assert(0,AND(TRUE,FALSE)(1)(0))
Assert(1,AND(TRUE,TRUE)(1)(0))
Assert(1,OR(FALSE,TRUE)(1)(0))
Assert(0,OR(FALSE,FALSE)(1)(0))

console.info('---------数据结构---------')
Assert(0,FST(PAIR(ZERO,ONE)))
Assert(1,SED(PAIR(ZERO,ONE)))

Assert(0,FST(NEXT(PAIR(ZERO,ZERO))))
Assert(1,FST(NEXT(NEXT(PAIR(ZERO,ZERO)))))
Assert(2,FST(NEXT(NEXT(NEXT(PAIR(ZERO,ZERO))))))

Assert(3,PRED(FOUR))
Assert(4,PRED(FIVE))

console.info('---------分支---------')
Assert(1,IF(TRUE,1,0))
Assert(0,IF(FALSE,1,0))

console.info('---------循环递归---------')
Assert(4,WHILE(FOUR,SUCC)(ZERO))
Assert(120,Y(fact1)(5))
Assert(120,Y(fact2)(FIVE))