&REST args

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

    Date: Thu, 17 Mar 88 00:38 EST
    From: Charles Hornig <Hornig@ALDERAAN.SCRC.Symbolics.COM>

    Yes, declarations would be a good thing if we decide that Common Lisp
    permits valid programs to store pointers to or to destructively modify
    &REST arguments.  If we decide that Common Lisp does not permit it, or
    leaves the result undefined (which is another way of saying the same
    thing), then there is no need for declarations.

Agreed.

    I believe that there is general agreement that one is allowed to save
    pointers to &REST arguments.

Agreed.

    There seems to be no agreement about destructive modification.

The X3J13 Cleanup subcommittee has taken on this issue.  We discussed
it at a meeting on Tuesday and will be discussing it further.  It's likely
that X3J13 will make a decision on this issue in June.  Of course, nothing
X3J13 decides is final until a language specification is created, accepted
by written ballot, and reported out of the X3J13 committee to the parent
standards organizations.

    I, personally, believe that destructive
    modification should be permitted and that the language implementation
    must guarantee that this will not currupt structures passed as APPLY
    arguments.  This guarantee can be done through declarations, code
    analysis, or just consing a lot.  

For the record, I strongly disagree with this.  I believe Common Lisp should
specify that the value of an &REST parameter is permitted, but not required,
to share structure with the last argument to APPLY.  I have two reasons for
this belief (both of which have come up on the mailing list before).

1. In no other place does Common Lisp automatically unshare structure,
except when the user is explicitly modifying the structure (as in REMOVE).
Making APPLY automatically unshare would be a semantic wart.

2. If APPLY copies its last argument, recursive programs that receive an
&REST argument and pass it to APPLY become inefficient.  A linear time
algorithm can change to a quadratic time algorithm.  While the efficiency
could be regained through compiler flow analysis in many cases, I think
it's better not to put the inefficiency into the language in the first
place.