REST-LIST-ALLOCATIONREST list via APPLY, Common Lisp fails to specify whether a new copy of the list is freshly allocated. For example, given
(DEFVAR *MY-LIST* '(A B C))
(DEFUN FOO (&REST X) (EQ X *MY-LIST*))
does (APPLY #'FOO *MY-LIST*) return T?
This issue is different from the question of the extent of "rest lists" in the case when they *are* newly allocated which is indefinite; the issue DYNAMIC-EXTENT also contains some proposals about extent.
REST lists are newly allocated in the case when the function is called via APPLY.REST parameter is permitted, but not required, to share (top-level) structure with the last argument to APPLY.REST parameter is required to share (top-level) structure with the last argument to APPLY.
>> this needs better spec about how the args match <<
DEFVAR *MY-LIST* '(A B C))
(DEFUN FOO (&REST X) (EQ X *MY-LIST*))
(APPLY #'FOO *MY-LIST*) => T ;on Symbolics systems and probably ; many stock hardware implementations
This implies that
(DEFUN BAR (&REST X) (RPLACA X 'D))
(APPLY #'BAR *MY-LIST*)
*MY-LIST* => (D B C) ;on Symbolics systems and probably many stock ; hardware implementations
Another example: which of the following have the same semantics?
(setq x '(1 2 3))
[1] (apply #'foo 1 2 3 NIL) [2] (apply #'foo 1 2 (cddr x)) [3] (apply #'foo 1 (cdr x)) [4] (apply #'foo x) [5] (funcall #'foo 1 2 3)
Under REST-LIST-ALLOCATION:NEWLY-ALLOCATED: [1]-[5] are equivalent. Under REST-LIST-ALLOCATION:MAY-SHARE: Any answer to the question is correct for some conceivable implementation. Abstracting over implementations, this means that [1]-[5] are pairwise non-equivalent. Under REST-LIST-ALLOCATION:MUST-SHARE: [1]-[4] are pairwise non-equivalent in all implementations. This proposal leaves open the question of whether [1] is equivalent to [5].
And finally:
Should (defun foo (&rest x) ...)
behave (aside from efficiency) as if it were defined:
(defun foo (&rest G0047) ;Gensym really (let ((x (copy-list G0047))) ...))
APPLY is unclear. In consequence it is impossible to write portable code that relies on &REST arguments sharing structure with the last argument to APPLY. Portable code can rely on &REST arguments *not* sharing structure with the last argument to APPLY, but only by performing an explicit COPY-LIST on all &REST arguments; this is redundant and inefficient in implementations where &REST arguments are newly allocated anyway.MAY-SHARE, since that is the status quo. Both of the other proposals entail a significant cost for some implementations. If MUST-SHARE is adopted, then implementations that don't share structure may be nearly impossible to convert. If NEWLY-ALLOCATED is adopted, then implementations that do share will have to insert a call to COPY-LIST inside either APPLY or &REST list handling, which will slow things down and may be difficult as well.MAY-SHARE means you have to write awkward and inefficient code if you care. (This is already the case for portable code.) MUST-SHARE means you have to add explicit calls to COPY-LIST to code that assumes the contrary. NEWLY-ALLOCATED means you have to rewrite code that assumes sharing.MUST-SHARE costs least in consing, but might slow down function call for some implementations. MAY-SHARE lets implementations pick, has least impact. NEWLY-ALLOCATED requires consing in cases where it didn't before.REST argument must be a newly allocated list, to avoid precisely this problem.
The argument for MUST-SHARE is that copying is inefficient, so &REST should never cause copying of a list passed to it from APPLY. Functions that desire a new copy can just call COPY-LIST.
Two arguments for MAY-SHARE are:
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, it's better not to put the inefficiency into the language in the first place.
The DYNAMIC-EXTENT proposal would allow &REST lists that were "newly allocated" to have dynamic extent if they were to be passed down via APPLY. This puts the burden in the right place.
Two (closely related) arguments for NEWLY-ALLOCATED:
1. The programmer's model of function calling is simpler: functions take arguments, and any two calls that pass the same arguments to the same function are equivalent. The MAY-SHARE and MUST-SHARE proposals require a model in which functions generally take their arguments in the form of a list, and the extent to which that list shares structure with other lists in the system becomes an important part of the semantics of a function call.
2. It's not only smashing a &rest argument that's a problem, it's smashing any list that has been given as the last argument to APPLY as well. Consider the following in an implementation that doesn't copy the last argument to APPLY when it is passed as a &rest argument:
> (defvar *message*) *MESSAGE* > (defun set-message (&rest mess) (setq *message* mess)) SET-MESSAGE > (let ((winner (list 'a 'winner))) (apply #'set-message winner) (setf (cdr winner) (list 'loser)) winner) (A LOSER)
Is *message* (A WINNER) or (A LOSER)? (It might be (#<DTP-LOCATIVE 76123756> #<DTP-ODD-PC 12313453> ...) but that's a different problem.) This suggests that once a list has been given as the last argument to APPLY it is no longer OK to modify it.
Gail Zacharias talked about the common idiom of simply doing a COPY-LIST on every &rest argument, to insure some normalcy. Her reasoning seems to bolster the case for those who claim that the current CL semantics (MAY-SHARE) are deficient:
Subject: &REST Lists
Date: 24 Mar 88 12:23:15 EST (Thu)
From: gz@spt.entity.com (Gail Zacharias)
. . .
If Common Lisp doesn't require unshared &rest lists, then I think
it must provide a declarative version of this idiom so the COPY-LIST can
be portably avoided when it's redundant. Seems to me that the fact that
this is a common case where users find a need for conditionalization
indicates a real deficiency in Common Lisp's specification.
. . .
So we have a responsibility to resolve the very thorny issue of REST-LIST-ALLOCATION.