How I Solved the Expression Problem

Introduction

The Expression Problem (EP) is, in my opinion, the toughest problem facing programming languages. Even unseating a giant, firmly established rival language is easier!

So what is the Expression Problem? I like the description in this post:

Imagine that we have a set of data types and a set of operations that act on these types. Sometimes we need to add more operations and make sure they work properly on all types; sometimes we need to add more types and make sure all operations work properly on them. Sometimes, however, we need to add both - and herein lies the problem. Most of the mainstream programming languages don’t provide good tools to add both new types and new operations to an existing system without having to change existing code.

– Eli Bendersky

In fact, I like that post so much that I will refer to it several times in this post, so you should go read it, especially since it dives into concrete attempts to solve the EP in various programming languages.

It also introduces the example that this post will use, so reading Eli’s post is a prerequisite to this one. Seriously, go read it.

The Expression Problem

Alright, now let’s get on with it. I will try to explain the EP in my own words.

Have you heard the adage that language shapes thought? And not just thought, but capability. In that linked article, a five-year-old in an Aboriginal culture could point North without hesitation. Scholars at universities could not.

The EP is, essentially, about how programming languages limit thought and capability.

Object-oriented programming (OOP) languages are oriented towards objects, which are concrete instances of types. So in OOP, it is easy to add types.

Functional programming focuses on functions, which are concrete instances of operations. So in functional programming, it is easy to add operations.

But “no plan survives contact with the enemy” of changing requirements and technical debt.

Especially since we are so “Agile” now.

So in an OOP language, when faced with a change that requires a refactor, programmers may have to add operations. Of course, since the language limits their thoughts and capabilities, they may not be able to do so.

And in a functional language, when faced with a similar change, programmers may have to add types.

In both cases, a typical, but subpar, language requires them to go through the entire code base making small changes to many places. This is not good, for two reasons:

• They may miss one or more spots, leading to bugs.
• They may not even be able to change some code if it is from a third party.

The first can be solved with manpower. The second is, in many cases, unsolvable.

This is why the EP is so important in software development.

Requirements

So what problems must be solved in a solution to the EP?

According to the original formulation, there are only four prongs:

1. “add new cases to [a] datatype”
2. “add new functions over [a] datatype”
3. “without recompiling existing code”
4. “while retaining static type safety (e.g., no casts)”

These are numbered, so I can refer to them later.

Solutions and Their Tradeoffs

There have been a lot of solutions to the EP, and to be honest, some of them do completely solve it.

That is why I titled this post “How I Solved the Expression Problem.”

It’s just that I wonder if the tradeoffs are worth it.

So let’s talk about those based on what languages they are found in.

C++

From Eli Bendersky’s post, the first solution is in C++. He does this by using the visitor pattern to flip the EP on its head, essentially allowing C++ to add functions but not types, then adding multiple inheritance to add new types as well.

It is actually not a valid solution because it requires a cast, which is explicitly disallowed by Requirement 4.

But C++ has another wrinkle: the One Definition Rule (ODR). If there is more than one definition of a class and its methods it is Undefined Behavior, and Undefined Behavior is very bad. Every C++ solution must be careful to not violate the ODR.

Clojure

The next two solutions by Eli Bendersky are in Clojure, both of which are quite impressive.

The first one takes advantage of multi-methods, an extraordinarily powerful concept. And yes, they can solve the EP if done right.

However, even though I have known about multiple dispatch for a long time, I do not want to have it. There are a few reasons, but the biggest is ambiguity.

Of course, Rich Hickey, Clojure’s creator, is brilliant, so Clojure has a solution: the prefer-method function.

I’m still not a fan of multiple dispatch, though.

Eli then provides another solution, one using protocols. This one seems better to me, and it is an example of just how powerful Clojure is.

But as it turns out, both of these solutions are technically invalid; Clojure is dynamically typed, not statically typed, so it cannot satisfy Requirement 4.

Haskell

Next, in a separate post, Eli creates a solution in Haskell. It’s quite convoluted, but Haskell is fully statically typed, so EP solved, right?

Unfortunately, no. Of his solution, Eli said:

Also, if we add more node types to our expression language, these definitions will get even more complicated because the ET tree will get deeper; and finally, the worst problem of all, we’d have to rewrite the existing code that creates expressions because the El/Er paths change.

(Emphasis added.)

The emphasized part violates Requirement 3. So this is technically not a solution either.

In reality, this is the other side of the coin for an old problem in Haskell: orphan instances.

tl;dr: Haskell has two things: types and typeclasses (somewhat like Java/C# interfaces or Rust traits). A module can make an instance of a typeclass for a specific type. If either the typeclass or the type is defined in the module defining the instance, all is well.

An instance defined in a module that does not define the typeclass or type is an orphan instance.

These are allowed in Haskell, but they have an important limitation:

Unlike other declarations, for which only the entities declared in a signature file are brought into scope, instances from the implementation are always brought into scope, even if they were not declared in the signature file. This means that a module may typecheck against a signature, but not against a matching implementation. You can avoid situations like this by never defining orphan instances inside a package that has signatures.

– GHC Manual

In other words, orphan instances can cause the compiler to claim that some code successfully passes the type checker when it should not (false negative).

In other words, Haskell’s famously strict static typing can be bypassed, which violates Requirement 4.

This means that Haskell has two ways to solve the EP, but they both violate one requirement.

Rust

Rust, with its traits, has a similar problem to Haskell, but they decided to ban orphan instances through the orphan rule. The Rust designers decided that avoiding latent compiler errors was worth it, and I agree.

Instead, Rustaceans created the extension crate pattern.

And this, I think, is the closest that any language has gotten to solving the expression problem:

1. It fulfills Requirement 1 because Rust allows users to create new types.
2. It fulfills Requirement 2 because extension traits allow adding new functions to traits, and new methods can be added to types through impls.
3. It fulfills Requirement 3 because it explicitly avoids recompiling code, or causing existing code to not compile by banning orphan instances (impls).
4. It fulfills Requirement 4 because traits are fully type checked.

The only small thing that might violate a requirement is the fact that extension crates do not allow adding functions to existing types; extension traits are new types, not actual extensions to existing types.

Nevertheless, in my opinion, Rust fulfills the spirit of the requirements the best because the new type (extension trait) would not be used by the existing code anyway. And in any case, people generally accept adding new types as a valid fulfillment of Requirement 1, which technically calls for “new cases,” not new types.

Thus, I argue that Rust extension traits, with new impls, qualifies as “new functions over [a] datatype.”

Python and Ruby

Next are Python and Ruby. I am lumping them together because they both use the same solution: monkey patching.

Unfortunately, monkey patching is not a valid solution because it requires dynamic types, so it violates Requirement 4.

Also monkey patching is dangerous.

Julia

Julia is another language with multiple dispatch, so it must solve the EP, right?

Unfortunately, Julia is dynamically typed, so it does not fulfill Requirement 4.

Go

Eli Bendersky also created a solution in Go. Unfortunately, it requires casts, so it fails Requirement 4.

My Solution

Alright, now I can talk about my solution and my language which I named Yao.

The implementation of these ideas is not finished yet.

Yao does not have impls, but it does have methods:

struct Constant
{
    val: f64;

    eval() -> f64
    {
        return val;
    }
}

Calling a method is done the usual way:

c := Constant { 7.0 };

c.eval();

But now, let’s look at what the Expr trait/interface/whatever might look like:

trait Expr
{
    eval() -> f64;
}

Notice that eval() does not take any arguments, even a self argument. How can the Constant type implement Expr when eval() does not allow it to give itself as an argument?

The answer is that methods work differently in Yao; they are not functions with an implicit first argument. Instead, they are curried functions.

Curried functions in Yao look like this:

fn standalone_test(exe: str, vg: bool) -> (inject: bool) -> uint
{
    // Code goes here.
}

The above is actual code from my test script.

You can do this:

test_func: (bool)->uint = standalone_test("exe", true);

And later, test_func can be used as a function:

res: uint = test_func(true);

This is also how Yao implements closures.

Methods are just an extension of curried functions. They do have an implicit argument, but the argument is in its own part. Thus, the eval() method for Constant is actually this:

fn eval(this: &Constant) -> () -> f64
{
    return this.val;
}

Yes, this means that you can curry it like this:

func: ()->f64 = c.eval;

Notice no trailing parentheses.

This is how Constant can implement the Expr trait: currying the method to create a function that implements the corresponding function in the trait.

Now, suppose someone adds a ExprString trait that has this:

// The colon and name construct means that `ExprString` requires an
// implementation for `eval()` too.
trait ExprString: Expr
{
    to_str() -> str;
}

And even if Constant is defined in a different package, to_str() could be implemented for it using a curried function:

fn to_str(c: &Constant) -> () -> str
{
    return str(c.eval());
}

Awesome; it’s just like Yao can extend types with more methods, but it’s not monkey patching, and it’s static, so it’s perfectly safe.

Except, what if there are multiple packages that create ExprString implementations for Constant? This is, after all, the real crux of the EP.

Yao has a solution: make trait instances runtime values.

See, in Rust, traits are only a thing at compile time, and the same is true of Haskell typeclasses; that is why Eli’s Haskell solution was so convoluted: he couldn’t pass a typeclass to a function as a value.

But what if Yao lets us do that? It would look like this:

fn example(es: ExprString) -> f64
{
    io.print(es.to_str() +~ "\n");

    return es.eval();
}

How will that work? Assume that both Expr, ExprString and Constant are defined in different packages, and Constant does not implement ExprString.

We can define the curried function above to implement ExprString for Constant, as per usual.

Then, when we need to use an ExprString (say, pass it to example()), we can do this:

es := ExprString { c.eval, to_str(c) };

example(es);

Alright, let’s go one step further. Let’s assume that Expr and Constant are defined in the expr package, ExprString is defined in the string package, to_str() is defined in the other package, and example() is defined in the example package.

Then, assume that there is another ExprString implementation for Constant in the orphan package. We could even assume it has its own implementation of eval() too:

fn eval(c: &Constant) -> () -> f64
{
    return c.eval();
}

fn to_str(c: &Constant) -> () -> str
{
    return "orphan: " +~ other.to_str(c)() +~ "\n";
}

Yes, this is a scuffed example; work with me here.

Perhaps we are working on the dependent package that has to import all of the above packages; what happens then? There are multiple implementations of ExprString for Constant, so how does Yao resolve it?

The answer: it uses whatever the programmer uses at runtime. We can even use both, just for kicks:

es1 := string.ExprString { c.eval, other.to_str(c) };

example.example(es1);

es2 := string.ExprString { orphan.eval(c), orphan.to_str(c) };

example.example(es2);

We can even mix and match implementations:

es1 := string.ExprString { c.eval, orphan.to_str(c) };

example.example(es1);

es2 := string.ExprString { orphan.eval(c), other.to_str(c) };

example.example(es2);

This shows that it doesn’t matter if some other package defines a new implementation; Yao knows which to use because that’s done at runtime.

But it goes further! You could even create an ExprString from an Expr:

e: expr.Expr { c.eval };
es := string.ExprString { e.eval, other.to_str(c) };

But it goes even further! Since the “functions” are actually curried, they can be renamed; they do not have to have the same name as the traits they help implement:

fn evaluate(c: &Constant) -> () -> f64
{
    return c.eval();
}

e := expr.Expr { evaluate(c) };

And of course, you can add a BinaryAdd type that implements both traits:

struct BinaryAdd
{
    a: string.ExprString;
    b: string.ExprString;

    fn eval() -> f64
    {
        return a.eval() + b.eval();
    }

    fn to_str() -> str
    {
        return "(" +~ a.to_str() +~ " + " +~ b.to_str() +~ ")";
    }
}

You could even create an ExprString from standalone functions:

fn zero_eval() -> f64
{
    return 0.0;
}

fn zero_to_str() -> str
{
    return "0.0";
}

zero := string.ExprString { zero_eval, zero_to_str };

So does Yao solve the EP? I argue that yes, it does:

1. It can add new types (such as BinaryAdd).
2. It can add new functions over a datatype (curried functions for types, as well as new traits that extend other traits).
3. It can add both without recompiling existing code because that existing code does not need to know about the new types to keep working; the use of existing types in existing code uses explicit runtime trait values, which means that new compile-time definitions do not interfere.
4. It does this while retaining static type safety because traits are types themselves and can be fully type checked. Plus, it avoids a self argument that could be any type and interfere with type checking.

Why Does This Work?

Yes, I understand that people smarter than me might be able to find a hole and prove me wrong.

But assuming that this does solve the EP, the question then becomes: why does this work?

The answer has two parts.

First, one reason the EP is so hard to solve is that every language with static typing has statics-dynamics biformity. Somehow, this needs to be worked around while still retaining the benefits of static typing.

Second, runtime is more powerful than compile-time. This is a double-edged sword; yes, it is more powerful, but that makes it harder to prove non-trivial properties about runtime. This is especially relevant to the EP because Requirement 4, static type safety, essentially requires proving a non-trivial property.

So all I did with Yao was move one thing, traits, to runtime. This made them more powerful, which allows Yao to fulfill Requirement 3.

But I was careful how I did that; I still needed to be sure those new runtime values had static types.

It was one flash of insight that helped me figure it out: I was thinking about Go interfaces and object-oriented programming. And I realized that objects are values and types. More accurately, classes are types, and objects are values.

So what if I created values from traits? So Yao has traits and trait values. And that was the key.

Of course, currying and closures were a big help as well, but the important bit was creating values from compile-time traits because traits allow type checking, while trait values allow the types within to vary at runtime.

Tradeoffs

Of course, like every solution to the EP, Yao’s solution has tradeoffs.

First, every function in Yao is technically a closure. This has a cost, although one of the main optimizations in the compiler would be to represent standalone functions efficiently.

Second, there is the performance penalty of building a trait value at runtime.

Third, there is a performance penalty of calling closures, which would be function pointers.

Fourth, the programmer has to do extra work to write the code to build trait values. I’m sure programmers don’t want to do that over and over. So I am going to make a shorthand.

But I do not see this as a bad thing; I see it as an advantage because “explicit is better than implicit.”

Conclusion

Of course, I am biased, but even so, I firmly believe that this solution is the best.

It is more elegant than any other; it avoids the superfluous self and is more powerful than purely static traits/typeclasses.

It is also easier; there is no “orphan rule” to remember.

It is also safe; there is no dangerous monkey patching because there is no need to dynamically change a type’s methods to extend the type.

But caveat emptor; the implementation is not finished, so I could be wrong.