Re: SETF and variable issues in Self Similar program.

In article <yxztzmq6r5p.fsf@xxxxxx>,
Holger Schauer <Holger.Schauer@xxxxxx> wrote:

On 5213 September 1993, Rainer Joswig wrote:
In article <yxzmysib8xt.fsf@xxxxxx>,
Holger Schauer <Holger.Schauer@xxxxxx> wrote:
The typical idiom for using append is the following, isn't it?
(setq reversedresult (append (list singleitem) reversedresult)
I have not seen that. Most people just use CONS.
(equal
(CONS 'a '(b c d))
(append (list 'a) '(b c d)))

Yes, right. I was somehow too fixated on discussing append. Hmm, I
can't remember where I learned about that "idiom". Maybe it's a Prolog
thing, but that's not very likely either. Perhaps I was just confusing
append and cons wrt. the idiom.

The only difference is that the first form is a bit
more efficient, since it just CONSes one cons.
The APPEND form creates copies the first list into
a fresh new list.

I was only thinking about traversing the first list to find the last
cons cell to use for appending. Thanks for reminding me of the copying
issue. A penny saved is a penny earned.

means that all long-list-1 .. long-list-n are copied.
If you need to append them, that's fine. But be
careful in recursive algorithms where the
recursive call is in the first arguments (minus the last one).

Sure. Although CL doesn't promise tail call optimization, most
implementations do, AFAIK. So avoiding using append on the result of a
recursive call follows from the general advice to try to come up with
tail-recursive algorithms (if you're using recursion at all, of
course).

Right.

(defun foo ...
...
(append (foo ...) ...))

(FOO ...) is not a tail call. But the issue is that
calling APPEND on lists in recursive functions
can make the complexity of the function to be n^2.
Means, for inputs of ten or hundred items it may not be
an issue, but if n gets 1000 or more you see lots
of cons operations going on. Wasted also, since most
create temporary objects that will be GCed.

BUT:

Hmm, I would avoid tail-recursive code in Common Lisp if possible.

The language Common Lisp was not designed with tail-call
optimization in mind. The way to get a compiler to optimize a tail-call
is clumsy in most implementations - the amount of
optimizations differ from implementation to implementation.
Plus debugging gets harder. Plus it may be different
when you run the code in the interpreter.

LispWorks:
http://www.lispworks.com/documentation/lw50/LWUG/html/lwuser-98.htm#pgfId-889221

Tail call optimization when DEBUG<3 (see the restrictions)

The DEBUG declaration is used to turn that on/off in compiled (!)
code. That alone is clumsy.
Say, I want full debugging, but tail call optimization turned
on. What now? Insert LOCALLY declarations?

The biggest problem I see is that tail call optimizations
has various restrictions (REST args, Dynamic Variables, ...),
so that it is not obvious from staring at the code, what
the compiler will do. Will the call be optimized or not?
Difficult to say! You have to analyze the code carefully,
look at the disassembly or try to see the effect by
running some test data -> UGLY.

I would say, avoid tail call optimization.

Use a plain old iteration construct (DOLIST, DOTIMES, LOOP, ITERATE).
You want to list integers from 1 to n?

(loop for i from 1 upto n collect i)

No need for tail-call optimization. Just use a plain LOOP.

It gets more problematic with graph traversal and other
things, but the typical loop is a good candidate
to be written as a LOOP and not as a tail-recursive
function.

A few friends of mine have written an extremely complicated piece
of software. They are using tail call optimization.
Their software would not run without it. I tried to
tell them that this is not a good idea. But they don't listen. ;-)
For them the optimization helped to code their complex algorithms.
But then, there is no chance that this code will run on
the Lisp Machine, though they still have one - since the
Lisp Machine compiler does not support it. ;-)





Holger
.

Relevant Pages

  • Re: style issues
    ... No need to call APPEND in either branch. ... CONS prepends, and APPEND appends, so why not have a choice ... I know you can say that CONS is the right constructor ... Lists are not symmetric structures. ...
    (comp.lang.scheme)
  • Re: cons discussion from a newbie
    ... >to keep in mind that the elements of a list can themselves be lists. ... Abelson and Sussman use no data types except numbers in chapter 1, ... things as the asymmetry of CONS. ... I prefer to answer the question about CONS vs LIST vs APPEND ...
    (comp.lang.scheme)
  • Re: execise n.7 cap 6 wilensky book
    ... reason you cannot choose between CONS and APPEND. ... but APPEND to concatenate the two lists returned by the ...
    (comp.lang.lisp)
  • Re: [NEWBIE]CONS,APPEND AND LIST
    ... Roberto wrote: ... (CONS X Y) ... Y must be proper lists. ... append takes any number of arguments and appends them in this ...
    (comp.lang.lisp)
  • Re: SETF and variable issues in Self Similar program.
    ... APPEND is always a warning sign. ... ;;automatically - these lists contain all numbers that are equivalent ... Global variables should always be written as *foo*. ... (defun ordered-union (x y) ...
    (comp.lang.lisp)