### From Object Algebras to Finally Tagless Interpreters

Last Saturday I gave a talk at kiev::fprog meetup. I really enjoyed the event, and taking the opportunity I would like to thank Vladimir Kirillov for organizing it.

The slides of the talk can be found here, but I thought I would also write it up in a blog post.

## 1 Overview

I am going to describe two design patterns, “object algebras” and “finally tagless interpreters”, developed by the object-oriented and functional communities to solve the expression problem. I hope my presentation will serve as a hands-on, down-to-earth introduction to both patterns, but more importantly I am going to argue that they are really implementations of the same idea.

The plan is as follows. First, we are going to recall what the expression problem is about. Then, I will introduce object algebras and we will see how they help to solve the expression problem. Finally, we will see that the Java code for object algebras admits a pretty natural translation to Haskell, which will lead us to the finally tagless encoding.

## 2 Expression Problem

We begin by discussing the expression problem. To this end, we will use a classic example known as “Hutton’s Razor”. It is a language of simple arithmetic expressions built up from integer literals using the addition operation `+`. In Haskell, expressions in this language are described by the following algebraic data type `Exp`:

```data Exp = Lit Int | Add Exp Exp
```

For example, the expression `(1 + (2 + 3))` is represented in Haskell as follows:

```e1 = Add (Lit 1)
(Lit 3))
```

The function `eval` takes an expression as an argument and returns its integer value:

```eval :: Exp -> Int
eval (Lit n)   = n
eval (Add x y) = eval x + eval y
```

This is a minimal setup that we will try to extend in various ways.

Suppose that we want to add a function `view` that converts an expression to a string, its textual representation. This is fairly straightforward:

```view :: Exp -> String
view (Lit n)   = show n
view (Add x y) = "(" ++ view x ++ " + " ++ view y ++ ")"
```

If, however, we decide to extend our language with the multiplication operation `*`, we have to introduce a new constructor `Mul` in the definition of the data type `Exp`, which entails adding a new case to every function defined on `Exp`.

Java, as well as many other object-oriented languages, doesn’t have algebraic data types and the standard object-oriented approach to this problem is different.

To wit, one defines an interface (or an abstract class) `Exp` of expressions, which is implemented (or subclassed) by concrete classes `Lit` and `Add` representing different types of expressions:

```interface Exp {
int eval();
}

class Lit implements Exp {
int n;
int eval() { return n; }
}

Exp x, y;
int eval() { return x.eval() + y.eval(); }
}
```

For the sake of brevity, from now on I will omit access modifiers and constructor definitions in Java code.

The operation `eval` is defined as a method of the interface `Exp`, and the concrete classes `Lit` and `Add` implement this method.

In order to add the multiplication operation, it suffices to define a new class `Mul` that implements the interface `Exp`:

```class Mul implements Exp {
Exp x, y;
int eval() { return x.eval() * y.eval(); }
}
```

Note that we don’t need to touch the classes `Lit` and `Add`.

However, it is rather awkward to add new operations as we need to add new methods to the interface `Exp`, which is going to break all its concrete implementations.

We see that the functional and object-oriented paradigms are in some sense dual to each other. There is a standard way to visualize this duality.

Consider a rectangular table whose columns are labeled by operations and whose rows are labeled by expression types, and the cell at the intersection of given column and row contains a definition of the corresponding operation for the corresponding expression type. In the functional approach, the definitions in the table are grouped by columns. A column corresponding to an operation represents a function containing definitions of that operation for all types of expressions. The table is naturally extensible in the dimension of operations: adding a new operation is easy and corresponds to adding a new function, i.e., a new column. Extensibility in the dimension of expression types is problematic: adding a new expression type is hard as it corresponds to adding a new row crossing all columns, and every intersection is a new case that has to be added to the corresponding function definition. In the object-oriented approach, the definitions are grouped by rows. A row corresponding to a given expression type represents a class containing definitions of all operations for that type. One of the promises of the object-oriented programming is painless extensibility in the direction of expression types. Indeed, adding a new expression type is easy in the object-oriented approach and corresponds to adding a new class, i.e., a new row to the table. Adding a new operation is hard as it corresponds to adding a new column crossing all rows, and every intersection is a new method definition that has to be added to each of the existing classes. Can we achieve extensibility in both dimensions without loss of static guarantees and without having to modify existing code? That is the essence of the expression problem.

## 3 Object Algebras

Object algebras is a relatively new object-oriented design pattern for solving the expression problem. It has been introduced in the paper “Extensiblity for the Masses”. What makes it attractive is that it is a relatively lightweight pattern that doesn’t require fancy language extensions. In particular, it can be easily implemented in mainstream languages like Java and C#. Let us see how.

We begin again by considering the language containing only literals and addition. It is going to be described by an interface

```interface ExpAlg<T> {
T lit(int n);
}
```

If you are familiar with GoF design patterns, you may recognize this as the Visitor interface. However, in this approach this interface is going to play a completely different role. Namely, in terms of GoF design patterns `ExpAlg<T>` is an interface of an abstract factory for creating expressions.

For example, the expression `(1 + (2 + 3))` is represented as follows:

