The Expression Problem in Go

The Go way

Go's main vehicle of abstraction and polymorphism is interfaces. Go encourages the use of small interfaces, such that types could be easily implementing multiple interfaces if needed.

It turns out this tool and philosophy is exactly suitable for tackling the expression problem in Go.

The expression problem in Go

For a recap of the expression problem, please refer to the past posts linked at the top. Without further ado, here's a Go solution.

type Expr interface {
}

// Types
type Constant struct {
  value float64
}

type BinaryPlus struct {
  left  Expr
  right Expr
}

Note that the Expr interface is empty - any type implements it. We need something like this so that we can specify the types for the left and right members of BinaryPlus; it really means left and right can be of any type. We'll get back to this discussion shortly.

Now an interface for expressions we can evaluate:

type Eval interface {
  Eval() float64
}

And implementations for our existing types:

func (c *Constant) Eval() float64 {
  return c.value
}

func (bp *BinaryPlus) Eval() float64 {
  return bp.left.(Eval).Eval() + bp.right.(Eval).Eval()
}

The instance for Constant is straightforward, but what's going on with BinaryPlus? Recall that left and right can have arbitrary types at compile time. But at run-time, we need these to be Eval, hence the type casts. This code will fail with a cast error at run-time if the objects occupying b's left or right slots don't, in fact, imlement Eval.

Note that we could force Expr to have at least an Eval method - all expressions have to be evaluable, after all. This would make the Expr interface a bit less empty, and also would remove the need for casts in implementations of Eval. We'd still need casts for other interfaces though, as we'll see shortly.

OK, now we have the basics. Let's add another operation, without modifying existing code:

type Stringify interface {
  ToString() string
}

func (c *Constant) ToString() string {
  return strconv.FormatFloat(c.value, 'f', -1, 64)
}

func (bp *BinaryPlus) ToString() string {
  ls := bp.left.(Stringify)
  rs := bp.right.(Stringify)
  return fmt.Sprintf("(%s + %s)", ls.ToString(), rs.ToString())
}

No surprises here. How about adding a new type:

type BinaryMul struct {
  left  Expr
  right Expr
}

func (bm *BinaryMul) Eval() float64 {
  return bm.left.(Eval).Eval() * bm.right.(Eval).Eval()
}

func (bm *BinaryMul) ToString() string {
  ls := bm.left.(Stringify)
  rs := bm.right.(Stringify)
  return fmt.Sprintf("(%s * %s)", ls.ToString(), rs.ToString())
}

Again, very similar code to what we've written for other types. Finally, let's write some client code that uses these types and operations:

func CreateNewExpr() Expr {
  c11 := Constant{value: 1.1}
  c22 := Constant{value: 2.2}
  c33 := Constant{value: 3.3}
  bp := BinaryPlus{left: &BinaryPlus{left: &c11, right: &c22}, right: &c33}
  return &bp
}

func main() {
  ne := CreateNewExpr()
  fmt.Printf("ne Eval = %g\n", ne.(Eval).Eval())
  fmt.Printf("ne ToString = %s\n", ne.(Stringify).ToString())
}

This snippet demonstrates how we can create new expressions at runtime (the return type of CreateNewExpr is simply Expr) and observe their implementation of the interfaces we've defined. When run, it prints:

ne Eval = 6.6
ne ToString = ((1.1 + 2.2) + 3.3)

Discussion

So, what works well for Go here, and what doesn't?

On one hand, this seems too easy. In my initial post, I've shown an attempt to implement the same thing in C++, and encountered a fundamental problem very early - C++ has to know, at compile-time, which interfaces a class implements. Go doesn't, and herein lies the difference. Go is more like Clojure than like C++ in this respect - methods are defined outside of types, which provides two strong advantages:

1. Given a new type, we can make it implement a bunch of interfaces without modifying these interfaces.
2. Given a new interface, we can make existing types implement it without modifying their code, just by adding new code. One could say that Go satisfies the open/closed principle very well.

On the other hand, it's important to understand that the casts involved in this solution lose the static type safety guarantees of the language. Again, here Go is more like Clojure than like C++. The compiler can not verify at compile-time that we assign the right sub-expressions to a BinaryPlus, for example. We can write non-sensical code like this:

bp1 := BinaryPlus{left: "john", right: Constant{value: 2.2}}
fmt.Printf("bp1 Eval = %g\n", bp1.Eval())

And it will compile just fine! It will fail at run-time, though:

panic: interface conversion: string is not main.Eval: missing method Eval

goroutine 1 [running]:
main.(*BinaryPlus).Eval(0xc420047f30, 0xc420047df0)
  goexprsolution.go:47 +0x47
[...]

In fact, one could reasonably claim this is not a valid solution to the expression problem as originally defined by Philip Wadler:

The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

Note the explicit ban on casts.