Anyone have an explanation for the inability of the delete command to
delete the car from a list (at least in clisp)? I guess this falls
under the category of "never expect destructive list functions to act
how you expect."
CL-USER> (defvar testing)
TESTING
CL-USER> (setq testing '(a b c d))
(A B C D)
CL-USER> (delete 'a testing)
(B C D)
CL-USER> testing
(A B C D)
CL-USER> (delete 'b testing)
(A C D)
CL-USER> testing
(A C D)
-Nat
On May 13, 2:06 am, Nathaniel Calloway <····@cornell.edu> wrote:
> Anyone have an explanation for the inability of the delete command to
> delete the car from a list (at least in clisp)? I guess this falls
> under the category of "never expect destructive list functions to act
> how you expect."
>
> CL-USER> (defvar testing)
> TESTING
> CL-USER> (setq testing '(a b c d))
> (A B C D)
> CL-USER> (delete 'a testing)
> (B C D)
> CL-USER> testing
> (A B C D)
> CL-USER> (delete 'b testing)
> (A C D)
> CL-USER> testing
> (A C D)
>
> -Nat
[1]> (defvar testing)
TESTING
[2]> (setq testing '(a b c d))
(A B C D)
[3]> (setq testing (delete 'a testing))
(B C D)
[4]> testing
(B C D)
[5]> (setq testing (delete 'c testing))
(B D)
[6]> testing
(B D)
[7]> (lisp-implementation-type)
"CLISP"
[8]> (lisp-implementation-version)
"2.44 (2008-02-02) (built on reini [192.168.1.7])"
Nathaniel Calloway wrote:
> Anyone have an explanation for the inability of the delete command to
Common Lisp does not have "commands". It does have functions.
Thinking of a function as a command may warp your expectations.
Functions may have documented side effects, but you need to
examine whether you are expecting side effects that are not
guaranteed by documentation.
"Steven M. Haflich" <···@alum.mit.edu> writes:
> Nathaniel Calloway wrote:
>> Anyone have an explanation for the inability of the delete command to
>
> Common Lisp does not have "commands". It does have functions.
> Thinking of a function as a command may warp your expectations.
> Functions may have documented side effects, but you need to
> examine whether you are expecting side effects that are not
> guaranteed by documentation.
Comp.lang.lisp does not have "discussions". It does have pedants.
delete exists exclusively for its side effects because there is
another function *with the exact same behavior* and no side effects.
And for the record, simply because the behavior of a function is in the
documentation, doesn't mean it isn't retarded.
This ain't scheme or haskel we're talking about. CL has quite its fair
share of imperative commands...wait, no...operations, that's it.....I
mean methods...oh SHIT...FUNCTIONS.
-Nat
Nathaniel Calloway <····@cornell.edu> writes:
> "Steven M. Haflich" <···@alum.mit.edu> writes:
>
> > Nathaniel Calloway wrote:
> >> Anyone have an explanation for the inability of the delete command to
> >
> > Common Lisp does not have "commands". It does have functions.
> > Thinking of a function as a command may warp your expectations.
> > Functions may have documented side effects, but you need to
> > examine whether you are expecting side effects that are not
> > guaranteed by documentation.
>
> Comp.lang.lisp does not have "discussions". It does have pedants.
He's is not making a pedantic point here. There is a front-and-center
connotation to the notion of command, specifically that of "side effect",
that is misleading the OP here.
From the American Heritage Dictionary...
pedant
1. One who pays undue attention to book learning and formal rules.
2. One who exhibits one's learning or scholarship ostentatiously.
I don't see Steve's use as undue, since it's on topic. The attempt at
formality underscores important and relevant truth here. And as to
ostentation [not sure I've ever had occasion to use that word before],
I've known him a long time and while he's often a stickler for detail,
I think the purpose of his being so isn't to make a show, but rather to
make a helpful point and to document his reasons for making such a point.
> delete exists exclusively for its side effects because there is
> another function *with the exact same behavior* and no side effects.
Actually, this is definitely not true. The notion of
destructive adj. (of an operator) capable of modifying some
program-visible aspect of one or more objects that are either
explicit arguments to the operator or that can be obtained
directly or indirectly from the global environment by the
operator.
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_d.htm#destructive
The sense of "capable of" is critical here. It does not imply an
obligation, and conforming implementations have existed in which
there has been no side-effect. (They weren't very popular in the
market, mind you, but not because they didn't work by side-effect.)
The purpose of DELETE is not to do the impossible [which would be to
accomplish the OP's concern given CL's data model] but rather to
permit an implementation to perform the action done by REMOVE but
without the need to create new cells.
> And for the record, simply because the behavior of a function is in the
> documentation, doesn't mean it isn't retarded.
"Once you eliminate the impssible, whatever remains, no matter
how improbable, must be the truth."
--Sherlock Holmes
You may substitute "retarded" for "improbable" if you like. Personally,
I thought your tone somewhat really unnecessarily acid for civil discussion.
But your mileage may vary.
Anyway, back to Holmes, it seems to me that the strategies chosen by Lisp
really proceed by analysis of the fixed constraints of the language, and
that only ways to "fix" DELETE are:
* Change the basic linked-list data structure of CL to a more
complicated structure that does not permit a great deal of
other sharing that CL has. (Other languages have chosen to offer
different structures and to call them lists; that's ok, but it has
implications beyond DELETE.)
* Not offer the function DELETE and instead offer a SETF-like
abstraction atop it. (This would basically require you to
have the equivalent of DELETE but not advertise it; you might
call it DELETE-INTERNAL and then use DEFINE-MODIFY-MACRO in
order to make yourself a DELETE you like. This can,
incidentally, be done by making your own package and doing
appropriate symbol shadowing. But while doing so is easily
feasible, its consequent implication would be that DELETE
was not a simple function but rather a piece of syntax. This
would seem to me to complicate use of your then-modified DELETE
in the context of the functional programming style that some
try to use in CL [even in the presence of side-effect, since
"style" does not have to imply "ubiquitous use", or to re-use
your chosen term, being a "pedant"].)
> This ain't scheme or haskel we're talking about.
At the risk of accusations of pedantry, but really just to enable
search engines to find this thread better, I believe the correct
spelling is Haskell.
> CL has quite its fair
> share of imperative commands...wait, no...operations, that's it.....I
> mean methods...oh SHIT...FUNCTIONS.
The issue has nothing to do with Lisp's imperative nature.
Although I've used functional languages, I've not done a detailed
analysis of how they get away without this, so someone correct me if
I'm wrong, but the way they get away without the DELETE/REMOVE
distinction has always appeared to me to be through leaning more
heavily on the GC. The sense of imperative nature that DELETE
provides in CL seems to me to be not one imperative of action but one
of politely commanded (and, strictly speaking, ignorable) trust--that
is--to suggest that it is a reasonable and appropriate to prematurely
optimize the recycling of certain cells even when the dynamic
untangling of their availability has not yet been dynamically
detectable.
My intuition has always been (though I've not ever thought this
through in rigorous detail, so a theoretician who has is welcome to
correct me) that it is undecidable in general (it seems to me likely
subject to the Halting Problem) whether a compiler can detect
statically, even in the "relaxed comfort" of a strictly functional
language, that such an optimization is appropriate in all cases where
a user might decide it is useful in CL because it effectively promises
a mode of use of certain dynamically interconnected conses in the
future that doesn't seem to be knowable in all cases statically
(especially since in the general case it could depend on external data
not apparent to the compiler).
So I suspect this is more analogous to the question of whether
malloc/free is more efficient than cons/gc. Probably it is in some
cases. But the cost may be program error. Some people regard the use
of explicit allocation an important speed issue, and some regard it as
a foolish reliance on fallible human judgment. The two claims both
each some merit and the result is that an apples-to-apples (rather
than apples-to-oranges) comparison of the two [malloc/free and cons/gc]
is therefore difficult, just as a comparison of a functional language
and its use of remove-only + gc is hard to compare to a side-effecting
world and remove/delete are hard to compare.
Or so it seems to me. (I was up in the middle of the night for a few
minutes and I admit the possibility that I could just be tired and
missing something... But there are a great many thoughtful people in
this forum and I've rarely been ill-served by putting such mullings out
for conversation--someone will usually correct me when I'm wrong.)
> delete exists exclusively for its side effects because there is
> another function *with the exact same behavior* and no side effects.
WRONG WRONG WRONG
Although that seems very reasonable, it is not correct.
The EXCLUSIVE goal of destructive functions is SPEED, not destruction.
When the maximum speed can be achieved by simply returning the cdr,
delete will do just that.
Note that the following KMP comment is also dangerous in this regard
> The purpose of DELETE is not to do the impossible [which would be to
> accomplish the OP's concern given CL's data model] but rather to
> permit an implementation to perform the action done by REMOVE but
> without the need to create new cells.
Again, only if and when creating new cells reduces speed then the
comment holds. Otherwise it wouldn't.
·······@eurogaran.com escribi�:
>> delete exists exclusively for its side effects because there is
>> another function *with the exact same behavior* and no side effects.
>
> WRONG WRONG WRONG
> Although that seems very reasonable, it is not correct.
> The EXCLUSIVE goal of destructive functions is SPEED, not destruction.
> When the maximum speed can be achieved by simply returning the cdr,
> delete will do just that.
>
> Note that the following KMP comment is also dangerous in this regard
>
>> The purpose of DELETE is not to do the impossible [which would be to
>> accomplish the OP's concern given CL's data model] but rather to
>> permit an implementation to perform the action done by REMOVE but
>> without the need to create new cells.
>
> Again, only if and when creating new cells reduces speed then the
> comment holds. Otherwise it wouldn't.
I understand that DELETE's (and destructive functions in general) main
purpose is to reduce consing by means of reuse. Am I wrong?
Leandro
> I understand that DELETE's (and destructive functions in general) main
> purpose is to reduce consing by means of reuse. Am I wrong?
That is not wrong, only conceptually dangerous.
The EXCLUSIVE purpose of destructive functions is SPEED.
The fact that reducing consing increases speed in practically every
known case is in principle a different question altogether.
Note also that destructiveness refers to destruction achieved in other
much subtler ways:
Even if (delete a' testing) does not destroy the contents of testing,
things like
(rplacd (delete 'a testing) 'z)
would. Try it in your implementation.
<·······@eurogaran.com> wrote:
+---------------
| > I understand that DELETE's (and destructive functions in general) main
| > purpose is to reduce consing by means of reuse. Am I wrong?
|
| That is not wrong, only conceptually dangerous.
|
| The EXCLUSIVE purpose of destructive functions is SPEED.
| The fact that reducing consing increases speed in practically every
| known case is in principle a different question altogether.
+---------------
And just to keep the pedantry going, there are definitely situations
where re-use of conses *is* slower than new allocation/initialization.
For a specific example, consider a system with a generational garbage
collector (with Ungar-style "nursery"), when the list being DELETE'd
is already in a higher-generation GC area. Stores into that list structure
might be *very* expensive, due to the necessity of implementing the
write barrier required for a generational collector. In fact, if one
is using the operating system's page protections to implement the
write barrier [e.g., as CMUCL currently does for x86], then doing a
DELETE of a small but "old" list could be *much* more expensive than
allocating fresh conses for all of the non-deleted elements (a la REMOVE),
since it would require an O/S trap for each memory page modified during
the DELETE!
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Leandro Rios <··················@gmail.com> writes:
> ·······@eurogaran.com escribi�:
>>> delete exists exclusively for its side effects because there is
>>> another function *with the exact same behavior* and no side effects.
>> WRONG WRONG WRONG
>> Although that seems very reasonable, it is not correct.
>> The EXCLUSIVE goal of destructive functions is SPEED, not destruction.
>> When the maximum speed can be achieved by simply returning the cdr,
>> delete will do just that.
>> Note that the following KMP comment is also dangerous in this regard
>>
>>> The purpose of DELETE is not to do the impossible [which would be to
>>> accomplish the OP's concern given CL's data model] but rather to
>>> permit an implementation to perform the action done by REMOVE but
>>> without the need to create new cells.
>> Again, only if and when creating new cells reduces speed then the
>> comment holds. Otherwise it wouldn't.
>
> I understand that DELETE's (and destructive functions in general) main
> purpose is to reduce consing by means of reuse.
Correct.
> Am I wrong?
No, you're not wrong.
--
__Pascal Bourguignon__
·······@eurogaran.com writes:
> > delete exists exclusively for its side effects because there is
> > another function *with the exact same behavior* and no side effects.
>
> WRONG WRONG WRONG
> Although that seems very reasonable, it is not correct.
> The EXCLUSIVE goal of destructive functions is SPEED, not destruction.
> When the maximum speed can be achieved by simply returning the cdr,
> delete will do just that.
>
> Note that the following KMP comment is also dangerous in this regard
>
> > The purpose of DELETE is not to do the impossible [which would be to
> > accomplish the OP's concern given CL's data model] but rather to
> > permit an implementation to perform the action done by REMOVE but
> > without the need to create new cells.
>
> Again, only if and when creating new cells reduces speed then the
> comment holds. Otherwise it wouldn't.
Uh, look again. My words speak to permission, not imperative.
("permit...with the need to..." does not oblige anything to do
anything.) And the permission is there whether or not the
implementation uses it. And, incidentally, conforming implementations
are not required to be fast. That's managed by market pressure, not
by the spec. So "only if ... reduces speed" has no relevance with
respect to the standard.
> From: Nathaniel Calloway <····@cornell.edu>
> delete exists exclusively for its side effects because there is
> another function *with the exact same behavior* and no side effects.
No, you are completely wrong. DELETE exists exclusively for its
*SPEED*, because there is another function *with the exact same
return value* and no side effects, but which is much slower because
it does a lot more CONSing while building that return value. The
side effects are a *COST* of the speed. You can have it fast, or
you can avoid side effects, but you can't have both. You get to
choose which is more important for a given application.
It's the same with REVERSE (non-destructive, but slow because it
does lots of CONSing), and NREVERSE (fast, no CONSING at all, but
destructive).
> CL has quite its fair share of imperative commands.
No, you're completely wrong. CL doesn't have any commands at all.
It has only functions, macro operators, and a very few special
operators. Tell me three examples of something in CL that you
believe is a command.
> wait, no...operations, that's it.
You're getting closer. Functions perform data-processing
operations, such as modifying a place to have a new value,
allocating a new object and initializing its slots/places,
reading/writing I/O stuff, ...
> I mean methods.
In a generic way (as in ordinary English usage), method and
procedure and algorithm all mean the same thing. In Java, there are
three kinds of English.methods, namely primitive operations,
*static*methods* (which are really the same as functions), and
*instance*methods* (which really truly are OOP methods).
> oh SHIT...FUNCTIONS.
That's only part of the truth. CL also has special operators which
in the CAR position of a form cause Lisp to do low-level things or
set up unusual control structures, and macro operators which in the
CAR position of a form cause the form to be replaced by another
form containing special forms and/or function calls.
Remember that evaluating a form which expresses a function call can
*only* evaluate each element (except the first), and then pass the
resultant values as parameters to the function described by the
first element of the form.
By comparison, a form that expresses a special form (i.e. the first
element of the form is a special operator) can do any confangled
thing the special operator wants to do with the form. For example:
(SETQ sym ...) can modify the place defined by sym in both the case
of a lexical variable (a magic place accessible only to the
compiler, including the JIT compiler used by EVAL) and the case of
a special variable (the value cell of the symbol sym). In the case
of a special variable, it's pretty simple: There's some internal
function like SETVALUECELL which takes the symbol and the new value
as parameters, rather analagous to RPLACA which takes a CONS cell
and a new value. But in the case of a lexical variable, it's deep
innerds of the way Lisp is implemeted as to where the lexical
"value cell" really is located. It's not the value cell of the
symbol. Maybe it's on the stack. Maybe it's in a lexical-closure
object. You don't need to know or care how it's implemented.
···················@SpamGourmet.Com (Robert Maas, http://tinyurl.com/uh3t) writes:
> > From: Nathaniel Calloway <····@cornell.edu>
> > delete exists exclusively for its side effects because there is
> > another function *with the exact same behavior* and no side effects.
>
> No, you are completely wrong. DELETE exists exclusively for its
> *SPEED*,
This isn't true, though. (As I've explained in other posts on this
thread.) It's better to say that the thing that is different is what
the spec says: the _permission_ to make side-effects. What an
implementation makes of that permission is up to it.
A couple of additional notes beyond what I've said:
First, there was a time at which we were discussing the speed issue as
it applied to something and I said "why don't we write down the
algorithmic complexity of functions if we want to require that?". And
while it wasn't made a formal matter of record, the discussion of that
moment was by people who insisted that while speed was important, it
was equally important not to require that speed be the dominant thing.
That might preserve the right to do other optimizations, and it might
also just be to not accidentally mis-specify the details.
But also, ignoring all of that, there's a space issue, too. The spec
doesn't speak to space either, really. But if I make a huge list as
by something like (make-list n), where n is some huge number like
array-total-size-limit (but for lists), and then you want to do
something like delete an element, it may be that you will inevitably
cons in some implementations. (e.g., on the Lisp Machine, delete could
cause consing because it might wreck cdr-coding...) If you do cons,
you're lost if you've already consed more than half your memory in making
the original list. But DELETE, by its side-effect, preserves the right
of the lisp vendor to have provided relief in this case and to allow you
to win (even though you had no guaranteed right to win) in this case.
This has nothing to do with speed, and yet it follows from the side-effect
semantics. That's again why I say that the semantics is what it is, and
if you abstract it further, you do so at the peril of losing the meaning.
To switch topics momentarily, because I like analogies, people have
constructed any number of shrines to DEFVAR and DEFPARAMETER that try
to explain off the names. But in the end, DEFVAR does what the LispM
called setq-if-unbound and defparameter does setq. And there's really
no other difference. So you can describe one by talking about
parameter abstractions and the other by talking about var
abstractions--whatever you imagine those to be. But that doesn't
change the fact of the definition.
> because there is another function *with the exact same
> return value* and no side effects,
no potential for side effects.
DELETE doesn't reliably have side effects at all.
It has permission to make side effects of an unspecified nature.
> but which is much slower because
> it does a lot more CONSing while building that return value.
It might. But only if DELETE was not defined by
(SETF (SYMBOL-FUNCTION 'DELETE) (SYMBOL-FUNCTION 'REMOVE))
which is a conforming implementation, I believe.
> The
> side effects are a *COST* of the speed.
I don't agree.
> You can have it fast, or
> you can avoid side effects, but you can't have both. You get to
> choose which is more important for a given application.
>
> It's the same with REVERSE
That NREVERSE give permission to side effect and REVERSE doesn't.
Yes, that is the same.
> (non-destructive, but slow because it
> does lots of CONSing), and NREVERSE (fast, no CONSING at all, but
> destructive).
This isn't the right summary of that, though, IMO. YMMV.
I'm starting to repeat myself though. See my other posts on this thread.
On May 12, 9:06 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> Anyone have an explanation for the inability of the delete command to
> delete the car from a list (at least in clisp)? I guess this falls
> under the category of "never expect destructive list functions to act
> how you expect."
More specifically, destructive functions don't store the new value
back into the old place (variable). Functions deal with values,
not places. That's what Steve means when he says delete isn't a
command (although I don't see how that applies to setq, defun, etc.).
In order to change a variable in place, you would have to write
a *macro* that expands to a setf or setq form, as vanekl and Ken
showed you:
(defmacro setf-delete (val var)
`(setf ,var (delete ,val ,var)))
--Dan
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
danb <·········@gmail.com> writes:
> On May 12, 9:06 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> > Anyone have an explanation for the inability of the delete command to
> > delete the car from a list (at least in clisp)? I guess this falls
> > under the category of "never expect destructive list functions to act
> > how you expect."
>
> More specifically, destructive functions don't store the new value
> back into the old place (variable). Functions deal with values,
> not places. That's what Steve means when he says delete isn't a
> command (although I don't see how that applies to setq, defun, etc.).
Right.
> In order to change a variable in place, you would have to write
> a *macro* that expands to a setf or setq form, as vanekl and Ken
> showed you:
>
> (defmacro setf-delete (val var)
> `(setf ,var (delete ,val ,var)))
Hmm. While the remark about the macro is correct, you want to be careful
about writing macros that deal with side-effects if they are going to
rearrange the order of things or if they're going to evaluate the "place" [1]
more than once, particularly when such places might have subforms that
are (or could be) implicated by the location being assigned.
(defparameter *foo* (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))
=> ((1 2 3) (4 5 6) (7 8 9))
(let ((i 0))
(setf-delete 5 (nth (incf i) *foo*))
(list *foo* i))
=> (((1 2 3) (7 8 9) (7 8 9)) 2)
It's a bad idea to write macros that make too many presuppositions
about the nature of the desired argument. e.g., you could mostly
correct your macro by just inserting
(check-type var symbol)
at the top of the macro, before the expansion. But that would limit
its use.
You probably want to learn about DEFINE-MODIFY-MACRO [2].
I suggest the following definition will get you in a lot less trouble:
(defun xdelete (list element &rest keys)
(apply #'delete element list keys))
(define-modify-macro delete-from (element &rest keys) xdelete)
(defparameter *foo* (list (list 1 2 3) (list 4 5 6) (list 7 8 9)))
=> ((1 2 3) (4 5 6) (7 8 9))
(let ((i 0))
(delete-from (nth (incf i) *foo*) 5)
(list *foo* i))
=> (((1 2 3) (4 6) (7 8 9)) 1)
Naming Trivia: In MACLISP, the function XCONS was used to refer
to a function like CONS but with the arguments "eXchanged". I
sometimes still use the convention of a prefix X to highlight
an argument order shift on another, more well-known, function.
Hence my use of the name XDELETE. A rearranged DELETE is more
useful for use with DEFINE-MODIFY-MACRO given that it likes its
place argument first.
[1] Glossary: place
http://www.lispworks.com/documentation/HyperSpec/Body/m_defi_2.htm#define-modify-macro
[2] DEFINE-MODIFY-MACRO
http://www.lispworks.com/documentation/HyperSpec/Body/26_glo_p.htm#place
> danb <·········@gmail.com> writes:
> > (defmacro setf-delete (val var)
> > `(setf ,var (delete ,val ,var)))
On May 13, 5:27 am, Kent M Pitman wrote:
> You probably want to learn about DEFINE-MODIFY-MACRO
Very good. Thanks for pointing that out, Kent.
--Dan
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
Nathaniel Calloway wrote:
> Anyone have an explanation for the inability of the delete command to
> delete the car from a list (at least in clisp)? I guess this falls
> under the category of "never expect destructive list functions to act
> how you expect."
>
>
> CL-USER> (defvar testing)
> TESTING
> CL-USER> (setq testing '(a b c d))
> (A B C D)
> CL-USER> (delete 'a testing)
> (B C D)
The (B C D) you see above is the value returned by delete. Obvious,
perhaps, but I am just warming up.
> CL-USER> testing
> (A B C D)
If you are familiar at all with programming (I do not know how
experienced you are) you will realize delete does not see the /variable/
testing, the caller pulls a value out of that variable and passes it to
delete. ie, delete sees (a b c d), not "testing".
All delete can do is dutifully return a list without A, and whaddaya
know, it can do just by returning the CDR of the list received (since A
appears only in the car of the first cons).
> CL-USER> (delete 'b testing)
> (A C D)
Now delete is forced to do some work, and makes the cdr of the first
cons the cdr of the second cons, effectively discarding the second cons
from the structure received.
Another way for you to understand this is to try to write a destructive
version of my-delete that does behave they way you expected. Methinks
the light will go on before you write a line of code.
kzo
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
>> CL-USER> (defvar testing)
>> TESTING
>> CL-USER> (setq testing '(a b c d))
>> (A B C D)
>> CL-USER> (delete 'a testing)
>> (B C D)
>
> The (B C D) you see above is the value returned by delete. Obvious,
> perhaps, but I am just warming up.
Uh huh....I know how lisp works.
>> CL-USER> testing
>> (A B C D)
>
> If you are familiar at all with programming (I do not know how
> experienced you are) you will realize delete does not see the
> /variable/ testing, the caller pulls a value out of that variable and
> passes it to delete. ie, delete sees (a b c d), not "testing".
This is wrong. When you don't try to change the car, it goes to where
testing points to the memory and changes the various cons'es, IE it
"sees" where testing is pointing. Don't confuse this with the
differences in the eval loop between macros and functions.
> All delete can do is dutifully return a list without A, and whaddaya
> know, it can do just by returning the CDR of the list received (since
> A appears only in the car of the first cons).
Well, sure, but that's not the issue. The issue is why it doesn't
change the assignment of testing.
>> CL-USER> (delete 'b testing)
>> (A C D)
>
> Now delete is forced to do some work, and makes the cdr of the first
> cons the cdr of the second cons, effectively discarding the second
> cons from the structure received.
You skipped the last line showing that delete is in fact
destructive...but only when you aren't changing the car.
> Another way for you to understand this is to try to write a
> destructive version of my-delete that does behave they way you
> expected. Methinks the light will go on before you write a line of
> code.
My problem isn't writing code, it's understanding why exactly this
behavior was chosen. This is indicative of something deeper in lisp
than anything you have touched on. I'm assuming it has to do with how
variables are assigned. What I fail to understand is why exactly lisp
doesn't have a problem changing where a particular cdr points, but
does have a problem with changing where a variable points. My feeling
is that because variables are handled differently in some way,
whomever coded delete sacrificed consistent behavior for consistent
code. (For the record, if this is the case, I think it is silly:
either smash everything into the same namespace like scheme and treat
it all the same, and have your theoretical consistency, or just make
it work intuitively).
And that brings me to another question: Why even include delete at
all? Remove works just fine in a non-destructive way, and we can
always just (setq testing (remove 'a testing)). Is there any purpose
to having a function that will destructively delete anything but the
car? Perhaps, but I sure can't think of one.
-Nat
In article <·············@cornell.edu>,
Nathaniel Calloway <····@cornell.edu> wrote:
> My problem isn't writing code, it's understanding why exactly this
> behavior was chosen. This is indicative of something deeper in lisp
> than anything you have touched on. I'm assuming it has to do with how
> variables are assigned. What I fail to understand is why exactly lisp
> doesn't have a problem changing where a particular cdr points, but
> does have a problem with changing where a variable points.
It's because parameters are passed by value, not reference. So when you
call:
(delete 'a testing)
the DELETE function doesn't receive the variable TESTING, it just
receives the list that TESTING refers to. It can't change the value of
the variable because it doesn't have a reference to TESTING's value cell.
It's the same as the following:
(defvar testing2 3)
(1+ testing2) => 4
testing2 => 3
The 1+ funtion receives 3 as the parameter, not a reference to
TESTING2's value cell, so it can't update the variable's value.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
In article <·············@cornell.edu>,
Nathaniel Calloway <····@cornell.edu> wrote:
> And that brings me to another question: Why even include delete at
> all? Remove works just fine in a non-destructive way, and we can
> always just (setq testing (remove 'a testing)). Is there any purpose
> to having a function that will destructively delete anything but the
> car? Perhaps, but I sure can't think of one.
It's purely an efficiency thing, because DELETE doesn't have to cons
while REMOVE usually does.
If we were redesigning it from scratch, perhaps this would have been a
keyword option, i.e. (remove 'a testing :reuse t). But DELETE and
REMOVE have a long history, so they were kept for historical reasons
(although now that I think of it, Maclisp called the analogous functions
DELQ and REMQ -- it used DELETE and REMOVE for the :TEST #'EQUAL
variants -- so it isn't really maintaining compatibility).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin <······@alum.mit.edu> writes:
> In article <·············@cornell.edu>,
> Nathaniel Calloway <····@cornell.edu> wrote:
>
>> And that brings me to another question: Why even include delete at
>> all? Remove works just fine in a non-destructive way, and we can
>> always just (setq testing (remove 'a testing)). Is there any purpose
>> to having a function that will destructively delete anything but the
>> car? Perhaps, but I sure can't think of one.
>
> It's purely an efficiency thing, because DELETE doesn't have to cons
> while REMOVE usually does.
>
> If we were redesigning it from scratch, perhaps this would have been a
> keyword option, i.e. (remove 'a testing :reuse t). But DELETE and
> REMOVE have a long history, so they were kept for historical reasons
> (although now that I think of it, Maclisp called the analogous functions
> DELQ and REMQ -- it used DELETE and REMOVE for the :TEST #'EQUAL
> variants -- so it isn't really maintaining compatibility).
I love you. Thanks for a real answer. They are rare now days.
I was probably born after the days when the efficiency difference
between delete and remove was an issue.
This somewhat explains why everyone is referencing delete as if it
didn't have side effects, even though it does. I assumed that like
push, pop, setq, etc, the function existed for these side effects, not
for a historical efficiency concern.
-Nat
Nathaniel Calloway wrote:
> Barry Margolin <······@alum.mit.edu> writes:
>
>> In article <·············@cornell.edu>,
>> Nathaniel Calloway <····@cornell.edu> wrote:
>>
>>> And that brings me to another question: Why even include delete at
>>> all? Remove works just fine in a non-destructive way, and we can
>>> always just (setq testing (remove 'a testing)). Is there any purpose
>>> to having a function that will destructively delete anything but the
>>> car? Perhaps, but I sure can't think of one.
>> It's purely an efficiency thing, because DELETE doesn't have to cons
>> while REMOVE usually does.
>>
>> If we were redesigning it from scratch, perhaps this would have been a
>> keyword option, i.e. (remove 'a testing :reuse t). But DELETE and
>> REMOVE have a long history, so they were kept for historical reasons
>> (although now that I think of it, Maclisp called the analogous functions
>> DELQ and REMQ -- it used DELETE and REMOVE for the :TEST #'EQUAL
>> variants -- so it isn't really maintaining compatibility).
>
>
> I love you. Thanks for a real answer. They are rare now days.
I think you misunderstood Barry.
The naming convention is for historic reasons. Not the existence.
> I was probably born after the days when the efficiency difference
> between delete and remove was an issue.
Okay, my machine is four years old -- but, when exactly were you born?
Check out a little toy example:
CL-USER> (defpackage :test-delete (:use :cl))
#<PACKAGE "TEST-DELETE">
CL-USER> (in-package :test-delete)
#<PACKAGE "TEST-DELETE">
TEST-DELETE> (time (defparameter *list* (loop for i from 0 below
10000000 collect (random 1000))))
Evaluation took:
2.748 seconds of real time
2.24814 seconds of user run time
0.296018 seconds of system run time
[Run times include 1.876 seconds GC run time.]
0 calls to %EVAL
0 page faults and
80,019,264 bytes consed.
*LIST*
Okay, 10 million values, nothing major, right? Now check out remove:
TEST-DELETE> (time (length (remove (random 1000) *list*)))
Evaluation took:
4.783 seconds of real time
3.884242 seconds of user run time
0.48403 seconds of system run time
[Run times include 3.74 seconds GC run time.]
0 calls to %EVAL
0 page faults and
79,944,408 bytes consed.
9989995
One call to remove takes nearly 5 seconds and 80 MB of RAM.
Compare delete:
TEST-DELETE> (time (length (delete (random 1000) *list*)))
Evaluation took:
0.996 seconds of real time
0.564035 seconds of user run time
0.084005 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
9990096
Less than one second, *no* memory usage. If you paid attention to what
other people wrote, this does not come as a surprise.
Now consider a real world scenario where you have not 10 million
numbers, but, say, a billion. Scale everything by 100:
Remove will use 8 GB of RAM, delete will use none.
I don't know how much RAM you have ...
> This somewhat explains why everyone is referencing delete as if it
> didn't have side effects, even though it does.
No. Not "somewhat". This explains it. The sequence passed to delete
must not be used afterwards. The CLHS says that the behavior is
undefined. delete could just make that sequence be the birthday of the
lead programmer, if it wanted to.
> I assumed that like
> push, pop, setq, etc, the function existed for these side effects, not
> for a historical efficiency concern.
>
> -Nat
>
On 13 Kvì, 09:51, Peter Hildebrandt <·················@gmail.com>
wrote:
>
> No. Not "somewhat". This explains it. The sequence passed to delete
> must not be used afterwards. The CLHS says that the behavior is
> undefined. delete could just make that sequence be the birthday of the
> lead programmer, if it wanted to.
Does it? I do not see word undefined on this CLHS page, and at least
for vectors it is much more specific. I would certainly hope that I
can declare the variable passed to delete as vector of some type
(e.g., string or bit-vector) and rely on delete not ruining this
declaration. Or do I misunderstand?
Tomas Zellerin wrote:
> On 13 Kv�, 09:51, Peter Hildebrandt <·················@gmail.com>
> wrote:
>> No. Not "somewhat". This explains it. The sequence passed to delete
>> must not be used afterwards. The CLHS says that the behavior is
>> undefined. delete could just make that sequence be the birthday of the
>> lead programmer, if it wanted to.
>
> Does it? I do not see word undefined on this CLHS page,
Well, ok, I was a little unprecise here. Quoting from the hyperspec:
"delete, when sequence is a list, is *permitted to setf any part*, car
or cdr, of the top-level list structure in that sequence."
It does not say what it may setf it to, does it?
Peter
> From: Nathaniel Calloway <····@cornell.edu>
> I was probably born after the days when the efficiency difference
> between delete and remove was an issue.
Nope. When there are orders of magnitude difference in speed
between two different operations, it *does* make a difference, even
now, *if* the operations are done often enough to show up in
perceived slowness of the software. Nowadays we expect our software
to do a lot more than we expected it to do during the same length
of time twenty years ago, so what used to take a minute then takes
a microsecond, so instead we now do something that would have taken
a year then but takes five seconds now. That itty bitty thing we
did twenty years ago, that took only a minute, if it had taken a
hundred times as long, it would have been too slow. And that huge
gigantic computation that takes five seconds now, if it instead
takes five hundred seconds, that's too slow. You still need to
avoid doing grossly wasteful operations, but only if your task is
huge enough that you can actually see the slowness. Even one order
of magnitude different in speed can be crucial, like if you were
expecting a click at the Web browser to take at most 3 seconds, but
it takes 30 seconds instead, that would be a real pain. Tell me the
truth. Would you ever notice the difference between 3-second and
30-second response time when you click on a Web link? For some
applications, the efficiency difference between delete and remove
can be that one order of magnitude that makes a task unbearably
slow with remove but fast enough with delete.
> This somewhat explains why everyone is referencing delete as if
> it didn't have side effects, even though it does.
No, you're wrong, again! DELETE may have side effects, but they are
unpredictable, not specified by the language specification, so you
can't rely on them, and you should go to lengths to ever have to
even look at them. If you ever see the side effects, you've made
some kind of logic error in your software. Maybe you simply forgot
to clobber an unusable value to NIL, and later you accidently
looked at it and was puzzled by its strange value. For example:
* (length (setq foo (loop for ix from 0 to 100 collect (random 42))))
101
;That step was fine.
* foo
(35 18 26 26 31 38 27 29 9 0 1 19 40 12 29 37 12 13 2 3 20 0 41 41 5 6 39 29 39
24 0 1 32 6 8 4 25 34 31 32 33 23 39 11 1 4 23 14 10 3 34 24 0 27 21 25 30 25
31 0 19 18 13 9 37 18 39 29 14 3 21 7 31 38 5 29 22 23 17 24 19 15 28 21 38 22
32 14 3 41 6 15 17 23 10 36 21 10 0 11 27)
;Looking at foo was fine. It is a list of 101 different random numbers.
* (setq baz (sort foo #'<))
(0 0 0 0 0 0 1 1 1 2 3 3 3 3 4 4 5 5 6 6 6 7 8 9 9 10 10 10 11 11 12 12 13 13
14 14 14 15 15 17 17 18 18 18 19 19 19 20 21 21 21 21 22 22 23 23 23 23 24 24
24 25 25 25 26 26 27 27 27 28 29 29 29 29 29 30 31 31 31 31 32 32 32 33 34 34
35 36 37 37 38 38 38 39 39 39 39 40 41 41 41)
;In that step you failed to clobber FOO to be something reasonable.
;FOO is now unpredictably different from anything meaningful.
;From now on, you must remember *not* to look at FOO again.
* foo
(35 36 37 37 38 38 38 39 39 39 39 40 41 41 41)
;Dammit, you looked at foo. You forgot that its value is
; unpredictable and you should never look at it again.
;So you see some random segment shared with BAZ and you're all
; confused why it should have that particular value.
;Get it in your head: It is *not* required by the spec to have any
; particular value whatsoever. But by the logic of Lisp, it must have
; *some* value. It's just that *what* value it happens to have is
; anybody's guess, not anything you should bother with.
> I assumed that like push, pop, setq, etc, the function existed
> for these side effects, not for a historical efficiency concern.
Instead of guessing that purpose of each function, you should RTFM!!
PUSH and POP are macros which generate code for specific side
effects *and* for specific return values.
SETQ is a special operator which produces specific side effect and
returns a specific value.
DELETE and REMOVE are functions that are purely for return value,
not for side effects, but with different tradeoffs between speed
and purity. DELETE is fast, but clobbers stuff in unpredictable
ways. REMOVE is slow, but pure, doesn't clobber anything.
Next time you look in the HyperSpec or other manual to find the
definition of a function or special operator or macro operator,
please try to understand carefully what are the intended
(well-defined, expected) consequences, and what are undefined
side-effects purely for purpose of efficiency.
(describe 'delete)
..
Returns a sequence formed by destructively removing the specified Item from
the given Sequence.
Do you see anything *defining* precisely what side effects it'll do? No!!!
Only the return value is specified precisely.
(describe 'setq)
..
Set the variables to the values. If more than one pair is supplied, the
assignments are done sequentially. ...
Do you see how the side-effect of setting a variable to have a
value is clearly defined?
Actually that documentation there (in CMUCL) is deficient in one
aspect, it doesn't tell what the return value should be. The
HyperSpec is better in this case, telling both return value and
side effects:
<http://www.famsolberg.com/HyperSpec/Body/s_setq.htm>
..
result---the primary value of the last form, or nil if no pairs were
supplied.
..
(setq var1 form1 var2 form2 ...) is the simple variable assignment
statement of Lisp. First form1 is evaluated and the result is stored
in the variable var1, then form2 is evaluated and the result stored in
var2, and so forth. setq may be used for assignment of both lexical
and dynamic variables.
I personally recommend using (DESCRIBE ...) only to verify whether
you are thinking of the correct name, but the HyperSpec to really
learn what the function or special operator or macro operator is
supposed to do that you can rely on (modulo occasional bugs).
Nathaniel Calloway <····@cornell.edu> wrote on Tue, 13 May 2008:
> This somewhat explains why everyone is referencing delete as if it
> didn't have side effects, even though it does. I assumed that like
> push, pop, setq, etc, the function existed for these side effects
While it's clear that the OP was quite confused about Common Lisp, and
unfortunately arrogant and bitter when people tried to help ... he does
seem, at last, to have a reasonable point, which I'm not sure has been
addressed in the huge volume of replies on this topic.
Namely: Why wasn't DELETE defined to be a macro like PUSH and POP?
There are all the usual tradeoffs between macros and functions, like
the lack of ability to FUNCALL macros, etc. But the real question is:
why did the decision come down differently for DELETE than it did for
PUSH and POP? The functionality of the three seems roughly analogous,
suggesting that the macro/function tradeoffs would be the same.
Is it merely for historical consistency? Or is there a deeper reason why
DELETE was a function (leading to the OP's confusion) but PUSH/POP were
able to have "more convenient" implementations?
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
You see, wire telegraph is a kind of a very, very long cat. You pull his tail
in New York and his head is meowing in Los Angeles. Do you understand this?
And radio operates exactly the same way: you send signals here, they receive
them there. The only difference is that there is no cat.
-- Albert Einstein, when asked to describe radio
Don Geddis <···@geddis.org> writes:
> Namely: Why wasn't DELETE defined to be a macro like PUSH and POP?
> There are all the usual tradeoffs between macros and functions, like
> the lack of ability to FUNCALL macros, etc. But the real question is:
> why did the decision come down differently for DELETE than it did for
> PUSH and POP? The functionality of the three seems roughly analogous,
> suggesting that the macro/function tradeoffs would be the same.
Well, PUSH and POP really have to be macros, or else they don't make any
sense at all. Without the rebinding of the value, they would be the
same as CONS and CAR.
> Is it merely for historical consistency? Or is there a deeper reason why
> DELETE was a function (leading to the OP's confusion) but PUSH/POP were
> able to have "more convenient" implementations?
If you want DELETE to be a macro, then symmetry would also dictate
that REMOVE should be a macro as well. But then you lose some
functionality:
1. You can't use higher-order functions like MAP, MAPCAR, etc. because
they require functions as arguments, not macros.
2. You lose the flexibility to assign the result to a different
variable. Now this is likely not a big issue with DELETE, since you
can't really trust what is in the old variable, but with REMOVE it
can be a major issue, where you may want to keep pointers to both
before and after. And you can't do that if the operators
"helpfully" rebind the inputs for you.
3. You are then also limited in what arguments you can pass to DELETE,
since it has to be a SETF-able place. So that means that the
following code would break:
(DELETE 'a (list 'a 'b 'c 'd 'e))
because the list is not something you can setf.
Now I have seen people define additional macros to provide the
convenience that you request. Something along the lines of
(defmacro deletef (item place &rest other-args)
`(setf ,place (delete ,item ,place ,@other-args)))
I suppose that there are some potential issues with the simple macro
because of multiple evaluation of PLACE. I'm not quite sure what the
solution to that would be, though. Is there a way to improve it so that
(deletef 'a (aref table (incf i)))
would work properly?
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) wrote on 15 May 2008 09:1:
> Don Geddis <···@geddis.org> writes:
>> Namely: Why wasn't DELETE defined to be a macro like PUSH and POP?
> 3. You are then also limited in what arguments you can pass to DELETE,
> since it has to be a SETF-able place. So that means that the
> following code would break:
> (DELETE 'a (list 'a 'b 'c 'd 'e))
> because the list is not something you can setf.
Ah. Good point.
> (defmacro deletef (item place &rest other-args)
> `(setf ,place (delete ,item ,place ,@other-args)))
> I suppose that there are some potential issues with the simple macro
> because of multiple evaluation of PLACE. I'm not quite sure what the
> solution to that would be, though. Is there a way to improve it so that
> (deletef 'a (aref table (incf i)))
> would work properly?
You probably want DEFINE-MODIFY-MACRO.
(You can write the regular macro "properly" yourself, but D-M-M makes it
easier.)
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
So far as I can remember, there is not one word in the Gospels in praise of
intelligence. -- Bertrand Russell
···@sevak.isi.edu (Thomas A. Russ) writes:
> Now I have seen people define additional macros to provide the
> convenience that you request. Something along the lines of
>
> (defmacro deletef (item place &rest other-args)
> `(setf ,place (delete ,item ,place ,@other-args)))
>
I already responded to this in another subthread of this thread.
Rather than belabor what I said there, let me add the one useful
bit of info I had left out:
http://www.maclisp.info/pitmanual/files.html#19.5.3
Fortunately, the cryptic nature of the URL hides the punchline
to this joke. You'll have to click through to see if you don't
already know. :)
Don Geddis <···@geddis.org> writes:
> Nathaniel Calloway <····@cornell.edu> wrote on Tue, 13 May 2008:
>> This somewhat explains why everyone is referencing delete as if it
>> didn't have side effects, even though it does. I assumed that like
>> push, pop, setq, etc, the function existed for these side effects
>
> While it's clear that the OP was quite confused about Common Lisp, and
> unfortunately arrogant and bitter when people tried to help ... he does
> seem, at last, to have a reasonable point, which I'm not sure has been
> addressed in the huge volume of replies on this topic.
>
> Namely: Why wasn't DELETE defined to be a macro like PUSH and POP?
It wasn't defined in the same plane. DELETE is but NREMOVE with an
historical name.
> There are all the usual tradeoffs between macros and functions, like
> the lack of ability to FUNCALL macros, etc. But the real question is:
> why did the decision come down differently for DELETE than it did for
> PUSH and POP? The functionality of the three seems roughly analogous,
> suggesting that the macro/function tradeoffs would be the same.
>
> Is it merely for historical consistency? Or is there a deeper reason why
> DELETE was a function (leading to the OP's confusion) but PUSH/POP were
> able to have "more convenient" implementations?
"Usually", DELETE is not passed the contents of a variable. It's just
passed a list, that happens not to be useful thereafter.
This usage:
(defun f (list)
(delete 0 (mapcar (lambda (x) (- (* x 3) 2)) list)))
is more typical (of lisp functional style) than:
(let ((list (list 1 2 3)))
(setf list (delete 2 list))
(setf list (delete 3 list))
list)
If you go this way, ALL the lisp operators (that take arguments) may
take actually the value of a variable, and the result may be stored
into that same variable, so they should all be defined as place
modifying macros:
(deletef item list) for (setf list (delete item list))
(cdrf cons) (setf cons (cdr cons))
(prin1-to-string-f thing) (setf thing (prin1-to-string thing))
(/f number) (setf number (/ number))
(*f x 2) (setf x (* x 2))
...
So you'd add about 900 new macros.
And why stop there? After all, we can go on generating all the little
program pieces. If we do that enough, we'll include in Common Lisp
all the small programs!
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
> If you go this way, ALL the lisp operators (that take arguments) may
> take actually the value of a variable, and the result may be stored
> into that same variable, so they should all be defined as place
> modifying macros:
>
> (deletef item list) for (setf list (delete item list))
Just for historical completeness, DELETEF was the Maclisp name for
DELETE-FILE. This is tickling a vague memory that there was a discussion
of adding a DELETEF as a SETF variant and having people say "maybe not".
Enough years have passed that this is probably not a fear any more.
But on the LispM, with both the old Maclisp names and the new CL names
active in the same environment (differing only by package) you can see
the fear it would lead to in designers not wanting to lead people down
the path to accidental file deletion.
Kent M Pitman <······@nhplace.com> writes:
> ···@informatimago.com (Pascal J. Bourguignon) writes:
>
>> If you go this way, ALL the lisp operators (that take arguments) may
>> take actually the value of a variable, and the result may be stored
>> into that same variable, so they should all be defined as place
>> modifying macros:
>>
>> (deletef item list) for (setf list (delete item list))
>
> Just for historical completeness, DELETEF was the Maclisp name for
> DELETE-FILE. This is tickling a vague memory that there was a discussion
> of adding a DELETEF as a SETF variant and having people say "maybe not".
>
> Enough years have passed that this is probably not a fear any more.
> But on the LispM, with both the old Maclisp names and the new CL names
> active in the same environment (differing only by package) you can see
> the fear it would lead to in designers not wanting to lead people down
> the path to accidental file deletion.
Yes, indeed :-)
I guess everybody became better typists with time, so we're not
restricted to short names anymore.
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
> I guess everybody became better typists with time, so we're not
> restricted to short names anymore.
Well, that plus the fact that with more memory, you didn't have to worry
about squeezing every last byte out of the names.
IIRC the PDP-10 had (at one time) 6-bit bytes, with a word length of 36
bits, so the operating system (ITS) command names were really truncated
to only 6 characters, so they would all only take up a single machine
word. That led to the interesting bit of trivia that you could kill all
of your running jobs by typing "massachusetts" at the command line. It
happens to share the same 6-character prefix with "massacre".
["massacre" which was a mass version of "kill". "kill" would kill one
job, "massacre" all of them.]
--
Thomas A. Russ, USC/Information Sciences Institute
···@sevak.isi.edu (Thomas A. Russ) writes:
> IIRC the PDP-10 had (at one time) 6-bit bytes, with a word length of
> 36 bits
Correct word length, but the PDP-10 has no fixed byte length. The
byte instructions works with any length between 1 and 36. (Leaving
aside the extended architecture one-word global byte pointers.) Some
software uses 6-bit bytes to store an ASCII subset, but 7-bit bytes
are also commonly used for text, and recently 8-bit bytes has proven
useful.
> From: Nathaniel Calloway <····@cornell.edu>
> My problem isn't writing code, it's understanding why exactly
> this behavior was chosen.
You're talking about the way functions in lisp take values and
return values, and how there's no magic way a function can learn
where a value given to it came from hence no way to backtrack to
cause side effects whereever that value came from? Why do you care
why *that* behaviour was chosen? It's the same in C. If you pass a
value to a function, the function has no idea where it came from,
and can't backtrack to modify whereever that value came from.
One difference is that C allows direct access to memory cells via
address pointers, whereby if you pass the address of a value
instead of the value itself then the function getting that address
*can* directly modify memory at that location, and in adjacent
locations, making everything in the whole system susceptable to
modification, such that you can't trust any function you *ever*
pass an address too.
void clobber (int* ptr) {
for (ix=-60000; ix<=60000; ix++) *(ptr+ix)=42;
}
I think I got that syntax correct. If not, you can fix it to do
what I intended, right?
So with the ability to pass raw machine addresses to functions,
and the ability to do address arithmetic, "all hell breaks loose".
Common Lisp's designers decided that allowing that was a very bad idea.
So in Common Lisp, you can't pass the addresses of things, only
ordinary values, such as symbols, CONS cells, arrays, strings,
numbers, etc. And given such a passed value, the only operations
you can perform on it are properly defined operations within that
object itself, not inside other objects that might happen to point
to it, such as a variable in some other scope where you obtained
that value that was passed to the function.
> I'm assuming it has to do with how variables are assigned.
In a sense, there's no such thing as a variable in Lisp.
Instead there are lots of different kinds of places where values
may be stored:
- In the value cell of some symbol. You need to be passed that
symbol in order to know where the value cell is so that you can
then replace the current value with some other value.
- Within the property list of some symbol. You need to be passed that
symbol, and somehow you need to know the key to specify which
key-value pair needs the value changed.
- In the CAR or CDR position of some CONS cell. You need to be
passed that CONS cell, and you need to have some way to decide
whether it's the CAR cell or the CDR cell where the value is to
be changed.
- An element of an array. You need to be passed that ARRAY object,
and also you need to have some way to know which index(s) to use
to select the element to be changed.
- A character in a string. A string is a type of vector, which is a
one-dimensional array, so you need to have a way to decide what
index to use to find the character.
- Within an assoc list. You need to be passed the assoc list, and
somehow you need to know the key to specify which key-value pair
needs the value changed.
- Within some structure or CLOS object, more complicated what
places are available, but you need to be passed that structure
of object and you need additional information as to which slot
to change.
In all those cases, if a function is just passed a value that came
from one of those kinds of places, it has no way to know what kind
of place it came from, and no way to know which specific object of
that type it came from, hence not the slightest idea what place
needs changing.
Macros such as SETF are completely different. They don't have the
value from a place, they have the actual expression used to produce
a value, so they *can* backtrack the logic of getting the value to
see how that value might be changed instead of merely fetched. For
example:
(setf (car (cdr (cdr x))) 5)
sees that the last step to get the value would have been CAR,
so RPLACA can be used to change it instead.
But note that there are values that don't come from any place at all!
They are *computed* and not stored anywhere (except on the stack or
in a machine register). For example (+ 3 9) produces the value 12,
which is not the value in any place. So if you tried to do SETF of
such a value:
(setf (+ 3 9) 5)
it can't possibly work, because there's no place to backtrack.
Do you understand the difference between a place and the value in
that place? Do you understand how a macro can figure out what place
you're talking about by analyzing the source code passed to it, but
a function just gets the resultant value from evaluating that
source code, which may fetch from a place or not, and so a function
doesn't have any information to figure out whether that value came
from a place or not, and if so what place?
Note that a value is an actual something in Lisp, which can be passed
around in various ways:
- Passed into a function as parameter.
- Passed from a function as return value.
- Stored in a place.
- Fetched from a place.
- Read from input.
- Printed to output.
- Computed as the result of a calculation, then one of the above.
- One of the above, then used as input to a calculation.
But a place is just a human concept, which SETF and some other
macros understand to some degree, but is *not* something that can
be directly passed around the way values can. You can pass a symbol
to a function, but that function needs to be written to accept a
symbol and to know what to do with that symbol. SET is the only
basic Lisp function that takes a symbol and changes its value cell.
> What I fail to understand is why exactly lisp doesn't have a
> problem changing where a particular cdr points, but does have a
> problem with changing where a variable points.
Variables don't point anywhere. Variables have value cells (and
property-list cells, and package cells), and those value cells have
pointers to other things. Some functions take a symbol and modify
the contents its value cell. (SET is the only such function I know
of.) Some functions take a CONS cell and modify the CAR or CDR
(RPLACA and RPLACD respectively). Some functions take a CDR-linked
chain of CONS cells and search down the list and might sometimes
modify the CDRs of some of those CONS cells. (DELETE is such a
function. NREVERSE is another.)
Would you like to write a function that could take either a symbol
or a CDR-chained list, and if it gets a symbol then it modifies the
value cell, but if it gets a CDR-chained list then it modifies some
of the CARs?
It's not going to do what you really want, because lexical symbols
disappear in compiled code, and even in interpreted code they are
effectively inaccessible via SET. You think you are modifying the
value cell of the symbol, and you think if you pass the symbol
itself to a function then you can modify the value cell, but in
fact the symbol has only the special binding if any, not lexical
bindings.
(defun make42 (sym)
(setf (symbol-value sym) 42))
(let ((x 5))
(format t "first x = ~S~%" x)
(make42 'x)
(format t "then x = ~S~%" x)
)
first x = 5
then x = 5
(format t "global x = ~S~%" x)
global x = 42
> Why even include delete at all?
It's nothing more than a more efficient way to implement REMOVE.
Consider these two operations:
(defvar x)
(setq x (list 1 2 3 4 5 6))
(setq y (remove 4 x))
Must re-build a copy of the first three elements. In effect it does:
(setq y (list* 1 2 3 (cddddr x))
(setq y (delete 4 x))
Needn't re-build anything, just patches the existing list to skip over 4:
(progn (rplacd (cddr x) (cddddr x)) x)
> Remove works just fine in a non-destructive way, and we can
> always just (setq testing (remove 'a testing)). Is there any
> purpose to having a function that will destructively delete
> anything but the car?
Yeah, efficiency. If you have a list of ten million elements, and
you want to REMOVE the next-to-last element, nine hundred ninety
nine thousand nine hundred ninety eight CONS cells must be
re-built. But if you destructively DELETE the next-to-last element
by patching the CDR of the previous element to skip over it, you
don't need to rebuild anything at all.
(length (setq foo (loop for ix from 0 to (expt 10 6) collect ix)))
=> 1000001
(subseq foo 999997)
=> (999997 999998 999999 1000000)
(time (length (setq bar1 (remove 999998 foo))))
Evaluation took:
1.27 seconds of real time
1.080475 seconds of user run time
0.092979 seconds of system run time
[Run times include 0.88 seconds GC run time]
0 page faults and
7980864 bytes consed.
=> 1000000
(subseq foo 999997)
=> (999997 999998 999999 1000000) ;This result is guaranteed by ANSI spec.
(subseq bar1 999997)
=> (999997 999999 1000000)
(time (length (setq bar2 (delete 999998 foo))))
Evaluation took:
0.22 seconds of real time
0.217294 seconds of user run time
0.0 seconds of system run time
0 page faults and
0 bytes consed.
=> 1000000
(subseq foo 999997)
=> (999997 999999 1000000) ;This result is *not* guaranteed by ANSI spec.
(subseq bar2 999997)
=> (999997 999999 1000000)
Compare the number of bytes consed!! Which is more efficient?
If this was the timing bottleneck of your program,
would you choose to use REMOVE or DELETE?
>> CL-USER> (defvar testing)
>> TESTING
>> CL-USER> (setq testing '(a b c d))
>> (A B C D)
>> CL-USER> (delete 'a testing)
>> (B C D)
>
> The (B C D) you see above is the value returned by delete. Obvious,
> perhaps, but I am just warming up.
Uh huh....I know how lisp works.
>> CL-USER> testing
>> (A B C D)
>
> If you are familiar at all with programming (I do not know how
> experienced you are) you will realize delete does not see the
> /variable/ testing, the caller pulls a value out of that variable and
> passes it to delete. ie, delete sees (a b c d), not "testing".
When you don't try to change the car, it goes to where testing points
to the memory and changes the various cons'es, IE it "sees" where
testing is pointing. It doesn't need to know any more details about
testing to change it's value, as there are many functions (like setq)
that do this quite efficiently. Don't confuse this with the
differences in the eval loop between macros and functions.
> All delete can do is dutifully return a list without A, and whaddaya
> know, it can do just by returning the CDR of the list received (since
> A appears only in the car of the first cons).
Well, sure, but that's not the issue. The issue is why it doesn't
change the assignment of testing.
>> CL-USER> (delete 'b testing)
>> (A C D)
>
> Now delete is forced to do some work, and makes the cdr of the first
> cons the cdr of the second cons, effectively discarding the second
> cons from the structure received.
You skipped the last line showing that delete is in fact
destructive...but only when you aren't changing the car.
> Another way for you to understand this is to try to write a
> destructive version of my-delete that does behave they way you
> expected. Methinks the light will go on before you write a line of
> code.
My problem isn't writing code, it's understanding why exactly this
behavior was chosen. This is indicative of something deeper in lisp
than anything you have touched on. I'm assuming it has to do with how
variables are assigned. What I fail to understand is why exactly lisp
doesn't have a problem changing where a particular cdr points, but
does have a problem with changing where a variable points. My feeling
is that because variables are handled differently in some way,
whomever coded delete sacrificed consistent behavior for consistent
code. (For the record, if this is the case, I think it is silly:
either smash everything into the same namespace like scheme and treat
it all the same, and have your theoretical consistency, or just make
it work intuitively).
And that brings me to another question: Why even include delete at
all? Remove works just fine in a non-destructive way, and we can
always just (setq testing (remove 'a testing)). Is there any purpose
to having a function that will destructively delete anything but the
car? Perhaps, but I sure can't think of one.
-Nat
Ken Tilton <···········@optonline.net> writes:
Nathaniel Calloway <····@cornell.edu> writes:
>>> CL-USER> (defvar testing)
>>> TESTING
>>> CL-USER> (setq testing '(a b c d))
>>> (A B C D)
>>> CL-USER> (delete 'a testing)
>>> (B C D)
>>
>> The (B C D) you see above is the value returned by delete. Obvious,
>> perhaps, but I am just warming up.
>
> Uh huh....I know how lisp works.
>
>>> CL-USER> testing
>>> (A B C D)
>>
>> If you are familiar at all with programming (I do not know how
>> experienced you are) you will realize delete does not see the
>> /variable/ testing, the caller pulls a value out of that variable and
>> passes it to delete. ie, delete sees (a b c d), not "testing".
>
> When you don't try to change the car, it goes to where testing points
> to the memory and changes the various cons'es, IE it "sees" where
> testing is pointing. It doesn't need to know any more details about
> testing to change it's value, as there are many functions (like setq)
> that do this quite efficiently. Don't confuse this with the
> differences in the eval loop between macros and functions.
But it doesn't see where it's pointing, that's the thing. A list is
passed to DELETE, not a variable. This is precisely the difference
between macros and functions. To change a variable's binding, you need
to use SETQ, some variant of SETF, or a macro calling on of those, none
of which are functions (they're all macros or special forms), and you
have to do it in a scope where that variable exists.
>> All delete can do is dutifully return a list without A, and whaddaya
>> know, it can do just by returning the CDR of the list received (since
>> A appears only in the car of the first cons).
>
> Well, sure, but that's not the issue. The issue is why it doesn't
> change the assignment of testing.
It's a function, and couldn't if it wanted to. TESTING is not even in
its scope.
>>> CL-USER> (delete 'b testing)
>>> (A C D)
>>
>> Now delete is forced to do some work, and makes the cdr of the first
>> cons the cdr of the second cons, effectively discarding the second
>> cons from the structure received.
>
> You skipped the last line showing that delete is in fact
> destructive...but only when you aren't changing the car.
>
>> Another way for you to understand this is to try to write a
>> destructive version of my-delete that does behave they way you
>> expected. Methinks the light will go on before you write a line of
>> code.
>
> My problem isn't writing code, it's understanding why exactly this
> behavior was chosen. This is indicative of something deeper in lisp
> than anything you have touched on. I'm assuming it has to do with how
> variables are assigned. What I fail to understand is why exactly lisp
> doesn't have a problem changing where a particular cdr points, but
> does have a problem with changing where a variable points. My feeling
> is that because variables are handled differently in some way,
> whomever coded delete sacrificed consistent behavior for consistent
> code. (For the record, if this is the case, I think it is silly:
> either smash everything into the same namespace like scheme and treat
> it all the same, and have your theoretical consistency, or just make
> it work intuitively).
If you did what he suggested, you would understand why the DELETE
function can't possibly do what you expected. No function can change a
binding in its caller's scope. Try it. You'll be completely stumped.
Lisp doesn't have a problem changing a cdr because it's not a
variable. A cons cell is a mutable object whose car and cdr can be
changed by any function with a reference to it. DELETE is passed a cons
cell whose cdr (probably) contains some more cons cells, and that's the
list. No matter what DELETE does with these cons cells, it can't change
the binding of the variable in its caller's scope. That variable remains
bound to the original head of the list. If the original head just so
happens to be the head of the returned list, it's just useless
coincidence that the variable points to the same object that DELETE has
returned.
Variables are not just being handled differently, they're completely
different in nature from objects. Variables are bindings of values to
symbols within a particular scope. Put another way, when Lisp encounters
an unquoted symbol not in the car of a form (which would be a function
call), it checks to see whether that variable is bound to an object. A
variable is a *name*, not a thing. A behavior of the EVAL rather than an
object that can be passed around.
DELETE's behavior is also not inconsistent in the way you're
thinking. Like every other function, you call it and it returns a value
for you to use. The only way it's odd is that it is allowed to mess up
the structure you have passed to it.
> And that brings me to another question: Why even include delete at
> all? Remove works just fine in a non-destructive way, and we can
> always just (setq testing (remove 'a testing)). Is there any purpose
> to having a function that will destructively delete anything but the
> car? Perhaps, but I sure can't think of one.
An efficiency hack. If you've got lists millions of items long, you
might not want to copy the whole thing to remove three items from it. If
you know that list isn't referenced by other code, you can use DELETE
rather than REMOVE, using half the memory for the operation. Often this
doesn't matter, even in terms of GC performance, but it does
sometimes. So you can trade slightly funny semantics (trashing your
data) for better performance.
The crucial thing to understand is that in Lisp, functions are not
normally called for side effects. Even when a library function is marked
as destructive, that's not meant to mean "usefully modificative". It's
destructive like blowing up your engine in a drag race. A strange thing
you do because you've got good reason to and know it won't be a problem
later.
On May 13, 2:49 am, Paul Donnelly <·············@sbcglobal.net> wrote:
>
> The crucial thing to understand is that in Lisp, functions are not
> normally called for side effects. Even when a library function is marked
> as destructive, that's not meant to mean "usefully modificative". It's
> destructive like blowing up your engine in a drag race. A strange thing
> you do because you've got good reason to and know it won't be a problem
> later.
Just to add a bit, consider:
(defun pseudo-remove (x list)
(let ((result nil))
(dolist (car list (nreverse result))
(unless (eql x car)
(push car result)))))
From the outside, this function behaves functionally, it calls a
destructive function on a list created inside itself, so we know
the list is disposable, the side effects don't 'leak'.
It also is the last thing called, it doesn't need to setf anything,
we are only interested in the result of the destructive function
as a return value.
This is a pretty common pattern, looks functional on the outside,
all the hairy stuff inside where it can be controlled and most
of the destructive calls end up being the last thing done.
As for efficency, wait till you tell a client not to worry,
in just 5 years time Moore's law will make his new application
work as fast as he wants it to. :)
---
Geoff
Paul Donnelly wrote:
> Nathaniel Calloway <····@cornell.edu> writes:
>
>
>>>>CL-USER> (defvar testing)
>>>>TESTING
>>>>CL-USER> (setq testing '(a b c d))
>>>>(A B C D)
>>>>CL-USER> (delete 'a testing)
>>>>(B C D)
>>>
>>>The (B C D) you see above is the value returned by delete. Obvious,
>>>perhaps, but I am just warming up.
>>
>>Uh huh....I know how lisp works.
>>
>>
>>>>CL-USER> testing
>>>>(A B C D)
>>>
>>>If you are familiar at all with programming (I do not know how
>>>experienced you are) you will realize delete does not see the
>>>/variable/ testing, the caller pulls a value out of that variable and
>>>passes it to delete. ie, delete sees (a b c d), not "testing".
>>
>>When you don't try to change the car, it goes to where testing points
>>to the memory and changes the various cons'es, IE it "sees" where
>>testing is pointing. It doesn't need to know any more details about
>>testing to change it's value, as there are many functions (like setq)
>>that do this quite efficiently. Don't confuse this with the
>>differences in the eval loop between macros and functions.
>
>
> But it doesn't see where it's pointing, that's the thing. A list is
> passed to DELETE, not a variable. This is precisely the difference
> between macros and functions. To change a variable's binding, you need
> to use SETQ, some variant of SETF, or a macro calling on of those, none
> of which are functions (they're all macros or special forms), and you
> have to do it in a scope where that variable exists.
>
>
>>>All delete can do is dutifully return a list without A, and whaddaya
>>>know, it can do just by returning the CDR of the list received (since
>>>A appears only in the car of the first cons).
>>
>>Well, sure, but that's not the issue. The issue is why it doesn't
>>change the assignment of testing.
>
>
> It's a function, and couldn't if it wanted to. TESTING is not even in
> its scope.
>
>
>>>>CL-USER> (delete 'b testing)
>>>>(A C D)
>>>
>>>Now delete is forced to do some work, and makes the cdr of the first
>>>cons the cdr of the second cons, effectively discarding the second
>>>cons from the structure received.
>>
>>You skipped the last line showing that delete is in fact
>>destructive...but only when you aren't changing the car.
>>
>>
>>>Another way for you to understand this is to try to write a
>>>destructive version of my-delete that does behave they way you
>>>expected. Methinks the light will go on before you write a line of
>>>code.
>>
>>My problem isn't writing code, it's understanding why exactly this
>>behavior was chosen. This is indicative of something deeper in lisp
>>than anything you have touched on. I'm assuming it has to do with how
>>variables are assigned. What I fail to understand is why exactly lisp
>>doesn't have a problem changing where a particular cdr points, but
>>does have a problem with changing where a variable points. My feeling
>>is that because variables are handled differently in some way,
>>whomever coded delete sacrificed consistent behavior for consistent
>>code. (For the record, if this is the case, I think it is silly:
>>either smash everything into the same namespace like scheme and treat
>>it all the same, and have your theoretical consistency, or just make
>>it work intuitively).
>
>
> If you did what he suggested, you would understand why the DELETE
> function can't possibly do what you expected. No function can change a
> binding in its caller's scope. Try it. You'll be completely stumped.
Yeah, but I was completely wrong when I said the light would then go on
for Natty Dread: this clown is so wrapped up in what he "knows" that he
cannot hear a word we say.
I hope he stays around, he's funny. :)
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
Well it appears I started quite the shit storm. I know I'm not writing
the spec for CL or maintaining a particular implementation, as some of
the respondents to this thread are. However, I am not nearly as
noobish as many of my questions were taken, or as I might have
appeared. I have a very different perspective, however, and lisp is
not my first language.
I'm sorry for my snarky comments, but they were largely because of
frustration because the answers I was receiving were missing the key
questions I had. I apologize, because this is probably due to my
limited vernacular for discussing these types of questions amongst
lisp people. The original posts being at 2:00 in the morning because I
couldn't sleep, might have something else to do with it.
My initial confusion was over the fact that I thought delete was a
function was designed for its side effects, not speed, as I am informed.
>> If you did what he suggested, you would understand why the DELETE
>> function can't possibly do what you expected. No function can change a
>> binding in its caller's scope. Try it. You'll be completely stumped.
This above is indicative of where the miss-communication was. I
understand that functions cannot change bindings. However, because I
thought that delete existed for its side effects, this lead to two questions:
Q1. Why design delete this way? Why not use a macro?
A1. Its a function you idiot! (What I realize now what people were
saying was that it is not designed for its side effects, but hopefully
you can understand why exactly I thought that was a non-sequitur)
Q2. Why exactly can delete destructively change how the cdrs in its
target list are bound? IE if changing the binding of variables is
forbidden, what exactly is different about the cdr's in the list?
A2. ....
This is where my lack of understanding of lisp comes in. This is also
where my vernacular is lacking. If I can explain it in terms of
pointing, using my original example:
testing -> (a . -> (b . -> (c . -> (d . -> nil)))
You follow?
Where exactly is this description wrong? (I am assuming it is in some way).
If this is accurate, then why are changing some assignments forbidden?
For the sake of keeping things "functional?"
> Yeah, but I was completely wrong when I said the light would then go
> on for Natty Dread: this clown is so wrapped up in what he "knows"
> that he cannot hear a word we say.
>
> I hope he stays around, he's funny. :)
Yes, you have proved how stupid I am. I'm glad to have amused you. I
hope I have explained why exactly "I didn't hear" what you were
saying, why I thought the discussion was pedantic, and why I've
reposted this so we can rip into eachother some more.
-Nat
On May 13, 12:01 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> Q2. Why exactly can delete destructively change how the cdrs in its
> target list are bound? IE if changing the binding of variables is
> forbidden, what exactly is different about the cdr's in the list?
>
> A2. ....
>
> This is where my lack of understanding of lisp comes in. This is also
> where my vernacular is lacking. If I can explain it in terms of
> pointing, using my original example:
>
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>
> You follow?
>
> Where exactly is this description wrong? (I am assuming it is in some way).
>
> If this is accurate, then why are changing some assignments forbidden?
> For the sake of keeping things "functional?"
>
>
As others have mentioned, delete only sees the value of testing. The
name / symbol / binding testing does not exist in the scope of delete.
If
testing -> (a . -> (b . -> (c . -> (d . -> nil)))
and delete takes list argument 'list', delete sees
list -> (a . -> (b . -> (c . -> (d . -> nil)))
because list points to a 's cons it can modify its cdr and return
(a . -> (c . -> (d . -> nil)))
if it feels like it. However, delete does not know about testing and
therefore can not modify where testing points.
If delete returned (b . -> (c . -> (d . -> nil)))
You can assign testing to point to that result, otherwise testing will
still point to a, as you saw.
-David
> why are changing some assignments forbidden?
> For the sake of keeping things "functional?"
In your mind there's still a residue that the goal of DELETE is to
alter things (i.e. "changing some assignments"). The goal of
destructive functions is NOT destruction. It is efficiency.
In other words, when you write
(setq testing '(a b c d))
(delete 'a testing)
the goal of delete is to return the result '(b c d)
_as_quick_as_possible_.
(Why loose time reassigning testing?)
·······@eurogaran.com writes:
> the goal of delete is to return the result '(b c d)
> _as_quick_as_possible_.
This is not so. The goal is to permit implementations that want to
worry about speed issues to do so. There are two material differences
between my statement and yours.
First, an implementation may desire to worry about speed issues in ways
other than returning that particular answer faster. For example, it
may be faster to copy but the GC in some implementation may run long.
In that case, DELETE may optimize overall performance but not copying
performance. Implementations can decide what they want to optimize.
The spec takes no position on that.
Second, some implementations may not be concerned with speed. It has
happened that there were implementations that wanted a small binary
footprint and that made DELETE and REMOVE be synonyms. The same for
several other destructive operations. While this behavior may
pessimize performance, it is presumed that the implementation knows
what market it is shooting for and what is valued by that market.
Consequently, the presence of DELETE in that circumstance preserves
the right of SOME implementations to care about speed but does not
force ALL implementations to care.
In general, I think it's not a good idea for you to keep telling
people in some authoritative tone that you know the reasons that
something is there when you have not asked around to find out all the
possible reasons. For one thing, the language was designed by a
committee and there's really no one who is empowered to speak for the
committee; the committee did not publish a rationale, and in fact its
reasons are not required to even be the same for each person who voted
the same way on each issue. Everyone voted for their own reason.
It's fine, of course, to say "this is A reason" but before you start
to talk about "this is the ONLY reason", especially when there are
others who voted on those matters alleging otherwise and who you are
contradicting, you need to do more research. This may be the only
thing YOU care about (I can't say--not being an expert on your tastes
and wishes), but the language design had a number of goals in mind.
Just for example: If forcing the optimizing of speed was the key
issue, there would not be an OPTIMIZE declaration that allows you to
trade speed for other factors.
In article
<····································@e39g2000hsf.googlegroups.com>,
·······@eurogaran.com wrote:
> > why are changing some assignments forbidden?
> > For the sake of keeping things "functional?"
>
> In your mind there's still a residue that the goal of DELETE is to
> alter things (i.e. "changing some assignments"). The goal of
> destructive functions is NOT destruction. It is efficiency.
> In other words, when you write
> (setq testing '(a b c d))
> (delete 'a testing)
> the goal of delete is to return the result '(b c d)
> _as_quick_as_possible_.
> (Why loose time reassigning testing?)
only in ANSI Common Lisp you are not allow to destructively modify
literal data.
--
http://lispm.dyndns.org/
On May 13, 6:01 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>
> [...]
>
> If this is accurate, then why are changing some assignments forbidden?
> For the sake of keeping things "functional?"
http://en.wikipedia.org/w/index.php?title=Evaluation_strategy&oldid=211022127#Call_by_value
Hope this helps,
Matthias
Nathaniel Calloway wrote:
> Well it appears I started quite the shit storm. I know I'm not writing
> the spec for CL or maintaining a particular implementation, as some of
> the respondents to this thread are. However, I am not nearly as
> noobish as many of my questions were taken, or as I might have
> appeared. I have a very different perspective, however, and lisp is
> not my first language.
>
> I'm sorry for my snarky comments, but they were largely because of
> frustration because the answers I was receiving were missing the key
> questions I had. I apologize, because this is probably due to my
> limited vernacular for discussing these types of questions amongst
> lisp people. The original posts being at 2:00 in the morning because I
> couldn't sleep, might have something else to do with it.
>
> My initial confusion was over the fact that I thought delete was a
> function was designed for its side effects, not speed, as I am informed.
>
>
>>>If you did what he suggested, you would understand why the DELETE
>>>function can't possibly do what you expected. No function can change a
>>>binding in its caller's scope. Try it. You'll be completely stumped.
>
>
> This above is indicative of where the miss-communication was. I
> understand that functions cannot change bindings. However, because I
> thought that delete existed for its side effects, this lead to two questions:
>
> Q1. Why design delete this way? Why not use a macro?
>
> A1. Its a function you idiot! (What I realize now what people were
> saying was that it is not designed for its side effects, but hopefully
> you can understand why exactly I thought that was a non-sequitur)
>
> Q2. Why exactly can delete destructively change how the cdrs in its
> target list are bound? IE if changing the binding of variables is
> forbidden, what exactly is different about the cdr's in the list?
>
> A2. ....
>
> This is where my lack of understanding of lisp comes in. This is also
> where my vernacular is lacking. If I can explain it in terms of
> pointing, using my original example:
>
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>
> You follow?
>
> Where exactly is this description wrong? (I am assuming it is in some way).
>
> If this is accurate, then why are changing some assignments forbidden?
> For the sake of keeping things "functional?"
>
>
>>Yeah, but I was completely wrong when I said the light would then go
>>on for Natty Dread: this clown is so wrapped up in what he "knows"
>>that he cannot hear a word we say.
>>
>>I hope he stays around, he's funny. :)
>
>
> Yes, you have proved how stupid I am. I'm glad to have amused you. I
> hope I have explained why exactly "I didn't hear" what you were
> saying, why I thought the discussion was pedantic, and why I've
> reposted this so we can rip into eachother some more.
Oh, no, that's too much like work, and I am exhausted already! I'll just
be reading and laughing from now on.
If you ever Actually Write Some Code you might hear from me again.
Don't change!
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
> "Steven M. Haflich" <····@alum.mit.edu> writes:
> > Common Lisp does not have "commands".
> It does have functions.
On May 13, 12:43 am, Nathaniel Calloway wrote:
> Comp.lang.lisp does not have "discussions".
> It does have pedants.
C.L.L has interminable hyper-meta-uber-debates ignited
and maintained by (a) the aforementioned pedants,
(b) clueless newbies attempting to impart wisdom to
said pedants, (c) attention-seeking trolls basking
in the glory and notoriety of C.L.L, and (d) assorted
innocent passersby.
<pedantic>
> delete exists exclusively for its side effects because
> there is another function *with the exact same behavior*
> and no side effects.
delete exists exclusively for *performance* reasons, not
side effects. A better name for delete would be NREMOVE,
because the N- indicates that delete is *allowed* to de-
structively reuse the structure it recieves as an argument.
> My initial confusion was over the fact that I thought
> delete was a function was designed for its side effects,
> not speed
Your *continuing* confusion is over the fact that you
still haven't figured out how functions receive their
arguments. When you call (delete 'a testing), testing
is passed to delete by *value*, not by reference.
So delete receives a reference to the first cons in
'(a b c d), not a reference to testing.
> I understand that functions cannot change bindings.
We're not talking about pure functions here. A Lisp
function can change any binding whose variable name
is hard-coded into the function (and in scope).
> Q1. Why design delete this way? Why not use a macro?
> A1. Its a function you idiot!
> (What I realize now what people were saying was that
> it is not designed for its side effects
No, that's not what they're saying. We're emphasizing that
delete is a function not because of what it *does*, but
what it *receives*.
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
> Where exactly is this description wrong?
Where it's wrong is that you keep assuming delete
receives a reference to testing:
(delete 'a '(testing -> (a . -> (b . -> (c . -> (d . -> nil))))
but it doesn't. testing is eval'd before being passed
to delete, so all delete sees is, as you said yourself,
the thing that testing points to, not the variable testing
itself:
(delete 'a '(a . -> (b . -> (c . -> (d . -> nil)))
> Q2. Why exactly can delete destructively change how
> the cdrs in its target list are bound? IE if changing
> the binding of variables is forbidden, what exactly
> is different about the cdr's in the list?
> This is where my lack of understanding of lisp comes in.
> If this is accurate, then why are changing some assignments
> forbidden? For the sake of keeping things "functional?"
It's not forbidden, it's *impossible*, because the reference
to testing is thrown away before it ever gets to delete.
CDRs can be changed because, in terms of pointer chains,
they're "downstream" of the head of the list, whereas
the variable 'testing is upstream, so it's not accessible.
--Dan
</pedantic>
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
In article <·············@cornell.edu>,
Nathaniel Calloway <····@cornell.edu> wrote:
> Well it appears I started quite the shit storm. I know I'm not writing
> the spec for CL or maintaining a particular implementation, as some of
> the respondents to this thread are. However, I am not nearly as
> noobish as many of my questions were taken, or as I might have
> appeared. I have a very different perspective, however, and lisp is
> not my first language.
>
> I'm sorry for my snarky comments, but they were largely because of
> frustration because the answers I was receiving were missing the key
> questions I had. I apologize, because this is probably due to my
> limited vernacular for discussing these types of questions amongst
> lisp people. The original posts being at 2:00 in the morning because I
> couldn't sleep, might have something else to do with it.
>
> My initial confusion was over the fact that I thought delete was a
> function was designed for its side effects, not speed, as I am informed.
>
> >> If you did what he suggested, you would understand why the DELETE
> >> function can't possibly do what you expected. No function can change a
> >> binding in its caller's scope. Try it. You'll be completely stumped.
>
> This above is indicative of where the miss-communication was. I
> understand that functions cannot change bindings. However, because I
> thought that delete existed for its side effects, this lead to two questions:
>
> Q1. Why design delete this way? Why not use a macro?
>
> A1. Its a function you idiot! (What I realize now what people were
> saying was that it is not designed for its side effects, but hopefully
> you can understand why exactly I thought that was a non-sequitur)
>
> Q2. Why exactly can delete destructively change how the cdrs in its
> target list are bound? IE if changing the binding of variables is
> forbidden, what exactly is different about the cdr's in the list?
>
> A2. ....
>
> This is where my lack of understanding of lisp comes in. This is also
> where my vernacular is lacking. If I can explain it in terms of
> pointing, using my original example:
>
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>
> You follow?
Yes.
>
> Where exactly is this description wrong? (I am assuming it is in some way).
>
> If this is accurate, then why are changing some assignments forbidden?
> For the sake of keeping things "functional?"
You may want to understand how Lisp evaluates forms and passes arguments.
If you have *testing* bound to a list, it really points to a cons.
(defun foo (bar) ...)
if you call a function FOO like (foo *testing*), then *testing* gets
evaluated, so FOO gets called with the cons. The parameter BAR of
foo gets bound to that cons. Means, you now have *testing*
point to the first cons and BAR point to the first cons, too.
But rebinding or setting BAR will not change *testing*.
The function FOO cannot affect the binding of *TESTING*,
because it does not see it. It hasn't got a binding as an argument,
but a cons that then was bound to the BAR parameter.
Argument = the thing that appears in a call like (foo *testing*)
Parameter = the variable that appears in a parameter list
of a function. Here one parameter named BAR.
Common Lisp does not pass arguments by name or similar.
So DELETE (like every function) can change mutable objects it gets
passed. But it can't change bindings of variables that appear in a
call to DELETE. The bindings are not passed, but the values.
Is that clear enough? Do you need a better explanation?
--
http://lispm.dyndns.org/
Nathaniel Calloway wrote:
...
> This is where my lack of understanding of lisp comes in. This is also
> where my vernacular is lacking. If I can explain it in terms of
> pointing, using my original example:
>
> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
Perfect. So let's see:
Delete is a function, so it is passed the contents of testing, that is,
the whole list:
(a . -> (b . -> (c . -> (d . -> nil)))
Now, it can do with it whatever it wants. If it wants to get rid of b,
it could take the first pointer and make it point to the c:
+----------+
| |
(a . -+ (b . -> (c . -> (d . -> nil)))
Then the list becomes
(a . -> (c . -> (d . -> nil))
The symbol testing, however still points like this
testing
|
v
(a . -> (c . -> (d . -> nil))
So, how do you want to get rid of the a? If you put a nil there, you'd
have
Testing
|
v
(nil . -> (c . -> (d . -> nil))
which is
CL-USER> (cons nil (cons 'b (cons 'c (cons 'd nil))))
(NIL B C D)
not what you want. What else could delete do?
If you wish to try things out, you may want to start with something like
this:
(defun my-delete (remove-item seq)
(loop for rest on seq by #'cdr
if (eql (cadr rest) remove-item)
do (setf (cdr rest) (cddr rest)))
seq)
Try (my-delete 'b (list 'a 'b 'c 'd)) and then (my-delete 'a ...) -- and
think about what happens in each case.
Peter
Peter Hildebrandt wrote:
> Nathaniel Calloway wrote:
> ...
>
>> This is where my lack of understanding of lisp comes in. This is also
>> where my vernacular is lacking. If I can explain it in terms of
>> pointing, using my original example:
>>
>> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>
>
> Perfect. So let's see:
>
> Delete is a function, so it is passed the contents of testing, that is,
> the whole list:
>
> (a . -> (b . -> (c . -> (d . -> nil)))
>
> Now, it can do with it whatever it wants. If it wants to get rid of b,
> it could take the first pointer and make it point to the c:
>
> +----------+
> | |
> (a . -+ (b . -> (c . -> (d . -> nil)))
>
> Then the list becomes
>
> (a . -> (c . -> (d . -> nil))
>
> The symbol testing, however still points like this
>
> testing
> |
> v
> (a . -> (c . -> (d . -> nil))
>
> So, how do you want to get rid of the a?
You know, it occurred to me that an implementation could copy the car
and cdr of the second cons cell into the car and cdr of the first cons
cell -- that would be cute.
Of course we are still not operating on "testing" itself, we just happen
in this case to create that illusion via mutation.
I hope this confuses things. :)
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On May 13, 7:35 pm, Ken Tilton <···········@optonline.net> wrote:
> You know, it occurred to me that an implementation could copy the car
> and cdr of the second cons cell into the car and cdr of the first cons
> cell -- that would be cute.
>
> Of course we are still not operating on "testing" itself, we just happen
> in this case to create that illusion via mutation.
Except that it wouldn't work on one-element lists. Then again, who
ever uses one-element lists in a real-world application, anyway?
Ain't gonna happen, right? ;)
Matthias
> You know, it occurred to me that an implementation could copy the car
> and cdr of the second cons cell into the car and cdr of the first cons
> cell -- that would be cute.
>
> Of course we are still not operating on "testing" itself, we just
> happen in this case to create that illusion via mutation.
>
> I hope this confuses things. :)
This is exactly the behavior I was asking about. I initially didn't
understand why delete wouldn't do something like this. I now know that
this sort of behavior isn't the concern of delete
However it became obfuscated in the storm of people calling me a clown
and whatnot.
-Nat
On May 13, 7:58 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> > You know, it occurred to me that an implementation could copy the car
> > and cdr of the second cons cell into the car and cdr of the first cons
> > cell -- that would be cute.
> > [...]
>
> This is exactly the behavior I was asking about. I initially didn't
> understand why delete wouldn't do something like this. I now know that
> this sort of behavior isn't the concern of delete
...and it couldn't be even if the CLHS wanted it to, because you can't
replace a cons by NIL that way. (let ((x (list 10))) (delete 10 x) x)
is never going to work the way you imagine, no matter what DELETE
does. You'd have to use something other than raw cons cells as lists
for it to work.
Matthias
In article
<····································@l42g2000hsc.googlegroups.com>,
Matthias Benkard <··········@gmail.com> wrote:
> On May 13, 7:58 pm, Nathaniel Calloway <····@cornell.edu> wrote:
> > > You know, it occurred to me that an implementation could copy the car
> > > and cdr of the second cons cell into the car and cdr of the first cons
> > > cell -- that would be cute.
> > > [...]
> >
> > This is exactly the behavior I was asking about. I initially didn't
> > understand why delete wouldn't do something like this. I now know that
> > this sort of behavior isn't the concern of delete
>
> ...and it couldn't be even if the CLHS wanted it to, because you can't
> replace a cons by NIL that way. (let ((x (list 10))) (delete 10 x) x)
> is never going to work the way you imagine, no matter what DELETE
> does. You'd have to use something other than raw cons cells as lists
> for it to work.
Right.
People who are used to languages like C are familiar with ADT
representations of data structures like lists and trees, which make this
kind of side effecting easier. There's a structure that represents the
list as a whole, and it contains the pointer to the head of the list.
Then a function like DELETE can work by updating this pointer, and you
don't have to worry about the original variable.
You could do this in Lisp using DEFSTRUCT, but it's not how the built-in
list operations work. So you'd have to write all your own functions to
deal with it.
The ADT design would have additional benefits. For example, you could
have multiple pointers to the same list, and when you update it through
any of them they all see the change. With Lisp's destructive
operations, this is not typically a safe way to program -- you have to
ensure that all the references to the list get updated. Applications
that need to do this are likely to implement their own indirection
through a structure or class.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Ken Tilton <···········@optonline.net> writes:
> Peter Hildebrandt wrote:
>> Nathaniel Calloway wrote:
>> ...
>>
>>> This is where my lack of understanding of lisp comes in. This is also
>>> where my vernacular is lacking. If I can explain it in terms of
>>> pointing, using my original example:
>>>
>>> testing -> (a . -> (b . -> (c . -> (d . -> nil)))
>> Perfect. So let's see:
>> Delete is a function, so it is passed the contents of testing, that
>> is, the whole list:
>> (a . -> (b . -> (c . -> (d . -> nil)))
>> Now, it can do with it whatever it wants. If it wants to get rid of
>> b, it could take the first pointer and make it point to the c:
>> +----------+
>> | |
>> (a . -+ (b . -> (c . -> (d . -> nil)))
>> Then the list becomes
>> (a . -> (c . -> (d . -> nil))
>> The symbol testing, however still points like this
>> testing
>> |
>> v
>> (a . -> (c . -> (d . -> nil))
>> So, how do you want to get rid of the a?
>
> You know, it occurred to me that an implementation could copy the car
> and cdr of the second cons cell into the car and cdr of the first cons
> cell -- that would be cute.
In the case of delete it may not be so cute, because you may still
want to rather have:
(let* ((example (list 1 2 3 4))
(conses example))
(setf example (delete 1 example))
(values example conses))
(2 3 4) ;
(1 2 3 4)
But note that clisp does that for nreverse:
C/USER[16]> (let* ((example (list 1 2 3 4 5))
(conses example)
(in-the-middle (cdr conses)))
(setf example (nreverse example))
(values example conses in-the-middle))
(5 4 3 2 1) ;
(5 4 3 2 1) ;
(2 1)
It keeps the first and last cons of the list in position, and nreverse
in the middle. Helps newbies.
> Of course we are still not operating on "testing" itself, we just
> happen in this case to create that illusion via mutation.
>
> I hope this confuses things. :)
--
__Pascal Bourguignon__
Nathaniel Calloway <····@cornell.edu> writes:
> My problem isn't writing code, it's understanding why exactly this
> behavior was chosen. This is indicative of something deeper in lisp
> than anything you have touched on. I'm assuming it has to do with how
> variables are assigned. What I fail to understand is why exactly lisp
> doesn't have a problem changing where a particular cdr points, but
> does have a problem with changing where a variable points. My feeling
> is that because variables are handled differently in some way,
> whomever coded delete sacrificed consistent behavior for consistent
> code. (For the record, if this is the case, I think it is silly:
> either smash everything into the same namespace like scheme and treat
> it all the same, and have your theoretical consistency, or just make
> it work intuitively).
I'll assume you know some C. How would you do what you want in C?
list_t* delete(object_t*,list_t*);
list_t* my_delete(object_t*,list_t**);
list_t* testing=list(4,1,2,3,4);
my_delete(1,&testing); // instead of testing=delete(1,testing);
print(testing); // would print (2 3 4)
Do you notice that strangle squirgly little character there? This
'&' before 'testing'?
Why don't do you do the same in lisp and still expect the same results?
Just write what you mean:
(let ((testing (list 'a 'b 'c 'd)))
(my-delete 'a (& testing)) ; instead of (setf testing (delete 'a testing))
(print testing))
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/6c4700f48de98f14/d141c5636559ba3b?lnk=st&q=locative+deref+author%3APascal+author%3ABourguignon#d141c5636559ba3b
Of course, you'd have to define my-delete differently than delete.
(defun my-delete (object seq-by-ref)
(setf (deref seq-by-ref) (delete object (deref seq-by-ref))))
Ok, but let's stop being silly. Like in C, the only way arguments are
passed to function is by value, that is, the value of the argument is
copied into the parameter. You can be often oblious of this fact in
lisp because most values in lisp are actually references to the
object, and because thanks to the garbage collector it is much easier
to write in functional style, so you just do that usually.
> And that brings me to another question: Why even include delete at
> all? Remove works just fine in a non-destructive way, and we can
> always just (setq testing (remove 'a testing)).
Then why can't you just do (setq testing (delete 'a testing))
when you want to avoid spoilling memory?
> Is there any purpose to having a function that will destructively
> delete anything but the car? Perhaps, but I sure can't think of one.
The purpose is to spare some consing.
(delete (1- n) (iota n)) --> O(n) in time, O(1) in space.
(remove (1- n) (iota n)) --> O(n) in time, O(n) in space!
--
__Pascal Bourguignon__
Nathaniel Calloway <····@cornell.edu> wrote:
>> The (B C D) you see above is the value returned by delete. Obvious,
>> perhaps, but I am just warming up.
>
> Uh huh....I know how lisp works.
[snip]
>> All delete can do is dutifully return a list without A, and whaddaya
>> know, it can do just by returning the CDR of the list received (since
>> A appears only in the car of the first cons).
>
> Well, sure, but that's not the issue. The issue is why it doesn't
> change the assignment of testing.
This appears to contradict your previous claim.
It can't change TESTING because it doesn't know which variable to
twiddle.
Suppose FOO initially points at (A B C). After
(delete 'b foo)
=> (A C)
we find that FOO is probably (A C). Typically (i.e., in usual
implementations -- this isn't guaranteed), DELETE will mess with cdrs in
order to do its job. In particular, in this case, it's probably
equivalent to
(progn (rplacd foo (cddr foo)) foo)
(Let's reset FOO back to (A B C).) However, if you zap the first
element of the list,
(delete 'a foo)
=> (B C)
it does more or less the same as
(cdr foo)
which doesn't have any side-effects at all.
Now, it's possible that an implementation of DELETE might work by
hacking cars as well as cdrs. Such a version might do the equivalent of
(progn
(rplaca foo (cadr foo))
(rplacd foo (cddr foo))
foo)
This will leave FOO pointing at a list (B C).
You might think that this will solve your problems, and everyone's
DELETE ought to work like this. But that's not right. In particular,
suppose FOO was initially just (A). Then
(delete 'a foo)
=> NIL
foo
=> (A)
Unfortunately there's no part of a cons cell to hack that will make it
look like NIL. The only way DELETE can hack FOO to be nil afterwards is
if it can find the variable FOO; but DELETE is a function, so its
arguments are passed by value and this is simply impossible.
As others have mentioned, the purpose of DELETE is to be fast, not to
mutate your list in some carefully described way. This is reasonable:
as just shown, it's not always possible to mutate the given list so as
to allow the caller to ignore the return value; so since correct
programs can't ignore the value anyway, it's just not sensible to bend
over backwards doing the 98% job. Besides, note that the full car- and
cdr-hacking DELETE operation is considerably slower than the one which
just returns the appropriate tail of the input list.
It's also somewhat more complicated in the general case; try writing
one.
-- [mdw]
Mark Wooding <···@distorted.org.uk> writes:
> Nathaniel Calloway <····@cornell.edu> wrote:
>
>>> The (B C D) you see above is the value returned by delete. Obvious,
>>> perhaps, but I am just warming up.
>>
>> Uh huh....I know how lisp works.
>
> [snip]
>
>>> All delete can do is dutifully return a list without A, and whaddaya
>>> know, it can do just by returning the CDR of the list received (since
>>> A appears only in the car of the first cons).
>>
>> Well, sure, but that's not the issue. The issue is why it doesn't
>> change the assignment of testing.
>
> This appears to contradict your previous claim.
>
> It can't change TESTING because it doesn't know which variable to
> twiddle.
>
> Suppose FOO initially points at (A B C). After
>
> (delete 'b foo)
> => (A C)
>
> we find that FOO is probably (A C). Typically (i.e., in usual
> implementations -- this isn't guaranteed), DELETE will mess with cdrs in
> order to do its job. In particular, in this case, it's probably
> equivalent to
>
> (progn (rplacd foo (cddr foo)) foo)
>
> (Let's reset FOO back to (A B C).) However, if you zap the first
> element of the list,
>
> (delete 'a foo)
> => (B C)
>
> it does more or less the same as
>
> (cdr foo)
>
> which doesn't have any side-effects at all.
>
> Now, it's possible that an implementation of DELETE might work by
> hacking cars as well as cdrs. Such a version might do the equivalent of
>
> (progn
> (rplaca foo (cadr foo))
> (rplacd foo (cddr foo))
> foo)
>
> This will leave FOO pointing at a list (B C).
>
> You might think that this will solve your problems, and everyone's
> DELETE ought to work like this. But that's not right. In particular,
> suppose FOO was initially just (A). Then
>
> (delete 'a foo)
> => NIL
>
> foo
> => (A)
>
> Unfortunately there's no part of a cons cell to hack that will make it
> look like NIL.
(defun make-it-look-like-nil (cons)
(rplaca cons nil)
(rplacd cons nil)
cons)
(let ((cons (cons 1 2)))
(print (and (eq (car 'nil) (car cons))
(eq (cdr 'nil) (cdr cons))))
(make-it-look-like-nil cons)
(print (and (eq (car 'nil) (car cons))
(eq (cdr 'nil) (cdr cons)))))
prints:
NIL
T
Therefore:
(defun look-like-nil-p (object)
(ignore-errors
(and (eq (car 'nil) (car object))
(eq (cdr 'nil) (cdr object)))))
;-)
> As others have mentioned, the purpose of DELETE is to be fast, not to
> mutate your list in some carefully described way.
I don't think that "being fast" is any criterion for DELETE. It may
help to remeber that DELETE works also on vectors (including strings).
In anycase, it will always be O(length(seq)) in time. What we can do
is to make it O(1) in _space_ vs. O(length(seq)) for REMOVE.
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
> I don't think that "being fast" is any criterion for DELETE. It may
> help to remeber that DELETE works also on vectors (including strings).
As does REMOVE.
> In anycase, it will always be O(length(seq)) in time. What we can do
> is to make it O(1) in _space_ vs. O(length(seq)) for REMOVE.
While both functions have the same asymptotic algorithmic complexity,
the big-O notation does hide constant factors that can be important for
practical uses.
After all, the following non-destructive function is also O(length(seq))
in time, even though it must traverse the list twice.
(defun remove- (item list)
(delete item (copy-sequence list)))
--
Thomas A. Russ, USC/Information Sciences Institute
In article <··············@pbourguignon.anevia.com>,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> Mark Wooding <···@distorted.org.uk> writes:
> > Unfortunately there's no part of a cons cell to hack that will make it
> > look like NIL.
>
> (defun make-it-look-like-nil (cons)
> (rplaca cons nil)
> (rplacd cons nil)
> cons)
>
> (let ((cons (cons 1 2)))
> (print (and (eq (car 'nil) (car cons))
> (eq (cdr 'nil) (cdr cons))))
> (make-it-look-like-nil cons)
> (print (and (eq (car 'nil) (car cons))
> (eq (cdr 'nil) (cdr cons)))))
>
> prints:
>
> NIL
> T
>
>
> Therefore:
>
> (defun look-like-nil-p (object)
> (ignore-errors
> (and (eq (car 'nil) (car object))
> (eq (cdr 'nil) (cdr object)))))
>
> ;-)
Question: How many legs does a person have, if you call an arm a leg?
Answer: 2 -- calling an arm a leg doesn't make it a leg.
>
>
>
> > As others have mentioned, the purpose of DELETE is to be fast, not to
> > mutate your list in some carefully described way.
>
> I don't think that "being fast" is any criterion for DELETE. It may
> help to remeber that DELETE works also on vectors (including strings).
>
> In anycase, it will always be O(length(seq)) in time. What we can do
> is to make it O(1) in _space_ vs. O(length(seq)) for REMOVE.
REMOVE on a vector has to copy the entire vector (except the removed
elements). DELETE only has to copy starting from the first match. So
while they're both O(length(vector)), DELETE will do fewer copies unless
you're deleting the first element. Also, since DELETE is simply
shifting elements within the same array, it should have excellent
locality, hence fewer cache misses than REMOVE, which must copy between
arrays that are likely to be far apart in memory.
An interesting point about REMOVE on a list is that the result is
permitted to share the unmodified tail (i.e. everything after the last
match) with the original. But in order to do this, I think you need to
make two passes -- first you have to search for the last match, then you
have to copy everything (except the matching elements) leading up to it.
Still O(n), but the coefficient is doubled -- O() notation doesn't tell
all.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Barry Margolin <······@alum.mit.edu> writes:
> In article <··············@pbourguignon.anevia.com>,
> ···@informatimago.com (Pascal J. Bourguignon) wrote:
>
>> Mark Wooding <···@distorted.org.uk> writes:
>> > Unfortunately there's no part of a cons cell to hack that will make it
>> > look like NIL.
>>
>> (defun make-it-look-like-nil (cons)
>> (rplaca cons nil)
>> (rplacd cons nil)
>> cons)
>>
>> (let ((cons (cons 1 2)))
>> (print (and (eq (car 'nil) (car cons))
>> (eq (cdr 'nil) (cdr cons))))
>> (make-it-look-like-nil cons)
>> (print (and (eq (car 'nil) (car cons))
>> (eq (cdr 'nil) (cdr cons)))))
>>
>> prints:
>>
>> NIL
>> T
>>
>>
>> Therefore:
>>
>> (defun look-like-nil-p (object)
>> (ignore-errors
>> (and (eq (car 'nil) (car object))
>> (eq (cdr 'nil) (cdr object)))))
>>
>> ;-)
>
> Question: How many legs does a person have, if you call an arm a leg?
> Answer: 2 -- calling an arm a leg doesn't make it a leg.
Yes, that's the difference between making a cons cell look like nil,
and making a cons cell become the symbol nil.
>> > As others have mentioned, the purpose of DELETE is to be fast, not to
>> > mutate your list in some carefully described way.
>>
>> I don't think that "being fast" is any criterion for DELETE. It may
>> help to remeber that DELETE works also on vectors (including strings).
>>
>> In anycase, it will always be O(length(seq)) in time. What we can do
>> is to make it O(1) in _space_ vs. O(length(seq)) for REMOVE.
>
> REMOVE on a vector has to copy the entire vector (except the removed
> elements). DELETE only has to copy starting from the first match. So
> while they're both O(length(vector)), DELETE will do fewer copies unless
> you're deleting the first element. Also, since DELETE is simply
> shifting elements within the same array, it should have excellent
> locality, hence fewer cache misses than REMOVE, which must copy between
> arrays that are likely to be far apart in memory.
>
> An interesting point about REMOVE on a list is that the result is
> permitted to share the unmodified tail (i.e. everything after the last
> match) with the original. But in order to do this, I think you need to
> make two passes -- first you have to search for the last match, then you
> have to copy everything (except the matching elements) leading up to it.
> Still O(n), but the coefficient is doubled -- O() notation doesn't tell
> all.
True, the constants are usually what matter.
--
__Pascal Bourguignon__
Nathaniel Calloway <····@cornell.edu> writes:
> Anyone have an explanation for the inability of the delete command to
> delete the car from a list (at least in clisp)? I guess this falls
> under the category of "never expect destructive list functions to act
> how you expect."
Well, the general point to remember is that destructive (list) functions
are typically designed to be more "efficient" than their non-destructive
brethren. But they are not guaranteed to modify their arguments. In
fact, a conforming CL implementation is free to do
(defun delete (item list ...) (remove item list ...))
since destructive modification is supported.
> CL-USER> (defvar testing)
> TESTING
> CL-USER> (setq testing '(a b c d))
> (A B C D)
Insert obligatory warning about not destructively modifying constants here.
> CL-USER> (delete 'a testing)
> (B C D)
> CL-USER> testing
> (A B C D)
Now, it would, in principle be possible to write delete such that it
could destructively modify the list structure to remove the first
element of a list. But doing that would involve more work than just
returning the CDR of its input. And since the point of the destructive
operations is to be more efficient, doing MORE work than the
non-destructive REMOVE would defeat the motivation for being
destructive. It would have to be something like this:
(defun delete+ (item list)
(cond ((null list) list)
((null (rest list))
(if (eq item (first list))
nil
list))
((eq item (first list))
(setf (first list) (second list)
(cdr list) (cddr list))
(delete+ item list)
list)
((eq item (second list))
(setf (cdr list) (cddr list))
(delete+ item (cdr list))
list)
(t (delete+ item (cdr list))
list)))
Especially since there is one case where DELETE would not be able to
destructively remove an element:
(delete 'a (list 'a))
There is no destructive operation available that will take a CONS cell
and turn it into NIL. It just can't be done. And that is part of the
reason Kenny wanted you to try writing this yourself.
As you can see, there is no way for DELETE to have any access to the
binding of the variable that holds the list you pass in. It can only
alter the structure of the object that is passed, not any variable
bindings.
Note that the same thing holds true of the destructive SORT operation
(at least when applied to lists). It can destructively rearrange the
list, but you aren't guaranteed that the head cons is still the head
cons.
So for all destructive list operations you have to make sure you bind
the return value and not rely on destruction. Especially since it is
often optional in the language specification.
--
Thomas A. Russ, USC/Information Sciences Institute