Hacker News

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 3 days 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:

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 3 days ago [ - ]

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 3 days ago [ - ]

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

ceronman 3 days ago [ - ]

> 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 3 days 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:

  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.

ceronman 3 days ago [ - ]

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 3 days ago [ - ]

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.