Original post

I’ve written about the expression problem here
and later also here.
Between them, these posts presented various solutions and non-solutions in C++,
Haskell and Clojure.

Today I want to add another language into the mix – . It turns out that
interfaces allow us to solve the expression problem, or at least a limited
variant thereof.

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 = %gn", ne.(Eval).Eval())
  fmt.Printf("ne ToString = %sn", 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 = %gn", 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.