Newbie here. In my lisp hackery, I came across the need for a
function to get the first n items off a list. I was kind of surprised
to not find such a function already in the common lisp spec. If there
is, and I've overlooked it, by all means direct me there.
Anyway, I whipped one up in a few lines that not only pulls n items
off the list, but it returns the remaining items as well. Let me know
what you think. I was kind of surprised that I was able to do it
without the use of an accumulator parameter.
(defun first-n (n list)
"Splits the list after the first n elements"
(if (= 0 n)
(values '() list)
(multiple-value-bind (from-front rest) (first-n (1- n) (rest
list))
(values (cons (first list) from-front) rest))))
So my question is this: does this count as tail recursion? The actual
"last operation" of the function is just repackaging the values
returned from the recursive call. Can lisp's compiler optimize this
into a loop?
And, secondarily, is it considered naughty to use variables like
"list" and "rest" that are built-in function names?
Thanks,
Erik
>
> So my question is this: does this count as tail recursion? The actual
> "last operation" of the function is just repackaging the values
> returned from the recursive call. Can lisp's compiler optimize this
> into a loop?
Common Lisp does not promise tail call elimination of any kind, so
whether this gets optimised is entirely dependent on the
implementation. If you need it to be a loop on any implementation,
you should write it as one (indeed the LOOP macro is the absolute king
of clarity for doing something like this.
>
> And, secondarily, is it considered naughty to use variables like
> "list" and "rest" that are built-in function names?
No. Indeed since it causes Lisp-1 people to go red in the face it is
considered particularly good style. If you can cause them actually to
burst Kenny will send you a reward.
--tim
Erik R. wrote:
> Newbie here.
Will it never end?!
> In my lisp hackery, I came across the need for a
> function to get the first n items off a list. I was kind of surprised
> to not find such a function already in the common lisp spec. If there
> is, and I've overlooked it, by all means direct me there.
SUBSEQ?
hth, kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
On Sep 6, 7:01 pm, Ken Tilton <···········@optonline.net> wrote:
> Erik R. wrote:
> > Newbie here.
>
> Will it never end?!
>
> > In my lisp hackery, I came across the need for a
> > function to get the first n items off a list. I was kind of surprised
> > to not find such a function already in the common lisp spec. If there
> > is, and I've overlooked it, by all means direct me there.
>
> SUBSEQ?
>
> hth, kt
>
> --http://www.theoryyalgebra.com/
>
> "We are what we pretend to be." -Kurt Vonnegut
It will end when all us newbies get to be hardened newbie haters like
you. :-)
SUBSEQ is kinda what I'm looking for, yeah. Since I actually want
both the first N and the remaining list, it looks like I'd have to
call SUBSEQ twice. Thanks for that.
Anyway, you didn't answer my principle question, which was "Is that
function actually tail recursive enough to be optimized by the
compiler?"
On Sep 6, 1:16 pm, "Erik R." <·············@gmail.com> wrote:
[...]
> It will end when all us newbies get to be hardened newbie haters like
> you. :-)
I've already concluded that all you newbies are actually Kenny's
alternate personalities, and the other readers of comp.lang.lisp are
watching some sort of weird psychodrama play out across Usenet. It's
kind of like the movie "Identity", but with less Amanda Peet and more
parentheses.
Cheers,
Pillsy
Erik R. wrote:
> On Sep 6, 7:01 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>Erik R. wrote:
>>
>>>Newbie here.
>>
>>Will it never end?!
>>
>>
>>> In my lisp hackery, I came across the need for a
>>>function to get the first n items off a list. I was kind of surprised
>>>to not find such a function already in the common lisp spec. If there
>>>is, and I've overlooked it, by all means direct me there.
>>
>>SUBSEQ?
>>
>>hth, kt
>>
>>--http://www.theoryyalgebra.com/
>>
>>"We are what we pretend to be." -Kurt Vonnegut
>
>
> It will end when all us newbies get to be hardened newbie haters like
> you. :-)
I'd tell you to shut and go fill in your Road to Lisp Survey, but I
doubt the ALU servers could handle the load if all you rugrats descended
on it at once.
>
> SUBSEQ is kinda what I'm looking for, yeah. Since I actually want
> both the first N and the remaining list, it looks like I'd have to
> call SUBSEQ twice. Thanks for that.
Sorry, did not notice that requirement. Lessee:
(let ((x '(dear noobs please go a way)))
(flet ((bifurcate (list n &aux
(c (copy-list list))
(mthcdr (nthcdr (1- n) c)))
(values c (prog1 (cdr mthcdr)
(rplacd mthcdr nil)))))
(bifurcate x 2)))
>
> Anyway, you didn't answer my principle question, which was "Is that
> function actually tail recursive enough to be optimized by the
> compiler?"
>
Oh, I thought I would let the Scheme-haters test your asbestos over that
affront to the community.
kenny
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
"Erik R." <·············@gmail.com> writes:
> (defun first-n (n list)
> "Splits the list after the first n elements"
> (if (= 0 n)
> (values '() list)
> (multiple-value-bind (from-front rest) (first-n (1- n) (rest
> list))
> (values (cons (first list) from-front) rest))))
>
> So my question is this: does this count as tail recursion?
No, you'd have to use an accumulator to make this tail recursive.
> The actual "last operation" of the function is just repackaging the
> values returned from the recursive call. Can lisp's compiler
> optimize this into a loop?
In theory of course the compiler can make any program into any
functional equivalent. But in practice I doubt it very much. And what
would be the point of haing the compiler de-obfuscate your code,
really? If you want it to be a loop, it's better for everybody to
write a loop:
(values (loop repeat n collect (pop list))
list)
which should be equivalent to
(values (subseq list 0 n)
(nthcdr n list))
> And, secondarily, is it considered naughty to use variables like
> "list" and "rest" that are built-in function names?
No, that's generally considered perfectly acceptable in Common
Lisp. Rather, names like "lst" that are disliked here.
--
Frode Vatvedt Fjeld
On Sep 6, 7:37 pm, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> "Erik R." <·············@gmail.com> writes:
> > (defun first-n (n list)
> > "Splits the list after the first n elements"
> > (if (= 0 n)
> > (values '() list)
> > (multiple-value-bind (from-front rest) (first-n (1- n) (rest
> > list))
> > (values (cons (first list) from-front) rest))))
>
> > So my question is this: does this count as tail recursion?
>
> No, you'd have to use an accumulator to make this tail recursive.
>
> > The actual "last operation" of the function is just repackaging the
> > values returned from the recursive call. Can lisp's compiler
> > optimize this into a loop?
>
> In theory of course the compiler can make any program into any
> functional equivalent. But in practice I doubt it very much. And what
> would be the point of haing the compiler de-obfuscate your code,
> really? If you want it to be a loop, it's better for everybody to
> write a loop:
>
> (values (loop repeat n collect (pop list))
> list)
>
> which should be equivalent to
>
> (values (subseq list 0 n)
> (nthcdr n list))
>
> > And, secondarily, is it considered naughty to use variables like
> > "list" and "rest" that are built-in function names?
>
> No, that's generally considered perfectly acceptable in Common
> Lisp. Rather, names like "lst" that are disliked here.
>
> --
> Frode Vatvedt Fjeld
Thanks guys. I particularly like Frode's: (values (loop repeat n
collect (pop list)) list).
Sounds like the loop macro is a 'must learn' feature of common lisp.
Cheers,
Erik
On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
> Sounds like the loop macro is a 'must learn' feature of common lisp.
There are some good alternatives out there, like ITERATE and SERIES
(which I particularly recommend; it transforms functional-looking code
into optimized iterative code), but LOOP is built-in and a lot of CL
coders (including myself) use it.
mfh
Mark H. wrote:
> On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>
>>Sounds like the loop macro is a 'must learn' feature of common lisp.
Absolutely. I refused for years because it was a different language and
every time I looked at the CLHS it made no sense. I tested PCL by
reading the section on loop and peter had done a good job of breaking it
down sensibly, never looked back. One of the strokes of genius from
McCarthy was making lists the center of the language, so a DSL for
mucking with lists is both justified and essential.
It's a bit of a hassle to have to learn something so un-Lispy soon after
starting with Lisp, but if unlike most of the clowns who hang around
this NG you are actually interested in getting some work done with Lisp,
treat yourself to a pint of single-malt and a bag of chips and spend
two hours with PCL and loop.
hth, kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
On Sep 6, 6:31 pm, Ken Tilton <···········@optonline.net> wrote:
> It's a bit of a hassle to have to learn something so un-Lispy soon after
> starting with Lisp, but if unlike most of the clowns who hang around
> this NG you are actually interested in getting some work done with Lisp,
> treat yourself to a pint of single-malt and a bag of chips and spend
> two hours with PCL and loop.
>
While doing the problems at Project Euler may not be considered work,
I can say that LOOP makes some of those puzzles easy to come up with
reasonable answers. Something like
(loop for i from 1 to 1000 sum (expt i i))
sure is easy to type at the REPL.
I would take the time to learn the basics of LOOP, at the very least.
Kenny, you're human!
Thanks for proving to me that you're not an AI hell bent on scaring
away
us mortals from learning Lisp effectively enough to understand your
source.
I'm hopeful that early AI won't be able to appreciate the
complementary nature
of alcohol and sodium.
-Mike
On Sep 6, 6:31 pm, Ken Tilton <···········@optonline.net> wrote:
> Mark H. wrote:
> > On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>
> >>Sounds like the loop macro is a 'must learn' feature of common lisp.
>
> Absolutely. I refused for years because it was a different language and
> every time I looked at the CLHS it made no sense. I tested PCL by
> reading the section on loop and peter had done a good job of breaking it
> down sensibly, never looked back. One of the strokes of genius from
> McCarthy was making lists the center of the language, so a DSL for
> mucking with lists is both justified and essential.
>
> It's a bit of a hassle to have to learn something so un-Lispy soon after
> starting with Lisp, but if unlike most of the clowns who hang around
> this NG you are actually interested in getting some work done with Lisp,
> treat yourself to a pint of single-malt and a bag of chips and spend
> two hours with PCL and loop.
>
> hth, kt
>
> --http://www.theoryyalgebra.com/
>
> "We are what we pretend to be." -Kurt Vonnegut
Mike G. wrote:
> Kenny, you're human!
No, but if you saw me in my natural form you'd be scarred for life. We
Lisp Gods assume a mortal form just long enough to convey messages such
as "learn loop" and "master those funny cons diagrams".
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
On Sep 7, 11:25 am, Ken Tilton <···········@optonline.net> wrote:
> We
> Lisp Gods
We?
Kzo, the ex-King of Eritivaria having pointed out to me those
unparalleled cdr codes to which I have alluded, and many more besides,
hospitably asked me if there was anything else that I would care to
see, he meant the pieces of data that they had in the cupboards, the
curiously graven fixnums of other princes, historic functions,
legendary hacks, but I who had had a glimpse of their marvellous
staircase, whose balustrade I believed to be solid conses and
wondering why in such a stately house they chose to dine in the
basement, mentioned the word "upstairs." A profound hush came down on
the whole assembly, the hush that might greet levity in a cathedral.
"Upstairs!" he gasped. "We cannot go upstairs."
I perceived that what I had said was an ill-chosen thing. I tried to
excuse myself but knew not how.
"Of course," I muttered, "members may not take guests upstairs."
"Members!" he said to me. "We are not the members!"
There was such reproof in his voice that I said no more, I looked at
him questioningly, perhaps my lips moved, I may have said "What are
you?" A great surprise had come on me at their attitude.
"We are the waiters," he said.
That I could not have known, here at last was honest ignorance that I
had no need to be ashamed of, the very obfuscation of their code
denied it.
"Then who are the members?" I asked.
Such a hush fell at that question, such a hush of genuine awe, that
all of a sudden a wild thought entered my head, a thought strange and
fantastic and terrible. I gripped my host by the wrist and hushed my
voice.
"Are they too exiles?" I asked.
Twice as he looked in my face he gravely nodded his head.
I left that newsgroup very swiftly indeed, never to see it again,
scarcely pausing to say farewell to those menial kings, and as I left
the door a great window opened far up at the top of the house and a
flash of lightning streamed from it and killed a dog.
(with very considerable apologies to Edward John Moreton Drax Plunkett
from whom I have stolen this)
Tim Bradshaw wrote:
> On Sep 7, 11:25 am, Ken Tilton <···········@optonline.net> wrote:
>
>
>>We
>>Lisp Gods
>
>
> We?
Fine, bring me a single malt, a pint of amber back, a wedge of cheddar
and some saltines. And we'll need more napkins before we're done with
this design.
kt
ps. Oh, and another jar of dijon, and ask the redhead under the
moosehead if she would like to join us. Ta. k
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
On Sep 7, 8:03 pm, Ken Tilton <···········@optonline.net> wrote:
>
> Fine, bring me a single malt,
You should try some smokehead if it's available over there. It's
rumoured to be a (young) Caol Ila and I think it might be, though
there are other theories. The glasses smell amazing the next morning.
On Fri, 07 Sep 2007 06:25:14 -0400, Ken Tilton
<···········@optonline.net> wrote:
>Mike G. wrote:
>> Kenny, you're human!
>
>No, but if you saw me in my natural form you'd be scarred for life. We
>Lisp Gods assume a mortal form just long enough to convey messages such
>as "learn loop" and "master those funny cons diagrams".
Angelic or demonic?
--
for email reply remove "/" from address
On Sep 7, 12:31 am, Ken Tilton <···········@optonline.net> wrote:
> Mark H. wrote:
> > On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>
> >>Sounds like the loop macro is a 'must learn' feature of common lisp.
>
> Absolutely. I refused for years because it was a different language and
> every time I looked at the CLHS it made no sense. I tested PCL by
> reading the section on loop and peter had done a good job of breaking it
> down sensibly, never looked back. One of the strokes of genius from
> McCarthy was making lists the center of the language, so a DSL for
> mucking with lists is both justified and essential.
>
> It's a bit of a hassle to have to learn something so un-Lispy soon after
> starting with Lisp, but if unlike most of the clowns who hang around
> this NG you are actually interested in getting some work done with Lisp,
> treat yourself to a pint of single-malt and a bag of chips and spend
> two hours with PCL and loop.
>
> hth, kt
>
> --http://www.theoryyalgebra.com/
>
> "We are what we pretend to be." -Kurt Vonnegut
Thanks. I just re-read the PCL LOOP chapter. A pint of single-malt
probably isn't the best companion when trying to learn a complex new
looping syntax, but I appreciate the gesture.
I think you'll find that I'm serious about learning Lisp. Hopefully
my questions will get more "clueful".
Cheers,
Erik
"Erik R." <·············@gmail.com> writes:
> On Sep 7, 12:31 am, Ken Tilton <···········@optonline.net> wrote:
>> Mark H. wrote:
>> > On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>>
>> >>Sounds like the loop macro is a 'must learn' feature of common lisp.
>>
>> Absolutely. I refused for years because it was a different language and
>> every time I looked at the CLHS it made no sense. I tested PCL by
>> reading the section on loop and peter had done a good job of breaking it
>> down sensibly, never looked back. One of the strokes of genius from
>> McCarthy was making lists the center of the language, so a DSL for
>> mucking with lists is both justified and essential.
>>
>> It's a bit of a hassle to have to learn something so un-Lispy soon after
>> starting with Lisp, but if unlike most of the clowns who hang around
>> this NG you are actually interested in getting some work done with Lisp,
>> treat yourself to a pint of single-malt and a bag of chips and spend
>> two hours with PCL and loop.
>>
>> hth, kt
>>
>> --http://www.theoryyalgebra.com/
>>
>> "We are what we pretend to be." -Kurt Vonnegut
>
> Thanks. I just re-read the PCL LOOP chapter. A pint of single-malt
> probably isn't the best companion when trying to learn a complex new
> looping syntax, but I appreciate the gesture.
I suspect after drinking a pint of single malt in two hours you'd
never find the opportunity to use loop again.
Rob St. Amant wrote:
> "Erik R." <·············@gmail.com> writes:
>
>
>>On Sep 7, 12:31 am, Ken Tilton <···········@optonline.net> wrote:
>>
>>>Mark H. wrote:
>>>
>>>>On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>>>
>>>>>Sounds like the loop macro is a 'must learn' feature of common lisp.
>>>
>>>Absolutely. I refused for years because it was a different language and
>>>every time I looked at the CLHS it made no sense. I tested PCL by
>>>reading the section on loop and peter had done a good job of breaking it
>>>down sensibly, never looked back. One of the strokes of genius from
>>>McCarthy was making lists the center of the language, so a DSL for
>>>mucking with lists is both justified and essential.
>>>
>>>It's a bit of a hassle to have to learn something so un-Lispy soon after
>>>starting with Lisp, but if unlike most of the clowns who hang around
>>>this NG you are actually interested in getting some work done with Lisp,
>>> treat yourself to a pint of single-malt and a bag of chips and spend
>>>two hours with PCL and loop.
>>>
>>>hth, kt
>>>
>>>--http://www.theoryyalgebra.com/
>>>
>>>"We are what we pretend to be." -Kurt Vonnegut
>>
>>Thanks. I just re-read the PCL LOOP chapter. A pint of single-malt
>>probably isn't the best companion when trying to learn a complex new
>>looping syntax, but I appreciate the gesture.
>
>
> I suspect after drinking a pint of single malt in two hours you'd
> never find the opportunity to use loop again.
Nonsense, the blood alcohol would only be .016. Depending on how many
chips he ate, of course.
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
"Mark H." <············@gmail.com> writes:
> On Sep 6, 11:13 am, "Erik R." <·············@gmail.com> wrote:
>> Sounds like the loop macro is a 'must learn' feature of common lisp.
>
> There are some good alternatives out there, like ITERATE and SERIES
> (which I particularly recommend; it transforms functional-looking code
> into optimized iterative code), but LOOP is built-in and a lot of CL
> coders (including myself) use it.
Is there any advantage to using ITERATE (and/or SERIES) instead of
LOOP? I guess I'm asking what sorts of things these constructs are
good at, where LOOP might not do so well.
David
[Hey, Kenny, See? I finally figured out this old skool newsreader.
Who'd a thought it knows how to send email, too! ;-) ]
--
These are not the droids you are looking for. Move along.
David Trudgett <·········@yahoo.com> writes:
> Is there any advantage to using ITERATE (and/or SERIES) instead of
> LOOP?
I'll leave ITERATE for now, but SERIES is definitely a different sort of
beast. Most important, it /composes/ loops and step-wise processing, and
is somewhat analogous to generators and streams. (CLtL2 defines a
sibling set "generators" and "gatherers" that build atop SERIES.�)
SERIES is useful when you have some very long or infinite stream of
input, and you have several kinds of processing or transformations you'd
like to do with each element of this input (or even groups of input
elements), and you want to be able to compose these processes or
transformations. The important part: You don't want to have to feed the
whole input stream through the first transformation, collect the output,
then feed it again through the second transformation, collect that
output, and so on. Such "list at a time" processing wastes time, memory,
and forces you to only accept /bounded/ input streams.
Instead, with SERIES, you can define each of these transformations as
"series functions", meaning that they take as input one or more series
(like the "streams" mentioned above) and usually produce one or more
series. But by "produce" here, we really mean something more like
"transform and provide".
As a simple example, consider a very long series of integers (maybe it's
a column from a database query) that you'd like to multiply by two. One
way to do that is to read the entire column from the database query into
an array or a list, then walk the sequence and multiply each entry by
two, either in place or into a fresh target sequence. Alternately, you
could use a cursor to take the database rows one by one, multiplying
each entry by two.
But now you realize you'd like to take those doubled numbers and clamp
some of them; maybe all those over 100 should be changed to 100. Would
you take the "doubling" output sequence again and walk it, adjusting the
values in-place or writing them to yet another fresh sequence? You'd be
visiting each element twice, and possibly wasting a lot of intermediate
storage among these transformation steps. And what would you do if the
database held more records that you could fit in RAM?
One can write the first "doubling" iteration in terms of a
"call-with-..." function and "do-..." macro pair that calls on some
caller-provided function with each doubled value. That would allow
integrating the second clamping transformation without needing the
intermediate storage. And when a third transformation comes along, one
can write a similar "call-with-..."/"do-..." pair for the clamped
transformation. SERIES automates, or at least formalizes these composed
transformations.
Note that there are some rules one must abide by to get the efficiency
gains out of SERIES. Not all problems can benefit from SERIES.
I've used it recently in some digital signal processing work, where I
modeled a few shift registers as series functions and built several
downstream processing steps as series functions as well. As the shift
registers produce an infinite output sequence, it makes sense to compose
the consumption of the shift registers' output as transformations on
discrete elements (or clumps of elements, such as delayed values). Each
"pump" of the system yields one value out of the shift registers, which
passes through all the composed transformations before another value is
drawn from the shift registers.
Some of what I describe here could be done with mapcar and curried or
composed functions just as well; SERIES raises the conceptual level to a
kit of parts.
Footnotes:
� http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node362.html
--
Steven E. Harris
Why doesn't anyone use a lambda in a let block to build lists? Is
that not good practice?
(let ((accum '())
(foo (lambda (n)
(cond ((nullp n) nil)
(t (push (car n) accum)
(foo (cdr n)))))))
(foo '(some sort of list)))
Jeff <········@gmail.com> writes:
> Why doesn't anyone use a lambda in a let block to build lists? Is
> that not good practice?
>
> (let ((accum '())
> (foo (lambda (n)
> (cond ((nullp n) nil)
> (t (push (car n) accum)
> (foo (cdr n)))))))
> (foo '(some sort of list)))
1. this is not valid CL code, perhaps Scheme
2. even if you rewrite in CL, there is no guarantee that your
implementation will make this tail recursive, as it is not required in
CL
3. perfectly good macros (loop, iterate) are available that generate
nice code very easily
Tamas
Tamas Papp wrote:
> Jeff <········@gmail.com> writes:
>
>> Why doesn't anyone use a lambda in a let block to build lists? Is
>> that not good practice?
>>
>> (let ((accum '())
>> (foo (lambda (n)
>> (cond ((nullp n) nil)
>> (t (push (car n) accum)
>> (foo (cdr n)))))))
>> (foo '(some sort of list)))
>
> 1. this is not valid CL code, perhaps Scheme
>
> 2. even if you rewrite in CL, there is no guarantee that your
> implementation will make this tail recursive, as it is not required in
> CL
>
> 3. perfectly good macros (loop, iterate) are available that generate
> nice code very easily
4. Recursive code and push? Urgh. At least accumulate as a parameter if
a functional solution is desired. :)
Jeff <········@gmail.com> writes:
> Why doesn't anyone use a lambda in a let block to build lists? Is
> that not good practice?
>
> (let ((accum '())
> (foo (lambda (n)
> (cond ((nullp n) nil)
> (t (push (car n) accum)
> (foo (cdr n)))))))
> (foo '(some sort of list)))
>
Well, to translate your Scheme to Common Lisp, you would have:
(let ((accum '()))
(labels ((foo (n)
(cond ((null n) nil)
(t (push (car n) accum)
(foo (cdr n))))))
(foo '(some sort of list))
accum))
which in this case would yield:
(LIST OF SORT SOME)
But in CL we don't use recursive procedure definitions to do
iteration. We use iterative constructs instead:
(LOOP FOR ITEM IN '(SOME SORT OF LIST) COLLECT ITEM)
=> (SOME SORT OF LIST)
Of course, this solution doesn't look nearly as impressive and also
neglects to reverse the order of the items in the list...
Regards,
David Trudgett
--
These are not the droids you are looking for. Move along.
David Trudgett <·········@yahoo.com> wrote:
+---------------
| But in CL we don't use recursive procedure definitions to do
| iteration. We use iterative constructs instead:
| (LOOP FOR ITEM IN '(SOME SORT OF LIST) COLLECT ITEM)
| => (SOME SORT OF LIST)
| Of course, this solution doesn't look nearly as impressive and also
| neglects to reverse the order of the items in the list...
+---------------
And even if one were resisting LOOP for sme odd reason,
there are still plenty of other ways to do it in CL, e.g.:
> (let (accum)
(dolist (i '(some sort of list) accum)
(push i accum)))
(LIST OF SORT SOME)
>
Of course, for that *particular* semantics you'd be better
of with simply:
> (reverse '(some sort of list))
(LIST OF SORT SOME)
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
> But in CL we don't use recursive procedure definitions to do
> iteration. We use iterative constructs instead...
Why is that? It seems more elegant than passing an accumulator around
(and less expensive).
> And even if one were resisting LOOP for sme odd reason,
> there are still plenty of other ways to do it in CL, e.g.:
>
> > (let (accum)
> (dolist (i '(some sort of list) accum)
> (push i accum)))
>
> (LIST OF SORT SOME)
That makes a lot of sense - most cases where tail recursion applies
could be more easily and quickly done using imperative, destructive
mechanisms. But when I think of trying to apply tail recursion to
accumulating functions, I think functional programming (because most
other languages do it with iteration), and that makes me think of a
lambda building a list outside its scope a la OCaml (not to start
*that* fight here).
> Of course, for that *particular* semantics you'd be better
> of with simply:
>
> > (reverse '(some sort of list))
:)
Jeff wrote:
>>But in CL we don't use recursive procedure definitions to do
>>iteration. We use iterative constructs instead...
>
>
> Why is that? It seems more elegant than passing an accumulator around
> (and less expensive).
I had fun using recursion for iteration in Logo, which had no iteration
constructs, but Lisp does have iterative constructs, so using recursion
is misleading in that it suggests more than iteration is going on, that
I somehow need the result of the recursive call to complete my
processing of the current item. The elegance lies in using the tool most
like the task.
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
Jeff <········@gmail.com> writes:
>> But in CL we don't use recursive procedure definitions to do
>> iteration. We use iterative constructs instead...
>
> Why is that? It seems more elegant than passing an accumulator around
> (and less expensive).
Using a recursive procedure definition to perform an iterative
accumulation avoids the necessity of passing around an accumulator...
how?
On the other hand, closing over lexical variables or using special
variables where appropriate are both ways in which one might avoid
passing around an accumulator. One could also use an object oriented
programming style.
As for seeming more elegant, Ken is quite right to point out that the
elegance lies in choosing the appropriate tool for the job: don't use
a blaster to unwrap your Christmas presents when a light sabre will do
the job quite nicely, thank you very much.
There is nothing elegant about using recursion to do non-recursive
tasks, when there are better tools to hand. Minimalism as per the
Scheme credo is not the only kind of elegance, although Scheme is
really quite neat in its own way. For instance, it's cool to be able
to write stuff like:
((generate-operation x y z) arg1 arg2 arg3 arg4)
although I am not sure of the extent of the practical advantage to
being able to write things like that.
David Trudgett
--
These are not the droids you are looking for. Move along.
> Using a recursive procedure definition to perform an iterative
> accumulation avoids the necessity of passing around an accumulator...
> how?
I meant that by locally assigning a lambda which can access and push
to a list in the current scope (outside of the lambda), the function
can use recursion without having to pass the accumulator around
(since the accumulator is outside of the lambda and the lambda is
destructively modifying it). It's a technique used my lots of
functional
languages (OCaml and so forth) to keep programmers from tarnishing
their
soul by using iterative structures ;)
> As for seeming more elegant, Ken is quite right to point out that the
> elegance lies in choosing the appropriate tool for the job: don't use
> a blaster to unwrap your Christmas presents when a light sabre will do
> the job quite nicely, thank you very much.
I agree completely. The example was contrived; in jut about any case
where tail recursion is possible, iteration is more succinct. I was
simply
wondering why that tactic was not used in cl in cases where it might
save
time or be more expressive to use recursion.
> There is nothing elegant about using recursion to do non-recursive
> tasks, when there are better tools to hand.
I absolutely agree.
> These are not the droids you are looking for. Move along.
They are too. He is trying a Jedi mind trick on you!
Jeff <········@gmail.com> writes:
>> As for seeming more elegant, Ken is quite right to point out that the
>> elegance lies in choosing the appropriate tool for the job: don't use
>> a blaster to unwrap your Christmas presents when a light sabre will do
>> the job quite nicely, thank you very much.
>
> I agree completely. The example was contrived; in jut about any case
> where tail recursion is possible, iteration is more succinct. I was
> simply wondering why that tactic was not used in cl in cases where
> it might save time or be more expressive to use recursion.
I think you were probably wondering about something that isn't true.
By that I mean that it is in fact the case that recursive procedures
are generally programmed recursively in Common Lisp, these being the
cases where using recursion is both more expressive and saves
programmer time.
As others have noted in the past and in at least one current thread,
in Common Lisp (the standard) there is no guarantee that tail call
optimisation will occur, which means that if your intention is to
write portable code, you may run into some difficulty. On the other
hand, as a CL programmer wanting to make use of this type of
optimisation, you would (a) use an implementation that does it, and
(b) make sure you know the relevant incantation to invoke it.
Seeing that such optimising Common Lisp implementations actually
exist, then it must be the case (one would reasonably assume) that the
feature exists because CL programmers sometimes make use of it.
In contrast to the Scheme flavour of Lisp, however, tail call
elimination in Common Lisp is an /optimising/ step that is taken after
writing actual working code. Depending on the implementation, there
may be special steps required to turn on the optimisation. In Scheme,
it is taken for granted that it will happen without any special
consideration by the programmer (beyond ensuring that the recursive
call really /is/ in the tail position).
All of this may be interesting, but I don't think it is of great
practical concern, at least not for beginning to intermediate CL
programmers. The danger, if any, may lie in a Schemer coming to Common
Lisp with the idea of using recursion for everything, and then
wondering why the stack gets blown CDRing down a million item list...
It will work in Scheme, but you may have to take special steps to have
it work in Common Lisp.
David Trudgett
--
I suggest a new strategy. Let the Wookie win.
> I think you were probably wondering about something that isn't true.
That happens more often than I'd like to admit.
> All of this may be interesting, but I don't think it is of great
> practical concern, at least not for beginning to intermediate CL
> programmers. The danger, if any, may lie in a Schemer coming to Common
> Lisp with the idea of using recursion for everything, and then
> wondering why the stack gets blown CDRing down a million item list...
> It will work in Scheme, but you may have to take special steps to have
> it work in Common Lisp.
Thanks. That is helpful to keep in mind. I didn't phrase my question
well. I was specifically wondering what the difference is between
using dolist or some other iteration-based function for list building
and the ML-style method of declaring a recursive function in the local
scope as well as an empty list and then running the recursive function
to build the list. For example,
(set 'foo '(some sort of list))
(let ((accum '()))
(labels ((iter (lst)
(cond
((null (car lst)) accum)
(t (progn
(push (car lst) accum)
(iter (cdr lst)))))))
(set 'bar (iter foo))))
While this is obviously contrived (it just copies list foo to list
bar), the basic idea is that there is a list that gets accumulated,
there is a locally defined iterator function that can be customized to
the exact needs of the programmer (i.e., should it return the value of
the accumulated list, etc.).
I think that most likely, dolist is much faster for iteration. But I
figured that in some situations, this would be an ideal solution. I
was just wondering if there was a specific reason not to do this.
Jeff wrote:
> (set 'foo '(some sort of list))
> (let ((accum '()))
> (labels ((iter (lst)
> (cond
> ((null (car lst)) accum)
> (t (progn
> (push (car lst) accum)
> (iter (cdr lst)))))))
> (set 'bar (iter foo))))
>
> While this is obviously contrived (it just copies list foo to list
> bar),
No, it doesn't.. it copies the reverse of a list.
Also, I don't think your use of an external accumulator (with
assignment) is really "ML-style", or functional style in any case. The
typical way to do this is like the following:
(labels ((iter (list accumulator)
(cond
((null list) (reverse accumulator))
(t (iter (cdr list) (cons (car list) accumulator))))))
(iter ... nil))
Jeff wrote:
>> I think you were probably wondering about something that isn't true.
>
> That happens more often than I'd like to admit.
>
>> All of this may be interesting, but I don't think it is of great
>> practical concern, at least not for beginning to intermediate CL
>> programmers. The danger, if any, may lie in a Schemer coming to Common
>> Lisp with the idea of using recursion for everything, and then
>> wondering why the stack gets blown CDRing down a million item list...
>> It will work in Scheme, but you may have to take special steps to have
>> it work in Common Lisp.
>
> Thanks. That is helpful to keep in mind. I didn't phrase my question
> well. I was specifically wondering what the difference is between
> using dolist or some other iteration-based function for list building
> and the ML-style method of declaring a recursive function in the local
> scope as well as an empty list and then running the recursive function
> to build the list. For example,
>
> (set 'foo '(some sort of list))
> (let ((accum '()))
> (labels ((iter (lst)
> (cond
> ((null (car lst)) accum)
> (t (progn
> (push (car lst) accum)
> (iter (cdr lst)))))))
> (set 'bar (iter foo))))
>
> While this is obviously contrived (it just copies list foo to list
> bar), the basic idea is that there is a list that gets accumulated,
> there is a locally defined iterator function that can be customized to
> the exact needs of the programmer (i.e., should it return the value of
> the accumulated list, etc.).
>
> I think that most likely, dolist is much faster for iteration. But I
> figured that in some situations, this would be an ideal solution. I
> was just wondering if there was a specific reason not to do this.
By itself, using recursive versions of algorithms doesn't buy you a lot,
especially not if you use side effects inside the recursively defined
functions.
What is interesting about a functional programming style is that if you
don't use any side effects (or any other effects), you can be sure that
for every set of concrete parameters, a function will always return the
same result. This makes it easier to prove properties about such
functions. If you use iterative constructs, you use side effects, so
that makes such proofs harder.
To be able to express iterations without using side effects, you have to
resort to recursive function definitions to keep the definitions
effect-free. When you define a function recursively, you need a base
case (in your code the test for the empty list), and a general case (if
the list is not empty). This gives you a natural way of proving
properties via induction.
If you don't need to (formally) prove properties of your programs, you
can ignore such considerations - then iteration constructs are typically
easier to read.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> What is interesting about a functional programming style is that if you
> don't use any side effects (or any other effects), you can be sure that
> for every set of concrete parameters, a function will always return the
> same result. This makes it easier to prove properties about such
> functions. If you use iterative constructs, you use side effects, so
> that makes such proofs harder.
There is another interesting thing about a functional programming
style. It parallelizes with no need for locks and mutexes. If I
were given the task of getting a system working and using the full
benefit of a thousand-CPU (or billion-CPU) supercomputer, I would
immediately start using as absolutely pure a functional programming
style as I could.
It's my opinion that we're going to be forced to functional coding
eventually in order to take full advantage of ridiculously large
multiprocessing computer systems.
Bear
Ray Dillinger wrote:
> Pascal Costanza wrote:
>
>> What is interesting about a functional programming style is that if
>> you don't use any side effects (or any other effects), you can be sure
>> that for every set of concrete parameters, a function will always
>> return the same result. This makes it easier to prove properties about
>> such functions. If you use iterative constructs, you use side effects,
>> so that makes such proofs harder.
>
> There is another interesting thing about a functional programming
> style. It parallelizes with no need for locks and mutexes. If I
> were given the task of getting a system working and using the full
> benefit of a thousand-CPU (or billion-CPU) supercomputer, I would
> immediately start using as absolutely pure a functional programming
> style as I could.
>
> It's my opinion that we're going to be forced to functional coding
> eventually in order to take full advantage of ridiculously large
> multiprocessing computer systems.
I am not convinced that this scales.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Ray Dillinger <····@sonic.net> writes:
> It's my opinion that we're going to be forced to functional coding
> eventually in order to take full advantage of ridiculously large
> multiprocessing computer systems.
Oh, absolutely.
Distributed processing could never work usefully using autonomous,
stateful, distributed entities communicating in an ad hoc way, or even
a formal way that involved more description than today's functional
programming languages.
For example, the internet is made up of a ridiculously large number of
multiprocessing computer systems, and it is ONLY able to survive because
it uses a pure-functional state model with no side-effects. That was
the only tractable way to get the whole thing bootstrapped and we were
lucky to have it.
Now, having said that, we all know what that means: let's all just
serialize ourselves for transport yet again while archive.org makes
room on their disks for the new Internet state object that results
from my having posted this message.
"Give me a place to store and synchronize all the intermediate data,
and I will move the world with functional programming."
--Kent Pitman (with apologizes to Archimedes)
Kent M Pitman wrote:
> Ray Dillinger <····@sonic.net> writes:
>
>
>>It's my opinion that we're going to be forced to functional coding
>>eventually in order to take full advantage of ridiculously large
>>multiprocessing computer systems.
>
>
> Oh, absolutely.
>
> Distributed processing could never work usefully using autonomous,
> stateful, distributed entities communicating in an ad hoc way, or even
> a formal way that involved more description than today's functional
> programming languages.
True sarcasm, or just bait?
Hmmm. Separate problem spaces, in my mind. Network programming
does work fine in an agent-based model where you have a lot of
semi-autonomous agents making local side effects on local machines,
working for various different interests by executing different
programs with different objectives. Cooperation between processes
is for mutual self-interest.
It eventually becomes very similar to an ecological problem, and
the main difficulty is making sure network integrity never depends
on folk hosting on their own machinery a program whose operation is
inimical to their own interests (because then they'll just shut
it down, natch).
But parallel computing is where a single interest has a bunch of
CPUs and a single problem and a single program and wants to get a
good answer as fast as possible. And functional (stateless)
programming absolutely blows the pants off of any model where you
have to keep track of mutexes and locks and side effects and etc.
> Now, having said that, we all know what that means: let's all just
> serialize ourselves for transport yet again while archive.org makes
> room on their disks for the new Internet state object that results
> from my having posted this message.
Ergh. Gods, no. That whole 'global state' crap is exactly
what I'm talking about trying to avoid. It's not the best
use of functional programming to try to simulate sequential
mutation programming models. You can do it, but it's a mismatch
between problem requirements and solution technique, like
welding a bulldozer blade on a mercedes.
> "Give me a place to store and synchronize all the intermediate data,
> and I will move the world with functional programming."
> --Kent Pitman (with apologizes to Archimedes)
Riiight. a place to store and synchronize all intermediate data with
instantaneous infinite-bandwidth connectivity to every node in the
billion-CPU computronium substrate.
Bear
Ray Dillinger <····@sonic.net> writes:
> Kent M Pitman wrote:
> > Ray Dillinger <····@sonic.net> writes:
> >
> >>It's my opinion that we're going to be forced to functional coding
> >>eventually in order to take full advantage of ridiculously large
> >>multiprocessing computer systems.
> > Oh, absolutely. Distributed processing could never work usefully
> > using autonomous,
> > stateful, distributed entities communicating in an ad hoc way, or even
> > a formal way that involved more description than today's functional
> > programming languages.
>
> True sarcasm, or just bait?
In some vague form, I suppose the latter, though I wouldn't have
phrased it that way. I was only intending some light-hearted fun. To
the extent it provoked you into responding in more detail, though, I
enjoyed your analysis even if I disagree with some of your conclusions
(as hopefully explained below).
Incidentally, I don't dispute that functional programming is a
possible and useful paradigm for addressing the issues you raise. I
only got into this because of your use of the word "forced" ... which
seems to me to imply "there will be no other choice of how to
proceed".
(Then again, force is sometimes--some might say always, but I'll be
generous--attempted for political, not technical reasons. So if that
was the kind of force you meant, I guess I can't say it won't happen.)
> But parallel computing is where a single interest has a bunch of
> CPUs and a single problem and a single program and wants to get a
> good answer as fast as possible. And functional (stateless)
> programming absolutely blows the pants off of any model where you
> have to keep track of mutexes and locks and side effects and etc.
Well, there is such a heap of assumptions in here that I don't know
where to begin. Just off the top of my head though, without a lot of
careful thought, here are a couple of questions for you:
If functional programming can represent processes that are stateful
without becoming expensive, then why does my surface language have to
be functional and why isn't this just built into the back end of the
language. Or, taking the other side, if functional programming cannot
represent stateful situations, then how can I be sure the world (which
is made up largely of stateful situations) can be properly and
efficiently modeled in all the ways I require of my programming
languages?
The easiest example I can see is a state machine full of GO's. It's
entirely possible to write that as GO's or as pure-functional,
elegantly tail-called functions in Scheme--the difference is only a
matter of syntax. But that implies that if there is something yucky
about it from the point of view of making it parallel, it's not about
the formalism (since I can choose either) but about the coding style.
Requiring everyone to program functionally will not suddenly clean up
everyone's coding style. I'm sure one can still box oneself in. And
the first day you make functional programming required for all will be
the first day people start making a FORTRAN compatibility package in
that functional language, I suspect.
I don't doubt that functional programming, as a paradigm, can be
useful. I use it all the time in Lisp. But not to the exclusion of
all else. So if all you're saying is that there are places functional
computations are useful, you're not saying much different than what is
true now. If what you mean is "to the exclusion of all else", then
I'm dubious. I don't see us being forced into it because I expect
people will want and need to go back and forth among paradigms. Which
is already the present state of affairs.
Kent M Pitman wrote:
> The easiest example I can see is a state machine full of GO's. It's
> entirely possible to write that as GO's or as pure-functional,
> elegantly tail-called functions in Scheme--the difference is only a
> matter of syntax. But that implies that if there is something yucky
> about it from the point of view of making it parallel, it's not about
> the formalism (since I can choose either) but about the coding style.
No, coding style is just a surface issue. I really am not talking
about such things as how control flow is expressed, although I
greatly prefer tail-calls in my own code.
The important thing is that if the algorithm can be written in
such a way as to not rely on mutation, then we suddenly no longer
have update-propagation and cache coherency issues.
Bear
On 2007-10-12 03:56:26 -0400, Ray Dillinger <····@sonic.net> said:
> if the algorithm can be written in
> such a way as to not rely on mutation, then we suddenly no longer
> have update-propagation and cache coherency issues
I think that part of Kent's point is that some algorithms that do not
rely on mutation of their arguments do so by copying them. When the
data they take as args get large this copying can be a significant
bottleneck.
Ray Dillinger <····@sonic.net> writes:
> The important thing is that if the algorithm can be written in
> such a way as to not rely on mutation, then we suddenly no longer
> have update-propagation and cache coherency issues.
A big if, of course.
This vaguely implies that it won't be economical for us to be doing all
calculations that way.
Kent M Pitman wrote:
> Ray Dillinger <····@sonic.net> writes:
>
>
>>The important thing is that if the algorithm can be written in
>>such a way as to not rely on mutation, then we suddenly no longer
>>have update-propagation and cache coherency issues.
>
>
> A big if, of course.
>
> This vaguely implies that it won't be economical for us to be doing all
> calculations that way.
True. "All calculations" is such a large thing.
Okay, how about this expression of my speculation:
I think that the subset of calculations for which we can get
>90% CPU utilization on in large multiprocessing systems
with a global store will be the same subset of calculations
for which we can write algorithms that don't need global
update-propagation and cache coherency.
There's another large class of highly parallelizable algorithms,
but that's for hardware specialized to have distributed stores
per CPU and direct (lock-free) communications between "neighboring"
CPUs (which is how a lot of Digital Signal Processors work, now
that I think about it).
Bear
On Wed, 10 Oct 2007 19:34:36 -0700, Ray Dillinger <····@sonic.net>
wrote:
>... parallel computing is where a single interest has a bunch of
>CPUs and a single problem and a single program and wants to get a
>good answer as fast as possible. And functional (stateless)
>programming absolutely blows the pants off of any model where you
>have to keep track of mutexes and locks and side effects and etc.
But functional languages still have the state, and parallel FPLs have
the locks as well ... they just try hard to hide it all from the
programmer. There is also the fact that the world, in general, is
stateful, and modeling and interacting with it is also. Kent's reply
touched on both of these points also.
So far, the current crop of parallel (or parallelizable) FPLs don't
scale particularly well. The grain size of the problem matters
significantly as do computation dependencies. Too fine a grain or too
many dependencies and program run time is overwhelmed by thread
management (where "thread" generically means an execution path, not a
runtime or system feature).
I've been thinking about how I would design a runtime to exploit fine
grain parallelism for quite a while. I'm certain the answer will
involve immutable data, but I don't think any of the current FPL
runtime models are the proper base - many current implementations are
actually hostile to fine grain parallelism. As I said previously in
some discussion of parallelization (might have been in c.l.f), my
current thinking is that the right approach involves predicated
micro-threading and a state machine approach to the runtime. I'm
(very) slowly working on a prototype.
George
--
for email reply remove "/" from address
On Oct 11, 2:52 pm, George Neuner <·········@/comcast.net> wrote:
> I've been thinking about how I would design a runtime to exploit fine
> grain parallelism for quite a while. I'm certain the answer will
> involve immutable data, but I don't think any of the current FPL
> runtime models are the proper base - many current implementations are
> actually hostile to fine grain parallelism. As I said previously in
> some discussion of parallelization (might have been in c.l.f), my
> current thinking is that the right approach involves predicated
> micro-threading and a state machine approach to the runtime. I'm
> (very) slowly working on a prototype.
Have you taken a look at the Cilk runtime / compiler? The Cilk
developers have managed to get the overhead of parallelism quite
low, and also can exploit task locality. They achieve this in
part by sacrificing some programming flexibility (you only get
a fork and join model of task parallelism -- no futures or the
like), which also gives them bounds on the stack size.
I'm very much interested in languages and runtimes of this sort,
and would like to contribute to or at least advise such a project.
mfh
On Tue, 16 Oct 2007 11:37:57 -0700, "Mark H." <············@gmail.com>
wrote:
>On Oct 11, 2:52 pm, George Neuner <·········@/comcast.net> wrote:
>> I've been thinking about how I would design a runtime to exploit fine
>> grain parallelism for quite a while. I'm certain the answer will
>> involve immutable data, but I don't think any of the current FPL
>> runtime models are the proper base - many current implementations are
>> actually hostile to fine grain parallelism. As I said previously in
>> some discussion of parallelization (might have been in c.l.f), my
>> current thinking is that the right approach involves predicated
>> micro-threading and a state machine approach to the runtime. I'm
>> (very) slowly working on a prototype.
>
>Have you taken a look at the Cilk runtime / compiler? The Cilk
>developers have managed to get the overhead of parallelism quite
>low, and also can exploit task locality. They achieve this in
>part by sacrificing some programming flexibility (you only get
>a fork and join model of task parallelism -- no futures or the
>like), which also gives them bounds on the stack size.
Yes. Fork/join can be quite lightweight in a shared memory
environment, but it doesn't scale well to distributed memory systems.
I'm interested in supporting both models.
I have looked at Cilk - its thread DAG approach is very similar to the
way I would do it. The 2 level scheduler is also similar to my
approach, but IMO it is heavyweight and could be simplified and sped
up significantly (even for Cilk).
The problem with Cilk, at least from the point of view of this
discussion, is that the language (an extension to C) doesn't do
anything to expose parallelism: it is up to the programmer to identify
it and arrange for mutual exclusion where necessary. In addition,
Cilk's parallelism is fixed: the compiler slices the program rather
than allowing the runtime to adapt it in situ (the runtime does allow
migration, but the number of processors is fixed at compile time).
Cilk is also predicated towards programs with lots of independent
computations - most programs perform highly dependent computations
where opportunities for parallel execution are hidden.
IMO, starting from a functional (or mostly functional) language will
provide a better base for an automatic parallelizer.
>I'm very much interested in languages and runtimes of this sort,
>and would like to contribute to or at least advise such a project.
Well, I have a day job and so this project is low priority. There's a
lot of work yet to be done even to get to alpha status. I'm happy to
keep people apprised of progress and to discuss any topic related to
it, but it will probably be sometime next year before I have enough
code in place to know if I might be on to something or am just wasting
time.
George
--
for email reply remove "/" from address
David Trudgett <·········@yahoo.com> wrote:
+---------------
| There is nothing elegant about using recursion to do non-recursive
| tasks, when there are better tools to hand. Minimalism as per the
| Scheme credo is not the only kind of elegance, although Scheme is
| really quite neat in its own way. For instance, it's cool to be able
| to write stuff like:
|
| ((generate-operation x y z) arg1 arg2 arg3 arg4)
+---------------
You can do that in CL too with only one more token:
(funcall (generate-operation x y z) arg1 arg2 arg3 arg4)
To me the elegance of that is in the dynamically-generated closure,
*not* in being able to write function calls in the Scheme way per se.
+---------------
| ...although I am not sure of the extent of the practical advantage
| to being able to write things like that.
+---------------
Any number of cases where GENERATE-OPERATION might do some sort
of expensive pre-computation, the results of which are then cached
in the returned closure for use multiple times, e.g.:
(mapcar (generate-operation x y z) sequence1 sequence2 sequence3)
(remove-if-not (generate-operation x y z) sequence)
And the classic case: GENERATE-OPERATION compiles a pattern
specified at runtime into an optimized match routine, which is
then used many times when scanning the lines of a large file, e.g.,
<http://weitz.de/cl-ppcre/#create-scanner2> followed by using the
result in a loop with <http://weitz.de/cl-ppcre/#scan>, or the like.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
>
> > (reverse '(some sort of list))
You're being a bit wasteful with CPU cycles, aren't you? A little
static code analysis reveals that the following achieves the correct
output with fewer compute resources:
'(list of sort some) => (LIST OF SORT SOME)
David
--
These are not the droids you are looking for. Move along.
Jeff wrote:
> Why doesn't anyone use a lambda in a let block to build lists? Is
> that not good practice?
>
> (let ((accum '())
> (foo (lambda (n)
> (cond ((nullp n) nil)
> (t (push (car n) accum)
> (foo (cdr n)))))))
>
> (foo '(some sort of list)))
Indentation errors fixed....
Ergh. EuLisp? That's a dialect we don't see much of here.
Argument order of push is reversed from CL standard and most
scheme implementations, but correct (I think?) for Eulisp.
Nullp, car and cdr with the same semantics as in CL, let with
the same semantics as in scheme, lexical scope as a default
and no separate function namespace. Do I remember these
things correctly? Whatever: most other assumptions make the
above code bugged.
I think it's bad practice, for three reasons. Firstly, it's
unnecessarily complex. Secondly, lexical scoping makes this
function (which appears to be intended as a widely used utility)
unavailable outside the let form (because let in Eulisp doesn't
establish top-level bindings; instead it establishes bindings
within its own scope, as in Scheme). Thirdly, the result
(accum) is available in that same scope but built by side
effects and never actually returned, which makes the interface
for the function foo nonstandard and unexpected.
Bear
David Golden wrote:
> David Trudgett wrote:
>>
>> Is there any advantage to using ITERATE (and/or SERIES) instead of
>> LOOP?
>
> Iterate:
>
<snip>
>
> Series:
>
<snip>
Thanks for the information, David and Steven. I spent some time this
afternoon reading through some of the doc for ITERATE, which looks
interesting. Haven't got to SERIES, yet, but I did watch the two SICP
videos[*] on streams recently, so at the moment I am thinking of
SERIES as a Common Lispy implementation of that idea.
Looks like a couple of extra bits to add to the toolbox!
Thanks,
David
[*] Lectures 6a and 6b. See:
http://www.swiss.ai.mit.edu/classes/6.001/abelson-sussman-lectures/
--
These are not the droids you are looking for. Move along.
Matthias Buelow <···@incubus.de> writes:
> Erik R. wrote:
>
> > Sounds like the loop macro is a 'must learn' feature of common lisp.
>
> Just like vomitting is a "must learn" feature of drinking.
I suppose there's some truth to that, but at the risk of losing your moment
of humor, I think this is still overly harsh and risks dissuading people
from thinking it's ok to use LOOP.
There are some things about LOOP that are syntactically different than
other parts of the language, and if I were choosing the syntax, I
might have done it differently, but the syntax has been in wide use
for a long time and is heavily tested. All in all, I think the
benefits strongly outweigh the costs, and one should not be dissuaded
by talk of vomiting.
Decades ago, I was an early detractor of LOOP and strongly advocated
DO, but the redesign of it for CL eliminated most of my major concerns
(even though it also, lamentably, lost some functionality in the
process--like extensibility) and, as a side-effect, made much more easy
for me to decide on a case-by-case basis that the good features
really strongly outweigh the bad.
I'm not religious about my use of LOOP but I no longer try to stop
myself on some purist grounds. As a matter of statistics, I use CL's
LOOP routinely these days when a simple DOLIST or DOTIMES isn't
enough. I rarely use DO any more. And I find my code to be generally
far more readable (not just by me, but I suspect by a casual reader
looking on) than it ever was using DO, even for as "pure" as DO is
[it's intended to be essentially more-easily-compiler-recognizable
syntactic sugar for tail calling self (i.e., looping)]. Indeed, I
think one of the main reasons I do not use DO is that it is _not_
really accessible to casual readers because you have to examine the
entire data flow to guess what the basic paradigm is, while it's dead
easy looking at most properly written LOOP expressions to see which
are filters, which are just doing side-effect, what type of return
value there is, etc.
I think it's still the case that the temptation is to think of LOOP as
English and something you don't have to program. It therefore appeals
to users a little ahead of when they are ready to use it, and really
it is something one has to know a fair bit about to use. But even so,
I think it's something people should be taught and should use without
shame when, like with all programs, the program says what it means in
a way that is easily accessible.
Loops like:
(loop for x below 10 collect x)
(loop for x in '(3 5 7)
for y in '(2 5 8)
when (= x y)
collect (cons x y))
(defun lookup (key table)
(loop for (ind val) in table
when (eq key ind)
return val))
are examples of loops that are really quite clear and nothing to be seeking
more complicated ways to say just to prove they can do it a more "lispy" way.
To be "lispy" is NOT to "seek the obscure".
Sadly, too, LOOP seems to never get taught in classes, so it's the
perfect construct to use in responding to newbies when one is not sure
if they're accidentally doing their homework. There seems about zero
risk that a teacher would ever accept a LOOP as the right answer, and
yet the LOOP often perfectly expresses what a serious programmer needs
to solve a problem.
Kent M Pitman wrote:
> Matthias Buelow <···@incubus.de> writes:
>
>> Erik R. wrote:
>>
>>> Sounds like the loop macro is a 'must learn' feature of common lisp.
>> Just like vomitting is a "must learn" feature of drinking.
That's silly. CL LOOP is indeed nice and it took me a little walk
through another (imperative) programming language to come to appreciate
its power and elegance.
>
> I suppose there's some truth to that, but at the risk of losing your moment
> of humor, I think this is still overly harsh and risks dissuading people
> from thinking it's ok to use LOOP.
>
> There are some things about LOOP that are syntactically different than
> other parts of the language, and if I were choosing the syntax, I
> might have done it differently, but the syntax has been in wide use
> for a long time and is heavily tested. All in all, I think the
> benefits strongly outweigh the costs, and one should not be dissuaded
> by talk of vomiting.
>
> Decades ago, I was an early detractor of LOOP and strongly advocated
> DO, but the redesign of it for CL eliminated most of my major concerns
> (even though it also, lamentably, lost some functionality in the
> process--like extensibility) and, as a side-effect, made much more easy
> for me to decide on a case-by-case basis that the good features
> really strongly outweigh the bad.
>
> I'm not religious about my use of LOOP but I no longer try to stop
> myself on some purist grounds. As a matter of statistics, I use CL's
> LOOP routinely these days when a simple DOLIST or DOTIMES isn't
> enough. I rarely use DO any more. And I find my code to be generally
> far more readable (not just by me, but I suspect by a casual reader
> looking on) than it ever was using DO, even for as "pure" as DO is
> [it's intended to be essentially more-easily-compiler-recognizable
> syntactic sugar for tail calling self (i.e., looping)]. Indeed, I
> think one of the main reasons I do not use DO is that it is _not_
> really accessible to casual readers because you have to examine the
> entire data flow to guess what the basic paradigm is, while it's dead
> easy looking at most properly written LOOP expressions to see which
> are filters, which are just doing side-effect, what type of return
> value there is, etc.
>
> I think it's still the case that the temptation is to think of LOOP as
> English and something you don't have to program. It therefore appeals
> to users a little ahead of when they are ready to use it, and really
> it is something one has to know a fair bit about to use. But even so,
> I think it's something people should be taught and should use without
> shame when, like with all programs, the program says what it means in
> a way that is easily accessible.
Seeing LOOP as english gibberish, or more precisely some read-only
construct, was my reading of it until I started to practice Python (I
program in it for a living) and its looping constructs (instead of
*merely* reading lisp code, to be fair). That helped tremendously. Also
one nice thing about python's iteration protocol is that it's easily
extended, but it seems like something is being cooked these days, based
on work by Christophe Rhodes related to extensible sequences for CL.
Whatever. I still stare at DO forms with despair but now loops are
indeed so easily parsed.
>
> Loops like:
>
> (loop for x below 10 collect x)
range(10)
>
> (loop for x in '(3 5 7)
> for y in '(2 5 8)
> when (= x y)
> collect (cons x y))
>
[(x, y) for x, y in zip([3,5,7], [2,5,8])
if x == y]
> (defun lookup (key table)
> (loop for (ind val) in table
> when (eq key ind)
> return val))
def lookup (key, table):
for ind, val in table.iteritems():
if key == ind: return val
there are some differences there under the hood, esp. when it comes to
sequences, python's lists are really vectors ; the table argument in
python should be a mapping, but that is not important
I noticed however that CL's LOOP does loop *across* vectors, not *in*
them, and that is probably (I can only guess) some optimization problem
(or design choice wrt performance), also related to the inextensibility
of LOOP wrt generalized sequences.
>
> are examples of loops that are really quite clear and nothing to be seeking
> more complicated ways to say just to prove they can do it a more "lispy" way.
> To be "lispy" is NOT to "seek the obscure".
>
> Sadly, too, LOOP seems to never get taught in classes, so it's the
> perfect construct to use in responding to newbies when one is not sure
> if they're accidentally doing their homework. There seems about zero
> risk that a teacher would ever accept a LOOP as the right answer, and
> yet the LOOP often perfectly expresses what a serious programmer needs
> to solve a problem.
Iteration protocol is one of the great points/pleasures of Python, and,
now seeing how LOOP (and ancestors) invented it decades ago, I can't but
agree with your lamentation.
Confusedly yours,
Aur�lien.
Aur�lien Camp�as <·························@free.fr> wrote:
+---------------
| I noticed however that CL's LOOP does loop *across* vectors, not *in*
| them, and that is probably (I can only guess) some optimization problem
| (or design choice wrt performance), also related to the inextensibility
| of LOOP wrt generalized sequences.
+---------------
I suspect it's more that the authors didn't want to have to always
provide for selecting the iteration method at *runtime*, instead of
simply making the selection at macroexpansion time from the syntax.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Aur�lien Camp�as wrote:
> CL LOOP is indeed nice and it took me a little walk
> through another (imperative) programming language to come to appreciate
> its power and elegance.
I don't like Python either.
From: Robert Maas, see http://tinyurl.com/uh3t
Subject: Re: Multivalue tail recursion?
Date:
Message-ID: <rem-2007oct11-002@yahoo.com>
> > Sounds like the loop macro is a 'must learn' feature of common lisp.
> From: Matthias Buelow <····@incubus.de>
> Just like vomitting is a "must learn" feature of drinking.
It sounds like you like the loop macro about as much as Jay Leno
likes a certain movie star who got arrested for DUI several times.
Tonight's joke about her (from the cover of her worst-selling book):
- Drink
- Drive
- Repeat
Adapting that, here's how she would program using Lisp:
Pseudocode (adapted from the cover of her worst-selling book):
- Loop
- Vomit
- Repeat
Actual code:
(loop (vomit))
Frode Vatvedt Fjeld wrote:
> "Erik R." <·············@gmail.com> writes:
>
>
>>(defun first-n (n list)
>> "Splits the list after the first n elements"
>> (if (= 0 n)
>> (values '() list)
>> (multiple-value-bind (from-front rest) (first-n (1- n) (rest
>>list))
>> (values (cons (first list) from-front) rest))))
>>
>>So my question is this: does this count as tail recursion?
>
>
> No, you'd have to use an accumulator to make this tail recursive.
>
>
>>The actual "last operation" of the function is just repackaging the
>>values returned from the recursive call. Can lisp's compiler
>>optimize this into a loop?
>
>
> In theory of course the compiler can make any program into any
> functional equivalent. But in practice I doubt it very much. And what
> would be the point of haing the compiler de-obfuscate your code,
> really? If you want it to be a loop, it's better for everybody to
> write a loop:
>
> (values (loop repeat n collect (pop list))
> list)
>
> which should be equivalent to
>
> (values (subseq list 0 n)
> (nthcdr n list))
Ah, good point, no need to copy the rest of the list.
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
+ "Erik R." <·············@gmail.com>:
> Anyway, I whipped one up in a few lines that not only pulls n items
> off the list, but it returns the remaining items as well. Let me know
> what you think. I was kind of surprised that I was able to do it
> without the use of an accumulator parameter.
>
> (defun first-n (n list)
> "Splits the list after the first n elements"
> (if (= 0 n)
> (values '() list)
> (multiple-value-bind (from-front rest) (first-n (1- n) (rest
> list))
> (values (cons (first list) from-front) rest))))
I would probably do something like this instead:
(defun first-n (n list)
(loop for i below n for (a . d) on list
collect a into x
finally (return (values x d))))
> So my question is this: does this count as tail recursion? The
> actual "last operation" of the function is just repackaging the
> values returned from the recursive call.
No. �Just repackaging� is not little enough to make it tail
recursive. �Just returning the value of the recursive call� is the
only thing that qualifies.
In any case, in Common Lisp you cannot rely on the compiler to
eliminate tail calls. Some compilers may do it, depending on
appropriate declarations - (DEBUG 0) comes to mind, since tail call
eliminition really plays havoc with your ability to debug program.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
Harald Hanche-Olsen wrote:
> + "Erik R." <·············@gmail.com>:
>
>
>>Anyway, I whipped one up in a few lines that not only pulls n items
>>off the list, but it returns the remaining items as well. Let me know
>>what you think. I was kind of surprised that I was able to do it
>>without the use of an accumulator parameter.
>>
>>(defun first-n (n list)
>> "Splits the list after the first n elements"
>> (if (= 0 n)
>> (values '() list)
>> (multiple-value-bind (from-front rest) (first-n (1- n) (rest
>>list))
>> (values (cons (first list) from-front) rest))))
>
>
> I would probably do something like this instead:
>
> (defun first-n (n list)
> (loop for i below n for (a . d) on list
> collect a into x
> finally (return (values x d))))
Niiiiiiice.
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut