Java 8 and lambda calculus equivalent

Question

Does anybody have any idea on how to write the basic expressions of (untyped) lambda calculus in java? i.e.

• identity (λx.x),
• self application (λx.x x) and
• function application (λx.λarg.x arg)

Java is not untyped, so I guess any solution will have to accomodate types. But I only found the following, cumbersume to read, solutions:

static<T> Function<T,T> identity() {
    return x->x;
}

static<T> Function<? extends Function<? super Function,T>,T> self() {
    return x->x.apply(x);
}

static <B,C> Function<? extends Function<B,C>, Function<B,C>> apply() {
   return x -> arg -> x.apply(arg);
}

and I am not even sure they are correct(!). Can anybody propose a better alternative?

---

Edit: Note, that I am trying to apply the basic notions of lambda calculus with as little as possible of syntactic sugar or ready-made functions. E.g. I know there is identity(), BiFunction etc. I am trying to implement the above with only the basic lambda constructs available, and that means basically only function application

Answer 1

Your solutions for identity and application are correct. If wouldn't define them as functions however, I find x->x and Function::apply as readable as identity() and apply(), so I would simply use them directly.

As for self-application, well, as you note Java is typed, and also in typed lambda calculus self-application is impossible (at least in all typed lambda calculi I know). You can produce something by using raw types (like you did), but then you essentially throw away the part of the type system.

But also, why do you need all this?

Answer 2

What your looking for is this type(translated from table 19 of cardelli's type systems paper).

interface Untyped {
    Untyped call(Untyped x);
}

This type cleanly embeds the untyped lambda calculus's terms.

static Untyped identity = x -> x;
static Untyped self = x -> x.call(x);
static Untyped apply = f -> x -> f.call(x);