Issue: REST-ARGUMENT-EXTENT

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

I wrote the following "straw man" proposal mostly because I'm tired of
seeing the incessant mail on Common-Lisp about this topic and I'm hoping
we can quickly work toward having something to push back at the
Common-Lisp community to appease them on this obviously important issue.
I expect that this will go through a few iterations before the form and
content settle down, but I just wanted to get something concrete (straw?)
on our table...
-----
Issue:        REST-ARGUMENT-EXTENT
References:   5.2.2 Lambda Expressions (pp59-66)
Category:     ADDITION
Edit history: 10-Apr-88, Version 1 by Pitman
Status:	      For Internal Discussion

Problem Description:

  Currently, all lists created for use with the &REST syntax in lambda lists
  have indefinite extent. Many users have complained that this is not always
  necessary and often creates unnecessary garbage.

Proposal (REST-ARGUMENT-EXTENT:GENERAL)

  Introduce a DYNAMIC-EXTENT declaration such that
   (DECLARE (DYNAMIC-EXTENT variable))
  would permit the implementation to make the list held by the indicated
  VARIABLE to have only dynamic extent.

  Example:	(DEFUN FOO (&REST L)
		  (DECLARE (DYNAMIC-EXTENT L))
		  (APPLY #'BAR L))

  Rationale:

    This would allow the programmer to declare general information about
    data flow which it might be difficult or impossible for a compiler to
    obtain mechanically.

Proposal (REST-ARGUMENT-EXTENT:CONSERVATIVE)

  Introduce a DYNAMIC-EXTENT declaration such that
   (DECLARE (DOWNWARD-REST-ARGUMENT))
  would permit the implementation to make the list held by the rest argument
  to the immediately containing binding form have only dynamic extent. It would
  be an error if the immediately containing binding form did not have an
  &REST specifier to which this declaration could apply.

  Example:	(DEFUN FOO (&REST L)
		  (DECLARE (DOWNWARD-REST-ARGUMENT))
		  (APPLY #'BAR L))

  Rationale:

    This would allow the programmer to declare specific information about
    rest argument data flow which it might be difficult or impossible for
    a compiler to obtain mechanically, but would not attempt to treat the
    more general issue of how this related to other kinds of data flow.

Current Practice:

  Lucid implements REST-ARGUMENT-EXTENT:GENERAL [at least for rest arguments;
  I don't know if they attach a meaning to its use for any other arguments. -kmp]

  Symbolics Cloe implements REST-ARGUMENT-EXTENT:CONSERVATIVE.

Cost to Implementors:

  Since implementations are only allowed (and not required) to make any use
  of this declaration, there is no forced cost. In practice, though, some
  users will probably get irritated if implementations fail to do something
  useful with this declaration, so some implementors may end up having to pay
  even if they don't technically have to.

  Fully implementing even dynamic rest lists (let alone dynamic objects of
  all kinds or for other data flow paths, whatever that may mean) may not be
  a small change in some implementations. There is possible interaction with
  garbage collection, possible implications on hidden assumptions in code
  generation for stack winding and unwinding, TYPEP, etc. depending on how the
  details of how dynamic lists end up being implemented.

Cost to Users:

  None. This is an upward-compatible change for users.

  Many users are already exploiting this feature in an implementation-dependent
  way, so this change will improve the maintainability of code for those
  implementations and may encourage some new implementations to offer equivalent
  functionality.

Cost of Non-Adoption:

  Some users will continue to be discouraged with implementations that do
  "gratuitous heap consing" of rest lists.

Benefits:

  Many implementors claim that large improvements in the performance of programs
  (and their associated garbage collection) are to be had from adopting some form
  of proposal such as this.

Aesthetics:

  Debugging program errors involving dynamic extent objects can be very tricky.
  This feature should be strongly discouraged for naive programmers.

Discussion:

  The example above is perhaps not the best example because APPLY is something
  the compiler can have primitive knowledge about, and good compilers may in fact
  already optimize this case even without the need for a user declaration.
  Nevertheless, if the function were MY-APPLY rather than APPLY, the case would
  be made because (non-block) compilers cannot make assumptions about what
  MY-APPLY would do without violating the normal rules for modular compilation.

  KMP supports REST-ARGUMENT-EXTENT:CONSERVATIVE pending discussion of why
  REST-ARGUMENT-EXTENT:GENERAL is not overkill.