First off, congrats Kent for a tour de force over at slashdot. second:
> KMP: The example you cite is quite simplistic.....snip...A loop like this:
>
> (loop for x from 0
> for y in some-list
> when (good-result? y)
> collect (list x y))
>
> is easy to write and maintain, and much easier to explain than the equivalent, but more Lispy:
>
> (do ((x 0 (+ x 1))
> (y-list some-list (cdr y-list))
> (result '()))
> ((null y-list) ;; [fixed]
> (nreverse result))
> (let ((y (first y-list)))
> (when (good-result? y)
> (push (list x y) result))))
Ugh. Howse about:
(let ((goody-pos -1)
goodies)
(dolist (it some-list (nreverse goodies))
(incf goody-pos)
(when (good-result? it)
(push (list goody-pos it) goodies))))
perhaps i will be swayed someday by the charms of loop, but i gotta tell
you, i just don't get it. is loop for people who can't read lisp? can't
be, lisp is easier to read than loop. stumped.
kenny
clinisys
Kenny Tilton wrote:
> First off, congrats Kent for a tour de force over at slashdot. second:
>
>
>> KMP: The example you cite is quite simplistic.....snip...A loop like
>> this:
>>
>> (loop for x from 0
>> for y in some-list
>> when (good-result? y)
>> collect (list x y))
>>
>> is easy to write and maintain, and much easier to explain than the
>> equivalent, but more Lispy:
>>
>> (do ((x 0 (+ x 1))
>> (y-list some-list (cdr y-list))
>> (result '()))
>> ((null y-list) ;; [fixed]
>> (nreverse result))
>> (let ((y (first y-list)))
>> (when (good-result? y)
>> (push (list x y) result))))
>
> Ugh. Howse about:
>
> (let ((goody-pos -1)
> goodies)
> (dolist (it some-list (nreverse goodies))
> (incf goody-pos)
> (when (good-result? it)
> (push (list goody-pos it) goodies))))
>
> perhaps i will be swayed someday by the charms of loop, but i gotta tell
> you, i just don't get it. is loop for people who can't read lisp? can't
> be, lisp is easier to read than loop. stumped.
If we are over it again, this one should not be missing:
(iter (for x from 0)
(for y in some-list)
(when (good-result? y)
(collect x y)))
ciao,
Jochen
--
http://www.dataheaven.de
Is it just me? This bugs me (as does loop version):
> (iter (for x from 0)
> (for y in some-list)
> (when (good-result? y)
> (collect x y)))
That screams "nested loop" to me. Maybe the problem is that the keywords
are reminiscent of languages which would never handle two FORs in
parallel.
The problem to me with stuff like this is that they went after a natlang
quality and to the degree they succeeded I have to mentally compile the
code into straight CL to work out what is really going on.
And bottom line, what the hell problem are we solving? I doubt there is
any real-world loop code not expressible in as readable or better
non-loop CL.
kenny
clinisys
Kenny Tilton wrote:
> Is it just me? This bugs me (as does loop version):
>
>> (iter (for x from 0)
>> (for y in some-list)
>> (when (good-result? y)
>> (collect x y)))
>
> That screams "nested loop" to me. Maybe the problem is that the keywords
> are reminiscent of languages which would never handle two FORs in
> parallel.
IMHO it actually _is_ the groundbreaking feature of LOOP or ITERATE to offer
parallel stepping forms (like DO) in a more readable (probably
subjective...) manner. I'm often impressed how easy it is to translate
pseudo-code or formal math statements into loop code. Another nice thing is
that you can encapsulate some optimizations that would definitely look more
unreadable if written out directly (like collecting to the tail of a list
instead of the PUSH/NREVERSE approach you have chosen).
> The problem to me with stuff like this is that they went after a natlang
> quality and to the degree they succeeded I have to mentally compile the
> code into straight CL to work out what is really going on.
I don't see it as trying to be full-scale natural language but more the
restricted subset of common formal mathematic speaking, where you
intentfully restrict and unify your vocabulary. Fact is that I don't
have only "no problem" understanding LOOP but also tend to find it more
readable for the kind of topic (iteration) it handles.
> And bottom line, what the hell problem are we solving? I doubt there is
> any real-world loop code not expressible in as readable or better
> non-loop CL.
I doubt that there is any real-world CL code not expressible in assembler.
And probably an experienced assembler-code that does not know anything of
CL might find assembly more readable than CL...
Please try to understand that "readability" is a subjective topic. It
depends almost only on what someone is *capable* of reading and is
therefore a trait that has to be counted "per person".
ciao,
Jochen
--
http://www.dataheaven.de
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<·················@nyc.rr.com>...
> perhaps i will be swayed someday by the charms of loop, but i gotta tell
> you, i just don't get it. is loop for people who can't read lisp? can't
> be, lisp is easier to read than loop. stumped.
I think the point is that Lisp is a multiparadigm language and there
is more than one way to do it[1]. I think I can read Lisp OK, and I
use LOOP on occasion. I've been through phases of religiously
avoiding it, and similar phases with various other control/iteration
constructs, up to and including writing my own. But I think I've kind
of grown out of that now and I find myself using a wide-range of
constructs - including still occasionally writing my own - in a way
which I hope is consistent, but probably has more to do with elegant
variation or just plain inconsistency depending on how cynical you are
about my programming style.
One thing that I use LOOP for is doing what MAPCAR does in some cases.
I find (and I don't pretend to speak for anyone but me) that
something like this:
(mapcar #'(lambda (x)
... 50 lines ...)
list)
is kind of hard to read because it separates the thing being iterated
over from the variable of iteration, and it puts the thing being
iterated over in a fairly unusual place. This, I find, is easier:
(dolist (i list)
... 50 lines ...)
but it crucially does something quite different. The foillowing is
just mysterious (and obsessives will worry about performance):
(let ((r '()))
(dolist (i list (nreverse r))
... (push i r) ...))
I used to do this:
(collecting
(dolist (i list)
... (collect ...) ...))
(see my other post in this thread for COLLECTING).
What I often do now is
(loop for i in list
...
collect ...
...)
which works.
--tim
[1] and most of the ways are better than Perl, too.
[some interesting personal style notes of Tim Bradshaw snipped]
I try first to use facilities like MAPCAR, MAPCAN, REDUCE ...
and if those do not fit so well I try DOLIST or DOTIMES.
If that does not suffice I use LOOP (which seems to happen rather often...)
I prefer for example to write
(dotimes (x width)
(dotimes (y height)
(do-something-on-element array x y)))
instead of
(loop for x from 0 to width
do (loop for y from 0 to height
do (do-something-on-element array x y)))
I never use DO or DO* because I personally find them more difficult
to read than the equivalent LOOP constructs.
I somewhat like Jonathan Amsterdams ITERATE macro, but I have not used
it in any production-code since it's gains over LOOP was simply enough for
me to introduce another non-standard dependency into my sources.
ciao,
Jochen
--
http://www.dataheaven.de
In article <·················@nyc.rr.com>, Kenny Tilton
<·······@nyc.rr.com> wrote:
> First off, congrats Kent for a tour de force over at slashdot. second:
>
>
> > KMP: The example you cite is quite simplistic.....snip...A loop like
> > this:
> >
> > (loop for x from 0
> > for y in some-list
> > when (good-result? y)
> > collect (list x y))
> >
> > is easy to write and maintain, and much easier to explain than the
> > equivalent, but more Lispy:
> >
> > (do ((x 0 (+ x 1))
> > (y-list some-list (cdr y-list))
> > (result '()))
> > ((null y-list) ;; [fixed]
> > (nreverse result))
> > (let ((y (first y-list)))
> > (when (good-result? y)
> > (push (list x y) result))))
>
> Ugh. Howse about:
>
> (let ((goody-pos -1)
> goodies)
> (dolist (it some-list (nreverse goodies))
> (incf goody-pos)
> (when (good-result? it)
> (push (list goody-pos it) goodies))))
>
> perhaps i will be swayed someday by the charms of loop, but i gotta tell
> you, i just don't get it. is loop for people who can't read lisp? can't
> be, lisp is easier to read than loop. stumped.
I agree that loop feels funny inside CL -- it fits much better into
Dylan, which has that sort of syntax *anyway*:
let result = make(<stretchy-vector>);
for(x from 0, y in some-collection)
if (y.good-result?)
add!(result, list(x, y))
end
end
Of course you could also use a list to accumulate the result, but I
usually prefer to use a vector as bein more efficient and tidier too.
This "collect" thing could be nice ... have to think about that.
I guess the Dylan could also be done as:
for(x from 0,
y in some-collection,
result = #() then
if (y.good-result?) add!(result, list(x, y)) else result end)
finally result
end
-- Bruce
Bruce Hoult wrote:
[snipped Dylan example]
> Of course you could also use a list to accumulate the result, but I
> usually prefer to use a vector as bein more efficient and tidier too.
I'm not sure what you mean by more efficient or tidier.
Using PUSH and NREVERSE is not the only way to collect items in the order
they appear (and is not the way LOOPs collect works at least in LispWorks
and CMUCL - other implementations not checked but certainly with similar
result).
You can hold a binding to the tail of the collecting-list and
append to it by sideeffecting (RPLACD or (setf (cdr..))) it. Packaged in a
nice macro (like LOOP) it should be convenient to use and efficient too.
The question if accumulating into a vector or into a list is more a question
of what you intend to do with it afterwards. Therefore it would probably be
a good idea to specify the result-type of the collection-sequence. It is an
interesting fact that Jonathan Amsterdam's ITERATE macro offers a
result-type parameter in the collect clause even if the manual lets it
unspecified what sequence type is being used for accumulation if a non-list
sequence is chosen as a result-type.
> This "collect" thing could be nice ... have to think about that.
It is definitely a nice abstraction.
ciao,
Jochen
--
http://www.dataheaven.de
In article <············@rznews2.rrze.uni-erlangen.de>, Jochen Schmidt
<···@dataheaven.de> wrote:
> Bruce Hoult wrote:
> [snipped Dylan example]
> > Of course you could also use a list to accumulate the result, but I
> > usually prefer to use a vector as bein more efficient and tidier too.
>
> I'm not sure what you mean by more efficient or tidier.
> Using PUSH and NREVERSE is not the only way to collect items in the order
> they appear (and is not the way LOOPs collect works at least in LispWorks
> and CMUCL - other implementations not checked but certainly with similar
> result).
I'm just back from reading that part of the hypespec ... and I see that
it specifies that "collect" puts the items on the end of a list (and
only a list).
Since it's possible to tell the difference between appending directly at
the end, and pushing and the reversing later -- by making the form a
progn and retaining the value returned and peeking at it later -- I
would assume that it *has* to append at the end.
> You can hold a binding to the tail of the collecting-list and
> append to it by sideeffecting (RPLACD or (setf (cdr..))) it.
> Packaged in a nice macro (like LOOP) it should be convenient to
> use and efficient too.
That's certainly better than having to walk all the way down the list
each time!
> The question if accumulating into a vector or into a list is more
> a question of what you intend to do with it afterwards.
There is that, but a stretchy vector takes a lot fewer heap allocations
than consing up a list, and it's usually faster to process afterwards
too, so I use one any time I don't absolutely, positively need a list.
All the Dylan iteration constructs and mapping functions are agnostic
with regard to collection type. They work just the same with lists,
vectors, stretchy vectors, strings, hash tables, or user-defined
collections. I understand that isn't the case in CL.
> > This "collect" thing could be nice ... have to think about that.
>
> It is definitely a nice abstraction.
After reading that bit of the hyperspec, I see that "collect" is indeed
a quite restricted thing. Dylan puts the (in CL terms)
variable-clause's into the () following the "for", but it puts all the
main-clause's into a regular block body, the same as a method or
if/then/else has. i.e. it essentially follows C or Pascal except for
allowing multiple loop variables. (OK, C allows that, but interleaves
the init/test/increment parts for each variable -- yuk!).
Dylan has a "finally", which is a syntactically distinguished toplevel
part of the loop body, but where CL has special "when" and "unless"
clauses in the loop macro, Dylan just uses the ordinary "if" and
"unless" statements. The Dylan "for" macro therefore doesn't have
anywhere to hang a special "collect" keyword.
Perhaps the best that you can do in Dylan is something like this:
define macro collecting
{ collecting (?:name, ?more-names:*) ?:body end }
=> {let vals = #();
local method ?name(item) vals := pair(item, vals) end;
let (#rest results) = collecting (?more-names) ?body end;
apply(values, reverse!(vals), results);}
{ collecting () ?:body end } => { ?body; values() }
end;
Now you can use it:
collecting (odds, evens)
for (i from 0 below 10)
if (i.odd?) odds(i) else evens(i) end
end
end
=> #(1, 3, 5, 7, 9) #(2, 4, 6, 8)
Of course you could do the same thing with a stretchy-vector, or let the
user choose which collection class to use.
Applying it to the original task here:
(loop for x from 0
for y in some-list
when (good-result? y)
collect (list x y))
collecting (good-uns)
for (x from 0,
y in some-collection)
if (y.good-result?)
good-uns(list(x, y))
end
end
end
How's that look?
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> After reading that bit of the hyperspec, I see that "collect" is
> indeed a quite restricted thing.
That's true, it's a part of the LOOP macro. On the other hand,
writing a simple with-collectors macro is about 5 minutes' work (and
I'm sure most LOOP un-fans have some sort of custom collection
facility they use). Eg:
(defmacro with-collectors ((&rest vars) &body forms)
(let ((collectors (loop for v in vars
collecting (cons v (gensym)))))
`(let ,(loop for (name . sym) in collectors
collecting `(,name ())
collecting `(,sym (cons nil nil)))
(macrolet ((collect (value &key into)
(let* ((collectors ',collectors)
(collector (cdr (assoc into collectors))))
(unless (symbolp collector)
(error "Unknown collector ~S" into))
`(let* ((val ,value)
(last-cell (cdr ,collector))
(new-cell (cons val nil)))
(cond
((consp last-cell)
(setf (cdr last-cell) new-cell
(cdr ,collector) new-cell))
(t (setf (car ,collector) new-cell
(cdr ,collector) new-cell
,into new-cell)))))))
,@forms))))
Then, you can use it like
* (with-collectors (a b c)
(dotimes (i 10)
(collect i :into a)
(collect (* 10 i) :into b)
(collect (* 100 i) :into c))
(values a b c))
(0 1 2 3 4 5 6 7 8 9)
(0 10 20 30 40 50 60 70 80 90)
(0 100 200 300 400 500 600 700 800 900)
The idea could obviously be extended to use vectors and VECTOR-PUSH-EXTEND.
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
In article <···············@apocalypse.OCF.Berkeley.EDU>,
···@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) wrote:
> Bruce Hoult <·····@hoult.org> writes:
>
> > After reading that bit of the hyperspec, I see that "collect" is
> > indeed a quite restricted thing.
>
> That's true, it's a part of the LOOP macro. On the other hand,
> writing a simple with-collectors macro is about 5 minutes' work (and
> I'm sure most LOOP un-fans have some sort of custom collection
> facility they use). Eg:
>
> (defmacro with-collectors ((&rest vars) &body forms)
> (let ((collectors (loop for v in vars
> collecting (cons v (gensym)))))
> `(let ,(loop for (name . sym) in collectors
> collecting `(,name ())
> collecting `(,sym (cons nil nil)))
> (macrolet ((collect (value &key into)
> (let* ((collectors ',collectors)
> (collector (cdr (assoc into collectors))))
> (unless (symbolp collector)
> (error "Unknown collector ~S" into))
> `(let* ((val ,value)
> (last-cell (cdr ,collector))
> (new-cell (cons val nil)))
> (cond
> ((consp last-cell)
> (setf (cdr last-cell) new-cell
> (cdr ,collector) new-cell))
> (t (setf (car ,collector) new-cell
> (cdr ,collector) new-cell
> ,into new-cell)))))))
> ,@forms))))
Right, I just showed a Dylan equivalent to that, using a recursive
macro, but it was a little different (used reverse!). I can make it a
more direct mirror of yours:
define macro with-collectors
{ with-collectors (?:name, ?more-names:*) ?:body end }
=> {let vals = #();
let last-cell = #();
local method ?name(val)
let new-cell = pair(val, #());
if (last-cell == #())
vals := last-cell := new-cell
else
last-cell := last-cell.tail := new-cell
end
end method ?name;
let (#rest results) = with-collectors (?more-names) ?body end;
apply(values, vals, results);}
{ with-collectors () ?:body end } => { ?body; values() }
end;
> Then, you can use it like
>
> * (with-collectors (a b c)
> (dotimes (i 10)
> (collect i :into a)
> (collect (* 10 i) :into b)
> (collect (* 100 i) :into c))
> (values a b c))
> (0 1 2 3 4 5 6 7 8 9)
> (0 10 20 30 40 50 60 70 80 90)
> (0 100 200 300 400 500 600 700 800 900)
with-collectors(a, b, c)
for(i from 0 below 10)
a(i);
b(10 * i);
c(100 * i)
end
end
> The idea could obviously be extended to use vectors and
> VECTOR-PUSH-EXTEND.
Right.
-- Bruce
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@news.paradise.net.nz>...
> define macro collecting
> { collecting (?:name, ?more-names:*) ?:body end }
> => {let vals = #();
> local method ?name(item) vals := pair(item, vals) end;
> let (#rest results) = collecting (?more-names) ?body end;
> apply(values, reverse!(vals), results);}
> { collecting () ?:body end } => { ?body; values() }
> end;
>
I can't read dylan, but this looks like it is doing the PUSH/REVERSE
thing.
LOOP almost certainly does not do that, and in fact there are a number
of independent COLLECTING macros around. Mine (which comes, somehow,
from InterLisp, which I think had such a thing?) is at
http://www.tfeb.org/lisp/hax.html#COLLECTING for what it's worth.
There's a single-list one and a multiple-list one which is more like
yours I think. Both do the tail-pointer thing.
--tim
In article <···························@posting.google.com>,
··········@tfeb.org (Tim Bradshaw) wrote:
> Bruce Hoult <·····@hoult.org> wrote in message
> news:<···························@news.paradise.net.nz>...
>
> > define macro collecting
> > { collecting (?:name, ?more-names:*) ?:body end }
> > => {let vals = #();
> > local method ?name(item) vals := pair(item, vals) end;
> > let (#rest results) = collecting (?more-names) ?body end;
> > apply(values, reverse!(vals), results);}
> > { collecting () ?:body end } => { ?body; values() }
> > end;
> >
>
> I can't read dylan, but this looks like it is doing the PUSH/REVERSE
> thing.
That's correct. I posted another version later which does the
tail-pointer thing.
Of course in my preferred style of using a stretchy-vector rather than a
list, putting the elements at the end is the natural thing to do.
-- Bruce
Bruce Hoult wrote:
> In article <············@rznews2.rrze.uni-erlangen.de>, Jochen Schmidt
> <···@dataheaven.de> wrote:
>
>> Bruce Hoult wrote:
>> [snipped Dylan example]
>> > Of course you could also use a list to accumulate the result, but I
>> > usually prefer to use a vector as bein more efficient and tidier too.
>>
>> I'm not sure what you mean by more efficient or tidier.
>> Using PUSH and NREVERSE is not the only way to collect items in the order
>> they appear (and is not the way LOOPs collect works at least in LispWorks
>> and CMUCL - other implementations not checked but certainly with similar
>> result).
>
> I'm just back from reading that part of the hypespec ... and I see that
> it specifies that "collect" puts the items on the end of a list (and
> only a list).
Ah ok - I definitely should try to always take a look at the HyperSpec
first...
> Since it's possible to tell the difference between appending directly at
> the end, and pushing and the reversing later -- by making the form a
> progn and retaining the value returned and peeking at it later -- I
> would assume that it *has* to append at the end.
Hm... I think I do not really understand what you mean...
>> You can hold a binding to the tail of the collecting-list and
>> append to it by sideeffecting (RPLACD or (setf (cdr..))) it.
>> Packaged in a nice macro (like LOOP) it should be convenient to
>> use and efficient too.
>
> That's certainly better than having to walk all the way down the list
> each time!
Definitely.
>> The question if accumulating into a vector or into a list is more
>> a question of what you intend to do with it afterwards.
>
> There is that, but a stretchy vector takes a lot fewer heap allocations
> than consing up a list, and it's usually faster to process afterwards
> too, so I use one any time I don't absolutely, positively need a list.
If you have a good measure on how big your collection gets than
preallocating the vector is probably a good idea. I don't know how a
"stretchy vector" in Dylan works but I think increasing it will mean
allocating a bigger vector and copying the old items over to the new space.
On the other side, allocation in GC Systems can be rather cheap (pointer
increment and return...). But I still think that the emphasis lies on what
you need the collection after accumulating. In Lisp collecting into a list
is definitely a good idea since generating code (with macros a. s. o.)
almost always means fiddling around with lists. Therefore it is possible
that the list as a datatype is more often needed in Lisp than in Dylan.
> All the Dylan iteration constructs and mapping functions are agnostic
> with regard to collection type. They work just the same with lists,
> vectors, stretchy vectors, strings, hash tables, or user-defined
> collections. I understand that isn't the case in CL.
Yes - LOOP is in several ways not as much generalized as it could be.
ITERATE offers more like this and most implementations of LOOP are
extensible too. To get iterating over arbitrary defined collection-types
possible one could define a generic function named ITEM that has methods
for lists, arrays or user-defined collections. Then you would add another
clause to LOOP or ITERATE that uses this method.
Something like:
(loop for x over user-defined-sequence
...)
On the other side - I do not need user-defined sequences very often (I
actually cannot remember if I ever needed one...) in Common Lisp since it
already offers a good amount of primitives to choose from.
>> > This "collect" thing could be nice ... have to think about that.
>>
>> It is definitely a nice abstraction.
>
> After reading that bit of the hyperspec, I see that "collect" is indeed
> a quite restricted thing. Dylan puts the (in CL terms)
> variable-clause's into the () following the "for", but it puts all the
> main-clause's into a regular block body, the same as a method or
> if/then/else has. i.e. it essentially follows C or Pascal except for
> allowing multiple loop variables. (OK, C allows that, but interleaves
> the init/test/increment parts for each variable -- yuk!).
Yes - the main problem with LOOPs collect is IMHO that you cannot embed it
in arbitrary Lispcode. In this regard ITERATE is better since ITERATE's
collect is simply like a normal function-call.
(iter (for i from 0 to 20)
(if (only-print-p i)
(print i)
(collect i)))
> Dylan has a "finally", which is a syntactically distinguished toplevel
> part of the loop body, but where CL has special "when" and "unless"
> clauses in the loop macro, Dylan just uses the ordinary "if" and
> "unless" statements. The Dylan "for" macro therefore doesn't have
> anywhere to hang a special "collect" keyword.
As I said - ITERATE solves this "problem" pretty well.
> Perhaps the best that you can do in Dylan is something like this:
>
>
>
> define macro collecting
> { collecting (?:name, ?more-names:*) ?:body end }
> => {let vals = #();
> local method ?name(item) vals := pair(item, vals) end;
> let (#rest results) = collecting (?more-names) ?body end;
> apply(values, reverse!(vals), results);}
> { collecting () ?:body end } => { ?body; values() }
> end;
>
> Now you can use it:
>
>
> collecting (odds, evens)
> for (i from 0 below 10)
> if (i.odd?) odds(i) else evens(i) end
> end
> end
>
> => #(1, 3, 5, 7, 9) #(2, 4, 6, 8)
>
> Of course you could do the same thing with a stretchy-vector, or let the
> user choose which collection class to use.
This looks similar to some collection macros I've seen somewhere (AFAIR Tim
Bradshaw has written something like this for CL)
> Applying it to the original task here:
>
> (loop for x from 0
> for y in some-list
> when (good-result? y)
> collect (list x y))
>
> collecting (good-uns)
> for (x from 0,
> y in some-collection)
> if (y.good-result?)
> good-uns(list(x, y))
> end
> end
> end
>
> How's that look?
It looks ok for me... ;-)
ciao,
Jochen
--
http://www.dataheaven.de
In article <············@rznews2.rrze.uni-erlangen.de>, Jochen Schmidt
<···@dataheaven.de> wrote:
> > Since it's possible to tell the difference between appending directly
> > at
> > the end, and pushing and the reversing later -- by making the form a
> > progn and retaining the value returned and peeking at it later -- I
> > would assume that it *has* to append at the end.
>
> Hm... I think I do not really understand what you mean...
Well, I changed my mind :-) What I was thinking of was something like:
(setq l '())
(loop for i from 0 to 10
collect (let ((a (list i (* i i))))
(setq l (cons a l))
a))
But then I realized that although you can do stuff with the element
you're collecting afterwards, you can't get at the cons cell that the
loop macro allocated to link it into the list.
> >> The question if accumulating into a vector or into a list is more
> >> a question of what you intend to do with it afterwards.
> >
> > There is that, but a stretchy vector takes a lot fewer heap allocations
> > than consing up a list, and it's usually faster to process afterwards
> > too, so I use one any time I don't absolutely, positively need a list.
>
> If you have a good measure on how big your collection gets than
> preallocating the vector is probably a good idea. I don't know how a
> "stretchy vector" in Dylan works but I think increasing it will mean
> allocating a bigger vector and copying the old items over to the new
> space.
Right. If you increase the size of the vector by a multiplicative
factor each time then it's amortized constant time per element -- for
example if you double the size each time, then each element is on
average copied no more than once. The total memory allocated (and the
numbe of memory writes) is also no more than twice the size of the final
vector, which is exactly the same as the amount of memory allocated for
the same number of cons cells, but it is done in fewer allocations:
log2(N) vs N.
Allocation might or might not be faster, but iterating through it later
almost certainly is, because bumping a pointer is faster than chasing a
pointer.
And if you know in advance how many elements you need then you can
preallocate them :-)
> > All the Dylan iteration constructs and mapping functions are agnostic
> > with regard to collection type. They work just the same with lists,
> > vectors, stretchy vectors, strings, hash tables, or user-defined
> > collections. I understand that isn't the case in CL.
>
> Yes - LOOP is in several ways not as much generalized as it could be.
> ITERATE offers more like this and most implementations of LOOP are
> extensible too. To get iterating over arbitrary defined collection-types
> possible one could define a generic function named ITEM that has methods
> for lists, arrays or user-defined collections. Then you would add another
> clause to LOOP or ITERATE that uses this method.
>
> Something like:
> (loop for x over user-defined-sequence
> ...)
Dylan uses a Generic Function called "forward-iteration-protocol" as the
link between the iteration/mapping constructs and the collections.
For example, the standard "find-key()" function:
-------------------------------------------------------
define method find-key
(collection :: <collection>, predicate :: <function>,
#key skip :: <integer> = 0, failure = #f)
=> (key-or-failure :: <object>);
let (init-state, limit, next-state, done?,
current-key, current-element)
= forward-iteration-protocol(collection);
block (found)
for (state = init-state then next-state(collection, state),
until: done?(collection, state, limit))
if (predicate(current-element(collection, state)))
if (skip > 0)
skip := skip - 1;
else
found(current-key(collection, state));
end if;
end if;
finally
failure
end for;
end block;
end method find-key;
-------------------------------------------------------
For collections where the compiler knows the type this gets optimized
to the same simple loop you'd code in C to iterate through an array, or
step along a linked list.
For unknown collections, you get a GF call at the start to extract two
objects and four function pointers (the 5th, current-element-setter, is
ignored here) and then three function calls per iteration.
> On the other side - I do not need user-defined sequences very often (I
> actually cannot remember if I ever needed one...) in Common Lisp since it
> already offers a good amount of primitives to choose from.
New data structures are being invented all the time: AVL trees,
Red/Black trees, tries, B-trees, B+-trees, B*-trees, skip lists... OK,
those are all old. But if you do happen to design a new data structure,
in Dylan you just add a method to forward-iteration-protocol and your
data structure will instantly work with for(e in c), map, do, find-key,
reverse, any?, every?, reduce, member?, fill!, size, choose, choose-by,
shallow-copy ... you name it.
-- Bruce
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@news.paradise.net.nz>...
>
> Well, I changed my mind :-) What I was thinking of was something like:
>
> (setq l '())
> (loop for i from 0 to 10
> collect (let ((a (list i (* i i))))
> (setq l (cons a l))
> a))
>
> But then I realized that although you can do stuff with the element
> you're collecting afterwards, you can't get at the cons cell that the
> loop macro allocated to link it into the list.
I think you can.
(loop repeat 10
collect 1 into results
do (print results)
finally (return results))
or maybe I don't understand what you mean.
--tim
In article <····························@posting.google.com>,
··········@tfeb.org (Tim Bradshaw) wrote:
> Bruce Hoult <·····@hoult.org> wrote in message
> news:<···························@news.paradise.net.nz>...
> >
> > Well, I changed my mind :-) What I was thinking of was something like:
> >
> > (setq l '())
> > (loop for i from 0 to 10
> > collect (let ((a (list i (* i i))))
> > (setq l (cons a l))
> > a))
> >
> > But then I realized that although you can do stuff with the element
> > you're collecting afterwards, you can't get at the cons cell that the
> > loop macro allocated to link it into the list.
>
> I think you can.
>
> (loop repeat 10
> collect 1 into results
> do (print results)
> finally (return results))
>
> or maybe I don't understand what you mean.
Ah, OK. But it would be more revealing to do:
* (loop for n from 1 to 10
collect n into results
do (print results)
finally (return results))
(1)
(1 2)
(1 2 3)
(1 2 3 4)
(1 2 3 4 5)
(1 2 3 4 5 6)
(1 2 3 4 5 6 7)
(1 2 3 4 5 6 7 8)
(1 2 3 4 5 6 7 8 9)
(1 2 3 4 5 6 7 8 9 10)
(1 2 3 4 5 6 7 8 9 10)
*
-- Bruce
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@news.paradise.net.nz>...
> In article <···························@news.paradise.net.nz>, Bruce
> Hoult <·····@hoult.org> wrote:
>
> > Ah, OK. But it would be more revealing to do:
> >
> > * (loop for n from 1 to 10
> > collect n into results
> > do (print results)
> > finally (return results))
> >
> > (1)
> > (1 2)
> > (1 2 3)
> > (1 2 3 4)
> > (1 2 3 4 5)
> > (1 2 3 4 5 6)
> > (1 2 3 4 5 6 7)
> > (1 2 3 4 5 6 7 8)
> > (1 2 3 4 5 6 7 8 9)
> > (1 2 3 4 5 6 7 8 9 10)
> > (1 2 3 4 5 6 7 8 9 10)
> > *
>
> Interesting. It seems that "results" is being rebound from something
> else each time around the loop:
I don't see how you get this. There will be a special case at the
start I expect but after that the binding should not be altered,
collect will just smash something into the tail (presumably keeping a
tail-pointer somewhere).
--tim
Bruce Hoult <·····@hoult.org> wrote in message news:<···························@news.paradise.net.nz>...
> You looked at the wrong code. Look at the code after that comment, not
> before.
Yes, I did, sorry.
--tim