```<T> T e1(ExpAlg<T> f) {
f.lit(1),
f.lit(2),
f.lit(3)));
}
```

That is, it is represented as a function taking as an argument an object `f` implementing the interface `ExpAlg<T>` (i.e., a concrete factory) and returning a value of type `T`. The body of the function simply calls the methods `lit` and `add` of the factory `f` in a suitable order with suitable arguments.

This representation allows us to vary the concrete factory `f` thus interpreting the expression `e1` in different ways.

Let us see how this works in the case of evaluation of expressions.

First of all, we introduce an interface `Eval` of “objects that can be evaluated”:

```interface Eval { int eval(); }
```

Next we define a concrete factory `EvalExp`, which is going to manufacture expression that can be evaluated:

```class EvalExp implements ExpAlg<Eval> {
Eval lit(final int n) {
return new Eval() {
int eval() {
return n;
}
};
}
Eval add(final Eval x, final Eval y) {
return new Eval() {
int eval() {
return x.eval() + y.eval();
}
};
}
}
```

We can now pass an instance of the factory `EvalExp` into the expression `e1` and get back an object that has a method `eval`. We can call this method and convince ourselves that it returns the right value:

```int v1 = e1(new EvalExp()).eval();
```

We shall soon see another example of defining operations, but first let us think how we could add multiplication to our language.

We could add a new method `mul` to the interface `ExpAlg<T>`, but then the implementation of the concrete factory `EvalExp` would require changes, which is precisely what we would like to avoid.

Instead, we introduce a new interface `MulAlg<T>` that extends the interface `ExpAlg<T>` and adds a new method `mul` to it:

```interface MulAlg<T> extends ExpAlg<T> {
T mul(T x, T y);
}
```

Expressions containing multiplication are now going to be represented as functions taking as an argument objects implementing the extended interface `MulAlg<T>`. For example, the expression `(4 * (5 + 6))` will be represented as follows:

```<T> T e2(MulAlg<T> f) {
return f.mul(
f.lit(4),
f.lit(5),
f.lit(6)));
}
```

To extend the implementation of evaluation of expressions to expressions containing multiplication we define a new concrete factory `EvalMul` that implements the interface `MulAlg<Eval>` and inherits from the factory `EvalExp` implementations of the methods `lit` and `add`:

```class EvalMul extends EvalExp implements MulAlg<Eval> {
Eval mul(final Eval x, final Eval y) {
return new Eval() {
int eval() {
return x.eval() * y.eval();
}
};
}
}
```

We can now pass an instance of the factory `EvalMul` into the expression `e2`, get back an object that can be evaluated, and compute its value by calling the `eval` method:

```int v2 = e2(new EvalMul()).eval();
```

Note that we are not touching any existing code: we are defining new interfaces and classes and use inheritance to avoid duplication.

Let us consider an example of adding a new operation and convince ourselves that it doesn’t require touching existing code either.

We introduce an interface `View` of “object that can be converted to a string”:

```interface View { String view(); }
```

We then define concrete factories `ViewExp` and `ViewMul` implementing the interfaces `ExpAlg<View>` and `MulAlg<View>`:

```class ViewExp implements ExpAlg<View> {
View lit(final int n) {
return new View() {
String view() {
return Integer.toString(n);
}
};
}
View add(final View x, final View y) {
return new View() {
String view() {
return "(" + x.view() + " + " + y.view() + ")";
}
};
}
}
```

```class ViewMul extends ViewExp implements MulAlg<View> {
View mul(final View x, final View y) {
return new View() {
String view() {
return "(" + x.view() + " * " + y.view() + ")";
}
};
}
}
```

Notice that we have a choice: to define conversion to a string only for expression containing literals and addition or also for expressions containing multiplication. In the latter case, the class `ViewMul` inherits from `ViewExp` the methods responsible for conversion of literals and addition and adds a definition of conversion of multiplication, thereby implementing the interface `MulAlg<View>`.

We can now pass these factories into the expressions `e1` and `e2`, get back objects supporting the method `view`, and convince ourselves that this method returns the right values:

```String s1 = e1(new ViewExp()).view();
String s2 = e2(new ViewMul()).view();
```

A few words about the terminology. The abstract factory interface `ExpAlg<T>` is called an object algebra interface and concrete factories implementing it are called object algebras. The terminology and the approach in general are inspired by abstract algebra, in which algebraic structures (or simply algebras) are described by signatures. A signature acts as an interface that specifies the types of operations defined on the underlying set of an algebraic structure, and an algebra provides concrete definitions of those operations and is similar to a class implementing an interface.

## 4 Finally Tagless

We now translate the above example from Java to Haskell and arrive at essentially the finally tagless approach.

This approach has been introduced in the paper “Finally Tagless, Partially Evaluated”. It enjoys many interesting properties, but we are only going to focus on how it helps us to solve the expression problem.

First, we consider how expressions are represented in the finally tagless approach.

The Haskell counterpart of the interface `ExpAlg<T>` in Java is a typeclass `ExpAlg`:

```class ExpAlg t where
lit :: Int -> t
add :: t -> t -> t
```

