Understanding Implementation of call-with-continuation

Question

I'm trying to understand a scheme procedure written in python code:

def callcc(proc):
    "Call proc with current continuation; escape only"
    ball = RuntimeWarning("Sorry, can't continue this continuation any longer.")
    def throw(retval): ball.retval = retval; raise ball
    try:
        return proc(throw)
    except RuntimeWarning as w:
        if w is ball: return ball.retval
        else: raise w

It is from this tutorial: http://norvig.com/lispy2.html.

How does the above work? What does ball mean, and why would a proc(edure?) be called with a throw as its argument value? And what does the comment "escape only" mean?

---

By he way, here is my current (probably misguided) understanding of continuation as it applies to python, which is similar to passing a function with a yield:

def c(func, *args, **kwargs):
    # func must be a coroutine
    return func(*args, **kwargs)

def inc(x=0):
    while True:
        yield x
        x += 1

>>> ct=c(inc, 3)
>>> next(ct)
3
>>> next(ct)
4

Answer 1

[I'm not sure if this answer is more useful than the other one: I started it before the other one and then got distracted.]

The thing you really want to be able to achieve in any language is the ability to painlessly escape from some context back up to a given point. This is obviously something which underlies exception-handling, but it's much more general than that. let's say you've got some search procedure:

(define (search-thing thing)
  (if (thing-is-interesting? thing)
      <return from search routine>
      (search-children (thing-children thing)))

(define (search-children children)
  ... (search-thing ...) ...)

Sometimes you can naturally express this so that when you've found the thing you just return and it percolates all the way up. Sometimes that's much harder. So what you'd like is some way of being able to say 'here is a place in the program and here is a little machine which will return to that place'. So in some hypothetical language:

(block here
  ...
  (return-from here ...)
  ...)

Here this block construct establishes a location and return-from returns from a block.

Well, what do you do if the block you want to return from isn't lexically visible to you? You can wrap the return-from in a function:

(block here
  ...
  (my-search-function (lambda (v) (return-from here v)) ...
  ...)

And this is enough to do this 'escape to a given point' thing: if you call this procedure within the dynamic extent of the block, it will return its argument from the block, immediately. Note that what it doesn't do is somehow search up the call stack looking for the right place to return from: it just goes directly to the block and returns a value from it.

Well, a more natural way to do this, perhaps, would just be to do away with all this making-a-block thing and go straight to the procedure thing: just have a procedure which takes a procedure as an argument and calls it with this escape-procedure I made above. That's what call/cc is:

(call/cc (lambda (escape)
           (my-search-function escape ...))

Now if my-search-function or any function it calls calls escape then it will immediately return its argument from the call/cc form.

Python has no construct really like this (disclaimer: I may be wrong about this as I am in the process of replacing the Python I knew three years ago with more interesting things). return in Python always returns from the lexically innermost function: you can't say return-from to return from a function outside the lexically innermost one (there is nothing like nonlocal for returns). But you can simulate it using exceptions, because exceptions have identity. So if you make an exception then you can wrap it in a function which just raises that exception which gets passed into your code. Calling this function will just raise that exception (not one of the same class: that actual object), stashing a value in it. Then you establish a try ... except: block which checks if the exception it's just caught is the one just created, and if it is the same object, it returns the value it knows is stashed there. If it's not it just reraises it.

So this is a hack because if you have lots of these things nested lots of handlers get to look at it and reject it until it finds the one it belongs to. But it's an acceptable hack for this purpose. In particular it means that you can pass a function into another function which, if it calls it, will return a value from where you created it and abandon any intermediate computation.

This idiom like a very structured use of GOTO: you are allowed to do a nonlocal transfer of control, but only to a point 'above' you in the chain of function calls (as is well known call stacks always grow downwards: this is because it's much easier to build structures which are stable under tension than compression, and structural failures also don't damage the part of the stack above the failure).

And this is exactly what the Python sample code does:

1. it creates an exception, ball;
2. it creates a procedure throw which stashes a value in ball and then raises it;
3. it then calls proc with this throw procedure as its argument, (returning the value of the call to proc in the case that it does return), wrapped in a little try: ... except: ... block which checks for this specific exception passing upwards through it, and if it finds it returns the value throw stashed in it.

So you might use this, for instance, like this:

def search(thing):
    callcc(lambda escape: search_with_escape(escape, thing))

def search_with_escape(escape, thing):
    ...
    if all_done_now:
        escape(result)
    ...

Here search_with_escape implements some elaborate search process, which can be abandoned by calling escape.

---

But of course that's only half of what continuations let you do in Scheme. Because once you've got this procedure object which will return from somewhere, then, well, it's a procedure: it's a first-class object which you can return and then call later if you want. In our hypothetical language what should this do:

(let ((c (block foo (lambda (v) (return-from foo v)))))
  (funcall foo 3))

Well, in our hypothetical language (which, as you can see, is a Lisp-2) that's a run-time error, because the moment control passes out through the block form the return-from becomes invalid, so although I have this procedure it's no longer any use.

But that's horrid, right? How do I know I can't call this thing? Do I need some special 'it is OK to call this here' predicate? Why can't it just do the right thing? Well, the Scheme people were feeling their oats and they made it so that the Scheme equivalent does work:

(let ((c (call/cc (lambda (cc) cc))))
  (c 3))

Well, when I say 'does work' it's still a runtime error, but for a quite different reason: you are allowed to call the thing which I called an 'escape procedure' and it will dutifully return a value from the form that made it, wherever it is. So:

1. (call/cc (lambda (cc) cc)) simply returns the continuation object;
2. (let ((c ...)) ...) binds it to c;
3. (c 3) invokes the continuation which ...
4. ... returns (again) 3 from call/cc, which ...
5. ... binds c to 3;
6. and now you try to invoke (c 3)which is an error.

these runtime errors you need to make it into something like this:

(let ((c (call/cc (lambda (cc) cc))))
  (c (lambda (x) 3)))

1. (call/cc ...) returns a continuation object as before;
2. (let ... ...) binds it to c;
3. (c (lambda (x) 3) invokes the continuation which ...
4. ... returns (lambda (x) 3) from call/cc, which ...
5. ... binds c to (lambda (x) 3);
6. and now you call ((lambda (x) 3) (lambda (x) 3)) which returns 3.

And finally

(let ((c (call/cc (lambda (cc) cc))))
  (c c))

which I am not going to try to explain.

Answer 2

Do you understand what a continuation is? callcc(proc) says to call the function proc with a single argument called "the continuation". If somewhere later in your code, you call this continuation with an argument, it will return whatever value the continuation was called with back to whoever called callcc.

throw is that continuation. When you call the continuation with an argument, it raises an exception, and then pops the stack until it finds the precise call to callcc that created it. And then returns a value.

A real implementation of callcc can actually do a lot of things that this implementation can't do. The continuation outlives the stack. But this is a good start.

Answer 3

The other questions are more correct, but I'm posting a working example in python that can be used for testing:

def callcc(function):
    bail = RuntimeWarning("My custom bail.")
    def escape_function(retval): 
        bail.retval = retval; # adding our functions return value into the exception itself
        raise bail
    try:
        # this will call the function and the escape function RAISES bail 
        # so it'll never return
        return function(escape_function)
    except RuntimeWarning as w:
        if w is bail: 
            retval = bail.retval
            print("About to return value of %s..." % retval)
            return retval
        else: 
            raise w

def countdown(n):
    # the function we are passing to callcc is `countdown_with_escape`
    # countdown_with_escape will later be called by callcc with the 'throw' as the escape function
    return callcc(lambda escape_function: countdown_with_escape(escape_function, n))


def countdown_with_escape(escape_function, n):
    while True:
        print (n)
        if n == 9:
            escape_function(n) # this passes '9' as the retval to the escape function
        n -= 1

And running it:

x = countdown(20)
print ('Done with value: %s' % x)

20
19
18
17
16
15
14
13
12
11
10
9
About to return value of 9...
Done with value: 9