discussion of Moon's comments re: ELIMINATE-FORCED-CONSING

[trwrb!smpvax1!jrg@ucbvax.Berkeley.EDU]

!   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.

The problem is that the :TARGET argument is used for two different
purposes.  One is to fill a subsequence of a useful sequence, as in
filling in a substring of a longer string.  The other is to recycle
storage (i.e., an obsolete sequence that would otherwise be garbage)
without regard for the previous contents of that storage (except to
insure type compatibility).  It seems useful to regard these as
different operations; although, except for the list case, they often can
be conveniently denoted using the same basic syntax, as in my proposal.
Some of the modifications you suggest to the proposal seem to stem from
assuming one or the other of these uses, disregarding the other.  Thus I
believe I should modify the proposal to have two different keywords that
can reflect the intention of a programmer.

For sake of argument, let's call the two keyword arguments :MODIFY (for
changing a subsequence of a useful sequence) and :RECYCLE (for recycling
a sequence that is otherwise garbage).  A list passed as a :RECYCLE
argument is re-used as a linear list made of conses to recycle.  CAR's
are ignored (i.e., it is not a tree of conses to re-use!).

!   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 believe this is correct.  My proposal will be altered to reflect this.

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

:TARGET-FROM-END specifies that the target sequence is filled from the
end with the result of the operation.  This allows the elements of the
result sequence to be placed into the target argument in reverse order.
This is not essential to the proposal.  It was included for sake of
symetry, in some sense of the word, since one might expect this
capability after surveying the other keywords available.  It would
become :MODIFY-FROM-END given the distinction in usage of the target
sequence already discussed.  I'll take it out if most people think it
excessive.

!       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.

I do not agree that this feature will usually be limited to vectors
rather than lists.  It is, however, tied to the :MODIFY/:RECYCLE
distinction.  A new proposal will address the return values in light of
this distinction.

!   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.

This would prevent the use of the :TARGET argument for filling in a
sublist, since the sublist is terminated.  It also breaks symetry with
other sequence types where a subsequence of a larger-than-needed TARGET
sequence is filled.  The problem is overloading :TARGET with the
semantics of :MODIFY and :RECYCLE.  For :MODIFY semantics, you want to
return a second value which is the tail of the list that was not used,
leaving that tail linked to the head that was used.  For :RECYCLE
semantics, you want as the first value the the null-terminated head of
the list that was used, and as the second value the tail that was not
used.  The difference is whether the first list value is null terminated
or not.  In addition, for a sequence with a fill-pointer used as the
RECYLE argument, the fill-pointer would be adjusted to point after the
last sequence element inserted.  As a MODIFY argument, the fill-pointer
would remain unchanged.  [Would the fill-pointer be extended if filling
the MODIFY argument used elements after the fill-pointer?  Or would
those elements of the MODIFY sequence after the fill pointer remain
unchanged?  I prefer the former.]

I oppose any change to the proposal that causes excess conses to be
thrown away.

!   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.

This provides maximum generality, but requires function call overhead
that might be avoided if storage is passed directly.  One might achieve
the same effect by supporting storage-freeing operations so Lisp could
keep a "free list" of recyclable storage to re-use rather than
allocating new storage.  Of course this leads to the desire to preserve
storage locality, including free-lists, thus a discussion of storage
allocation areas with free-lists per area, etc.  I would not oppose such
a mechanism, however.

!       (4) :TARGET-START and :TARGET-END keywords are supported.
!
!   These seem useful but should be named :OVERWRITE-START and
!   :OVERWRITE-END.

Well, I'd say :MODIFY-START and :MODIFY-END now.  :RECYCLE-START and
:RECYCLE-END are redundant with the normal :START and :END argument as
:RECYCLE implies the sequence passed in is just for storage recycling.
The :RECYCLE argument should not be used to modify a subsequence of a
useful sequence; use :MODIFY instead.

!   The functions SUBSEQ, COPY-SEQ, COPY-LIST, and BUTLAST need not be
!   modified, because the functionality is already available from
!   REPLACE.

I believe the :RECYCLE argument should be supported for these.

!   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).

Since it is well-defined when COPY-ALIST copies a cons, and since it is
well-defined that circularities and shared substructure are NOT
preserved in COPY-TREE, I see no reason not to include a :RECYLE
argument for these functions.  While modifiying an existing alist or
tree using the :MODIFY argument is ill-defined, the use of the :RECYLE
argument as a glob of available, linear cons storage is quite useful.

It would be useful, given the semantics above, to provide functions to
"flatten" an alist or a tree.  A new proposal will address this.

!   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.

Again, for sake of symetry, I (mildly) disagree.  The unused conses
should be returned, which is the interface complication you mention, I
guess.  Of course, the TARGET argument should be changed to :RECYLE for
ADJOIN.

!   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.

You're correct, I forgot SUBST.  However, I believe :RECYCLE should be
supported for SUBST, UNION, INTERSECTION, SET-DIFFERENCE, and
SET-EXCLUSIVE-OR.

!   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.

To reflect the clearer set of keywords, these would be changed to
support RECYCLE/MODIFY in my new proposal.

!   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.

I agree.  This was an oversight.

!   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.

OK, I'll remove the -INTO-SUBSEQ stuff.  But I disagree that passing in
too many conses and getting the unused ones back as a second value is
too complex.  I think this is a big win that is extremely useful.

!   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.

I'll submit a modified proposal for discussion.
-- Joe Ginder