Catamorph your DSL: C++ Port

In the previous posts, we went over the process of building a DSL for arithmetic operations and we introduced the concept of Catamorphism as a way to decouple the traversal of the AST from the operations we want to perform on it.

We saw how it could help us compose operations before traversing the AST of our DSL, leading to more efficient composition and better testability.

Unless you are quite familiar with catamorphisms, you might want first to read these previous posts before this one:

All these previous posts were based on Haskell. Because Haskell is such a special (wonderful) language, the last post started to explore whether this concept would port as nicely in other languages.

We translated our Haskell code into Clojure, a functional language that put much less emphasis on types as Haskell. We saw that this concept translated to a post-order depth first search. The resulting Clojure code was both short and elegant.

This post will be focused on exploring the limits of the applicability of this concept some more, by trying to bring it into C++.

 

Boost to the rescue


We could implement our DSL in C++ with only the STL available, using Design Patterns such as the Visitors.

To keep the code short and concise, we will however rely boost as well. All the code that follows will assume the following Boost header inclusions:

 
In particular, boost::variant will be one of the cornerstone of the design, as it allows to avoid the Visitor design pattern. You might want to have a look at the documentation of boost::variant before proceeding.

The rest of the header are mostly for convenience. We could do without it, but at the expense of some more code to write.

 

Arithmetic expression in C++/Boost


There are many ways we could represent our expression DSL in C++. We could choose to use the Visitor design pattern for example. The solution below is based instead of boost::variant for convenience.

The recursive expression_r implements our open recursive data type. This type is implemented as a boost::variant on:

  • nb which represents an integer constant
  • id which represents a variable identifier
  • add_op which represents an addition operation
  • mul_op which represents an multiplication operation

The add_op and mul_op operations are themselves factorized as a single tagged op data type. Two tags represent the two operations, add_tag and mul_tag.

 
To get our recursive expression, we will use the same trick as we used in Haskell: we will compute the fixed point of the type recursion.

As in Haskell, C++ is not able to create infinite types. The Fix wrapper type of Haskell needed to circumvent this limitation is replaced by the boost::recursive_wrapper. The overall design is the same:

 
Note: this naive implementation triggers deep copies at each level of our AST. This might lead to a quadratic behaviour in the depth of our tree when playing with transformations on our AST. A production ready implementation would have to handle these aspects we voluntarily left out for simplicity. We will come back to this issue in the conclusion.

 

Factory functions and accessors


The trouble with constructors of class templates in C++ is that they require their explicit templates to be listed in the code. The usual trick is to define factory functions outside of the class to automatically deduce the template parameters.

We will define some factory functions to help us write code more easily. These functions are somehow similar to the “smart constructors” of Haskell:

 
Having introduced this layer of “named constructors” allows us create expression more succinctly and to better declare our intent:

 
Similarly, to “pattern match” on our boost::variant, we will introduce some helper accessors functions. Indeed, the trouble with boost::get is that it requires explicit templates to be listed in the code. Dedicated and correctly named functions will simplify the pattern matching greatly by removing noisy templates from our code:

 
Note: boost::variant also offers visitors to handle pattern matching as an alternative to boost::get. But as our interpreters will not need to exhaustively match all cases, sticking to boost::get ends up being less code. This is ultimately a matter of taste: we could have done the other choice instead.

 

Our C++ Catamorphism


Now that we have our expression_r type, we will need to write the equivalent of the catamorphism function cata of Haskell. This function will be responsible for lifting local AST transformations into operations on the whole AST.

The details on how to build a catamorphism from an open recursive type were already covered in the previous post on catamorphism in Haskell. This section will only aim at translating this code into C++.

 

Functor Instance

The first step is to make our expression_r type an instance of a Functor. In C++, one way to do it is to implement fmap for our type:

  • The map argument represents the transformation to apply
  • Constants and variable matches are left unchanged by this transformation
  • For operations, we recursively apply the transformation on the sub-expressions

We use boost::ranges to make the code more succinct:

 

Catamorphism

Next, we need to write the catamorphism function, whose goal is to apply fmap at each level of our expression, starting from the lower levels.

The details behind the inner workings of this function are provided in a previous post on Haskell. We only translate here this definition to C++:

  • We replace function composition in Haskell by nested function call in C++
  • We use get to extract the expression from the recursive_wrapper

Some of the types listed below are deduced automatically. We left them in the code to show what is going on under the cover:

One noticeable drawback of this implementation is the need to provide the output type of the cata function explicitly. This could probably be dealt with.

 

Pretty printing our expression in C++


We now have everything to start implementing our first interpreter, our expression pretty printer.

It is noticeably more verbose than in both Haskell and Clojure, but not that much. I was quite surprised by the overall concision:

  • print_alg handles pattern matching and the two trivial cases
  • print_op handles the operations by joining the sub-expression strings, prepends the operation and wraps the whole with parentheses

 
