A couple of weeks ago, a colleague and I were working on an application that needed to traverse a simple AST. The code came with a bundled visitor for performing the traversal and we needed to transform a simple decision tree model to BPMN using a builder. The implementation was second nature, but left my colleague confused about the techniques used. It was absolutely not because he was below average, but it made me realize that modern object-oriented developers have very little experience with techniques that come from the functional domain. This despite modern object-oriented languages, such as Java and Typescript embrace more and more functional techniques. Making full use of streams and anonymous functions in Java rely heavily on understanding functional programming. One of the most prevalent computing paradigms in big data, map-reduce, is nothing more than an application of a single special case of functional programming. Getting a fuller understanding of more advanced topics like asynchronous programming (whether in Java, Typescript/Javascript, Kotlin or elsewhere) or fully understanding how a JIT compiler works can be achieved by intimate knowledge of functional programming.
This post is a reworking, cleanup, and expansion of a demo application I made to introduce some of the concepts to my colleague. The goal is to serve as an introduction to all of the topics mentioned above. That is quite a mouthful; in fact there are books on several of the topics individually, so covering them all in this piece, despite its length, means it will be very condensed. I’ll include points to think about, suggested extended assignments to deepen your understanding, and code snippets that I invite you to try out and extend yourself. I did not put advanced in the title for no reason; while I’ll introduce some simple bits, I’ll also go into very deep things that makes the word-counter and automatically generated estimated time to read above completely seem silly. This piece builds on Java, but applies to pretty much any modern language.
The Visitor Pattern
Let’s start with a topic that’s probably familiar at least superficially to many object-oriented developers: design patterns. Most developers work with modern language that come with a standard library of reusable code (like collections and I/O), likely builds on one or more frameworks (like Spring), and uses different libraries (like the Apache Commons libraries). Standard libraries, frameworks and third(/first) party libraries all allows developers to share code between different projects and applications. This makes development much more efficient because developers do not have to write code for solving the same problem again and again. Since the code is re-used, it is also possible to increase its quality as it is possible to amortize costs for testing and documentation over multiple projects. Libraries facilitate re-use at the level of code. Design patterns on the other hand facilitate re-use at the level of ideas.
Design patterns are general solutions to common problems. OO developers will likely have heard of the MVC (model-view controller) design pattern, which is a design pattern solving the problem of building applications (with user interfaces), by splitting them into a model (the data), zero, one or more views (the user interfaces), and a set of controllers (actually manipulating the data). This is literally the source of the name for Spring MVC. Other patterns (from the GoF book) that OO developers may have heard of are the composite pattern, adapters, builders, factories, iterators, observers and maybe the command pattern.
A less prominent pattern among OO developers is the visitor pattern. While iterators can be considered as a special case of visitors and some library functions have semblance of the visitor pattern, it is a bit more specialized. A visitor is a generic solution to the problem of traversing a data structure. An iterator is a generic way of traversing a simple, typically linear data structure like a list or a map, but a visitor can traverse “any” data structure like an abstract syntax tree or a file system (IIRC, one of the file APIs in Java essentially provide this functionality). The visitor pattern is a bit more abstract, requires more structured thinking, and is less frequently strictly needed, which means less experience developers tend to prefer to explicitly traverse their data structures instead of implementing a generic traversal.
Let us introduce the visitor pattern by an example. The example defined an AST for a simple expression language:
abstract class Expression<T> {
public abstract <V> V visit(SimpleExpressionVisitor<T, V> visitor);
}
class Constant<T> extends Expression<T> {
T value;
public Constant(T value) {
this.value = value;
}
public <V> V visit(SimpleExpressionVisitor<T, V> visitor) {
return visitor.visit(this, value);
}
}
class Plus<T> extends Expression<T> {
Expression<T> left, right;
public Plus(Expression<T> left, Expression<T> right) {
this.left = left;
this.right = right;
}
public <V> V visit(SimpleExpressionVisitor<T, V> visitor) {
return visitor.visit(this, left.visit(visitor), right.visit(visitor));
}
}
class Times<T> extends Expression<T> {
Expression<T> left, right;
public Times(Expression<T> left, Expression<T> right) {
this.left = left;
this.right = right;
}
public <V> V visit(SimpleExpressionVisitor<T, V> visitor) {
return visitor.visit(this, left.visit(visitor), right.visit(visitor));
}
}
// We create a simple visitor for them
interface SimpleExpressionVisitor<T, V> {
V visit(Constant<T> constant, T value);
V visit(Plus<T> plus, V left, V right);
V visit(Times<T> times, V left, V right);
}
Our language allows simple expressions built from constants, addition and multiplication. Examples of expressions are 5, 5*7, or (5*7) + 3. In fact, our expression language is not confined to deal with integers, but are parametrized with the domain they deal with, and an equally valid interpretation would be that expressions could be true, true * false, or (true * false) + true.
In effect, what we have implemented using the expressions above is what is known as an abstract sigma algebra (no, not the one from probability theory, the one from category theory). A sigma algebra defines the structure of an algebra with dealing with the specific. Here, I used used an abstract algebra for the fun of it; after a brief example of a Boolean algebra, we’ll be dealing with plain old integers.
In addition, we define a visitor. A visitor allows us to abstract away the tedium of traversing expressions expressed using an AST. To allow that, we define an interface SimpleExpressionVisitor which defined methods for all three concrete classes of our expressions. We also add an abstract method to the abstract base class and concrete methods for all concrete classes for performing the traversal. This visit methods in the expression classes take a visitor and returns a value defined by the visitor. Each of the three methods in the SimpleExpressionVisitor take a concrete subclass of the expression as well as a number of recursively computed values, and return a new value. The visit methods in the expression classes supply the expression and calls the visitor on eventual linked children. Let’s quickly move to viewing an example:
class IntegerAlgebra implements SimpleExpressionVisitor<Integer, Integer> {
@Override
public Integer visit(Constant<Integer> constant, Integer value) {
System.out.println("visit constant");
return value;
}
@Override
public Integer visit(Plus<Integer> plus, Integer left, Integer right) {
System.out.println("visit plus");
return left + right;
}
@Override
public Integer visit(Times<Integer> times, Integer left, Integer right) {
System.out.println("visit times");
return left * right;
}
}
This visitor computes the value of the expression as an integer value (5 = 5, 5 * 7 = 35, (5 * 7) + 3 = 38). The CS101 way of doing this would be to define an evaluate method on each of the individual expression classes, but here we do it instead using a visitor. It has the consequence that we have a simple overview of the evaluation of all of the types of expression in a single place, we do not pollute the data classes with business functionality, and it is easier to add functionalty later without having to alter our domain model. On the downside, it is somewhat harder to extend out AST with new nodes, but more on that later.
The result of the visitor is an integer, the result of the evaluation. This visitor only works with integer expressions. Thus the abstract value computed in integer, and the three visit methods receive integer expressions and integer results computed recursively. Aside from logging calls, the three functions just perform the obvious computations. The visitor can be used as follows:
Expression<Integer> integerExpression = new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3)); System.out.println(integerExpression.visit(new IntegerAlgebra()));
Just for the fun of it, let’s consider implementation of evaluation of a Boolean algebra as well:
class BooleanAlgebra implements SimpleExpressionVisitor<Boolean, Boolean> {
@Override
public Boolean visit(Constant<Boolean> constant, Boolean value) {
return value;
}
@Override
public Boolean visit(Plus<Boolean> plus, Boolean left, Boolean right) {
return left || right;
}
@Override
public Boolean visit(Times<Boolean> times, Boolean left, Boolean right) {
return left && right;
}
}
This is used similarly:
Expression<Boolean> booleanExpression = new Plus<>(new Times<>(new Constant<>(true), new Constant<>(false)), new Constant<>(true)); System.out.println(booleanExpression.visit(new BooleanAlgebra()));
I mentioned the strength of the visitor pattern is that we can implement different computations easily, so let’s immediately do that. Aside from evaluating expressions, the next obvious thing to do to them is printing them as strings:
class SimpleToString<T> implements SimpleExpressionVisitor<T, String> {
@Override
public String visit(Constant<T> constant, T value) {
return Objects.toString(value);
}
@Override
public String visit(Plus<T> plus, String left, String right) {
return "(" + left + " + " + right + ")";
}
@Override
public String visit(Times<T> times, String left, String right) {
return "(" + left + " * " + right + ")";
}
}
This code should also be relatively straight-forward at this point. The only slightly interesting thing is that this code works with expressions of any type but always returns a string, so we could use it as:
Expression<Integer> integerExpression = new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3)); System.out.println(integerExpression.visit(new SimpleToString<>())); Expression<Boolean> booleanExpression = new Plus<>(new Times<>(new Constant<>(true), new Constant<>(false)), new Constant<>(true)); System.out.println(booleanExpression.visit(new SimpleToString<>()));
From here on out, we’ll only consider integer expressions. Let’s test our code on some big expresions:
Expression<Integer> build(int size) {
Expression<Integer> result = new Constant<>(0);
for (int i = 1; i < size; i++) {
result = new Plus<>(new Constant<>(i), result);
}
return result;
}
This function builds up large expressions with a given size. Only size around 4000 works with the default Java stack size. We can test our print code as follows:
Expression<Integer> integerExpression = build(4000);
long before = System.currentTimeMillis();
integerExpression.visit(new SimpleToString<>());
System.out.println("simple: " + (System.currentTimeMillis() - before));
Try experimenting with the above code, varying the value of the parameter given to build and comparing with the execution time.
Running the above code on my computer, I obtained 4000 -> 117 ms, 3000 -> 59 ms, 2000 -> 24 ms, 1000 -> 3 ms.
Try explaining the progression of the performance you see.
It looks like the performance progresses worse than linearly. Going from 1000 -> 2000 yields an increase of 24 ms – 3 ms = 21 ms while going from 3000 -> 4000 increases the execution time by 117 ms – 59 ms = 58 ms.
The explanation is that to convert to a string using parameter 1000, each call to one of th three visit methods in the SimpleToString visitor produces a new string. For a constant, the length of this string is at least one, and for an addition or multiplication, the length of the string is at least one + the length of the strings for the children. We have 1000 constants and 999 additions when using parameter 1000, and if we focus on the length of the strings produced when converting additions to strings, we get that the first has length at least 1 + 1 + 1 (one plus of two constants). The next has length at least 1 + 1 + 3 (one constant, one plus, and the result of the previous step). Then comes 1 + 1 + 5, 9, 11, etc. We can see this is 3 + 5 + 7 + 9 + 11 + … + (1 + 2 * 999), or 1 + 2 * (1 + 2 + 3 + 4 + … + 999). Astute readers will recognize the sum in the parenthesis and know it has value (1000 * 999) / 2 (for explanation Bing “Gauss sum of integers to 100”). In fact, in general our code will produce strings with an accumulated length of at least 1 + n * (n-1) for expressions with length n.
Readers familiar with big-oh notation, should be able to easily see this way of building strings has a complexity of O(n2).
Stronger yet, it should be relatively simple to see that the complexity is really Ө(n2) (convince yourself of the fact by realizing that we can bound the length of strings both upwards and downwards, e.g., by saying that the lower bound is adding 1 for each step and the upper bound is adding 20, and using the basic fact that no function can operate faster than linear in the accumulated size of the output it produces).
This means that using this way of producing strings for our expressions will never be more efficient than quadratic in the size of length of the formula. This includes the CS101 way of adding a toString method to each concrete expression class.
Continuations
So, we have noticed that our string conversion is sub-optimal; we would expect it to only take time linear in the size of expressions. We can solve this using a design pattern called continuation passing style. CPS is a design pattern from the functional programming world and unfamiliar to all OO developers, even the ones that are relatively at home in using function parameters. CPS is used as the foundation for implementing asynchronous programming, implementing JIT compilers, and for implementing exceptions in functional languages. It is an immensely powerful style, but also has a very high barrier to entry. Let us implement a facier toString method using a continuation:
class FancyToString<T> implements SimpleExpressionVisitor<T, Function<StringBuilder, StringBuilder>> {
@Override
public Function<StringBuilder, StringBuilder> visit(Constant<T> constant, T value) {
return sb -> {
sb.append(value);
return sb;
};
}
@Override
public Function<StringBuilder, StringBuilder> visit(Plus<T> plus, Function<StringBuilder, StringBuilder> left,
Function<StringBuilder, StringBuilder> right) {
return sb -> {
sb.append('(');
sb = left.apply(sb);
sb.append(" + ");
sb = right.apply(sb);
sb.append(')');
return sb;
};
}
@Override
public Function<StringBuilder, StringBuilder> visit(Times<T> times, Function<StringBuilder, StringBuilder> left,
Function<StringBuilder, StringBuilder> right) {
return sb -> {
sb.append('(');
sb = left.apply(sb);
sb.append(" * ");
sb = right.apply(sb);
sb.append(')');
return sb;
};
}
}
This visitor no longer produces a string, but instead a function that takes a StringBuilder as input and produces a StringBuilder as output. This fancy version can be used like this:
Expression<Integer> integerExpression = new Plus<>(new Times<>(new Constant<>(5), new Constant<>(7)), new Constant<>(3)); System.out.println(integerExpression.visit(new FancyToString<>()).apply(new StringBuilder()).toString()); Expression<Boolean> booleanExpression = new Plus<>(new Times<>(new Constant<>(true), new Constant<>(false)), new Constant<>(true)); System.out.println(booleanExpression.visit(new FancyToString<>()).apply(new StringBuilder()).toString());
Compared with our previous implementation, we now have to call apply on the result of the visitor and call toString to convert the StringBuilder to a string (yes, that’s not strictly needed in the code here but it’s there to show general operation).
Comparing the output with the previous version, we notice that the output the same, only the visitor and the use is more complex, so what’s the purpose. Well, if we compare the two:
Expression<Integer> integerExpression = build(4000);
long before = System.currentTimeMillis();
integerExpression.visit(new SimpleToString<>());
System.out.println("simple: " + (System.currentTimeMillis() - before));
before = System.currentTimeMillis();
integerExpression.visit(new FancyToString<>()).apply(new StringBuilder()).toString();
System.out.println("fancy: " + (System.currentTimeMillis() - before));\
Running this code, we notice that the fancy new visitor is faster and has a much nicer progression as we change the parameter to build (1000 -> 2000: 5 ms – 3 ms = 2 ms, 3000 -> 4000: 6 ms – 4 ms = 2 ms; the times are so low we should run repetitions if we want accurate values). How can this be?
The trick is that we no longer produce 1000 strings for an expression of length 1000, we only produce the one. Instead, we append the individual values to a single StringBuilder, and only at the very end do we convert that into a string. In complexity-theory terms, this fancy toString method has complexity O(n) while the simple one (and any simple one) has complexity O(n2).
We could achieve the same performance by manually traversing the AST and accumulating data in a global StringBuilder, but it is very hard to achieve this using a visitor without a contiuation. The reason is that we have to append data to the StringBuilder before traversing children, during the traversal of children, between traversal of two children (for plus and times) and after traversing all children. We could define a visitor with hook at all these places, but that would mean our nice visitor with 3 methods would instead get 7 methods (3 for each of plus and times for before, between, and after), and 1 for constant).
By using a contiuation, we can perform computations both before, between, and after traversal of children. If we split up the visitor, starting from within:
sb.append('(');
sb = left.apply(sb);
sb.append(" + ");
sb = right.apply(sb);
sb.append(')');
return sb;
Most of this should be relatively simple: first we add a left parenthesis to the StringBuilder, then we call recursively, append +, call recursively on the other child term, append a right parenthesis, and finally return the StringBuilder. The real magic is just one line before and after this:
return sb -> {
sb.append('(');
sb = left.apply(sb);
sb.append(" + ");
sb = right.apply(sb);
sb.append(')');
return sb;
};
Java 8 makes this almost invisible using anonymous functions, but the magic that happens here is that what I just wrote in the preceding paragraph does not actually happen. Instead, we construct a function that can do this.
@Override
public Function<StringBuilder, StringBuilder> visit(Plus<T> plus, Function<StringBuilder, StringBuilder> left,
Function<StringBuilder, StringBuilder> right) {
return sb -> {
sb.append('(');
sb = left.apply(sb);
sb.append(" + ");
sb = right.apply(sb);
sb.append(')');
return sb;
};
}
So, the effect of this method is not that it adds things to a StringBuilder, instead it constructs a function that can do that. That is why we have to call the function when using this visitor:
integerExpression.visit(new FancyToString<>())
.apply(new StringBuilder())
.toString()
The first line constructs a big function that can convert integerExpression to a string, and the second line actually does this. Or, rather, it constructs a StringBuilder with all the individual pieces added to it, and the last line converts this finally to a string.
Conclusion
This is just part 1, introducing two basic concepts: the visitor design pattern and the continuation passing style design pattern. We have seen how using these in combination allows us to implement some recursive functions more efficiently than the native implementation.
In the next bit, we’ll look at using functions instead of data structures, how to evaluate expressions using continuations, and how to evaluate more complex expressions that are very hard to evaluate without using continuations.
