install

tutorials

- Java API

- Java + LISP

- Lisp Repl

- Assembler

Javadoc

Lisp manual

fun4j - functional programming for the JVM

The functional assembler

The lowest level API that fun4j provides is the functional assembler. This assembler allows to build up AST representations of functions and compile them to Java bytecode, implementing the org.fun4j.Function interface. I'll just cover the most basic stuff here, as most users will prefer to use the highlevel APIs.

Assembling simple non-recursive functions

Let's assume we want to write a Function that computes the powers of two of its input, that is f(x) => x*x. We will have to define a function Expression that performs an integer multiplication, taking the single variable x as both its arguments. The AST expression for looking up the first local variable of a function invocation is new Var(0). The AST expression for multiply is new Mul(exp1, exp2). Thus the Expression representing f(x) = x*x becomes: new Mul(new Var(0), new Var(0)).

// org.fun4j.Template is the central facade to the fun4J API. 
// A default instance can be obtained by a static import:
import static org.fun4j.Template.fun4j;

// f(x) => x*x
Expression expPower = new Mul(new Var(0), new Var(0));

This expression can then be compiled to a Function object and applied to an Integer to compute, say, powers of two of seven:

Function power = fun4j.compile(expPower, "power");

System.out.println(power.apply(7));

Here comes another simple example where we write a function that adds two values (f(x,y) = x + y).

Expression expAdd = new Add(new Var(0), new Var(1));
Function add = fun4j.compile(expAdd, "add");

System.out.println(power.apply(add.apply(3, 4)));

Assembling recursive functions

That looks quite simple so far, didn't it? Now we want to see how recursive function can be implemented. So let's start with the 'Hello World' of recursion: the notorious factorial function:

factorial(0) = 1
factorial(n) = n * factorial(n - 1)

As an AST expression we can define this as follows:

Expression expFac = new If(new NumEq(new CstInt(0), new Var(0)), 
                           new CstInt(1), 
                           new Mul(new Var(0), new Recurse(new Sub1(new Var(0)))));
						
Function fac = fun4j.compile(expFac, "fac");
System.out.println(fac.apply(5))						

Assembling higher order functions

In this section we will have a look at higher-order functions. As an example we take Summing from 0 to n over a function fun:

sum(0, fun) = fun(0)
sum(n, fun) = fun(n) + sum(n-1, fun)

This can be defined as an AST Expression as follows:

Expression expSum = new If(new NumEq(new Var(0), new CstInt(0)), 
                           new Apply(new Var(1), new Var(0)), 
                           new Add(new Apply(new Var(1), new Var(0)), 
                                   new Recurse(new Sub1(new Var(0)), new Var(1))));
Function sum = fun4j.compile(sum, "sum");

// id: f(x) => x
Function id = fun4j.compile(new Var(0), "id");

// testing higher order functions, computing sum(x) and sum(x*x)
System.out.println(sum.apply(100, id));
System.out.println(sum.apply(100, power));

Tailcall optimization (TCO)

Fun4j comes with support for optimization of tail recursive functions. The compiler traverses AST graphs and looks for Recurse expressions in tail-position. If such an expression is found it is marked and instead of bytecode for a full recursive function call (including allocation of a new stack-frame) bytecode is emitted that manipulates the current stack frame to contain the values for the next "recursive" call and executes the body of the function again. If you want to see how this works in detail have a look at org.fun4j.compiler.expressions.Recurse.compile(MethodVisitor mv).

Now let's see how this works for a simple tail-recursive function that counts down from n to zero:

countdown(0) = 0
countdown(n) = countdown(n-1)

This function can be written as an AST Expression as follows:

Expression expCount = new If(new NumEq(new CstInt(0), new Var(0, "n")), 
                             new CstInt(0),
                             new Recurse(new Sub1(new Var(0, "n"))));

On compilation the compiler will detect that the Recurse expression is in a tail position. (Compare this to the Recurse expressions in expSum and expFac that are not in tail positions but nested into Add and Mul expressions.) Now let's see if it really works:

Function count = fun4j.compile(expCount, "count");
// this would cause a stack overflow without tail call optimization:
count.apply(1000000);

These are the basics about the AST assembler. As we have seen, this Assembler can be used to compile functional expressions into efficient Java bytecode.

Roll your own...

The fun4j Lisp compiler pre-compiles lambda-terms into AST Expressions and gets them compiled into Java Bytecode in the way we have studied in the previous examples. Have a closer look at org.fun4j.compiler.Parser and org.fun4j.compiler.Compiler to see how straight-forward this works.

So in order to build an implementation for your functional language of choice just add a Parser and you have a fully operational implementation with garbage collection and tail code optimization for free.

I'm happy that you did not quit reading somewhere en route but have studied all these rather dry examples with so much patience. Thanks a lot for your interest! If you have further questions or suggestions don't hesitate to contact me.