My guess is that anyone coming from the OO or structural world of programming style trying to learn Scheme, will take a while to get his/her mind around continuations and how they can be used in Scheme. I still am trying to get my mind around it. The problem is exacerbated by the thought that I think I know it but can’t point at what I don’t know 🙁 This post is an attempt to brain-dump whatever I know and see if it makes sense; both to me and to anyone reading this post, in the fervent hope to try to understand Continuations and Scheme.
The first place to head to understand continuations is the wikipedia.Another nice place to understand what continuations are seems to be this excellent post on comp.lang.scheme. Look for the post by bear wherein he/she explains continuations as can be understood by a C programmer. The moment one thinks of the stack frames as being on the heap and not on the stack, the possibility of continuations becomes very clear. If each of the stack frames are always available for access at any time during the program’s execution, one can jump to any part of the program. This part of the program that one can jump to can be in the future or can be in the past. The continuation as a concept liberates from the sequential stack based model.
Coming to continuations in Scheme, it took me a while to get a hang of it, and even now, I don’t think I have fully gotten it. May be writing more code that uses continuations might help reduce the haze. Or it could be one of those things, you just get it while writing some code or understanding some code.I found The Scheme Programming Language more helpful in trying to understand continuations in Scheme, than the TY Scheme in fixed num days. Of course, YMMW. Once the idea of continuations is clear, lets dive into how Scheme implements them with the
call/cc. Whenever a Scheme S-expression is executed, there is some other S-expression waiting for the result of the previous expression’s result. This S-expression which is waiting for the results, or in other words, the expression that will be executed in the future is the continuation.I am going to use an example similar to the one in the The Scheme Programming Language to derive the usage of
call/cc.Take the following example
(+ 5 ( k 4))))
(lambda (x) (+ 12 x)))
Simple example ? I guess so. The myproc takes a procedure, to which it applies 4 and then takes the result and adds it to 5 and returns it to the caller. I have just described the various continuations that are part of the code – the addition of 5 to the result of the procedure result of
(k 4) is a continuation. The caller waiting on the result of
myproc is also another continuation. As for the invocation of the above code, it can be invoked thus:
> (myproc t1) # 21
The t1 procedure is passed as a parameter to myproc. So first the evaluation of
(t1 4) happens and the result is returned, to which 5 is added. So the output of the call is 21 ( (5+ (12+4)). This is fine till now ? Now lets enter the realm of continuations. Now consider the case wherein you wanted to return from the myproc immediately without any processing. Some parameter that was passed to myproc was invalid and you don’t want to perform any operation at all and return some value immediately. How do you achieve that ? Before answering that question, lets look at what happens if we do this
(call/cc myproc ). It results in a continuation being displayed and 4 being the result.
What happened here ? The myproc was supposed to take a procedure as a parameter and pass 4 to it as the parameter and then add 5 to it. But when the procedure is called with
(call/cc myproc) then the procedure returns a 4. The procedure call/cc packages up the current continuation into a procedure and passes it as the parameter to the function. And the output shows that the parameter k is a continuation. The current continuation is the procedure myproc and it was supposed to do all the calculations and return a value, but we have effectively short-circuited the entire process. In the S-expression
(k 4) the current continuation is applied to 4, and as you know the current continuation is the procedure myproc ==> the result of the entire procedure is 4. The remaining expressions are not evaluated (in this example).Any top level expression using the result of the myproc though will be processed. Take a look at this example
(+ 2 In this example, once the continuation returns 4, the top level addition 2 + is executed and the result is 6.
(* 5 (k 4)))))
I hope I was able to explain continuations in a very layman’s terms; and also continuations in Scheme. If there are any errors in my explanation please write a comment, and I shall fix it. Also, this is titled Continuations-I because, I assume that I will be writing more about this topic. May be I will try to provide more examples which make it very easy to understand how continuations are used in Scheme.