Sorry for the wait, but it's almost Christmas and I had things to do.
>>7
Incidentally, I'm that person. I'll explain why delconts are more powerful/expressive than
call/cc without mutable state (if you add mutable state in the mix, their expressive power are equivalent), and why
>>1's code breaks with
call/cc.
So, let's start.
What's a continuation?
A continuation is a kind-of-procedure-but-not-really representing what's to do next, or the future of a computation.
This is not helpful, and it's confusing, so let's make an example:
We have this code:
(+ 1 3). Assuming strict evaluation, we need to evaluate
+, then
1, then
3, and apply the resulting procedure
+ to the results of
1 and
3: (
[]s mark the piece of code currently being evaluated)
[(+ 1 3)] ; start
([+] 1 2) ; evaluate +
(#<proc> [1] 2) ; evaluate 1
(#<proc> 1 [2]) ; evaluate 2
[(#<proc> 1 2)] ; apply #<proc> to 1 and 2
3
That was pretty pointless, how is that related to continuations?
The []s represent the current evaluation point, and what's outside of them is the continuation of it.
Look at the second line,
([+] 1 2).
+ is being evaluated, and
([] 1 2) is its continuation, because, after its evaluation is done, that' how the computation will
continue.
Basically,
([] 1 2) is pretty much equivalent to
(lambda (x) (x 1 2), and the evaluation of
+ in the context
([] 1 2) is like
((lambda (x) (x 1 2)) +). Instead of returning a value, we're passing an argument to a procedure, called continuation.
Extend that idea to the whole expression, or even the whole program, and you get Continuation Passing Style, CPS for short, where every expression is in tail position, and every procedure takes an extra ``continuation'' argument.
Example:
(define (fact x) ; factorial
(if (zero? x) 1
(* x (fact (- x 1)))))
(define (fact-cps x cont) ; CPSed factorial
(zero?-cps x ; `zero?-cps' is the CPS version of `zero?',
(lambda (is-zero?) ; and `is-zero?' is the return value of `zero?-cps'.
; This procedure is the continuation of the (zero? x) expression: (if [] 1 (* x (fact (- x 1)))).
(if is-zero?
(cont 1) ; ``return'' 1 to our continuation.
(--cps x 1 ; CPSed `-'.
(lambda (x-1) ; return value of (- x 1)
; Same as before, this procedure is the continuation of (- x 1): (* x (fact []))
(fact-cps x-1
(lambda (x2) ; x2 = (fact (- x 1)), continuation: (* x [])
(*-cps x x2 cont)) ; (* x []) is in tail position, it has the same continuation of the original `fact-cps' call.
; A bad person who doesn't optimize his tail calls would have written
; (*-cps x x2 (lambda (x3) (cont x3))) instead.
)))))))
I know this is a bad explaination, so please, if you don't understand something, ask me anything.
What's call/cc?
Usually, when we code, continuations are implicit, and are only made explicit when the code is converted in CPS.
call-with-current-continuation calls a procedure with, well, the current continuation. Except that the continuation procedure given by
call/cc is special: it does not only represent the captured continuation, but, when called, it totally replaces the continuation of where it is called with the original one.
Example time:
Say we have this expression:
(+ (call/cc f) 2), and that
f is something like
(lambda (x) (set! c x) 1).
The continuation of
(call/cc f) is
(+ [] 2), or
(lambda (x) (+ x 2)) if you want.
So,
f receives a procedure
similar to
(lambda (x) (+ x 2)), stores it in
c, and returns 1.
The whole thing, now
(+ 1 2), evaluates to
3. Yay.
We have, now,
(/ (c 2) 0), where
c still holds the continuation
(+ [] 2).
The continuation of
(c 2) is
(/ [] 0). That's bad, it's a division by zero, it will fail as soon as we evaluate it, and that's right after
(c 2) returns!
But,
c is a continuation reified by
call/cc, so it will replace the continuation
(/ [] 0) with its original
(+ [] 2), the resulting expression will be
(+ 2 2), and it will return
4. No division by zero error.
That's
call/cc.
In CPS, it is implemented as:
(define (call/cc fun cont) ; cont is the current continuation
(let ((reified-cont (lambda (x new-cont) (cont x)))) ; disregard the new continuation, return `x' to the old continuation.
(fun reified-cont cont))) ; fun is given the reified continuation, and returns to the old continuation.
Example:
[code]
(define c #f)
(+ (call/cc (lambda (x) (set! c x) 1)) 2)
; =>
(call/cc (lambda (x cont) (set! c x) (cont 1))
(lambda (x) (+ x 2))) ; (+ [] 2)
; evaluate:
(let ((reified-cont (lambda (x new-cont)
((lambda (x) (+ x 2)) x))))
((lambda (x cont) (set! c x) (cont 1))
reified-cont
(lambda (x) (+ x 2))))
; evaluate:
(set! c reified-cont)
((lambda (x) (+ x 2)) 1)
; evaluate:
(+ 1 2) ; => 3, and c is now reified-cont.
(/ (c 2) 0)
; =>
(c 2 (lambda (x) (/ x 0)) ; (/ [] 0)
; c = reified-cont, so:
((lambda (x new-cont)
((lambda (x) (+ x 2)) x))
2
(lambda (x) (/ x 0))
; evaluate:
((lambda (x) (+ x 2)) 2) ; at this point, (lambda (x) (/ x 0)) is already discarded, as it was bound to new-cont.
; evaluate:
(+ 2 2) ; => 4
More in the next post.