Heard of call with current continuation and never grokked it? Here is a worked introduction to call/cc in BASIC.
10 REM ---- MAIN -------
20 PRINT "MAIN 1"
30 GOSUB 110
40 PRINT "MAIN 2"
100 REM --- FOOA ------
110 PRINT " FOOA 1"
120 GOSUB 220
130 PRINT " FOOA 2"
140 RETURN
200 REM --- FOOB ------
210 PRINT " FOOB 1"
220 PRINT " FOOB 2"
230 RETURN
When you run the program, you get this.
MAIN 1
FOOA 1
FOOB 1
FOOB 2
FOOA 2
MAIN 2
Alright, let’s consider what’s going on here
Main calls FOOA, which in turn calls FOOB
+-------+
| MAIN 1|
+-------+
|
| +----------+
+-->| FOOA 1 |
+----------+
|
| +-----------+
+-------->| FooB 1 |
+-----------+
and then FOOB returns to FOOA, which in turn returns to MAIN
+-------+
| MAIN 2|
+-------+
^
| +----------+
+-->| FOOA 2 |
+----------+
^
| +-----------+
+---------| FooB 2 |
+-----------+
If we draw a vertical timeline, this is what happens
+-------+
| MAIN 1|
+-------+
|
| +----------+
+-->| FOOA 1 |
+----------+
|
| +-----------+
+-------->| FooB 1 |
+-----------+
|
|
v
+-----------+
+---------| FooB 2 |
| +-----------+
v
+----------+
+---| FOOA 2 |
| +----------+
v
+-------+
| MAIN 2|
+-------+
Take another look at the vertical timeline. The entire program could actually have been constructed entirely of GOTOs. GOSUB and RETURN is actually a special case of GOTO. Conversely, we can also say GOTO is a special case of GOSUB/RETURN.
Here is a possible implementation of GOTO as a special case of GOSUB.
(code copied from the top so that you don't have to scroll)
10 REM ---- MAIN -------
20 PRINT "MAIN 1"
30 GOSUB 110
40 PRINT "MAIN 2"
100 REM --- FOOA ------
110 PRINT " FOOA 1"
120 GOSUB 220
130 PRINT " FOOA 2"
140 RETURN
When line 30 calls line 110, line 30 could pass an additional argument with a value of ‘40′ (which is the next line to be executed after FOOA returns). When the BASIC interpreter encounters a RETURN statement at line 140, it GOSUB to line 40.
(pregnant pause here)
OK, now your head is spinning. You might ask: GOSUB without returns? Wouldn’t that blow the stack? Or … argue that Chui is cheating, because BASIC doesn’t have local variables in functions. Just bear with me one more moment.
In structured programming, say if you could pass in ‘40′ as well as a pointer to the list of local variables in the current function. Then when FOOA returns it can call GOSUB 40, passing in the list of local variables passed in earlier from MAIN. Of course, this may mean that the local variables live on the heap instead of a stack, and you need alternate garbage collection algorithms. (For instance, when refcount of the variable list goes back down to 0, then free the memory.)
OK, now that we have given form to a concept, what are we going to call this ‘40′ and the ‘list-of-local-variables’ ? Answer: current continuation. Call-with-current-continuation converts the remaining code in the calling function into a closure (which is a function that has preinitialized local variables), and passes this closure to the function it is calling.
(pregnant pause)
With explicit access to the a continuation, you can optionally choose not to call it, or even to call it again and again. It is counterintuitive, but being able to call continuations can actually make the program logic more transparent in cooperative multitasking. But that’s for another day.
What about performance? Calling functions can be expensive, isn’t it? Remember that GOSUB and GOTO are equivalent? Guy Steele had shown in a paper titled “Lambda the Ultimate GOTO”, that there is a standard series of steps for a compiler to transform function-calling into equivalent GOTOs.
Questions? comments?