At call site, the code is not that verbose either. The main drawback is the need to specify the output type of the catamorphism (std::string in this case):

Now, this is not the most efficient code that we could come up with. It does create quite a lot of intermediary strings. This is the subject for another time.

 

Eval and dependencies


We can as translate to C++ our next two most straightforward interpreters, eval and dependencies.

The eval function needs an environment holding the value of the variables in the arithmetic expression. To make it simple and keep the code short, we will:

  • Rely on a std::map from id to integer to model this environment
  • Ignore errors such as an unbound variable in the environment

In addition, and to compensate for the absence of currying in Haskell, our eval function returns a lambda:

 
The dependencies functions lists all the variables of the expression. It sub-expressions are transformed to a set of variable identifiers, which are combined (set union) while climbing up the AST.

 

Composable C++ optimizations


Until now, the main advantage of introducing Catamorphism was to specify local transformations, which the cata function could lift to operations on the whole AST of our arithmetic DSL.

We will now leverage on the other advantage of Catamorphism, the ability to compose them efficiently, to implement our arithmetic AST optimization functions.

We left out the detailed implementation of the has_zero and optimize_op functions in the snippet below. The detailed implementation of these functions is available on GitHub.

This allows us to concentrate on the real value added by Catamorphisms, composability of transformations:

  • opt_add_alg is only concerned in optimising additions
  • opt_add_mul is only concerned in optimising additions
  • optimize_alg is only concerned in combining these algebra into one

This leads to the following code:

 
Note that how the optimize_alg function is able to combine the two algebra by composing them. The call to get allows to unwrap the expression of the first algebra, before calling the second algebra. We can give it a try:

 

Partial evaluation


Our last remaining challenge is to implement the partial evaluation of an arithmetic expression.

The partial_eval_alg simply replaces variables bound in the evaluation environment with their respective value. As for our evaluation function, our partial evaluation returns a lambda to compensate for the lack of currying in C++.

 
We can combine this function with our optimization functions to obtain a fully fledged partial application that simplifies expression in one single tree traversal.

 
We can also re-implement our evaluation function in terms of our partial evaluation:

  • If the resulting expression, after optimizations, is a constant, we output it.
  • Otherwise, we can use our dependency function to output the missing variables

This leads to the following evaluation function, which handles errors much nicer than our previous one:

We can give it a try to convince ourselves that it works:

 

Conclusion


In this post, we managed to port the Catamorphism notion in C++ to build a series of arithmetic DSL interpreters made of:

  • Composable local operations (our different algebra)
  • Decoupled from the traversal of the AST (handled by cata)
  • Avoiding any kind of mutations on our AST

The complete resulting code is about three times the length of the equivalent Haskell or Clojure code (320 lines give or take), which is quite good overall. But there is a catch: this implementation is unrealistically simplistic. This is the topic of the next section.

 

What’s the catch?

Our simplistic memory management did exhibit some problematic quadratic behaviour in terms of copy. Addressing this concern would require some manual work: C++ offers no standard support for immutable data structure with structural sharing in its standard library, so we would probably have to rely on move semantics.

We also had some remaining issues regarding type deduction, which would require some more tricks to improve. The biggest issue is however dealing with the long error messages GCC outputs upon the simplest type error. Try removing the .get() in the catamorphism function, or messing up with the types of an algebra function, and you shall see. Concepts could probably help there.

So I do not think that the 320 lines of C++ code do quite compare in maturity with the 120 corresponding lines in Haskell.

 

On Catamorphisms in C++

This concludes our study of the applicability of Catamorphism in C++. Overall, I felt like this design quite not as natural as it was in Haskell or Clojure. It sometimes felt like going against the idiomatic use of the language, which is not a good sign.

