A Lambda-to-Java Compiler

To demonstrate objects and classes (especially anonymous inner classes) to people with functional programming background (SML, Haskell, etc), and for the general fun of it, here is a compiler from the untyped lambda calculus to Java.

In a nutshell, you write a lambda expression, such as

(fun x -> x end fun y -> y end)

in a file, say my.lambda. You give it to the compiler (of course written in Java)

% java -jar lambda2java.jar my.lambda

and you'll get a Java program my.java, which you can then compile and run:

% javac my.java
% java my

Idea of the Compiler

Here is how it works:

Variables remain unchanged.
Applications of the form (E1 E2) are translated to <E1>.apply(<E1>), where <E1> and <E2> are the results of translating E1 and E2, respectively.
Lambda abstractions of the form fun x -> E end are translated to
```
new Lambda() { Lambda apply(Lambda x) { return <c>; } }
```
where Lambda is an abstract class that makes sure that every lambda expression knows how to handle apply.

For people with less-than-firm Java background: the Java syntax new Lambda() { ... } is called an anonymous inner class. It creates a new instance of a class that is built on-the-fly by extending the given class (here Lambda) and adding the methods enclosed in { ... }. Thus, lambda abstractions become objects whose application behavior is defined by the method apply(...), which results from translating the body of the lambda abstraction. Note that lexical scoping is preserved, because in Java's anonymous inner classes, identifiers can be used that refer to declarations outside the inner class. Java's restriction that such identifiers must be final can be easily complied to.

The idea of using anonymous inner classes in Java as target for compiling lambda expressions is also present in Matthew Might's Scheme-to-Java compiler.

Reduction order and correctness

The Java Virtual Machine, restricted to the set of programs that can possibly result from the described translation process, is fairly close to Landin's SECD machine (of course using JVM code, rather than the somewhat more high-level SECD instruction sequences).

Plotkin showed in "Call-by-name, call-by-value and the lambda-calculus" (TCS 1 (1975), 125-159) that this machine faithfully implements a restricted form of the lambda calculus called λ_v. Thanks to Matthias Felleisen for pointing out the relevance of this paper for this work.

More specifically, the reduction implemented by the translation and the JVM reduces only closed expressions, and repeatedly reduces the left-most inner-most redex outside lambda-abstractions.

Another Example

In order to demonstrate that it all works, I added some support for Church numerals. The translated lambda expression is interpreted as a Church numeral, and converted to an integer. Thus, if your lambda expression is

fun f -> fun x -> (f (f x)) end end

then the translated Java program will print the number 2.

As a more elaborate example, here is how to raise the number 3 to the power of 4 in the lambda calculus.

(
 (fun i -> 
   fun j -> (i j) end
  end
  fun f -> fun x -> (f (f (f (f x)))) end end
 )
 fun f -> fun x -> (f (f (f x))) end end
)

The Java program resulting from compiling this lambda expression will print 81, when compiled and run.

Download and Run

Simply download the jar file lambda2java.jar. Then download the power example examples/power.lambda.

Now you can run the compiler, and compile and run the result:

% java -jar lambda2java.jar power.lambda
% javac power.java
% java power
81

If you want to play with the compiler, feel free to download the Java sources from lambda2java.zip.

Restrictions

Since lambda expressions are represented as Java objects whose behavior is defined by Java's own runtime data structures, it would be very difficult to print out the syntax of a lambda expression, for example the result of an evaluation. This explains the emphasis on Church numerals.

However, any lambda expression can be compiled and run. It's just that the result of the evaluation will not be displayed except in terms of Church numerals.

Another restriction is of course that the Java compiler only accepts the results of compiling closed lambda expressions. Lambda expressions with free variables can be compiled to Java, but the resulting Java programs have these variables undefined, and thus cannot themselves be compiled.

Details

Here is how Church numerals are interpreted as integers. The abstract class Lambda that all classes extend supports a as_church_numeral() function, which applies this to an Inc an then to a Zero lambda expression.

abstract class Lambda { 

