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 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).
It is your responsibility to ensure you use shift# with the right type to match the enclosing reset#.
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”).
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.
@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!
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 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.
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− 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 −F− semantics.
The −F− semantics is desirable because you can implement +F−, −F+, and +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:
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.
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
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
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: :
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, andshift#
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 lazyST
), 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:
shift#
is only defined if you pushedreset#
frame in the current state thread (so you can’t callreset#
in an outerST
computation and then callshift#
in a nestedrunST
computation unless you push a newreset#
frame in the nested computation, for example).shift#
with the right type to match the enclosingreset#
.shift#
inside any STM-related things or insideunsafeInterleaveIO
”).TheMatten said:
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 arbitraryIO
computation becauseshift#
does not run exception handlers while unwinding the stack, so if you have code that usesbracket
, it’ll just leak.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
andabort
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:
Eff
-specific"?eff
, will it be possible to embed/interpret intoIO
?@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 tomtl
" :slight_smile:TheMatten said:
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 toeff
’s needs.Yes, this is possible in
eff
today, though I still need to add support for things like exceptions.Callan McGill said:
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:
This crashes, but
returns
[1,2,3,4,5]
- That is,reset
has to be paired with oneshift
only to work properly?(
([email protected])
=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 −F− semantics.Strictly speaking, this is not faithful to the semantics of the traditional
shift
operator, which uses a +F+ semantics.If I were to choose names that are most accurate, the right ones would probably be
prompt0
andcontrol0
, which are presented in “Shift to control” by Chung-chieh Shan and also use the −F− semantics.The −F− semantics is desirable because you can implement +F−, −F+, and +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
Eff
does with multiple effects?Yes. A more direct explanation is that if you want to define versions of
shift
andreset
that are completely faithful to their usual Scheme equivalents, you can use this definition ofshift'
instead ofshift
:That is, the traditional formulation of
shift
keeps thereset
frame in place after aborting viashift
, and it also reinstalls a newreset
frame whenever the continuation is applied.https://github.com/ghc-proposals/ghc-proposals/pull/313 :party_ball:
#313 was accepted :tada:
yorp :clink: