The Expression Problem and its solutions

This article discusses details of trying to use language features to model a fairly basic problem but doesn’t discuss the fundamentals of the problem very much.

If I have O operations (e.g. evaluate, stringify) and T types, then I need O•T implementations. If I fix O, I can add types until the cows come home by adding O implementations per new type. If I fix T, I can add new operations with T implementations per operation. If I want to let O and T vary, then the number of implementations I need to add per additional operation/type varies depending on what I’ve added before. No amount of programming language magic will change this basic count.

ISTM what’s really going on in the article is that the author is using the programming language as a registry of implementations. Those O•T implementations need to be stored somewhere so their callers can find them. In C++ this can be done when very verbose inheritance and virtual calls. In other languages, it’s less verbose. If multiple dispatch is built in, then one can use it directly. One can, of course, also build an actual table indexed on operation and type as a data structure in just about any language and use it, and in a language like C++ the result may well be quite a bit nicer than using a class hierarchy.

I think this is missing mentioning:

Object algebras: https://i.cs.hku.hk/~bruno/oa/

Tagless final: https://okmij.org/ftp/tagless-final/course/lecture.pdf

and Data types a’la carte: https://webspace.science.uu.nl/~swier004/publications/2008-j...

We were discussing this a few days ago in https://news.ycombinator.com/item?id=45121080.

Rust doesn't merely have a way around the Expression Problem, the entire language & it's set of libraries is built constructively / additively bottom-up atop very dumb types, with operations added latter! Traits and impls invert the responsibility to define operations, are still static definitions & static types but late-created / created-elsewhere types, that aggregate more and more impls than the type is initially defined with. An inversion of control of typing. Dynamic but still compile-time static types.

It's refreshing to see this very clear problem statement, which feels like an ideal anti-thesis that reveals the hidden glory of Rust's traits/impls:

> It turns out that adding new operations isn't as easy as adding new types. We'd have to change the Expr interface, and consequently change every existing expression type to support the new method(s). If we don't control the original code or it's hard to change it for other reasons, we're in trouble.

> In other words, we'd have to violate the venerable open-closed principle, one of the main principles of object-oriented design, defined as:

> software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification

Apologies for the self link, but this came up very recently in a sub thread about Rust & I'm so glad to close the loop & find a name for this. I said there & I'll say again, I think this is one of Rust's Greta superpowers, that we are not trapped by the design parameters of the libraries we consume, that Rust allows us to layer in more and more to our types, as we please. An amazing superpower of Rust that imo gets way too little attention, where-as the borrow-checking tends to soak all the attention/fixation for the language. https://news.ycombinator.com/item?id=45041286#45045202

There's a whole chapter of the Rust book on Rust & OOP, btw, which provides a side-ways look at how Rust & OOP and the Expression Problem relate. https://doc.rust-lang.org/book/ch18-00-oop.html

C# and others have extension methods, where you can add operations. But most of the language & it's use is pretty conventional OOP; it's a feature not the core. Mentioned in the thread above, there's a claim that Standard ML functors have similarities to rust: I haven't investigated yet but that'a piqued my interest & I'm eager to find out at some point!