Continuations and Scheme – Part I

Continuations howto, scheme, continuations explained, understand continuations in scheme

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
(define myproc
(lambda (k)
(display k)
(+ 5 ( k 4))))
(define t1
(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
(lambda (k)
(* 5 (k 4)))))
In this example, once the continuation returns 4, the top level addition 2 + is executed and the result is 6.

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.

Understading macros in Scheme

Scheme macros howto, explanation of how macros are expanded in Scheme

Disclaimer first: this post is about how I understood how macros in Scheme work. I am still a beginner, so there might be errors. Point them, and they shall be fixed. Now onto the actual thing. Most of the literature on Lisp and Lisp-like languages (like Scheme) mention the advantages of using macros in the language. The macros in these languages help one extend the language. This is indeed true, but for someone who sees a define-macro for the first time, trying to get his/her head around what is happening might be a little daunting. This post is an attempt to explain what is happening in simple steps. I am reading Teach yourself Scheme in fixnum days and am going to use the example mentioned in the text about macros. The example used is to create the form when.The code verbatim: (define-macro when
(lambda (test . branch)
(list 'if test
(cons 'begin branch))))

Before trying to understand this code, there are somethings that can be useful to go over. First the procedure cons, and the dotted pairs. A dotted pair is a compound value made of two (or more values). When there are more than two values in a dotted pair, the car returns the first element, and the cdr returns the remaining values. This aspect of it is what is exploited in the macro too. Here is a small example for this:
(define p
(lambda (test1 . branch)
(display test1)
(display branch)
(cons 'begin branch)))

In this snippet, p is a procedure which takes two parameters and it displays the parameters passed to it. In the REPL prompt, type this >(p '2 '3)
(begin 3)

As you can see, the second parameter 3 is part of a dotted pair. To make it clear, lets pass more parameters to the procedure. Type this at the prompt >(p '2 '3 '4)
(3 4)
(begin 3 4)

As you see in this case, 3 and 4 are passed to the lambda in the branch parameter. This exact thing is what is exploited in the creation of the macro. Also note the line (cons 'begin branch). The text “begin is needed because cons takes two parameters and creates a pair out of both the parameters.

Now that we have talked about why we need a dotted pair in the parameters of the macro, lets now look at the actual macro definition itself. In the macro definition, look at this part
(list 'if test
(cons 'begin branch))

This is the meat of the macro. The list is being used to generate a S-expression which can be evaluated. Without the list the expression generated can”t be evaluated. Now, let”s look at the list itself. The first element of the S-expression is the literal if, followed by the contents of the local variable test. And the second part of the dotted pair, the branch is the remaining part of the expression passed to the macro. And this part is made a S-expression by using the cons operator, and using the keyword begin. This way, the else part of the if evaluation is handled as another S-expression. So putting all this together, if you define the when macro as mywhen (because when exists in PLT Scheme) and invoke it thus
>(mywhen (< x 200) "less")
The expansion will be (not exact, just what it looks like) (list 'if (< x 200) (cons begin "less"))
Of course the above is just to give an idea of how it will be evaluated. The actual evaluation, as explained in the chapter will be (apply
(lambda (test . branch) (list 'if test (cons 'begin branch))) (< x 200) "less"))
As you can see, macros indeed are very powerful in Scheme, and can be used to extend the language.