What Is "Open Recursion"? (2013)

I wasn't really familiar with this term, but as another comment here said, the only language I use that doesn't have such late binding/dynamic dispatch is C

i.e. it seems natural in Python and C++ (and Java and Rust …)

But I did notice the term "open recursion" in Siek's Essentials of Compilation - https://mitpress.mit.edu/9780262048248/essentials-of-compila...

To make our interpreters extensible we need something called "open recursion", in which the tying of the recursive knot is delayed until the functions are composed. Objected-oriented languages provide open recursion via method overriding

---

I mentioned that here too, on a thread about a type checker: https://news.ycombinator.com/item?id=45151620

To me the open recursion style clearly seems like a better default than VISITORS?

You can still REUSE traversal logic, and you don't "lose the stack", as I pointed out in the comment below: https://news.ycombinator.com/item?id=45160402

Am I missing something? I noticed there is a significant disagreement about style, which seems to not have a clear rationale: MyPy uses visitors all over, while TypeScript uses switch statements

This is a big difference! It affects nearly every line of code, and these projects have a ton of code ...

This was really helpful and easy to follow. I came across this term the other day in that article that was going around about defining OOP and was a little baffled and thought "uh, I'll come back to this", but this gave me the perspective I needed to get it.

For an example of a language feature that looks kind of like standard object-oriented inheritance, but isn’t, check out “struct embedding” in Go. Struct embedding gives you the syntax of inheritance and you can even override methods, but for internal self-calls, methods don’t get overridden. (If you wanted to allow that, you’d need to add function pointers or an interface to the struct.)

Example of open recursion: add a new object type into a low-level language run time.

You implement a garbage traversal routine for it, which recurses over traversing the child objects.

The system is open to extension; the garbage collector doesn't just have a switch statement to handle all the known objects. It may have that too, but for some object kinds, it dispatches their method.

Reminds me of tricks about implementing `letrec` in Lisp in small pieces.

Am I understanding it correctly that those lambda functions are lexically bound rather than creating closures, in the "Open" section?