Continuations → Delimited continuations

[Anthony Di Franco]

Hi all, an indecent proposal:
 TL;DR: Avian should deprecate its current continuation API and implement Oleg Kiselyov's scAPI and delimited continuations on top of it, as soon as possible, to avoid the emergence of (more?) work that relies on the old API.
 The rest:
 For a long while I've been looking for JVM support for delimited continuations in order to port Oleg Kiselyov's domain specific language for probabilistic programming to Scala so that I can extend it and do various experiments with it. This will first involve re-targeting the (unusably flawed) Scala standard library support for delimited continuations to use proper VM support. As a result, and while hardly being an expert on the nuances of JVM internals or on continuations, I've ended up doing a fairly thorough survey of the various implementations of various flavors of continuations on and in the JVM. I've just found Avian's implementation that seems to generally follow Stadler et. al. 09, Lazy Continuations for Java Virtual Machines, to implement full-stack-only continuations and also to be in practice implicitly delimited by native call frames, and it is the first thing that seems close enough to usability, (and quite close,) and I found Avian's stated plan to “Experiment with optimizations and extensions to better support languages other than Java” encouraging.
 I've already been frustrated by the fact that the work on continuations on the Sun / Oracle MLVM / JVM has stalled. John R. Rose writes in this blog post (one of the last signs of life of the effort) that what is essentially the part of scAPI lacking from the JVM, but with only optional delimitation, is used internally to implement full-stack continuations, and cites serious security concerns remaining with this approach. Making the explicit, within-scope delimitation mandatory (as in scAPI) and assuring it applies to all access to information on the stack including access to locals seems to me to solve the specific concerns he describes and all similar concerns, and so perhaps access to scAPI would not need to be privileged or break otherwise assured forms of security. I think it solves the issue he mentions with finally blocks as well in that the scope of a delimited continuation could not cross the boundaries of the scope of a try-finally pair. (This delimitation may already be technically possible by means of hack in the Avian implementation by intentionally placing native calls as delimiters.)
 As Kiselyov notes here, (and here,) there are many other reasons that undelimited (limited?) continuations are impractical and delimited continuations are preferable. It is a bonus that Kiselyov and others also have already-worked-out implementations in terms of scAPI of resumable exceptions, delimited dynamic binding, serialization for delimited continuations with a system to choose correctly the references to the environment to restore, a simple yet sophisticated nondeterminism DSL, lazy evaluation (which already appears on the Avian to-do list), tail calls, direct-style functional reactive programming, coroutines, and more. Having all these, to say nothing of adding all these to the JVM ecosystem at once, would quickly make Avian one of the best platforms around for many things.
 For more information, I went into more/different background details when asking (so far in vain) if a bytecode-munging implementation might be feasible here.

— Anthony

[Simon Ochsenreither]

As a mostly non-involved but interested observer, I'm wondering whether you are proposing to do this work or are you suggesting that others do it?

Nevertheless, having Scala's continuations target Avian's continuation support would be quite nice. I also didn't know that Mono had support for continuations. Thanks!

[Anthony Di Franco]

