DRAFT Issue: REST-LIST-ALLOCATION (Version 1)

[masinter.pa@Xerox.COM]

This is an issue that we've avoided; I've had it on file for at least six
months. It addresses the question of whether APPLY newly allocations &REST
lists. There are the following options:

Always newly allocated
Always share structure
sharing permitted but not required


Always newly allocated is made more palatable by DYNAMIC-EXTENT
declarations or some such.
Permitted but not required would be made more palatable by a portable way
of saying "unshared" so that COPY-LIST could be avoided.

As time is short and this issue is not going to be ready in time, I've done
a rush job on filling this out, made some mistakes about the proposal name,
etc.

!
Forum:         Cleanup
Issue:         REST-LIST-ALLOCATION

References:    CLtL pp >>????<<

Related issues: DYNAMIC-EXTENT

Category:      CLARIFICATION

Edit history:  8-Dec-88, Version 1 by Masinter

Problem description:

In the special case of calling a function with an &REST list via APPLY,
implementations differ on 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.


Proposal (REST-LIST-ALLOCATION:NEWLY-ALLOCATED): 

Specify that &REST lists are newly allocated in the case when the function
is called via APPLY.

Proposal (REST-LIST-ALLOCATION:MAY-SHARE): 

Specify that the value of an &REST parameter is permitted, but not
required,
to share (top-level) structure with the last argument to APPLY.

Proposal (REST-LIST-ALLOCATION:MUST-SHARE)

Specify that the value of an &REST parameter is permitted, but not
required,
to share (top-level) structure with the last argument to APPLY.

>> this needs better spec about how the args match << 

Examples:

 (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

    (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)
    [6] (eval (cons 'foo x))
    [7] (eval (list 'foo 1 2 3))
    [8] (foo 1 2 3)

Which have the same semantics?

--> file 1:
  (let ((shared-state nil))
    (defun bar (x)
       (setq shared-state x))
    (defun foo ()
        shared-state))
  
--> file 2:

  (defun test (&rest arg)
    (bar arg)
    (foo))

(apply #'test '(a b c))

Should     (defun foo (&rest x) ...)
    
     behave as if it were defined:
    
(defun foo (&rest G0047)     ;Gensym really
      (let ((x (copy-list G0047)))
         ...))
    

Rationale:

[[confusion]]

Current practice:

Some implementations always share. Some implementations never share.
A few may share interpreted and not share compiled, or vice versa.

Cost to Implementors:

Low, for MAY. Higher for the others, for those implementations that
don't conform. If you don't share and have to, nearly impossible. 
If you do share and shouldn't, inserting COPY-LIST inside either
APPLY or &REST handling is still hard and slow. 

Cost to Users:

No matter what, somebody gets hurt. MAY means you have to
write awkward code if you care. The others, it depends on what
you currently count on.

Cost of non-adoption:

Great confusion over the issue.

Performance impact:

SHARE costs least in consing, might slow down function call 
for some implementations. MAY lets implementations pick, has
least impact. NEWLY-ALLOCATED requires consing in
cases where it didn't before.

Benefits:

Less confusion

Esthetics:

Differing, strongly held opinions.

Discussion:

The Revised3 Report on Scheme specifies that the equivalent of a
&REST argument must be a newly allocated list, to avoid precisely this
problem.

Two arguments for PERMITTED-NOT-REQUIRED 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, I think
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.

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.


&REST should never cause copying of a list passed to it from APPLY.


"if the CL spec can't get its act together to 
guarantee non-sharing in &rest lists, then there *must* be some construct 
added to the language so that the discerning user can prevent it.  In my
message to Common-Lisp@sail of 8 Apr 88 01:00:38 PDT I quoted her:
   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
me, 
   to bolster the case for those who claim that that CL semantics 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.
       . . . 
   Of course, the problem isn't only the sharing of &rest lists, but the
more 
   common flaw that they may, unannouncedly, have dynamic extent.  By this,
I 
   mean the bug where a stack-allocated &rest list can creep out into
global 
   data structures, even though it will surely disappear when the frame
that 
   created it returns.  Allegedly, Symbolics is going to fix this bug in
their 
   next release (and TI may have already fixed it?); but we are now five
years 
   beyond the first CL specification!


So as you say, we have a responsibility to resolve the very thorny issue
of REST-LIST-ALLOCATION.