Feasibility of native RTS support for continuations?

[Alexis King]

> On Jan 28, 2020, at 04:09, Simon Peyton Jones <simonpj at microsoft.com> wrote:
> 
> I've thought about this quite a bit in the past, but got stalled for lack of cycles to think about it more.  But there's a paper or two

Many thanks! I’d stumbled upon the 2007 paper, but I hadn’t seen the 2016 one. In the case of the former, I had thought it probably wasn’t enormously relevant, since the “continuations” appear to be fundamentally one-shot. At first glance, that doesn’t seem to have changed in the JFP article, but I haven’t really read it yet, so maybe I’m mistaken. I’ll take a closer look.

> On the effects front I think Daan Leijen is doing interesting stuff, although I'm not very up to date:
> https://www.microsoft.com/en-us/research/people/daan/publications/

Indeed, I’ve read a handful of his papers while working on this! I didn’t mention it in the original email, but I’ve also talked a little with Matthew Flatt about efficient implementation of delimited control, and he pointed me to a few papers a couple of months ago. One of those was “Final Shift for call/cc: a Direct Implementation of Shift and Reset” by Gasbichler and Sperber, which describes an approach closest to what I currently have in mind to try to implement in the RTS.

> One interesting dimension is whether or not the continuations you capture are one-shot.  If so, particularly efficient implementations are possible.

Quite so. One thing I’ve considered is that it’s possible to obtain much of that efficiency even without requiring strict one-shot continuations if you have a separate operation for restoring a continuation that guarantees you won’t ever restore it again, sort of like the existing unsafeThaw/unsafeFreeze operations. That is, you can essentially convert a multi-shot continuation into a one-shot continuation and reap performance benefits, even if you’ve already applied the continuation.

This is a micro-optimization, though, so I’m not worrying too much about it right now.

> Also: much of the "capture stack chunk" stuff is *already* implemented, because it is (I think) what happens when a thread receives an asynchronous exception, and just abandon its evaluation of thunks that it has started work on.

Now that is very interesting, and certainly not something I would have expected! Why would asynchronous exceptions need to capture any portion of the stack? Exceptions obviously trigger stack unwinding, so I assumed the “abort to the current prompt” part of my implementation would already exist, but not the “capture a slice of the stack” part. Could you say a little more about this, or point me to some relevant code?

Thanks again,
Alexis