The expression `(1 + (2 + 3))` is represented as follows:

```e1 = add (lit 1)
(lit 3))
```

and its inferred type `ExpAlg t => t` can be read as a statement that the term `e1` can be given any type `t` as long as `t` is an instance of the typeclass `ExpAlg`, i.e., supports the operations `lit` and `add`.

What is remarkable is that at the stage of desugaring the typeclass `ExpAlg` is translated into a record type with fields `lit` and `add`, instance declarations of `ExpAlg` are translated into record values of this type, and the expression `e1` is translated into a function taking as an argument a record value corresponding to an instance declaration of `ExpAlg` for a given type `t`. This record value is a direct analog of the concrete factory `f` in Java.

The difference between Haskell and Java is that in Haskell for every pair of a typeclass and a type there can be at most one instance declaration, and once this instance declaration is defined, it remains implicitly in the scope and is passed around automatically by the compiler. In Java, there can be many implementations of a given generic interface instantiated with a given type, and these implementation are entities in the program that have names and have to be passed around explicitly.

To understand how operations are defined in the finally tagless approach, let us look again at evaluation of expressions. We are going to simplify the Java implementation first to make translation to Haskell more obvious.

Namely, we observe that we don’t have to make `Eval` an interface, although conceptually this is cleaner. After all, if all we know about an object is that it implements the interface `Eval`, then all we can do with this object is to call the method `eval`. Therefore, for an external observer such an object is practically indistinguishable from an object of a class `Eval` with a public field `eval` of type `int`. With this change, the definition of the factory `EvalExp` becomes:

```class Eval { public int eval; }

class EvalExp implements ExpAlg<Eval> {
Eval lit(int n) {
return Eval(n);
}
Eval add(Eval x, Eval y) {
return Eval(x.eval + y.eval);
}
}
```

To evaluate the expression `e1` we pass it an instance of the class `EvalExp`, which produces an object of the class `Eval`, which we can ask the value of its field `eval`:

```int v1 = e1(new EvalExp()).eval;
```

The class `Eval` is a wrapper around the type `int`. In Haskell, we introduce a wrapper `Eval` around the type `Int` implemented, say, as a `newtype`:

```newtype Eval = Eval { eval :: Int }
```

The definition of the class `EvalExp` translates into an instance declaration of the typeclass `ExpAlg` for the type `Eval`:

```instance ExpAlg Eval where
lit n   = Eval n
add x y = Eval \$ eval x + eval y
```

To evaluate the expression `e1` we restrict its type `ExpAlg t => t` to `Eval`, which is similar to applying the expression `e1` to the concrete factory `EvalExp` in Java, and then the obtained value of type `Eval` can be queried the value of the field `eval`:

```v1 = eval (e1 :: Eval)
```

In fact, we don’t have to explicitly restrict the type of `e1` to `Eval` as the compiler will infer this automatically from the fact that `e1` is passed as an argument to the function `eval :: Eval -> Int`.

In Java, extension of the language with the multiplication operation corresponded to extension of the interface `ExpAlg<T>` to `MulAlg<T>` with the method `mul`. In Haskell, this translates into a definition of a new typeclass `MulAlg` that is a subclass of `ExpAlg`:

```class ExpAlg t => MulAlg t where
mul :: t -> t -> t
```

Expressions containing multiplication will now have the type `MulAlg t => t`, for example:

```e2 = mul (lit 4)
(lit 6))
```

To extend the definition of the operation `eval`, we perform the same transformation as above: we replace the interface `Eval` with a class `Eval` with a public field of type `int`. Then the definition of the class `EvalMul` implementing the interface `MulAlg<Eval>` translates in Haskell into a definition of an instance declaration of the typeclass `MulAlg` for the type `Eval`:

```instance MulAlg Eval where
mul x y = Eval \$ eval x * eval y
```

Finally, we consider an example of adding new operations in the finally tagless approach. Let us implement conversion to string.

We transform the object algebras implementation of conversion in Java similarly to what we did to the implementation of evaluation: we replace the interface `View` with a class `View` with a public field `view` of the type `String`. Then in Haskell this all is going to turn into an instance declaration of the typeclass `ExpAlg` for a type `View` that is a `newtype` wrapper around `String`:

```newtype View = View { view :: String }

instance ExpAlg View where
lit n   = View \$ show n
add x y = View \$ "(" ++ view x ++ " + " ++ view y ++ ")"
```

Extension of the operation `view` to expressions containing multiplication is done similarly and amounts to defining an instance declaration of the typeclass `MulAlg` for the type `View`:

```instance MulAlg View where
mul x y = View \$ "(" ++ view x ++ " * " ++ view y ++ ")"
```

The encoding we have arrived at is almost identical to that proposed in “Finally Tagless, Partially Evaluated”. The difference is that in Haskell there is no need to make `MulAlg` a subclass of `ExpAlg`: we can define it as a separate typeclass:

```class MulAlg t where
mul :: t -> t -> t
```

and then expressions containing multiplication will be represented by values of the type `(ExpAlg t, MulAlg t) => t`. This gives us more flexibility because we can represent different language extensions as separate typeclasses that can be arbitrarily combined.