Hacker News

jauntywundrkind 3 days ago [ - ]

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

3 days ago [ - ]

[deleted]

adastra22 3 days ago [ - ]

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

naasking 3 days ago [ - ]

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

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

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

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

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

adastra22 3 days ago [ - ]

Unfortunately I don’t speak Haskell. As none of the terminology used by Haskell folks align with languages I do know, I really can’t make head or tails of that article.

internet_points 3 days ago [ - ]

There's data definitions:

    data Constant           = Constant Double deriving (Show)

is a bit like `#[derive(Debug)] struct Constant(f64);`, ie. it's just a wrapper around a double and you can print it.

And there's typeclasses. Show is a typeclass. You can think of them as interfaces, so `instance Sqlite DB where open dsn = ...` is a bit like saying Sqlite is an implementation (instance) of the DB interface (typeclass). The typeclass itself could be defined like `class DB where open :: String -> IO ()` meaning the interface requires a function taking a string and having IO access (and of course you can require more than one function in your interface/typeclass).

The article also uses typeclasses with parameters. Parameters (and functions and variables) are written lowercase, while classes and constructors and such are capitalized, so

    class (Expr e) => Stringify e where
      stringify :: e -> String

    instance Stringify Constant where
      stringify (Constant x) = show x

means there's an interface Stringify that's parametrized over some type e (and that e in turn has to be in the Expr typeclass).

adastra22 3 days ago [ - ]

Thank you. Now I understand the article. And the problem identified for type classes isn’t an issue in Rust. You’d return a ‘dyn Trait’ and be done. It means the object would have to be heap allocated, but that is already a given because you are wanting to define a function that can work with any type including future defined types. I guess Haskell doesn’t support the equivalent of trait objects for type classes?

I’m not trying to prove that rust is better or something. People who do that are annoying. It’s just weird to me that this is being presented as a fundamental and largely unsolved challenge when there is a simple solution at the heart of a widely deployed and well known language, which in turn stole it from elsewhere.

naasking 2 days ago [ - ]

dyn traits have quite a few restrictions if I'm reading the docs right. Like, dispatchable functions can't even have type parameters [1]. I wouldn't exactly call that "solved", although maybe a language with traits and dyn traits that used GC wouldn't have such onerous restrictions.

[1] https://doc.rust-lang.org/reference/items/traits.html#dyn-co...

gf000 3 days ago [ - ]

I tried to translate the article to Rust, but seems that the article's gotcha in Haskell is not necessarily an issue in Rust if we return `dyn OurTrait`, so now I'm even more confused. If anyone could take a look what I'm missing that would be welcome:

------------

Say, you want to write a simple language interpreter.

You have an `Expr` enum (sum type), with say, a `Constant(f64)` and a `BinaryPlus(Expression, Expression)`.

You can easily add a new function expecting an `Expr` indeed, but if you were to add a new variant to the `Expr` enum, you would have to go through the code and change every use site.

You can solve the issue by simply making a `struct Constant` and a `struct BinaryPlus`. Now you can just define a new trait for both of them, and you can use that `dyn trait` in your code -- you can add new functions and also new types without code change at use site!

So what's the issue?

In Haskell, a logic like

```

func example(runtime_val: f64) -> Expr {

  if (runtime_val is someRuntimeCheck())
    return Constant(..)

  else
    return BinaryPlus(.., ..)

}

```

can't compile in itself as `Expr` is a type class (=trait). Basically, in this mode Haskell awaits a concrete implementation (we actually get the exact same behavior with `impl Expr` in Rust), but here is my confusion: this can be circumvented in Rust with dyn traits..

Here is my (very ugly due to just hacking something together while pleasing the borrow checker) code showing it in Rust: https://play.rust-lang.org/?version=stable&mode=debug&editio...

adastra22 3 days ago [ - ]

Your confusion is my confusion: Rust supports this.

Kranar 3 days ago [ - ]

Classes in C++ have methods too.

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

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

mrkeen 3 days ago [ - ]

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

Kranar 2 days ago [ - ]

New virtual methods, yes.

bitwize 3 days ago [ - ]

Rust lets you combine multiple traits per type.

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

adastra22 3 days ago [ - ]

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

bitwize 3 days ago [ - ]

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

Kranar 3 days ago [ - ]

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