9

Back in the day, I thought I understood call/cc. These days I'm seeing a lot more references to "delimited" continuation operators, which seem to come in pairs like shift/reset, prompt/control, and sometimes more exotic ones. But I haven't seen a clear explanation anywhere of the basics, so

  1. What do they do?
  2. What are they for?
  3. What might make one set of operators better for a particular language/context/purpose than another?
Flux
  • 9,805
  • 5
  • 46
  • 92
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 5
    There's like a thousand pages of writing on this topic [on Oleg's website](http://okmij.org/ftp/continuations/) that might get you started. – Daniel Wagner Aug 27 '21 at 02:25
  • 2
    @DanielWagner, I've actually run into that before but had no idea where to start. Suggestions? – dfeuer Aug 27 '21 at 02:36
  • 6
    I'd start with the one labeled "introduction". (As of time of writing, this uniquely identifies an article there.) – Daniel Wagner Aug 27 '21 at 02:36
  • 2
    I guess everyone interested in the topic knows Oleg's great section on his website. But a more structured, easier accessible summary would be very helpful to start with. I'd find it particularly interesting how delimited conts can be used to implement algebraic effects. This would probably shed some light on how they work in general. –  Aug 27 '21 at 08:58
  • @DanielWagner You can post that into an answer – Xwtek Aug 28 '21 at 09:02
  • @Xwtek No, SO has explicit rules saying that text of the form "check out the answer on this other site over here" is not an answer. A good answer would be a self-contained text. (And, to talk off to the side for a moment: I think the reason there hasn't been one written is that the topic is, like, huge, and so writing a solid answer that covers all the questions in a satisfactory way is a monumental undertaking. You can't boil 1000 pages of text -- on just **one** of the styles of delimited continuations! -- down to something small enough for SO easily.) – Daniel Wagner Aug 28 '21 at 14:44
  • What is the reason for having voted to close this topic!? – alinsoar Aug 29 '21 at 20:18
  • 2
    @alinsoar It's a *really* broad question. – chepner Aug 29 '21 at 20:52
  • Yes, and the question can still be closed until it is edited down to be more focused, or a new, more focused question can be asked. – chepner Aug 29 '21 at 22:16
  • 1
    @chepner when a topic is not clear it is hard/impossible to formulate focused questions. The question is clear and very useful for many. – alinsoar Aug 29 '21 at 22:22
  • 1
    Neither of which is *sufficient*. Please read https://stackoverflow.com/help/dont-ask. Any one of the three question asked here could, at the very least, be a standalone question. – chepner Aug 29 '21 at 22:36
  • @chepner I am highly interested about the topic and couldn't formulate a better question, I am waiting for competent programmers to enlight. So s.o. rules should be reformulated. – alinsoar Aug 29 '21 at 23:08
  • That's a discussion for meta.stackexchange.com. – chepner Aug 29 '21 at 23:50
  • 3
    @alinsoar I'm not sure I agree with this question being closed either (although the subquestion 3 is probably too broad, yeah). But SO is not required to suit all questions; "I'm interested in this question, so if SO rules don't allow it the rules should be reformulated" isn't really a good argument. – Ben Aug 30 '21 at 00:02

1 Answers1

3

I have read a few articles and I can explain the idea. So I do not know how to implement it and how to use it in practical way, but I understood the main idea.

Suppose you have a call like

 (f (h (g x)) 2)
^     << scheme undelimited cont. captures from here

and g captures the continuation.

  1. In scheme, if you call call/cc within g, it will copy all the execution stack starting from the top-level (starting from the point where f was invoked) -- in case you have many expressions at the top level each one will have its own stacklet and invoking the saved continuation will stop at the top level (so, in the above expression, it will stop after f and at that point it has the value of f).

  2. If you want the continuation to be captured from inside g up to the exit point of h, and each invocation of the continuation to return a value to f it is enough to capture the stack starting from the point of invocation of h, not the full stacklet of the invocation of f, so you want to tell the system that calling a call/cc-like function not to duplicate the rest of computation from the top level, but from a given point, and return each time a value at that point:

    (f (h (g x)) 2)

   ^        << delimited cont. captures from here

    In this case, you instrument the system, something like:

    (f (shift (h (g x)) 2))

    and call the reset inside g, in the place where you would need to capture the continuation.

  3. Delimited continuations can be simulated by undelimited continuations, but I think it is more practical to be able to use delimited, in some cases. So you cannot do it in scheme in a practical way of duplicating the stack only in the region of interest, it obliges you to copy a full stacklet (I say "stacklet" instead of stack, as the real stack is bigger, and the outside chained stacklets represent the continuation of the initialization code that is executed when you quit your code).

These are a few ideas that I glaned from the papers I have read. I am also interested to hear a more detailed answer.

alinsoar
  • 15,386
  • 4
  • 57
  • 74
  • are you sure it's `shift` on the delimiter and `reset` from inside `g`? I'm pretty sure it's the other way around. – Moth Apr 28 '22 at 10:14
  • @Moth it may be possible, never wrote such code, only read papers to see how *try-raise-finally* could be implemented, etc. – alinsoar Apr 28 '22 at 10:47
  • yes, `reset` places the delimiter and `shift` captures the continuation. you can think of `shift` as the delimited equivalent of `call/cc`. cf https://docs.racket-lang.org/reference/cont.html#%28form._%28%28lib._racket%2Fcontrol..rkt%29._reset%29%29 – Moth Apr 28 '22 at 11:22