DSLs with the Free Monad in Java 8 : Part I
A program in Free
Recently, there has been an explosion of interest in the Scala community about a data structure known as Free or the Free Monad. It allows Scala developers to define internal mini languages, and hence programs, inside their own applications that they can interpret and execute independently as needed. Free behaves much like Stream and Optional do in Java 8. While the map and flatMap methods on Stream capture the transformation steps to be applied to a Stream of data, the map and flatMap methods on Free can capture the sequencing of commands to be executed in a custom program.
This technique, of defining DSLs can be used to enforce SOLID design principles (in particular Dependency Inversion) and allows us to ensure that we don’t mix abstraction levels at critical junctures in our code. While our DSLs lack the syntax for lower or higher levels of abstraction, they force us to keep to the right path. We can also attach different interpreters to our DSLs at runtime, so for example in our unit tests the interpreter can mock the live service calls we’d actually make in a production environment.
While Free itself is an advanced concept, defining DSLs in terms in of Free can be done entirely in terms of pure Java 8 and is arguably a simpler task than defining and combining multiple grammars and parsers using tooling such as Antlr. However I suspect most Java developers will find this article useful as a primer on a concept that may seem alien and even unintelligible when expressed in other languages.
The examples in Part I will be based on a simplified implementation of Free provided in cyclops-react called Unrestricted.
This series of articles / tutorials is based on the Haskell Blog Post by Gabriel Gonzalez called Why Free Monads Matter, and its Java Conversion by Kenji Yoshida.
The article continues below, where we will
define a simple DSL
a program written in that DSL
2 Interpreters for our new DSL that handle program execution differently
Expressing Free in Java
Let’s start by defining a simple program
In this program we want to
output A to the console
ring a bell
output B to the console
terminate
Using the Unrestricted type in cyclops-react (a simplified implementation of Free) we can express and capture this program in pure Java as follows :-
The meat and bones of the program are on the right, and boiler plate to capture this is defined on the left (don’t worry we will explain what is going on here soon).
The variable ‘program’ captures the sequence of commands to be executed. Once the above code is run, we end up with a linked Data Structure that could be visualized something like this;
The returned Unrestricted (free monad) Instance has an embedded reference to the first command in our program which in turn can generate a reference to the next Unrestricted instance and so on. To execute our program all we need do is walk this data structure (using the resume method on Unrestricted) and attach an interpreter to handle each of the commands.
Building an Interpreter
In our interpreter we want to walk the captured data structure and interpret each of the commands. At this stage we know we will have to handle output, bell and done commands. We will be able to put more meat on the bones of our interpreter after introducing a few more concepts.
Free works with Functors
Java 8 introduced a number of Functors (or data types that can transformed via a function) including Stream, Optional and CompletableFuture.
When we make use of the map method on a Stream, we are treating it as a Functor.
We can also define our own Functors, for example to make List behave as a Functor we could define a map method for Lists.
A more general Functor interface could be defined something like this
In cyclops-react the name Functor is reserved for the more abstract Functor type class that leverages psuedo Higher Kinded Types (of which more in part II of this series). The type Transformable is used to define a simpler / easier to use Functor interface -> Link To Transformable class
Commands are Transformable
We can define each of our programs’ commands by defining an appropriate map method. Our first step is to create an appropriate base class for our DSLs’ commands.
Our map method will be used by our Free implementation (Unrestricted) to realize the chain of Unrestricted instances that represent our program. The provided Function will often return an instance of Unrestricted that can lead us to the next Command in the chain (and so on).
Done
This makes defining Done really simple, as Done represents the last stage of the program we can pretty much ignore the supplied Function.
Bell
Bell is a little more complex.
We need to define a generic variable that can represent a path to the next stage (although it is not shown in this example we can also use next to pass data between commands). In practice, the next stage of the program will stored inside Bell as an instance of Unrestricted / Free.
In the map method we need to apply the provided function to our next variable.
Output
The implementation of Output is pretty much identical to that of Bell, except that we also need to capture & store the character that we wish to output to the console.
Commands want to be Free
In our program all our commands are embedded inside instances of Free / Unrestricted. We use a static method to create each command.
To embed an Output instance inside an instance of Free we can create a static method to do that and make use of the ‘LiftF’ method on Unrestricted.
LiftF creates an instance of Unrestricted with an embedded functor (an instance of Transformable). As all our Commands implement Transformable we can pass them to LiftF.
Interpreting our Java Program
Hopefully the boilerplate makes a little more sense now. On the right we are creating instances of our commands embedded inside Free / Unrestricted.
On the left we are defining our program in terms of a Free instance. On the right each command is provided as a parameter to the forEach method — either directly or as the return value from a function.
Ultimately the variable program represents the sequencing of these commands in a data-structure something like a linked chain of Free / Unrestricted instances. Any combination of the commands we have defined can be put together in this way to define any acceptable program. We just need to finish our interpreter to be able to execute it.
Interpreting the Output Command
When we have an output command we want to do 2 things.
We want to append the character defined as an operand to this Command to our output String
We want to interpret the next step of the program
With Java 8 lambdas we can implement the visitor pattern (aka pattern matching in functional languages) for this type really simply. In our visitor we should provide both the captured character and the next step of the program to a user defined function.
We can then make use of this visit method when we handle output by passing it a BiFunction that appends the appropriate character to an output String and recursively interprets the next stage of the program.
Interpreting the Bell Command
We can do the same for our Bell command.
In this case things are even simpler as we only need to capture the next stage of the program.
Our visit method should take a function that accepts the next stage of the program.
To interpret each Bell command we can use our visitor to append the word ‘bell’ to our output (or if you are feeling adventurous use some Java library to play a sample of a bell ringing) before making a recursive call to interpret the next stage of the program.
Implementing the interpret method
The last piece of the puzzle is to implement the interpret method itself. We can use the resume method on Free to interpret the next stage in the program. The returned object also implements a visitor which allows us to pattern match on the result. Resume will either return the current command to be interpreted or a raw result, we can implement matchCommand to handle each command type.
For simplicity’s sake, and to avoid introducing another potentially new data type, we can implement matchCommand in terms of a traditional if / else block — but there are cleaner and more functional ways to implement this without risking throwing an exception (which we will cover in part II of this series).
If we run our program via
We should see the following printed to the console -
emitted A
bell
emitted B
done
Converting from Transformable to Command
One of the downsides of not having Higher Kinded Types means we lose the fact that the functor type is actually a Command (rather than just something that implements Transformable). The purpose of the ‘decoder’ function passed to resume() is to provide a way to convert back from Transformables to Commands. Here we lack full type safety and will make use of a cast.
A note on syntax
Unrestricted.comprehensions.forEach is an API that provides ‘for comprehensions’ for Unrestricted free monad instances.
The following code snippets are all equivalent in effect, but using the forEach facility provided by Unrestricted.comprehensions produces much cleaner code.
Also note, that Free / Unrestricted programs can be arbitrarily large.
Multiple interpreters can be used
Once you have created one interpreter for your knew DSL, it’s pretty straightforward to add more. The StringBuildingInterpreter we’ve created looks like it could be useful for testing programs written in our new mini-language, but at runtime we might want each command to actually Output to the Console or play a bell.
We can create a new EffectfulInterpreter, based on the old one, that does just that.
At runtime we can choose which interpreter should be used, or even leverage both.
Running the main method above will result in the following output to the console.
And a real-life beep will be played when it is executed with the EffectfulInterpreter!
Coming Soon — Part II
Hopefully that wasn’t too scary and you are still here! If so, do check out the complete code from this article on github here (https://github.com/johnmcclean/unrestricted-example1). In part II we will repurpose these examples to leverage the Higher Kinded Free class in cyclops-react. From there odd numbered versions in the series will extend the examples using Restricted in a simpler fashion and even numbered examples will work with the more advanced kind. See you soon!