I would prefer for various reasons (including my lack of much direct experience with this sort of thing generally and with Avian's code specifically, and my having my work cut out for me already with what I hope to build on top of this) for the authors of the original continuation support to make this change if they agree with my reasoning, (and it seems a priori like a small change to implement, especially for someone coming from implementing the rest) but I may work doing it myself into my plans otherwise. I would be open to some kind of collaboration that makes sense as well.

Meanwhile, as the only two with any explicit interest in this, we may need to recruit for our lobby.

[Joshua Warner]

Anthony,

I would prefer for various reasons (including my lack of much direct experience with this sort of thing generally and with Avian's code specifically, and my having my work cut out for me already with what I hope to build on top of this) for the authors of the original continuation support to make this change if they agree with my reasoning, (and it seems a priori like a small change to implement, especially for someone coming from implementing the rest) but I may work doing it myself into my plans otherwise. I would be open to some kind of collaboration that makes sense as well.

Your reasoning looks good to me - but the original author of the continuation support (and avian in general) is Joel - and I think he'll be out of contact for a while longer.  I don't think I have a complete enough understanding of the difference between avian's current implementation and your suggestion to make the requisite changes.

If you want to take a crack at implementing it, I may be able to guide you along w.r.t. avian's code base.  We can pool our knowledge.

 

we may need to recruit for our lobby.

Not sure what you mean by this...

-Joshua

[Anthony Di Franco]

Excellent! I'll get some notes together and run them by the author of the ocaml implementation, Oleg Kiselyov, and get right back to you with the details.
 

we may need to recruit for our lobby.

Not sure what you mean by this...

Just a slightly whimsical way of saying I might need to encourage others to chime in with support to get your attention; moot now that I have it.

[Joel Dice]

On Thu, 3 Oct 2013, Anthony Di Franco wrote:

> Hi all, an indecent proposal:

> �TL;DR: Avian should deprecate its current continuation API and implement

> Oleg Kiselyov's scAPI and delimited continuations on top of it, as soon as
> possible, to avoid the emergence of (more?) work that relies on the old API.

Hi Anthony. I'm the one who implemented the current continuation support,
and I've been following this discussion and reading up on the subject.
From what I've read so far, I think switching to delimited continuations
is probably a good idea, but I haven't done enough research or thinking
about it yet to understand all the issues involved.

I'm in Hawaii right now, so my main priority is body surfing, etc., not
thinking about continuations. I guess I could do both at the same time.
Anyway, I'll definitely follow up on this, but it may have to wait until I
return home at the end of the month.

[Simon Ochsenreither]

Have a nice holiday!

[Anthony Di Franco]

Great. It turns out to not be urgent for me at all, and I understand maybe a fair bit of the general issues, but I know of / understand zero of the specifics of the current Avian implementation, so comparing notes should be quite fruitful.

Until then, I will also say enjoy your trip.

[Joel Dice]

Sorry it took so long, but I finally got a chance to look at this again
today. I'm still not sure I understand all the issues involved, but I
decided it would help to sketch out an implementation of shift/reset in
terms of call/cc and solicit test cases which break it.

Here's what I've got so far:

https://github.com/dicej/avian/compare/composable-continuations

I know it's not pretty, and the exception handling is probably wrong, but
I'm mostly curious about what tests we could add to
ComposableContinuations.java which will fail using this implementation.
There's nothing like a concrete, failing test to focus the mind.

Any suggestions?

[Simon Ochsenreither]

Hi,

I tried to drum up some interest regarding the questions you raised here: https://groups.google.com/d/msg/scala-internals/9Ts3GLsXuOg/oPLG_W4QimUJ
(I'm not good at that, but maybe someone takes some pity on me and decides to post here anyway :-D)

Bye,

Simon

[Joel Dice]

Thanks, Simon. I still haven't finished reading all the stuff Anthony
linked to, so I'll focus on that for now.

[Simon Ochsenreither]

Regarding ...

I've been told by knowledgeable people that it is impossible to implement composable continuations (AKA delimited continuations AKA shift/reset) in terms of call-with-current-continuation. Since I don't yet understand why that is, I figured it would help my understanding to attempt it and see how it fails.

... maybe these links have some more information:

http://okmij.org/ftp/continuations/against-callcc.html
http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim
http://okmij.org/ftp/continuations/

[Simon Ochsenreither]

Thanks, Simon.  I still haven't finished reading all the stuff Anthony
linked to, so I'll focus on that for now.

Ah right, sorry. I just saw that one of Anthony's links aready pointed to Oleg Kiselyov's resources.

[Joshua Warner]

I'm generally in agreement with Joel, but I'm also a little curious about your goal.  Throwing money at the problem means it's materially important to someone, and that means they're probably going to _do_ something with it.  Which is awesome, btw...

But for any serious applications of an Avian feature not in the standard JVM, I see two possible paths:

* We maintain the avian feature as, effectively, a fork in the JVM spec - and your software continues to run only on avian (or perhaps utilizing something like quasar on other jvms)

* Avian's implementation is used as a demonstration/foothold to try to get the feature included in the JVM spec and eventually hotspot (probably through a JSR).

I would be really excited about the latter, but it's quite a long-shot; and the former has serious caveats.

Of course, like as not, I'm way off base on both of those.  Anthony, could you shed some light?

Thanks,

-Joshua

On 7 March 2014 07:23, Joel Dice <joel...@gmail.com> wrote:

Hi Anthony,

I haven't talked to Josh yet, but speaking for myself I'd say that it's not a matter of money or even time at this point.

If your Typesafe contact wants to see delimited continuations in Avian, but isn't picky about what that means, then it's done already: https://github.com/dicej/avian/compare/composable-continuations

If, on the other hand, he or she has specific requirements (e.g. speed, memory usage, corner cases) which need to be fulfilled, then even better: please have him or her provide feedback on that implementation.  What I'd like best is runnable test cases that cause that implementation to fail, but I'd settle for a precisely worded description of what's missing or wrong with it.

If, once we get into the details, we find that the client needs something that will take significant time and effort beyond what we're willing to do without pay, we can talk about that.  I would be very surprised if that were the case, though.

TL;DR: we need feedback, not money (we like money, too, but that's not what Avian is about right now)

On Thu, 6 Mar 2014, Anthony Di Franco wrote:

Hey y'all,
Sorry to have let this drop away. My employer has been running out of
money which created various cascading complications for me. However,
meanwhile, I may have a Typesafe person be willing to pay out of his
personal pocket to get this done. Would you be willing to give a ballpark
estimate on it? I can advise throughout.


On Fri, Dec 27, 2013 at 3:53 PM, Joel Dice <joel...@gmail.com> wrote:

No worries.  I'll be busy all day tomorrow, but I'm generally logged in to
Google Talk from 8 to 5 on weekdays, so feel free to ping me there.

Thanks for the link; I'll read it when I get a chance.



On Fri, 27 Dec 2013, Anthony Di Franco wrote:

Sorry, I failed to notice your reply until now. Tomorrow at the same time
would work if still possible.
Also, I just found this very comprehensible passage with a reference to
the
mincaml implementation and a simple explanation (though I'd still suggest
named prompts)
http://stackoverflow.com/questions/5989961/why-are-
delimited-continuation-p
rimitives-named-shift-and-reset

On Dec 20, 2013 8:58 AM, "Joel Dice" <joel...@gmail.com> wrote:
      How about noon MST (1PM PST)?  I'll plan to be logged in as
      joel...@gmail.com on Google Talk at that time.  Let me know if
      you want to use something different or meet at a different time.

      The code of interest is in types.def (the continuationContext
      and continuation types), compile.cpp (makeCurrentContinuation,
      callContinuation, callWithCurrentContinuation, and dynamicWind),
      and of course the wall of assembly in e.g. continuations-x86.S,
      which is responsible for copying the next continuation frame to
      the real stack and jumping to it.

      Here's a breakdown of the types defined in types.def (which are
      translated into C++ code at build time):

      (type continuationContext
        (object next)   ;; used to walk the list of dynamic-wind
      frames so the
                        ;; appropriate "before" and "after" callbacks
      can be
                        ;; called.

        (object before) ;; the dynamic-wind "before" callback

        (object after)  ;; the dynamic-wind "after" callback

        (object continuation) ;; the continuation to call when
      unwinding through
                              ;; a dynamic-wind frame

        (object method)) ;; used to check whether the context of the
      called
                         ;; continuation is compatible with the
      context of the
                         ;; calling continuation (e.g. the return
      types are
                         ;; compatible)

      ;; this should probably be called continuationFrame:
      (type continuation avian/Continuations$Continuation
        (object next)    ;; the next frame in the continuation

        (object context) ;; the continuationContext this continuation
      belongs to

        (object method)  ;; the method for which this frame was
      allocated

        (void* address)  ;; the instruction pointer within the method
      at the
                         ;; time the continuation was captured

        (uintptr_t returnAddressOffset) ;; the offset within the body
      of the
                                        ;; frame where the return
      address can be
                                        ;; found, so we can change it
      when the
                                        ;; frame is copied to the
      stack

        (uintptr_t framePointerOffset)  ;; as above, except this is
      for the
                                        ;; frame pointer

        (array uintptr_t body)) ;; the body of the frame, as copied
      straight
                                ;; from the native stack

      The layout of the body of the frame depends on the architecture,
      but it looks roughly like this:

      |-------------------------|
      | Java stack              |
      |-------------------------|
      | alignment padding       |
      |-------------------------|
      | Java locals             |
      |-------------------------|
      | frame header            |
      |-------------------------|
      | frame footer for caller |
      |-------------------------|
      | arguments from caller   |
      |-------------------------|

      The frame header and frame footer are the arch-dependent parts
      and contain the return address, frame pointer, etc.

      Hopefully that helps a bit.


      On Thu, 19 Dec 2013, Anthony Di Franco wrote:


            Saturday should be fine, early afternoon best. I'm
            in San Francisco (-8)

            Regarding the stack, going a bit lower level, what
            would the binary format
            of frames look like in an RFC type of explication?
            And where in the source
            tree do I find the key parts defining and
            manipulating them? I am pretty
            clear on the concepts but I had a brief peek around
            and was repelled by a
            wall of assembler so I could use a little primer.

            On Dec 18, 2013 7:59 AM, "Joel Dice"
            <joel...@gmail.com> wrote:
                  Yeah, I should have time for a live meeting
            this Saturday.  What
                  time zone are you in?  Josh and I are in MST
            (UTC -7).

                  The current implementation is pretty simple to
            describe:

                  At any given point in execution, the stack may
            be composed of
                  some combination of the following:

                   * "real" Java frames, i.e. frames on the
            actual process stack

                   * continuation Java frames: heap-allocated,
            immutable objects
                  containing snapshots of frames captured as
            part of a
                  continuation and collected in a singly-linked
            list.  These
                  frames must be copied to the real stack before
            they can be used.
                   Since it's a singly-linked list, several
            unique continuations
                  can share frames which they have in common,
            forming a tree.

                   * "real" native frames, i.e. frames allocated
            by native code on
                  the actual process stack

                  To capture a continuation, we visit all the
            "real" Java frames,
                  starting with the most recent, and make a
            continuation frame
                  from each one.  When we run out of real Java
            frames, we link our
                  continuation-list-in-progress to the next
            continuation Java
                  frame, if any.  Otherwise, we've reached a
            native frame, so we
                  stop.

                  To call a continuation, we unwind the stack to
            the most recent
                  frame shared by the current continuation and
            the one we want to
                  call, then "push" any additional frames in the
            called
                  continuation.  The "push" itself does not
            require copying all
                  those frames to the real stack; we only need
            to copy the top one
                  and set Thread::continuation to point to the
            next one, which
                  will be copied to the real stack if and when
            it is needed, etc.

                  Okay, maybe it's not as simple to describe as
            I thought.
                   Hopefully it will make more sense when we
            chat later.


                  On Tue, 17 Dec 2013, Anthony Di Franco wrote:


                        Now that you're getting started, I'd
            like to help
                        out if possible. I could
                        benefit from some pointers or recipes
            for exposing
                        vm internals via the
                        avian package and on the stack frame
            format and
                        existing operations that
                        manipulate it, installing exception
            handlers
                        especially. Do you have time
                        for a live text or video interaction to
            go over
                        these things? I think it
                        would save me a lot of time and maybe I
            can
                        reciprocate by advising on the
                        implementation strategy.

                        Anthony

                        On Nov 16, 2013 11:20 AM, "Joel Dice"

                        <joel...@gmail.com> wrote:
                              On Thu, 3 Oct 2013, Anthony Di
            Franco wrote:

                                    Hi all, an indecent
            proposal:

                              --
                              You received this message because
            you are
                        subscribed to a topic
                              in the Google Groups "Avian"
            group.
                              To unsubscribe from this topic,
            visit


            https://groups.google.com/d/topic/avian/yrdlmjLy1Ng/
unsubscribe.
                              To unsubscribe from this group and
            all its
                        topics, send an email
                              to
            avian+unsubscribe@googlegroups.com.
                              To post to this group, send email
            to
                        av...@googlegroups.com.
                              Visit this group at
                        http://groups.google.com/group/avian.
                              For more options, visit

            https://groups.google.com/groups/opt_out.

[Simon Ochsenreither]

Hi,

any ideas what's the way forward on this?

I'll try Joel's implementation and report back ... what would be necessary to get it merged into trunk? Are there any known issues/limitations which block this?

Thanks,

Simon

[Simon Ochsenreither]

Just tried it: https://gist.github.com/soc/9616169

It works with make continuations=true tails=true
... but fails with make continuations=true tails=true openjdk=/home/soc/Entwicklung/avian-build/jdk-avian

... issuing the following error message:

classpath/avian/Continuations.java:211: error: cannot find symbol

(final FunctionReceiver<T> receiver)

^

symbol: class FunctionReceiver

location: class Continuations

classpath/avian/Continuations.java:222: error: cannot find symbol

(new Function() {

^

symbol: class Function

2 errors

Is this expected?

Thanks,

Simon

[Anthony Di Franco]

I am supposed to be porting some tests in from the working OCaml version.

I am quite sure that it's impossible to implement this correctly without VM support. (Not even bytecode rewriting to CPS transformed code will work in general because the JVM has no tail calls optimization.)

I don't understand the avian code purporting to implement this as it is now so ignore this: the code as it is does not look like it is implementing or leveraging some kind of VM support.

[Simon Ochsenreither]

I converted some scala-continuation samples to use Avian and it seems to work fine. For instance, this example correctly returns 20:

  val result5 = reset {
    shift { k: (AvianFunction[Int]) =>
      k.call(k.call(k.call(7)))
    } + 1
  } * 2 // result 20

Can you add some details about what's missing?

[Simon Ochsenreither]

See https://gist.github.com/soc/9617078 for things which work.

[Simon Ochsenreither]

One issue I found is that Scala defines shift as

def shift[A,B,C](fun: (A => B) => C): A

and reset as

def reset[A,C](ctx: =>A): C

while Avian's shift and reset is basically shift[T](fun: (T => T) => T): T and reset[T](ctx: => T): T.

[Joel Dice]

No, and I wasn't able to reproduce it. And in your Gist, it looks like
the error went away the second time you ran make, which is weird.

[Simon Ochsenreither]

No, and I wasn't able to reproduce it.  And in your Gist, it looks like
the error went away the second time you ran make, which is weird.

Definitely weird. It's not order-dependent though. It really seems to depend on whether the openjdk argument is set...

[Joel Dice]

On Tue, 18 Mar 2014, Simon Ochsenreither wrote:

Ah, I didn't read carefully -- that's the part I was missing. It's fixed
now:

https://github.com/dicej/avian/commit/6abedc00d4d991b6b6425dcb9c09f76b5363adb2

[Anthony Di Franco]

Could someone say in English a summary of the strategy of how this is implemented?

--
You received this message because you are subscribed to a topic in the Google Groups "Avian" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/avian/yrdlmjLy1Ng/unsubscribe.
To unsubscribe from this group and all its topics, send an email to avian+unsubscribe@googlegroups.com.
To post to this group, send email to av...@googlegroups.com.
Visit this group at http://groups.google.com/group/avian.

For more options, visit https://groups.google.com/d/optout.

[Simon Ochsenreither]

Ah, I didn't read carefully -- that's the part I was missing.  It's fixed
now:

Ahhh, damn. I could have figured out this on my own. :-/

Thanks!

[Joel Dice]

On Tue, 18 Mar 2014, Simon Ochsenreither wrote:

> One issue I found is that Scala defines shift as
>
> def shift[A,B,C](fun: (A => B) => C): A
>
>
> and reset as
>
> def reset[A,C](ctx: =>A): C
>
>

> while Avian's shift and reset is basically shift[T](fun: (T => T) => T): Tand reset[T](ctx:
> => T): T.

Good point. I've updated the API:
https://github.com/dicej/avian/commit/fd778c2c7608290d16459b05a73e279c4718e09e

One thing I'm not sure about is whether there should be a relationship
between the types named in the Scala API. Are the A and C in reset
supposed to correspond to the A and C in any enclosed shifts? If there is
supposed to be a correspondence, it seems like reset should be defined as
"def reset[B,C](ctx: =>B):C" to match "def shift[A,B,C](fun: (A => B) =>
C): A". See
https://github.com/dicej/avian/blob/fd778c2c7608290d16459b05a73e279c4718e09e/test/extra/ComposableContinuations.java#L73
for an example. Am I missing something?

Of course, javac won't (and, in general, can't) ensure there's any type
correspondence between shifts and their resets, so we have to rely on
runtime type checks anyway.

[Joel Dice]

On Tue, 18 Mar 2014, Anthony Di Franco wrote:

> Could someone say in English a summary of the strategy of how this is
> implemented?

I assume you're asking about the shift and reset methods in
https://github.com/dicej/avian/blob/composable-continuations/classpath/avian/Continuations.java.

I'll describe what happens when shift is called only once from within the
thunk passed to reset. Here's what the call stack looks like before reset
is called (stack grows down, assume F0 is the method that calls reset):

| ... |
|------------------------|
| F0 |
|------------------------|

The reset method starts by pushing a new reset context on a thread-local
stack so that any nested shifts will know which one to use. Then it
captures the current (full) continuation (let's call it C1), stores it in
the aforementioned context, and calls the thunk (call it F1) it was
passed.

The call stack now looks like this:

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F1 |
|------------------------|

When the thunk calls shift (directly or indirectly), it receives a
function (call it F2) which we'll invoke later. First, though, we capture
the current (full) continuation (call it C2) and retrieve the reset
context. Then we create a new callback (call it F3) and push it onto a
callback stack attached to the reset context and invoke the reset
continuation (C1), passing null to it (which will be ignored).

Just before we invoke C1, the call stack looks like this:

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F1 |
|------------------------|
| ... |
|------------------------|
| shift | <- C2
|------------------------|

After we invoke C1, it looks like this:

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|

Having jumped back to the reset continuation, we pop the latest callback
(F3) off the callback stack and call it. F3 immediately invokes F2,
passing it a new function (call it F4).

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F3 |
|------------------------|
| F2 |
|------------------------|

Recall that F2 was provided by the application, so it does its thing, and
may or may not do anything with F4. Let's assume in this case that it
does eventually call F4. F4 now captures the current (full) continuation
(call it C3) and pushes it onto the callback stack.

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F3 |
|------------------------|
| F2 |
|------------------------|
| ... |
|------------------------|
| F4 | <- C3
|------------------------|

Next, F4 calls the earlier continuation captured when shift was first
called (C2).

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F1 |
|------------------------|
| ... |
|------------------------|
| shift | <- C2
|------------------------|

Having jumped back to the shift continuation, we return from shift,
continuing on until F1 returns a value (call it R1), at which point we
find ourselves back in reset (having unwound the call stack there
naturally this time instead of jumping to it).

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|

Now we pop the latest continuation (C3) off the callback stack, and call
it, passing R1 to it.

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F3 |
|------------------------|
| F2 |
|------------------------|
| ... |
|------------------------|
| F4 | <- C3
|------------------------|

This causes R1 to be returned to whatever called F4, and eventually F2
returns a result (call it R2) to F3.

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|
| F3 |
|------------------------|

Here we call the reset continuation a final time, passing it R2.

| ... |
|------------------------|
| F0 |
|------------------------|
| reset | <- C1
|------------------------|

Having jumped back to the reset continuation, we find the callback stack
is empty, so we just return R2, popping the reset context off the
thread-local stack before we do so. Thus the result returned to F0 is R2.

If there's more than one shift, the story is mostly the same, but we'll
have as many callbacks/continuations on the callback stack as there are
shifts before its over. If there are no shifts, the thunk just runs to
completion with nothing special happening.

BTW, upon writing this, I realized that a little refactoring would let F3
return R2 to reset with a natural method return, rather than calling the
continuation. The effect would be the same, but it would be a bit more
efficient.

Hope that helps.