3 ms·

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 havin

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
- deredede 3y ago
  This is somewhat glossing over the fact that you can only do this mechanical translation if you have access to the whole program, and the two approaches have drastically different implications for modularity. With the "data"/sum types approach, new analyses or transformations on the program can be added in another module, but new nodes can't be. With the "codata"/protocol approach, new analyses can't be added (you are limited to those encoded in the protocol), but new nodes can easily be added in a separate module where you implement the protocol for them.
  - valenterry 3y ago
    What you are refering to is known as the expression problem. > With the "data"/sum types approach, new analyses or transformations on the program can be added in another module, but new nodes can't be. That's not true at all. Typeclasses solve this exact problem very elegantly in (P)FP languages. In other languages there are sometimes similar solutions (such as object algebras[1] in Java) but it is more tricky and usually less orgonomic or impossible to do while keeping things typesafe. [1] https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf
    - 3cats-in-a-coat 3y ago
      Typeclasses dispatch is static. You can use a typeclass implementation as a proxy for holding a dynamically injected implementation you call through the typeclass implementation, but that's a hack, not exactly "elegant".
      - valenterry 3y ago
        I don't think that matters in this case. The list of node-types is static in the context of the execution of the program so there is no need for nodes of the same types to have different behaviour, apart from the data/configuration that they store. The point in question was what happens if new node-types come in (e.g. through a plugin that extends the language). But in this case the number of node-types is still static and the new functionality can therefore be adapted using type-classes.
- 3cats-in-a-coat 3y ago
  I didn't describe a mental model difference, but an actual factual difference in how it works. You can't add more types to a sum type, without modifying the sum type, which is a deal breaker for this use.
  - js8 3y ago
    > You can't add more types to a sum type, without modifying the sum type, which is a deal breaker for this use. Honestly, why is it a deal breaker? We are talking about a small DSL with a handful of primitives in the sum type. I am asking because I have seen people advocate against if/case/pattern matching (FP) in favor of overloading (OOP) approach, without any consideration of the readability and simplicity of the former. I would understand that if you need to extend a sum type across module boundary, for example give this ability to a user of a library, then the latter approach makes sense (although in FP, this can be also done with typeclasses). But I don't really see the need here.
    - noelwelsh 3y ago
      I agree. As this comment said: https://news.ycombinator.com/item?id=36858774 https://news.ycombinator.com/item?id=36858774 and I glossed over in "two different ways that have different tradeoffs", the data vs codata approach gives you orthogonal extensibility. (Note the original article didn't talk about extensibility at all.) In a DSL context you usually want new transformations (debuggers, pretty printers, etc.) on a fixed language. For this the FP / data approach is ideal. In some cases you want fixed transformations on an extensible language. An example is a visualization DSL. There are limitless visualizations but the operation you want to use on them is always the same: draw it. For this the OOP / codata approach is ideal. So choose the implementation technique that best suits your problem domain (and your implementation language.)
      - js8 3y ago
        > An example is a visualization DSL. Interesting. I would say, this is not a DSL, but rather co-DSL. I can't really provide a formal definition right now, but I feel like primitives of DSL compose in the input of the evaluation function, while the primitives of co-DSL compose in the output of the evaluation function. In both cases, the evaluation function is fixed by the DSL's implementation. That's why DSL has a syntax tree (on input), but co-DSL has a tree of output widgets.

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
deredede 3y ago
This is somewhat glossing over the fact that you can only do this mechanical translation if you have access to the whole program, and the two approaches have drastically different implications for modularity. With the "data"/sum types approach, new analyses or transformations on the program can be added in another module, but new nodes can't be. With the "codata"/protocol approach, new analyses can't be added (you are limited to those encoded in the protocol), but new nodes can easily be added in a separate module where you implement the protocol for them.
- valenterry 3y ago
  What you are refering to is known as the expression problem. > With the "data"/sum types approach, new analyses or transformations on the program can be added in another module, but new nodes can't be. That's not true at all. Typeclasses solve this exact problem very elegantly in (P)FP languages. In other languages there are sometimes similar solutions (such as object algebras[1] in Java) but it is more tricky and usually less orgonomic or impossible to do while keeping things typesafe. [1] https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf
  - 3cats-in-a-coat 3y ago
    Typeclasses dispatch is static. You can use a typeclass implementation as a proxy for holding a dynamically injected implementation you call through the typeclass implementation, but that's a hack, not exactly "elegant".
    - valenterry 3y ago
      I don't think that matters in this case. The list of node-types is static in the context of the execution of the program so there is no need for nodes of the same types to have different behaviour, apart from the data/configuration that they store. The point in question was what happens if new node-types come in (e.g. through a plugin that extends the language). But in this case the number of node-types is still static and the new functionality can therefore be adapted using type-classes.
3cats-in-a-coat 3y ago
I didn't describe a mental model difference, but an actual factual difference in how it works. You can't add more types to a sum type, without modifying the sum type, which is a deal breaker for this use.
- js8 3y ago
  > You can't add more types to a sum type, without modifying the sum type, which is a deal breaker for this use. Honestly, why is it a deal breaker? We are talking about a small DSL with a handful of primitives in the sum type. I am asking because I have seen people advocate against if/case/pattern matching (FP) in favor of overloading (OOP) approach, without any consideration of the readability and simplicity of the former. I would understand that if you need to extend a sum type across module boundary, for example give this ability to a user of a library, then the latter approach makes sense (although in FP, this can be also done with typeclasses). But I don't really see the need here.
  - noelwelsh 3y ago
    I agree. As this comment said: https://news.ycombinator.com/item?id=36858774 https://news.ycombinator.com/item?id=36858774 and I glossed over in "two different ways that have different tradeoffs", the data vs codata approach gives you orthogonal extensibility. (Note the original article didn't talk about extensibility at all.) In a DSL context you usually want new transformations (debuggers, pretty printers, etc.) on a fixed language. For this the FP / data approach is ideal. In some cases you want fixed transformations on an extensible language. An example is a visualization DSL. There are limitless visualizations but the operation you want to use on them is always the same: draw it. For this the OOP / codata approach is ideal. So choose the implementation technique that best suits your problem domain (and your implementation language.)
    - js8 3y ago
      > An example is a visualization DSL. Interesting. I would say, this is not a DSL, but rather co-DSL. I can't really provide a formal definition right now, but I feel like primitives of DSL compose in the input of the evaluation function, while the primitives of co-DSL compose in the output of the evaluation function. In both cases, the evaluation function is fixed by the DSL's implementation. That's why DSL has a syntax tree (on input), but co-DSL has a tree of output widgets.