> 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.
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.
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.
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!
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.
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.
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.)
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.
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.
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".
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.
The assumption it's a closed system that received no new content at runtime is a very functional programming-like assumption, but quite restrictive in most real long-lived systems.
That's not the assumption. The assumption is that the system does not receive new node-types at runtime.
Think of the JVM: you can load new bytecode (e.g. classes) at runtime, but you can't load bytecode that contains features of newer jvm versions that isn't compatible with the existing one.
I don't think this is a "functional programming-like assumption".
Yes, the name slipped from my mind, thank you for pointing that out!
With type classes however you mostly switch to the codata/protocol view, you can't pattern match on "the things that implement the type class" anymore and you have to rely on the methods provided by the type class.
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.
> 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.
As this comment said: 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.)
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.
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.
I think the general concept described here is great, but I feel the description is lacking a bit. I find the description is imprecise and suggests some things are hard that I don't think are difficult.
In the FP world this very very (very!) standard. A tree walking interpreter is one hop away from FP basics. The tools you need are tools that beginners learn in their first few weeks:
1. algebraic data types to represent the abstract syntax tree; and
2. structural recursion (usually implemented via pattern matching) to walk over the algebraic data type and interpret it.
Using generalized algebraic data types is a small extension if you don't want to box your result types (which addresses the comment "Python's duck typing definitely helps make your life simpler, because otherwise you need to be careful about designing what all the Eval()s return." in the OP.)
I don't understand why OP says conditionals or control flow are difficult. Those have been straightforward in the interpreters I have created.
Overall, I feel there are standard techniques for this kind of thing, in both the OO and FP worlds. In my experience the FP world is more precise with terminology, and I think this is beneficial.
The only truly difficult control flow to implement is unrestricted goto. Conditionals/loops/function invocations are trivial at best, slightly annoying (due to juggling the scopes/environments) at worst.
As far as I can see, generalized control flow complicates the situation because you need to propagate a variety of signalling results up the tree. Consider a for loop with a switch inside of it, inside of which is an if with a return; if you hit that return, you need to propagate 'return from the function with this result' out through the containing if, switch, and for loop, which means that the Eval() or equivalent for each of them probably all need to know about all of your early-return options (since a 'break' is different from a 'return', especially if you support multi-level breaks).
31 comments
[ 11.6 ms ] story [ 1248 ms ] threadOr 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.
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.
Somewhat interestingly the visitor pattern is even useful in languages that have sum types as it makes it easier to implement generic traversals!
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.
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... [2]: https://arxiv.org/abs/2211.13004
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.
> 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
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.
Think of the JVM: you can load new bytecode (e.g. classes) at runtime, but you can't load bytecode that contains features of newer jvm versions that isn't compatible with the existing one.
I don't think this is a "functional programming-like assumption".
I believe typeclasse in Haskell at least are lowered to an array of method, i.e. a vtable, and (single) dispatch happens at runtime.
With type classes however you mostly switch to the codata/protocol view, you can't pattern match on "the things that implement the type class" anymore and you have to rely on the methods provided by the type class.
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.
As this comment said: 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.)
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.
AST -eval-> Result
where AST is fixed and Result varies (depending on the choice of eval).
Then a coDSL is
AST -eval-> Result
where AST varies and Result is fixed ?
This feels like a restatement of the difference in modularity / extensibility.
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.
What is being described is a basic tree walking interpreter. If this is new to you, and you come from the OO world, there is an extended description in https://craftinginterpreters.com/a-tree-walk-interpreter.htm...
In the FP world this very very (very!) standard. A tree walking interpreter is one hop away from FP basics. The tools you need are tools that beginners learn in their first few weeks:
1. algebraic data types to represent the abstract syntax tree; and
2. structural recursion (usually implemented via pattern matching) to walk over the algebraic data type and interpret it.
Using generalized algebraic data types is a small extension if you don't want to box your result types (which addresses the comment "Python's duck typing definitely helps make your life simpler, because otherwise you need to be careful about designing what all the Eval()s return." in the OP.)
I don't understand why OP says conditionals or control flow are difficult. Those have been straightforward in the interpreters I have created.
Overall, I feel there are standard techniques for this kind of thing, in both the OO and FP worlds. In my experience the FP world is more precise with terminology, and I think this is beneficial.
(I'm the author of the linked-to article.)