Wednesday, December 5, 2007

Delimited continuations with cl-cont

As continuations are becoming popular for web-development and with growth of web frameworks and servers using them like: PLT Scheme Web Server, Seaside for Smalltalk, Apache Cocoon and finally Uncommon Web and Weblocks for Common Lisp, like most of us who never programmed in Scheme I didn't understood what are they? After searching the web, reading dozen of articles and revisited On Lisp especially the chapter about continuations which I skipped last time I finally understand them and found that they are quite simple concept. Continuations is an abstraction representing the rest of the program at some point. Lets make it clear through some examples. Common Lisp doesn't have continuations built-in so I will use cl-cont package as demonstration facility. Cl-cont implements delimited continuations for the needs of the weblocks framework.

In the below program :

(with-call/cc
(+ 1 (call/cc
(lambda (k)
(funcall k 3)))))
4

the rest of program is simply adding one, while the current program is the whole between the square brackets as seen in (+ 1 []).
Why should something like this be useful to anybody ?
Well the continuations could be saved and than called at any time, let's see that:

(with-call/cc
(+ 1
(call/cc

(lambda (k)
(setf cc k)
(funcall k 3)))))
4


In above we saved current continuation, read adding one, into the variable cc , now we could call it, like this :

(funcall cc 1)
2
(funcall cc 10)
11

Let's do little bit more complex example :

(with-call/cc
(list (+ 1 (call/cc
(lambda (k)
(setf cc k)
(funcall k 3))))))
(4)

(funcall cc 77)
(78)

Ok now we are ready for our first non trivial thing, implementing generators.
Let's implement a generator that returns multiplies of seven using continuations, the code

(defun test ()
(with-call/cc
(let ((i 0))
(call/cc
(lambda (k)
(setf cc k)))
(incf i 7))))

We start the generator by simply calling

(test)
#

and than we call the saved continuations, like this:

(funcall cc)
7
(funcall cc)
14
(funcall cc)
21

The reset is done by calling test again:

(test)
#

(funcall cc)
7

Ok enough with toy examples. Imagine that newbie came into c.l.l asking for help about his homework, saying write a program that flattens a tree. And though you sympathize with a poor kid that have to learn artifical intellegence and half a dozen programming languages in a single course,he didn't tried to show you that at least he opened his copy of Practical Common Lisp. Such ignorance can't be tolerated. You look at your poster of Kenny Tilton, the one you bought as soon as you finally understood Cells, even without documentation, and write something like below


(defun tree-gen (tree)
(let (saved)
(labels
((get-atom (tree)
(with-call/cc
(cond ((null tree) nil)
((atom tree) tree)
(t (call/cc
(lambda (k)
(push #'(lambda ()
(funcall k (get-atom (cdr tree)))
)

saved
)

(get-atom (car tree))
)
)
)
)
)
)

(yield ()
(if (null saved)
(values nil nil)
(let* ((cont (pop saved))
(val (funcall cont))
)

(if val (values val t) (yield))
)
)
)
)

(let ((res (list (get-atom tree))))
(loop
(multiple-value-bind (val more)
(yield)
(if more
(push val res)
(return (nreverse res))
)
)
)
)
)
)
)

Better formatted version at http://paste.lisp.org/display/51958
And you can call it like this:

(tree-gen '(((0 (1))) (2 3 (4)) (5 ((((6) 7) 8 ) 9) 10) 11))
(0 1 2 3 4 5 6 7 8 9 10 11)


Few references that helped me understood continuations:
1.Tim Peters thread at
http://mail.python.org/pipermail/python-dev/1999-July/000467.html
2. Chapter about continuations at Teach Yourself Scheme in Fixnum Days:
http://www.plt-scheme.org/software/drscheme/
3. Paul Graham chapter about continuations at On Lisp
http://www.paulgraham.com/onlisp.html

And finally you can find cl-cont project at:
http://common-lisp.net/project/cl-cont/ also take a look at weblocks framework that's using it at http://common-lisp.net/project/cl-weblocks/

kind regards
Slobodan Blazeski

5 comments:

  1. Nicely done. I like the example on generators.

    You can use the html pre tags to format code with Blogger. It is annoying, but oh well.. Atleast Lisp doesn't normally have any characters you need to escape :-)

    ReplyDelete
  2. I don't know whether this is intentional, but you're explaining nowhere what the with-call/cc and call/cc operators do.

    ReplyDelete
  3. Sohail:
    Please show me an example how to do it, post it as comment or mail it to me.

    Leslie:
    I usually can't understand anything from definitions. Probably it's my style for learning things but that's just what am I. I read all the articles Slava wrote about weblocks, but the real knowledge I got is from the test-cases, weblocks-demo and snippets posted at the group.

    Thanks to both of you for your feedback, if I feel in a mood I would write another post about implementing coroutines with cl-cont.

    ReplyDelete
  4. You can do it like this:
    <pre>
    (my
     (fancy
      (lisp
       (code...
    </pre>

    ReplyDelete
  5. Thanks for a nice article. I appreciated the links in particular.

    I made a post about my continuations learning here if you're interested...

    Cheers. :-)

    ReplyDelete

Note: Only a member of this blog may post a comment.