Multiprompt delimited continuations

Fri Sep 7 14:33:56 UTC 2018

Hey Ron,

thanks for your fast response.

Regarding recursion: While I couldn't immediately apply your trampolining trick,
your answer prompted me to look into it again and I found a potential solution
that works well for one-shot continuations. Maybe it is interesting for you:

https://gist.github.com/b-studios/65e9e614f006d2125659267f6113efac#file-delimcc-java-L28-L82

The basic idea is to install a second delimiter around the body of `shift` that allows to capture
the continuation after the call to `resume` -- up to the call of `shift`. The continuation is stored
in a java.lang.Stack which is later trampolined when returning from the original `reset`. That is,
for

    reset {
       ... shift { k => ... resume() ... }2 
    }1

we have a continuation delimited by block (1) and a continuation delimited by block (2). The first
one is suspended by `shift`, the second one is suspended by `resume`.

This solution only works if the continuation (passed as argument to `shift`) does not escape the
dynamic scope of `shift`. If it does, however, we still could fall back to the original implementation.

Again, thanks for making me look again into trampolining. 

Cheers

Jonathan

> On 6. Sep 2018, at 17:30, Ron Pressler <ron.pressler at oracle.com> wrote:
> 
> Hi Jonathan. 
> Glad to hear you like this project.
> 
> Regarding the recursion issue, this is the general problem of not having tail-
> calls, which this project aims to address once fibers are further along. In the
> meantime, you can trampoline (how it's done in Quasar: https://github.com/punive
> rse/quasar/blob/b80b66d871826c0794e7dcc10a9e245889f9f06f/quasar-
> core/src/main/java/co/paralleluniverse/fibers/Continuation.java#L235).
> 
> As to naming, the nomenclature is far from standardized when it comes to
> continuations. Obviously, Continuation is short for delimited continuation. Loom
> currently implements what can be called "non-reentrant (one-shot) assymetric
> delimited continuations with multiple named prompts," but with cloning, you get
> reentrant ("multi-shot") delimited continuations. You are correct that non-
> reentrant delimited continuations are often called coroutines, but the name
> coroutine also used to have the connotation of being symmetric, and more
> recently has gained the connotation (not in academic literature but in language
> implementations) of being a syntactic construct, rather than a purely dynamic
> one. In any event, what "coroutine" means exactly is not standardized, and "non-
> reentrant assymetric delimited continuations with multiple named prompts" is
> too-long a name. "Continuation" is sufficiently general and sufficiently vague
> to be malleable and applicable. Whatever we call this construct, if we decide to
> expose it as a public API, it will serve as a low-level construct, which the
> vast majority of programmers will only use indirectly through higher-level
> constructs such as fibers and generators. Having said that, we may decide to
> change the name to coroutine if we think it makes more sense or if we want to
> use the name continuation for something else.
> 
> 
> Ron
> 
> 
> On September 6, 2018 at 3:09:31 PM, Jonathan Brachthäuser (jonathan.brachthaeuser at uni-tuebingen.de) wrote:
> 
>> Hey everybody, 
>> 
>> first of all I want to say that I am really happy to see multiprompt  
>> delimited continuations coming to the JVM. Thanks to all committers and 
>> to Ron for all the great work! I experimented with the prototype and it 
>> already works great. 
>> 
>> While I see that the currently implemented API and programming model 
>> works perfectly well with Fibers (which is your main motivation as I 
>> understand), there are some issues that I would like to bring up. 
>> 
>> 
>> # Continuations in Literature 
>> Usually in literature "the continuation" represents the remainder of 
>> a program. To briefly summarize some background, for instance, in  
>> 
>> { 
>> 1 + callcc(k -> ... k.resume(3) ... ); 
>> System.out.println("Hello"); 
>> } 
>> 
>> `k` is the (undelimited) continuation. It expects a value of type `int`  
>> and represents the complete callstack at the point of calling `callcc` 
>> -- including both the addition `1 + []` and the `println` statement. 
>> 
>> On the other hand, with some notion of *delimited continuations*, we might have 
>> 
>> reset(p1, () -> 5 - shift(p1, k -> k.resume(2) * 7)); 
>> 
>> which evaluates to `(5 - 3) * 7 = 21`. The continuation `k` corresponds  
>> to the delimited evaluation context `5 - []`. 
>> 
>> 
>> # Continuations in Loom 
>> Since designed with fibers and threads in mind, continuations in loom  
>> conflate multiple aspects of delimited continuations in one class: 
>> 
>> - delimiting a continuation (`reset`). This is modeled by providing a 
>> runnable to the constructor, which can also be thought of as the 
>> initial continuation. 
>> - capturing the continuation (`shift`). While capturing the continuation 
>> is triggered by `Continuation.yield`, the actual continuation itself is 
>> never really exposed. Instead, an object of type `Continuation` in  
>> loom can be thought of as a **mutable reference cell** storing  
>> the actual current (delimited) continuation. 
>> - resuming a continuation (`resume`). When calling `Continuation.run`,  
>> the current continuation, stored in the mutable reference cell, is  
>> resumed and the cell is updated on yielding. 
>> 
>> I am bringing this up for two reasons: 
>> 
>> 1) Conceptually continuations, as they are currently proposed, are closer 
>> to coroutines than to continuations in the traditional sense. I don't 
>> want to start bike shedding, but naming them "Continuation" can be 
>> very confusing for people coming from a functional programming background. 
>> 
>> 2) The traditional interface of delimited continuations can be 
>> implemented using the current proposal: 
>> 
>> https://gist.github.com/b-studios/65e9e614f006d2125659267f6113efac#file-delimcc-java-L33-L37 
>> 
>> However, in order to actually run a continuation to the end a recursive  
>> function `runCont` is required and I couldn't yet find a non-recursive  
>> implementation. This obviously will lead to unnecessary stack  
>> usage. I am working on a library to program with algebraic effect 
>> handlers in Java, which is based on multiprompt delimited continuations. 
>> Project loom is very promising as a backend. However, the stack  
>> usage of `runCont`, imposed by the current loom design is a blocker 
>> since every yield will lead to an additional stackframe. Every 
>> long running computation will thus eventually run out of stack space. 
>> 
>> I would love to hear your thoughts on this. 
>> 
>> Again, thanks to everybody working on this project and all the best, 
>> 
>> Jonathan