4 ms·

The 'eval' pattern for interpreting simple languages

35 points by ingve 3y ago

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.
noelwelsh 3y ago
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. 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.html 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.
- Joker_vD 3y ago
  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.
- thatcks 3y ago
  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). (I'm the author of the linked-to article.)

35 points by ingve 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.

noelwelsh 3y ago

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

Joker_vD 3y ago
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.
thatcks 3y ago
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). (I'm the author of the linked-to article.)