I have been trying to figure out continuations after a recent question got me interested in them again. I stumbled back onto Matt Might's voluminous blog, and saw this entry, that had this function:
(define (current-continuation)
(call/cc (lambda (cc)
(cc cc))))
What in the world is (cc cc) doing? Perhaps it is like a bookmark: I am calling the current continuation with itself.
The (cc cc) is unnecessary. If you rename cc to return, then it's (return return), so you're just returning the return continuation. But you could just return it instead. 
(define (current-continuation)
(call/cc (lambda (return) return)))(not an expert on continuation, but here's the way I see it.)
Whenever you invoke (cc <X>), you replace (call/cc ...) with <X>. So calling (current-continuation) returns <X>, which happens to be cc itself. Here calling (cc ...) short-circuits the (call/cc ...) block, as in the (display "But not here.\n") example in the blog bost.
With @ryanc's code, it's a little different: cc is not invoked, but cc is the value returned at the end of the call to (call/cc ...), hence without short-circuiting it.
@ryanc and @Laurent.O have already good answers.
I'd like to provide a different perspective, i.e. you can implement current-continuation by (call/cc call/cc):
(define (current-continuation)
(call/cc call/cc))
For example,
(define *k* #f)
(define (current-continuation)
(call/cc call/cc))
(let ()
(printf "111\n")
(let ((k (current-continuation)))
(printf "222 k=~a\n" k)
(set! *k* k))
(printf "333\n"))
(*k* 42)
;; 111
;; 222 k=#<procedure>
;; 333
;; 222 k=42
;; 333
It works as the same as @ryanc and Matt Might's version.
You can even implement current-continuation by ((call/cc call/cc) call/cc ) or (call/cc (call/cc call/cc)), they are all the same, because (call/cc call/cc) is a fixed-point of call/cc.
However, what about ((call/cc call/cc) (call/cc call/cc))? Is it the same?
The answer is no, it loops ⊥.
You may ask about how to reason about these call/cc trees? It seems hard to predicate the behavior if someone randomly composes these call/cc trees.
The answer is surprisingly easy:
These call/cc trees can be only divided into three classes to describe their behavior:
call/cc alone has a behavior we will call C.
The self-extraction behavior of (call/cc call/cc) we’ll call E.
The infinite loop we’ll call ⊥.
Thus we have multiplication table:
| C | E | ⊥ | |
|---|---|---|---|
| C | E | E | ⊥ |
| E | E | ⊥ | ⊥ |
| ⊥ | ⊥ | ⊥ | ⊥ |
So you can think of call/cc trees as some sort of algebra, although it doesn't seem to have very interesting properties (it has commutative, but no associative, no identity, has zero which is looping).
Source: (call/cc call/cc) and friends by Pavel Panchekha
A piece of caution when using call/cc at the module top-level though: it may not behave as you expect. This works as you'd expect:
#lang racket
(let ()
(define mycc #f)
(define i 0)
(call/cc (λ (cc) (set! mycc cc)))
(set! i (+ i 1))
(displayln i)
(when (< i 5)
(mycc '_)))
; prints 1 2 3 4 5
but not this:
#lang racket
(begin
(define mycc #f)
(define i 0)
(call/cc (λ (cc) (set! mycc cc)))
(set! i (+ i 1))
(displayln i)
(when (< i 5)
(mycc '_)))
; prints 1 '_
Thanks folks, I appreciate the answers!
So, @chansey97, the page by Panchekha named the continuation around the call/cc as v@(...). I'm not sure what he meant by representing the continuation as k@v. The next paragraph attempted to show what he was getting at:
a@(call/cc call/cc)
a@(call/cc k@a)
This is obviously an entirely different question, but what happened in the transformation in the second line? Oh, I think I get it, he's just naming the continuation - like a name for whatever is usually a lambda in that spot.
This k@v is a notation used by the author, which represents the reification of execution context (or continuation) v@(...). You can think of a execution context as a call stack in imperative language, but that is not a good way to think. The good way is to think is as a textual representation.
For example,
(+ 1 (+ 1 (+ 1 ?)))
This text above represents a continuation around the ?, where ? is a expression. We say that (+ 1 (+ 1 (+ 1 ?))) is the continuation of ?.
In the author's blog, his v@(...) denotes some continuation, e.g. (+ 1 (+ 1 (+ 1 ?))), and k@v represents the reification of v@(...) . Notice that the continuation (+ 1 (+ 1 (+ 1 ?))) is very like a procedure and ? represents a place to plug in a value. The reification of v@(...) is exactly a such procedure (with effect).
I have relabeled the call/cc to make it clearer:
a@(call/cc1 call/cc2) ; line1
=> a@(call/cc2 k@a) ; line2
=> (k@a k@a) ; line3
=> k@a ; line4
The line1-> line2 just means 2 step:
call/cc1 capture the continuation a@ and reify it to k@acall/cc2 to k@a.P.s. You may also wonder what happened after that.
Alas, I think the author made a small bug here (although it does affect the final result of that blog), it should be written:
a@(call/cc1 call/cc2) ; line1
=> a@(call/cc2 k@a) ; line2
=> a@(k@a k@a) ; line3
=> a@k@a ; line4
The line2-> line3 means:
call/cc2 capture the continuation a@k@a, then apply k@a to k@a.The line3-> line4 means:
a@k@a to the context of the left k@a, thus result a@k@aIf we following the author's deriving, i.e. a@(call/cc1 call/cc2) => k@a, then (call/cc call/cc) will throw away the current context, but obviously it's not the case:
(let ()
(printf "111\n")
(let ((k (call/cc call/cc))) ; <--- continue execute after (call/cc call/cc), not jump to toplevel
(printf "222 k=~a\n" k)
(set! *k* k))
(printf "333\n"))
;; 111
;; 222 k=#<procedure>
;; 333
Correct me if i'm wrong.
I much appreciate the responses, and I'm trying to do some homework before I ask. I think I have distilled some of my confusion into this:
(call/cc1 call/cc2)
So, Scheme evaluates the arguments of functions first (or at least I assume it does). Next, call/cc2 is evaluated with the continuation being (call/cc1 _). However, if at the REPL, I input:
(call/cc)
I get an error ... it wants a procedure as an argument ... I don't doubt that (call/cc call/cc) is valid, I've tried it, I just wonder what the procedure is that is passed to the call/cc2?
(call/cc1 call/cc2)So, Scheme evaluates the arguments of functions first (or at least I assume it does). Next,
call/cc2is evaluated
call/cc2 is a function and therefore is a value.
wHowever, if at the REPL, I input:
(call/cc)I get an error ... it wants a procedure as an argument ... I don't doubt that
(call/cc call/cc)is valid, I've tried it, I just wonder what the procedure is that is passed to thecall/cc2
Keep in mind that call/cc reads out “call my argument with the continuation of the call to call/cc”.
So imagine some context (a stack) around an application of call/cc:
E[ (call/cc f) ]
The name tells you that f is applied to the “continuation” of the function call (call/cc f). What is the continuation? E represents the continuation. But Racketeers think of the continuation as a function, so we can spell it out as
(lambda (x) (jump-to-top-level E[x]))
This is how the “continuation” E gets “applied” (filled with) the value that a call to the continuation supplies. The jump-to-top-level has always been nebulous. What exactly is it? It’s one thing at the REPL, it’s another when you run this inside of a module. (When I was young and had to learn English, I called this a “prompt” (yeah I know) and that’s what’s stuck with Racket’s control library. Modules insert “artificial” prompts at certain places, behind your back.)
No, at least in R5RS, the evaluation order of a procedure call (operator and operands) are unspecified. I don't know how Racket do, but in general, you cannot assume it.
See Revised5 Report on the Algorithmic Language Scheme
4.1.3. P>rocedure calls
(<operator> <operand1> ...)
A procedure call is written by simply enclosing in parentheses expressions for the procedure to be called and the arguments to be passed to it. The operator and operand expressions are evaluated (in an unspecified order) and the resulting procedure is passed the resulting arguments
This is a syntax error, it require a procedure as argument. You cannot write (call/cc), just like you cannot write (if), see 10.4 Continuations .
tmeehan:
So, Scheme evaluates the arguments of functions first (or at least I assume it does).
No, at least in R5RS, the evaluation order of a procedure call (operator and operands) are unspecified. I don't know how Racket do, but in general, you cannot assume it
Racket and Scheme evaluate arguments before they evaluate the function body. I suspect the OP meant this denotation with “first”.
tmeehan:
However, if at the REPL, I input:
(call/cc)This is a syntax error, it require a procedure as argument.
This is a runtime error because call/cc is just a function. It is okay to write
(define [call/cc] 1)
and then the above works.
Strictly speaking you are right, it should be understand as contract violation or type error. I said it a "syntax error" just for intuition. Thanks for pointing out my bug.
Thank you all for humoring me. I have been a mediocre imperative programmer for a long time and want to write better programs, hopefully in something that isn't imperative. I'm aware that some of what I'm going to write will be restating what you all have been trying to show me.
Ok starting with:
(call/cc1 call/cc2)
Scheme knows that call/cc2 is a function, and is therefore a valid argument to call/cc1.
Scheme then evaluates the function call/cc1, passing it's continuation (say, k1) to call/cc2. So we are left with:
(call/cc2 k1)
Scheme then evaluates call/cc2, passing it's continuation (say, k2) to k1.
(k2 k1)
Here at this point, it appears that I am flying by pulling on my shoelaces. k2 seems like it would be (call/cc1 [...]) and k1 would be the exterior-most continuation. Thus, I would be pausing the exterior-most continuation, and then restarting (reifying?) the exterior-most continuation ... with the catch being that I could also assign it to something in a let binding?
Additionally, Racket does specify left-to-write evaluation.
This is illustrated the reference chapter on the evaluation model, §§ 1.1.1 Sub-expression Evaluation and Continuations and 1.1.7 Procedure Applications and Local Variables, but it seems like "left-to-right" isn't used explicitly: I'll open an issue about that. It is definitely something Racket intends to guarantee: the Racket CS backend introduces let bindings as needed to preserve evaluation order, as Chez Scheme makes no such guarantee.
(It was hypothesized that leaving evaluation order unspecified would present optimization opportunities, but AIUI empirical measurements have shown that it doesn't actually offer much benefit in practice—particularly considering that a sufficiently smart compiler can reorder subexpressions anyway as long as it can determine there are no observable effects—and giving up the small optimization opportunity is a bargain price for eliminating a confusing source of nondeterminism.)
P.S. I've opened Docs should discuss left-to-right evaluation · Issue #4189 · racket/racket · GitHub.
Actually, k1 and k2 denote the same continuation. It is a@[...], not a@(call/cc1 [...]).
Also, your derivation missed a@.
Let's write this as a step-by-step calculation, after all “computation” involves calculation:
E[ (call/cc1 call/cc2) ]
is the program that executes. Both “call/cc”s refer to Racket’s call/cc. E is what is left to do when the application (call/cc1 call/cc2) is evaluated (calculated to a value). So let’s do that:
step 1:
E[ (call/cc2 k1) ]
where k1 is really just an encoding of E. (See my previous post.)
step 2:
E[ (k1 k2) ]
where k2 is really just the same encoding of E as before — again!. But now we need to recall what this encoding is: (lambda (x) (jump-to-top-level E[ x ]). (The x is a variable that does not show up in E.)
So let’s replace k1 with its meaning:
step 3:
E[ ((lambda (x) (jump-to-top-level E[ x ]) k2) ]
We know how to deal with lambda, that’s Algebra 1 from Middle School. Substitute x in (jump-to-top-level E[ x ] with k2.
step 4:
E[ (jump-to-top-level E[ k2 ]) ]
What does jump mean? It’s like goto in old imperative languages, setlongjump and friends in C, meaning it erases the the surrounding E because the “top” of E is the top level:
step 5:
E[ k2 ]
k2 is an identifier, just like call/cc and we’re done until we find out what E is.
Let’s make two examples for E.
Example 1:
[[ Is there a char limit on posts? The example sections got cut off. ]]
Let’s make two examples for E.
Example 1:
Do you happen to have ----- at the beginning of a line in your post? I think it cuts everything after that, if you use the email interface to reply (the web interface works fine though).
See also my bug report: Content after a horizontal line in email replies is stripped? - bug - Discourse Meta
[[ Thanks Oak. ]]
Third try, must be a charm, no?
Let’s make two examples for E.
E is (add1 [ ])
step 6 (for example 1):
(add1 k2)
The “contract” for add1 says its argument must be a number. But we know that k2 is this funny lambda-encoding of add1: (lambda (x) (jump-to-top (add1 x))). Ergo:
RUNTIME ERROR
E is
(define resumption-point #false)
(set! resumption-point [ ])
Plug in k2 and you get a new expression:
step 6 (for example 2):
(define resumption-point #false)
(set! resumption-point k2)
Ah, we know how to deal with set! (that’s like = in C):
step 7:
(define resumption-point k2)
Here the identifier resumption-point stands for (the value of) k2. It’s the lambda from above. But this is just a definition so what?
The program can use resumption-point anywhere and “go back” to the assignment statement everything that follows. So if someone wrote (resumption-point 5) all of a sudden resumption-point would stand for 5. Hah!
;; - - - - - -
(call/cc call/cc) is a brain teaser, and as such not very insightful.
It is better to think of call/cc uses, such as this:
(1) set a timer
(2) set a clock interrupt handler to use call/cc
(3) when the timer expirses, use the interrupt handler to grab the rest of the computation (= continuation)
(4) switch to a new one
Soon you will realize that call/cc is “wrong”. It stands in the way of proper uses of continuations for things like writing an OS. That’s why racket/control offers variants of call/cc that are better suited for practical programming..
This whole thread has been great! And now I'm going to have to go learn about racket/control because all of this was very fun to think about.