    // every Lambda has an apply function
    // (to say what it should return, when applied)
    abstract Lambda apply(Lambda x);

    // to demonstrate that this all works,
    // we add functions as_church_numeral and to_int

    // as_church_numeral inteprets _this_
    // as a church numeral by applying
    // it to Inc and Zero
    int as_church_numeral() {
	return this.apply(new Inc()).apply(new Zero()).to_int();
    }

    // non-church-numerals should
    // be spotted as negative numbers
    int to_int() { 
	return -1000000; 
    };
}

// Applying an Inc returns a lambda
// expression whose to_int adds 1 to
// the to_int-result of its argument

class Inc extends Lambda {
    Lambda apply(final Lambda x) {
	return new Lambda() {
	    Lambda apply(Lambda x) { return x; }
	    public int to_int() {
		return x.to_int() + 1;
	    }
	};
    }
}

// a Zero is a lambda expression
// whose to_int returns 0

class Zero extends Lambda {
    Lambda apply(Lambda x) { return x; }
    public int to_int() {
	return 0;
    }
}

The classes above are included in the result of the compilation, to make it self-contained. They are followed by the class that bears the name of your file that contains the lambda expression (in our case power). Here is how it looks, in that case. Note that the result of translating the lambda expression (the part new Lambda() {...}.apply(...) is converted to an integer using as_church_numeral(), and then printed.

class power {
    public static void main(String[] args) {
	 System.out.println(

            new Lambda() {
                Lambda apply(final Lambda i) {
                    return
                    new Lambda() {
                        Lambda apply(final Lambda j) {
                            return
                            i
                            .apply(
                                j
                              )
                            ;
                        }
                    }
                    ;
                }
            }
            .apply(
                new Lambda() {
                    Lambda apply(final Lambda f) {
                        return
                        new Lambda() {
                            Lambda apply(final Lambda x) {
                                return
                                f
                                .apply(
                                    f
                                    .apply(
                                        f
                                        .apply(
                                            f
                                            .apply(
                                                x
                                              )
                                          )
                                      )
                                  )
                                ;
                            }
                        }
                        ;
                    }
                }
              )
            .apply(
                new Lambda() {
                    Lambda apply(final Lambda f) {
                        return
                        new Lambda() {
                            Lambda apply(final Lambda x) {
                                return
                                f
                                .apply(
                                    f
                                    .apply(
                                        f
                                        .apply(
                                            x
                                          )
                                      )
                                  )
                                ;
                            }
                        }
                        ;
                    }
                }
              )

            .as_church_numeral()
        );
    }
}

Homework

Compute the factorial of 5 using lambda2java. Here are the steps needed:
- Write a call-by-value fixed point combinator in the syntax used here.
- Write the factorial function in the lambda calculus, using Church numerals, in a form where the recursive call is abstracted out (see (Y Y) Works!, a lecture by Matthias Felleisen). You find ingredients such as conditionals, multiplication, and the predecessor function here.
- Write the number 5 in the Church encoding.
- Put together a lambda expression of the form ((<Y> <factorial>) <five>), where <Y> is the Y combinator, <factorial> the factorial function, and <five> the encoding of the number 5, mentioned above.
- Compile the lambda expression to Java, using lambda2java, and compile and run the Java program.
Implement the factorial function using lambda2java. Here are the steps needed, in addition to Homework 1:
- Write a function String int2church(int x) which generates a lambda expression for the given integer, using Church's encoding, as a Java String.
- Put it all together in a Java program int2factorial that takes an integer i, and generates a lambda expression, which applies the fixed point combinator to the factorial function, and then to the result of int2church applied to i.
- To compute the factorial of a number, you would have to call int2factorial, then compile the resulting lambda expression to Java using lambda2java, and finally compile and run the Java program.
- It would be cool to do the latter compilation step from within int2factorial; your factorial program would then implement the factorial function by first generating a lambda expression, then compiling it to Java, and then compiling it to JVM code, and finally running it!

Martin Henz