Open Recursion | Lambda the Ultimate (original) (raw)

I've been contemplating an embedded DSL. It strikes me how incredibly useful open recursion would be for what I want to achieve, to the point that I might want to give the technique some kind of explicit support and encouragement. Curious to see what had already been done, a quick google search turned up Closed and Open Recursion by Ralf Hinze.

Open recursion Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some langauges, this. The special behavior of self is that it is late-bound, allowing a method defined in one class to invoke another method that is defined later, in some subclass of the first.

I don't particularly like the examples being offered, but it's an interesting set of slides nonetheless. Of all the many features of objects, somehow I had failed to fully appreciate this aspect. I don't necessarily want to keep the recursion open until the last possible minute either; I would prefer to close up the recursion as I see fit, quite possibly at compile time. Is there any sensible and attractive way to re-open a recursion once it's been closed?

I was quite impressed with CTL Model Checking in Haskell: A Classic Algorithm Explained as Memoization on Kenn Knowles' blog. Seeing another good example of open recursion would require solving Project Euler Problem 220.