Catamorphisms, part three

As promised in a previous blog entry, today let’s apply catamorphisms to a more real-world-ish example.  Say we’re creating a new programming language, and we’re authoring tools for this language.  A parser for the language will probably output an intermediate representation called an abstract syntax tree (AST), which other language tools then process.  For example, an interpreter would walk the AST and "execute" the code that it represents, whereas a pretty-printer would walk the AST and convert it into a nicely displayed text string.  If you were coding in an OO language, you’d probably apply the visitor pattern, where the interpreter and pretty-printer were two different kinds of visitors accepted by the AST.  (Once upon a time I gave just such an assignment in a programming languages class.)  On the other hand, if you’re using a functional language, then each ‘visitor’ is just a catamorphism on the tree type.  Today we’ll see that.

The problem facing the blog author (that is, me) is trying to make the example rich enough to demonstrate the overall generality of the point I’m trying to make, as well as deep enough to give you the sense that yes, this does apply/scale to real-world problems… while at the same time keeping things small enough that you can digest it all in a sitting while reading the blog, and the code snippets stay short enough to be readable on the screen along with the complementary prose.  I’ve tried to invent a tiny "language" that is the smallest possible thing that will allow me to demonstrate the power of catamorphisms without being overwhelming.  So I decided a minimal set would be an expression language with: literal values, operators, control structures, and effects.  Hence…

Today’s tiny language

Our "language" for today will be a language of integer expressions.  It can represent literal numbers (e.g. 42) as well as plus or minus expressions (e.g. 3+4-2).  It has one control structure, an if-then-else (where the condition is an integer, and 0 means false).  And it has one "effect" expression: print(5) would print out 5 and also return 5 as a value.  We aren’t writing a parser for the language (not today, at least), but the corresponding AST might look like this:

// types capable of representing a small integer expression language
type Op =
    | Plus
    | Minus
    override this.ToString() =
        match this with
        | Plus -> "+"
        | Minus -> "-"
type Expr =
    | Literal of int
    | BinaryOp of Expr * Op * Expr     // left, op, right
    | IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
    | Print of Expr                    // prints, then returns that value

Discriminated unions fit the bill nicely.  One thing I haven’t discussed before is that discriminated unions can have member functions, just like classes (indeed they are converted into IL classes under the hood).  In this code I’m overriding the ToString() for the "Op" type to give us a pretty-printable representation (which we’ll use later when we write a function to pretty-print entire expressions).  Apart from that, there’s no new F# here.  I hope it’s clear how these data types represent the language I described in the previous paragraph.

Since we’re not writing a parser for this language today, we have to create representations of these expressions "by hand".  Here is a list of three small expressions:

let exprs = [Literal(42)
             BinaryOp(Literal(1), Plus, Literal(1))
             IfThenElse(Literal(1), Print(Literal(42)), Print(Literal(0)))
            ]

Lovely.

Folding expressions

If you’ve been following along, then you know that a catamorphism on the "Expr" type will be a function that takes five arguments – one for each of the four alternatives of the discriminated union (Literal, BinaryOp, IfThenElse, Print), and a final argument that is the Expr to be "folded".  This function can be derived entirely from the shape of the data type itself, so even if you don’t quite follow how catamorphisms work yet, you still might be able to write:

let FoldExpr litF binF ifF printF e =
    let rec Loop e cont =
        match e with
        | Literal(x) -> cont (litF x)
        | BinaryOp(l,op,r) -> Loop l (fun lacc ->
                              Loop r (fun racc ->
                              cont (binF lacc op racc)))
        | IfThenElse(c,t,e) -> Loop c (fun cacc ->
                               Loop t (fun tacc ->
                               Loop e (fun eacc ->
                               cont (ifF cacc tacc eacc))))
        | Print(e) -> Loop e (fun eacc ->
                      cont (printF eacc))
    Loop e (fun x -> x)

just based on the previous examples we’ve done.  We do our usual "loop with continuation" pattern to ensure the function is tail-recursive.  For each alternative, we pattern-match out the corresponding data, recurse when necessary, call the corresponding function on the results, and pass the final value to the continuation.   So, for example, the second alternative of the Expr data type was

    BinaryOp of Expr * Op * Expr

First we pattern match it to

    BinaryOp(l,op,r)

