All you need is call/cc (2013)

[daanx]

The modern way of call/cc and shift/reset is using Effect Handlers instead [1].

If you are interested in this, Ningning Xie and I give a tutorial about effect handlers (and more) at ICFP'21 tomorrow (Thursday 12:30 EST): <https://icfp21.sigplan.org/details/icfp-2021-tutorials/5/Pro...>

[1] <https://koka-lang.github.io/koka/doc/book.html>

[kazinator]

I'm not convinced that effect handlers are other than (at most) just a different name for delimited continuations.

[rscho]

Interesting! Can one have effect handlers in an untyped language such as scheme ?

[Koshkin]

This has reminded me of "closures are poor man's objects; objects are poor man's closures."

[b3morales]

Indeed; a classic hacker koan. For the reader's reference: http://wiki.c2.com/?ClosuresAndObjectsAreEquivalent

[yodsanklai]

This was a "aha" moment for me, realizing objects and closures were the same thing.

[tempodox]

More material about this fascinating topic:

http://okmij.org/ftp/continuations/

Has many articles and some code in OCaml, Haskell, Scheme.

[dharmab]

Slightly OT: Is the title a reference to "All You Need Is Kill", the source material for the Tom Cruise movie "Edge of Tomorrow"?

[unclesaamm]

I'm guessing it's more likely, All You Need is Love, the Beatles song.

[gpderetta]

somehow I have no issues understanding call/cc, but shift reset has never clicked for me.

[convolvatron]

I think this is really interesting. I'm in the same boat. and its easy to dismiss the delimited people as being deluded. but a lot of highly developed people think shift/reset is _alot_ easier to work with.

I can understand the basic case...but its totally unclear for me how to compose them.

this is kind of a fundamental issue about language development...apparently we can get used to all sorts of terrible ideas - which makes evaluating them quite difficult.

[the-smug-one]

The reduction rules copied from Racket's docs:

    (reset val) => val
    (reset E[(shift k expr)]) => (reset ((lambda (k) expr)
                                         (lambda (v) (reset E[v]))))
      ; where E has no reset

E is the current-continuation of the expression, and the comment is an invariant to be held.

And I think call/cc is this:

E[(call/cc k expr)] => ((lambda (k) expr) (lambda (v) E[v]))

So imagine a stack like this:

g

h

call/cc my-fun

this captures the whole stack.

And now imagine:

g

reset

h

shift my-fun

this only captures h (see how it moves the E in the reduction rules and wraps it in reset). So if I try to store k from shift and call it at a later time it won't reach g, but doing the same with call/cc it would reach g.

[dleslie]

I understand it as: shift captures a continuation scope, and reset defines a scope in which a captured continuation can be released.

[oshiar53-0]

You can basically think of call/cc as subroutine + return/throw (break out of control structures), and delimited continuations as yield + next/send in Python.

Of course this explanation is heavily simplified.

[zzo38computer]

Another variant is "law of excluded middle" continuations. It gives you a function, but when you call that then it will go back and give you the value passed instead. You can implement this in terms of call/cc and vice-versa.

[threepio]

From the article:

> The magic is that all Scheme code, by virtue of supporting the capture (and unwind) of delimited continuation

Is that true? I thought Racket was the only Scheme (and maybe the only language in general) that supported delimited continuations.

[pkhuong]

You can implement delimited continuations with regular call/cc and a mutable cell. Of course, like all abstractions based on raw call/cc, it's not modular: you can't do that and use the result inside, for example, a multitasking scheduler that itself uses raw call/cc as well.

http://okmij.org/ftp/continuations/against-callcc.html#traps

Closer to your point, there are a few other implementations that offer delimited continuations natively. See https://wingolog.org/archives/2010/02/26/guile-and-delimited... for a 11 year old post on adding them to guile scheme.

[rscho]

Nope, there are others. Prolog, for example:

https://www.swi-prolog.org/pldoc/man?section=delcont

[martinflack]

I found this fascinating but I need an ELI5. ;-)

[dragontamer]

call/cc is a widget from Scheme / Lisp is a glorified come_here statement (where "come_here" is roughly the exact opposite of a "goto" statement). Its gloriously complicated but its applications are seemingly endless.

call/cc calls function "f" with a "come_here" label. Later, if you call the label, you return to the "come_here" point. call/cc saves off the stack-frame, so the "come_here" executes exactly as before (all local variables remain the same as they were before).

------

