This is the third part of a series of posts introducing principles from functional programming to OO developers, primarily using Java. In the first two parts, we covered the visitor pattern and basic use of continuations, as well as functional data structures and more advanced use of continuations. We used a basic example of expression evaluation for illustration. I urge you to read the preceeding parts if you have not already, as this part will not make much sense on its own.
In this third and penultimate part, we’ll first add a simple extension of our expression language to illustrate how we can add syntactical sugar to easily extend the usability of our language. We’ll then pick up the cliff-hanger from the second part considering the differences in expression evaluation using a direct evaluator and one using a continuation, and build on this to illustrate the difference between interpreted and JIT-compiled code. We’ll then provide hints for further experimentation to extend our expression language with named functions illustrating even fancier continuations.
Adding Square Functions to our Expressions and Syntactic Sugar
Let’s extend our language with a new Square primitive representing computing the square of a number:
class Square<T> extends Expression<T> { Expression<T> expression; public Square(Expression<T> expression) { this.expression = expression; } public <V> V visit(FancyExpressionVisitor<T, V> visitor) { return visitor.visit(this, expression.visit(visitor)); } @Override public <V> V visit(SimpleExpressionVisitor<T, V> visitor) { if (visitor instanceof FancyExpressionVisitor<?, ?>) { return visit((FancyExpressionVisitor<T, V>) visitor); } throw new IllegalArgumentException(); } } interface FancyExpressionVisitor<T, V> extends ExpressionVisitor<T, V> { V visit(Square<T> square, V expression); } class FancierExtendedToString<T> extends FancyExtendedToString<T> implements FancyExpressionVisitor<T, Function<StringBuilder, StringBuilder>> { @Override public Function<StringBuilder, StringBuilder> visit(Square<T> square, Function<StringBuilder, StringBuilder> expression) { return sb -> { sb.append('('); sb = expression.apply(sb); sb.append("^2)"); return sb; }; } }
This should be relatively standard by now; we add a new AST node and extend our visitor to handle the new node, completely analogous to how we added variables in part 2. You might note that we have only extended the ToString visitor, not the IntegerAlgebra visitor, and this is on purpose. We are going to treat this new functionality as purely syntactic sugar. Instead of handling the square function specially, we instead implement a visitor that removes the newly added syntactic sugar from our AST (it desugars it), so we can use the FancyIntegerAlgebra we already implemented in part 2:
class SquareDesugar<T> implements FancyExpressionVisitor<T, Expression<T>> { @Override public Expression<T> visit(Variable<T> variable, String name) { return new Variable<>(name); } @Override public Expression<T> visit(Assignment<T> assignment, String name, Expression<T> value, Expression<T> next) { return new Assignment<>(name, value, next); } @Override public Expression<T> visit(Constant<T> constant, T value) { return new Constant<>(value); } @Override public Expression<T> visit(Plus<T> plus, Expression<T> left, Expression<T> right) { return new Plus<>(left, right); } @Override public Expression<T> visit(Times<T> times, Expression<T> left, Expression<T> right) { return new Times<>(left, right); } @Override public Expression<T> visit(Square<T> square, Expression<T> expression) { return new Assignment<>("s", expression, new Times<>(new Variable<>("s"), new Variable<>("s"))); } }
This visitor transforms an Expression tree into another Expression tree. Most of the nodes are copied directly, but the last, the Square node, is instead transformed into an assignment and a multiplication.
Exercise: why do we construct new copies of the first five expression nodes instead of just returning the original?
Consider the expression (5^2) + 1
We need to make clones because sub-elements may have changed if we are using a Square inside a larger expression. In functional programming it is custom to not alter objects but instead create new ones, so the only way to ensure that a Square inside a Plus is transformed correctly is to create a new Plus based on transformed children.
We could in principle just return the passed Constants and Variables as they can never contain sub-expressions, and doing so would be more efficient (and acceptable since we never alter objects).
In functional languages the developer is forced to crate new objects instead of mutating existing ones, in object oriented languages this is not a requirement, but can be very beneficial as it reduces errors due to unintended or concurrent modifications, and allows developers to ignore locking altogether. I strongly encourage all OO developers to never modify objects unless they represent a complex data structure that is either long-lived or persisted to external storage, like a database.
We can now use our extended expressions as such:
Expression<Integer> integerExpression = new Square<>( new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3))); System.out.println("Original expression: " + integerExpression.visit(new FancierExtendedToString<>()).apply(new StringBuilder()).toString()); Expression<Integer> desugaredExpression = integerExpression.visit(new SquareDesugar<>()); System.out.println("Desugared expression: " + desugaredExpression.visit(new FancierExtendedToString<>()).apply(new StringBuilder()).toString()); System.out.println(desugaredExpression.visit(new FancyIntegerAlgebra()).apply(FunctionMap.empty())); assertThrows(IllegalArgumentException.class, () -> integerExpression.visit(new FancyIntegerAlgebra()));
We construct an expression using our new Square construct. We can put anything into the expression, even other Squares or expressions using the variable s, and it will work due to how we have implemented scoped variables.
Exercise: Make sure you understand why we can nest squares. Try implementing an expression with multiple Squares and uses of the variable s, and consider what the value of s is throughout the evaluation. This is a mouthful because variables work differently in functional languages than they do in Java, but you can think of how you can use a variable named s in two different methods for two different things.
Our code then prints out the expression along with the first-order support for squares and constructs a desugared expression which is printed as well. Note how the desugared expression has no mention of Square anymore. We could in fact use the FancyExtendedToString from part 2 to print the desugared expression instead of the new one.
We evaluate our desugared expression using our old FancyIntegerAlgebra; it works just fine and produces the expected result. Evaluating the original expression will yield an error because our old visitor does not know what to do with the new Square AST node.
It can be very beneficial to add such syntactic sugar to programming languages as it can make the language easier for the developer to use without really adding complexity to the visitor. We just saw we could add an entirely new built-in function without having to touch our visitor at all, and it just worked.
Exercise: Extend the language with a function x^4 that raises an expression to the fourth power. Try implementing direct desugaring all the way to our original simple language, desugaring to our language with Squares (using either or both of the equalities that x^4 = x^2 * x^2 = (x^2)^2), and a single desugaring from a language supporting both x^4 and x^2.
Interpreted and JIT-compiled Code Execution
If this were written 15-20 years ago, I could claim that there are two main paradigms when it comes to program execution: interpreted code and compiled code. Interpreted code keeps a representation of our high-level code in memory and executes it by inspecting the high-level representation. The IntegerAlgebra class from part 1 implements interpretation of our expressions. It represents expressions using the abstract syntax tree data structure represented by the Expression class and its subclasses, and executes it by inspecting each node in the AST using a visitor. Compiled code instead uses a compiler to translate the abstract representation directly into machine executable code. It is out of scope of this post to explain how this happens exactly, but you can think of it as this bit of code
Expression<Integer> integerExpression = new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3)); System.out.println(integerExpression.visit(new IntegerAlgebra()));
getting translated into this bit of code:
int integerExpression = (5 * 7) + 3; System.out.println(integerExpression);
The example is not perfect as both pieces of code are Java, but it is close enough to get the idea, and it should be clear that the second bit of code is faster to run. The system does not have to traverse and selectively execute code for each node of the AST.
More recently, there is also an intermediate step, where applications are not exactly interpreted and not exactly compiled. The application has a representation of the entire program, like interpreted code, but will turn it into faster executable code just before executing it. Just-in-time for executing, if you will.
If we consider the cliff-hanger from last time:
System.out.println("Starting simple evaluation"); Integer simpleEvaluation = integerExpression.visit(new IntegerAlgebra()); System.out.println("Simple evaluation done"); System.out.println("Simple result: " + simpleEvaluation); System.out.println("Starting fancy evaluation"); Function<Function<String, Integer>, Integer> fancyEvaluation = integerExpression .visit(new FancyIntegerAlgebra()); System.out.println("Fancy evaluation done"); System.out.println("Fancy result: " + fancyEvaluation.apply(FunctionMap.empty())); System.out.println("Fancy result again: " + fancyEvaluation.apply(FunctionMap.empty()));
we notice that for the first block of code, we print out visiting the different nodes and then the result. Not much else we can do: we traverse the AST only once. For the second block, we notice that we print out only half of the logging, the half mentioning visiting the nodes, during the evaluation phase and then print that the evaluation is done. We then apply the generated continuation twice to print the result twice, and now we get the second half of the logging, the half mentioning evaluating the nodes, during each evaluation. We can think of the visit step as JIT compiling the expressions into executable code, and the evaluation step as executing the code. We can test the performance of the two kinds of execution:
Expression<Integer> integerExpression = new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3)); long before = System.currentTimeMillis(); for (int i = 0; i < 1000000000; i++) { integerExpression.visit(new IntegerAlgebra()); } integerExpression.visit(new SimpleToString<>()); System.out.println("interpreted: " + (System.currentTimeMillis() - before)); before = System.currentTimeMillis(); Function<Function<String, Integer>, Integer> fancyEvaluation = integerExpression .visit(new FancyIntegerAlgebra()); for (int i = 0; i < 1000000000; i++) { fancyEvaluation.apply(FunctionMap.empty()); } integerExpression.visit(new SimpleToString<>()); System.out.println("JIT compiled: " + (System.currentTimeMillis() - before));
You’re going to want to comment out the logging in the two visitors before running or this will never terminate. If we do so, we get that running the interpreted code one billion times takes 3926 ms while running the JIT-compiled code one billion times takes only 2675 ms. We only visit the AST once but can apply the resulting continuation more times, resulting in 32% faster executing code. The reason the speed gain is not larger is due to how Java works and a language built purposely to handle this sort of code can do it much faster.
Java has multiple memory areas. One is the heap and another is the stack. If you remember back in part 1, I mentioned that certain code could not be executed with a too large parameter without increasing the Java stack size.
The stack is used to handle method calls and has very fast memory management for that exact purpose. Java objects live in the heap, which is good for all-purpose memory where objects are created, live for a while and are then cleaned up by a garbage collector. The Java heap is much slower than the stack.
Normally when calling functions, the stack is used, but when using anonymous functions, an object is created on the heap. This also happens in our FancyIntegerAlgebra when it is constructing the continuation. This is a limitation of how anonymous functions are implemented in Java due to backwards compatibility, and is the reason our JIT-compiled code is only 32% faster than the interpreted code instead of hundreds or thousands of times faster: instead of traversing an object graph consisting of AST nodes, we are instead traversing an object graph consisting of anonymous function nodes. Some languages do not have the overhead of constructing functions objects on the heap and can therefore execute our JIT-compiled code much more efficiently.
Adding Named Functions to our Expressions
Having split the code into a JIT-compilation phase and an execution phase, we also notice that we can use our continuations in a different way. So far, our assignments are not terribly useful: we’d have to bind a name to a value and then use it immediately. What if we could split those two apart? What if we created an expression using an undefined variable?
Expression<Integer> squareExpression = new Times<>(new Variable<>("a"), new Variable<>("a")); System.out.println("Starting square evaluation"); Function<Function<String, Integer>, Integer> squareEvaluation = squareExpression .visit(new FancyIntegerAlgebra()); System.out.println("Square evaluation done"); assertThrows(IllegalArgumentException.class, () -> squareEvaluation.apply(FunctionMap.empty()));
Here, we define an expression representing a * a, just like our Square extension above. We can successfully JIT-compile the code, but we get an error when we try executing it. That makes sense: the variable a is not defined, so the expression does not make sense. But what if a were defined, then the expression would make sense… You may have noticed that every time we invoke the continuation, we pass it an empty FunctionMap. That’s the initial environment of variables. Normally, we say that no variables are defined, but nothing prevents us from providing a value for a. For example, we could continue the code snippet above with the following lines:
System.out.println("Square result of 5: " + squareEvaluation.apply(FunctionMap.put(FunctionMap.empty(), "a", 5))); System.out.println("Square result of 7: " + squareEvaluation.apply(FunctionMap.put(FunctionMap.empty(), "a", 7)));
Now, we can execute the same continuation, which we have only JIT-compiled once, two times with different parameters. The code will no longer fail, because as soon as a is needed, our application will find it is already defined. We now get two different results, 25 and 49, corresponding to the square of the two parameters 5 and 7. We have just used our JIT-compiler to create a function that we cannot only execute faster than the interpreted version one billion times with the same parameter, but we can even execute it faster one billion times with different parameters, computing different results.
At this point, an idea might spring to mind: using syntactic sugar, the language developer can easily add new functionality to the language. What if the language user could do the same? Couldn’t we just view a user function as a variable that can contain a continuation?
Exercise: Implement named functions using “function variables” that can contain continuations.
For simplicity, only consider functions with one variable and assume that variable has a particular name, e.g., p for parameter.
When we introduced variables, we introduced two new AST nodes, Assignment for assigning an expression to a name and Variable for using a predefined name. We will want something analogous for functions, say a FunctionDefinition and a FunctionApplication.
A FunctionDefinition needs a function name (String) for the function we define, a function body (Expression) and a “next” expression, very similar to an Assignment. Since we’re assuming exactly one parameter with a given name, we do not need to represent that.
A FunctionApplication needs a function name for the function we wish to use, and a parameter (Expression) we wish to pass to the function.
For our simple language, we can actually implement functions as another desugaring step, but the desugaring will require using a continuation taking a map of function definitions and returning an expression.
abstract class FunctionExpression<T> extends Expression<T> { public abstract <V> V visit(FunctionExpressionVisitor<T, V> visitor); @Override public <V> V visit(SimpleExpressionVisitor<T, V> visitor) { if (visitor instanceof FunctionExpressionVisitor<?, ?>) { return visit((FunctionExpressionVisitor<T, V>) visitor); } throw new IllegalArgumentException(); } } class FunctionDefinition<T> extends FunctionExpression<T> { String name; Expression<T> body; Expression<T> next; public FunctionDefinition(String name, Expression<T> body, Expression<T> next) { this.name = name; this.body = body; this.next = next; } public <V> V visit(FunctionExpressionVisitor<T, V> visitor) { return visitor.visit(this, name, body.visit(visitor), next.visit(visitor)); } } class FunctionApplication<T> extends FunctionExpression<T> { String name; Expression<T> parameter; public FunctionApplication(String name, Expression<T> parameter) { this.name = name; this.parameter = parameter; } public <V> V visit(FunctionExpressionVisitor<T, V> visitor) { return visitor.visit(this, name, parameter.visit(visitor)); } } interface FunctionExpressionVisitor<T, V> extends ExpressionVisitor<T, V> { V visit(FunctionDefinition<T> functionDefinition, String name, V body, V next); V visit(FunctionApplication<T> functionApplication, String name, V parameter); } class FunctionDesugar<T> implements FunctionExpressionVisitor<T, Function<Function<String, Expression<T>>, Expression<T>>> { @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(Variable<T> variable, String name) { return e -> new Variable<>(name); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(Assignment<T> assignment, String name, Function<Function<String, Expression<T>>, Expression<T>> value, Function<Function<String, Expression<T>>, Expression<T>> next) { return e -> new Assignment<>(name, value.apply(e), next.apply(e)); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(Constant<T> constant, T value) { return e -> new Constant<>(value); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(Plus<T> plus, Function<Function<String, Expression<T>>, Expression<T>> left, Function<Function<String, Expression<T>>, Expression<T>> right) { return e -> new Plus<>(left.apply(e), right.apply(e)); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(Times<T> times, Function<Function<String, Expression<T>>, Expression<T>> left, Function<Function<String, Expression<T>>, Expression<T>> right) { return e -> new Times<>(left.apply(e), right.apply(e)); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit(FunctionDefinition<T> functionDefinition, String name, Function<Function<String, Expression<T>>, Expression<T>> body, Function<Function<String, Expression<T>>, Expression<T>> next) { return e -> next.apply(FunctionMap.put(e, name, body.apply(e))); } @Override public Function<Function<String, Expression<T>>, Expression<T>> visit( FunctionApplication<T> functionApplication, String name, Function<Function<String, Expression<T>>, Expression<T>> parameter) { return e -> new Assignment<>("p", parameter.apply(e), e.apply(name)); } }
which can be used as:
FunctionDefinition<Integer> functionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new Constant<>(5))); Expression<Integer> desugaredExpression = functionExpression.visit(new FunctionDesugar<>()) .apply(FunctionMap.empty()); System.out.println(desugaredExpression.visit(new FancyExtendedToString<>()).apply(new StringBuilder())); System.out.println(desugaredExpression.visit(new FancyIntegerAlgebra()).apply(FunctionMap.empty())); FunctionDefinition<Integer> nestedFunctionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new FunctionApplication<>("square", new Constant<>(5)))); desugaredExpression = nestedFunctionExpression.visit(new FunctionDesugar<>()).apply(FunctionMap.empty()); System.out.println(desugaredExpression.visit(new FancyExtendedToString<>()).apply(new StringBuilder())); System.out.println(desugaredExpression.visit(new FancyIntegerAlgebra()).apply(FunctionMap.empty()));
If we implement functions using desugaring, it means we’ll clone the function body in our JIT-compilation step each time we use it. This can have benefits if the function is small, but means our program gets large if the function body is large and we use the function many times. Our code will also fail miserably if we try using recursion (functions calling themselves), though that does not make sense at this point anyway.
It can therefore be beneficial to support functions directly. Try extending the existing FancyIntegerAlgebra to also handle our new AST nodes. You will likely want a second FunctionMap to contain function bodies just like in the desugaring code, so the Java interface BiFunction can be useful. As tempting as it might be, you cannot extend the FancyIntegerAlgebra, but have to copy it due to how the code is organized.
class FunctionIntegerAlgebra implements FunctionExpressionVisitor<Integer, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer>> { @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( Constant<Integer> constant, Integer value) { return (env, fenv) -> { return value; }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( Plus<Integer> plus, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> left, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> right) { return (env, fenv) -> { return left.apply(env, fenv) + right.apply(env, fenv); }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( Times<Integer> times, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> left, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> right) { return (env, fenv) -> { return left.apply(env, fenv) * right.apply(env, fenv); }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( Variable<Integer> variable, String name) { return (env, fenv) -> { return env.apply(name); }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( Assignment<Integer> assignment, String name, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> value, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> next) { return (env, fenv) -> { return next.apply(FunctionMap.put(env, name, value.apply(env, fenv)), fenv); }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( FunctionDefinition<Integer> functionDefinition, String name, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> body, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> next) { return (env, fenv) -> { return next.apply(env, FunctionMap.put(fenv, name, functionDefinition.body)); }; } @Override public BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> visit( FunctionApplication<Integer> functionApplication, String name, BiFunction<Function<String, Integer>, Function<String, Expression<Integer>>, Integer> parameter) { return (env, fenv) -> { return fenv.apply(name).visit(this).apply(FunctionMap.put(env, "p", parameter.apply(env, fenv)), fenv); }; } }
The first five cases are relatively simple. We introduce a second parameter, fenv, to hold function definitions and just pass it along, otherwise duplicating the code from the FancyIntegerAlgebra.
We handle FunctionDefinitions by just storing the function body in the function environment, similar to how we handle variable definitions.
We handle FunctionApplications by looking up the function definition in fenv, compiling it using the visitor, and using the resulting code with a new environment where we define p to contain the value of evaluating the parameter.
This code can be used like this:
FunctionDefinition<Integer> functionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new Constant<>(5))); System.out.println( functionExpression.visit(new FunctionIntegerAlgebra()).apply(FunctionMap.empty(), FunctionMap.empty())); FunctionDefinition<Integer> nestedFunctionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new FunctionApplication<>("square", new Constant<>(5)))); System.out.println( nestedFunctionExpression.visit(new FunctionIntegerAlgebra()).apply(FunctionMap.empty(), FunctionMap.empty()));
The above implementation has issues; what are they?
Consider when (and how often) we do the JIT-compilation of the function body.
To avoid compiling the used function for each use, we’ll change our code to store continuations in the function map instead. To do that, we combine the idea from reusing continuations to compute the same expression with different parameters with the desugaring step and a new visitor. We end up with a visitor that computes a continuation that computes a continuation. The outer continuation does the compilation and function lookup, and the inner does the actual computation.
class BetterFunctionIntegerAlgebra implements FunctionExpressionVisitor<Integer, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>>> { @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( Constant<Integer> constant, Integer value) { return fenv -> env -> { return value; }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( Plus<Integer> plus, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> left, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> right) { return fenv -> { Function<Function<String, Integer>, Integer> l = left.apply(fenv); Function<Function<String, Integer>, Integer> r = right.apply(fenv); return env -> { return l.apply(env) + r.apply(env); }; }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( Times<Integer> times, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> left, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> right) { return fenv -> { Function<Function<String, Integer>, Integer> l = left.apply(fenv); Function<Function<String, Integer>, Integer> r = right.apply(fenv); return env -> { return l.apply(env) * r.apply(env); }; }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( Variable<Integer> variable, String name) { return fenv -> env -> { return env.apply(name); }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( Assignment<Integer> assignment, String name, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> value, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> next) { return fenv -> { Function<Function<String, Integer>, Integer> v = value.apply(fenv); Function<Function<String, Integer>, Integer> n = next.apply(fenv); return env -> { return n.apply(FunctionMap.put(env, name, v.apply(env))); }; }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( FunctionDefinition<Integer> functionDefinition, String name, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> body, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> next) { return fenv -> { Function<Function<String, Integer>, Integer> b = body.apply(fenv); return next.apply(FunctionMap.put(fenv, name, b)); // Function<Function<String, Integer>, Integer> n = next.apply(FunctionMap.put(fenv, name, b)); // return env -> { // return n.apply(env); // }; }; } @Override public Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> visit( FunctionApplication<Integer> functionApplication, String name, Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> parameter) { return fenv -> { Function<Function<String, Integer>, Integer> f = fenv.apply(name); Function<Function<String, Integer>, Integer> p = parameter.apply(fenv); return env -> { return f.apply(FunctionMap.put(env, "p", p.apply(env))); }; }; } }
This is obviously a mouthful, a bigger one, and not really helped by the use of the general Function interface. Function<Function<String, Integer>, Integer>
is a continuation that can be used to evaluate an expression with an environment (pretend it’s a class FunctionContinuation
), so Function<String, Function<Function<String, Integer>, Integer>>
(do mental substitution to get Function<String, FunctionContinuation>
which we can think of as FunctionEnvironment
) is a map from function names to continuations, and Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>>
is a continuation that takes a function map and returns a continuation for evaluating an expression, mentally think of it as Function<FunctionEnvironment, FunctionContinuation>
.
Handling of Constants and Variables is relatively straightforward, but now even handling the Plus and Times becomes more involved. We split the continuation computation into two steps: in the outer step we use the FunctionEnvironment to compute FunctionContinuations for both parameters. In the inner layer, we then use the regular environment to evaluate the two continuations. In this way, the JIT compilation takes place in the outer continuation and the inner continuation is the actual execution. Variable Assignment behaves in much the same way.
The new functionality is in handling of FunctionDefinitions. Here, we first JIT compile the function body (inside the outer continuation). We then have two alternate but equivalent code paths. The commented out code path is likely easier to understand at first glance. Here, we first JIT compile the next part but with a new FunctionEnvironment where we have defined our new function. In the inner continuation, we then evaluate our compiled next part with the given variable environment. We can observe that constructing a new function to just pass on the environment to the compiled next bit is not necessary, leading to the uncommented version. This means we now compile the function where it is defined instead of where it is used.
FunctionApplication is almost trivial after this; we look up the function in the FunctionEnvironment and JIT compile the parameter. By looking up the function during JIT compilation, we do not need to keep the map of functions during actual execution. We then evaluate the parameter and function body, analogous to how we evaluate an assignment.
Despite the complexity of the visitor, usage is delightfully simple:
FunctionDefinition<Integer> functionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new Constant<>(5))); Function<Function<String, Function<Function<String, Integer>, Integer>>, Function<Function<String, Integer>, Integer>> outerContinuation = functionExpression .visit(new BetterFunctionIntegerAlgebra()); Function<Function<String, Integer>, Integer> innerContinuation = outerContinuation.apply(FunctionMap.empty()); System.out.println(innerContinuation.apply(FunctionMap.empty())); FunctionDefinition<Integer> nestedFunctionExpression = new FunctionDefinition<>("square", new Times<>(new Variable<>("p"), new Variable<>("p")), new FunctionApplication<>("square", new FunctionApplication<>("square", new Constant<>(5)))); outerContinuation = nestedFunctionExpression(new BetterFunctionIntegerAlgebra()); innerContinuation = outerContinuation.apply(FunctionMap.empty()); System.out.println(innerContinuation.apply(FunctionMap.empty()));
If we want to reuse our code, we can do so by reusing the innerContinuation. The map passed to the outerContinuation to get the innerContinuation is empty here, much like we often evaluate FunctionContinuations using an empty map. It indicates that we start out with no functions defined. If we wanted, we could instead pass it a map prepopulated with a standard library of useful functions. As the map contains JIT compiled functions, we would not even have to compile them during compilation of our program, and our application would only include the functions actually used, making this very efficient.
As great as the above code is, it still has a problem. What is it?
Consider the below snippet:
FunctionDefinition<Integer> recursiveFunctionExpression = new FunctionDefinition<>("factorial", new Times<>(new Variable<>("p"), new FunctionApplication<>("factorial", new Plus<>(new Variable<>("p"), new Constant<>(-1)))), new FunctionApplication<>("factorial", new Constant<>(5))); assertThrows(IllegalArgumentException.class, () -> recursiveFunctionExpression.visit(new BetterFunctionIntegerAlgebra()).apply(FunctionMap.empty()));
And with that, I think this part is long enough. Come back for the exciting conclusion in part 4, where we look at the above problem and how to solve it, as well as adding some more common features to our language and some functional concepts that don’t really belong in the OO world.
Time person of the year 2006, Nobel Peace Prize winner 2012.