Structure sharing in arguments

[David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>]

    Date: Wed, 23 Jul 86 14:24 EDT
    From: Brad Miller <miller@UR-ACORN.ARPA>

	Return-path: <@ROCHESTER.ARPA,@SAIL.STANFORD.EDU:DCP@ELEPHANT-BUTTE.SCRC.Symbolics.COM>
	Received: from ur-cayuga.rochester.arpa (ROCHESTER.ARPA) by UR-ACORN.ARPA via INTERNET with SMTP id 31199; 23 Jul 86 13:58:36-EDT
	Received: from SAIL.STANFORD.EDU (su-ai.arpa) by ur-cayuga.rochester.arpa id AA09110 (4.12w); Wed, 23 Jul 86 14:01:05 edt
	Received: from [192.10.41.41] by SAIL.STANFORD.EDU with TCP; 23 Jul 86  10:21:51 PDT
	Received: from FIREBIRD.SCRC.Symbolics.COM by ELEPHANT-BUTTE.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 48241; Wed 23-Jul-86 13:21:25 EDT
	Date: Wed, 23 Jul 86 13:21 EDT
	From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>
	Subject: Structure sharing in arguments
	To: hpfclp!diamant@hplabs.HP.COM, common-lisp@SU-AI.ARPA
	In-Reply-To: The message of 23 Jul 86 00:39 EDT from hpfclp!diamant@hplabs.HP.COM
	Message-Id: <860723132120.2.DCP@FIREBIRD.SCRC.Symbolics.COM>

	    Date: Tue, 22 Jul 86 21:39:37 pdt
	    From: hpfclp!diamant@hplabs.HP.COM

		    From: Scott Fahlman <fahlman@C.CS.CMU.EDU>
		    Subject: Some easy ones (?)
		    Proposal #13: Structure Sharing in Arguments
	
		    Clarification:
	
		    Specify that the &REST or &BODY argument to a macro may be the very list
		    from the macro call, and not a copy, and therefore the user should not
		    perform destructive operations on it.
	
		    Similarly, a function that takes a &REST argument should not
		    destructively modify it because in some implementations its top-level
		    list structure might share with a list that the user gave as the last
		    argument to APPLY.

	    I don't really care whether you add a restriction not to do destructive
	    operations on a &REST or &BODY argument, but it better be clear that the
	    list returned may not be something which will go away on exiting the function
	    (which could happen if the parameter list were stored on the stack and a
	    pointer to that list was returned -- apparently what Symbolics does).
	    Nothing currently in CLtL limits me from doing the following (nor should it):

	    (defun foo (&rest x) x)

	(defun list (&rest list) list)
	(defun copy-list (list) (apply #'list list))

	[Yes, Symbolics uses stack-consed &rest lists, and they will screw you
	every now and then.  >>> My view of our current position <<< is that the
	efficiency issues (e.g., not calling copy-list on every &rest arg) are
	outweighed by the programmer resources needed to implement the copying
	only when necessary.]

	I'm fairly convinced that disallowing destructive operations on &rest
	lists is funtionally equivalent to not being allowed to store them in
	stable storage or to return them.  I think my first proof caused CLtL to
	dictate some aspects of function calls.  I'm looking for a proof that is
	within the bounds of CLtL that does have such dictations.  Maybe there
	aren't any.  Maybe I'm wrong and they aren't equivalent, but I suspect
	they are.

    Now wait a second. (defun foo (&rest x) x) is not destroying the rest
    argument. The problem is that the programmer who uses the result of foo
    may destroy that result. Should he have to know how foo is implemented
    to know what he is allowed to do to the result? I should think not....

Precisely.  Now consider this.  What is the difference between FOO being
destructive on X and the caller of FOO being destructive on the result.
Are not the X that FOO sees and the result that FOO returns EQL?  I
should hope so!  This means you can't copy-if-return or
copy-if-stable-store.  (There are harder issues about passing it to
other functions.)  Therefore, if you let the caller of FOO be
destructive on the result of FOO (your premise which I agree with), you
have to let FOO be destructive on X.  In other words, the proposal
(repeated here)

    Similarly, a function that takes a &REST argument should not
    destructively modify it because in some implementations its top-level
    list structure might share with a list that the user gave as the last
    argument to APPLY.

simply doesn't hold water.  The only way out of this I can see is that
if an &REST arg cannot be proven to be used in only a "downward" fashion
(i.e., it nor any tail is returned or stored in stable storage), then it
must always be a freshly consed list.

Let's see if I can summarize this line of thought.  Requiring
implementations to be non-destructive on their &REST arg implies
non-local knowledge by the callers.  This isn't good, and therefore
discarded.  Therefore, we should allow destructive operations on &REST
args.