On Jan 28, 2020, at 04:09, Simon Peyton Jones 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

On Jan 29, 2020, at 03:32, Simon Peyton Jones wrote:

Suppose a thread happens to be evaluating a pure thunk for (factorial 200). […] This stack-freezing stuff is definitely implemented.

That’s fascinating! I had no idea, but your explanation makes sense (as do the papers you linked). That is definitely promising, as it seems like many of the tricky cases may already be accounted for? I’ll see if I can follow the Cmm code well enough to hunt down how it’s implemented. One other thing I have been thinking about: this is completely incompatible with the state hack, isn’t it? That is not a showstopper, of course—I do not intend to suggest that continuations be capturable in ordinary IO—but it does mean I probably want a way to selectively opt out. (But I’ll worry about that if I ever get that far.) Alexis

On Jan 30, 2020, at 02:35, Simon Marlow wrote:

My guess is you can almost do what you want with asynchronous exceptions but some changes to the RTS would be needed.

There's a bit of code in the IO library that literally looks like this (https://gitlab.haskell.org/ghc/ghc/blob/master/libraries%2Fbase%2FGHC%2FIO%2...)

Thanks for the pointer, I definitely had not discovered that! That is an interesting trick. I think your explanation paired with the Note is enough for it to make sense to me, though I don’t yet understand all the implementation subtleties of raiseAsync itself.

Also you might want to optimise the implementation so that it doesn't actually tear down the stack as it copies it into the heap, so that you could avoid the need to copy it back from the heap again in shift#.

I don’t fully understand this point — do you mean “avoid the need to copy it back on continuation application”? shift# just copies the stack slice to the heap, so it doesn’t need to copy it back. If I was right, and you were referring to continuation application rather than shift#, I agree with you there. It seems as though it ought to be possible to represent the stack slice as a stack itself, so if the stack looks like ┌───────────┐ │ RET_SMALL │ ├───────────┤ │ CATCH │ ├───────────┤ │ RESET │ ├───────────┤ then the captured continuation could itself essentially be a stack like ┌───────────┐ │ RET_SMALL │ ├───────────┤ │ CATCH │ ├───────────┤ │ UNDERFLOW │ └───────────┘ where restoring a continuation just copies the captured stack and updates its underflow frame to point at the top of the current stack. If the caller promises not to use the continuation again after applying it, the copying could be skipped entirely, and the captured stack could just become the new stack. However, I don’t understand enough about the way the RTS currently works to know if this is viable. For example, what if I write this: reset (mask_ (shift f)) Now presumably I want to ensure the masking state is restored when I invoke the continuation. But it can’t just be unconditionally restored, since if I write mask_ (reset (shift f >>= g)) then the mask frame isn’t included on the stack, so applying the continuation shouldn’t affect the masking state. Presumably this means a continuation restore can’t be as simple as copying the captured stack frames onto the current stack, since restoring certain frames affects other parts of the RTS state. (Tangentially, it seems like this particular example is not handled properly in the existing capture/restore code, as this comment in Exception.cmm notes: NB. there's a bug in here. If a thread is inside an unsafePerformIO, and inside maskAsyncExceptions# (there is an unmaskAsyncExceptions_ret on the stack), and it is blocked in an interruptible operation, and it receives an exception, then the unsafePerformIO thunk will be updated with a stack object containing the unmaskAsyncExceptions_ret frame. Later, when someone else evaluates this thunk, the original masking state is not restored. I think getting this right probably matters more if continuations are added, so that’s something else to worry about.)

So that's shift#. What about reset#? I expect it's something like `unsafeInterleaveIO`, that is it creates a thunk to name the continuation. You probably also want a `catch` in there, so that we don't tear down more of the stack than we need to.

It would be nice to be able to capture slices of the stack that include catch frames, though theoretically it isn’t necessary — it would be possible to arrange for a continuation that wants to capture through a catch to do something like reset (... (catch (reset ...) ...)) instead, then call shift twice and compose the two continuations by hand (inserting another call to catch in between). I don’t know enough yet to understand all the tradeoffs involved, but I’ll see if it’s possible to get away with the userland emulation, since I figure the less code in the RTS the better!