Since "l" and "r" have type "Expr", we need to recurse with each, following the usual pattern:

    Loop l (fun lacc -> 
    Loop r (fun racc ->

Finally we apply the corresponding function (which I named "binF") on the pieces, and pass the final result to the continuation:

    cont (binF lacc op racc)

The same logic applies to each alternative.  So creating the "fold" function which defines a catamorphism over a recursive data type is mechanically straightforward.

Visitor 1: a pretty-printer

Now let’s define a simple pretty-printing function for Exprs.  Since we have the "fold" in hand, it is very easy:

// PrettyPrint : Expr -> String
let PrettyPrint = 
    FoldExpr (fun x ->      sprintf "%d" x)
             (fun l op r -> sprintf "%s %s %s" l (op.ToString()) r)
             (fun c t e ->  sprintf "if %s then %s else %s endif" c t e)
             (fun e ->      sprintf "print(%s)" e)

// call it on our sample expressions

exprs |> List.iter (fun expr -> printfn "%s" (PrettyPrint expr))
// 42
// 1 + 1
// if 1 then print(42) else print(0) endif

All we do is create four functions – one for each Expr alternative – where each function defines how to pretty-print that particular alternative.  Pass those 4 functions to FoldExpr and we have our pretty-printer.  FoldExpr takes care of the recursion.  This is, in a sense, the visitor pattern boiled down to its essence: we want to walk the tree to accomplish some task, and so we just need to define the logic about how to handle each kind of node in the tree.

Visitor 2: an interpreter

Now let’s define an interpreter – an expression evaluator that will "run" the code represented by an expression tree.  Once again, it seems we can just pass simple functions for each alternative to FoldExpr and have it all work out:

// NaiveEval : Expr -> int
let NaiveEval = 
    FoldExpr (fun x -> x)
             (fun l op r -> match op with
                            | Plus -> l + r
                            | Minus -> l – r)
             (fun c t e -> if c <> 0 then t else e)
             (fun e -> let x = e
                       printf "<%d>" x
                       x) 
                    
// call it on our sample expressions

exprs |> List.iter (fun expr -> printfn "%d" (NaiveEval expr))
// 42
// 2
// <42><0>42

It almost works, but notice that the third expression – the one with the if-then-else – ended up "executing" both the "then" branch and the "else" branch, printing both "<42>" and "<0>" while evaluating the expression.  Presumably this is not the desired semantic for our little language!  Since FoldExpr handles the recursion and always recurses to traverse the whole tree, it isn’t obvious how to fix this.  But in fact, we just use a trick we already saw in the last installment.  Currently FoldExpr returns an "int", and thus each recursive call fully evaluates things to yield a final result.  We can easily change it so that instead of returning an int, the FoldExpr call will return a function "unit -> int" – a function that is waiting to be invoked to produce a result.  This changes the type of all the recursive parts, and gives us control over when code is actually executed.  Here’s the new code:

// Eval : Expr -> int
let Eval expr = 
    // f : Expr -> unit -> int
    let f = FoldExpr (fun x () -> x)
                     (fun l op r () -> match op with
                                       | Plus -> l() + r()
                                       | Minus -> l() – r())
                     (fun c t e () -> if c() <> 0 then t() else e())
                     (fun e () -> let x = e()
                                  printf "<%d>" x
                                  x)
    f expr ()
                    
exprs |> List.iter (fun expr -> printfn "%d" (Eval expr))
// 42
// 2
// <42>42

We’ve added one extra "unit" argument to each function passed to FoldExpr.  As a result, the types change so that entities like "c", "t", and "e" in the third function no longer have type "int"; instead they have type "unit -> int".  Thus the code we write in the body of the third function can choose when&whether to call each of these functions.  We call c(), and based on its value, either call t() or call e().  As a result, in our third example expression, only the print in the "then" branch gets executed ("<42>" is printed but "<0>" is not).  Just what we want!  Note that in the last line of the Eval function, we had to call the result of the FoldExpr (which I named "f" above) with not just the expression, but also a unit in order to ‘kick off’ the execution of the evaluation.

This example demonstrates not only the power of currying and partial application, but also the value of type inference.  In the change from "NaiveEval" to "Eval", we changed the type of 7 different named entities.  But we didn’t have to write a single type annotation.  Type inference works out all those details, so we can focus on making a simple change to the code, without having to worry about changing various occurances of "int" to "Func<unit,int>" or some other such drudgery.

Summary

A catamorphism is a generalization of the "fold" function to a particular data type.  In three blog entries, we’ve seen examples of folds on lists, binary trees, and abstract syntax trees for a tiny expression language.  Data that can be described using a discriminated union type is data that’s naturally amenable to catamorphisms.  Rather than define a data type, and then write lots of recursive functions that walk over that data to do various computations, you can write a single "fold" function that encapsulates all the logic in walking/recursing the data structure once-and-for-all, and then all the various computations can be expressed as applications of that "fold".  Just pass in the logic that’s essential to the particular computation to "fold" and you’re done.  As a result, writing functions like Sum for a list or a binary tree, or PrettyPrint and Eval for an AST, doesn’t need to involve writing any code that actually recurses/traverses/pattern-matches the structure.  Instead, "fold" will handle that, and the individual functions like Sum/PrettyPrint/Eval can just call "fold" with the logic appropriate to each alternative.

This was a very quick/steep walk through a deep topic.  If you’re new to functional programming in general, or F# in particular, I can imagine it may have been hard to follow.  If so, feel free to leave comments with questions.  I’m toying with the idea of trying to rewrite these examples in C#, if there are readers having a tough time coping with both the new concepts and the new syntax all at once.