4 ms·

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 ve

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 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 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 1y 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.
- justinpombrio 1y 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.
  - wavemode 1y 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 1y 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.

Kranar 1y 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.

justinpombrio 1y 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.
- wavemode 1y 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 1y 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.