Continuations in lisp

Discussion of Common Lisp
Post Reply
Suroy
Posts: 46
Joined: Sat Dec 19, 2009 11:20 am

Continuations in lisp

Post by Suroy » Mon Jun 28, 2010 9:32 pm

I was looking at cl-cont and the statement:

"call/cc cannot appear within the body of catch, throw, progv, or unwind-protect."

I was wondering why this was and could there be a way around it? After all, at the very least unwind-protect is used at least somewhat frequently and so is error handling code.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Continuations in lisp

Post by ramarren » Mon Jun 28, 2010 11:37 pm

Continuations do not compose with dynamic scope well, which is one of the reasons why Scheme uses lexical scope only. There are some ways to make them cooperate a little better (look for DYNAMIC-WIND) but that is usually beyond the scope of libraries like cl-cont. There is only so much you can do at that level without reimplementing an entire CL compiler.

Suroy
Posts: 46
Joined: Sat Dec 19, 2009 11:20 am

Re: Continuations in lisp

Post by Suroy » Tue Jun 29, 2010 6:27 am

not exactly sure why that is true. with a code walker, code which creates a continuation could be informed of the surround protect form and add it to its continuation. Similar for dynamic variables, im pretty sure the lisp compiler knows which variables are special and which are not, the continuation creating code could be informed and rebind those variables upon calling. basically it can rebuild the surrounding environment that it cant capture through closures, somehow.

i was just searching and haven't really looked at it but this looks interesting
http://www.discontinuity.info/~pkhuong/common-cold/

looks like it has its own special forms you can use to indicate that a continuation is inside the catch form, a dynamic variable is being bound, etc.

edit: ... i better look at the above before i say anything else :D ...i see it is using sbcl...

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Continuations in lisp

Post by ramarren » Tue Jun 29, 2010 10:42 am

Suroy wrote:with a code walker, code which creates a continuation could be informed of the surround protect form and add it to its continuation.
Protected forms often refer to external resources, which might become unavailable or be in different state when the continuation is reentered. It is easier to just disallow UNWIND-PROTECT in delimited continuation implementation, which is what cl-cont did, than to crash or try to detect it somehow when external state is wrong. Especially considering that once you have continuation computational-only part UNWIND-PROTECT is trivial to implement, I believe. I never looked too deep into continuations.

Suroy
Posts: 46
Joined: Sat Dec 19, 2009 11:20 am

Re: Continuations in lisp

Post by Suroy » Tue Jun 29, 2010 8:19 pm

true, though maybe placing the unwind protect code in a function which can be passed to the continuation will create a closure and you can use that function? no matter, i was just curious dont really need them.

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Continuations in lisp

Post by gugamilare » Wed Jun 30, 2010 6:10 am

About unwind-protect, I believe the problem is that some functions won't be able to know that they are unwind-protected if you stop the computation and restart it later. For instance, consider the following code:

Code: Select all

(defun a (cc2)
  (with-call/cc
    (print 1)
    (setf cc2
          (let/cc k
            (funcall cc2 k)))
    (print 3)
    (format t "~%STOP NOW!~%")
    (let/cc k
      (return-from a
        (lambda ()
          (format t "~&Continuing...~%")
          (funcall cc2 k))))
    (print 5)))

(defun b (cc1)
  (with-call/cc
    (print 2)
    (setf cc1
          (let/cc k
            (funcall cc1 k)))
    (print 4)
    (let/cc k
      (funcall cc1 k))))
Then

Code: Select all

cl-user> (a #'b)

1 
2 
3 
STOP NOW!
#<CLOSURE (lambda ()) {1003BD0919}>
cl-user> (funcall *)
Continuing...

4 
5 5
Neat :D

Now, suppose you modify it a little bit:

Code: Select all

(defun a (cc2)
  (with-call/cc
    (unwind-protect
         (progn
           (print 1)
           (setf cc2
                 (let/cc k
                   (Funcall cc2 k)))
           (print 3)
           (format t "~%STOP NOW!~%")
           (let/cc k
             (return-from a
               (lambda ()
                 (format t "~&Continuing...~%")
                 (funcall cc2 k))))
           (print 5))
      (format t "~&Function A has been successfully executed!~&"))))

(defun b (cc1)
  (with-call/cc
    (print 2)
    (setf cc1
          (let/cc k
            (funcall cc1 k)))
    (oops-undefined-function)
    (print 4)
    (let/cc k
      (funcall cc1 k))))
Now, there will be an error once you try to continue the computation, because the function oops-undefined-function is not defined.

Well, how would you like the code to behave? Function A returns right after STOP NOW is printed, so, if the unwind-protect is left as-is, then the cleanup code will execute after STOP NOW, which happens if you put the unwind-protect around with-call/cc:

Code: Select all

(defun a (cc2)
  (unwind-protect
       (with-call/cc
         (print 1)
         (setf cc2
               (let/cc k
                 (Funcall cc2 k)))
         (print 3)
         (format t "~%STOP NOW!~%")
         (let/cc k
           (return-from a
             (lambda ()
               (format t "~&Continuing...~%")
               (funcall cc2 k))))
         (print 5))
    (format t "~&Function A has been successfully executed!~&")))
If you want the cleanup after you try to continue and the undefined function error is thrown, how is B supposed to know that it is running under the scope of a unwind-protect? For this to work that way, you would need to do this:

Code: Select all

(defun a (cc2)
  (with-call/cc
    (print 1)
    (setf cc2
          (let/cc k
            (Funcall cc2 k)))
    (print 3)
    (format t "~%STOP NOW!~%")
    (let/cc k
      (return-from a
        (lambda ()
          (unwind-protect
               (progn
                 (format t "~&Continuing...~%")
                 (funcall cc2 k))
            (format t "~&Function A has been (un)successfully executed!~&")))))
    (print 5)))
With the exception that, if A or B fails before that, the cleanup code will not be executed. I don't see how this can be possibly implemented. You are welcome to try doing this and, if you manage to do it, you will deserve a very warm congratulations ;)

It should be possible to modify the previous example to show why catch and throw are bad to use in this case - you might not be able to know that you are under the scope of a catch after continuation.

Finally, about progv, the problem is it binds special variables during runtime. You can't know during macroexpansion time which variables are to be rebound. That is not the case when you use let, since the names are explicit in the body of let. Well, I don't actually know if cl-cont supports special variables or not, but, even if it does, I would not trust that progv could be easily implemented at all.

Post Reply