In C++ (call/cc doesn't exist, but we can imagine it in C++ lambdas)

    int f(auto come_here){
        come_here(25); // call the "come_here" function with the parameter 25
    }

    ...

    int x; 
    x = call/cc(f);
    // x now equals 25, because f called come_here with 25.

We can imagine the "come_here" function to be the exact line of code "x = call/cc". Now funny things can happen if you do ... funny things.

    int g(auto come_here){
        some_global_variable = come_here; // Yeah, lets store this come_here label off for later.
        return 0; // Notice, come_here hasn't been called yet. Return 0 normally.
    }

    int x; 
    x = call/cc(g); // defaults to the 0, for the "Return 0" in g.

    if(x < 100){
        some_global_variable(x+1); // Loop back to the x=call/cc command, and set x+1.
    }

Look Ma, I created an overly complicated while loop!

---------

EDIT: Now for fun, try _writing_ try, catch, finally statements (from Java). By saving off the right labels in the right order, you can experiment with try/catch, or other complicated maneuvers (ex: the "Ambiguous" operator, often named "amb").

This call/cc exists because scheme is catering itself as a meta-language. A language to build other languages out of.

[Twisol]

There are two important ideas to pick up here, I think. First, functional programming prefers a reduction-based model of computation: the whole program text represents the current state of the program, and a "step" of computation corresponds to simplifying ("reducing") the expression in a well-defined way. Second, `call/cc` adds a novel reduction rule that behaves a bit like function application, but looks a bit backwards. (`shift` and `reduce` then generalize the basic idea, but use the same machinery.)

In detail: Consider a program `fib 2`, which simply computes the third Fibonacci number and then exits. We can define `fib` like so (using Haskell-y syntax, which I find a little lighter for this purpose):

    fib n = fib' n 0 1

    fib' 0 a b = b
    fib' n a b = fib (n - 1) b (a + b)

If we run this program, what do the individual steps look like?

      print (fib 2)
    = print (fib' 2 0 1)              -- Substitute the definition of fib
    = print (fib' (2 - 1) 1 (0 + 1))  -- Substitute the second clause of fib'
    = print (fib' 1 1 1)              -- Simplify - and + (technically, this is two steps)
    = print (fib' (1 - 1) 1 (1 + 1))
    = print (fib' 0 1 2)
    = print 2                         -- Substitute the first clause of fib'
    = ()

This isn't just an analogy; this is exactly how an unoptimized interpreter could fully implement a simple functional language. There's no need for an actual call stack when evaluating this program: the program text itself describes "what to do next" (which is the point of a call stack).

Now, what does `call/cc` do? Well, remember what function application does: we take something like `(\x. FOO) A` and substitute `A` into `FOO` where ever `x` appears, no matter how deep into the program it is (unless it's shadowed, i.e. not the same `x`). We could write this as `apply (\x. FOO) A` if we wanted, although by syntax rules we know that the first value in a call is the function to call. (The capitalized names could be entire other expressions, whereas `x` is just a variable name.)

Similarly, if the whole program looks like `A (call/cc \x. FOO)`, we substitute `\y. A` into `FOO` wherever `x` appears (unless it's shadowed)`. It's a weird kind of function call, where the function is nested inside `call/cc` like normal, but the argument is everything outside `call/cc`. And since `A _` has got a value-shaped hole where the `call/cc` was, we know that if `FOO` is going to use it, it needs to provide it a value -- hence why we substitute `\y. A`, not just `A`. (So we have to fill the hole with the new variable name `y`.)

      print (call/cc (\x. x 42))
    = (\x. x 42) (\y. print y)    -- `\y. print y` is equivalent to `print`,
    = (\y. print y) 42            --   so I'll elide this expansion next time. 
    = print 42

This example seems kind of useless -- call/cc did nothing! But what if we had more values to return than just `42` -- what if we had a whole bunch of things, and we wanted to run the same processing for all of them?

      print (call/cc (\x. x 42 >> x 101 >> x 0))
    = (\x. x 42 >> x 101 >> x 0) print
    = print 42 >> print 101 >> print 0

(`>>` is just a Haskell operator for sequencing, like `;` in C or Java.)

Now we've replicated the rest of our program based on each of the three values returned by the inner function. It's like we've bifurcated (trifurcated?) our program into multiple independent programs that continue from where the original program left off. (You might know that `fork` in Linux returns a different value depending on whether you're in the original process or in the spawned child process. This is very similar!)

But what if we don't want to do everything in our program multiple times? What if we just want to do some of it for each value, but join everything back together at the end for some final processing? Well, `shift` and `reset` let you do that. The `shift` operator slots in where `call/cc` was, but you now get to choose how much of the rest of the program to replicate by placing a `reset` somewhere else in the program. You can wrap the whole program in `reset` to get the same behavior as `call/cc`, or you can scope it to a smaller portion:

      (reset (print (shift (\x. x 42 >> x 101 >> x 0)))) >> print "Done"
    = ((\x. x 42 >> x 101 >> x 0) print) >> print "Done"
    = (print 42 >> print 101 >> print 0) >> print "Done"

(We definitely didn't want to print `Done` three times, right?)

None of the program's behavior needed call/cc or shift / reset. They're fundamentally rewriting rules that let us give such a program a different form. Sometimes the forms we can achieve with call/cc are more readable or provide better modularity. Sometimes they don't (so we shouldn't use them!).

Shift and reset let you write your own coroutine system like it was nothing, though, so it's certainly not without merit :)