I wanted to write a function that reads whitespace-separated numbers
from a string, i.e. given a string like "1 2 3 4" I wanted my function
to return the list (1 2 3 4).
Two different solutions came to mind:
(defun foo1 (string)
(loop for start = 0 then pos
for (object pos) = (multiple-value-list
(read-from-string string nil nil :start start))
while object
collect object))
(defun foo2 (string)
(let ((start 0) object result)
(loop
(multiple-value-setq (object start)
(read-from-string string nil nil :start start))
(unless object
(return-from foo2 (nreverse result)))
(push object result))))
I generally prefer LOOP but I have to admit that it isn't very
well-suited for multiple-valued functions in the "variable
accumulation and stepping clauses." My clutch was to use
MULTIPLE-VALUE-LIST and LOOP's destructuring capabilities but this of
course needlessly conses up a list for each iteration.
The alternative, FOO2, doesn't do that but I don't like it very much.
Am I missing another idiom here or do most people agree that FOO2 is
the canonical way to do it?
And, as a side note: I could imagine a sufficiently smart compiler[TM]
which recognizes that the consing in FOO1 isn't necessary and directly
binds OBJECT and POS to the return values of READ-FROM-STRING. Does
one of the existing Common Lisps already do that?
Thanks,
Edi.
Edi Weitz wrote:
> And, as a side note: I could imagine a sufficiently smart compiler[TM]
> which recognizes that the consing in FOO1 isn't necessary and directly
> binds OBJECT and POS to the return values of READ-FROM-STRING. Does
> one of the existing Common Lisps already do that?
I doubt you need a smart compiler -- a smart(er) LOOP macro should be enough.
Paul
On Sun, 14 Dec 2003 19:05:16 -0600, "Paul F. Dietz" <·····@dls.net> wrote:
> Edi Weitz wrote:
>
>> And, as a side note: I could imagine a sufficiently smart
>> compiler[TM] which recognizes that the consing in FOO1 isn't
>> necessary and directly binds OBJECT and POS to the return values of
>> READ-FROM-STRING. Does one of the existing Common Lisps already do
>> that?
>
> I doubt you need a smart compiler -- a smart(er) LOOP macro should
> be enough.
OK, before I posted I looked at the macro-expansions of the LOOP and
from what I saw you're definitely right. With a 'smarter' LOOP macro
the problem would be reduced to do something clever with
(destructuring-bind (x y)
(multiple-value-list (bar))
...)
Given that DESTRUCTURING-BIND and MULTIPLE-VALUE-LIST both are macros
I guess this could be translated to something like
(multiple-value-bind (x y)
(bar)
...)
However, this'll require that DESTRUCTURING-BIND "looks into" the
expression it is given and determines whether the structure it
receives isn't used elsewhere. From the Lisps I tried only AllegroCL
seems to be halfway there. With simple forms[1]:
CL-USER(1): (mac (destructuring-bind (x y) (list 1 2) (foo)))
(LET* () (LET* ((X '1) (Y '2)) (FOO)))
But with M-V-L:
CL-USER(2): (mac (destructuring-bind (x y) (multiple-value-list (bar)) (foo)))
(LET* ()
(LET* ((#:G31 (MULTIPLE-VALUE-LIST (BAR)))
(X (EXCL::CAR-FUSSY #:G31 'X))
(Y (EXCL::CAR-FUSSY (CDR #:G31) 'Y))
(#:G32 (EXCL::LAMBDASCAN-MAXARGS 0 (CDR (CDR #:G31)) '(X Y))))
(DECLARE (IGNORE-IF-UNUSED #:G32))
(FOO)))
No wonder, because
CL-USER(3): (mac (multiple-value-list (bar)))
(MULTIPLE-VALUE-CALL #'LIST (BAR))
which, as far as I understand, is necessary because M-V-C is a special
operator that you have to use unless you have special knowledge about
BAR. So, given a statement like
(declaim (ftype (function () (values fixnum fixnum)) bar))
it should in theory be possible that (M-V-L (BAR)) expands into
(multiple-value-bind (#:foo1 #:foo2)
(bar)
(list #:foo1 #:foo2))
and thus (D-B (X Y) (M-V-L (BAR)) ...) into
(multiple-value-bind (x y)
(bar)
...)
using a code walker.
Am I on the right track?
Thanks,
Edi.
[1] (defmacro mac (expr)
`(pprint (macroexpand-1 ',expr)))
Edi Weitz wrote:
> OK, before I posted I looked at the macro-expansions of the LOOP and
> from what I saw you're definitely right. With a 'smarter' LOOP macro
> the problem would be reduced to do something clever with
>
> (destructuring-bind (x y)
> (multiple-value-list (bar))
> ...)
>
> Given that DESTRUCTURING-BIND and MULTIPLE-VALUE-LIST both are macros
> I guess this could be translated to something like
>
> (multiple-value-bind (x y)
> (bar)
> ...)
>
> However, this'll require that DESTRUCTURING-BIND "looks into" the
> expression it is given and determines whether the structure it
> receives isn't used elsewhere.
Just have LOOP look into the form-to-be-destructured. If it's
a multiple-value-list, generate a m-v-b instead of d-b + m-v-l.
(In safe code, you might still want to generate the first form,
which would mean the macro would need to have access to the SAFETY
setting, but many lisps provide that as an accessor to the
macro's environment parameter.)
(LOOP could also macroexpand the form-to-be-destructured before
making its decision by calling macroexpand explicitly.)
Paul
"Paul F. Dietz" <·····@dls.net> writes:
> Just have LOOP look into the form-to-be-destructured. If it's
> a multiple-value-list, generate a m-v-b instead of d-b + m-v-l.
>
> (In safe code, you might still want to generate the first form,
> which would mean the macro would need to have access to the SAFETY
> setting, but many lisps provide that as an accessor to the
> macro's environment parameter.)
>
> (LOOP could also macroexpand the form-to-be-destructured before
> making its decision by calling macroexpand explicitly.)
This has been on my personal to-do list for a while, because I find
myself using the
(loop for (x y z) = (multiple-value-list (foo...))
...)
idiom often enough. The one or two times I've had speed/consing
sensitive code using this idiom, I rewrote the code directly into a
tagbody, because that also allowed me to optimize the iteration better
than loop could.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
Edi Weitz wrote:
> I wanted to write a function that reads whitespace-separated numbers
> from a string, i.e. given a string like "1 2 3 4" I wanted my function
> to return the list (1 2 3 4).
What about:
(let ((s "1 2 3 4"))
(read-from-string
(format nil "(~A)" s)))
?!?
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza <········@web.de> wrote:
> What about:
>
> (let ((s "1 2 3 4"))
> (read-from-string
> (format nil "(~A)" s)))
>
> ?!?
That's neat but it certainly conses a lot more (for long strings) than
my FOO1 function.
Edi.
Edi Weitz <···@agharta.de> writes:
> On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza <········@web.de> wrote:
>
> > What about:
> >
> > (let ((s "1 2 3 4"))
> > (read-from-string
> > (format nil "(~A)" s)))
> >
> > ?!?
>
> That's neat but it certainly conses a lot more (for long strings) than
> my FOO1 function.
It does not matter!
You came with two implementations and complained about what's not but
you did not say: "Look, I've run my program against typical data set
and I've measured that 58% of the time is spent in my FOO function. I
suspect I'm consing too much."
So use Pascal's solution which is cleaner, and if one day, in a long
long time in the future, in a galaxy far, far away, you find that your
program spends 78% of its time in (read-from-string (format nil "(~A)"
s)), then come back to us and we'll find a solution.
[ And if you're so afraid of consing, you can always add ONE character
to Pascal's sexp and get an array instead of a list! ].
--
__Pascal_Bourguignon__ . * * . * .* .
http://www.informatimago.com/ . * . .*
There is no worse tyranny than to force * . . /\ () . *
a man to pay for what he does not . . / .\ . * .
want merely because you think it .*. / * \ . .
would be good for him. -- Robert Heinlein . /* o \ .
http://www.theadvocates.org/ * '''||''' .
SCO Spam-magnet: ··········@sco.com ******************
On 15 Dec 2003 08:19:10 +0100, Pascal Bourguignon <····@thalassa.informatimago.com> wrote:
> It does not matter!
Says who?
> You came with two implementations and complained about what's not
I didn't complain.
> and if one day, in a long long time in the future, in a galaxy far,
> far away, you find that your program spends 78% of its time in
> (read-from-string (format nil "(~A)" s)), then come back to us and
> we'll find a solution.
Thanks. I hope the day where I have to depend on your solutions will
never come.
> [ And if you're so afraid of consing, you can always add ONE
> character to Pascal's sexp and get an array instead of a list! ].
So you have access to some �ber-Lisp which doesn't have to allocate
memory for arrays? Could you provide a URL? FWIW, if I replace "(~A)"
with "#(~A)" on my machine the function conses more, not less.
Edi.
From the CLHS glossary:
"cons [...] 3. v. Idiom. to create any object, or to allocate
storage."
Pascal Bourguignon <····@thalassa.informatimago.com> wrote in message news:<··············@thalassa.informatimago.com>...
> Edi Weitz <···@agharta.de> writes:
>
> > On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza <········@web.de> wrote:
> >
> > > What about:
> > >
> > > (let ((s "1 2 3 4"))
> > > (read-from-string
> > > (format nil "(~A)" s)))
> > >
> > > ?!?
> >
> > That's neat but it certainly conses a lot more (for long strings) than
> > my FOO1 function.
>
> It does not matter!
>
> [ And if you're so afraid of consing, you can always add ONE character
> to Pascal's sexp and get an array instead of a list! ].
You are allocating a bunch of things here in addition to the result
list. Firstly, (read-from-string ...) and (format nil) probably
require that string streams be constructed on the fly. The use of
string streams can be optimized away by the implementation only if it
can be proven that no program-defined functions will be called during
the formatting or reading that must be passed a stream parameter.
Secondly, you can't make "(X)" out of "X" without allocating a new
string; that is ``consing'' also.
From: Kalle Olavi Niemitalo
Subject: extent of string streams (was: Style question: LOOP and multiple values)
Date:
Message-ID: <87fzfizffw.fsf_-_@Astalo.kon.iki.fi>
···@ashi.footprints.net (Kaz Kylheku) writes:
> Firstly, (read-from-string ...) and (format nil) probably
> require that string streams be constructed on the fly.
CMUCL maintains a list of string input streams that it reuses in
different READ-FROM-STRING calls.
;; Define #? as a reader macro that returns the stream itself.
(defun grab-stream (stream sub-character parameter)
(declare (ignore sub-character parameter))
stream)
;; ==> GRAB-STREAM
(set-dispatch-macro-character #\# #\? #'grab-stream)
;; ==> #<Interpreted Function GRAB-STREAM {48029471}>
;; Save the stream used by READ-FROM-STRING.
(defparameter *stream* (read-from-string "#?hello there"))
;; ==> *STREAM*
;; CMUCL allows reading from the stream, even though
;; READ-FROM-STRING has already returned.
(read *stream*)
;; ==> HELLO
;; This call happens to use the same stream as the previous one.
(read-from-string "beam me up")
;; ==> BEAM
;; The stream is now connected to the new string.
(read *stream*)
;; ==> ME
WITH-INPUT-FROM-STRING is permitted to allocate the stream with
dynamic extent; as far as I can tell, READ-FROM-STRING is not.
Strangely, CMUCL does just the opposite.
Hi Edi Weitz,
> On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza <········@web.de> wrote:
>
>> What about:
>>
>> (let ((s "1 2 3 4"))
>> (read-from-string
>> (format nil "(~A)" s)))
>>
>> ?!?
>
> That's neat but it certainly conses a lot more (for long strings) than
> my FOO1 function.
Try this for long strings. I found it conses a lot less than FOO1 (CMUCL,
both functions compiled):
(defun foo3 (s)
(read-from-string (concatenate 'string '(#\() s '(#\)))))
Regards,
Adam
On Mon, 15 Dec 2003 16:10:37 +1300, Adam Warner <······@consulting.net.nz> wrote:
>> On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza
>> <········@web.de> wrote:
>>
>>> What about:
>>>
>>> (let ((s "1 2 3 4"))
>>> (read-from-string
>>> (format nil "(~A)" s)))
>>>
>>> ?!?
>>
>> That's neat but it certainly conses a lot more (for long strings)
>> than my FOO1 function.
I was wrong here, of course. The longer the strings the better
Pascal's approach is compared to my FOO1 w.r.t. consing.
> Try this for long strings. I found it conses a lot less than FOO1
> (CMUCL, both functions compiled):
>
> (defun foo3 (s)
> (read-from-string (concatenate 'string '(#\() s '(#\)))))
Yes, also better than using FORMAT.
Edi.
Edi Weitz wrote:
> On Mon, 15 Dec 2003 16:10:37 +1300, Adam Warner <······@consulting.net.nz> wrote:
>
>
>>>On Mon, 15 Dec 2003 01:43:06 +0100, Pascal Costanza
>>><········@web.de> wrote:
>>>
>>>
>>>>What about:
>>>>
>>>>(let ((s "1 2 3 4"))
>>>> (read-from-string
>>>> (format nil "(~A)" s)))
>>>>
>>>>?!?
>>>
>>>That's neat but it certainly conses a lot more (for long strings)
>>>than my FOO1 function.
>
>
> I was wrong here, of course. The longer the strings the better
> Pascal's approach is compared to my FOO1 w.r.t. consing.
>
>
>>Try this for long strings. I found it conses a lot less than FOO1
>>(CMUCL, both functions compiled):
>>
>>(defun foo3 (s)
>> (read-from-string (concatenate 'string '(#\() s '(#\)))))
Maybe a combination of READ-FROM-STRING and WITH-OUTPUT-TO-STRING also
works well. Maybe also the series macros provide something here.
Just brainstorming.
Pascal
--
Pascal Costanza University of Bonn
···············@web.de Institute of Computer Science III
http://www.pascalcostanza.de R�merstr. 164, D-53117 Bonn (Germany)
Edi Weitz wrote:
> I wanted to write a function that reads whitespace-separated numbers
> from a string, i.e. given a string like "1 2 3 4" I wanted my function
> to return the list (1 2 3 4).
>
> Two different solutions came to mind:
>
> (defun foo1 (string)
> (loop for start = 0 then pos
> for (object pos) = (multiple-value-list
> (read-from-string string nil nil :start start))
> while object
> collect object))
>
> (defun foo2 (string)
> (let ((start 0) object result)
> (loop
> (multiple-value-setq (object start)
> (read-from-string string nil nil :start start))
> (unless object
> (return-from foo2 (nreverse result)))
> (push object result))))
>
How about
(defun foo3 (string)
(with-input-from-string (stream string)
(loop for obj = (read stream nil nil)
while obj collect obj)))
Wade
On Mon, 15 Dec 2003 02:10:01 GMT, Wade Humeniuk <········@delete-this-antispam-device.telus.net> wrote:
> How about
>
> (defun foo3 (string)
> (with-input-from-string (stream string)
> (loop for obj = (read stream nil nil)
> while obj collect obj)))
D'oh! Yes, that was the one I missed.
Edi Weitz <···@agharta.de> wrote:
> I generally prefer LOOP but I have to admit that it isn't very
> well-suited for multiple-valued functions in the "variable
> accumulation and stepping clauses."
Yes. This is one of the situations where Jonathan Amsterdam's ITERATE
macro really shines. It's a pity that no one seems to use it (except
Jeffrey Siskind's Screamer package). It has more features than LOOP,
allows you to put clauses inside arbitrary Lisp code, and has a syntax
that's nicely integrated with the rest of Lisp.
Here's how your FOO2 version would look with ITERATE:
(defun foo-iter (string)
(iterate
(for start initially 0 then pos)
(for (values object pos) = (read-from-string string nil nil :start start))
(while object)
(collect object)))
On my implementation, this runs as fast as FOO2, and conses as much.
> Am I missing another idiom here or do most people agree that FOO2 is
> the canonical way to do it?
If I couldn't use ITERATE and really cared about the consing, I'd use
your FOO2 as well (except that Wade Humeniuk's solution is obviously
better in this specific case).
Arthur Lemmens
On Mon, 15 Dec 2003 21:03:40 +0100, Arthur Lemmens <········@xs4all.nl> wrote:
> This is one of the situations where Jonathan Amsterdam's ITERATE
> macro really shines.
Thanks for the pointer. I just downloaded it and begun to play with
it. (If someone else wants to do it: Get the version which is part of
Screamer[1] - it incorporates a couple of patches so iterate will run
out-of-the-box with "modern" CLs.)
I like it. It looks like I always thought LOOP should look like... :)
(And I /like/ LOOP. It's just that I think iterate is better. If it
were only for the fact that Emacs can indent it properly... :)
> It's a pity that no one seems to use it (except Jeffrey Siskind's
> Screamer package).
Yes.
Thanks,
Edi.
On Tue, 16 Dec 2003 01:05:17 +0100, Edi Weitz <···@agharta.de> wrote:
> On Mon, 15 Dec 2003 21:03:40 +0100, Arthur Lemmens <········@xs4all.nl> wrote:
>
>> This is one of the situations where Jonathan Amsterdam's ITERATE
>> macro really shines.
>
> Thanks for the pointer. I just downloaded it and begun to play with
> it. (If someone else wants to do it: Get the version which is part
> of Screamer[1] - it incorporates a couple of patches so iterate will
> run out-of-the-box with "modern" CLs.)
Forgot the link:
[1] <http://www.cis.upenn.edu/~screamer-tools/home.html>
Arthur Lemmens wrote:
> Edi Weitz <···@agharta.de> wrote:
>
>> I generally prefer LOOP but I have to admit that it isn't very
>> well-suited for multiple-valued functions in the "variable
>> accumulation and stepping clauses."
>
>
> Yes. This is one of the situations where Jonathan Amsterdam's ITERATE
> macro really shines.
Plug for my 'repeat' macro:
(defun foo (string)
(repeat :for ((start = 0 :then pos) pos)
:within
(multiple-value-bind (object nextpos)
(read-from-string string nil nil
:start start)
(:continue
:while object
:collect object
(setq pos nextpos)))))
I haven't looked at Amsterdam's 'iterate', but the way I allow the loop
to contain arbitrary code with loop constructs in it is the
:within-:continue notation illustrated by this example.
'repeat' is part of the YTools package, which is part of CLOCC:
http://clocc.sourceforge.net/. There is a large YTools manual in the
browsable CVS repository at CLOCC.
-- Drew McDermott