Musings on Java Closures and Continuations
By nico on Sep 07, 2006
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: