Can someone explain call / cc in simple words?

Question

I study roulette language and try to understand what call / cc is for. Can someone explain this in simple words and give an example or two? Thanks.

Answer 1

If you have an expression (+ (* 2 3) (/ 10 2)) , the Scheme system will not evaluate everything at the same time, but partially. The order is not specified in the Scheme, but imagine this from left to right (I think Racket always does from left to right):

You do (* 2 3) , the continuation of this will be to calculate (/ 10 2) , then (+ result1 result2) . The way that the Scheme system can do this is to convert your code into Continuation of the transfer style before it is executed. 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 & at the end are the same as in the Scheme, except that as the last argument it takes a continuation. An example of one of them: (define (+& abk) (k (+ ab))) . All the rest are done that way and are considered primitive.

if you apply this and go through display or values , it will display or evaluate to 11. However, if you used call/cc , you could override this. Imagine this option:

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

In the scheme, you get an error when dividing by zero, and if this happens, you want to cancel the rest of the calculations and say that the result is infinite. The above code does this, and if a is zero, it will not summarize the results of two previous calculations. It actually acts like a goto. The version of this CPS code will 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, this allows you to encode your normal way, not CPS, like the way the computer does the actual calculation, but you get the best of both worlds, getting a continuation so you can do the same thing as if you wrote it in CPS .

Now imagine this block of code:

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

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

Just like eval , I try to keep it at an absolute minimum, and when I do this, I usually do this to get an interrupt from going computation. For example.

 (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 

More Examples I love the Matt Mights page with lots of examples on how to use the sequels.

Answer 2

Not all call/cc implementations are exactly the same, but hopefully this answer can be applied to all common options, including Racket with minor problems. This story is actually based on c built-in Unlambda .

Call metaphor / cc

You are a superhero archaeologist on a breakout in old Maya. You open an exquisitely built, perfectly preserved stone doorway in an elegant arch. But this is just a doorway that was laid on its side; there is no wall nearby, and it seems that it has never been part of the wall. Your staff receives energy from him, so you transfer him back to the laboratory for study.

In your laboratory, a large clock hangs on the wall right in front of the now vertical arch that you placed near the middle of the room. Studying the arch, you pass through it.

4:17 pm

Going through the archway, you will now notice, to your surprise, that you are holding a cubic box in your hand, large enough to put the book inside, with a cover and one luminous button. You don’t remember how you picked up such a box or saw it before. You call the assistant and ask where the box comes from. The assistant does not know. If you put the box down, the button will turn off. You pick it up again, the button lights up again. It only glows when you hold it; if the assistant picks up the box, it does not light up. In a lark you put a paper clip in a box, close the lid and press the button.

4:23 PM

Having passed through the arch, you will now notice, to your surprise, that you are holding a paper clip in your hand. You do not remember how to pick it up. Your assistant in the room, looking at you, stunned. You do not remember how your assistant enters the room. It also seems that your watch is several minutes faster.

"What just happened?" asks the assistant.

“I just walked along the arch,” you say, not quite understanding the question.

"No, no! What happened to the box?" says the assistant.

"What are you talking about?" you say grow annoyed.

...

As soon as the whole situation erupts, and you find out what this arch does, you decided to do something bold. You read aloud the current time and go through the arch.

5:30 pm

Leaving the arch, you are holding an empty box. Observing that the time is 5:30 pm, as you expected, you attach a note to the box with the inscription #1 . You put the box on the table, read the current time out loud and again go through the arch.

5:31 pm

Leaving the arch, you are holding an empty box. Observing that the time is 5:31 pm, as you expected, you attach a note to the box with the inscription #2 - use to forget . You put box number 2 inside box number 1 (it shrinks to a fraction of its size as you do this, it seems that boxes are for this purpose).

As a superhero archaeologist, you equip yourself accordingly and break into the foreign embassy of your least beloved repressive regime, breaking through its vaults and stealing paper copies of some of its carefully kept state secrets. Hong Kong action movie, bullets and fists fly. You will barricade yourself in the vault by buying precious seconds before their guards can reach you. Creating box number 1 from your bag, you fill the paper inside (together, but not inside, box number 2, which is also there), close box number 1, and just as the storage door opens, you smile, pull the pin, lower grenade and press the button.

9:45 pm

Leaving the arch, you hold an empty box, which was marked as #2 - use to forget , and documents containing the secret secret secrets of your least favorite repressive regime. You also note that the time is not 5:30 pm, as you expected, but 9:45 pm, so you will not continue your planned hacking plan. You sit down and transfer the contents of the documents to memory, and as soon as you are sure that they are completely remembered, you write the documents into the basket. Now you read aloud the current time and go through the arch.

2:00 AM

Leaving the arch, you are holding an empty box. By observing that the current time is 2:00 AM, as you expected, you will immediately mark the new field #3 - use to remember . You write yourself a short note: Allow self to forget again. At exactly 7:15 PM call police and report suspicious persons at 14th and Maple. Allow self to forget again. At exactly 7:15 PM call police and report suspicious persons at 14th and Maple. Having placed box No. 3 and a note inside box No. 2, you then press the button on box No. 2.

2:01 am

Appearing from the arch, you hold an empty box, which is marked as #3 - use to remember , and a note in your own handwriting. The time is much later than the expected 5:31 pm, so you will not continue your planned hacking plan. Following the instructions for yourself, you again go through the arch, receiving a new box, which you will name #4 - use to forget . You call the police, as you indicated in your note, not knowing why, and hear on news days later than the international spy ring was broken in your hometown.

Mission accomplished! (Assume.) From now on, you have a choice to know the information yourself, but not what you did with it; or not know the information, but know how it was used.

After all, this wonderful tool is expensive. As you continue to rely on the arch in various activities, you must do this, knowing that you will forever fragment your life, and the fragments can never be combined, except by sending messages between your many alternative selves. And a single use of boxes with buttons can lead to the irretrievable loss of many precious memories, which can be either a stratagem or a grave and tragic mistake.

Description

Passing through an arch is a call/cc operation. This leads to the creation of a new button block, which is a continuation function. Putting things in a field represents passing arguments to the continuation function. Pressing a button in a field represents a continuation function call.

Pressing the button on the box (calling the continuation function) will restore the legendary symbol (call stack with variables) to the exact state at the time the field was created (continued), that is, the moment when call/cc initially completed. Arguments passed in the sequel result from the result of the original call/cc after the stack was restored; therefore, by pressing the button, the reference symbol does not store the field, but the contents of the field.

Boxes (continuations) can be encapsulated (transferred to each other), which allows you to use call/cc as a primitive for implementing shared routines, machine states, and other advanced designs.

Continuations can also be used to quickly exit code branches in ways that would otherwise be inconvenient ("drop the grenade, press the button"), for example, instantly exit deeply embedded conventions and loops that cause side effects.

Note also that the arch is not a time machine; time never cancels itself in history, and does nothing external to the legendary character walking along the arch. (Destructive assignments, changes in heap memory, and other side effects do not change, causing the continuation function.)

Exercise: write a pseudo-code for the legendary symbol, which will lead to the fact that the correctly executed espionage plan will be described.

Answer 3

This is some class text I use in my lectures on sequels. It was originally based on PLAI , but has expanded significantly with more practical code, and also includes some examples from the Matthew Might page. (In short, many people contributed to this indirectly.) It is not very short, but it should be easy to read.

Perhaps one day SO will allow the publication of this answer, but so far there is no way to post this text here.