Home » forums » LtU Forum

Open Recursion

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.

By Leon P Smith at 2009-02-04 14:43 | LtU Forum | previous forum topic | next forum topic | other blogs | 16248 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Reopening recursion

The term "reopening" sounds unattractive - does it mean we declare the recursion to be closed and then later add a declaration that negates the previous one? It seems preferable to support framework (or theory or module) refinement where we can refine a framework with open recursion by either adding new cases or by closing the recursion. In refining a framework with closed recursion, we would not be allowed to add new cases - but we could arrange for the open framework to still be around under a different name.

By Matt M at Wed, 2009-02-04 15:29 | login or register to post comments

I tend to agree

That was more of a whimsical offhand question... but possibly an interesting one nonetheless. If nothing else, good insights into that would be of help to the human refactorer.

Such functionality isn't being seriously considered for anything I'd like to turn into reality at this point in time.

By Leon P Smith at Wed, 2009-02-04 15:58 | login or register to post comments

Following the OO thread...

You might want to look at virtual classes and family polymorphism. Given a combination of those features and some kind of mixin composition, you can get fairly fine-grained control. I suspect this is basically what Matt M means by framework refinement, but I'm not as familiar with that terminology, so I could be way off...

By Matt Hellige at Wed, 2009-02-04 16:33 | login or register to post comments

Similar idea

Family, module, typeclass, framework, concept, theory, namespace ... I've seen all of these used with significant differences but all essentially trying to capture the idea of parameterized mathematical structure. IMO probably the most important mechanism in a programming language.

By Matt M at Wed, 2009-02-04 17:36 | login or register to post comments

Objects

Well, I must admit, I largely stopped thinking about objects about 10 years ago. At the time, I was transitioning to functional programming, which I felt was a far superior choice.

There are interesting forms of open recursion that don't naturally fit the OO model, although the OO model seems to fit the DSL I'm contemplating rather well. So, I suppose I'll have to go back and revisit objects at some point. Thanks for the pointers!

By Leon P Smith at Sun, 2009-02-15 16:45 | login or register to post comments

Risky?

I was under the possibly mistaken impression that open recursion can lead to trouble (and has).

By raould at Thu, 2009-02-05 00:55 | login or register to post comments

Can and has

Seems like a fair characterization. In fact it looks to me like the example cases mentioned in the paper you (indirectly) linked to would be better solved with pure interfaces and message forwarding.

But e.g. the most direct encoding of a solution to the expression problem is with an open recursive datatype. I think a good litmus test is: is the recursion naturally part of my problem or just part of some OOP apparatus?

By Matt M at Thu, 2009-02-05 01:46 | login or register to post comments

What hasn't lead to trouble?

I tend to agree; I prefer closed recursion in most instances, and it took me a long time to appreciate the true value of open recursion. I'd say my threshold for using it is set pretty high. I'm only really interested in the disciplined usage of open recursion, and not using it for the sake of itself, or because it's "dynamic."

I suspect that due to the nature of the DSL I'm contemplating, open recursion won't often lead to trouble. I also suspect that the "fragile base class" problem either won't manifest itself, or won't be a problem in practice, again due to the particulars of the problem.

In some sense, open recursion might be breaking an abstraction, but on the other hand, it can be such a compelling way to do so. :-)

By Leon P Smith at Sun, 2009-02-15 16:53 | login or register to post comments

TAPL has a nice discussion

TAPL has a nice discussion of open recursion and the risks associated with it.

By Ehud Lamm at Thu, 2009-02-05 06:47 | login or register to post comments