The Expression Problem and its solutions (2016)

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.

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

You've got T types (some new), and O operators (some new) and want to implement all operators for all types ... This is the exact definition of operator overloading.

There is no magic (other than inheritance or generics, if applicable) that will remove the need to individually implement all those O x T cases, and while that is obviously necessary, it is also all that you need to do.

If you are not talking about operator overloading - supporting the same operator for multiple different custom types, then what are you talking about ?!

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

    struct Constant { value: i32 }
    struct BinaryPlus { lhs: i32, rhs: i32 }
    
    trait Evaluate {
        fn evaluate(&self) -> i32;
    }
    
    impl Evaluate for Constant {
        fn evaluate(&self) -> i32 { self.value }
    }
    
    impl Evaluate for BinaryPlus {
        fn evaluate(&self) -> i32 { self.lhs + self.rhs }
    }
    
    // Adding a new operation is easy. Let's add stringify:
    
    trait Stringify {
        fn stringify(&self) -> String;
    }
    
    impl Stringify for Constant {
        fn stringify(&self) -> String { format!("{}", self.value) }
    }
    
    impl Stringify for BinaryPlus {
        fn stringify(&self) -> String { format!("{} + {}", self.lhs, self.rhs) }
    }
    
    // How about adding new types? Suppose we want to add FunctionCall
    
    struct FunctionCall { name: String, arguments: Vec<i32> }
    
    impl Evaluate for FunctionCall {
        fn evaluate(&self) -> i32 { todo!() }
    }
    
    impl Stringify for FunctionCall {
        fn stringify(&self) -> String { todo!() }
    }

The problem is that you can't add new methods to an existing class.

If you add a method to a trait, every implementation of that trait has to be modified in the original source code. The point of the expression problem is that you want to be able to add new operations in a way that is type safe and checked for completeness, even if you don't have access to the original source code.

Rust can probably do this, because its traits are equivalent to Haskell type classes and those have a solution to the expression problem, but it's not trivial. See the link in the article.