Lambda calculus in JavaScript syntax

Syntax

LambdaJavaScriptJavaScript 1.8
variablexxx
abstractionλx.M or \x.Mfunction(x){ return M }function(x) M
application((M) N)(M)(N)(M)(N)
declaration-var a = M;let a = M;
syntactic sugar
λx…yz.M
for λx…y.λz.M
λx.M N
for λx.(M N)
(x M)
for ((x) M)
(L M N)
for ((L M) N)
function(x,…,y,z){ return M }
for function(x,…,y){ return function(z){ return M } }
x(M)
for (x)(M)
L(M)(N)
for (L(M))(N)
function(x,…,y,z) M
for function(x,…,y) function(z) M
x(M)
for (x)(M)
L(M)(N)
for (L(M))(N)

Example

code1
(function(x){ return x })(a)

run code1

code2
(function(x,y){ return x })(a)

run code2

code3
var k = function(x,y){ return x };
k(a)(b)

run code3

code4
var s = function(x,y,z){ return x(z)(y(z)) };
var k = function(x,y){ return x };
s(k)(k)

run code4

code5
var s = function(x,y,z){ return x(z)(y(z)) };
var k = function(x,y){ return x };
s(a)(k)(c)

run code5

code6
var o = function(x){ return x(x)(c) };
o(o)

run code6

code7 (leftmost outermost)
var k = function(x,y){ return x };
var o = function(x){ return x(x)(c) };
k(a)(o(o))

run code7

code8 (call by value)
var k = function(x,y){ return x };
var o = function(x){ return x(x)(c) };
k(a)(o(o))

run code8

code9
var _0 = function(s,z){ return z };
var _1 = function(s,z){ return s(z) };
var _2 = function(s,z){ return s(s(z)) };
var _3 = function(s,z){ return s(s(s(z))) };

var add = function(m,n,s,z){ return m(s)(n(s)(z)) };

add(_2)(_3)

run code9

code10
var pair = function(P,Q,x){ return x(P)(Q) }; // cons
var fst = function(p){ return p(function(x,y){ return x }) }; // car
var snd = function(p){ return p(function(x,y){ return y }) }; // cdr

var p1 = pair(pair(a)(b))(pair(c)(d));
fst(snd(p1))

run code10

code11
var t = function(x,y){ return x }; // true
var f = function(x,y){ return y }; // false
var cond = function(B,P,Q){ return B(P)(Q) }; // if-then-else
cond(t)(a)(b) // if true then a else b

run code11

code12
var Y = function(f){ return (function(x){ return f((x)(x)) })(function(x){ return f((x)(x)) }) };

var _0 = function(s,z){ return z };
var _1 = function(s,z){ return s(z) };
var _2 = function(s,z){ return s(s(z)) };
var _3 = function(s,z){ return s(s(s(z))) };

var t = function(x,y){ return x }; // true
var f = function(x,y){ return y }; // false
var if0 = function(n){ return n(function(x){ return f })(t) }; // if n equals to _0

var mul = function(m,n,s,z){ return n(m(s))(z) };
var pred = function(n,s,z){ return n(function(f,g){ return g(f(s)) })(function(x){ return z })(function(x){ return x }) };

var fact = function(r,n){ return if0(n)(_1)(mul(n)(r(pred(n)))) };
Y(fact)(_3)

run code12

Source code

See: http://github.com/tarao/LambdaJS