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.
moelf · 1h ago
this is counting it as if O only takes an argument, which is single dispatch, which OOP covers already (the `self` is the single argument).
In practice, Multiple Dispatch shines when you have 1) more than one argument type (duh) 2) higher order `O` operation [1]
[1]: think of a numerical routine that calls eigen or something, and you want eigen to exploit the matrix's type, such as symmetry or upper-triangular, and this is encoded as a matrix type)
kqr · 2h ago
Huh, this is a very neat way to put it. Something about it seems... too neat? But I'm the wrong person to poke holes in it. Can I see other people debate it civilly?
magnio · 2h ago
My first exposure to the expression problem is the book Crafting Interpreters, Section 5.3.1,[1] which is very similar to the GP comment. The subsection is a short few paragraphs, with one or two tables for illustration, and it was one of the most eureka moments of my programming career. Ever since then, I see this trade-off everywhere, and I get reminded that engineering is all about finding the best trade-off and that the holy-grail of a perfect language or design is a waste of time.
I think the article as it stands makes that all pretty clear. But the point of the article is more that the language selection will determine how difficult it is to do that if you don't have control over the original definition of the operations or types.
HarHarVeryFunny · 1h ago
Overloading operators like "+" to work on new types, and maybe mixed types, requires each desired combination of operator and operand types to be implemented (as one can easily do in a language like C++, and presumably also in more modern languages). If there is any commonality between types as to how these operators are meant to work, then generics such as C++'s templates can also be used to reduce the number of implementations to those that are actually distinct.
I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch?
In any case, operator overloading, while it can make for cute-to-read code, isn't really a good idea for code readability and maintenance.
moelf · 1h ago
> operator overloading, while it can make for cute-to-read code, isn't really a good idea for code readability and maintenance
so should we write `add_int_int(1,1)` and `add_int_double(1, 1.0)` and `add_double_double(1.0, 1.0)`?...
HarHarVeryFunny · 1m ago
The expectation is that arithmetic operators are performing the corresponding arithmetic operations, so overloading for different arithmetic types (int, float, complex) doesn't produce any surprises or need to lookup operator definitions.
Applying arithmetic operators to non-arithmetic types starts to become a problem, even if some cases (set union/difference, string catenation) are natural...
The same goes for other operators... overloading '[]' indexing for maps as well as arrays seems natural, but would be highly confusing if you overloaded it for something unrelated to an index-like concept.
Kranar · 1h ago
>I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch?
The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages.
Operating overloading has nothing to do with the problem and can not be used to resolve it. Operators are nothing more than a one-off syntax so we can use familiar childhood notation like a + b, etc... they are not particularly meaningful. The ability to overload operators or functions in general is also irrelevant since such overloads are resolved statically at compile time.
munificent · 35m ago
> The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages.
Wadler's list of requirements for solving the expression problem include "with static checking that all cases are covered", so in one sense, yes, dynamic languages don't have this "problem". But in another sense, dynamic languages simply have no chance to solve the problem because they don't statically check anything.
It is true that it's much easier to do multiple dispatch and open-ended extension in dymamic languages. That's a nice benefit of them. But you do sacrifice all of the safety, code navigation, and performance of static types in order to get that.
The problem Wadler is trying to solve is "how can we have this sort of open-ended extension in both directions without giving up static safety?"
kibwen · 32m ago
> does not exist in dynamically typed programming languages
The "problem" exists for dynamically-typed languages as well. If you define a new class in Python, you still need to teach existing code how to operate on it (though you might be using inheritance to automatically derive some of those implementations, but inheritance obviously isn't limited to dynamic languages).
In short, the solution is to define an interface / typeclass / trait / protocol that factors out the particular kind of operation, and separates it from any specific class or data type. Basically it allows to tag any particular data representation with a trait, and then offer an implementation of that trait, without touching any pre-existing code related to that data representation.
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).
The article's `expression problem matrix` section states that the goal is make it `easy to add ops` and `easy to add types`. My learning of Rust so far indicates Rust satisfies both: traits satisfies the `ops` problem for all traits you want to support the op, and Rust's implementations (impl) solves the problem of adding types. Of course, for each new {op,type} combination, one must write the code, but Rust allows you to do that with its trait and generic systems. Am I missing something important?
wavemode · 1h ago
When people talk about the "expression problem", what they're describing is the fact that, (in your example) if you add a new method to the trait, you have to go around and implement that new method on every type that implements the trait.
This is in contrast to if you had used an enum (sum type) instead, wherein adding a new operation is easy and can be done in a single place. But then in exchange, adding new variants requires going around and updating every existing pattern match to support the new variant.
TuringTest · 10m ago
I'm thinking, didn't inheritance and abstract methods work to solve the problem?
I know inheritance has its own severe problems, but adding a generic abstract method at the base class could create reusable code that can be accessed by any new class that inherits from it.
DarkSucker · 20m ago
Thanks. I wasn't thinking of enums. To the extent one designs a trait to use an enum type (or the enum to satisfy the trait), one wins. But it seems impossible to avoid code to handle all future {type, op} combinations. The nice thing I've seen with Rust is the ability to add to what's been done before without breaking what already works. I'm thinking of "orphan rules" here.
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!
Kranar · 2h ago
Nothing you mention is related to this article and neither Rust or C# solve the expression problem.
The expression problem is about being able to extend both data types (new cases) and operations (new functions) without modifying existing code while preserving static type safety.
C#'s extension methods can't be virtual, so you can't use them to actually add any new operations which can be dispatched on. They're just syntactic sugar for adding static methods which in non-OOP languages can be accomplished by declaring a free function.
Rust traits let you add new types (just impl the Trait), but it doesn't let you add new functions, so it doesn't do anything to solve the problem.
adastra22 · 1h ago
Traits have methods. How is that not adding new functions?
Kranar · 1h ago
Classes in C++ have methods too.
The problem is that you can't add new methods to an existing class.
kbolino · 1h ago
More specifically, you cannot add new abstract (aka "pure virtual") methods to an existing class/interface/trait when that class/interface/trait is already extended/implemented by code you don't control.
bitwize · 1h ago
Rust lets you combine multiple traits per type.
Kranar · 54m ago
C++ lets you inherit from multiple classes as well. I don't see how this has anything to do with being able to add new methods to existing types.
tomjakubowski · 38m ago
There is an important difference: in Rust you can write a new trait, with new methods, and impl that trait for a type without having to change the existing structs/enums which comprise that type at all. You can also do this (with some restrictions, "the orphan rule") for types defined in another library.
In C++ classes, you have to be able to modify a class definition to extend it with new methods (or a new ancestor to multiply inherit from).
justinpombrio · 1h ago
Rust's traits _do_ solve the expression problem.
Each data type is a `struct`. Each operation is a trait. You `impl` each trait on each struct.
This works even if you're using a library that has declared `struct A` and `struct B` and `trait F` and `trait G`, and you want to add both a `struct C` and a `trait H`, and fill out the whole 3x3 grid without modifying the library.
The library says:
struct A { ... }
struct B { ... }
trait F { ... }
impl F for A { ... }
impl F for B { ... }
trait G { ... }
impl G for A { ... }
impl G for B { ... }
fn some_function<T: F + G>(data: T) { ... }
Your code says:
use library::{A, B, F, G};
struct C { ... }
impl F for C { ... }
impl G for C { ... }
trait H { ... }
impl H for A { ... }
impl H for B { ... }
impl H for C { ... }
fn another_function<T: F + G + H>(data: T);
Now `library::some_function()` can be called with an A, B, or C, even though C was defined by the user of the library. And `another_function()` can be called with A, B, or C, even though A was defined by the library.
Kranar · 49m ago
While this has nothing to do with the expression problem, it's worth noting that in any case your solution does not work in general.
Rust does let you impl traits for types or traits that are inside of your crate, so your example strictly speaking works, but it does not let you impl traits if both the type and the trait are not inside of your crate. This is known as the orphan rule:
As the article points out, the expression problem itself is pretty simple to solve for code that you control, it's when writing modular software that can vary independently that gives rise to issues.
wavemode · 59m ago
That's not the expression problem. The expression problem is the question of, what is required to add new methods to an existing trait. In your example, it requires modifying the existing impls for all types implementing the trait.
What you've done is different, you've simply added a new trait entirely. That's not unique to Rust, you can add new interfaces in any language...
kbolino · 37m ago
There is something in Rust that can help, though. You can define multiple impls for different bounds.
Supposing we started off with a trait for expression nodes:
Now, this library has gone out into the wild and been implemented, so we can't add new methods to ExprNode (ignoring default implementations, which don't help solve the problem). However, we can define a new trait:
And now we get to what is (somewhat) unique to Rust: you can define different method sets based upon different generic bounds. Suppose we have a parent Expr struct which encapsulates the root node and the context:
Of course, this is a trivial example (and doesn't even require the intersection bound), but it does illustrate how the expression problem can be solved. The problem this strategy creates, though, is combinatorial explosion. When we just have two traits, it's not a big deal. When we have several traits, and useful operations start to require various combinations of them (other than just Original + New), the number of impls and test cases start to grow rapidly.
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.
In practice, Multiple Dispatch shines when you have 1) more than one argument type (duh) 2) higher order `O` operation [1]
[1]: think of a numerical routine that calls eigen or something, and you want eigen to exploit the matrix's type, such as symmetry or upper-triangular, and this is encoded as a matrix type)
[1]: https://craftinginterpreters.com/representing-code.html#the-...
I don't understand what problem the author is trying to solve here - maybe it's language specific? More related to dynamic typing and efficient dispatch?
In any case, operator overloading, while it can make for cute-to-read code, isn't really a good idea for code readability and maintenance.
so should we write `add_int_int(1,1)` and `add_int_double(1, 1.0)` and `add_double_double(1.0, 1.0)`?...
Applying arithmetic operators to non-arithmetic types starts to become a problem, even if some cases (set union/difference, string catenation) are natural...
The same goes for other operators... overloading '[]' indexing for maps as well as arrays seems natural, but would be highly confusing if you overloaded it for something unrelated to an index-like concept.
The expression problem only arises in statically typed programming languages, it does not exist in dynamically typed programming languages.
Operating overloading has nothing to do with the problem and can not be used to resolve it. Operators are nothing more than a one-off syntax so we can use familiar childhood notation like a + b, etc... they are not particularly meaningful. The ability to overload operators or functions in general is also irrelevant since such overloads are resolved statically at compile time.
Wadler's list of requirements for solving the expression problem include "with static checking that all cases are covered", so in one sense, yes, dynamic languages don't have this "problem". But in another sense, dynamic languages simply have no chance to solve the problem because they don't statically check anything.
It is true that it's much easier to do multiple dispatch and open-ended extension in dymamic languages. That's a nice benefit of them. But you do sacrifice all of the safety, code navigation, and performance of static types in order to get that.
The problem Wadler is trying to solve is "how can we have this sort of open-ended extension in both directions without giving up static safety?"
The "problem" exists for dynamically-typed languages as well. If you define a new class in Python, you still need to teach existing code how to operate on it (though you might be using inheritance to automatically derive some of those implementations, but inheritance obviously isn't limited to dynamic languages).
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).
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....
This is in contrast to if you had used an enum (sum type) instead, wherein adding a new operation is easy and can be done in a single place. But then in exchange, adding new variants requires going around and updating every existing pattern match to support the new variant.
I know inheritance has its own severe problems, but adding a generic abstract method at the base class could create reusable code that can be accessed by any new class that inherits from it.
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!
The expression problem is about being able to extend both data types (new cases) and operations (new functions) without modifying existing code while preserving static type safety.
C#'s extension methods can't be virtual, so you can't use them to actually add any new operations which can be dispatched on. They're just syntactic sugar for adding static methods which in non-OOP languages can be accomplished by declaring a free function.
Rust traits let you add new types (just impl the Trait), but it doesn't let you add new functions, so it doesn't do anything to solve the problem.
The problem is that you can't add new methods to an existing class.
In C++ classes, you have to be able to modify a class definition to extend it with new methods (or a new ancestor to multiply inherit from).
Each data type is a `struct`. Each operation is a trait. You `impl` each trait on each struct.
This works even if you're using a library that has declared `struct A` and `struct B` and `trait F` and `trait G`, and you want to add both a `struct C` and a `trait H`, and fill out the whole 3x3 grid without modifying the library.
The library says:
Your code says: Now `library::some_function()` can be called with an A, B, or C, even though C was defined by the user of the library. And `another_function()` can be called with A, B, or C, even though A was defined by the library.Rust does let you impl traits for types or traits that are inside of your crate, so your example strictly speaking works, but it does not let you impl traits if both the type and the trait are not inside of your crate. This is known as the orphan rule:
https://doc.rust-lang.org/reference/items/implementations.ht...
As the article points out, the expression problem itself is pretty simple to solve for code that you control, it's when writing modular software that can vary independently that gives rise to issues.
What you've done is different, you've simply added a new trait entirely. That's not unique to Rust, you can add new interfaces in any language...
Supposing we started off with a trait for expression nodes:
Now, this library has gone out into the wild and been implemented, so we can't add new methods to ExprNode (ignoring default implementations, which don't help solve the problem). However, we can define a new trait: And now we get to what is (somewhat) unique to Rust: you can define different method sets based upon different generic bounds. Suppose we have a parent Expr struct which encapsulates the root node and the context: We would probably already have this impl: Now we just need to add this impl: Of course, this is a trivial example (and doesn't even require the intersection bound), but it does illustrate how the expression problem can be solved. The problem this strategy creates, though, is combinatorial explosion. When we just have two traits, it's not a big deal. When we have several traits, and useful operations start to require various combinations of them (other than just Original + New), the number of impls and test cases start to grow rapidly.