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
[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:
ball;throw which stashes a value in ball and then raises it;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:
(call/cc (lambda (cc) cc)) simply returns the continuation object;(let ((c ...)) ...) binds it to c;(c 3) invokes the continuation which ...3 from call/cc, which ...c to 3;(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)))
(call/cc ...) returns a continuation object as before;(let ... ...) binds it to c;(c (lambda (x) 3) invokes the continuation which ...(lambda (x) 3) from call/cc, which ...c to (lambda (x) 3);((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.