3 ms·

> Doing this requires or at least wants some form of polymorphic methods or functions, since you want to be able to call a node's Eval() without having to know

by kccqzy 3y ago

> Doing this requires or at least wants some form of polymorphic methods or functions, since you want to be able to call a node's Eval() without having to know anything about the node. Or you know, just use sum types. A polymorphic method as meant here is really not much different from the case analysis of a sum type.

apgwoz 3y ago
If only all languages had sum types …
- contravariant 3y ago
  You can make one in most languages with polymorphic types. I mean the sum type A+B is by definition just a type with maps A => A+B, B => A+B and for each two functions A => X and B => X a function A+B => X compatible with both maps. Even if the language doesn't support it it's easy enough to make one. Syntax is nicer with language support though.
  - apgwoz 3y ago
    We went in a circle. The article does this. The parent comment says “use sum types.” I said “most languages don’t have direct support” and now you’re repeating the article.
    - contravariant 3y ago
      Best I can tell the article does something else, though the notion that you can just implement the language features you lack is the same.
      - apgwoz 3y ago
        You can definitely implement language features poorly and in hard to maintain, “against the grain” ways in most languages. Lots of languages support multiple ways, sometimes, of doing so!
  - deredede 3y ago
    Implementing sum types in a language that doesn't support them is so common that it has a name: the visitor pattern. Somewhat interestingly the visitor pattern is even useful in languages that have sum types as it makes it easier to implement generic traversals!
    - contravariant 3y ago
      I wish having a polymorphic return value was more standard though. It always feels iffy to make a visitor that needs to keep an internal state in order to return anything.
3cats-in-a-coat 3y ago
If it's not much different why do you need to say "just use sum types"? The distinction is that a sum type is an enumeration of types. Therefore "without having to know anything about the node" is not met as a requirement, with sum types you do know the type of the node ("one of: a, b, c, d"). Polymorphism allows an abstract relationship where you say "I support protocol: a" and then any type/class can implement that protocol without prior knowledge of the implementation.
- noelwelsh 3y ago
  Sum types + pattern matching (algebraic data types + structural recursion) achieves the same goal as what the author describes, but uses a different implementation technique. In functional programming there is often talk of "duality". Two things are dual if you can make an exact correspondence between them. In this case, these two implementation techniques are duals. The OO technique is known as "codata", which, as you say, is all about having a uniform protocol to interact with. (In this case, the method "eval".) The FP technique is just "data", which is basically interchangeable with sum types or algebraic data types. (There are minor differences in meaning that are unimportant here.) We use recursion on data, and "corecursion" on codata. There is more in the papers "Codata in Action" [1] and "Data-Codata Symmetry" [2]. What this duality means is that you can have one mental model of what you are trying to achieve, and implement it in two different ways that have different tradeoffs. Since these two different implementations are duals you can mechanically (i.e. with a program) translate between the two. I find this a really powerful way to approach design. (This post is just a sketch of the ideas and, unfortunately, probably not comprehensible unless you have a pretty good grounding in programming language theory. Explaining them properly would take more space and time than I have right now.) [1]: https://www.microsoft.com/en-us/research/uploads/prod/202/01/CoDataInAction.pdf https://www.microsoft.com/en-us/research/uploads/prod/202/01... [2]: https://arxiv.org/abs/2211.13004 https://arxiv.org/abs/2211.13004
  - asplake 3y ago
    See also the Expression problem https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem
captainmuon 3y ago
I think what the author is hinting at is that you don't want to write a big `if` statement every time you use a node. I would include sum types in what they meant with polymorphism here, because as you say there is no big practical difference between using an `IExpression` interface, or an `Expression = Sum | Product | ...` sum type for the nodes.

by kccqzy 3y ago

apgwoz 3y ago

If only all languages had sum types …

contravariant 3y ago
You can make one in most languages with polymorphic types. I mean the sum type A+B is by definition just a type with maps A => A+B, B => A+B and for each two functions A => X and B => X a function A+B => X compatible with both maps. Even if the language doesn't support it it's easy enough to make one. Syntax is nicer with language support though.
- apgwoz 3y ago
  We went in a circle. The article does this. The parent comment says “use sum types.” I said “most languages don’t have direct support” and now you’re repeating the article.
  - contravariant 3y ago
    Best I can tell the article does something else, though the notion that you can just implement the language features you lack is the same.
    - apgwoz 3y ago
      You can definitely implement language features poorly and in hard to maintain, “against the grain” ways in most languages. Lots of languages support multiple ways, sometimes, of doing so!
- deredede 3y ago
  Implementing sum types in a language that doesn't support them is so common that it has a name: the visitor pattern. Somewhat interestingly the visitor pattern is even useful in languages that have sum types as it makes it easier to implement generic traversals!
  - contravariant 3y ago
    I wish having a polymorphic return value was more standard though. It always feels iffy to make a visitor that needs to keep an internal state in order to return anything.

3cats-in-a-coat 3y ago

If it's not much different why do you need to say "just use sum types"? The distinction is that a sum type is an enumeration of types. Therefore "without having to know anything about the node" is not met as a requirement, with sum types you do know the type of the node ("one of: a, b, c, d"). Polymorphism allows an abstract relationship where you say "I support protocol: a" and then any type/class can implement that protocol without prior knowledge of the implementation.

noelwelsh 3y ago
Sum types + pattern matching (algebraic data types + structural recursion) achieves the same goal as what the author describes, but uses a different implementation technique. In functional programming there is often talk of "duality". Two things are dual if you can make an exact correspondence between them. In this case, these two implementation techniques are duals. The OO technique is known as "codata", which, as you say, is all about having a uniform protocol to interact with. (In this case, the method "eval".) The FP technique is just "data", which is basically interchangeable with sum types or algebraic data types. (There are minor differences in meaning that are unimportant here.) We use recursion on data, and "corecursion" on codata. There is more in the papers "Codata in Action" [1] and "Data-Codata Symmetry" [2]. What this duality means is that you can have one mental model of what you are trying to achieve, and implement it in two different ways that have different tradeoffs. Since these two different implementations are duals you can mechanically (i.e. with a program) translate between the two. I find this a really powerful way to approach design. (This post is just a sketch of the ideas and, unfortunately, probably not comprehensible unless you have a pretty good grounding in programming language theory. Explaining them properly would take more space and time than I have right now.) [1]: https://www.microsoft.com/en-us/research/uploads/prod/202/01/CoDataInAction.pdf https://www.microsoft.com/en-us/research/uploads/prod/202/01... [2]: https://arxiv.org/abs/2211.13004 https://arxiv.org/abs/2211.13004
- asplake 3y ago
  See also the Expression problem https://en.wikipedia.org/wiki/Expression_problem https://en.wikipedia.org/wiki/Expression_problem

captainmuon 3y ago

I think what the author is hinting at is that you don't want to write a big `if` statement every time you use a node. I would include sum types in what they meant with polymorphism here, because as you say there is no big practical difference between using an `IExpression` interface, or an `Expression = Sum | Product | ...` sum type for the nodes.