Re: Issue "Eliminate forced consing" re-visited

[Dan L. Pierson <pierson%mist@multimax.ARPA>]

    > All-in-all, this has moved from what I remember as more a philosophical
    > statement than a cleanup proposal to something that I think we can,
    > and should, pass unless we are prepared to "depreciate" the sequence
    > functions entirely.
    
    I think that is going a bit far.  Surely the sequence functions are
    not nearly useless without this change.  (Recall, for example, that
    some of them just search.)
    
Sorry, I don't mean that the sequence functions are useless without
this change.  "Depreciate" is a technical term from some other
language standard (Fortran?) that means the feature is left in this
version of the language but may (will?) be removed in a future
version.  My point was that if we consider the sequence functions a
desirable part of the language, this enhancement is worthwhile.  If we
don't want to enhance them because we expect them to become obsolete
we should also make that clear.

    I would be interested in an informed opinion on how much of the
    excess allocation can be eliminated by soemthing like OSS and how
    much still requires destructive operations.  I also wonder whether
    OSS-like optimizations could be added to ordinary CL compilers for
    some class of operations involving the normal sequence functions.
    
The only class of OSS functions that have to cons are some of the
reducers (I don't believe that anything else does cons at run time,
but haven't gone over the source to make sure).  For example:

Rlist items  => list

  This function creates a list of the elements in items in order.

This could easily be extended to:

Rlist items &optional list  => list

  This function creates a list of the elements in items in order.  If
  an optional list is supplied the items are placed in it ...,
  otherwise a new list is created.

There are only two sequence functions not supported by OSS: REVERSE,
and SORT (and their variants).  As I understand it, the problem with
supporting OSS by compiler optimization with no extensions is that
efficient compilation of compositions of OSS functions depends on
adherence to a specific set of constraints.  The OSS package checks
for and either corrects or signals violations of these constraints.

For example (using some examples from part one of Dick's manual):

 This works: 
  (OR (Rfirst (Tpositions (EQ ITEMP (Elist UNIVERSE))))

 This doesn't work:
  (letS* ((VALUES (Evector VALUE-VECTOR))
          (WEIGHTS (Evector WEIGHT-VECTOR))
	  (SQUARES (* VALUES VALUES))
          (WEIGHTED-SQUARES (* SQUARES WEIGHTS)))
    (LIST (Rvector SQUARES) (Rvector WEIGHTED-SQUARES)))

 This works:
  (letS* (((VALUES WEIGHTS) (Tcotruncate (Evector VALUE-VECTOR)
			                 (Evector WEIGHT-VECTOR)))
	  (SQUARES (* VALUES VALUES))
          (WEIGHTED-SQUARES (* SQUARES WEIGHTS)))
    (LIST (Rvector SQUARES) (Rvector WEIGHTED-SQUARES)))

It seems likely that an "ordinary CL compiler" could support some
OSS-style optimization, but it would probably be restricted to a much
smaller subset of compositions of sequence operations than OSS.  It
would also be harder for a compiler to deal with cases it couldn't
optimize because, since the programmer hadn't declared any intent, the
compiler would be unable to distinguish between normal code to which
an optimization didn't apply and a programmer error that prevented an
intended optimization.  For these reasons, I think that something like
OSS is needed.  However anything accepted in CL should certainly fit
better into the CL naming world.