Musings on Java Closures and Continuations

I see lots of posts on closures and continuations (more, and more) lately, many relating to Java. See also lambda-the-ultimate.org.

Must I re-hash what these are? No, not really.

Now, I do find the evolution of Java here interesting.

There is a proposal to add closures to Java.

And these closures will support non-local exits to lexical exit points of dynamic extent! Which means that, Java being a safe language, runtime exceptions have to result from attempting a non-local exit that is no longer in scope. How would one implement this? My guess: write a magic value to a hidden variable closed by all closures that close a given exit label prior to exiting the scope of each label closed by the closure. But if Java had continuations then non-local exits from closures could be made to have indefinite extent: closures that close labels implicitly grab the associated continuations.

But no continuations for Java. At least not in that proposal.

Why not? Given Java as it stands today it should be easy enough (ha! something a non-expert like me would say) to compile Scheme to Java, just as Scheme can be compiled to C, just don't expect to be able to read the result, and don't expect efficiency. One way would be to create closures out of objects -- but functional application then wouldn't be the same for Scheme-compiled-to-Java as for plain Java -- then perform CPS conversion on Scheme code, reify continuations, get "rid" of the Java stack (each Scheme functional application would return a continuation to a Java function whose job is to do a call-receive-continuation-call-continuation-... loop). This would be wasteful as the Java stack and associated machinery (think of stack and frame pointers in C) continue to exist and be used but not for anything useful. And such continuations could not capture native Java continuations, only Scheme ones.

Given native Java support for closures this gets easier -- now there'd be only the CPS conversion and the getting-rid-of-the-stack bit to do.

Given that this can be done, and given that the JVM has much better control over its stack than C, why not just implement continuations in Java? One way would be to use stack copying, another would be to put all the function call frames on the heap -- these being the canonical methods of implementing call/cc. With stack copying the impact on Java apps that don't use continuations should be near (but probably not quite) zero, whereas putting call frames on the heap makes the cost of grabbing and calling continuations near zero. Stack copying burdens users of continuations with most of the runtime cost of continuations, whereas putting call frames on the heap relies more on the garbage collector, thus more evenly spreading the cost of making continuations available across all users (though I suspect optimizations to lighten the burden on call stacks where continuations are not grabbed are possible).

It is said that LISP programmers know the value of everything and the cost of nothing.

What's the benefit of having native support for continuations? First, it would make the job of a Scheme- or Ruby-on-Java implementor a lot easier. Second, it would improve the performance of such implementations. Third, native continuations would have the ability to capture the state of a native Java call stack (via a closure passed to some Java API that takes closures as arguments and calls them or passes them to other APIs that might call them).

And the cost? There's the cost of specifying continuations for Java, implementing them (see above), and the runtime cost of making continuations available (see above). Also there is the possibility that native continuations that capture native Java state may represent a subtle but non-trivial change to the language, particularly if there are existing APIs that could be passed closures that can capture continuations to be used and re-used later. It might be easier to deal with such subtle changes if closures and continuations were introduced at the same time.

My stab at answering my question, then: native Java support for continuations would, at best, likely have some non-zero, negative impact on the performance of existing Java applications, but few users would reap the benefits of continuations, thus continuations aren't worth it. Such an answer, of course, ignores the things that native Java users could, and probably would, do with native continuations, including building all manner of backtracking algorithms, light-weight multi-threading for event driven applications, etc... I don't really know how to judge the cost/value of native continuations, and I have nothing to do with any of these efforts -- I am a lurker -- so take all this with at least some salt, or perhaps lots of salt.

Aside: here's a few useful books that I'd recommend:

Comments:

Wouldn't continuations make a mess of try-finally?

Posted by Tom Hawtin on September 08, 2006 at 05:22 AM CDT #

Because you could not detect when the current continuation is abandoned? Or is that true? The GC could throw some runtime exception to continuations it reaps that have never been called. Or because of the ability to call continuations multiple times? That would definitely be a change, and I mentioned this. I just don't know how serious a change that would be.

Posted by Nico on September 08, 2006 at 11:34 AM CDT #

One might deal with continuations that can be called multiple times by allowing one to declare that this is OK for a particular function (default to "no") and then detect when a given activation frame is entered more than once through continuation invocation and then throw a runtime exception. This would limit the usefulness of continuations a bit, but I think not so much.

Posted by Nico on September 08, 2006 at 11:38 AM CDT #

http://people.csail.mit.edu/gregs/ll1-discuss-archive-html/msg01383.html deals with this. Basically, I think finally blocks can be handled by having the GC throw an exception at abandoned continuations, and arrange for second, third, nth calls to any continuation to throw another exception. This would guarantee that finally blocks are always executed (unless the process dies, or otherwise exits) and no more than once (unless the continuation reentrance exception is caught, which, presumably, Scheme-in-Java would catch). There is no guarantee about the timeliness of the execution of finally clauses.

Posted by Nico on September 13, 2006 at 07:30 AM CDT #

Post a Comment:
Comments are closed for this entry.
About

I'm an engineer at Oracle (erstwhile Sun), where I've been since 2002, working on Sun_SSH, Solaris Kerberos, Active Directory interoperability, Lustre, and misc. other things.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today