Pycket has the fastest implementation of delimited control that I know. Pycket's continuations are fast because it uses heap-based continuation frames. SML/NJ continuations are fast for the same reason. And Pycket gets all of Racket's control operators, because it directly implements the ICFP'07 model.
As long as your program is just manipulating continuations, then heap-based frames are the way to go. But if your programs spends a lot of time in more conventional control patterns, then further work is needed to make heap-based frames perform well overall. Pycket relies on a tracing JIT to make its heap-based on model run fast overall, while SML/NJ relies on compile-time analysis. For an implementation that relies on a representation choice instead of tracing or analysis, Racket CS's implementation of delimited control is the state of the art --- mostly by building on Chez Scheme's implementation of continuations. For details, you'll want to go back to "Representing Control in the Presence of First-Class Continuations" Hieb, Dybvig, and Bruggeman (PLDI 1990) The Rumble layer on top of that for delimiting uses metacontinuations. It's probably about the same as implementations in "Final Shift for call/cc: a Direct Implementation of Shift and Reset" Gasbichler and Sperber (ICFP 2002) but I haven't yet gone back to check or to see how that compares to the approach in "A Mondaic Framework ...". Rumble's tail correction to metacontinuations is probably essentially the same as in "A Mondaic Framework ...". In any case, see "racket/src/cs/rumble/control.ss". The Racket CS implementation of continuation marks benefits from direct support in Chez Scheme for "continuation attachments". Attachments are like marks, but with just one implicit key, so a key+value layer is implemented in Racket CS by installing a dictionary as the single attachment value. The implementation of attachments in Chez Scheme exploits the representation of continuations to make mark operations inexpensive. I'll send you more details separately. For a monadic implementation, "A Mondaic Framework ..." is state-of-the-art as far as I know. See also Oleg's variant (http://okmij.org/ftp/continuations/implementations.html). I don't know what it would meant to implement delimited control more primitively in a lazy language. At Sat, 30 Nov 2019 22:21:25 -0600, Alexis King wrote: > If I may ask one more question of you, Matthew: following up from the thread > on `dynamic-wind`, I would love to pick your brain on what you think are the > state of the art implementation techniques for delimited continuations. When > I > went looking for resources, I mostly found two papers: > > “A Monadic Framework for Delimited Continuations” by Dvbvig, Peyton Jones, > and > Sabry (JFP 2007) > > “Adding Delimited and Composable Control to a Production Programming > Environment” by Flatt, Yu, Findler, and Felleisen (ICFP 2007) > > Both these papers are extremely helpful, but they’re also both 12 years old. > Moreover, I remember reading somewhere (perhaps from Sam?) that the 3m > implementation of continuations is relatively slow compared to the > implementation by Chez Scheme. Especially given your recent work on Racket on > Chez, I imagine it’s something you’ve thought about a lot, so I’m curious if > you have any pointers about what you consider to be the most desirable > implementation approach. > > Naïvely, it seems hard to get away from the need to maintain an annotated > stack of frames, grouped into chunks separated by prompts, but I wonder if > there are any tricks or optimizations that seem to win big in practice. > Likewise, it would be helpful to know if any optimizations ended up not > panning out. My context here is a project to implement efficient delimited > control in Haskell, so in practice I might not have a ton of control at the > lowest level, but that’s okay—I’m still interested in understanding the > low-level details in case they might inform a change that could be made to > GHC > itself. > > I’m sure a fully detailed explanation would take more time than I can > reasonably ask you to give, so some high-level comments and pointers to other > resources is more than fine. :) I’m mostly just trying to get a handle on > where to start—I want to avoid choosing a path that leads to a dead end. > > Thanks, > Alexis > > -- > You received this message because you are subscribed to the Google Groups > "Racket Developers" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/racket-dev/7559EBB2-4B34-49D1-921A-21C0D93B3E > BE%40gmail.com. -- You received this message because you are subscribed to the Google Groups "Racket Developers" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/5de3d289.1c69fb81.c9267.65a8SMTPIN_ADDED_MISSING%40gmr-mx.google.com.
