js-lambda

DSL for lambda calculus

npm install js-lambda
2 downloads in the last week
8 downloads in the last month

build status

js-lambda

DSL for, but not limited to, the lambda calculus.

USAGE

In Browser

<script src="lambda.js" charset="UTF-8"></script>

node.js

var lambda = require('./lambda.js').lambda,
λ = lambda;

SYNOPSIS

lambda("x:x")(42) === 42;
λ("x:x")(42) === 42;                        // λ = lambda
λ("n:n<=1?n:n*_0(n-1)")(10) === 3628800;    // _0 for recursion
λ("x,y:Math.sqrt(x*x+y*y)")(3,4) === 5;     // multiple arguments, 
λ("x:λ(y:Math.sqrt(x*x+y*y))")(3)(4) === 5; // λ can be nested
// church numerals
var cn2num = λ("f:f(λ(n:n+1))(0)"),
succ = λ("n:λ(f:λ(x:f(n(f)(x))))"),
zero = λ("f:λ(x:x)"),
one = succ(zero),
add = λ("m:λ(n:m("+succ+")(n))"),
two = add(one)(one),
mul = λ("m:λ(n:m("+add+"(n))("+zero+"))"),
four = mul(two)(two),
pow = λ("b:λ(e:e(b))"),
sixteen = pow(two)(four);
cn2num(sixteen) === 16;

DESCRIPTION

This script exports lambda() and its alias λ(). As seen in the synopsis, it is a DSL compiler that returns a function.

the lambda notation

As seen in SYNOPSYS,

lambda(arg0,arg1,...argn:expression)

Turns into:

function(arg0, arg1, ...argn){return expression }

nesting and recursion

As seen in SYNOPSYS, the lambda can be nested.

λ('x:λ(y:Math.sqrt(x*x+y*y))');

Turns into:

function _0(x){return function _1(y){return Math.sqrt(x*x+y*y)}}

As seen above, the function is named accordingly to De Bruijin index. _n is the nth level function.

Use the name to implement self-recursion. The strict mode has deprived us of beloved arguments.callee but with lambda.js, it is as short as _0.

// function fact(n){ return n <= 1 ? n : n * fact(n-1) }
λ("n:n<=1?n:n*_0(n-1)");

limitation

To use lexical functions, you have to "interpolate".

var succ = λ("n:λ(f:λ(x:f(n(f)(x))))"),
add = λ("m:λ(n:m("+succ+")(n))");    // λ("m:λ(n:m(succ)(n))") does not work

This is because lambda() needs to eval() to compile the function but lexicals are out of its scope.

memoization

By default, the compiled function is memoized. Suppose you have:

function rms(ary) {
    return Math.sqrt(ary.reduce(λ("t,x:t+x*x"), 0))
}

And you use rms over and over, the same function is used throughout the session. If that is not what you want, you can suppress it by passing truish value to the second argument:

var uncached = lambda("a,b,c:...", true);

And if you wish, you can inspect cached functions via lambda.memo.

SEE ALSO

npm loves you