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:

~ by nico on September 7, 2006.

4 Responses to “Musings on Java Closures and Continuations”

  1. Wouldn’t continuations make a mess of try-finally?

  2. 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.

  3. 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.

  4. 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.

Leave a Reply to Nico Cancel reply

Your email address will not be published. Required fields are marked *