lambda

lambda is a really tiny library that brings lambda calculus in Java.

Introduction

One of the goals of the project is to make Java look like lambda calculus as much as possible. The identity function , for example, is pretty close.

λ I = (λ x) -> x;

β-reductions are introduced by the word β; for example, the function becomes

λ AND = (λ a) -> (λ b) -> β(a, b, a);

Performances

Long story short, it sucks, but it has never been the goal.

Function Library

The library contains a good number of λ-expressions. For example, three different fixed-point combinators (X, Y, and Θ).

λ X = (λ f) -> β((λ x) -> β(x, x), (λ x) -> β(f, β(x, x)));
λ Y = (λ f) -> β((λ x) -> β(f, β(x, x)), (λ x) -> β(f, β(x, x)));
λ Θ = β((λ x) -> (λ y) -> β(y, β(x, x, y)), (λ x) -> (λ y) -> β(y, β(x, x, y)));

Church encoding for numbers through 16 and powers of two through 1024 have been implemented.

λ ZERO  = (λ f) -> (λ x) -> x;
λ ONE   = β(SUCC, ZERO);
λ TWO   = β(SUCC, ONE);
// ...
λ ONETHOUSANDTWENTYFOUR = β(EXP, TWO, TEN);

Standard high-order functions such as FILTER, MAP, FOLDL and FOLDR.

Examples

λ FACT = β(Y, (λ f) -> (λ n) -> β(IF, β(LEQ, n, ONE),
                                      ONE,
                                      β(MUL, n, β(f, β(PRED, n)))));

λ FIB = β(Y, (λ f) -> (λ n) -> β(IF, β(LEQ, n, TWO),
                                     ONE,
                                     β(ADD, β(f, β(PRED, n)), β(f, β(SUB, n, TWO)))));

λ COLLATZ = β(Y, (λ f) -> (λ n) -> β(IF, β(EQ, n, ONE),
                                         β(CONS, ONE, NIL),
                                         β(CONS, n, β(f, β(IF, β(ISEVEN, n),
                                                               β(DIV, n, TWO),
                                                               β(SUCC, β(MUL, n, THREE)))))));

λ SORT = β(Y, (λ f) -> (λ l) -> β(IF, β(ISNIL, l),
                                      NIL,
                                      β(CAT, β(CAT, β(f, β(FILTER, β(FLIP, LEQ, β(HEAD, l)), β(TAIL, l))),
                                                         β(CONS, β(HEAD, l), NIL)),
                                             β(f, β(FILTER, β(FLIP, GREAT, β(HEAD, l)), β(TAIL, l))))));