Hope this is helpful.

Very much so, thank you!

On Jan 30, 2020, at 10:31, Ben Gamari wrote:

For the record, runtime system captures the stack state in an AP_STACK closure. This is done in rts/RaiseAsync.c:raiseAsync and some of this is described in the comment attached to that function.

As Simon PJ points out, this is all very tricky stuff, especially in a concurrent context. If you make any changes in this area do be sure to keep in mind the considerations described in Note [AP_STACKs must be eagerly blackholed], which arose out of the very-nast #13615.

Thank you for the pointers — I did manage to find raiseAsync, but I hadn’t seen that Note. I will try my best to be suitably wary, though I imagine I’m in far enough over my head that I don’t yet know half the things I need to be wary of. :) Alexis

On Sun, 2 Feb 2020 at 04:26, Alexis King wrote:

I took a stab at implementing this today, using the “continuation is a stack” implementation strategy I described in my previous email. I haven’t tried very hard to break it yet, but this tiny test program works:

{-# LANGUAGE BangPatterns, BlockArguments, MagicHash, ScopedTypeVariables, UnboxedTuples #-}

import GHC.Prim import GHC.Types

data Continuation a b = Continuation# (Continuation# RealWorld a b)

reset :: IO a -> IO a reset (IO m) = IO (reset# m)

shift :: (Continuation a b -> IO b) -> IO a shift f = IO (shift# \k -> let !(IO m) = f (Continuation# k) in m)

applyContinuation :: Continuation a b -> a -> IO b applyContinuation (Continuation# k) a = IO (applyContinuation# k a)

main :: IO () main = do ns <- reset do n <- shift \(k :: Continuation Integer [Integer]) -> do a <- applyContinuation k 2 b <- applyContinuation k 3 pure (a ++ b) pure [n] print ns

The output of this program is [2, 3], as expected.

That's impressive!

My implementation doesn’t share any code with raiseAsync. Currently, it isn’t very clever:

* reset# pushes a RET_SMALL frame with a well-known info pointer, &stg_reset_frame_info.

* shift# walks the stack and copies it up to the nearest reset frame. If the stack consists of several chunks, it only copies the chunk that contains the reset frame, and it just repurposes the other chunks as the continuation (since the stack is unwinding anyway).

* applyContinuation# copies the captured stack and updates the UNDERFLOW frames as needed to point to the current stack.

* I haven’t implemented it yet, but it would be straightforward to implement an applyContinuationOneShot# operation that works like applyContinuation#, but doesn’t actually copy anything and just updates the UNDERFLOW frames in the captured stack itself.

This seems to work in my very simple examples, but there are also things I know it doesn’t handle properly:

* It doesn’t make any attempt to handle modifications to the interrupt masking state properly. The right thing to do here is probably to look for mask/unmask frames on the stack during unwinding and to stash that information somewhere.

* It doesn’t do anything special for UPDATE_FRAMEs, so if there’s an UPDATE_FRAME that owns a blackhole on the stack, things will go quite wrong.

I haven’t been worrying about this because I don’t think there should ever be any update frames between shift# and reset#. In the case of raiseAsync, the location of the “prompt” is well-defined: it’s the update frame. But shift# captures up to an explicit prompt, so using shift# when there’s an update frame on the stack can surely only lead to nonsense... right?

* It doesn’t do anything special for STM frames, so trying to capture a continuation through those will be similarly broken.

Yes, these are all the things that make raiseAsync tricky! You can either copy what raiseAsync does (but be warned, it has taken a lot of iteration to get right) or try to use raiseAsync and/or modify it to do what you want. Cheers Simon

There are also probably bugs I don’t know about — I haven’t exercised the implementation very hard yet — but I’ll keep playing with it. If anyone is at all interested, I’ve pushed the code to a branch here:

https://gitlab.haskell.org/lexi.lambda/ghc/compare/master...first-class-cont...

My thanks again to everyone’s help!

Alexis

On Mon, 10 Feb 2020 at 08:10, Alexis King wrote:

On Feb 6, 2020, at 02:28, Simon Marlow wrote:

The issue here is that raiseAsync is destructive - it *moves* the stack to the heap, rather than copying it. So if you want to continue execution where you left off, for shift#, you would have to copy it back onto the stack again. That's the point I was trying to highlight here.

Ah, yes, I see what you mean! It happens that for my use case I actually do want to unwind the stack when I capture a continuation, so that isn’t a problem for me.

Yes, these are all the things that make raiseAsync tricky! You can either copy what raiseAsync does (but be warned, it has taken a lot of iteration to get right) or try to use raiseAsync and/or modify it to do what you want.

My point was more that I’m unsure that shift# *should* handle most of those cases. For raiseAsync, it makes sense, since asynchronous interrupts can, by their nature, occur at any time, even during pure code. But my shift# operation lives in IO, and the intent is to only capture up to a reset# in the same state thread.

My justification for this is that if you could use shift# in pure code, it would be ill-defined what you’d even be capturing. Suppose you return a thunk containing a call to shift#. When the thunk is evaluated, you capture up to the nearest reset#… but who knows what that is now? This opens you up to all sorts of general badness.

Therefore, I don’t think there should ever be an UPDATE_FRAME in the captured continuation—if there is, it’s probably a bug. So unless someone can think of any valid use cases, I’ll make that more explicit by modifying the continuation-capturing code to add some assertions that those frames never appear in the captured stack.

Let me just say "unsafePerformIO" :) You probably want to at least ensure that things don't crash in that case, even if you can't give a sensible semantics to what actually happens. We have a similar situation with unsafeIOToST - we can't tell you exactly what it does in general, except that it doesn't crash (I hope!). Cheers Simon

On Feb 10, 2020, at 02:18, Simon Marlow wrote:

...

On Mon, 10 Feb 2020 at 08:17, Simon Marlow wrote:

Let me just say "unsafePerformIO" :) You probably want to at least ensure that things don't crash in that case, even if you can't give a sensible semantics to what actually happens. We have a similar situation with unsafeIOToST - we can't tell you exactly what it does in general, except that it doesn't crash (I hope!).

Typo - I meant unsafeIOToSTM here.

I’ve been thinking about this. At first I figured you were probably right, and I decided I’d switch to a more raiseAsync-like approach. But once I started trying to implement it, I became less convinced it makes sense. As its name implies, an AP_STACK is sort of like a saturated application, where the stack itself is the “function.” Extending the analogy, a continuation would be a PAP_STACK, since the stack is awaiting a value. This difference is significant. Suppose you write: let x = 1 + unsafePerformIO (shift f >>= g) in ... If you force x, the stack will unwind to the nearest reset. When you unwind past x’s UPDATE_FRAME, you can’t replace the blackhole with an AP_STACK, since the captured slice of the stack represents the expression \m -> 1 + unsafePerformIO (m >>= g) which is a function, not a thunk. The only logical interpretation of this situation is that x is a thunk quite like let y = 1 + error "bang" except that it doesn’t just abort to the enclosing reset frame when forced, it actually composes the captured continuation with the upper frames of the current stack and passes the composed continuation to f to resume computation. That’s an awful lot of trouble given the resulting semantics is going to be unpredictable, anyway! I should be clear that I do not intend shift/reset to have any safe interface in IO directly. Even if you could make it type safe, it would break all kinds of code that manages resources using bracket. Rather, I have built a library that defines a totally separate Eff monad, and that monad uses the primops directly, wrapped in a safe interface. It isn’t possible for a user to screw things up using unsafePerformIO because there is no way to call shift from IO (unless you wrap shift# in IO yourself, but then I think you can be expected to know what you’re getting yourself into). So without mucking about with GHC.Exts, you still can’t get segfaults. Alexis

On Sat, 1 Feb 2020 at 00:23, Alexis King wrote:

...

On Jan 30, 2020, at 02:35, Simon Marlow wrote:

...

Also you might want to optimise the implementation so that it doesn't actually tear down the stack as it copies it into the heap, so that you could avoid the need to copy it back from the heap again in shift#.

I don’t fully understand this point — do you mean “avoid the need to copy it back on continuation application”? shift# just copies the stack slice to the heap, so it doesn’t need to copy it back.

The issue here is that raiseAsync is destructive - it *moves* the stack to the heap, rather than copying it. So if you want to continue execution where you left off, for shift#, you would have to copy it back onto the stack again. That's the point I was trying to highlight here. Cheers Simon

If I was right, and you were referring to continuation application rather than shift#, I agree with you there. It seems as though it ought to be possible to represent the stack slice as a stack itself, so if the stack looks like

┌───────────┐ │ RET_SMALL │ ├───────────┤ │ CATCH │ ├───────────┤ │ RESET │ ├───────────┤

then the captured continuation could itself essentially be a stack like

┌───────────┐ │ RET_SMALL │ ├───────────┤ │ CATCH │ ├───────────┤ │ UNDERFLOW │ └───────────┘

where restoring a continuation just copies the captured stack and updates its underflow frame to point at the top of the current stack. If the caller promises not to use the continuation again after applying it, the copying could be skipped entirely, and the captured stack could just become the new stack.

However, I don’t understand enough about the way the RTS currently works to know if this is viable. For example, what if I write this:

reset (mask_ (shift f))

Now presumably I want to ensure the masking state is restored when I invoke the continuation. But it can’t just be unconditionally restored, since if I write

mask_ (reset (shift f >>= g))

then the mask frame isn’t included on the stack, so applying the continuation shouldn’t affect the masking state. Presumably this means a continuation restore can’t be as simple as copying the captured stack frames onto the current stack, since restoring certain frames affects other parts of the RTS state.

(Tangentially, it seems like this particular example is not handled properly in the existing capture/restore code, as this comment in Exception.cmm notes:

NB. there's a bug in here. If a thread is inside an unsafePerformIO, and inside maskAsyncExceptions# (there is an unmaskAsyncExceptions_ret on the stack), and it is blocked in an interruptible operation, and it receives an exception, then the unsafePerformIO thunk will be updated with a stack object containing the unmaskAsyncExceptions_ret frame. Later, when someone else evaluates this thunk, the original masking state is not restored.

I think getting this right probably matters more if continuations are added, so that’s something else to worry about.)

...

So that's shift#. What about reset#? I expect it's something like `unsafeInterleaveIO`, that is it creates a thunk to name the continuation. You probably also want a `catch` in there, so that we don't tear down more of the stack than we need to.

It would be nice to be able to capture slices of the stack that include catch frames, though theoretically it isn’t necessary — it would be possible to arrange for a continuation that wants to capture through a catch to do something like

reset (... (catch (reset ...) ...))

instead, then call shift twice and compose the two continuations by hand (inserting another call to catch in between). I don’t know enough yet to understand all the tradeoffs involved, but I’ll see if it’s possible to get away with the userland emulation, since I figure the less code in the RTS the better!

...

Hope this is helpful.

Very much so, thank you!

...

On Jan 30, 2020, at 10:31, Ben Gamari wrote:

For the record, runtime system captures the stack state in an AP_STACK closure. This is done in rts/RaiseAsync.c:raiseAsync and some of this is described in the comment attached to that function.

As Simon PJ points out, this is all very tricky stuff, especially in a concurrent context. If you make any changes in this area do be sure to keep in mind the considerations described in Note [AP_STACKs must be eagerly blackholed], which arose out of the very-nast #13615.

Thank you for the pointers — I did manage to find raiseAsync, but I hadn’t seen that Note. I will try my best to be suitably wary, though I imagine I’m in far enough over my head that I don’t yet know half the things I need to be wary of. :)

Alexis