Hello,
Doees anybody knows, what is better
to use in LISP, recursion or interation...??
(in situation when you can use both)
Thanks in advance, Robert...!!!
Robert Bralic WROTE:
> Hello,
>
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
>
> Thanks in advance, Robert...!!!
It depends on your LISP implement. If your Lisp offers shallow stack
space for
recursion , very offen your job will burn out that stack space if you
code in recursion.
But recursion got its convenience , eg it's more expressive than the
iterative one.
For iteration , I am too stupid to remember those complicative
operators and their
syntax , eg do , dotimes , dolist ... I am so simple minded that I only
learned loop
plus conditions . And I am so foolished that I only learned "cond" for
conditioning.
I am very stupid but my codes still work. You can see :
http://groups.google.com.tw/group/comp.lang.lisp/msg/46338401c260b19c?dmode=source&hl=zh-TW
I hope you all enjoy that !!
··········@bbs.ee.ncu.edu.tw wrote:
> Robert Bralic WROTE:
>
>>Hello,
>>
>>Doees anybody knows, what is better
>>to use in LISP, recursion or interation...??
>>(in situation when you can use both)
Always use the approach that makes your code better understandable. If
you are uncertain about this, try both and then stick to the one that
suits the problem better. Over time, you will gain more experience in
making that decision faster.
> It depends on your LISP implement. If your Lisp offers shallow stack
> space for
> recursion , very offen your job will burn out that stack space if you
> code in recursion.
That's wrong. There is a danger that stack runs out of space, but that
doesn't necessarily mean that it will happen often.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
··········@bbs.ee.ncu.edu.tw writes:
> I am very stupid but my codes still work. You can see :
> http://groups.google.com.tw/group/comp.lang.lisp/msg/46338401c260b19c?dmode=source&hl=zh-TW
"C/C++/Java/Perl/etc are for people who want to make things that work.
Common Lisp is for people who want to make things that don't break."
- Erik Naggum
:)
On 2005-11-18 08:09:41, Robert Bralic wrote:
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
Depends on the LISP you use and your definition of better.
Robert Bralic wrote:
> Hello,
>
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
Iteration. Recursion is cool (even for iteration), but if you are
iterating, use iteration constructs in the language.
--
Kenny
Why Lisp? http://wiki.alu.org/RtL_Highlight_Film
"I've wrestled with reality for 35 years, Doctor, and I'm happy to state
I finally won out over it."
Elwood P. Dowd, "Harvey", 1950
Robert Bralic wrote:
> Hello,
>
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
>
> Thanks in advance, Robert...!!!
Since no one has (expressly) mentioned it yet, what about this
guideline (in HTDP, among others):
Use iteration for linear data structures, use recursion for nested data
structures.
In other words, if you're processing a list used as a linear list, use
dolist.
If you're processing a list used as a tree, recur on the car and cdr.
·············@gmail.com wrote:
> Robert Bralic wrote:
>
>>Hello,
>>
>>Doees anybody knows, what is better
>>to use in LISP, recursion or interation...??
>>(in situation when you can use both)
>>
>>Thanks in advance, Robert...!!!
>
> Since no one has (expressly) mentioned it yet, what about this
> guideline (in HTDP, among others):
> Use iteration for linear data structures, use recursion for nested data
> structures.
Two counter examples:
- In http://groups.google.com/group/comp.lang.lisp/msg/60353ea473b7493e
I have implemented a function 'collect-blobs which I found easier to
express with recursion than with iteration, although it traverses a
linear list.
- If you are traversing a binary tree, but are only every interested in
the right branches, you might as well use iteration instead of recursion.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> ·············@gmail.com wrote:
> > Robert Bralic wrote:
> >>Doees anybody knows, what is better
> >>to use in LISP, recursion or interation...??
> >>(in situation when you can use both)
One nice thing that functional programming perhaps more easily allows
is memoization. So go ahead and write the e-z implementation of
fibonacci and memoize the sucker.
And compiler macros work with functions too, if partial evaluation is
useful. Or a compiler macro can hide the messiness of sticking in a
call to Binet's fibonacci formula for small numbers.
Though you know, I very rarely use recursion in normal coding.
> > Since no one has (expressly) mentioned it yet, what about this
> > guideline (in HTDP, among others):
> > Use iteration for linear data structures, use recursion for nested data
> > structures.
>
> Two counter examples:
>
> - In http://groups.google.com/group/comp.lang.lisp/msg/60353ea473b7493e
> I have implemented a function 'collect-blobs which I found easier to
> express with recursion than with iteration, although it traverses a
> linear list.
>
> - If you are traversing a binary tree, but are only every interested in
> the right branches, you might as well use iteration instead of recursion.
What I'd like to see is if there's an example where tail-recursive
style is clearer than the alternative. ;)
Tayssir
--
"All human beings, whatever their position in society, are suffering
from this process of deterioration. Unknowingly prisoners of their own
egotism, they feel insecure, lonely, and deprived of the naive, simple,
and unsophisticated enjoyment of life."
-- Albert Einstein, 1949
Tayssir John Gabbour wrote:
> What I'd like to see is if there's an example where tail-recursive
> style is clearer than the alternative. ;)
(defun gcd (n m)
(if (zerop m)
n
(gcd m (mod n m))))
To me it's clearer than
(defun gcd (n m)
(loop while (/= m 0) do
(psetf n m
m (mod n m))
finally (return n)))
What do you think?
Patrick
Patrick Frankenberger wrote:
> Tayssir John Gabbour wrote:
> > What I'd like to see is if there's an example where tail-recursive
> > style is clearer than the alternative. ;)
>
> (defun gcd (n m)
> (if (zerop m)
> n
> (gcd m (mod n m))))
>
> To me it's clearer than
>
> (defun gcd (n m)
> (loop while (/= m 0) do
> (psetf n m
> m (mod n m))
> finally (return n)))
>
> What do you think?
Well, we shouldn't ignore the definition I gave in my previous post,
which took 0 lines.
http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_gcd.html
;)
But I wasn't at all precise. I meant clearer than a reasonable
recursive alternative. Of course there are cases where a tail-recursive
style is the natural one which you write immediately. But in others...
rewriting recursions into that style, to gain the optimization
benefits, is (in my view) often less readable.
And LOOP has its flaws, like above where (I believe) FOR won't act like
LET. So you end up doing something like:
(defun my-gcd (n1 n2)
(loop for num1 = n1 then num2
and num2 = n2 then (mod num1 num2)
until (zerop num2)
finally (return num1)))
Tayssir
Pascal Costanza wrote:
> - In
> http://groups.google.com/group/comp.lang.lisp/msg/60353ea473b7493e I
> have implemented a function 'collect-blobs which I found easier to
> express with recursion than with iteration, although it traverses a
> linear list.
Pascal's function was:
(defun collect-blobs (methods blob blobs)
(cond
((null methods)
(if blob (cons (nreverse blob) blobs) blobs))
((null blob)
(collect-blobs (cdr methods) (list (car methods)) blobs))
((betap (car methods))
(collect-blobs methods () (cons (nreverse blob) blobs)))
and is always called (other than by itself) with empty lists
for the second and third arguments. What it then does, if I
haven't misread, is to group METHODS into runs by putting a
run-boundary immediately before each method satisfying BETAP.
Perhaps it was easier to *write* recursively, but I think it
would have been easier to read like this:
(defun collect-blobs (methods)
(let ((blobs (list ())))
(flet ((complete-blob ()
(when (first blobs)
(setf blobs (list* () (nreverse (first blobs)) (rest blobs))))))
(loop for method in methods do
(when (betap method) (complete-blob))
(push method (first blobs)))
(complete-blob))
(nreverse (rest blobs))))
or -- a little longer but possibly more efficient and certainly
clearer --
(defun collect-blobs (methods)
(let ((complete-runs nil)
(current-run nil))
(flet ((complete-run ()
(when current-run
(push (nreverse current-run) complete-runs)
(setf current-run nil))))
(loop for method in methods do
(when (betap method) (complete-run))
(push method current-run))
(complete-run))
(nreverse complete-runs)))
Even the obvious near-mechanical transformation of your code
seems to me preferable to the original:
(defun collect-blobs (methods)
(let ((blob nil)
(blobs nil))
(loop
(cond
((null methods)
(return (if blob (cons (nreverse blob) blobs)
blobs)))
((null blob)
(setf blob (list (first methods))
methods (rest methods)))
((betap (car methods))
(setf blobs (cons (nreverse blob) blobs)
blob () ))))))
Better still with the renaming proposed in my second
version.
I suspect that the recursive version will seem preferable
only to people who have written a whole lot of list-processing
functions in tail-recursive form without any particular
reason for doing so, and have thereby become familiar with
the idiom. :-)
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Pascal Costanza wrote:
>
>
>>- In
>>http://groups.google.com/group/comp.lang.lisp/msg/60353ea473b7493e I
>>have implemented a function 'collect-blobs which I found easier to
>>express with recursion than with iteration, although it traverses a
>>linear list.
>
>
> Pascal's function was:
>
> (defun collect-blobs (methods blob blobs)
> (cond
> ((null methods)
> (if blob (cons (nreverse blob) blobs) blobs))
>
> ((null blob)
> (collect-blobs (cdr methods) (list (car methods)) blobs))
>
> ((betap (car methods))
> (collect-blobs methods () (cons (nreverse blob) blobs)))
>
> and is always called (other than by itself) with empty lists
> for the second and third arguments. What it then does, if I
> haven't misread, is to group METHODS into runs by putting a
> run-boundary immediately before each method satisfying BETAP.
>
> Perhaps it was easier to *write* recursively, but I think it
> would have been easier to read like this:
>
> (defun collect-blobs (methods)
> (let ((blobs (list ())))
> (flet ((complete-blob ()
> (when (first blobs)
> (setf blobs (list* () (nreverse (first blobs)) (rest blobs))))))
> (loop for method in methods do
> (when (betap method) (complete-blob))
> (push method (first blobs)))
> (complete-blob))
> (nreverse (rest blobs))))
>
> or -- a little longer but possibly more efficient and certainly
> clearer --
>
> (defun collect-blobs (methods)
> (let ((complete-runs nil)
> (current-run nil))
> (flet ((complete-run ()
> (when current-run
> (push (nreverse current-run) complete-runs)
> (setf current-run nil))))
> (loop for method in methods do
> (when (betap method) (complete-run))
> (push method current-run))
> (complete-run))
> (nreverse complete-runs)))
These two versions don't produce the correct results in my test case.
> Even the obvious near-mechanical transformation of your code
> seems to me preferable to the original:
>
> (defun collect-blobs (methods)
> (let ((blob nil)
> (blobs nil))
> (loop
> (cond
> ((null methods)
> (return (if blob (cons (nreverse blob) blobs)
> blobs)))
> ((null blob)
> (setf blob (list (first methods))
> methods (rest methods)))
> ((betap (car methods))
> (setf blobs (cons (nreverse blob) blobs)
> blob () ))))))
...and this version seems to run into an endless loop.
You can find the test case in my original posting.
> I suspect that the recursive version will seem preferable
> only to people who have written a whole lot of list-processing
> functions in tail-recursive form without any particular
> reason for doing so, and have thereby become familiar with
> the idiom. :-)
In general, I have a tendency to prefer iterative over recursive code,
but in this particular case, I have made several attempts to express
what I want, but only when I switched to the recursive version, I was
able to write a correct version.
I like your suggested renaming, though.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> These two versions don't produce the correct results in my test case.
Oops. :-) Does my informal description of what the function
is meant to do match your intention?
Well, I guess I should actually run your code. Hmm, no,
my description was absolutely wrong. Specifically, the
difference is that your COLLECT-BLOBS presents the
final list in reverse order. Which was in fact obvious;
I'd love to blame my error on the relative obscurity
of gratuitously recursive code, but I think I could have
made the same mistake if I'd been reading an iterative
version.
So, please pretend that I'd written
(defun collect-blobs (methods)
(let ((blobs (list ())))
(flet ((complete-blob ()
(when (first blobs)
(setf blobs (list* () (nreverse (first blobs)) (rest blobs))))))
(loop for method in methods do
(when (betap method) (complete-blob))
(push method (first blobs)))
(complete-blob))
(rest blobs)))
and
(defun collect-blobs (methods)
(let ((complete-runs nil)
(current-run nil))
(flet ((complete-run ()
(when current-run
(push (nreverse current-run) complete-runs)
(setf current-run nil))))
(loop for method in methods do
(when (betap method) (complete-run))
(push method current-run))
(complete-run))
complete-runs))
> ...and this version seems to run into an endless loop.
Er, yes, I omitted the T case when doing the "obvious
near-mechanical translation". Fixing this, and also
taking a couple of simplifying opportunities that result
from having done the transformation:
(defun collect-blobs (methods)
(let ((blob nil)
(blobs nil))
(loop
(cond
((null methods)
(return (if blob (cons (nreverse blob) blobs)
blobs)))
((null blob)
(setf blob (list (pop methods))))
((betap (car methods))
(push (nreverse blob) blobs)
(setf blob () ))
(t
(push (pop methods) blob))))))
> In general, I have a tendency to prefer iterative over recursive code,
> but in this particular case, I have made several attempts to express
> what I want, but only when I switched to the recursive version, I was
> able to write a correct version.
In such cases I find it helpful to ask myself whether it's
actually the spec that's wrong :-). But I'll trust you that
in this case the spec is well chosen.
> I like your suggested renaming, though.
I'd been assuming that you used the term "blob" because
you couldn't be bothered to think of a better name, rather
than because you thought it was the best possible. :-)
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Pascal Costanza wrote:
>
>>These two versions don't produce the correct results in my test case.
>
> Oops. :-) Does my informal description of what the function
> is meant to do match your intention?
>
> Well, I guess I should actually run your code. Hmm, no,
> my description was absolutely wrong. Specifically, the
> difference is that your COLLECT-BLOBS presents the
> final list in reverse order. Which was in fact obvious;
> I'd love to blame my error on the relative obscurity
> of gratuitously recursive code, but I think I could have
> made the same mistake if I'd been reading an iterative
> version.
Well, what the code does is indeed kind of tricky.
> So, please pretend that I'd written
[...]
> and
>
> (defun collect-blobs (methods)
> (let ((complete-runs nil)
> (current-run nil))
> (flet ((complete-run ()
> (when current-run
> (push (nreverse current-run) complete-runs)
> (setf current-run nil))))
> (loop for method in methods do
> (when (betap method) (complete-run))
> (push method current-run))
> (complete-run))
> complete-runs))
I like this version, and it indeed does what it should. Now I also agree
that it is better understandable than the recursive version. May I use
that code when I decide to make the original code publicly available?
>>In general, I have a tendency to prefer iterative over recursive code,
>>but in this particular case, I have made several attempts to express
>>what I want, but only when I switched to the recursive version, I was
>>able to write a correct version.
>
> In such cases I find it helpful to ask myself whether it's
> actually the spec that's wrong :-). But I'll trust you that
> in this case the spec is well chosen.
Well, actually it's just from a paper that claims that the described
functionality (methods with both super and inner calls) cannot be
implemented in CLOS, and this was mainly an exercise to prove that that
claim is wrong.
>>I like your suggested renaming, though.
>
> I'd been assuming that you used the term "blob" because
> you couldn't be bothered to think of a better name, rather
> than because you thought it was the best possible. :-)
Good guess. :)
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> Well, what the code does is indeed kind of tricky.
Yup. :-)
>> (defun collect-blobs (methods)
>> (let ((complete-runs nil)
>> (current-run nil))
>> (flet ((complete-run ()
>> (when current-run
>> (push (nreverse current-run) complete-runs)
>> (setf current-run nil))))
>> (loop for method in methods do
>> (when (betap method) (complete-run))
>> (push method current-run))
>> (complete-run))
>> complete-runs))
>
> I like this version, and it indeed does what it should. Now I also
> agree that it is better understandable than the recursive version. May
> I use that code when I decide to make the original code publicly
> available?
Of course.
--
Gareth McCaughan
.sig under construc
Gareth McCaughan wrote:
> Pascal Costanza wrote:
>
>> Well, what the code does is indeed kind of tricky.
>
> Yup. :-)
>
>>> (defun collect-blobs (methods)
>>> (let ((complete-runs nil)
>>> (current-run nil))
>>> (flet ((complete-run ()
>>> (when current-run
>>> (push (nreverse current-run) complete-runs)
>>> (setf current-run nil))))
>>> (loop for method in methods do
>>> (when (betap method) (complete-run))
>>> (push method current-run))
>>> (complete-run))
>>> complete-runs))
>>
>> I like this version, and it indeed does what it should. Now I also
>> agree that it is better understandable than the recursive version. May
>> I use that code when I decide to make the original code publicly
>> available?
>
> Of course.
And, even-more-of-course, feel free to make stylistic changes
such as replacing LOOP with DOLIST or NIL with (), if that
suits your taste better.
--
Gareth McCaughan
.sig under construc
On Fri, 18 Nov 2005 08:09:41 +0100, Robert Bralic wrote:
> Hello,
>
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
>
> Thanks in advance, Robert...!!!
Use which ever one makes your intent clearest, and your code the most
readable. Lisp does not favour one above the other.
Best wishes,
Bill.
"Robert Bralic" <···········@yahoo.co.uk> writes:
> Doees anybody knows, what is better
> to use in LISP, recursion or interation...??
> (in situation when you can use both)
I would avoid interation like the bird flu.
Stick with recursion or iteration depending on what is clearer to
express in your particular situation.
--
http://www.david-steuber.com/
The UnBlog: An island of conformity in a sea of quirks.
http://www.david-steuber.com/snippets/Boycott_Sony/