I'm looking for a simple fully functional call/cc. I looked into Arnesi,
but its call/cc is limited in scope to code enclosed in with-call/cc
(making it actually more like reset / shift). Matthew D. Swank posted an
example but I couldn't figure it out. I searched the web a lot and only
found discussions, no CL code.
I think I understand continuations and call/cc (I experimented a little
with it in Scheme), but I don't think I would be able to implement it.
I'm surprised that a full implementation of this operator is not easier
to find. What is the explanation?
-- there is a nice call/cc out there, but I couldn't find it
-- call/cc is so easy to write, I must be joking
-- a proper call/cc is not possible in CL
-- I should not be looking for call/cc
-- ...
> I think I understand continuations and call/cc (I experimented a little
> with it in Scheme), but I don't think I would be able to implement it.
> I'm surprised that a full implementation of this operator is not easier
> to find. What is the explanation?
> -- there is a nice call/cc out there, but I couldn't find it
> -- call/cc is so easy to write, I must be joking
> -- a proper call/cc is not possible in CL
> -- I should not be looking for call/cc
> -- ...
I think it's impossible to define a call/cc in cl without a wrapper like
with/cc. That is because a call/cc must know everything that happened
even before it was called, and as cl doesn't offer a way to inspect the
call stack (at least I don't know one...) you'll have to log it on your
own starting with a top-level-macro.
But if you like you can shadow defun et al. to wrap everything in that
macro automatically - screamer does something like this e.g.
Benjamin
Philippe Lorin wrote:
> I think I understand continuations and call/cc (I experimented a little
> with it in Scheme), but I don't think I would be able to implement it.
> I'm surprised that a full implementation of this operator is not easier
> to find. What is the explanation?
In this context there is nothing special about Common Lisp. The general
question is "How do I implement call/cc in a language in which function
calls doesn't support proper [1] tail call optimization?". If there is
an easy and efficient implementation, then indeed is surprising. If
there is only a complicated solution, which may affect the execution
speed it becomes less surprising.
The answer to the question can be found in the Scheme literature.
I'd start with Dybvig's "Three Implementation Models for Scheme"
which is *very* well written
<http://www.cs.indiana.edu/~dyb/papers/3imp.pdf>
to get a better understand of the underlying problems.
Then I'd turn to the papers on Scheme-to-C translation.
For example "Compiling Higher-Order Languages into Fully Tail-Recursive
Portable C" by Marc Feeley, James S. Miller, Guillermo J. Rozas, and
Jason A. Wilson.
<http://www.iro.umontreal.ca/~feeley/papers/tr1078.ps.gz>
Then there is the other papers in the section "Compiler Scheme to C"
at readscheme.org:
<http://library.readscheme.org/page8.html>
There is also the paper "Implementation strategies for continuations"
by William D. Clinger, Anne Hartheimer and Eric M. Ost - but you'll
have to go the library for that one.
[1] In the technical sense, see William D. Clinger. "Proper tail
recursion and space efficiency"
<ftp://ftp.ccs.neu.edu/pub/people/will/tail.ps.gz>
--
Jens Axel S�gaard
Philippe Lorin wrote:
> I'm looking for a simple fully functional call/cc. I looked into Arnesi,
> but its call/cc is limited in scope to code enclosed in with-call/cc
> (making it actually more like reset / shift). Matthew D. Swank posted an
> example but I couldn't figure it out. I searched the web a lot and only
> found discussions, no CL code.
>
> I think I understand continuations and call/cc (I experimented a little
> with it in Scheme), but I don't think I would be able to implement it.
> I'm surprised that a full implementation of this operator is not easier
> to find. What is the explanation?
> -- there is a nice call/cc out there, but I couldn't find it
> -- call/cc is so easy to write, I must be joking
> -- a proper call/cc is not possible in CL
> -- I should not be looking for call/cc
> -- ...
It seems that the expressive power of full continuations is very rarely
needed, if at all. Most of the time, you rather use them to achieve much
simpler things, like escaping continuations (throw / return-from), etc.
What do you actually want to express?
Pascal
--
3rd European Lisp Workshop
July 3-4 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
Pascal Costanza wrote:
> It seems that the expressive power of full continuations is very rarely
> needed, if at all. Most of the time, you rather use them to achieve much
> simpler things, like escaping continuations (throw / return-from), etc.
>
> What do you actually want to express?
It's a kind of cooperative multitasking.
I need three things: CSTART, CSTEP and YIELD.
(cstart body)
Returns a new object that can be called with CSTEP.
(cstep c)
Executes c's body until a YIELD or a normal return is encountered.
(yield) ; to be used only in a body passed to cstart, or in a function
; called by it.
"Returns" to the nearest CSTEP in the call stack, while somehow keeping
track of where we are in body, and what the "local values" are.
(cstep c) ; (again)
Executes c's body from where we left last time, until another YIELD or a
normal return is encountered.
CSTEP returns T when a yield is encountered; NIL otherwise. When NIL, it
should not be called again with the same argument.
;;; EXAMPLE 1
;;; A utility function.
(defun p (x) (print x) (terpri))
;;; Create a pseudo-coroutine *c*
(defparameter *c*
(cstart
(p 1)
(yield)
(p 2)))
;;; Execute *c* until the first YIELD
(cstep *c*)
=> 1
=> T
;;; Execute the remaining of *c*
(cstep *c*)
=> 2
=> NIL
;;; EXAMPLE 2
;;; Create a pseudo-coroutine *c1*
(defparameter *c1*
(cstart
(let ((x 1))
(p x)
(incf x)
(yield)
(p x))))
;;; This function will be called by *c2* below
(defun f ()
(p "b")
(yield) ; note that this will "return" to CSTEP, not to the direct
; caller (see below)
(p "c"))
;;; Create a pseudo-coroutine *c2*, which calls f
(defparameter *c2*
(cstart
(p "a")
(yield)
(f)
(p "d")))
;;; Execute *c1* until the first YIELD
(cstep *c1*)
=> 1
=> T
;;; Execute *c2* until the first YIELD
(cstep *c2*)
=> "a"
=> T
;;; Execute the remaining of *c1*
(cstep *c1*)
=> 2
=> NIL
;;; Execute *c2* until the first YIELD
(cstep *c2*)
=> "b"
=> T
;;; Execute the remaining of *c2*
(cstep *c2*)
=> "c"
=> "d"
=> NIL
Please tell me if anything is unclear. I do need this construct (the
ability to define that kind of things was my main motivation for
switching to Lisp), and I will learn whatever is required to implement it.
Philippe Lorin <············@gmail.com> wrote:
+---------------
| Pascal Costanza wrote:
| > What do you actually want to express?
|
| It's a kind of cooperative multitasking.
| I need three things: CSTART, CSTEP and YIELD.
+---------------
CMUCL's "multiprocessing" (green threads, really) can easily do this
[given some trivial wrappers], as can SBCL and several other Common
Lisps with threads. In the case of CMUCL, I think this [untested]
does approximately what you asked for:
(defmacro cstart (&body body)
`(mp:make-process (lambda () (yield) ,@body)))
(defun cstep (c)
(mp-enable-process c))
(defun yield ()
(mp-disable-process mp:*current-process*))
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> CMUCL's "multiprocessing" (green threads, really) can easily do this
> [given some trivial wrappers], as can SBCL and several other Common
> Lisps with threads. In the case of CMUCL, I think this [untested]
> does approximately what you asked for:
>
> (defmacro cstart (&body body)
> `(mp:make-process (lambda () (yield) ,@body)))
>
> (defun cstep (c)
> (mp-enable-process c))
>
> (defun yield ()
> (mp-disable-process mp:*current-process*))
Thanks. It does sound like it could do the job. Can I ask a few questions?
- There doesn't seem to be much documentation about CMUCL's mp package.
The best I found is:
http://www.trakt7.net/cmucl%20and%20multiprocessing
Isn't there anything better, more synthetic?
(NB: I've seen that question asked numerous times when googling, so my
hopes aren't high.)
- The following:
(mp:make-process (lambda () (print 1) (terpri)))
works as I'd expect (it prints "1") in a REPL run from the console, or
in the *inferior-lisp* buffer in Slime, but in the *slime-repl cmucl*
buffer it doesn't print anything. Why?
- Finally, while your code looks OK, it doesn't seem to work for me;
maybe I'm missing something. If I do:
(defun p (x) (print x) (terpri))
(defparameter *c*
(cstart
(p 1)
(yield)
(p 2)))
It immediately runs all the body, writing:
1
2
Philippe Lorin <············@gmail.com> wrote:
+---------------
| - There doesn't seem to be much documentation about CMUCL's mp package.
| The best I found is:
| http://www.trakt7.net/cmucl%20and%20multiprocessing
+---------------
That one's pretty good, based as it is on the actual output of
DESCRIBE, though it appears to be based on CMUCL-18e, whereas
CMUCL-19c is current, so you might want to repeat the DESCRIBE
for yourself with whichever version you're using.
+---------------
| Isn't there anything better, more synthetic?
+---------------
For questions not answered by DESCRIBE, the easiest thing
[and most accurate] would be to just read the code in the
CMUCL source distribution [which is what I did, once I started
using it seriously], in the file "src/code/multi-proc.lisp".
But if you want something *less* accurate but more narrative ;-} ;-}
you might try one of these:
http://www.mikemac.com/mikemac/clim/clim-sys.html
http://www.lispworks.com/reference/lwl42/CLIM-U/html/climguide-330.htm
http://alu.cliki.net/com-metacircles-clim-sys-mp
+---------------
| - The following:
| (mp:make-process (lambda () (print 1) (terpri)))
| works as I'd expect (it prints "1") in a REPL run from the console, or
| in the *inferior-lisp* buffer in Slime, but in the *slime-repl cmucl*
| buffer it doesn't print anything. Why?
+---------------
Sorry, I don't use SLIME, so I can't comment.
+---------------
| - Finally, while your code looks OK, it doesn't seem to work for me;
| maybe I'm missing something. If I do:
| (defun p (x) (print x) (terpri))
| (defparameter *c*
| (cstart
| (p 1)
| (yield)
| (p 2)))
| It immediately runs all the body, writing:
| 1
| 2
+---------------
Oops! Sorry, I *did* say it was untested! ;-}
I've actually never used MP:DISABLE-PROCESS and MP:ENABLE-PROCESS
before [all the threads I write run to completion (possibly blocking
on I/O)], and I didn't notice that MP:DISABLE-PROCESS *doesn't* give
up the CPU. I think you'll find things work better for you if you
change the definition of YIELD from:
(defun yield ()
(mp:disable-process mp:*current-process*))
to:
(defun yield ()
(mp:disable-process mp:*current-process*)
(mp:process-yield))
Testing:
cmu> (defparameter *c*
(cstart
(p 1)
(yield)
(p 2)))
*C*
cmu> (progn (cstep *c*) (mp:process-yield))
1
NIL
cmu> (progn (cstep *c*) (mp:process-yield))
2
NIL
cmu>
Is that more like what you expected?
-Rob
p.s. If you try typing just (CSTEP *C*) to the REPL you'll quickly
discover why I did (PROGN (CSTEP *C*) (MP:PROCESS-YIELD)) instead! ;-}
p.p.s. Also note that I typo'd MP:ENABLE-PROCESS & MP:DISABLE-PROCESS
as MP-ENABLE-PROCESS & MP-DISABLE-PROCESS in my original posting. Oops.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Thu, 06 Apr 2006 11:55:09 +0200, Philippe Lorin wrote:
> Pascal Costanza wrote:
>> It seems that the expressive power of full continuations is very rarely
>> needed, if at all. Most of the time, you rather use them to achieve much
>> simpler things, like escaping continuations (throw / return-from), etc.
>>
>> What do you actually want to express?
>
> It's a kind of cooperative multitasking.
> I need three things: CSTART, CSTEP and YIELD.
>
> (cstart body)
> Returns a new object that can be called with CSTEP.
>
> (cstep c)
> Executes c's body until a YIELD or a normal return is encountered.
>
> (yield) ; to be used only in a body passed to cstart, or in a function
>
> ; called by it.
> "Returns" to the nearest CSTEP in the call stack, while somehow keeping
> track of where we are in body, and what the "local values" are.
>
> (cstep c) ; (again)
> Executes c's body from where we left last time, until another YIELD or a
> normal return is encountered.
>
> CSTEP returns T when a yield is encountered; NIL otherwise. When NIL, it
> should not be called again with the same argument.
>
>
> ;;; EXAMPLE 1
>
> ;;; A utility function.
> (defun p (x) (print x) (terpri))
>
> ;;; Create a pseudo-coroutine *c*
> (defparameter *c*
> (cstart
> (p 1)
> (yield)
> (p 2)))
>
> ;;; Execute *c* until the first YIELD
> (cstep *c*)
> => 1
> => T
>
> ;;; Execute the remaining of *c*
> (cstep *c*)
> => 2
> => NIL
>
>
> ;;; EXAMPLE 2
>
> ;;; Create a pseudo-coroutine *c1*
> (defparameter *c1*
> (cstart
> (let ((x 1))
> (p x)
> (incf x)
> (yield)
> (p x))))
>
> ;;; This function will be called by *c2* below
> (defun f ()
> (p "b")
> (yield) ; note that this will "return" to CSTEP, not to the direct
> ; caller (see below)
> (p "c"))
>
> ;;; Create a pseudo-coroutine *c2*, which calls f
> (defparameter *c2*
> (cstart
> (p "a")
> (yield)
> (f)
> (p "d")))
>
>
> ;;; Execute *c1* until the first YIELD
> (cstep *c1*)
> => 1
> => T
>
> ;;; Execute *c2* until the first YIELD
> (cstep *c2*)
> => "a"
> => T
>
> ;;; Execute the remaining of *c1*
> (cstep *c1*)
> => 2
> => NIL
>
> ;;; Execute *c2* until the first YIELD
> (cstep *c2*)
> => "b"
> => T
>
> ;;; Execute the remaining of *c2*
> (cstep *c2*)
> => "c"
> => "d"
> => NIL
>
>
> Please tell me if anything is unclear. I do need this construct (the
> ability to define that kind of things was my main motivation for
> switching to Lisp), and I will learn whatever is required to implement it.
Well, you have to know what a continuation is, and how to keep track of it.
Yield effectively returns a continuation. When cstep starts the program
again it is taking the continuation returned by yield. Since you are
using Common Lisp and not Scheme, you have to construct the continuations
yourself. This means doing some bookkeeping at _every step_ of the
evaluation.
Usually it ends up looking pretty ugly. You can hide the ugly details
with a code-walker (a la with-call/cc), or with helper macros (see Paul
Graham's On Lisp or my previous posts on generators).
There are different ways of keeping track of continuations, but here are
your examples in a variant of CPS:
(defun p (x k)
(print x)
(terpri)
(funcall k))
(defmacro cstart (val)
`(cons #'(lambda ()
,val)
nil))
(defun cstep (corout)
(and (consp corout)
(functionp (car corout))
(setf (car corout) (funcall (car corout)))
t))
(defun c (k)
(p 1
#'(lambda ()
;;yield
#'(lambda ()
(p 2 k)))))
(defun c1 (k)
(let ((x 1))
(p x
#'(lambda ()
(incf x)
;;yield
#'(lambda ()
(p x k))))))
(defun f (k)
(p "b"
#'(lambda ()
;;yield
#'(lambda ()
(p "c" k)))))
(defun c2 (k)
(p "a"
#'(lambda ()
;;yield
#'(lambda ()
(f #'(lambda ()
(p "d" k)))))))
(defparameter *c*
(cstart (c (constantly nil))))
(defparameter *c1*
(cstart (c1 (constantly nil))))
(defparameter *c2*
(cstart (c2 (constantly nil))))
As mentioned in another message, you can forgo much of this if your
implementation has threads.
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Philippe Lorin <············@gmail.com> writes:
> Please tell me if anything is unclear. I do need this construct (the ability
> to define that kind of things was my main motivation for switching to Lisp),
I only scanned your post, but If I understood you correctly all you want are
generators, which would not be a good reason to switch to common lisp (not
that there aren't other attractions).
Several languages (python, icon and I think now even C#) offer generators out
of the box (and very well integrated) or make them trivial to implement
(scheme and other languages that have call/cc like IIRC ruby and some MLs).
There has been a recent thread on implementing generators in CL, you might
want to look it up.
'as
Alexander Schmolck wrote:
> I only scanned your post, but If I understood you correctly all you want are
> generators, which would not be a good reason to switch to common lisp (not
> that there aren't other attractions).
It is indeed a little like generators, but not quite, I think. I don't
need a return value, I just want the side effects. But more importantly,
I need functions called from within the "pseudo-generator" to be able to
yield to its caller, not theirs (and without being told explicitly who
it is).
> Several languages (python, icon and I think now even C#) offer generators out
> of the box (and very well integrated) or make them trivial to implement
I did write what I described in Python, using generators, although I'm
not fluent in Python. The result is not pretty; I wasn't able to make
the machinery disappear entirely. I'd post the code if anybody's
interested, but it's not very clear.
As a side note, I also implemented the thing on top of C, but I had to
make a custom preprocessor to achieve this.
On Thu, 06 Apr 2006 13:50:32 +0200, Philippe Lorin wrote:
> As a side note, I also implemented the thing on top of C, but I had to
> make a custom preprocessor to achieve this.
I don't know what your C code looked like, but it sounds like you could
write the preprocessor as a macro. Also, have you looked at TAGBODY and
GO?
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> I don't know what your C code looked like, but it sounds like you could
> write the preprocessor as a macro. Also, have you looked at TAGBODY and
> GO?
Unfortunately, I don't have a simple example at hand. I have working
code, but it's rather long. I did try to simply use macros, but how
would I store the state of local variables (in a portable way)?
I think the same problem applies to TAGBODY, doesn't it?
Philippe Lorin <············@gmail.com> writes:
> Alexander Schmolck wrote:
> > I only scanned your post, but If I understood you correctly all you want are
> > generators, which would not be a good reason to switch to common lisp (not
> > that there aren't other attractions).
>
> It is indeed a little like generators, but not quite, I think. I don't need a
> return value, I just want the side effects. But more importantly, I need
> functions called from within the "pseudo-generator" to be able to yield to its
> caller, not theirs (and without being told explicitly who it is).
Yes, my apologies. As indicated I only skimmed and although your post in fact
does make this requirement perfectly clear I just overlooked it.
'as
Philippe Lorin <············@gmail.com> writes:
> (yield) ; to be used only in a body passed to cstart, or in a function
> ; called by it.
> "Returns" to the nearest CSTEP in the call stack, while somehow
> keeping track of where we are in body, and what the "local values" are.
Alexander Schmolck <··········@gmail.com> writes:
> Several languages (python, icon and I think now even C#) offer
> generators out of the box (and very well integrated)
Neither Python nor C# allow to put yields in called functions. They
transform only selected functions to generators: it must be statically
known which functions to treat specially.
> or make them trivial to implement (scheme and other languages that
> have call/cc like IIRC ruby and some MLs).
Indeed. Note that in some language implementations call/cc copies the
stack and is quite slow; I think this applies to Ruby.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
On Wed, 05 Apr 2006 11:04:41 +0200, Philippe Lorin wrote:
> Matthew D. Swank posted an example but I couldn't figure it out. I
> searched the web a lot and only found discussions, no CL code.
Well, I apologize if my examples were confusing, but the post would have
been even longer if I had done a proper job of explaining continuations.
Perhaps it's not much consolation, but here are your examples using the
second of the generator implementations I posted previously
(http://groups.google.com/group/comp.lang.lisp/tree/browse_frm/thread/fbda37620268811).
(defun p (x)
(monad-progn
(unit 'continuation (print x))
(unit 'continuation (terpri))))
(defmacro cstart (&body body)
;;should be its own struct
`(cons (monad-progn
gen-nil
,@body
gen-nil) nil))
(defun cstep (corout)
(and (consp corout)
(typep (car corout) 'continuation)
(setf (car corout) (next (car corout)))
t))
(defparameter *c*
(cstart
(p 1)
(yield nil)
(p 2)))
(defparameter *c1*
(cstart
(let ((x 1))
(monad-progn
(p x)
(unit 'continuation (incf x))
(yield nil)
(p x)))))
(defun f ()
(monad-progn
(p "b")
(yield nil)
(p "c")))
(defparameter *c2*
(cstart
(p "a")
(yield nil)
(f)
(p "d")))
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> Well, I apologize if my examples were confusing, but the post would have
> been even longer if I had done a proper job of explaining continuations.
You don't have to apologize :) ! I do appreciate your posts and the fact
that you take some time to write them at all. Even when I don't
understand the code fully, it helps getting closer to a solution.
Matthew D Swank wrote:
> Perhaps it's not much consolation, but here are your examples using the
> second of the generator implementations I posted previously
> (http://groups.google.com/group/comp.lang.lisp/tree/browse_frm/thread/fbda37620268811).
It is easier to read; however I can't get it to work. When I do for
instance:
(cstep *c*) ; just once
I get this:
1
2
NIL
I am not familiar with monads, but I think I understand CPS now. Your
previous example works nicely, I will look more into it.
Matthew D Swank wrote:
> Well there was an error in NEXT that I corrected in a subsequent post.
> This should work:
> <snip>
OK. It works, and it looks nice and portable. I will try to make it
lighter with macros.
Am I right if I understand that:
- wherever there is a PROGN (even if implicit, as in LET) which may call
YIELD, MONAD-PROGN must be used;
- wherever there is a function that does not call YIELD but may contain
a PROGN, UNIT must be used.
On Fri, 07 Apr 2006 13:40:22 +0200, Philippe Lorin wrote:
> Matthew D Swank wrote:
>> Well there was an error in NEXT that I corrected in a subsequent post.
>> This should work:
>> <snip>
>
> OK. It works, and it looks nice and portable. I will try to make it
> lighter with macros.
>
> Am I right if I understand that:
> - wherever there is a PROGN (even if implicit, as in LET) which may call
> YIELD, MONAD-PROGN must be used;
> - wherever there is a function that does not call YIELD but may contain
> a PROGN, UNIT must be used.
Mostly. Every expression in a monad-progn must return a continuation or a
yield, and any sequence of expressions in which a yield might occur must
be sequenced with monad-progn. On the other hand, P probably could have
been written as:
(defun p (x)
(print x)
(unit 'continuation (terpri)))
or
(defun p (x)
(print x)
(terpri)
gen-nil)
if you didn't care about the return value-- For functions/expressions
you don't need to interrupt, the important thing is to return a
continuation when your done.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.