Over a million developers have joined DZone.

The Expression Problem in Go

DZone's Guide to

The Expression Problem in Go

We take a look at a problem known as the Expression Problem, this time in the Go language. Read on for the details and how Go attempts to address the issue.

· Integration Zone ·
Free Resource

How to Transform Your Business in the Digital Age: Learn how organizations are re-architecting their integration strategy with data-driven app integration for true digital transformation.

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 to the mix - Go. It turns out that Go 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 are 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, with an interface for expressions we can evaluate:

type Eval interface {
  Eval() float64

And implementations of 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, implement Eval.

Note that we could force Expr to have at least an Eval method - all expressions have to be evaluatable, 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 the 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)


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 cannot 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.

Build and deploy API integrations 7x faster. Try the Cloud Elements 100% RESTful platform for 30 days free. Access your trial here.

go ,interfaces ,integration ,expression problem

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}