What Is "Open Recursion"? (2013)
44 points by andsoitis 4 days ago | 9 comments
  • Akronymus 2 days ago |
    Am I understanding it correctly that those lambda functions are lexically bound rather than creating closures, in the "Open" section?
  • glhaynes 2 days ago |
    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.
    • jerf 2 days ago |
      It's one of those things that's hard to get for most of us not because we don't understand what it is, but that we don't understand what not having it is like. Most languages in common use have this.

      It can be similarly difficult to explain to people what structured programming is, because basically everything is structured programming now. The hard part is understanding what non-structured programming is, so that you can then understand the contrasts, because there is so little experience with it anymore.

  • kazinator 2 days ago |
    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.

  • chubot 2 days ago |
    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 ...

    • chubot 2 days ago |
      Also, I’m not 100% sure, but maybe Standard ML doesn’t support the open recursion pattern, but say OCaml does (?). So it could be a relevant distinction in that respect
    • 1718627440 2 days ago |
      > the only language I use that doesn't have such late binding/dynamic dispatch is C

      It's not that it doesn't support this, it is just explicit.

  • skybrian 2 days ago |
    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.)
  • agumonkey 2 days ago |
    Reminds me of tricks about implementing `letrec` in Lisp in small pieces.