Issue: DYNAMIC-EXTENT (Version 2)

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

I favor DYNAMIC-EXTENT:NEW-DECLARATION over STACK-LET, because
a declaration does seem more appropriate than a new special form.
I favor it over WITH-DYNAMIC-EXTENT, because (as BarMar pointed
out) saying that -all- objects consed during execution of a form
have dynamic extent is too dangerous.

However I cannot support the current version of the DYNAMIC-EXTENT
proposal, basically for the reason that Masinter gave.  See below.
While I'm here I'll also comment on typos.

    Date: Tue, 15 Nov 88 16:14 EST
    From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

    Issue:          DYNAMIC-EXTENT

    Problem Description:

->    Sometimes a programmers knows that a particular data structure
programmer[s]

    Proposal (DYNAMIC-EXTENT:NEW-DECLARATION):

      Other interesting cases are:

            (PROCLAIM '(INLINE G))
            (DEFUN G (X) (DECLARE (DYNAMIC-EXTENT X)) ...)
->          (DEFUN F () (F (LIST 1 2 3)))
The second F should be G.

      What data types (if any) can be stack-allocated will vary from
      implementation to implementation. In some implementations, it might be
      possible to allocate arrays, structures, or instances, for example.

Masinter seems not to have noticed this paragraph, since he complained
that the proposal addressed only lists, so perhaps it should be moved
earlier in the proposal.  I suggest coupling this with the second
paragraph in the proposal section, which makes it clear that the
declaration -allows- the declared object to be stack-allocated
regardless of its type, but does not -require- anything to be
stack-allocated.

The following is where I disagree strongly with the proposal:

      It is very important to note that it is the actual constructor operation
      and not the resulting data type which determines the level of the object
      referred to in the dynamic extent declaration. For example, in

            (LET ((X (LIST 'A1 'B1 'C1))
                  (Y (CONS 'A2 (CONS 'B2 (CONS 'C2 NIL)))))
              (DECLARE (DYNAMIC-EXTENT X Y))
              ...)

      The list (A1 B1 C1) which is the initial value of X will have three cons
      cells, all of which have dynamic extent. The cons (A2 . (B2 C2)) which is
      the initial value of Y will have dynamic extent, but its cdr (B2 C2) will
      have indefinite extent.

I think this is the wrong way to look at it in general, and furthermore
this means that backquote can't be used correctly with the
DYNAMIC-EXTENT declaration, since there is no promise what backquote
expands into.  Also this way of looking at it requires saying silly (in
my opinion) things like:

      If an implementation does not recognize the constructor, it calls
      MACROEXPAND-1 in hopes of seeing a constructor which it does recognize.

A particular implementation might well be implemented this way, but this
should not be the definition of the language!

I propose the following instead.  I admit that this is somewhat stilted,
but I think that is necessary in order to be precise and unambiguous.

The meaning of a dynamic extent declaration is that execution of the
forms in the scope of the declaration will not "save" any "proper part"
of the initial value of the declared variable.  To "save" an object
means to cause a reference to that object to be accessible outside the
dynamic extent of the form at the beginning of whose body the
declaration appears.  An object can be "saved" by storing it with a
side-effecting operation and not replacing it with a different value
before the end of the dynamic extent, by using it as a component of a
freshly-allocated object that is itself "saved," by capturing it in a
function closure that is itself "saved," by returning it as a value, or
by transmitting it outside the dynamic extent with THROW.  A "proper
part" of an object A is any object that is accessible at the beginning
of the scope of the declaration -only- by applying a function to A or to
a "proper part" of A.  This means that any objects freshly allocated
during the construction of the initial value of the declared variable,
and not "saved" during the construction of that value, are "proper
parts" and can be allocated on a stack.

Returning to the example
            (LET ((X (LIST 'A1 'B1 'C1))
                  (Y (CONS 'A2 (CONS 'B2 (CONS 'C2 NIL)))))
              (DECLARE (DYNAMIC-EXTENT X Y))
              ...)

The "proper parts" of X are three conses, and the "proper parts" of Y
are three other conses.  None of the symbols A1, B1, C1, A2, B2, C2, or
NIL is a "proper part" of X or Y.  However, if a freshly allocated
uninterned symbol had been used, it would have been a "proper part."

    Test Case:

          (DOTIMES (I N) 
            (DECLARE (DYNAMIC-EXTENT I))

This is particularly instructive.  Since I is an integer by the
definition of DOTIMES, but EQ and EQL are not necessarily equivalent for
integers, what are the "proper parts" of I, which this declaration
requires the body of the DOTIMES not to "save"?  If the value of I is 3,
and the body does (SETQ FOO 3), is that an error?  The answer is no, but
the interesting thing is that it depends on the implementation-dependent
behavior of EQ on numbers.  In an implementation where EQ and EQL are
equivalent for 3, then 3 is not a "proper part" because (EQ I (+ 2 1))
is true, and therefore there is another way to access the object besides
going through I.  On the other hand, in an implementation where EQ and
EQL are not equivalent for 3, then the particular 3 that is the value of
I is a "proper part", but any other 3 is not.  Thus (SETQ FOO 3) is valid
but (SETQ FOO I) is erroneous.  Since (SETQ FOO I) is erroneous in some
implementations, it is erroneous in all portable programs, but some other
implementations may not be able to detect the error.

I hope no one misreads the above as an argument that my proposal is too
complicated, since it does not derive at all from my proposal, but only
 from the way Common Lisp works.

    Discussion:

      Actually, a blurry issue is whether
       (LENGTH (LIST (LET ((X (LIST 1 2 3))) (DECLARE (DYNAMIC-EXTENT X)) X)))
       => 1
      is well-defined. I refer to these stack-allocated things as being invalid
      return values, but in fact we might want to say that they're ok to return
      but that you just can't do any serious operations on them (ie, you can't
      expect them to still be lists, etc.) Can anyone imagine a pointer into
      unallocated stack causing problems for their GC? If so, we could be more
      clear on this point.

In some if not all implementations, the part of the stack above the
current stack pointer can have its contents changed at any time by an
interrupt, possibly to something that will cause LIST to blow out when
it stores it into the CAR of the CONS it creates.  That's an
implementational point of view.  From a language point of view, I do not
believe you can make a coherent definition of "serious operations."  I
don't think this is a blurry issue at all, I think it's quite clear that
returning an object as a value is "saving" it regardless of what the
caller actually does with the value.  I would say that even

  (PROGN (LET ((X (LIST 1 2 3))) (DECLARE (DYNAMIC-EXTENT X)) X)
         NIL)

is an error.

    Date: 7 Dec 88 18:05 PST
    From: masinter.pa@Xerox.COM

    Version 2 of this writeup didn't mention one of the criticisms I sent on 1
    July, namely:

    "a) it is disturbing to introduce a construct within which a casual change
    of (CONS X (LIST Y Z)) to  (LIST X Y Z) could introduce a serious bug
    (e.g., if the tail were stashed away
    somewhere.)"

I quite agree with this.  My proposed alternative definition doesn't have any
problems like this, since it is defined in terms of the actual object, not in
terms of how it was constructed.

    I wonder if it might be useful to think about what the semantics of
    declaring something to be "dynamic extent" really means. 

    For example, I think of a type declaration as a promise from the programmer
    to the compiler that a TYPEP assertion will at certain points (exactly what
    points being subject to some debate).

    When you declare something as DYNAMIC-EXTENT, what is it you are promising
    to the compiler? That the value of the variable or any part of it will not
    be newly stored in any other permanent structure? It or any subpart of it
    will not be referenced outside of the dynamic extent of the enclosing form?

My proposed alternative definition addresses this, I believe.  I'd be interested
to hear if anyone can find any imprecisenesses in it.