Solution To The Expression Problem In Go Using Generics 🔗

This is how to solve the Expression Problem in the Go language using generics.

Click to read the Featherweight Go paper.

The paper says:

The goal is to define a data type by cases, where one can add new cases to the data type and new functions over the data type, without recompiling existing code, and while retaining static type safety.

Whether a language can solve the Expression Problem is a salient indicator of its capacity for expression. One can think of cases as rows and functions as columns in a table. In a functional language, the rows are fixed (cases in a datatype declaration) but it is easy to add new columns (functions). In an object-oriented language, the columns are fixed (methods in a class declaration) but it is easy to add new rows (subclasses). We want to make it easy to add either rows or columns.

The solution in the paper does not work for the current Go implementation of generics because the implementation does not allow:

func (e Plus(type a Evaler)) Eval() int
func (e Plus(type a Stringer)) String() string

Here is code that works with the current Go implementation of generics but is not really a solution to the Expression Problem, adapted from the paper:

package main

import (
	"fmt"
)

type Any interface{}

type Num struct {
	value int
}

// Should be: Plus(type a Any)
type Plus(type a Expr) struct {
	left  a
	right a
}

type Evaler interface {
	Eval() int
}

func (e Num) Eval() int {
	return e.value
}

// Should be: Plus(type a Evaler)
func (e Plus(a)) Eval() int {
	return e.left.Eval() + e.right.Eval()
}

type Stringer interface {
	String() string
}

func (e Num) String() string {
	return fmt.Sprintf("%d", e.value)
}

// Should be: Plus(type a Stringer)
func (e Plus(a)) String() string {
	return fmt.Sprintf("(%s+%s)",
		e.left.String(), e.right.String())
}

type Expr interface {
	Evaler
	Stringer
}

func main() {
	var e Expr = Plus(Expr){Num{1}, Num{2}}
	fmt.Println(e.Eval())   // 3
	fmt.Println(e.String()) // (1+2)
}

Click to run this on the Go playground.