I'm learning Common Lisp, coming from a Java/Python/Ruby background,
and I've just about completed ANSI Common Lisp. One of the examples
in the book is the Henley program. Contained within this example,
there is a function called READ-TEXT that parses text from a stream,
and for each valid token found, it invokes another function called
SEE. Here is the original function with comments on lines relevant to
this email:
(defun read-text (s)
(let ((buffer (make-string maxword))
(pos 0))
(do ((c (read-char s nil :eof)
(read-char s nil :eof)))
((eql c :eof))
(if (or (alpha-char-p c) (char= c #\'))
(progn
(setf (aref buffer pos) c)
(incf pos))
(progn
(unless (zerop pos)
(see (intern (string-downcase ; SEE invoked
(subseq buffer 0 pos))))
(setf pos 0))
(let ((p (punc c)))
(if p (see p)))))))) ; SEE invoked
While working on one of the exercise questions, I decided that I
wanted to reuse the parsing code. Thus, I modified READ-TEXT to
accept a functional argument so I could pass my own function to be
called when a valid token is found instead of SEE. The resulting code
is here:
(defun read-text (s fn) ; New argument
(let ((buffer (make-string maxword))
(pos 0))
(do ((c (read-char s nil :eof)
(read-char s nil :eof)))
((eql c :eof))
(if (or (alpha-char-p c) (char= c #\'))
(progn
(setf (aref buffer pos) c)
(incf pos))
(progn
(unless (zerop pos)
(funcall fn (intern (string-downcase ; FN invoked
(subseq buffer 0 pos))))
(setf pos 0))
(let ((p (punc c)))
(if p (funcall fn p)))))))) ; FN invoked
After I completed this, I realized it would be more elegant if I had
used a generator instead of passing a callback function to READ-TEXT.
As a result, I create READ-TEXT-GENERATOR which returns a closure that
returns the next token each time its invoked. Unfortunately, I had to
modify the code somewhat because READ-TEXT can find more than one
token per invocation. In the code below, I simply use s list to store
up tokens found on a single pass, and the next time the lambda is
invoked, I check to see if there were any tokens found from the
previous invocation, and simply return the next one off the list:
(defun read-text-generator (str) ; Generator
(let ((buffer (make-string maxword)) ; Closure variables
(next nil) ; stores tokens
(pos 0)
(s str))
#'(lambda ()
(if next ; any leftover from
(pop next) ; prev invocation?
(do ((c (read-char s nil :eof)
(read-char s nil :eof)))
((eql c :eof))
(if (or (alpha-char-p c) (char= c #\'))
(progn
(setf (aref buffer pos) c)
(incf pos))
(progn
(unless (zerop pos)
(setf next ; store the token
(append next (list (intern (string-downcase
(subseq buffer 0 pos))))))
(setf pos 0))
(let ((p (punc c)))
(if p (setf next ; store the token
(append next (list p)))))))
(when next
(return (pop next)))))))) ; return a single token
Is there a better idiom for this type of scenario? How does one
implement generators in lisp? Is there a way I can maintain the
simple logic of the original READ-TEXT yet obtain the functionality of
a generator?
For example, in the Python world (I'm not trolling here, I'm
legitimately trying to learn the Lisp-way of doing things), one could
use the original READ-TEXT function and simply replace the calls to
SEE with the "yield" operator, which returns from the function at that
point to the caller, but saves the execution state so that the next
time the function is invoked, it resumes from where it left off. For
example (the multiple assignment works like Lisp's PSETQ):
def fib():
a, b = 0, 1
while 1:
yield b
a, b = b, a+b
fib() => 1
fib() => 1
fib() => 2
fib() => 3
...
If I could do something like this in READ-TEXT, it would not require
any changes to the existing logic (unlike the closure I return from
MAKE-TEXT-READER). I'm also trying to wrap my head around CPS, can
that be used in this scenario? I've seen simple examples of CPS (from
the Little Schemer), but cannot see how one could apply that here (if
it even is applicable) I would appreciate any insight into the matter.
Thank you,
Pete
··················@kazmier.com writes:
> How does one implement generators in lisp? Is there a way I can
> maintain the simple logic of the original READ-TEXT yet obtain the
> functionality of a generator?
Look at Richard Waters's SERIES package.
In particular this part:
http://www-2.cs.cmu.edu/Groups/AI/html/cltl/clm/node362.html
I don't have a reference handy for the code, but it is around.
Joe Marshall wrote:
> Look at Richard Waters's SERIES package.
> In particular this part:
>
> http://www-2.cs.cmu.edu/Groups/AI/html/cltl/clm/node362.html
>
> I don't have a reference handy for the code, but it is around.
http://series.sf.net
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Joe Marshall <···@ccs.neu.edu> writes:
> Look at Richard Waters's SERIES package.
> In particular this part:
>
> http://www-2.cs.cmu.edu/Groups/AI/html/cltl/clm/node362.html
>
> I don't have a reference handy for the code, but it is around.
I took a look at the document (specifically Appendix A and B), but I
was hoping for some technique where READ-TEXT could still be written
in its natural form (with the calls to SEE simply replaced with some
magical call), thus mimicking the functionality of the Python "yield"
operator.
From what I understood, the above link seems to indicate that I need
to either completely rewrite READ-TEXT and break it into two functions
to be passed as arguments to SCAN-FN function, or that I need
READ-TEXT to return a list of all the tokens which is then simply
wrapped in a call to SCAN. Both of the above defeat the purpose of my
original question. In the first case, I'd like to be able to write
READ-TEXT in a natural manner (without going through machinations to
maintain state), and in the second case, it requires that all tokens
are parsed beforehand rather than when they are actually needed by the
caller.
Is this sort of thing possible using fancy footwork with macros and
closures? Is this a good case where continuations would make life
simpler? Alternatively, is there another solution that enables both
the caller of READ-TEXT and the implementor of READ-TEXT to use/write
their code without having to worry about state?
I'm sure I'm doing a terrible job of communicating what I'm looking
for so thanks in advance for bearing with me.
Thanks,
Pete
··················@kazmier.com writes:
> I took a look at the document (specifically Appendix A and B), but I
> was hoping for some technique where READ-TEXT could still be written
> in its natural form (with the calls to SEE simply replaced with some
> magical call), thus mimicking the functionality of the Python "yield"
> operator.
That's not natural. That's just slow and bulky. SERIES compiles the code
down to an iterative loop if the code describes an iterative loop.
> From what I understood, the above link seems to indicate that I need
> to either completely rewrite READ-TEXT and break it into two functions
> to be passed as arguments to SCAN-FN function
Er... how so? The only scanning you're doing there is scanning the
stream. But that has nothing to do with the parser, which should be an
optimizable-series-function that takes a series of characters.
(parse (scan-stream s)) for example.
> or that I need READ-TEXT to return a list of all the tokens which is
> then simply wrapped in a call to SCAN.
No need. It can return a SERIES which is then further processed by the
application.
> Both of the above defeat the purpose of my
> original question. In the first case, I'd like to be able to write
> READ-TEXT in a natural manner (without going through machinations to
> maintain state),
What does that mean? With series, you can split the series into two
subseries, one containing the text of the token and one containing the
remainder of the characters.
> and in the second case, it requires that all tokens
> are parsed beforehand rather than when they are actually needed by the
> caller.
The whole _point_ of SERIES is that you get lazy-functional iteration.
> Is this sort of thing possible using fancy footwork with macros and
> closures?
That's what SERIES is.
> Is this a good case where continuations would make life
> simpler?
You can pass a continuation that closes over the current parsing state
into some function SEE that processes the token and then calls the
continuation to do this recursively, I suppose. But that's just turning
a simple iteration into a co-recursion.
> Alternatively, is there another solution that enables both
> the caller of READ-TEXT and the implementor of READ-TEXT to use/write
> their code without having to worry about state?
That sounds to me like you're asking for code that has no state, yet
does different things each time it's executed. We call that "magic",
a.k.a. "fantasy".
> I'm sure I'm doing a terrible job of communicating what I'm looking
> for so thanks in advance for bearing with me.
SERIES was designed to efficiently do what you're asking for here, and
your communication was plenty clear enough to let us figure that out. :)
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
··················@kazmier.com writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
>> Look at Richard Waters's SERIES package.
>> In particular this part:
>>
>> http://www-2.cs.cmu.edu/Groups/AI/html/cltl/clm/node362.html
>>
>> I don't have a reference handy for the code, but it is around.
>
> I took a look at the document (specifically Appendix A and B), but I
> was hoping for some technique where READ-TEXT could still be written
> in its natural form (with the calls to SEE simply replaced with some
> magical call), thus mimicking the functionality of the Python "yield"
> operator.
The NEXT-OUT function is the magical call if you use the
generators/collectors code.
> From what I understood, the above link seems to indicate that I need
> to either completely rewrite READ-TEXT and break it into two functions
> to be passed as arguments to SCAN-FN function, or that I need
> READ-TEXT to return a list of all the tokens which is then simply
> wrapped in a call to SCAN.
There is a small concession to series, but read-text is basically the
same:
(defun read-text (s)
(declare (optimizable-series-function))
(let ((buffer (make-string maxword))
(pos 0))
(choose-if #'identity
(scan-fn 't
(lambda () nil)
(lambda (prev)
(let ((c (read-char s nil :eof)))
(cond ((eql c :eof) c)
((or (alpha-char-p c) (char= c #\'))
(setf (aref buffer pos) c)
(incf pos)
nil)
((not (zerop pos))
(prog1
(intern (string-downcase
(subseq buffer 0 pos)))
(setq pos 0)))
((punc c))
(t nil))))
(lambda (prev)
(eql prev :eof))))))
And you'd use it like this:
(collect 'list (read-text s))
--
~jrm
Joe Marshall <·············@comcast.net> writes:
> The NEXT-OUT function is the magical call if you use the
> generators/collectors code.
Right, I understand that, and I also understand that the series
package permits one to process only whats needed by the caller. I
guess my problem is that in my original example (from ANSI Common
Lisp), READ-TEXT can return one or MORE tokens for a single pass.
I believe your example is not a correct translation of the original,
because the punctuation character that terminates a word will never be
returned. And from what I understand, the lambda which is passed as
an argument to SCAN-FN should only generate the next token (not
multiple tokens), which brings us back to having to maintain
additional state in that function because it may or may not generate
more than one token. After coding that additional state handling, we
more or less get READ-TEXT-GENERATOR from my original post. [Assuming
of course, I correctly understand your example.]
Sticking with the use of a callback is less than ideal as the caller
has no control over when its going to be called, which was my original
motivation for the generator. And from my Python experience, creating
a generator is trivial, simply add the 'yield' call in place of where
a callback would normally have been called. Subsequent invocations of
READ-TEXT would start right where the 'yield' left off, and thus the
READ-TEXT function would be able to return multiple tokens in a single
pass without having to modify the code to maintain additional state.
As I type this, It seems someone else has posted a response that looks
exactly like what I was searching for (although I was under the
impression that CL did not have continuations). Joe, thank you very
much for taking the time to respond to my query in such detail.
Thanks,
Pete
Pete Kazmier <··················@kazmier.com> writes:
> Joe Marshall <·············@comcast.net> writes:
>
>> The NEXT-OUT function is the magical call if you use the
>> generators/collectors code.
>
> Right, I understand that, and I also understand that the series
> package permits one to process only whats needed by the caller. I
> guess my problem is that in my original example (from ANSI Common
> Lisp), READ-TEXT can return one or MORE tokens for a single pass.
Yes, that is a sticky point for series. There are a couple of
solutions, but they don't really satisfy the requirement for coding
`naturally'. Since a single input can produce more than one token,
this makes the output an `offline' series. My initial thought is to
make READ-TEXT always return two tokens per pass, one of which may be
NIL, and then use CHOOSE-IF to remove those.
I have to admit that I'm not entirely satisfied by series. I have,
however, been able to use them to good effect despite the occasional
offline series. One example is a UTF-8 to UCS-2 converter. This has
the opposite problem of multiple reads returning only one token. The
converting transducer itself is a bit ugly, but when I can write:
(collect 'string (ucs-2->latin-1 (utf-8->ucs-2 (scan-stream s))))
I think it is worth the occasional pain.
> As I type this, It seems someone else has posted a response that looks
> exactly like what I was searching for (although I was under the
> impression that CL did not have continuations).
CL has escaping (non-reentrant) continuations.
> Joe, thank you very much for taking the time to respond to my query
> in such detail.
You're welcome.
Joe Marshall <···@ccs.neu.edu> writes:
> Since a single input can produce more than one token, this makes the
> output an `offline' series.
Why is this so? Or, why does it matter? If you did go ahead and add
the queuing of tokens in per the original READ-TEXT-GENERATOR,
couldn't you just avoid calling on SCAN-FN until the token queue is
empty? Does the difference here lead to the preclusion of optimization
discussed in CLtL2 A.3.1?� Later we find this definition:�
A series input port or series output port of a series function is
on-line if and only if it is processed in lockstep with all the
other on-line ports as follows: the initial element of each on-line
input is read, then the initial element of each on-line output is
written, then the second element of each on-line input is read, then
the second element of each on-line output is written, and so
on. Ports that are not on-line are off-line.
So if we were to queue tokens, some calls would draw the next
character from the stream, while some calls would merely dequeue a
pending token. That breaks the "lockstep" constraint above. But why
should that preclude such a series function from behaving in the
expected optimal lazy fashion?
Finally, A.3.3 finishes up with:
Note that off-line ports virtually never arise when defining
scanners or reducers.
Isn't that exactly what we've proposed here -- a scanner that would be
off-line because it injects a conditional branch inside the series
expression?
I find SERIES rather pleasant to use as is, but adding to it is big
conceptual hill to climb.
Footnotes:
� http://www.supelec.fr/docs/cltl/clm/node357.html
� http://www.supelec.fr/docs/cltl/clm/node358.html
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> Joe Marshall <···@ccs.neu.edu> writes:
>
>> Since a single input can produce more than one token, this makes the
>> output an `offline' series.
>
> Why is this so? Or, why does it matter? If you did go ahead and add
> the queuing of tokens in per the original READ-TEXT-GENERATOR,
> couldn't you just avoid calling on SCAN-FN until the token queue is
> empty?
It has to do with how the series loop is constructed. When a series
collector function is found, the body is codewalked to find the
scanner. The scanner is either a primitive scanner or a user-defined
function wrapped around a primitive scanner. The intervening code
between the collector and the scanner represents a `slice' of the
computation. If the scanner and collector are in `lock step' then you
can easily assemble the intervening slices in a linear stack.
Macroexpanding a series form demonstrates this:
(collect 'list
(choose-if #'evenp
(map-fn 't (lambda (x) (* x x))
(until-if (lambda (y) (> y 10))
(scan-range)))))
=>
(LET* ((#:NUMBERS-1418 (COERCE (- 0 1) 'NUMBER))
#:ITEMS-1414
(#:LASTCONS-1408 (LIST NIL))
(#:LST-1409 #:LASTCONS-1408))
(DECLARE (TYPE NUMBER #:NUMBERS-1418)
(TYPE CONS #:LASTCONS-1408)
(TYPE LIST #:LST-1409))
(TAGBODY
#:LL-1422 (SETQ #:NUMBERS-1418 (+ #:NUMBERS-1418 (COERCE 1 'NUMBER)))
(IF ((LAMBDA (Y) (> Y 10)) #:NUMBERS-1418) (GO SERIES::END))
(SETQ #:ITEMS-1414 ((LAMBDA (X) (* X X)) #:NUMBERS-1418))
(IF (NOT (EVENP #:ITEMS-1414)) (GO #:LL-1422))
(SETQ #:LASTCONS-1408 (SETF (CDR #:LASTCONS-1408) (CONS #:ITEMS-1414 NIL)))
(GO #:LL-1422)
SERIES::END)
(CDR #:LST-1409))
If you look at the tagbody, you can see that the first form in the
loop are implementing the scan-range, the second implements the
until-if, the third is the map-fn, the fourth is the choose-if, and
the fifth is the collect.
> Does the difference here lead to the preclusion of optimization
> discussed in CLtL2 A.3.1?� Later we find this definition:�
>
> A series input port or series output port of a series function is
> on-line if and only if it is processed in lockstep with all the
> other on-line ports as follows: the initial element of each on-line
> input is read, then the initial element of each on-line output is
> written, then the second element of each on-line input is read, then
> the second element of each on-line output is written, and so
> on. Ports that are not on-line are off-line.
When all the ports are on-line, the resulting loop can be assembled as
above. If a port is off-line, however, things get more complicated.
In simple cases, it may be possible to use a nested loop or a state
machine to implement off-line generation or off-line collecting, but
if the consumer and the producer are too decoupled then there is no
way to determine what the intermediate control flow will do.
> So if we were to queue tokens, some calls would draw the next
> character from the stream, while some calls would merely dequeue a
> pending token. That breaks the "lockstep" constraint above. But why
> should that preclude such a series function from behaving in the
> expected optimal lazy fashion?
The series code has to perform data-flow analysis to determine how to
assemble the code fragments. If some calls draw the next token from
the stream, but some calls merely dequeue a pending token, then you
have two different sources for data-flow that are interleaved
depending on runtime conditions. That is a hard problem (even if the
answer obvious to us).
> Finally, A.3.3 finishes up with:
>
> Note that off-line ports virtually never arise when defining
> scanners or reducers.
>
> Isn't that exactly what we've proposed here -- a scanner that would be
> off-line because it injects a conditional branch inside the series
> expression?
Yes. I think `virtually never' is overstating it a bit.
> I find SERIES rather pleasant to use as is, but adding to it is big
> conceptual hill to climb.
Yes. For the things it does well it does *very* well, but the edge
conditions can be a pain in the butt.
You may be interested in some of the ways I was using series in a
recent project. One operation I was frequently doing was converting
between different character encodings `on the fly'. Converting from
and to UTF-8 would seem to be ideal for series code, but because a
UTF-8 uses anywhere from 1 to 4 bytes, it can be difficult to arrange
for lockstep processing. Here are some helper macros:
(defmacro scan-ahead (series bindings default &body body)
"Binds variables in BINDINGS to the series, the series displaced by one,
the series displaced by two, etc. In effect, allows a fixed amount of
lookahead for the body. The value of default is used to `pad out' the
tail of the series and will appear as the value of the last elements
near the end. Example:
(scan-ahead #z(foo bar baz quux) (a b c) 'xyzzy ....)
will bind A to the series #z(foo bar baz quux)
B to the series #z(bar baz quux xyzzy) and
C to the series #z(baz quux xyzzy xyzzy)"
(let ((n (length bindings)))
`(MULTIPLE-VALUE-BIND ,bindings
(CHUNK ,n 1 (CATENATE ,series (SUBSERIES (SERIES ,default) 1 ,n)))
,@body)))
(defmacro decode-series (series &key (padding nil) decoder (arity nil))
"DECODER must be a literal lambda expression with only REQUIRED args.
The decoder is invoked in turn on each overlapping n-tuple (where n
is the number of args) in the series. The decoder should return
two values: the decoded value and a `skip' count. The decoded value
is placed in the output followed by `skip' copies of PADDING.
To pass a value straight through, return (VALUES <first arg> 0)
Example: Decode the %nn parts of a URI.
(decode-series uri-characters
:padding #\null
:decoder (lambda (c0 c1 c2) ;; lookahead by two characters
(if (char/= c0 #\%)
(values c0 0) ;; if not a %, pass it through
;; Otherwise, decode the following characters,
;; and return that value. Use #\NULL for next two
;; outputs.
(values (code-char (+ (* (digit-char-p c1 16) 16) (digit-char-p c2 16)))
2))))
"
(destructure-function-lambda
arity decoder
(lambda (bindings docstring decls body)
(declare (ignore docstring decls))
(with-unique-names (output-code count)
`(SCAN-AHEAD ,series ,bindings ,padding
(MULTIPLE-VALUE-BIND (,output-code ,count)
(COLLECTING-FN '(VALUES T FIXNUM)
(LAMBDA () (VALUES ,padding 0))
(LAMBDA (,output-code ,count ,@bindings)
(IF (> ,count 0)
(VALUES ,padding (1- ,count))
(PROGN ,@body)))
,@bindings)
,output-code))))
(lambda () (error "Literal lambda needed for decode-series."))))
The code for DESTRUCTURE-FUNCTION-LAMBDA is given below.
DECODE-SERIES conceptually works as follows. Imagine the input series
layed out linearly:
(#\H #\e #\l #\l #\o #\% #\2 #\0 #\t #\h #\e #\r #\e)
DECODE-SERIES takes the decoder function and applies it to consecutive
tuples. In this example, first to #\H #\e #\l, then #\e #\l #\l, then
#\l #\l #\o, and so forth. On every invocation it generates an
output. Usually this is simply the first argument, but when it gets
to the tuple #\% #\2 #\0 it does the hex decoding and emits the
decoded character instead. The next iteration would normally be given
#\2 #\0 #\t, but we don't want that to cause a #\2 to be emitted. A
state variable indicates on each iteration whether or not to apply the
decoder function. If we do not apply the decoder, we simply emit a
padding character.
Conceptually, we are not in lock step, but in reality we are in lock
step because we generate an output on every iteration, it is just that
sometimes we generate it by applying the decoder while other times we
simply emit a padding element. The resulting output series would look
like this:
(#\H #\e #\l #\l #\o #\Space #\Null #\Null #\t #\h #\e #\r #\e)
It is a simple matter to use CHOOSE-IF to elide the nulls.
(collect 'string
(choose-if (lambda (char) (not (char= char #\Null)))
(decode-series (scan 'list '(#\H #\e #\l #\l #\o #\% #\2 #\0 #\t #\h #\e #\r #\e))
:padding #\Null
:decoder (lambda (c0 c1 c2)
(if (char/= c0 #\%)
(values c0 0)
(values (code-char (+ (* (digit-char-p c1 16) 16)
(digit-char-p c2 16)))
2))))))
=> "Hello there"
The actual code that the above generates is this:
(LET* ((#:OUT-1770 #\Null))
(LET (#:ELEMENTS-1759
(#:LISTPTR-1760 '(#\H #\e #\l #\l #\o #\% #\2 #\0 #\t #\h #\e #\r #\e))
(#:INDEX-1768 -1)
#:ITEMS-1756
(#:FLAG-1757 NIL)
(#:COUNT-1745 0)
#:CHUNK-1746
#:CHUNK-1747
#:CHUNK-1748
#:C-1777
(#:C-1776 0)
(#:SEQ-1731 NIL)
#:LST-1732)
(DECLARE (TYPE LIST #:LISTPTR-1760)
(TYPE (INTEGER -1) #:INDEX-1768)
(TYPE BOOLEAN #:FLAG-1757)
(TYPE FIXNUM #:COUNT-1745)
(TYPE FIXNUM #:C-1776)
(TYPE (NULL-OR (VECTOR CHARACTER)) #:SEQ-1731)
(TYPE LIST #:LST-1732))
(SETQ #:COUNT-1745 2)
(MULTIPLE-VALUE-SETQ (#:C-1777 #:C-1776) ((LAMBDA () (VALUES #\Null 0))))
(TAGBODY
#:LL-1779 (IF #:FLAG-1757 (GO #:B-1751))
(IF (ENDP #:LISTPTR-1760) (GO #:F-1752))
(SETQ #:ELEMENTS-1759 (CAR #:LISTPTR-1760))
(SETQ #:LISTPTR-1760 (CDR #:LISTPTR-1760))
(SETQ #:ITEMS-1756 #:ELEMENTS-1759)
(GO #:D-1749)
#:F-1752 (SETQ #:FLAG-1757 T)
#:B-1751 (INCF #:INDEX-1768)
(LOCALLY
(DECLARE (TYPE NONNEGATIVE-INTEGER #:INDEX-1768))
(IF (>= #:INDEX-1768 3) (GO END))
(IF (< #:INDEX-1768 1) (GO #:B-1751)))
(SETQ #:ITEMS-1756 #:OUT-1770)
#:D-1749 (SETQ #:CHUNK-1746 #:CHUNK-1747)
(SETQ #:CHUNK-1747 #:CHUNK-1748)
(SETQ #:CHUNK-1748 #:ITEMS-1756)
(CSF/UTILITY::COND ((PLUSP #:COUNT-1745) (DECF #:COUNT-1745) (GO #:LL-1779)) (T (SETQ #:COUNT-1745 0)))
(MULTIPLE-VALUE-SETQ (#:C-1777 #:C-1776)
((LAMBDA (#:OUTPUT-CODE1737 #:COUNT1738 C0 C1 C2)
(IF (> #:COUNT1738 0)
(VALUES #\Null (1- #:COUNT1738))
(PROGN (IF (CHAR/= C0 #\%) (VALUES C0 0) (VALUES (CODE-CHAR (+ (* (DIGIT-CHAR-P C1 16) 16) (DIGIT-CHAR-P C2 16))) 2)))))
#:C-1777
#:C-1776
#:CHUNK-1746
#:CHUNK-1747
#:CHUNK-1748))
(IF (NOT ((LAMBDA (CHAR) (NOT (CHAR= CHAR #\Null))) #:C-1777)) (GO #:LL-1779))
(SETQ #:LST-1732 (CONS #:C-1777 #:LST-1732))
(GO #:LL-1779)
END)
(LET ((NUM (LENGTH #:LST-1732)))
(DECLARE (TYPE NONNEGATIVE-INTEGER NUM))
(SETQ #:SEQ-1731 (MAKE-SEQUENCE 'STRING NUM))
(DO ((I (1- NUM) (1- I))) ((MINUSP I)) (SETF (AREF #:SEQ-1731 I) (POP #:LST-1732))))
#:SEQ-1731))
This is pretty horrrendous, but it is essentially a transducer for hex
decoding implemented as a state machine. To do this as a `one of'
would be a stunt (or exercise in self-flagellation), but the payoff is
that these things *compose*. In another section of code I have a
UTF-8->UCS-4 decoder implemeted using DECODE-SERIES. I also have a
UCS-4->UCS-2 transducer. International URIs may be UTF-8 encoded.
The http request is represented a series of (unsigned-byte 8). To
turn this series of codes into a lisp string (where the lisp uses
UCS-2 for string encoding) the code is trivial:
(defun utf-8->ucs-2 (code-vector)
"Convert a code-series to a lisp string."
(collect 'string
(#m code-char
(ucs-4->ucs-2
(utf-8->ucs-4
(scan 'simple-vector-8b code-vector))))))
This expands into 138 lines of impenetrable code that features a nasty
nested conditional that determines the state transition based on a
variable amount of lookahead. But the code is performing all of its
operations on (unsigned-byte 8) values, so when the code is compiled
it turns into an extremely efficient state machine.
Given that http has layers upon layers of twisty turning encodings,
all subtly different, (is that base64 content transfer encoding of a
utf-8 encoding of a query-xxx-encoded value or the octet encoding of a
uri-encoded query string that contains chinese characters?), the
ability to mix and match encoding and decoding layers *and* have the
resulting code be efficient is incredibly valuable.
--
~jrm
Here is some auxiliary code for the above macros:
(defun destructure-function-lambda (arity fl receiver if-not-function)
"If fl is of the form (FUNCTION (LAMBDA (bound-variable-list) docstring decls body))
invoke receiver on the bound-variable-list, docstring, decls, and the body.
If fl is of the form (FUNCTION name), invoke receiver on a
fake eta-expanded form.
If fl is of the form NAME, invoke receiver on a
fake eta-expanded form.
Otherwise invoke if-not-function."
(macrolet ((list-length-equals-one (list)
`(AND (CONSP ,list)
(NULL (CDR ,list))))
(list-length-greater-than-one (list)
`(AND (CONSP ,list)
(CONSP (CDR ,list))))
(is-function-form (form)
`(AND (CONSP ,form)
(EQ (CAR ,form) 'FUNCTION)
(LIST-LENGTH-EQUALS-ONE (CDR ,form))))
(function-form-body (function-form)
`(CADR ,function-form))
(is-lambda-form (form)
`(AND (CONSP ,form)
(EQ (CAR ,form) 'LAMBDA)
(LIST-LENGTH-GREATER-THAN-ONE (CDR ,form))))
(lambda-form-arguments (lambda-form)
`(CADR ,lambda-form))
(lambda-form-body (lambda-form)
`(CDDR ,lambda-form)))
(cl:cond ((is-function-form fl)
(let ((pl (function-form-body fl)))
;; Look for `(LAMBDA ...)
(cl:cond ((is-lambda-form pl)
(multiple-value-bind (docstring declarations body)
(split-declarations (lambda-form-body pl))
(funcall receiver (lambda-form-arguments pl) docstring declarations body)))
;; can't fake eta expand if arity is unknown
((null arity) (funcall if-not-function))
((symbolp pl) ; is something like (function foo)
;; perform eta expansion
(let ((arglist nil))
(dotimes (i arity)
(push (gensym "ARG-") arglist))
(funcall receiver arglist nil nil `((,pl ,@arglist)))))
(t (funcall if-not-function)))))
;; Look for naked '(lambda ...)
;; treat as if it were '(function (lambda ...))
((is-lambda-form fl)
(multiple-value-bind (docstring declarations body)
(split-declarations (lambda-form-body fl))
(funcall receiver (lambda-form-arguments fl) docstring declarations body)))
;; Can't fake an eta expansion if we don't know the arity.
((null arity) (funcall if-not-function))
;; Perform an ETA expansion
((symbolp fl)
(let ((arglist nil))
(dotimes (i arity)
(push (gensym "ARG-") arglist))
(funcall receiver arglist nil nil `((FUNCALL ,fl ,@arglist)))))
(t (funcall if-not-function)))))
(defun split-declarations (body)
"Given a LAMBDA body, return three values, the declarations, the doc string,
if present, and the body stripped of the declarations and doc string."
(labels ((scan (forms docstring declarations)
(cl:cond ((and (consp (car forms))
(eq (caar forms) 'declare))
(scan (cdr forms) docstring (cons (car forms) declarations)))
((or (null forms)
(not (stringp (car forms)))
docstring
(null (cdr forms)))
(values docstring (nreverse declarations) forms))
(t (scan (cdr forms) (car forms) declarations)))))
(scan body nil nil)))
Joe Marshall <·············@comcast.net> writes:
First of all, wow. Thank you for laying this all out.
> The series code has to perform data-flow analysis to determine how
> to assemble the code fragments. If some calls draw the next token
> from the stream, but some calls merely dequeue a pending token, then
> you have two different sources for data-flow that are interleaved
> depending on runtime conditions. That is a hard problem (even if
> the answer obvious to us).
Doesn't your (very elegant) hex decoding function encounter this same
hard problem? That is, sometimes it pulls from an underlying series,
and sometimes it doesn't, just returning the padding characters
instead. Why, despite the admonishment in the SERIES documentation
about the "lockstep" draw/yield alternation, does your function still
get the full optimization?
[...]
> Conceptually, we are not in lock step, but in reality we are in lock
> step because we generate an output on every iteration, it is just
> that sometimes we generate it by applying the decoder while other
> times we simply emit a padding element.
But when you don't apply the decoder, you're not drawing from the
source series expression. That seems to violate this paragraph's
definition of "lockstep":
A series input port or series output port of a series function is
on-line if and only if it is processed in lockstep with all the
other on-line ports as follows: the initial element of each on-line
input is read, then the initial element of each on-line output is
written, then the second element of each on-line input is read, then
the second element of each on-line output is written, and so
on. Ports that are not on-line are off-line.
Notice the clause, "then the second element of each on-line input is
read." It sounds like it precludes yielding another output without
first drawing another input.
I don't mean to argue with your code. I understand how it works. What
evades me is whether your code violates the series optimization
constraints. If it does violate them, I don't understand why it
remains optimized. If it doesn't violate them, then I don't understand
the rules.
--
Steven E. Harris :: ········@raytheon.com
Raytheon :: http://www.raytheon.com
"Steven E. Harris" <········@raytheon.com> writes:
> Doesn't your (very elegant) hex decoding function encounter this
> same hard [dataflow] problem? That is, sometimes it pulls from an
> underlying series, and sometimes it doesn't, just returning the
> padding characters instead. Why, despite the admonishment in the
> SERIES documentation about the "lockstep" draw/yield alternation,
> does your function still get the full optimization?
I cheated.
It took me a while to figure out how to cheat, but here's what's going
on. If we take this example series expression:
(collect 'list
(choose-if #'evenp
(map-fn 't (lambda (x) (* x x))
(until-if (lambda (x) (> x 10))
(scan-range)))))
which macroexpands to this:
(LET* ((#:NUMBERS-1434 (COERCE (- 0 1) 'NUMBER))
#:ITEMS-1430
(#:LASTCONS-1424 (LIST NIL))
(#:LST-1425 #:LASTCONS-1424))
(DECLARE (TYPE NUMBER #:NUMBERS-1434)
(TYPE CONS #:LASTCONS-1424)
(TYPE LIST #:LST-1425))
(TAGBODY
#:LL-1437 (SETQ #:NUMBERS-1434 (+ #:NUMBERS-1434 (COERCE 1 'NUMBER)))
(IF ((LAMBDA (X) (> X 10)) #:NUMBERS-1434) (GO END))
(SETQ #:ITEMS-1430 ((LAMBDA (X) (* X X)) #:NUMBERS-1434))
(IF (NOT (EVENP #:ITEMS-1430)) (GO #:LL-1437))
(SETQ #:LASTCONS-1424 (SETF (CDR #:LASTCONS-1424) (CONS #:ITEMS-1430 NIL)))
(GO #:LL-1437)
END)
(CDR #:LST-1425))
and replace the literal functions with meaningless names,
(collect 'list
(choose-if #'choosing-function
(map-fn 't #'function-to-map
(until-if #'end-test
(scan-range)))))
and macroexpand it:
(LET* ((#:NUMBERS-2311 (COERCE (- 0 1) 'NUMBER))
#:ITEMS-2307
(#:LASTCONS-2301 (LIST NIL))
(#:LST-2302 #:LASTCONS-2301))
(DECLARE (TYPE NUMBER #:NUMBERS-2311)
(TYPE CONS #:LASTCONS-2301)
(TYPE LIST #:LST-2302))
(TAGBODY
#:LL-2314 (SETQ #:NUMBERS-2311 (+ #:NUMBERS-2311 (COERCE 1 'NUMBER)))
(IF (END-TEST #:NUMBERS-2311) (GO END))
(SETQ #:ITEMS-2307 (FUNCTION-TO-MAP #:NUMBERS-2311))
(IF (NOT (CHOOSING-FUNCTION #:ITEMS-2307)) (GO #:LL-2314))
(SETQ #:LASTCONS-2301 (SETF (CDR #:LASTCONS-2301) (CONS #:ITEMS-2307 NIL)))
(GO #:LL-2314)
END)
(CDR #:LST-2302))
You can see what is going on behind the scenes. The series code takes
a series expression and computes the dataflow between the
series-oriented subforms in order to construct a `template' which it
will fill in with the non-series-oriented code. So the
(collect 'list
(choose-if ....
(map-fun 't ....
(until-if ...
(scan-range)))))
part of the code is what the series code is analyzing. It peeks into
the other expressions, but when it discovers that they are `normal'
code that doesn't operate on the series as a whole, it just plugs
those expressions into the template. The non-series code can pretty
much do what it wants provided that it doesn't refer to a series and
doesn't try to do any funny control flow (like RETURN-FROM).
So let's go back to the hex decode problem. First, here's the
scan-ahead macro:
(defmacro scan-ahead (series bindings default &body body)
(let ((n (length bindings)))
`(MULTIPLE-VALUE-BIND ,bindings
(CHUNK ,n 1 (CATENATE ,series (SUBSERIES (SERIES ,default) 1 ,n)))
,@body)))
The CHUNK form works by creating several temporary variables and
shifting the values through them. Expanding a CHUNK form will explain
this better than I can:
(macroexpand '(multiple-value-bind (a b c d e) (chunk 5 1 (scan-range :below 10)) (collect 'list a)))
(COMMON-LISP:LET* ((#:NUMBERS-2418 (COERCE (- 0 1) 'NUMBER))
(#:COUNT-2409 4)
(A 0)
(B 0)
(C 0)
(D 0)
(E 0)
(#:LASTCONS-2423 (LIST NIL))
(#:LST-2424 #:LASTCONS-2423))
(DECLARE (TYPE NUMBER #:NUMBERS-2418)
(TYPE FIXNUM #:COUNT-2409)
(TYPE NUMBER A)
(TYPE NUMBER B)
(TYPE NUMBER C)
(TYPE NUMBER D)
(TYPE NUMBER E)
(TYPE CONS #:LASTCONS-2423)
(TYPE LIST #:LST-2424))
(TAGBODY
#:LL-2425 (SETQ #:NUMBERS-2418 (+ #:NUMBERS-2418 (COERCE 1 'NUMBER)))
(IF (NOT (< #:NUMBERS-2418 10)) (GO SERIES::END))
(SETQ A B)
(SETQ B C)
(SETQ C D)
(SETQ D E)
(SETQ E #:NUMBERS-2418)
(COND ((PLUSP #:COUNT-2409) (DECF #:COUNT-2409) (GO #:LL-2425)) (T (SETQ #:COUNT-2409 0)))
(SETQ #:LASTCONS-2423 (SETF (CDR #:LASTCONS-2423) (CONS A NIL)))
(GO #:LL-2425)
SERIES::END)
(CDR #:LST-2424))
Note how the values are `chunked' by shifting them through the
intermediate variables a, b, c, d, e. The SCAN-AHEAD macro simply
adds appropriate padding so that the final element will be shifted all
the way up. Without the padding, the shifting will stop as soon as
the input stream is consumed. You can see that `scan-ahead' is going
to be lock step because it consumes an element of the input series on
each step.
The DECODE-SERIES macro is built on top of the series primitive
COLLECTING-FN. COLLECTING-FN builds a state machine. The state
machine works like this:
+------------------------+
| +--------------------+ |
| | +-----+ | |
| +->| | m-outputs| |
+--->| |-----------+-->
n-inputs | |-------------+>
------------>| |
------------>| |
------------>| |
+-----+
(collecting-fn '(values t fixnum) ;; output value types
(lambda () (values 'foo 22)) ;; initial output values
(lambda (o1 o2 i1 i2 i3 i4) ;; state transition function
(values (next-o1)
(next-o2)))
input-1
input-2
input-3
input-4)
You have to `prime' the state machine by supplying the initial output
values, but then it runs in lock step by applying the state transition
function to the prior outputs and one element each from the input
streams. You can see that this runs in lock step as well.
Ok, so now we're going to do the tricky part. We use the SCAN-AHEAD
macro provide the inputs to the state machine (so the original series
is advanced every step, and the values get shifted in a
`bucket-brigade' style through the inputs of the collecting-fn). The
primary function of the state machine is to produce new values for
output. It uses the state transition function to compute them. We're
going to use two state variables instead of one. The first is simply
our decoded output. It is fed back, but we just ignore it. The
second is a counter. The state transition function begins with a
conditional. If the counter is non-zero, the new state is computed by
ignoring the other inputs completely and emitting a padding character
and count that is one less. If the counter is zero, we apply the
decode function and use whatever it returns for the new count and
output. Either way, however, we consume one input and produce one
output in lock step. It is just that when the counter is non-zero we
don't bother running the decode function and just emit some padding.
> But when you don't apply the decoder, you're not drawing from the
> source series expression.
No, each time we *do* draw from the source series. But when we don't
run the decoder we just discard the input we draw. So we aren't in
violation of the lockstep requirement.
We could use this trick with the original poster's problem by always
emitting a `punctuation' character on each step. We'd define a `null'
punctuation character that we can emit when there really isn't
punctuation. When we collect the series at the end, we simply discard
the null punctuation. But this doesn't seem `natural' to me.
--
~jrm
··················@kazmier.com writes:
> For example, in the Python world (I'm not trolling here, I'm
> legitimately trying to learn the Lisp-way of doing things), one could
> use the original READ-TEXT function and simply replace the calls to
> SEE with the "yield" operator, which returns from the function at that
> point to the caller, but saves the execution state so that the next
> time the function is invoked, it resumes from where it left off. For
> example (the multiple assignment works like Lisp's PSETQ):
>
> def fib():
> a, b = 0, 1
> while 1:
> yield b
> a, b = b, a+b
>
> fib() => 1
> fib() => 1
> fib() => 2
> fib() => 3
> ...
I don't know how your original problem, but here is my take on the
Fibonacci sequence genorator:
;;; Fibonacci sequence generator as closure
(let ((a 0) (b 1))
(defun fib-gen ()
"Return next Fibonacci number in sequence with each call"
(let ((ret b) (n a))
(setf a b
b (+ ret n))
ret)))
(progn
(dotimes (i 10)
(format t "~A " (fib-gen)))
(terpri))·····@interloper:~/usr/src/ds-xxml
That Python code looks kinda clever.
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
David Steuber <·····@david-steuber.com> writes:
> I don't know how your original problem, but here is my take on the
> Fibonacci sequence genorator:
The Fibonacci sequence generator is a trivial example because it
always generates a single value. I know how to implement it in CL.
Thanks :-)
The more interesting problem is when you have a function that may
generate one *or* more values per pass. In that case, you need to
keep additional state to queue up values, and then when the generator
function is called again, check the queue for any values that may have
been generated in a previous pass and return those before you go off
and compute new values. This is how I coded my READ-TEXT-GENERATOR.
Unfortunately, this required that I change the way the original
READ-TEXT was implemented. This is exactly what I was trying to avoid
in the first place. I was simply looking for an equivalent to
Python's 'yield' operator which I think is very slick. The motivation
for this operator does a much better job of explaining why its useful:
http://www.python.org/peps/pep-0255.html
I believe the same can be accomplished in the lisp world using
continuations as Marco has pointed out; however, I'm not positive as I
can't verify if his example actually works because I don't think
continuations are part of CL.
Thanks,
Pete
Pete Kazmier <··················@kazmier.com> writes:
> David Steuber <·····@david-steuber.com> writes:
>
> > I don't know how your original problem, but here is my take on the
> > Fibonacci sequence genorator:
>
> The Fibonacci sequence generator is a trivial example because it
> always generates a single value. I know how to implement it in CL.
> Thanks :-)
Well I knew an answer to the easy problem ;-)
> I believe the same can be accomplished in the lisp world using
> continuations as Marco has pointed out; however, I'm not positive as I
> can't verify if his example actually works because I don't think
> continuations are part of CL.
cc is not part of CL, but I think it can be hacked in with macros. I
think either or both of On Lisp and PAIP have an example to do that.
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
David Steuber wrote:
> I don't know how your original problem, but here is my take on the
> Fibonacci sequence genorator:
>
> ;;; Fibonacci sequence generator as closure
>
> (let ((a 0) (b 1))
> (defun fib-gen ()
> "Return next Fibonacci number in sequence with each call"
> (let ((ret b) (n a))
> (setf a b
> b (+ ret n))
> ret)))
You don't need to store a in a temporary variable because you can use
psetf to perform assignments "in parallel". Since psetf returns the last
assigned value, you can rewrite your code as follows:
(let ((a 0) (b 1))
(defun fib-gen ()
(psetf b (+ a b)
a b)))
If you find that too tricky, you could make the code a bit clearer as
follows.
(let ((a 0) (b 1))
(defun fib-gen ()
(prog1 b
(psetf a b
b (+ a b)))))
Pascal
--
ECOOP 2004 Workshops - Oslo, Norway
*1st European Lisp and Scheme Workshop, June 13*
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
*2nd Post-Java Workshop, June 14*
http://prog.vub.ac.be/~wdmeuter/PostJava04/
Pascal Costanza <········@web.de> wrote:
> Since psetf returns the last assigned value,
It seems like PSETF returns NIL. Like this, maybe:
(let ((a 0) (b 1))
(defun fib-gen ()
(psetf b (+ a b)
a b)
a))
Peter Lewerin wrote:
> Pascal Costanza <········@web.de> wrote:
>
>>Since psetf returns the last assigned value,
>
> It seems like PSETF returns NIL. Like this, maybe:
>
> (let ((a 0) (b 1))
> (defun fib-gen ()
> (psetf b (+ a b)
> a b)
> a))
Yes, you're right. I haven't read the HyperSpec closely enough.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Pascal Costanza <········@web.de> writes:
> David Steuber wrote:
>
> > I don't know how your original problem, but here is my take on the
> > Fibonacci sequence genorator:
> > ;;; Fibonacci sequence generator as closure
> > (let ((a 0) (b 1))
> > (defun fib-gen ()
> > "Return next Fibonacci number in sequence with each call"
> > (let ((ret b) (n a))
> > (setf a b b (+ ret n))
> > ret)))
>
> You don't need to store a in a temporary variable because you can use
> psetf to perform assignments "in parallel". Since psetf returns the
> last assigned value, you can rewrite your code as follows:
>
> (let ((a 0) (b 1))
> (defun fib-gen ()
> (psetf b (+ a b)
> a b)))
Cool. I did not know about psetf.
You would think with only 978 symbols in CL, I would know them all by
now ;-)
--
An ideal world is left as an excercise to the reader.
--- Paul Graham, On Lisp 8.1
Pascal Costanza <········@web.de> writes:
> (let ((a 0) (b 1))
> (defun fib-gen ()
> (prog1 b
> (psetf a b
> b (+ a b)))))
That looks a little like SHIFTF. The return value is different,
but that can be compensated by changing the initial state:
(let ((a 1) (b 1))
(defun fib-gen ()
(shiftf a b (+ a b))))
Kalle Olavi Niemitalo wrote:
> Pascal Costanza <········@web.de> writes:
>
>
>>(let ((a 0) (b 1))
>> (defun fib-gen ()
>> (prog1 b
>> (psetf a b
>> b (+ a b)))))
>
> That looks a little like SHIFTF. The return value is different,
> but that can be compensated by changing the initial state:
>
> (let ((a 1) (b 1))
> (defun fib-gen ()
> (shiftf a b (+ a b))))
Cool.
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Kalle Olavi Niemitalo <···@iki.fi> wrote:
>
> That looks a little like SHIFTF. The return value is different,
> but that can be compensated by changing the initial state:
>
> (let ((a 1) (b 1))
> (defun fib-gen ()
> (shiftf a b (+ a b))))
Having just read through _The Seasoned Schemer_ in hopes of grokking the
style differences between Lisp and Scheme, I have two things to say
about this:
1. SHIFTF looks like a great idea.
2. Allowing non-top-level DEFUN -also- looks like a great idea. _TSS_
has to resort to prototypes to place two functions in the same LET:
(define bar)
(define foo
(let ((var value))
(lambda (foo-parm)
... body of foo ...)
(set! bar
(lambda (bar-parm)
... body of bar ...))))
... which seems terribly unclear to me.
(On the other hand, _TSS_ gave me a Zen moment regarding exceptions and
continuations. I now understand what the hell Mailman (written in
Python) is up to when it throws an exception from deep in the stack to
indicate that it has decided how to deliver an email message.)
--
Karl A. Krueger <········@example.edu>
Woods Hole Oceanographic Institution
Email address is spamtrapped. s/example/whoi/
"Outlook not so good." -- Magic 8-Ball Software Reviews
"Karl A. Krueger" <········@example.edu> writes:
> (On the other hand, _TSS_ gave me a Zen moment regarding exceptions and
> continuations. I now understand what the hell Mailman (written in
> Python) is up to when it throws an exception from deep in the stack to
> indicate that it has decided how to deliver an email message.)
Eh, that's what THROW and CATCH are for. They have nothing strictly to
do with exceptional situations. They are just a way to transfer control
non-locally to a dynamically determined stack frame. Exceptions are for
exceptional situations, not for control flow. Then again, python doesn't
have all the basic control structures, so you have to pretend that
normal behavior is exceptional.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
David Steuber <·····@david-steuber.com> writes:
> I don't know how your original problem, but here is my take on the
> Fibonacci sequence genorator:
The Fibonacci sequence generator is a trivial example because it
always generates a single value. I know how to implement it in CL.
Thanks :-)
The more interesting problem is when you have a function that may
generate one *or* more values per pass. In that case, you need to
keep additional state to queue up values, and then when the generator
function is called again, check the queue for any values that may have
been generated in a previous pass and return those before you go off
and compute new values. This is how I coded my READ-TEXT-GENERATOR.
Unfortunately, this required that I change the way the original
READ-TEXT was implemented. This is exactly what I was trying to avoid
in the first place. I was simply looking for an equivalent to
Python's 'yield' operator which I think is very slick. The motivation
for this operator does a much better job of explaining why its useful:
http://www.python.org/peps/pep-0255.html
I believe the same can be accomplished in the lisp world using
continuations as Marco has pointed out; however, I'm not positive as I
can't verify if his example actually works because I don't think
continuations are part of CL.
Thanks,
Pete
David Steuber <·····@david-steuber.com> wrote:
+---------------
| ;;; Fibonacci sequence generator as closure
| (let ((a 0) (b 1))
| (defun fib-gen ()
| "Return next Fibonacci number in sequence with each call"
| (let ((ret b) (n a))
| (setf a b
| b (+ ret n))
| ret)))
|
| (progn
| (dotimes (i 10)
| (format t "~A " (fib-gen)))
| (terpri))
+---------------
That works, but of course permits only one Fibonacci sequence generator
per Lisp image. Instead, I generally prefer to use anonymous closures[1]
for such generators, which are initialized to the beginning each time
a new closure is created, and whose steppings can be interleaved in any
desired order:
> (defun make-fib-gen (&optional (first 0) (second (1+ first)))
(let ((a first)
(b second))
(flet ((fib-gen ()
(prog1 a
(psetf a b
b (+ a b)))))
#'fib-gen)))
MAKE-FIB-GEN
> (defvar *fg1* (make-fib-gen))
*FG1*
> (defvar *fg2* (make-fib-gen))
*FG2*
> (defvar *fg3* (make-fib-gen 17 56))
*FG3*
> (loop for i below 10 collect (funcall *fg1*))
(0 1 1 2 3 5 8 13 21 34)
> (loop for i below 15 collect (funcall *fg2*))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377)
> (loop for i below 10 collect (funcall *fg1*))
(55 89 144 233 377 610 987 1597 2584 4181)
>
Now let's interleave all of them [including our forgotten friend *FG3*]:
> (loop for i below 5
collect (list (funcall *fg1*) (funcall *fg2*) (funcall *fg3*)))
((6765 610 17) (10946 987 56) (17711 1597 73) (28657 2584 129)
(46368 4181 202))
>
-Rob
[1] Although that the use of FLET as above (rather than LAMBDA per se)
causes many implementations to still store the "name" internally
in a way that is useful for debugging [note: this is in CMUCL,
and I compiled MAKE-FIB-GEN between creating *FG1* & *FG2*]:
> *fg1*
#<Interpreted Function FIB-GEN {485717D1}>
> *fg2*
#<Closure Over Function FIB-GEN {48530471}>
>
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
David Steuber <·····@david-steuber.com> wrote:
+---------------
| ;;; Fibonacci sequence generator as closure
| (let ((a 0) (b 1))
| (defun fib-gen ()
| "Return next Fibonacci number in sequence with each call"
| (let ((ret b) (n a))
| (setf a b
| b (+ ret n))
| ret)))
|
| (progn
| (dotimes (i 10)
| (format t "~A " (fib-gen)))
| (terpri))
+---------------
That works, but of course permits only one Fibonacci sequence generator
per Lisp image. Instead, I generally prefer to use anonymous[1] closures
for such generators, which are initialized to the beginning each time
a new closure is created, and whose steppings can be interleaved in any
desired order:
> (defun make-fib-gen (&optional (first 0) (second (1+ first)))
(let ((a first)
(b second))
(flet ((fib-gen ()
(prog1 a
(psetf a b
b (+ a b)))))
#'fib-gen)))
MAKE-FIB-GEN
> (defvar *fg1* (make-fib-gen))
*FG1*
> (defvar *fg2* (make-fib-gen))
*FG2*
> (defvar *fg3* (make-fib-gen 17 56))
*FG3*
> (loop for i below 10 collect (funcall *fg1*))
(0 1 1 2 3 5 8 13 21 34)
> (loop for i below 15 collect (funcall *fg2*))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377)
> (loop for i below 10 collect (funcall *fg1*))
(55 89 144 233 377 610 987 1597 2584 4181)
>
Now let's interleave all of them [including our forgotten friend *FG3*]:
> (loop for i below 5
collect (list (funcall *fg1*) (funcall *fg2*) (funcall *fg3*)))
((6765 610 17) (10946 987 56) (17711 1597 73) (28657 2584 129)
(46368 4181 202))
>
-Rob
[1] Although note that the use of FLET as above (rather than LAMBDA per se)
causes many implementations to store the name internally in a way
that is useful for debugging [note: this is in CMUCL, and I compiled
MAKE-FIB-GEN between creating *FG1* & *FG2*]:
> *fg1*
#<Interpreted Function FIB-GEN {485717D1}>
> *fg2*
#<Closure Over Function FIB-GEN {48530471}>
>
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Marco Baringer <··@bese.it> writes:
> There's a reason they call it the "programmable programming
> language".
>
> (defmacro yield (value)
> (with-unique-names (k)
> `(let/cc ,k
> (list ,value (lambda () (funcall ,k nil))))))
This is exactly what I was hoping to find. Is this CL? I was under
the impression that CL did not have direct support for continuations.
Although, I have seen lots of comments that they are possible to
simulate with macros and closures (and references to Graham's OnLisp
book which is in my queue after Norvig's PAIP book).
Thanks,
Pete
In article <··············@coco.kazmier.com>,
Pete Kazmier <··················@kazmier.com> wrote:
> Marco Baringer <··@bese.it> writes:
> > There's a reason they call it the "programmable programming
> > language".
>
> This is exactly what I was hoping to find. Is this CL? I was under
> the impression that CL did not have direct support for continuations.
> Although, I have seen lots of comments that they are possible to
> simulate with macros and closures (and references to Graham's OnLisp
> book which is in my queue after Norvig's PAIP book).
From the package in the prompt, I assume this is from arnesi, part of
the bese project.
http://www.cliki.net/arnesi
http://www.common-lisp.net/project/bese/
``arnesi is a Common Lisp utility suite. It contains various "bits 'n
pieces" of code which were usefull while developing other code.
including:
* cps transformer - an ad-hoc, bug ridden implementation of half of
call/cc.''
Unfortunatly it looks like the tarballs are down, probably due to the
cl.net problems recently. The arch respository looks active though.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
Pete Kazmier <··················@kazmier.com> writes:
> Marco Baringer <··@bese.it> writes:
>
>> There's a reason they call it the "programmable programming
>> language".
>>
>> (defmacro yield (value)
>> (with-unique-names (k)
>> `(let/cc ,k
>> (list ,value (lambda () (funcall ,k nil))))))
>
> This is exactly what I was hoping to find. Is this CL? I was under
> the impression that CL did not have direct support for continuations.
it's as much CL as SCREAMER or ITERATE or CLOS or CELLS is. the code
uses a CPS transformer which is part of this:
http://common-lisp.net/project/bese/arnesi.html
i must however warn you that this implementation of call/cc is for
from perfect, not all special operators are supported and some
iterative code sequences may overflow the stack. but hey, it's fun to
play with.
due to cl.net difficulties the normal distribution point is
unavailable, however i have put up a copy of the latest source at:
http://common-lisp.net/~mbaringer/arnesi--dev--1.1--patch-49.tar.bz2
this url will live only until the regular ftp stuff comes back.
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
··················@kazmier.com wrote:
> [...] Thus, I modified READ-TEXT to accept a functional argument so I
> could pass my own function to be called when a valid token is found
> instead of SEE.
> After I completed this, I realized it would be more elegant if I had
> used a generator instead of passing a callback function to READ-TEXT.
> [...]
Actually, your first approach is a common technique in Common Lisp, and
is not considered inelegant. See, for example, the definition of cl:sort.
> As a result, I create READ-TEXT-GENERATOR which returns a closure that
> returns the next token each time its invoked. [...]
> Is there a better idiom for this type of scenario?
The only thing I'd change in your code is the use of cl:pop and
cl:append to implement a queue. Investigate the various techniques used
for "collecting" a series of values in CL. See
http://www.cliki.net/COLLECTING. Others have proposed using the SERIES
package, but that may be overkill for this problem.
-Len