[Kranar]

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.

[justinpombrio]

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.

[ceronman]

I don't know why you're getting down voted. But you are right. Rust type system solves this in a very nice way. Maybe to clarify we can show how to do the exact same example shown with Clojure multi-methods, but in Rust:

    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!() }
    }

[mrkeen]

The only thing missing here is separation of files.

Assuming the whole Stringify section goes into a new file (likewise with FunctionCall) then I agree that this solves the expression problem.

[Kranar]

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:

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.

[ceronman]

Why would the the orphan rule be a problem here?

The orphan rule only disallow impls if both the trait and the type are defined outside the crate.

But in this example if you are adding a new type (struct) or a new operation (trait), well this new item should be in your crate, so all the impls that follow are allowed.

[Kranar]

It's not a problem here as it has nothing to do with this to begin with. I am pointing out a limitation in a feature that the author has presented, but that feature does not resolve anything about the topic being discussed.

The goal isn't to allow a new type to work for an existing implementation of a function nor is it to take an existing type and write a new function that works with it. In the proposed solution you have `some_function` and the author claims that this solves the expression problem because you can take a new type C and pass it into some_function. Pretty much every language has a way to define new types and pass them into existing functions.

The goal is to allow for that new type, C, to have its own implementation of `some_function` that is particular to C, as well as the ability to write new functions that can be specialized for existing types. In particular we want calls to `some_function` through an interface to call C's specific implementation when the runtime type of an object resolves to C, and calls whatever other implementations exist when called through another interface.

The author's solution doesn't do that, it literally does nothing that you can't do in pretty much any other language.

[wavemode]

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

[ceronman]

> That's not the expression problem.

To me it looks like this is exactly the expression problem. The expression problem is not about adding methods to a trait, it's about adding an operation to a set of types. In this case every operation is defined by a single trait.

The idea behind the expression problem is to be able to define either a new operation or a new type in such a way that the code is nicely together. Rust trait system accomplish this beautifully.

> That's not unique to Rust, you can add new interfaces in any language...

Many languages have interfaces, but most of them don't allow you to implement them for an arbitrary type that you have not defined. For example, in Java, if you create an interface called `PrettyPrintable`, but you can't implement it for the `ArrayList` type from the standard library. In Rust you can do this kind of things.

[kbolino]

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:

  pub trait ExprNode { fn eval(&self, ctx: &Context) -> Value; }

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:

  pub trait CanValidate { fn validate(&self) -> Result<(), ValidationError>; }

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:

  pub struct Expr<N> { root: N, ctx: Context }

We would probably already have this impl:

  impl<N: ExprNode> Expr<N> {
    pub fn eval(&self) -> Value { self.root.eval(&self.ctx) }
  }

Now we just need to add this impl:

  impl<N: CanValidate + ExprNode> Expr<N> {
    pub fn validate(&self) -> Result<(), ValidationError> { self.root.validate() }
  }

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 starts to grow rapidly.

[adastra22]

Traits have methods. How is that not adding new functions?

[naasking]

> Traits have methods. How is that not adding new functions?

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.

[adastra22]

In rust you would add a NEW trait, which is brought in scope by those who need it. Or add a new method to an existing trait, with a default implementation.

The problem you describe makes no sense. It sounds like, for example, wanting to add a new variant to an enum while also not wanting to modify match statements which now fail exhaustive testing. That’s a direct contradiction.

The only sensible charitable interpretation I can come up with is that you want to add new methods to a type without having to update any existing type definitions. This is what traits do.

[naasking]

> In rust you would add a NEW trait, which is brought in scope by those who need it.

No, that's not sufficient if done naively as I think you're describing. You seem to be missing the context of this discussion as described by the article. Other code already depends on the current compiled abstraction, and you want to extend it in various ways, safely, so that existing code continues to work without recompilation, but you can extend the abstraction that code is already safely handling with new types and new operations without modifying the original source code.

If you want to add a new node type to an AST, with algebraic data types you would have to modify the original source code of the original functions that match on those types, so types are closed to extension. You can leave the type open to extension via traits, but now the operations are closed to extension without modifying the original source code.

> It sounds like, for example, wanting to add a new variant to an enum while also not wanting to modify match statements which now fail exhaustive testing. That’s a direct contradiction.

No it's not, if enums and match statements were safely open to extension rather than closed. That's exactly what would solve the expression problem. This can and has been done [1] as the article described, via multimethods or via lifting data constructors to the type class level. It's obtuse and awkward, but in theory it doesn't have to be.

The ultimate goal is that the new type and/or pattern matching cases have to be provided together to cover all of missing combinations, but importantly "together" means by the time the final program is assembled and not in the source code that defined the original types or operations.

[1] open pattern matching and open algebraic data types have also been done in research languages

[adastra22]

> No, that's not sufficient if done naively as I think you're describing. You seem to be missing the context of this discussion as described by the article. Other code already depends on the current compiled abstraction, and you want to extend it in various ways, safely, so that existing code continues to work without recompilation, but you can extend the abstraction that code is already safely handling with new types and new operations without modifying the original source code.

That is exactly what a new trait would accomplish. I remain confused as to the distinction you are making.

[naasking]

Read the Haskell-specific follow-up which I mentioned, type classes have a correspondance with traits so the problems with this approach are the same:

https://eli.thegreenplace.net/2018/more-thoughts-on-the-expr...

[Kranar]

Classes in C++ have methods too.

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

[kbolino]

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]

Rust lets you combine multiple traits per type.

[Kranar]

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]

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

[adastra22]

You can add traits (with their methods) to existing types, without modification.

[bitwize]

C++ classes are types. Rust traits are applied to types.

[Kranar]

And what exactly do you think traits apply to types exactly?

If your answer doesn't start with an "m" and end with a "ethod", then you may need to re-read the Rust book found here:

https://doc.rust-lang.org/book/ch10-02-traits.html

[mrkeen]

So hypothetically, if you could add new methods to an existing class, it would solve the problem?

[Kranar]

New virtual methods, yes.