Hi,
I'd be interested to know how one could implement generators in Common Lisp,
ideally in GCL.
The concept of generators is explained in some detail here:
http://en.wikipedia.org/wiki/Generator_(computer_science)
Slightly more precisely, I would like to see generators available in SPAD, the
extension language of the CAS axiom, which is compiled to lisp. I guess, the
first step in adding this construction to SPAD would be to understand how it
can be implemented in Lisp...
Some examples would be
factorial: Generator Integer == generate {
z: Integer := 1;
yield z;
yield z;
for n in 2.. repeat {z := z * n; yield z;}
so
next! factorial
next! factorial
...
would return the factorials, one after the other. Recursion should be allowed:
preorder(t: BinaryTree): Generator S == generate {
if not empty? t then {
yield node t;
for n in preorder left t repeat yield n;
for n in preorder right t repeat yield n;
}
}
so
g := preorder t
next! g
next! g
...
would traverse the tree t.
Martin
Check below links and see does anything fit for you:
http://cs.northwestern.edu/academics/courses/325/readings/graham/generators.html
http://series.sourceforge.net/ it's documentation in cltl2 appendix.
Iterate http://common-lisp.net/project/iterate/ also has some
generator facilities , though probably not what you want out from the
box.
cheers
Slobodan
I forgot to add that I'm aware of the thread with the same subject of 2004, and
in particular of Marco Baringer mentioning the Arnesi package, but I wonder
whether this is "state of the art". Furthermore, "an ad-hoc, bug ridden
implementation of half of call/cc." sounds a little irritating. Since call/cc
is probably more than what I need, is there a simpler solution?
Martin
MR> I forgot to add that I'm aware of the thread with the same subject of
MR> 2004, and in particular of Marco Baringer mentioning the Arnesi
MR> package, but I wonder whether this is "state of the art". Furthermore,
MR> "an ad-hoc, bug ridden implementation of half of call/cc." sounds a
MR> little irritating. Since call/cc is probably more than what I need, is
MR> there a simpler solution?
i suspect CPS-transformer is inevitable. you should get familiar with
"continuation passing style" in order to implement generators.
afaik current version of arnesi uses an interpreter, however older one was a
CPS-transformer implemented as macro.
so you can get this, or some other CPS-transformer, to see how it works and
which code it generates.
it's not that hard, actually -- at least while supporting basic stuff. some
CL features like non-local control transfers obviously do not work well with
call/cc
In article <··············@aquin.mat.univie.ac.at>,
Martin Rubey <········@yahoo.de> wrote:
> Hi,
>
> I'd be interested to know how one could implement generators in Common Lisp,
> ideally in GCL.
>
> The concept of generators is explained in some detail here:
>
> http://en.wikipedia.org/wiki/Generator_(computer_science)
>
> Slightly more precisely, I would like to see generators available in SPAD,
> the
> extension language of the CAS axiom, which is compiled to lisp. I guess, the
> first step in adding this construction to SPAD would be to understand how it
> can be implemented in Lisp...
>
>
> Some examples would be
>
> factorial: Generator Integer == generate {
> z: Integer := 1;
> yield z;
> yield z;
> for n in 2.. repeat {z := z * n; yield z;}
>
> so
>
> next! factorial
> next! factorial
> ...
>
> would return the factorials, one after the other. Recursion should be
> allowed:
>
> preorder(t: BinaryTree): Generator S == generate {
> if not empty? t then {
> yield node t;
> for n in preorder left t repeat yield n;
> for n in preorder right t repeat yield n;
> }
> }
>
> so
>
> g := preorder t
> next! g
> next! g
> ...
>
> would traverse the tree t.
>
>
>
> Martin
Read for example SICP, the Chapter about streams and delayed evaluation.
(defun make-factorial-generator ()
(let ((n 1)
(value 1))
(lambda ()
(prog1 value
(setf value (* value n))
(incf n)))))
(let ((f (make-factorial-generator)))
(dotimes (i 10)
(print (funcall f))))
Dear Rainer, Daniel,
thanks for your answers, but I must admit I do not understand.
To make things clearer consider, for example
generate
code1
yield v1
code2
for i in h repeat
code3
yield v2
Now, next! g should
* first execute code1, then
* save the local bindings
* return v1.
Calling next! g again will
* first reestablish the local bindings saved before yielding v1,
* execute code2, enter the for loop, execute code3,
* save the local bindings
* return v2
Calling next! g again will
* first reestablish the local bindings saved just before,
* execute code3
* save the local bindings
* return v2
and so on. So, the questions seem to be
+ how to save the local bindings (i.e., yield)
+ how to jump back (i.e., next!)
I do not see how I can achieve this with closures. I hope I'm missing the
obvious...
More precisely, I cannot see the "automatic" correspondence between
factorial: Generator Integer == generate {
z: Integer := 1;
yield z;
yield z;
for n in 2.. repeat {z := z * n; yield z;}
and
Rainer Joswig <······@lisp.de> writes:
> (defun make-factorial-generator ()
> (let ((n 1)
> (value 1))
> (lambda ()
> (prog1 value
> (setf value (* value n))
> (incf n)))))
D Herring <········@at.tentpost.dot.com> writes:
> The two critical parts of a generator are
> - internal state
> - a function to update and retrieve the "next value"
Ah, maybe I was not clear enough. I do know how to implement a generater given
this information. But what I rather need is to extract this information given
generate {
code1;
yield v1;
code2;
for i in h repeat {
code3;
yield v2;
}
(I wouldn't be surprised if there is no "simple" solution as Alex suggested
already.)
Martin
On Oct 24, 9:55 am, Martin Rubey <········@yahoo.de> wrote:
> Ah, maybe I was not clear enough. I do know how to implement a generater given
> this information. But what I rather need is to extract this information given
>
Well, for the simple case:
You have
> generate {
> code1;
> yield v1;
> code2;
> for i in h repeat {
> code3;
> yield v2;
>
> }
You want
(let ((n -1)
(value (values 1)))
(defun factorial-next ()
(incf n)
(setf value (case n
(0 value)
(1 value)
(t (* value n))))))
So what about:
(defgenerator (factorial-next! :value v :state n)
:code0 1
:code1 v
:code2..n (* v n))
?
Written without magic
(defmacro defgenerator ((name &key (value 'value) (state 'n))
&key code0
code1
code2..n)
`(let ((,state -1)
(,value 0))
(defun ,name ()
(incf ,state)
(setf ,value (case ,state
(0 ,code0)
(1 ,code1)
(t ,code2..n))))
Is this homework?
Anyway, extending it for more genrality is left as an excercise to the
reader.
Peter
··················@gmail.com" <·················@gmail.com> writes:
> Is this homework?
No. Please go to the top of the thread to see my reasons. Maybe I should have
stated that
* I'm a mathematician, not a computer scientist or programmer
* Lisp is not my "native" language, although I did some things in lisp
> On Oct 24, 9:55 am, Martin Rubey <········@yahoo.de> wrote:
> > Ah, maybe I was not clear enough. I do know how to implement a generator
> > given this information. But what I rather need is to extract this
> > information given
>
> Well, for the simple case:
>
> You have
>
> > generate {
> > code1;
> > yield v1;
> > code2;
> > for i in h repeat {
> > code3;
> > yield v2;
> >
> > }
>
> You want
>
> (let ((n -1)
> (value (values 1)))
> (defun factorial-next ()
> (incf n)
> (setf value (case n
> (0 value)
> (1 value)
> (t (* value n))))))
> So what about:
>
> (defgenerator (factorial-next! :value v :state n)
> :code0 1
> :code1 v
> :code2..n (* v n))
>
I still do not see how this could be extracted automatically. Do you assume
that the expression I want to compile has a rather special structure?
> (defmacro defgenerator ((name &key (value 'value) (state 'n))
> &key code0
> code1
> code2..n)
> `(let ((,state -1)
> (,value 0))
> (defun ,name ()
> (incf ,state)
> (setf ,value (case ,state
> (0 ,code0)
> (1 ,code1)
> (t ,code2..n))))
How would this take care of restoring the right variable bindings? I do not
see at all how this generalizes to arbitrary code flow.
Martin
On 24 out, 09:14, Martin Rubey <········@yahoo.de> wrote:
> * I'm a mathematician, not a computer scientist or programmer
you say you're a mathematician, but you don't seem to think like one.
Shouldn't a mathematician define the factorial function in terms of
recursion, rather than the imperative mess you insist upon? stateful
computation is evil for mathematical reasoning...
like
(define (! n)
(if (= 0 n) 1
(* n (! (- n 1)))))
; or tail recursive
(define (! n)
(let ! ((x n) (r 1))
(if (= 0 x) r
(! (- x 1) (* x r)))))
namekuseijin <············@gmail.com> writes:
> On 24 out, 09:14, Martin Rubey <········@yahoo.de> wrote:
>> * I'm a mathematician, not a computer scientist or programmer
>
> you say you're a mathematician, but you don't seem to think like one.
> Shouldn't a mathematician define the factorial function in terms of
> recursion, rather than the imperative mess you insist upon? stateful
> computation is evil for mathematical reasoning...
Nonsense. I consider myself a mathematician, too. Nevertheless, I would
like it very much if Common Lisp could do generator pattern as well as it
absorbs other programming paradigms. This functionality (which can be
based on call/cc) and hygienic macros are interesting things that
apparently can only be incorporated by rewriting large parts of basic CL
functionality.
BTW, I am quite sure that Martin Rubey does not need your help in writing
trivial recursive factorial functions.
Nicolas
On 24 out, 17:29, Nicolas Neuss <········@mathematik.uni-karlsruhe.de>
wrote:
> This functionality (which can be
> based on call/cc) and hygienic macros are interesting things that
> apparently can only be incorporated by rewriting large parts of basic CL
> functionality.
or by simply embracing and switching to Scheme.
> BTW, I am quite sure that Martin Rubey does not need your help in writing
> trivial recursive factorial functions.
are you sure? His first example was exactly an unnecessarily messy
stateful factorial...
it seems he's in love with the Python way and wonders why Lisp way
isn't like that...
namekuseijin <············@gmail.com> writes:
> > BTW, I am quite sure that Martin Rubey does not need your help in writing
> > trivial recursive factorial functions.
>
> are you sure? His first example was exactly an unnecessarily messy
> stateful factorial...
Maybe I should have framed
-------------------------------------------------------------------------------
| Slightly more precisely, I would like to see generators available in SPAD,
| the extension language of the CAS axiom, which is compiled to lisp. I guess,
| the first step in adding this construction to SPAD would be to understand how
| it can be implemented in Lisp...
-------------------------------------------------------------------------------
> it seems he's in love with the Python way and wonders why Lisp way
> isn't like that...
In fact, I'm in love with Aldor for doing maths, although I like lisp, too.
In any case: sorry, no python here.
On a more technical side, I still do not entirely understand Matthew's code.
In particular, how to allow tagbodies. Help would be greatly appreciated.
Martin
On 24 out, 17:46, Martin Rubey <········@yahoo.de> wrote:
> | Slightly more precisely, I would like to see generators available in SPAD,
why do you want generators when you can trivially turn the examples
you gave into similar
purely-functional iterative code?
the next call behaves the same, except it provides the generator
function with the next current iteration:
(define next!
(let ((i -1))
(lambda (gen)
(set! i (+ 1 i))
(gen i))))
of course, it should be easier just to call (! i) directly...
namekuseijin <············@gmail.com> writes:
> On 24 out, 17:29, Nicolas Neuss <········@mathematik.uni-karlsruhe.de>
> wrote:
>> This functionality (which can be
>> based on call/cc) and hygienic macros are interesting things that
>> apparently can only be incorporated by rewriting large parts of basic CL
>> functionality.
>
> or by simply embracing and switching to Scheme.
You should do precisely that, _if_ these two properties are more important
for you than the topics from the following non-exhaustive list: CLOS,
readmacros and infix syntax, conditions, good native code generations,
LOOP, embedding Prolog and Python and Fortran if necessary, optional static
typing with Qi, optional proving of code correctness via ACL2,
incorporating large CAS programs (Maxima, Axiom), and last, but not least,
an uncontroversial and reasonably large standard.
For me, this is only the case when I give introductory courses to
programming.
Yours,
Nicolas
In article <··············@aquin.mat.univie.ac.at>,
Martin Rubey <········@yahoo.de> wrote:
> Dear Rainer, Daniel,
>
> thanks for your answers, but I must admit I do not understand.
>
> To make things clearer consider, for example
>
> generate
> code1
> yield v1
> code2
> for i in h repeat
> code3
> yield v2
>
>
> Now, next! g should
>
> * first execute code1, then
> * save the local bindings
> * return v1.
>
> Calling next! g again will
>
> * first reestablish the local bindings saved before yielding v1,
> * execute code2, enter the for loop, execute code3,
> * save the local bindings
> * return v2
>
> Calling next! g again will
>
> * first reestablish the local bindings saved just before,
> * execute code3
> * save the local bindings
> * return v2
>
> and so on. So, the questions seem to be
>
> + how to save the local bindings (i.e., yield)
> + how to jump back (i.e., next!)
Why would you want to use something like 'yield'?
Actually it looks a bit like the famous 'come from' statement.
>
> I do not see how I can achieve this with closures. I hope I'm missing the
> obvious...
>
> More precisely, I cannot see the "automatic" correspondence between
>
> factorial: Generator Integer == generate {
> z: Integer := 1;
> yield z;
> yield z;
> for n in 2.. repeat {z := z * n; yield z;}
Why would you want to save the state of execution in this case?
I really would say that
a simple functional approach is much easier to write,
understand and combine.
The yield-based version is a glorified imperative
version. You call it, then you jump out and then you
jump back in. Each time you call it, you may jump
to a different place.
>
> and
>
> Rainer Joswig <······@lisp.de> writes:
>
> > (defun make-factorial-generator ()
> > (let ((n 1)
> > (value 1))
> > (lambda ()
> > (prog1 value
> > (setf value (* value n))
> > (incf n)))))
This version is just a simple function (with environment), that you call
and each time it simply returns and gives you a result. No
multiple yields.
As long as you only need a simple internal state, you
don't really need the overhead of internal execution
state.
>
> D Herring <········@at.tentpost.dot.com> writes:
>
> > The two critical parts of a generator are
> > - internal state
> > - a function to update and retrieve the "next value"
>
> Ah, maybe I was not clear enough. I do know how to implement a generater
> given
> this information. But what I rather need is to extract this information
> given
>
> generate {
> code1;
> yield v1;
> code2;
> for i in h repeat {
> code3;
> yield v2;
> }
That's 'fine' in Python. Idiomatic Common Lisp looks different.
>
>
> (I wouldn't be surprised if there is no "simple" solution as Alex suggested
> already.)
>
> Martin
Rainer Joswig <······@lisp.de> writes:
> Why would you want to use something like 'yield'?
It seems that I didn't make my goal precise enough: I want to enhance an
existing compiler, which compiles from SPAD to common lisp.
Five lines of history:
SPAD is a language useful for describing mathematics, it is the extendion
language used in axiom. SPAD was much improved, given clear semantics and
renamed Aldor, and reimplemented in C. Unfortunately, Aldor cannot easily be
bundled with SPAD, since their licences are incompatible. I would like to see
the SPAD compiler improved to accept the Aldor language.
-------------------------------------------------------------------------------
As I said:
-------------------------------------------------------------------------------
| Slightly more precisely, I would like to see generators available in SPAD,
| the extension language of the CAS axiom, which is compiled to lisp. I guess,
| the first step in adding this construction to SPAD would be to understand how
| it can be implemented in Lisp...
-------------------------------------------------------------------------------
> > More precisely, I cannot see the "automatic" correspondence between
> >
> > factorial: Generator Integer == generate {
> > z: Integer := 1;
> > yield z;
> > yield z;
> > for n in 2.. repeat {z := z * n; yield z;}
>
> Why would you want to save the state of execution in this case?
Aldor provides a single iteration construct which reads
for e in g repeat { do something with e }
where g is a generator. In Aldor, a generator can be defined in two ways, one
of which is by using the generate ... yield construction, the other by
explicitly providing empty?, step!, value and bound functions.
> I really would say that a simple functional approach is much easier to write,
> understand and combine.
Probably in Lisp. But SPAD and Aldor are not Lisp. Many things work very well
in lisp, but for a CAS, the concepts provided by SPAD and Aldor prove extremely
useful.
> > generate {
> > code1;
> > yield v1;
> > code2;
> > for i in h repeat {
> > code3;
> > yield v2;
> > }
>
> That's 'fine' in Python. Idiomatic Common Lisp looks different.
I (think I) did not ask for being taught idiomatic common lisp. I wanted to be
taught how I could "compile" Aldor style generators to common lisp.
Is my goal clearer now?
Martin
In article <··············@aquin.mat.univie.ac.at>,
Martin Rubey <········@yahoo.de> wrote:
> Rainer Joswig <······@lisp.de> writes:
>
> > Why would you want to use something like 'yield'?
>
> It seems that I didn't make my goal precise enough: I want to enhance an
> existing compiler, which compiles from SPAD to common lisp.
>
> Five lines of history:
>
> SPAD is a language useful for describing mathematics, it is the extendion
> language used in axiom. SPAD was much improved, given clear semantics and
> renamed Aldor, and reimplemented in C. Unfortunately, Aldor cannot easily be
> bundled with SPAD, since their licences are incompatible. I would like to
> see
> the SPAD compiler improved to accept the Aldor language.
> ------------------------------------------------------------------------------
> -
>
> As I said:
> ------------------------------------------------------------------------------
> -
> | Slightly more precisely, I would like to see generators available in SPAD,
> | the extension language of the CAS axiom, which is compiled to lisp. I
> | guess,
> | the first step in adding this construction to SPAD would be to understand
> | how
> | it can be implemented in Lisp...
> ------------------------------------------------------------------------------
I see. Well, one needs to know what the syntax and semantics should be???
It would not be that trivial in Common Lisp, since it does not have
the equivalent of 'yield' in the standard. Also there is
no CALL-WITH-CURRENT-CONTINUATION, which I guess
could be use to implement it.
Rainer Joswig <······@lisp.de> writes:
> I see. Well, one needs to know what the syntax and semantics should be???
Could you tell me where I need to be more precise?
> It would not be that trivial in Common Lisp, since it does not have the
> equivalent of 'yield' in the standard. Also there is no
> CALL-WITH-CURRENT-CONTINUATION, which I guess could be use to implement it.
OK, so the thread pointed out by Ivan seems quite reasonable. I was worried
because some where offering a "simple solution" (closures), others something
rather sophisticated (a code walker). Matthew's code seems to be inbetween,
although I must admit that I fail to understand "monad-progn" so far.
Martin
Martin Rubey wrote:
> I'd be interested to know how one could implement generators in Common Lisp,
> ideally in GCL.
The two critical parts of a generator are
- internal state
- a function to update and retrieve the "next value"
Whether this uses hidden symbols in a function definition
(defun gen-pow-1 (n)
(let ((n0 n)
(val 1))
(lambda ()
(prog1 val
(setf val (* val n0))))))
(let ((f (gen-pow-1 3)))
(dotimes (i 10)
(print (funcall f))))
or an explicit structure that follows a standard interface
(defclass generator nil nil)
(defgeneric get-next (generator)
(:documentation "Get the next generator value."))
(defclass pow-2 (generator)
((n0 :initform 3)
(val :initform 1)))
(defmethod get-next ((pow pow-2))
(let ((v (slot-value pow 'val)))
(setf (slot-value pow 'val)
(* v (slot-value pow 'n0)))
v))
(let ((p (make-instance 'pow-2)))
(dotimes (i 10)
(print (get-next p))))
its all the same idea.
- Daniel
This thread may also help:
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/fbda37620268811/c558bf7e6feb5d55?hl=en&lnk=st&q=generator+monadic+continuations+defun#
Ivan Shvedunov <·······@depni.sinp.msu.ru> writes:
> This thread may also help:
> http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/fbda37620268811/c558bf7e6feb5d55?hl=en&lnk=st&q=generator+monadic+continuations+defun#
Many thanks for this one! Since I'm lazy:
* I do not quite understand what "monadic style" means. In particular, what
is monad-progn for? For example, in the paste I find:
(defun times (n)
(as-generator
(luup times ((m n))
(if (< m 1)
gen-nil
(monad-progn
(yield (- n m))
(times (1- m)))))))
What would be wrong with
(defun times (n)
(as-generator
(luup times ((m n))
(if (< m 1)
gen-nil
(progn
(yield (- n m))
(times (1- m)))))))
???
* Matthew wrote
> I have written a small generator facility which has shown up here from time
> to time in various forms that allows the user to re-enter a running
> computation using a fairly restricted subset of lisp. The code's not pretty
> or efficient, but does include some examples of what generators can do:
How serious should I take this?
Martin
Martin Rubey <········@yahoo.de> writes:
> Many thanks for this one!
OK, I think I understand monad-progn and monad-let* now, at least a little bit.
I still do not see how to implement an apropriate tagbody form though. I.e.,
how could I define a generator like
(defun iter (n)
(as-generator
(yield 1) (dotimes (i n) (yield i))))
(I'm to lazy to make up something non-trivial, please excuse.)
I guess I would need to implement something analogous to monad-let* and
monad-progn?
Many thanks in advance,
Martin
Martin Rubey wrote:
> Slightly more precisely, I would like to see generators available in SPAD, the
> extension language of the CAS axiom, which is compiled to lisp. I guess, the
> first step in adding this construction to SPAD would be to understand how it
> can be implemented in Lisp...
A few questions:
Where is the SPAD language described? I've used Axiom a few times,
but never got proficient with SPAD. What's the syntax/expected
behavior of SPAD generators (if they exist)? How does SPAD get
converted to Lisp? Is there an intermediate product (i.e. a lispish
syntax tree) that could be easily walked by a lisp function or macro?
> preorder(t: BinaryTree): Generator S == generate {
> if not empty? t then {
> yield node t;
> for n in preorder left t repeat yield n;
> for n in preorder right t repeat yield n;
> }
> }
I'm not saying its pretty (or even idiomatic), but the following just
took a few minutes to implement; and the pattern shouldn't be too hard
to generalize.
;;;;; BEGIN lisp
#| SPAD input:
preorder(t: BinaryTree): Generator S == generate {
if not empty? t then {
yield node t;
for n in preorder left t repeat yield n;
for n in preorder right t repeat yield n;
}
}
|#
;; Lisp "equivalent"
(defstruct node
(value nil)
(left nil)
(right nil))
(defun make-preorder (tree)
(let ((node tree) ; the node we are processing
(recurse nil) ; the generator to process children
(state (if tree :node :done))) ; which "yield" to process
(labels ((gen ()
(case state
(:node
(setf recurse (make-preorder (node-left node))
state :left)
(node-value node))
(:left
(let ((val (funcall recurse)))
(if val
val
(progn (setf recurse (make-preorder
(node-right node))
state :right)
(gen)))))
(:right
(let ((val (funcall recurse)))
(if val
val
(progn (setf recurse nil
state :done)
nil))))
(:done
nil))))
#'gen)))
(let ((tree (make-node
:value 1
:left (make-node
:value :l)
:right (make-node
:value :r
:left (make-node
:value :rl)
:right (make-node
:value :rr)))))
(let ((gen (make-preorder tree)))
(dotimes (n 10)
(format t "value[~A]: ~A~%" n (funcall gen)))))
;;;;; END lisp
- Daniel
Dear Daniel,
D Herring <········@at.tentpost.dot.com> writes:
> Where is the SPAD language described?
I like to describe the *current* situation as follows, although that's probably
biased and certainly not historically correct:
-------------------------------------------------------------------------------
There is a language, called Aldor, which is described in the "Aldor Compiler
User Guide"
http://www.aldor.org/wiki/index.php/User_Guides_for_Compiler_and_Libraries
This language has two implementations:
* one is, again, called Aldor, pretty complete, implemented in C, semi-free (no
commercial use)
* the other is called SPAD, quite incomplete, implemented on top of common
lisp, free (modified BSD)
SPAD is missing some essential features from Aldor. I list them in order of
severity:
- types are not really first class objects ("dependent types" are supported
only on the constructor level),
- post facto extensions are not supported,
- generators are missing
- exceptions are missing
-------------------------------------------------------------------------------
Historically, SPAD was developed as extension language of axiom, probably in a
bottom up fashion. Around 2000, Stephen Watt (et al., probably) designed
Aldor, abstracting the essentials of SPAD. The result is unbelievably
powerful, if you are interested in implementing mathematics.
-------------------------------------------------------------------------------
> What's the syntax/expected behavior of SPAD generators (if they exist)?
Personally, along with a few others, I would like SPAD to implement Aldor
fully. Thus, SPAD generators should just behave as described in the "Aldor
Compiler User Guide", II.9, pages 113ff. http://aldor.org/docs/HTML/chap9.html
As Waldek Hebisch pointed out, these generators are not entirely general: the
"yield" statement must appear within a "generate".
> How does SPAD get converted to Lisp? Is there an intermediate product
> (i.e. a lispish syntax tree) that could be easily walked by a lisp function
> or macro?
Unfortunately, I know very little about that, but as far as I know: yes. For
details, you should ask on the mailing lists. To get an impression, here is
the result of translating "foo" from the following stupid thing:
)abb package TEST Test
Test(): with
foo: Integer -> Integer
== add
foo n ==
j: Integer := 1783
for i in 1..n repeat
k := i*729
j := j + k
output(i::OutputForm)$OutputPackage
j
(DEFUN |TEST;foo;2I;1| (|n| $)
(PROG (|i| |k| |j|)
(RETURN
(SEQ (LETT |j| 1783 |TEST;foo;2I;1|)
(SEQ (LETT |i| 1 |TEST;foo;2I;1|) G190
(COND ((QSGREATERP |i| |n|) (GO G191)))
(SEQ (LETT |k| (* |i| 729) |TEST;foo;2I;1|)
(LETT |j| (+ |j| |k|) |TEST;foo;2I;1|)
(EXIT (SPADCALL (SPADCALL |i| (QREFELT $ 8))
(QREFELT $ 11))))
(LETT |i| (QSADD1 |i|) |TEST;foo;2I;1|) (GO G190) G191
(EXIT NIL))
(EXIT |j|)))))
> I'm not saying its pretty (or even idiomatic), but the following just took a
> few minutes to implement; and the pattern shouldn't be too hard to
> generalize.
I see. Hm, I begin to realise that this is beyond my skills/time frame,
though. It seems that your approach differs quite a lot from the one of
Matthew Swank?
Many thanks,
Martin
> ;;;;; BEGIN lisp
> #| SPAD input:
> preorder(t: BinaryTree): Generator S == generate {
> if not empty? t then {
> yield node t;
> for n in preorder left t repeat yield n;
> for n in preorder right t repeat yield n;
> }
> }
> |#
>
> ;; Lisp "equivalent"
> (defstruct node
> (value nil)
> (left nil)
> (right nil))
>
> (defun make-preorder (tree)
> (let ((node tree) ; the node we are processing
> (recurse nil) ; the generator to process children
> (state (if tree :node :done))) ; which "yield" to process
> (labels ((gen ()
> (case state
> (:node
> (setf recurse (make-preorder (node-left node))
> state :left)
> (node-value node))
> (:left
> (let ((val (funcall recurse)))
> (if val
> val
> (progn (setf recurse (make-preorder (node-right node))
> state :right)
> (gen)))))
> (:right
> (let ((val (funcall recurse)))
> (if val
> val
> (progn (setf recurse nil
> state :done)
> nil))))
> (:done
> nil))))
> #'gen)))
>
>
> (let ((tree (make-node
> :value 1
> :left (make-node
> :value :l)
> :right (make-node
> :value :r
> :left (make-node
> :value :rl)
> :right (make-node
> :value :rr)))))
> (let ((gen (make-preorder tree)))
> (dotimes (n 10)
> (format t "value[~A]: ~A~%" n (funcall gen)))))
> ;;;;; END lisp
>
> - Daniel
On Oct 25, 2:41 am, Martin Rubey <········@yahoo.de> wrote:
> Historically, SPAD was developed as extension language of axiom, probably in a
> bottom up fashion. Around 2000, Stephen Watt (et al., probably) designed
> Aldor, abstracting the essentials of SPAD. The result is unbelievably
> powerful, if you are interested in implementing mathematics.
>
Aldor is certainly older than that. I was working on the compiler in
2003 and the code base dates back to the early 90s. (The preface in
the user's guide is dated 1994). You're right that it's very good for
mathematics, though. My background isn't in applied mathematics, but
after all those Aldor meetings, I started to get familiar with Gr�bner
bases. :)
> I see. Hm, I begin to realise that this is beyond my skills/time frame, though.
>
Full support of Aldor generators in Lisp (and thus SPAD, I'm assuming)
would require a bit of effort, mostly to handle the yield construct.
You could certainly implement them as a macro, but you would need a
code walker to properly create the environment. I expect they would
be implemented as closures, maybe using a TAGBODY to jump to the
required locations after re-ordering some of the code.
As far as I know, Aldor lets you view code generation and will
generate Lisp code. You can use the -S option to the compiler to get
it, in case you didn't already know. Might give you an idea of how
they are done.
Generators are something I missed when I started using Lisp and I tend
to write ad hoc ones like those described earlier. This does get
tedious after a while, though. I've been contemplating making some
form of Aldor's generators (which are much the same as Python's, I
believe) for Lisp just for my own use. Perhaps I'll get on that.
Just for interest's sake, here's another example of a generator that
uses classes and closures, complete with the Aldor interface of step!,
empty?, value and bound. (I sincerely hope that Google Groups doesn't
mess up the code formatting).
;;; Here's an example that you gave earlier
(defun iter (n)
(as-generator
(yield 1) (dotimes (i n) (yield i))))
;;; And here's an implementation of it
(defclass generator ()
((empty? :initform nil :accessor empty?)
(bound :initform -1 :accessor bound)
(value :initform nil :accessor value)
(closure :initarg :closure :accessor closure)))
(defgeneric step! (gen)
(:method ((gen generator))
(cond
((empty? gen) nil)
(t (funcall (closure gen) gen) (value gen)))))
(defun iter (n)
(let ((place 1)
(counter 0))
(make-instance
'generator
:closure
#'(lambda (gen)
(block my-iter
(tagbody
0 (case place
(1 (go 1))
(2 (go 2)))
1 (setf place 2)
(setf (value gen) 1)
(unless (< counter n) (setf (empty? gen) t))
(return-from my-iter nil)
2 (when (< counter n) (setf (value gen) counter))
(incf counter)
(unless (< counter n) (setf (empty? gen) t))
(return-from my-iter nil)))))))
(defparameter *gen* (iter 5))
(loop until (empty? *gen*) do (print (step! *gen*)))
=>
1
0
1
2
3
4
NIL
I used the TAGBODY to give you an idea of how they work, although you
don't need them in this case. The tags roughly correspond to the the
yields in the ideally concieved original. The semantics are close to
Aldor's, although I don't remember all the nuances. (I don't know
what an empty generator returns, for example.) Obviously, the type
issues are not addressed either.
On Oct 23, 9:01 am, Martin Rubey <········@yahoo.de> wrote:
> I'd be interested to know how one could implement generators in Common Lisp,
> ideally in GCL.
If you have threads, finalizers and weak references, you can implement
generators using threads. I don't know if that would be an acceptable
solution for real use of generators, but it might possibly be an
option.
I've attached an example implementation for ACL7, it depends on the
implementations thread/gc-features so it would take some porting.
Also, I've not tested it all that much so there might be bugs.
Regards,
Iver Odin Kvello
iok at selvaag dot no
<---- cut here --->
;;;; Copyright (c) 2007, Selvaag Bluethink AS
;;;; All rights reserved.
;;;;
;;;; Redistribution and use in source and binary forms, with or
without
;;;; modification, are permitted provided that the following
conditions are met:
;;;; * Redistributions of source code must retain the above
copyright
;;;; notice, this list of conditions and the following
disclaimer.
;;;; * Redistributions in binary form must reproduce the above
copyright
;;;; notice, this list of conditions and the following
disclaimer in the
;;;; documentation and/or other materials provided with the
distribution.
;;;; * Neither the name of Selvaag Bluethink AS nor the
;;;; names of its contributors may be used to endorse or promote
products
;;;; derived from this software without specific prior written
permission.
;;;;
;;;; THIS SOFTWARE IS PROVIDED BY SELVAAG BLUETHINK AS ``AS IS'' AND
ANY
;;;; EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED
;;;; WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE
;;;; DISCLAIMED. IN NO EVENT SHALL SELVAAG BLUETHINK AS BE LIABLE FOR
ANY
;;;; DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES
;;;; (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
OR SERVICES;
;;;; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND
;;;; ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
LIABILITY, OR TORT
;;;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS
;;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
;;; This file implements generators using threads. The worst problem
is GC'ing: The process must
;;; not contain any live reference to the container, but it does need
to retain a weak reference.
;;; The finalizer for the generator is simple, however.
;;; Also, the code is specific to ACL7/8 and not portable.
(defpackage :generators
(:documentation "Generators using threads")
(:nicknames :gen)
(:use :common-lisp)
(:export :generator :make-generator :generate-next :yield))
(in-package :generators)
;; The generator-object contains a value-slot, the process and a
synchronization object.
(defstruct (generator (:constructor %make-generator))
process
next-value
;; GATES are ACL 7.0-specific, but neccessary to allow mp:process-
wait to not spend an eternity
;; for each generated value.
(wait-object (mp:make-gate t)))
;; We need a finalization on the generator to avoid having processes
kept by the system.
(defun generator-destructor (generator)
(mp:process-kill (generator-process generator)))
(defun get-process-generator (process)
(let ((box (getf (mp:process-property-list process) :generator-
process)))
(if box (values (aref box 0) t)
(values nil nil))))
(defun get-weak-generator-box (process)
(let ((box (getf (mp:process-property-list process) :generator-
process)))
box))
(defun make-generator-from-thunk (thunk)
(let ((generator-box (excl:weak-vector 1)))
(symbol-macrolet ((generator (aref generator-box 0)))
;; The strong reference to the generator must not be visible in
the
;; process-func closure, but must be here to avoid having the
generator
;; GC'ed before we can return.
(let ((strong-reference-to-the-generator (%make-generator))
(process-func
#'(lambda ()
;; Must let-bind the funcall, and evaluate it in the SETF below,
;; or a reference to the generator will be alive as long
;; as this closure.
(let ((final-value (funcall thunk)))
(setf (generator-next-value generator) final-value)
(mp:open-gate (generator-wait-object generator))))))
;; Initialize the weak reference, and add a finalizer
(setf generator strong-reference-to-the-generator)
(excl:schedule-finalization generator #'generator-destructor)
;; Initialize the generator process and return the generator
(prog1 generator
(let ((process (mp:make-process :name (symbol-name (gensym
"Generator")) :run-immediately nil)))
(setf (generator-process generator) process)
(mp:process-preset process process-func)
;; Store the weak reference to the generator in the process
(setf (getf (mp:process-property-list process) :generator-
process) generator-box)))))))
(defmacro make-generator (&body body)
"Make a generator from BODY"
`(make-generator-from-thunk
(lambda () ,@body)))
(defun generate-next (generator)
"Get the next value from a generator"
(let ((process (generator-process generator)))
(if (eql :terminated (mp::process-state process)) ;; MP:PROCESS-
STATE isn't exported
(error "Generator exhausted")
(let ((wait-object (generator-wait-object generator)))
(system::close-gate wait-object)
(mp:process-enable process)
(mp:process-wait "generating" #'mp:gate-open-p wait-object)
(generator-next-value generator)))))
(defun yield (value)
"Return a value from a generator continuing from the yield for the
next value."
;; YIELD too must not capture any references to its generator.
(let* ((process mp:*current-process*)
(generator-box (get-weak-generator-box process)))
(symbol-macrolet ((generator (aref generator-box 0)))
(cond
((not generator-box)
;; Called in a generator-process the generator of which doesn't exist
anymore,
;; or in a non-generating process
(return-from yield value))
(t
(progn (setf (generator-next-value generator) value)
;; we must open the gate and disable ourselves atomically.
(mp:without-scheduling
(system::open-gate (generator-wait-object generator))
(mp:process-disable process))))))))
;;; Examples
(defun generate-integers (&optional n)
(make-generator
(loop for x = 1 then (1+ x)
while (or (not n) (<= x n))
do (yield x))))
(defun doit ()
(loop with integers = (generate-integers 7)
for x = (generate-next integers)
while x collect x))
(defun doit2 ()
(loop with integers = (generate-integers)
for x = (generate-next integers)
while (< x 35)
when (oddp x)
collect x))