Native continuations - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here.

TheMatten

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
Alexis King

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

TheMatten

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

Alexis King

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

TheMatten

: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
Alexis King

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

TheMatten

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

TheMatten

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

Alexis King

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.

Alexis King

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.

TheMatten

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

Alexis King

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”).
Alexis King

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.

TheMatten

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

Alexis King

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.

Alexis King

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.

Joel McCracken

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

TheMatten

@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?
Callan McGill

@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!

TheMatten

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

Alexis King

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.

Alexis King

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.

TheMatten

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?

TheMatten

(($@) = applyContinuation)

Alexis King

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 F {}^{-}\mathcal{F}^{-} semantics.

Alexis King

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

Alexis King

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 F {}^{-}\mathcal{F}^{-} semantics.

Alexis King

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

TheMatten

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?

Alexis King

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)
Alexis King

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.

TheMatten

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

This is a proposal for adding primops for capturing slices of the RTS stack to improve the performance of algebraic effect systems, which require delimited continuations. Rendered
TheMatten

#313 was accepted :tada: