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

[adastra22]

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.

[gf000]

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

[internet_points]

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