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.

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

In languages that do not allow that (e.g. Java), one has to implement it by hand, using a Visitor pattern. Instead of relying on the language to do the dynamic dispatch, one has to explicitly add a visiting method for another data type.

To me, the turn towards interfaces / typeclasses / traits / protocols is one of the most notable bits of progress in the newer crop of programming languages (and, importantly, their standard libraries).

On the other hand, Rust / Haskell provide partial solutions with static typing — but run into annoying boilerplate related to the orphan rule.

I’m not sure if there’s a true solution, given the level of thinking which has gone into these two forks in the road.

The Expression Problem and its solutions - https://news.ycombinator.com/item?id=11683379 - May 2016 (49 comments)

I think Antlr 4 does similar, I just haven't used it in as much anger because its runtime always jammed me up https://github.com/antlr/antlr4/blob/4.13.2/doc/listeners.md...

I thought that IntelliJ did similarly but I am misremembering since they generate recursive descent style https://github.com/JetBrains/Grammar-Kit/blob/v2023.3/HOWTO....

We use this pretty effectively in our iOS app to model and implement Effect types in a functional core / imperative shell architecture.

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!