🧩 Exploring the Expression Problem in Go with Generics 🔗

The “Expression Problem” is a classic challenge in programming language design. In this post, we’ll explore how to approach solving it in Go using generics, referencing the ideas presented in the Featherweight Go paper, and examining the limitations of Go’s current implementation.

📑 Table of Contents 🔗

❓ What is the Expression Problem? 🔗

To understand the challenge, it helps to look at how the Featherweight Go paper defines it:

“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.”

The paper provides an excellent analogy to help visualize this:

“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.”

In short: A true solution allows us to effortlessly add new data variants (rows) and new operations/behaviors (columns) to our code without having to modify the existing source code.

🚧 The Limitation in Modern Go 🔗

The solution proposed in the original Featherweight Go draft relies on a feature that didn’t make it into the final Go 1.18 generics release.

Specifically, the paper’s ideal solution assumes you can apply stricter type constraints on a method receiver than what was defined on the base struct. For example, ideally, we would want to do this:

// Hypothetical (Not valid Go): 
// Constraining the method receiver directly
func (e Plus[T Evaler]) Eval() int
func (e Plus[T Stringer]) String() string

However, Go’s implementation of generics requires the method receiver’s type constraints to perfectly match the struct’s type definition. You cannot add new constraint requirements (like Evaler or Stringer) on a method-by-method basis.

🛠️ A Compromised Workaround 🔗

Because we cannot constrain type parameters at the method level, we are forced to constrain them at the struct level.

Below is an adapted code example that works perfectly with Go 1.18+ generics. However, notice that we are forced to define a combined Expr interface upfront. Because we must modify this interface every time we want to add a new operation, this is not a true solution to the Expression Problem, but rather a practical workaround adapted from the paper:

package main

import (
	"fmt"
)

// 1. Define our Base Data Type
type Num struct {
	value int
}

// 2. Define our Operations (Columns)
type Evaler interface {
	Eval() int
}

type Stringer interface {
	String() string
}

// Implement the operations for our base type
func (e Num) Eval() int {
	return e.value
}

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

// 3. The Compromise: We must pre-define a combined interface.
// If we want to add a new operation later, we are forced to edit this interface,
// violating the core rule of the Expression Problem.
type Expr interface {
	Evaler
	Stringer
}

// 4. Define a Generic Data Type (Row)
// Because Go doesn't allow method-level constraints, we must constrain T to Expr here.
type Plus[T Expr] struct {
	left  T
	right T
}

func (e Plus[T]) Eval() int {
	return e.left.Eval() + e.right.Eval()
}

func (e Plus[T]) String() string {
	return fmt.Sprintf("(%s+%s)", e.left.String(), e.right.String())
}

// 5. Execution
func main() {
	var e Expr = Plus[Expr]{left: Num{1}, right: Num{2}}
	
	fmt.Println(e.Eval())   // Output: 3
	fmt.Println(e.String()) // Output: (1+2)
}

🏁 Conclusion 🔗

While Go’s generics are incredibly powerful and bring much-needed flexibility to the language, they don’t natively solve the Expression Problem in the way the Featherweight Go paper originally envisioned. By requiring constraints to be defined at the struct level rather than the method level, developers still have to pre-plan interfaces or modify existing code when adding new operations to generic types.

Kaue's Way of Life

Get It Free