Could someone explain call/cc in simple words?

Question

I am studying the language racket and trying to grasp what call/cc is actually for. Could someone please explain it in simple words and give an example or two? Thanks.

Brahma

Answer 1

If you have an expression (+ (* 2 3) (/ 10 2)) a Scheme system will not evaluate everything at the same time but in parts. The order is not specified in Scheme but lets imagine it's from left to right (I think Racket always do left to right):

You do (* 2 3), the continuation to that would be to compute (/ 10 2), then (+ result1 result2). The way a Scheme system can do this is by transforming your code to Continuation passing style before execution. The expression above turns into something like this:

 (lambda (k)
  (*& 2 
      3
      (lambda (result1)
        (/& 10
            2
            (lambda (result2)
              (+& result1 result2 k))))))

Now, the procedures with & in the end are the same as in Scheme except it takes a continuation as it's last argument. An example of one of these: (define (+& a b k) (k (+ a b))). All the others are done just like that and are considered primitives.

if you apply that and pass display or values it will either display or evaluate to 11. However, if you used call/cc you could override that. Imagine this variant:

(call/cc (lambda (k) (+ (* 2 3) (/ 10 (if (zero? a) (k +inf.0) a))

In Scheme you get an error when dividing with zero and if that happens you want to call off the rest of the calculations and say the result is infinite. The code above does that and if a is zero it won't sum the results from the two previous calculations.. It actually acts as a GOTO. A CPS version of that code would look something like this:

(lambda (k)
   (*& 2 
       3
       (lambda (result1)
         (zero?& a 
                 (lambda (azero?)
                   (if azero?
                       (k +inf.0) ; continuation used here
                       (/& 10
                           a
                           (lambda (result2)
                             (+& result1 result2 k))))))))) ; and here

So what does call/cc do? Well it lets you code your usual way and not CPS like how the computer does the actual computation but you get the best of two worlds by getting hold of the continuation so that you can do the same as if you had written it in CPS.

Now, imagine this code block:

(let* ((c 10)
       (r (call/cc (lambda (exit) exit))))
  (display "Hello\n")
  (cond ((zero? c) 'done)
        (else (set! c (- c 1))
              (r r))))

Here you see I return the continuation as r. The continuation is the rest of the calculations starting with setting r, then doing display ... This actually displays "hello\n" 11 times since when you call the continuation in the bottom it does the same all over again.

Just like eval I do try to keep this at an absolute minimum and when I do I usually do it to get an abort from a on going computation. Eg.

(define (lstadd1 lst)
  (call/cc (lambda (exit)
    (let loop ((lst lst))
       (cond ((pair? lst) (cons (add1 (car lst)) (loop (cdr lst))))
             ((null? lst) '())
             (else (exit #f))))))) ; not proper 

(lstadd1 '(1 2 3))   ; ==> (2 3 4)
(lstadd1 '(1 2 . 3)) ; ==> #f

For more examples I love Matt Mights page with lots of examples on how to use continuations.

Semitrailer

Answer 2

Not all implementations of call/cc are exactly the same, but hopefully this answer can apply to all common variations including Racket with little trouble. This story is actually based on the c builtin of Unlambda.

A Metaphor for call/cc

You are a superhero archaeologist on a dig at an old Mayan site. You unearth an exquisitely constructed, perfectly preserved, stone doorway in an elegant arch. But it's just a doorway, that has been laid on its side; there is no wall anywhere near it, nor does it appear to have ever been part of a wall. Your staff gets an energy reading off it, so you transport it intact back to your lab for study.

In your lab, a large clock is hanging on the wall directly in front of the now-upright arch, which you have placed near the middle of the room. In examining the arch, you walk through it.

4:17 PM

After walking through the arch, you now notice, to your surprise, that you are holding a cubic box in your hand, large enough to put a book inside, with a lid and a single glowing pushbutton. You don't remember picking up such a box, or having seen it before. You call in your aide and ask where the box came from. The aide does not know. If you put the box down, the button stops glowing. You pick it up again, the button glows again. It only glows when you hold it; if the aide picks up the box it does not glow. On a lark, you put a paper clip into the box, close the lid, and push the button.

4:23 PM

After walking through the arch, you now notice, to your surprise, that you are holding a paper clip in your hand. You don't remember picking it up. Your aide is in the room, staring at you dumbfounded. You don't remember your aide coming into the room. It also seems that your clock is a few minutes fast.

"What just happened?" asks the aide.

"I just walked through the arch," you say, not really understanding the question.

"No you didn't! And what happened to the box?" says the aide.

"What are you talking about?" you say, growing annoyed.

...

Once that whole situation plays out, and you learn what this archway does, you decide to do something bold. You read aloud the current time, and walk through the arch.

5:30 PM

Emerging from the arch you hold an empty box. Observing that the time is 5:30 PM as you expected, you attach a sticky note to the box labeled #1. You put the box on the table, read aloud the current time, and walk through the arch again.

5:31 PM

Emerging from the arch you hold an empty box. Observing that the time is 5:31 PM as you expected, you attach a sticky note to the box labeled #2 - use to forget. You place box #2 inside box #1 (it shrinks to a fraction of its size as you do this; it seems the boxes are designed for this).

Being a superhero archaeologist, you then suitably equip yourself and break into the foreign embassy of your least favorite oppressive regime, breaching its vaults and stealing paper copies of some of its closely kept state secrets. Hong Kong action movie stuff, bullets and fists flying. You barricade yourself in the vault, buying precious seconds before their guards can get to you. Producing box #1 from your bag, you stuff the papers inside (along with, but not inside, box #2 which is also in there), close box #1, and just as the vault door is blown open, you smile, pull the pin, drop the grenade, and hit the button.

9:45 PM

Emerging from the arch you hold an empty box, which has been labeled #2 - use to forget and papers containing sensitive state secrets of your least favorite oppressive regime. You also note that the time is not 5:30 PM as you expected, but 9:45 PM, so you do not continue with your intended break-in plan. You sit down and commit the contents of the documents to memory, and once you are sure you have them fully memorized, you burn the documents in the trash can. Now you read aloud the current time and walk through the arch.

2:00 AM

Emerging from the arch you hold an empty box. Observing that the current time is 2:00 AM as you expected, you promptly label the new box #3 - use to remember. You write a quick note to yourself: Allow self to forget again. At exactly 7:15 PM call police and report suspicious persons at 14th and Maple. Placing box #3 and the note inside box #2, you then hit the button on box #2.

2:01 AM

Emerging from the arch you hold an empty box, which has been labeled #3 - use to remember, and a note in your own handwriting. The time is much later than the expected 5:31 PM, so you do not continue with your intended break-in plan. Following your instructions to yourself, you walk through the arch again, obtaining a new box which you label #4 - use to forget. You call police as you instructed in your note, not knowing why, and hear in the news days later than an international spy ring was broken up in your hometown.

Mission accomplished! (You assume.) From this point on, you have the choice to know the information itself, but not what you did with it; or not to know the information, but to know how it was used.

In the end, this wonderful tool comes at a price. As you continue to rely on the archway in various activities, you must do so with the knowledge that you are forever fragmenting your life, and the shards can never be unified except by sending messages between your many alternate selves. And a single use of the pushbutton boxes can lead to irrecoverable loss of many precious memories, which can either be a stratagem or a grievous and tragic mistake.

Explanation

Walking through the arch represents a call/cc operation. Doing so results in a new pushbutton box being created, which represents a continuation function. Putting things into the box represents passing arguments to the continuation function. Pushing the button on the box represents calling the continuation function.

Pushing the button on the box (calling the continuation function) causes the storied character (call stack with variables) to be restored to the exact state at the time the box (continuation) was created, i.e. the moment that call/cc originally completed. Arguments passed to the continuation become the result value of the original call/cc after stack restoration; this is why upon pressing the button, the storied character holds not a box but the contents of the box.

Boxes (continuations) may be encapsulated (passed to each other), allowing the use of call/cc as a primitive to implement co-routines, state machines and other advanced constructs.

Continuations may also be used to easily escape from branches of code in ways that are otherwise inconvenient ('drop the grenade, hit the button'), such as instantly exiting from deeply nested conditionals and loops that cause side effects.

Note also that the arch is not a time machine; time never reverses itself in the story, nor does anything external to the storied character walking through the arch. (Destructive assignments, changes to heap memory and other side effects are not reversed by calling the continuation function.)

Exercise: Write pseudocode for the storied character to follow that will result in the correctly executed espionage plan described.

Henequen

Answer 3

This is some class text I'm using in my lectures on continuations. It was originally based on PLAI, but much expanded with more practical code, and also incorporates some of the examples from Matthew Might's page. (In short, many people contributed to this indirectly.) It's not really short, but it should be easy to read.

Maybe one day SO will allow posting that as an answer, but for now, there's no way to put that much text here.

Shalloon

Answer 4

If you're familiar with other "normal" programming languages, one way to understand the continuation is as a function that does the job of "return".

Supposing we're calculating (+ (* 3 3) (* 4 4)), then the act of returning to the point after computing (* 3 3) is seen visibly in the expression --

(+ (call/cc (λ (return) (return (* 3 3)))) (* 4 4))

In other words, the function that call/cc passes to the lambda represents the act of returning to the expression the call/cc is embedded in.

Having explicit access to that "returning function" as a value (i.e. as a "reified continuation") lets us construct complex flows of control.

Whatley