Several articles about the delete function appeared recently.
This is a follow-up.
The simplest form of a call to delete is (delete item seq) where
seq is a sequence from which item is to be deleted.
Some authors pointed out that the effect of delete on seq is
unpredictable. Although a couple cited the standard for Common LISP,
which explicitly says the effect on seq is not specified, none said
why this is so.
Although I have not been involved with setting the LISP standard, I
have the impression that the standard does not require a specific
effect on seq because there are technical problems with defining the
delete function. The main problems I have found in writing my own
versions of delete are what to do if (1) the first element of seq is
to be deleted or (2) the result to be returned is nil.
If seq is a list and neither of these problems arises, I see
no reason why the effect on seq should not be specified. Without the
result of delete being specified in the standard, there is no reason
to have both remove and delete in the LISP language (except that
delete may be implemented more efficiently since seq provides a
convenient working list). I have been annoyed by this for years.
I suggest that the standard be revised to specify the effect of
delete on seq in some cases, particularly the one just mentioned.
I suggest that the effect should be the intuitively obvious one:
After delete is finished, seq should consist of all the original
cons cells of seq whose car's were not item and if the cdr of one
of these pointed at a cons cell which was deleted, it should now
either be at the end of the list or point at the first remaining
cons cell following it. This could be extended to apply in modified
form to cover the various options of delete.
If the result is not nil but problem (1) above occurs (i.e. the first
element is to be deleted), there is at least one solution (less
intuitively appealing) which might be considered. Call the first cons
cell of seq fir, and call first undeleted cons cell of seq elem. Then
the effect on seq is: set (car fir) to (car elem), set (cdr fir) to
(cdr elem), and do what is described above to any other remaining cons
cells in seq. If this were adopted, users would have to be careful of
how they deal with sublists of seq since cons cells in the middle of
seq might be cut out, but this seems a minor drawback.
I am aware of no technical problems with these proposals. Reactions?
What do you think, barmar?
In article <····@graceland.cme.nist.gov> ······@cme.nist.gov (Tom Kramer) writes:
>Some authors pointed out that the effect of delete on seq is
>unpredictable. Although a couple cited the standard for Common LISP,
>which explicitly says the effect on seq is not specified, none said
>why this is so.
The main reason is to permit implementors to programs it in whatever way is
most appropriate for their system. The primary reason for using
destructive versions of functions rather than the non-destructive versions
is efficiency, and restrictions on side effects could prohibit some
implementation-dependent optimizations.
For instance, in implementations with CDR-coding, RPLACD can be expensive
(it can allocate storage, introduce an invisible pointer, and result in
more page faulting when accessing the list); on such implementations,
DELETE might be optimized to shift the CARs rather than splice out a CDR (I
don't actually know whether any CDR-coded implementations do this for
DELETE, but I believe Genera has a similar optimization for NREVERSE and
maybe SORT).
Another reason for not specifying DELETE more precisely is tradition. Lisp
programmers have been taught for years that the right way to use
destructive functions is to use the value, not to depend on the side
effects. The Common Lisp designers learned DELETE that way, and felt no
need to "fix" it.
Even if we were to specify DELETE more precisely, you'd usually have to
follow this guideline, in order to handle the boundary cases of deleting
the first element or deleting all the elements. You might be able to get
around this by always having an extra element on the front that will never
get deleted or by shifting the first new element into the original first
cons, but those are kludges (MacLisp and Zetalisp used to use the first
kludge to implement "disembodied property lists", but in Common Lisp this
was replaced with SETF of GETF).
>I suggest that the standard be revised to specify the effect of
>delete on seq in some cases, particularly the one just mentioned.
It's too late to make such a change to the draft. At this point, we would
only make changes to fix serious problems in the language. This particular
wart has existed since the 60's, and many people consider it a feature.
>I suggest that the effect should be the intuitively obvious one:
>After delete is finished, seq should consist of all the original
>cons cells of seq whose car's were not item and if the cdr of one
>of these pointed at a cons cell which was deleted, it should now
>either be at the end of the list or point at the first remaining
>cons cell following it. This could be extended to apply in modified
>form to cover the various options of delete.
Last year we went over the destructive functions, and specified the
restrictions we believed were important. For instance, CLtL didn't specify
the behavior of NCONC, which is a much simpler function and has been
traditionally used for its precise side effects, so we fixed that. We
fixed the specification of NSUBSTITUTE and similar functions to say that
they may only modify the affected CARs. However, we consciously decided
*not* to restrict DELETE.
>If the result is not nil but problem (1) above occurs (i.e. the first
>element is to be deleted), there is at least one solution (less
>intuitively appealing) which might be considered. Call the first cons
>cell of seq fir, and call first undeleted cons cell of seq elem. Then
>the effect on seq is: set (car fir) to (car elem), set (cdr fir) to
>(cdr elem), and do what is described above to any other remaining cons
>cells in seq. If this were adopted, users would have to be careful of
>how they deal with sublists of seq since cons cells in the middle of
>seq might be cut out, but this seems a minor drawback.
>
>I am aware of no technical problems with these proposals. Reactions?
>What do you think, barmar?
But you still have to store the result back in case of NIL! And you even
pointed out that "users would have to be careful" in case the first element
was deleted.
If you want a version of DELETE whose behavior is strictly specified, you
can write it yourself. By leaving the official specification unfettered,
you have a choice of using a version that is optimized for the
implementation or one that has a precisely-known behavior. The Common Lisp
designers felt that giving the latter a standard name was important.
--
Barry Margolin, Thinking Machines Corp.
······@think.com
{uunet,harvard}!think!barmar
Does anyone know of the existence (or non-existence) of any simulators for
parallel versions of Lisp or Scheme? What I'm especially looking for is an
implementation that provides the "future" construct. I already know of the
existence of the *Lisp simulator from Thinking Machines, but are there others?
BTW, what I mean by `simulator' is something that'll run on a non-parallel
machine.
Thanks much in advance,
Joe
--
_____________________________________________________________________________
Joseph W. Lavinus, Virginia Tech email: ·······@csgrad.cs.vt.edu
"I don't believe in psychology. I believe in good moves." -- Bobby Fischer