Issue: DYNAMIC-EXTENT (Version 1)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

For those who don't remember, this issue used to be called STACK-LET.
There was opposition to STACK-LET and STACK-LET* with people seeming
to prefer a DYNAMIC-EXTENT declaration. This is that rewrite.

-----
Issue:          DYNAMIC-EXTENT
References:     None
Category:       ADDITION
Edit history:   27-Jun-88, Version 1 by Pitman (as issue STACK-LET)
		15-Nov-88, Version 2 by Pitman (issue renamed, major revision)
Related-Issues: REST-ARGUMENT-EXTENT, WITH-DYNAMIC-EXTENT
Status:	        For Internal Discussion

Problem Description:

  Sometimes a programmers knows that a particular data structure
  will have only dynamic extent. In some implementations, it is
  possible to allocate such structures in a way that will make them
  easier to reclaim than by general purpose garbage collection
  (eg, on the stack or in some temporary area). Currently, however,
  there is no way to request the use of such an allocation mechanism.

Proposal (DYNAMIC-EXTENT:NEW-DECLARATION):

  Introduce a new declaration called DYNAMIC-EXTENT. The arguments to
  this declaration are names of variables. The declaration asserts that
  the value which is initially held by the indicated variable will have
  dynamic extent. [In the case of an iteration variable, the declaration
  asserts that on every iteration, the initial value of that variable
  for the iteration will have dynamic extent.]

  It is permissible for an implementation to simply ignore this declaration.
  In implementations which do not ignore it, the compiler (or interpreter)
  is free to make whatever optimizations are appropriate given this
  information; the most common optimization is to stack-allocate the
  initial value of the object.

  Since stack allocation of the initial value entails knowing at the
  object's creation time that the object can be stack-allocated, it is
  not generally useful to declare DYNAMIC-EXTENT for variables for
  which have no lexically apparent initial value. For example,

	(DEFUN F ()
	  (LET ((X (LIST 1 2 3)))
	    (DECLARE (DYNAMIC-EXTENT X))
	    ...))

  would permit those compilers which wish to do so to stack-allocate the
  list in X. However,

	(DEFUN G (X) (DECLARE (DYNAMIC-EXTENT X)) ...)
	(DEFUN F () (G (LIST 1 2 3)))

  could not typically permit a similar optimization in G because it would
  be a modularity violation for the compiler to assume facts about G from
  within F. Only an implementation which was willing to be responsible for
  recompiling F if G's definition changed incompatibly could stack-allocate
  the list argument to G in F.

  Other interesting cases are:

	(PROCLAIM '(INLINE G))
	(DEFUN G (X) (DECLARE (DYNAMIC-EXTENT X)) ...)
	(DEFUN F () (F (LIST 1 2 3)))

    and	(DEFUN F ()
	  (FLET ((G (X) (DECLARE (DYNAMIC-EXTENT X)) ...))
	    (G (LIST 1 2 3))))

  where some compilers might realize the optimization was possible and others
  might not.

  An interesting variant of this is the so-called `stack allocated rest list'
  which can be achieved (in implementations supporting the optimization) by:

	(DEFUN F (&REST X)
	  (DECLARE (DYNAMIC-EXTENT X))
	  ...)

  Note here that although the initial value of X is not explicit, the F
  function is responsible for assembling the list X from the passed arguments,
  so the F function can be optimized by the compiler to construct a 
  stack-allocated list instead of a heap-allocated list in implementations
  which support such.

  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.

  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. As such, (CDR X) is not an appropriate return
  value from the above LET, but (CDR Y) is an appropriate return value.
  Further, in 

	(LET ((X (LIST 'A 'B (LIST 'C 'D))))
	  (DECLARE (DYNAMIC-EXTENT X))
	  ...)

  the three conses (A . <cons-cell>), (B . <cons-cell>), and 
  (<cons-cell> . NIL) are said to have dynamic extent, but the list (C D)
  has indefinite extent. To declare the entire structure to have dynamic
  extent, one must write something like:

	(LET* ((TEMP (LIST 'C 'D))
	       (X (LIST 'A 'B TEMP)))
	  (DECLARE (DYNAMIC-EXTENT X TEMP))
	  ...)

  If an implementation does not recognize the constructor, it calls
  MACROEXPAND-1 in hopes of seeing a constructor which it does recognize.
  It iterates this process until it either sees a constructor which it
  does recognize, or until no macro expansion is possible. If it is unable
  to recognize the constructor, it must treat the object as if it had
  indefinite extent.

Test Case:

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

  (DO ((L (LIST-ALL-PACKAGES) (CDR L)))
      ((NULL L))
    (DECLARE (DYNAMIC-EXTENT L))
    (PRINT (CAR L)))
  prints all packages

  (DEFUN ADD (&REST X) (DECLARE (DYNAMIC-EXTENT X)) (APPLY #'+ X))
  (ADD 1 2 3) => 6

  (DEFUN ZAP (X Y Z)
    (DO ((L (LIST X Y Z) (CDR L)))
	((NULL L))
      (DECLARE (DYNAMIC-EXTENT L))
      (PRIN1 (CAR L))))
  (ZAP 1 2 3)
  prints 123

  (DEFUN ZAP (N M)
    ;; Computes (RANDOM (+ M 1)) at relative speed of roughly O(N).
    ;; It may be slow, but with a good compiler at least it
    ;; doesn't waste much heap storage.  :-)
    (LET ((A (MAKE-ARRAY N)))
      (DECLARE (DYNAMIC-EXTENT A))
      (DOTIMES (I N) 
	(DECLARE (DYNAMIC-EXTENT I))
	(SETF (AREF A I) (RANDOM (+ I 1))))
      (AREF A M)))
  (< (ZAP 5 3) 3) => T

Rationale:

  This permits a programmer to offer advice to an implementation about
  what may be stack-allocated for efficiency.

  It may be difficult or impossible for a compiler to infer this
  same information statically.

  Since a number of implementations offer this capability and there
  is demand from users for access to the capability, this ``codifies
  existing practice.''

  Because this approach is purely lexical, it does not interact badly with
  other programs in the way that the macro WITH-DYNAMIC-EXTENT (see issue
  by same name) would.

Current Practice:

  Symbolics Genera and Symbolics Cloe offer stack allocation, though not
  in this strategy.

  [KMP thinks that] Lucid supports the proposal.

Cost to Implementors:

  No cost is forced since implementations are permitted to simply
  ignore the DYNAMIC-EXTENT declaration.

Cost to Users:

  None. This change is upward compatible.

  There may be some hidden costs to debugging using this declaration (or any
  feature which permits the user to access dynamic extent objects without
  the compiler proving that they are appropriate). If the user misdeclares
  something and returns a pointer into the stack (or stores it in the heap),
  an undefined situation may result and the integrity of the Lisp storage
  mechanism may be compromised. Debugging these situations may be tricky,
  but users who have asked for this feature have indicated a willingness
  to deal with such costs. Nevertheless, the perils should be clearly
  documented and casual users should not be encouraged to use this
  declaration.

Cost of Non-Adoption:

  Some portable code would be forced to run more slowly (due to
  GC overhead), or to use non-portable language features.

Benefits:

  The cost of non-adoption is avoided.

Aesthetics:

  This declaration allows a fairly low level optimization to work
  by asking the user to provide only very high level information.
  The alternatives (sharpsign conditionals, some of which may
  lead to more bit-picky abstractions) are far less aesthetic.

Discussion:

  A previous version of this proposal suggested primitives STACK-LET
  and STACK-LET*. Consensus was that the more general declaration facility
  would be more popular.

  Pitman supports the DYNAMIC-EXTENT:NEW-DECLARATION.

  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.