I recently read some good articles on the functional paradigm bursting in into C++ (like this series of posts on http://www.modernescpp.com).

Although this is true that C++ made great leaps in this direction by encouraging higher order functions usage with the addition of lambdas, it felt awkward using them in this context.

But the main difficulty in porting this concept to C++ is that it is implicitly based on efficient persistent data structure to exist in the language. And the support for immutable data and persistent data structures in C++ is simply not there.

To summarize, implementing catamorphisms in C++ was quite a fun exercise (except for the compilation error messages spanning over 2 or more screens), but it did not feel like it fits C++ as it does for Haskell or Clojure.

Catamorph your DSL: Clojure

In the previous three posts, we went over the process of building a DSL for arithmetic operations and we introduced the concept of Catamorphism as a way to decouple the traversal of the AST of our DSL from he operations we want to perform on it.

We saw how it could help us compose operations before traversing the AST of our DSL, leading to more efficient composition and better testability.

But Haskell being quite unique, it is quite interesting to take some distance and take time to investigate at how applicable is this concept in other languages.

In this post, we will focus on Clojure, and will:

  • Build a small arithmetic DSL in Clojure
  • Look at how catamorphism translates in Clojure
  • Implement the same interpreters as in Haskell
  • Marvel at the beauty of coding in Clojure

In the process, we will illustrate that the concept of Catamorphism is related to post-order depth first search traversal of trees.

 

Growing our arithmetic DSL


Our first task will be to choose a representation for our DSL.

Clojure encourages to use simple data structures as much as possible. We will follow the philosophy of the language and represent our DSL using nested vectors, and two keywords for addition and multiplication.

 
Using simple data structures does not forbid introducing abstractions. In the same spirit as in Haskell, we will introduce “smart constructor” (factory functions) to build our expression without having to know its internal structure:

The following code shows how to construct an arithmetic DSL from these constructors:

 
To complete our arithmetic expression, and abstract away from its representation, we also offer some query and extraction functions on it. In particular:

  • op? returns whether the top expression is an addition or multiplication.
  • rator extracts the operator of an operation (addition or multiplication)
  • rands extracts the operands of an operation (addition or multiplication)

These query functions will allow us to implement the equivalent of the pattern matching logic of Haskell in our Clojure code.

 

Introducing Clojure Walk


We already discussed in the previous posts that catamorphisms relate to post-order depth first search traversal of the AST of our DSL. Clojure offers a really good implementation of tree traversals in its clojure.walk namespace.

Our code will rely on this namespace, as well as some additional standard namespaces inclusions. You can find them below:

In particular, clojure.walk/postwalk will be of great interest to us. It visits all nodes in tree, apply a transformation on it, before visiting their father node recursively, until it reaches the root node.

Let us see how it works by tracing the visit of all nodes along the traversal:

  • The walk starts by the leftmost element and goes as deep as it possibly can
  • Each node is scanned and transformed exactly once (we used the identity here)
  • The father of a group of node is visited right after all its children

 
Note that there is one big difference with the Catamorphism we had in Haskell: because we visit every single node, we will also visit the keywords :add and :mul of our DSL. This is something we will have to take this into account.

 

Pretty printing walk


Let us put the postwalk function to use by translating in Clojure our most basic interpreter, the pretty printer.

  • walk/postwalk plays the role of the cata function in Haskell
  • The first argument of postwalk is the algebra (named for clarity only)
  • The :else handles the case of the keywords :add and :mul

The code below is the full Clojure implementation:

Using the function results in the result we expect:

 
Except for the matching of the operation keywords, the Clojure implementation looks really much like the Haskell implementation of our previous post:

 
Although it leverages very different means, Clojure achieves the same kind of simple, decoupled, and close-to-specification code than Haskell. Beautiful, right?

 

Evaluate and dependencies


We can as easily translate to Clojure our next two most straightforward interpreters, eval (renamed evaluate since eval already exists in Clojure) and dependencies.

The evaluate function below needs an environment holding the value of the variables in the arithmetic expression. To make it simple, we used a Clojure hash map (which we can consult using the get function).

 
The implementation of dependencies, which lists all the variables of the expression, is also quite small and simple to follow. It makes use of Clojure standard sets to gradually accumulate all variable names from an arithmetic expression:

 

Composable optimizations


After the appetizers, the main dish: the implementation of the arithmetic expression optimization functions.

To show how easy composition of tree walking functions, we will provide two separate functions to optimize the addition and the multiplication:

These two functions make use of the optimize-op helper function that contains their common parts, which you can consult here.

Because our solution in Clojure did not have to include a mysterious Fix type to create an infinite type (as it was required in Haskell), composition of our “algebra” is the standard function composition:

It almost looks too simple to be true. Let us try it out to check if we are not dreaming in high definition:

 

Partial application


Our last remaining challenge is to implement the partial evaluation of an arithmetic expression, which we will name partial-eval to avoid naming conflicts with existing Clojure functions.

To do so, we will create a replace-var function whose goal is to replace variables bound in the evaluation environment with their respective value. We can combine this function with our optimization functions to obtain a fully fledged partial application that simplifies expression in one single tree traversal.

Let us see if it works. We will partially apply our initial expression with “y” bound to zero:

 
Interestingly, if we partially evaluate our function with a environment holding all the variables appearing in the expression, the result is identical to a call to evaluate:

We did not have anything to do for that to be true. How amazing is this?

 

Conclusion and what’s next


In a few lines of code, we managed to build an arithmetic DSL, with all the interesting features we built in Haskell. The code is about the same length, as simple and composable as in Haskell.

The main difference to me is the efforts we had to put in to get the same result. There was no need to invent anything complicated, like parameterized recursion, to get to this result.

But on the other hand, we were able to count on the amazing clojure.walk namespace, and we lost almost all the type safety we had in Haskell.

As for myself, I enjoyed implementing both of these solutions equally well. I hope you enjoyed the ride too!

This concludes our study of how catamorphism translates into Clojure. The next post will be dedicated in trying to do the same exercise in C++, a much more mainstream language than our previous candidate.