The 'eval' pattern for interpreting simple languages
utcc.utoronto.ca
utcc.utoronto.ca
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.)
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.
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
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.
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.
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 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!
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.