Multiprompt delimited continuations

[Ron Pressler]

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