Native continuations - Haskell

I'm currently having fun with @Alexis King's branch of GHC with delimited continuations: https://gitlab.haskell.org/lexi.lambda/ghc/raw/continuations-bindist-8.11.0.20200211-x86_64-xenial/ghc.tar.xz

main :: IO ()
main = do
  x <- withReturn $ go 0
  print x
 where
  go :: Int -> Return Int Int
  go n = do
    when (n > 5) $ return 42
    go (n + 1)

newtype Return a b = UnsafeReturn { unsafeReturnToIO :: IO b }
  deriving newtype (Functor, Applicative, Monad, MonadIO)

return :: a -> Return a b
return = UnsafeReturn . shift . const . pure

withReturn :: Return a a -> IO a
withReturn = reset . unsafeReturnToIO

> main
42

Wow, someone actually went to the effort of trying it! :)

THAT THING IS SO COOL - thank you Alexis! :smiley:

The eff interface is nicer (and actually safe), so you should use that instead of calling the unsafe primops. ;)

:100:, I'm just trying this out mostly - I can see why they're unsafe :smiley: :

crazyCoerce :: a -> IO b
crazyCoerce = reset . shift . const . pure

Yes, you will smash your stack if you use them incorrectly. :)

And forgetting reset has nasty consequences :smiley:
BTW, what machinery does it use internally? Is it related to exceptions stuff?

(Oh, and is it safe in ST? :slight_smile: )

It’s all new code: reset# pushes a special kind of stack frame onto the stack, and shift# walks the stack until it finds a reset frame, then copies the upper chunk of the stack into the heap.

The behavior is well-defined in any strict state thread (so strict ST is okay, but not lazy ST), assuming you follow a laundry list of rules.

Cool!
Maybe a little bit crazy question, but is it potentially possible to have multiple overlapping reset/shift scopes?

The main rules are:

1. The behavior of shift# is only defined if you pushed reset# frame in the current state thread (so you can’t call reset# in an outer ST computation and then call shift# in a nested runST computation unless you push a new reset# frame in the nested computation, for example).
2. It is your responsibility to ensure you use shift# with the right type to match the enclosing reset#.
3. You are never allowed to capture STM stack frames or thunk update frames (which mostly translates to “don’t use shift# inside any STM-related things or inside unsafeInterleaveIO”).

TheMatten said:

Cool!
Maybe a little bit crazy question, but is it potentially possible to have multiple overlapping reset/shift scopes?

Not using the primops. eff adds this feature on top by managing a stack of continuation chunks in userspace.

Oh, so you reset and find wanted chunk in retrieved datastructure?

Using the primops is very dangerous. There is no safe way to use shift# in an arbitrary IO computation because shift# does not run exception handlers while unwinding the stack, so if you have code that uses bracket, it’ll just leak.

Oh, so you reset and find wanted chunk in retrieved datastructure?

Effectively yes, but in practice it’s actually much more elaborate for performance reasons. :) There’s a fancy calling convention that all the prompt frames use to handle shift and abort to the right places.

ooo i had no idea that someone had done delimited continuations in hs

cool

@Alexis King Thanks, I will keep these in mind - two more questions:

• Assuming I preserve specified invariants, is this interface meant to be "general" support for continuations, or is it "Eff-specific"?
• When it comes to eff, will it be possible to embed/interpret into IO?

@Alexis King I have been following this work via twitter and the GHC mailing list and just wanted to say that I find it incredibly inspiring and impressive! Thank you for doing it and I can't wait to use and learn from your library!

Yeah, referring to http://www.stephendiehl.com/posts/decade.html, eff is really starting to feel like a "next successor to mtl" :slight_smile:

TheMatten said:

• Assuming I preserve specified invariants, is this interface meant to be "general" support for continuations, or is it "Eff-specific"?

Philosophically, there’s nothing specific to eff in its design. That said, the design space for continuation implementation is enormous, and it’s possible that a different use case would have motivated a different design. The main variations in different implementations are performance tradeoffs: you can optimize for so many different things. You can optimize for capture, for restore, for frequent continuation use, for infrequent use, and any number of other things. Right now, I’m trying to come up with the simplest possible implementation that is reasonably performant, so that should at least ensure it isn’t overfitted to eff’s needs.

• When it comes to eff, will it be possible to embed/interpret into IO?

Yes, this is possible in eff today, though I still need to add support for things like exceptions.

Callan McGill said:

Alexis King I have been following this work via twitter and the GHC mailing list and just wanted to say that I find it incredibly inspiring and impressive! Thank you for doing it and I can't wait to use and learn from your library!

Thank you! :) I don’t know how long it will take to get the primops to a place where they can be merged into GHC, but I’m excited about how things are shaping up.

Inspired by example of Scheme's continuations on Wiki, I've tried out:

lists :: IO ()
lists = print @[Int] =<< reset do
  shift \k -> (1 :) <$> (k $@ pure ())
  shift \k -> (2 :) <$> (k $@ pure ())
  shift \k -> (3 :) <$> (k $@ pure ())
  pure [4,5]

This crashes, but

lists :: IO ()
lists = print @[Int] =<< reset do
  shift \k -> (1 :) <$> (k $@ pure ())
  reset do
  shift \k -> (2 :) <$> (k $@ pure ())
  reset do
  shift \k -> (3 :) <$> (k $@ pure ())
  pure [4,5]

returns [1,2,3,4,5] - That is, reset has to be paired with one shift only to work properly?

(($@) = applyContinuation)

Yes: my implementation of shift both does not capture the prompt and does not leave the prompt behind. Using the terminology of “A monadic framework for delimited continuations” by Dybvig et al., my implementation uses the ${}^{-}\mathcal{F}^{-}$ semantics.

Strictly speaking, this is not faithful to the semantics of the traditional shift operator, which uses a ${}^{+}\mathcal{F}^{+}$ semantics.

If I were to choose names that are most accurate, the right ones would probably be prompt0 and control0, which are presented in “Shift to control” by Chung-chieh Shan and also use the ${}^{-}\mathcal{F}^{-}$ semantics.

The ${}^{-}\mathcal{F}^{-}$ semantics is desirable because you can implement ${}^{+}\mathcal{F}^{-}$, ${}^{-}\mathcal{F}^{+}$, and ${}^{+}\mathcal{F}^{+}$ in terms of it, but the inverse is not true, so it’s a good choice for primitives.

Models you mention are currently out of my mental reach, but if I understand this right, is the fact that you can use current behaviour to emulate Scheme's one again related to what Effdoes with multiple effects?

Yes. A more direct explanation is that if you want to define versions of shift and reset that are completely faithful to their usual Scheme equivalents, you can use this definition of shift' instead of shift:

shift' f = shift \k -> reset $ f (reset . k)

That is, the traditional formulation of shift keeps the reset frame in place after aborting via shift, and it also reinstalls a new reset frame whenever the continuation is applied.

https://github.com/ghc-proposals/ghc-proposals/pull/313 :party_ball:

#313 was accepted :tada:

yorp :clink: