Issue ELIMINATE FORCED CONSING (Version 2) [formerly "Eliminate forced consing" re-visited]

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

    Date: Mon, 22 Aug 88 21:39:05 PDT
    From: trwrb!smpvax1!jrg@ucbvax.Berkeley.EDU

I think this is a reasonable proposal that needs a bit more work and some
simplification.  One can argue about whether it's better to provide these
storage reusing operations or to provide a good garbage collector, but I
think it makes a great deal of sense, in the context of Common Lisp, to
provide both.

I think the name :OVERWRITE would be more consistent with the rest of
Common Lisp than the name :TARGET.  It makes it clearer that this
argument is storage to be overwritten with new information.

When you say
    (1) The target sequence must accomodate elements of the type(s) in the
    source sequence.
I believe this is wrong.  It should refer to the type of the elements of the
-result- of the function, not the source.

I don't understand the need for the :TARGET-FROM-END feature and I think
you should drop it from the proposal.

    The last cons of the target list whose CAR was filled by the computation is
    returned as a second value.  The CDR of this cons is that tail of the
    target list not used to accomodate the sequence computation.

I think this feature is unnecessary and should be discarded.  I think
extra conses should simply be thrown away.  Most people exploiting this
non-consing feature are more likely to use vectors than lists, I feel.

If the feature is kept, the second value should be the cdr of what you
propose it to be, and the result should be null-terminated in the
correct place; that should not be left to the caller to do.

Another idea would be to allow the user to pass in a function that is
called whenever storage is to be allocated.  Perhaps it would take two
arguments and the default would be #'APPLY.  The first argument would
be one of #'CONS, #'MAKE-LIST, or #'MAKE-ARRAY, the second argument
would be a list of arguments with dynamic extent.  I'm not real fond
of this idea, but it does provide maximum generality.

    (4) :TARGET-START and :TARGET-END keywords are supported.

These seem useful but should be named :OVERWRITE-START and :OVERWRITE-END.

The functions SUBSEQ, COPY-SEQ, COPY-LIST, and BUTLAST need not be
modified, because the functionality is already available from REPLACE.
The functions COPY-ALIST and COPY-TREE should not be modified, because
their use of storage is too complex to fit into this model (they don't
deal in linear sequences).  The function ADJOIN should not be modified,
because a non-consing version is trivial for a user to write, and
because the consumption of storage is conditional, which would
complicate the interface.

I don't think UNION, INTERSECTION, SET-DIFFERENCE, and SET-EXCLUSIVE-OR
should be modified, because their conditional consumption of storage
would complicate the interface (unused storage has to be handed back to
the caller) and because the destructive versions that already exist can
solve the same problem, in my experience.  (They aren't completely
non-consing, but they minimize consing.)  You forgot to mention SUBST,
but I think the same reasoning applies and SUBST should not be modified.

This leaves REVERSE, MERGE, REMOVE, REMOVE-IF, REMOVE-IF-NOT,
REMOVE-DUPLICATES, SUBSTITUTE, SUBSTITUTE-IF, SUBSTITUTE-IF-NOT,
STRING-TRIM, STRING-LEFT-TRIM, STRING-RIGHT-TRIM, STRING-UPCASE,
STRING-DOWNCASE, STRING-CAPITALIZE.  I think it's reasonable to
modify these in the way you suggest.  Doing just these makes for
a much simpler proposal that is easier to understand.

MAKE-STRING-OUTPUT-STREAM should follow the same rules as
WITH-OUTPUT-TO-STRING when a string is supplied, instead of
the different rule you suggested.  With that change to make it
consistent, I support what you propose.

This leaves CONCATENATE, APPEND, REVAPPEND, and MAP (which you forgot,
but which has been discussed in the past), which take &rest arguments
and therefore are a problem.  I don't think the -into-subseq version is
useful enough to justify the extra complexity.  I also don't think the
extra complexity of allowing the caller to pass in too many conses to
APPEND and REVAPPEND and get back the unused ones as a second value is
justified.  In fact, I think I would prefer to omit APPEND-INTO from the
proposal (CONCATENATE-INTO and NCONC should suffice) and therefore to
omit REVAPPEND-INTO also.  I support CONCATENATE-INTO and MAP-INTO.

Current practice:  Symbolics Common Lisp already has MAP-INTO.

	    (2) Provide a special form like:
		   (designate-subseq sequence start end)
	    that didn't actually allocate anything but provided an imple-
	    mentation-specific "handle" on the subsequence for use
	    in such expressions as the CONCATENATE expression above.
	    (They'd print as the subseq, and setf's of their elements
	    would destructively modify the original sequence.)	

This is identical to displaced arrays, unless you propose it to work
for lists as well, in which case it is nearly unimplementable.  I think
it should be dropped.

I'd support your proposal if you simplify it more or less along the lines
I suggested.  I don't support version 2 because there is too much in it.