On Mar 14, 9:11 am, Szabolcs Szucs <····@elte.hu> wrote:
> How can I create a cons which points with its car and cdr to the
> same object? Therefore if I change the car the cdr will change too..
The function CONS takes two arguments, which will be the car & cdr of
the resulting cons.
> How can I create a cons which points with its car and cdr to the
> same object? Therefore if I change the car the cdr will change too..
You can do it by, well, doing it:
CL-USER> (defparameter initial-value (list 1 2 3))
INITIAL-VALUE
CL-USER> (defparameter mycons (cons initial-value initial-value))
MYCONS
CL-USER> mycons
((1 2 3) 1 2 3)
CL-USER> (setf (car (car mycons)) 42)
42
CL-USER> mycons
((42 2 3) 42 2 3)
CL-USER>
This is what you asked for, although there's a chance this is not what
you wanted.
Hi,
······@gmail.com writes:
>> How can I create a cons which points with its car and cdr to the
>> same object? Therefore if I change the car the cdr will change too..
> You can do it by, well, doing it:
>
> CL-USER> (defparameter initial-value (list 1 2 3))
> INITIAL-VALUE
> CL-USER> (defparameter mycons (cons initial-value initial-value))
> MYCONS
> CL-USER> mycons
> ((1 2 3) 1 2 3)
> CL-USER> (setf (car (car mycons)) 42)
> 42
> CL-USER> mycons
> ((42 2 3) 42 2 3)
> CL-USER>
>
>
> This is what you asked for, although there's a chance this is not what
> you wanted.
>
This is about objects. But with numbers (how can I pack a number as an
object?):
[1]> (defparameter i 1)
I
[2]> i
1
[3]> (defparameter k (cons i i))
K
[4]> k
(1 . 1)
[5]> (setf i 3)
3
[6]> k
(1 . 1)
--
kotee
On Mar 14, 10:04 am, Szabolcs Szucs <····@elte.hu> wrote:
>
> This is about objects. But with numbers (how can I pack a number as an
> object?):
Just to clarify what someone else said: numbers *are* objects in CL,
they are just immutable objects. To achieve what you want you need to
put the number inside some object which is mutable (a cons would be an
easy choice:
(let ((x (cons 1 nil)))
(cons x x))
(setf (car (car ...)) 2)
Of course the ideologically sound way to do this would be to have some
explicit box type rather than just using a cons.)
Contrast this to Java where numbers are *not* objects, but there are
classes like Integer whose sole purpose is to box integers. I think
that these classes are in fact themselves immutable in Java - at least
there are no methods to set the value being boxed. Recent Java (5)
specifications provide for a lot of automatic boxing and unboxing of
numbers which obfuscates this distinction somewhat.
--tim
Tim Bradshaw wrote:
> On Mar 14, 10:04 am, Szabolcs Szucs <····@elte.hu> wrote:
>
>
>>This is about objects. But with numbers (how can I pack a number as an
>>object?):
>
>
> Just to clarify what someone else said: numbers *are* objects in CL,
Without object identity, tho, and as objects go that's kinduva big without.
fwiw.
kt
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On Wed, 14 Mar 2007 18:41:11 +0100, Ken Tilton <···@theoryyalgebra.com>
wrote:
>
>
> Tim Bradshaw wrote:
>> On Mar 14, 10:04 am, Szabolcs Szucs <····@elte.hu> wrote:
>>
>>> This is about objects. But with numbers (how can I pack a number as an
>>> object?):
>> Just to clarify what someone else said: numbers *are* objects in CL,
>
> Without object identity, tho, and as objects go that's kinduva big
> without.
>
> fwiw.
>
> kt
>
What do you mean exactly?
They have type. The belong to a class.
if you mean (= a b) <==> (eq a b) then no
and making it so would give horrible performance penalties
(but then you probaly know this)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On 2007-03-14 18:44:37 +0000, "John Thingstad" <··············@chello.no> said:
>
> What do you mean exactly?
> They have type. The belong to a class.
> if you mean (= a b) <==> (eq a b) then no
> and making it so would give horrible performance penalties
> (but then you probaly know this)
I was going to castigate Kenny for not understanding anything and
generally needing a good melting down, but tragically he's right. The
issue is that:
(let ((x 1))
(eq x x))
is allowed to return NIL. That's a very different issue than, say:
(let ((x 1))
(eq x (- (+ x 1) 1)))
--tim
Tim Bradshaw wrote:
> On 2007-03-14 18:44:37 +0000, "John Thingstad"
> <··············@chello.no> said:
>
>>
>> What do you mean exactly?
>> They have type. The belong to a class.
>> if you mean (= a b) <==> (eq a b)
You mean like I said I meant when I referred to object identity? <sigh>
> then no
OK, that's another vote against numbers being objects.
>> and making it so would give horrible performance penalties
>> (but then you probaly know this)
>
>
> I was going to castigate Kenny for not understanding anything and
> generally needing a good melting down, but tragically he's right.
Was the typo in "sleaves" a good alternate justification?
What are those, btw? Not really typos -- maybe phoneticos?
> The
> issue is that:
>
> (let ((x 1))
> (eq x x))
>
> is allowed to return NIL.
Right. Isn't object identity part of the definition in OO? We want to be
able to talk about "That Thing" -- keep track of it, know it when we see
it again, process it differently from "That Other Thing" that is the
same in all respects other than the "Other".
Of course, Lisp invented OO so it gets to call objects what it wants.
Where are the language lawyers when we need them? I would check the CLHS
but I know I will get caught in a cycle clicking on two different
"object" links that lead to each other and lose three hours of programming.
kzo
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On 2007-03-14 21:45:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> Was the typo in "sleaves" a good alternate justification?
No, typos are allowed. Especially for Americans, whose idea of English
is pretty much one huge typo.
>
> Right. Isn't object identity part of the definition in OO? We want to
> be able to talk about "That Thing" -- keep track of it, know it when we
> see it again, process it differently from "That Other Thing" that is
> the same in all respects other than the "Other".
I think so. But there is EQL and I'm not sure what to think about that
- if we treat EQL as the identity operator are we OK?
--tim
Tim Bradshaw wrote:
> On 2007-03-14 21:45:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> Was the typo in "sleaves" a good alternate justification?
>
>
> No, typos are allowed. Especially for Americans, whose idea of English
> is pretty much one huge typo.
>
>>
>> Right. Isn't object identity part of the definition in OO? We want to
>> be able to talk about "That Thing" -- keep track of it, know it when
>> we see it again, process it differently from "That Other Thing" that
>> is the same in all respects other than the "Other".
>
>
> I think so. But there is EQL and I'm not sure what to think about that
> - if we treat EQL as the identity operator are we OK?
Only in the sense that a sledge hammer is a good way to drive home a
finishing nail:
EQ: "Returns true if its arguments are the same, identical object;
otherwise, returns false."
Too easy? Meanwhile the EQL spec is longer than the Scheme spec:
EQL:
"The value of eql is true of two objects, x and y, in the following
cases:
1. If x and y are eq.
2. If x and y are both numbers of the same type and the same value.
3. If they are both characters that represent the same character. "
Looks like an imprecise superset, inefficient, misleading, can return
false positives ... ewwwwwwww!
kzo
--
http://www.theoryyalgebra.com/
On 2007-03-15 00:59:57 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> EQ: "Returns true if its arguments are the same, identical object;
> otherwise, returns false."
>
> Too easy? Meanwhile the EQL spec is longer than the Scheme spec:
>
> EQL:
>
> "The value of eql is true of two objects, x and y, in the following cases:
> 1. If x and y are eq.
> 2. If x and y are both numbers of the same type and the same value.
> 3. If they are both characters that represent the same character. "
>
> Looks like an imprecise superset, inefficient, misleading, can return
> false positives ... ewwwwwwww!
As a thought experiment, if I had built toy universe for you to live in
at birth, and given you only a copy of the spec that I had secretly
edited to remove all mention of EQ and replace EQL's definition with
EQ's would you be happy? I think that in similar circumstances I
probably would (but only probably, there are some niggling issues). So
I think that it is almost the case that if one just forgets EQ and EQLs
definition in terms of it and only remembers EQL, then things are OK.
(Those niggles in full: bignums. In my toy universe I'm a bit
suspicious that implementations always ensure that (eql bignum
(huge-function-which-is-actually-identity bignum)) is true. In
particular I reckon the two bignums are actually often different
objects but the language will not let me see that. I therefore
hypothesise a variant of CL which has an additional function which I
call EQ which does this internal comparison, and in which EQL is
defined in terms of EQ. As an experiment, I construct a toy universe
and place in it one Kenny Tilton, to see how he reacts to the changed
language.)
--tim
Tim Bradshaw wrote:
> On 2007-03-15 00:59:57 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> EQ: "Returns true if its arguments are the same, identical object;
>> otherwise, returns false."
>>
>> Too easy? Meanwhile the EQL spec is longer than the Scheme spec:
>>
>> EQL:
>>
>> "The value of eql is true of two objects, x and y, in the following
>> cases:
>> 1. If x and y are eq.
>> 2. If x and y are both numbers of the same type and the same value.
>> 3. If they are both characters that represent the same character. "
>>
>> Looks like an imprecise superset, inefficient, misleading, can return
>> false positives ... ewwwwwwww!
>
>
> As a thought experiment, if I had built toy universe for you to live in
> at birth, and given you only a copy of the spec that I had secretly
> edited to remove all mention of EQ and replace EQL's definition with
> EQ's would you be happy?
Sure, but that would mean you had arranged for a different language in
which there was no exception for numbers and characters. Neato!
> I think that in similar circumstances I
> probably would (but only probably, there are some niggling issues). So
> I think that it is almost the case that if one just forgets EQ and EQLs
> definition in terms of it and only remembers EQL, then things are OK.
>
> (Those niggles in full: bignums. In my toy universe I'm a bit
> suspicious that implementations always ensure that (eql bignum
> (huge-function-which-is-actually-identity bignum)) is true. In
> particular I reckon the two bignums are actually often different objects
> but the language will not let me see that. I therefore hypothesise a
> variant of CL which has an additional function which I call EQ which
> does this internal comparison, and in which EQL is defined in terms of
> EQ. As an experiment, I construct a toy universe and place in it one
> Kenny Tilton, to see how he reacts to the changed language.)
You lost him, but he is busy getting ready for the unveiling of The Next
Big Lisp Thing (http://www.theoryyalgebra.com/News.html) so ... wish us
luck!
kt
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On Mar 15, 1:02 pm, Ken Tilton <····@theoryyalgebra.com> wrote:
> You lost him, but he is busy getting ready for the unveiling of The Next
> Big Lisp Thing (http://www.theoryyalgebra.com/News.html) so ... wish us
> luck!
>
I've only just looked at that. Looks pretty cool. Is it all you?
Tim Bradshaw wrote:
> On Mar 15, 1:02 pm, Ken Tilton <····@theoryyalgebra.com> wrote:
>
>
>>You lost him, but he is busy getting ready for the unveiling of The Next
>>Big Lisp Thing (http://www.theoryyalgebra.com/News.html) so ... wish us
>>luck!
>>
>
>
> I've only just looked at that. Looks pretty cool. Is it all you?
>
Yep. This is the fun part, getting signage made, arranging shows, doing
the web site, writing all the copy, getting business cards made. I did
this back in the nineties before the Web. My it's easier now. :)
If I make it, the book I will write is "One-Man Show" about all the
tools and tricks and whatever it takes for one individual to do the
whole thing. Federal tax ID, state DBA, MYOB accounting, eventually Kagi ...
But I do plan to contract out some work if this goes well on the
deployment/web programming, so watch this space folks for an RFP.
kt
--
http://www.theoryyalgebra.com/
On Mar 15, 3:33 pm, Ken Tilton <····@theoryyalgebra.com> wrote:
> Tim Bradshaw wrote:
> If I make it, the book I will write is "One-Man Show" about all the
> tools and tricks and whatever it takes for one individual to do the
> whole thing. Federal tax ID, state DBA, MYOB accounting, eventually Kagi ...
That would be an interesting book. Probably unfortunately will end up
annoyingly jurisdiction-specific (the details of solving many of the
same issues change so much from place to place - we had huge
confusions when dealing with some Americans who just could not
understand that in the UK even non-public companies must make their
accounts public), but interesting none-the-less: there is shit loads
of stuff that no one tells you how to do.
--tim
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <%neKh.4$xN1.1@newsfe12.lga>
And the subject line refers to....?
kt
Tim Bradshaw wrote:
> On Mar 15, 3:33 pm, Ken Tilton <····@theoryyalgebra.com> wrote:
>
>>Tim Bradshaw wrote:
>
>
>>If I make it, the book I will write is "One-Man Show" about all the
>>tools and tricks and whatever it takes for one individual to do the
>>whole thing. Federal tax ID, state DBA, MYOB accounting, eventually Kagi ...
>
>
> That would be an interesting book. Probably unfortunately will end up
> annoyingly jurisdiction-specific (the details of solving many of the
> same issues change so much from place to place - we had huge
> confusions when dealing with some Americans who just could not
> understand that in the UK even non-public companies must make their
> accounts public), but interesting none-the-less: there is shit loads
> of stuff that no one tells you how to do.
>
> --tim
>
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On 2007-03-15 16:21:15 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> And the subject line refers to....?
I dunno, I felt I had to change it to something.
From: Vassil Nikolov
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <yy8vird20zos.fsf@eskimo.com>
On Thu, 15 Mar 2007 19:01:30 +0000, Tim Bradshaw <···@tfeb.org> said:
| On 2007-03-15 16:21:15 +0000, Ken Tilton <···@theoryyalgebra.com> said:
|| And the subject line refers to....?
| I dunno, I felt I had to change it to something.
Louis de Funes plays the Minister of Finance in "Delusions of
Grandeur". The film opens with him personally collecting taxes...
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <S5mKh.549$xN1.269@newsfe12.lga>
Tim Bradshaw wrote:
> On 2007-03-15 16:21:15 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> And the subject line refers to....?
>
>
> I dunno, I felt I had to change it to something.
Well, the implicit concern is appreciated, but if you poke around you'll
see I have done this before and (not pokable) I was actually making
decent money at it /without/ the Internet to help with marketing, and
with C instead of Lisp I was still able to get some good results:
http://www.theoryyalgebra.com/roundup.html
http://www.theoryyalgebra.com/macworld.html
Meanwhile, nothing has come along to match what I had then, and what I
have now is somewhere between 50% and 100% better (picking numbers out
of the air, but not too badly, I think).
Meanwhile, we have a bit of an education panic going on now, especially
in math & science, and Algebra is the focus of the math panic -- the US
pretty much just wants kids to graduate HS with Algebra under their belt.
Meanwhile, by staying a one-person + one-artist operation, costs are
negligible, so there is no mad pressure to hit one into the bay, while
the upside (steady revenue from billing per student per year) is
delusively grand.
And boy do I have to hire a lot of Lispers if all goes well, there are a
lot more titles to turn out.
kzo
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On 2007-03-16 01:08:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> Well, the implicit concern is appreciated, but if you poke around
> you'll see I have done this before and (not pokable) I was actually
> making decent money at it /without/ the Internet to help with
> marketing, and with C instead of Lisp I was still able to get some good
> results:
I can see what it looks like, but I actually wasn't trying to imply I
thought you'd fail. I really was just trying to think of some witty
topic & didn't pick a very good one. Sorry!
> Meanwhile, we have a bit of an education panic going on now, especially
> in math & science, and Algebra is the focus of the math panic -- the US
> pretty much just wants kids to graduate HS with Algebra under their
> belt.
Yes, I think this is a good thing to aim at (I mean: this market). I
find it very hard to motivate people that algebra is interesting enough
to spend time on (even very smart, well-taught people), and my `you'll
*really* need to be fluent at this stuff when you're solving non-linear
PDEs in general relativiity' approach probably doesn't work too well
for most people.
--tim
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <qLoKh.3772$gN5.1685@newsfe12.lga>
Tim Bradshaw wrote:
> On 2007-03-16 01:08:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> Well, the implicit concern is appreciated, but if you poke around
>> you'll see I have done this before and (not pokable) I was actually
>> making decent money at it /without/ the Internet to help with
>> marketing, and with C instead of Lisp I was still able to get some
>> good results:
>
>
> I can see what it looks like, but I actually wasn't trying to imply I
> thought you'd fail.
I'll report back in ten days, meanwhile this NG is all yours. Please get
the hounds out for some exercise now and again.
Ta, kzo
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
From: Ken
Subject: Lisp RFP, or Grander Delusions (was Re: Delusions of grandeur (was Re: cons to the same object))
Date:
Message-ID: <FSrNh.1250$Px4.101@newsfe12.lga>
Ken Tilton wrote:
>
>
> Tim Bradshaw wrote:
>> On 2007-03-16 01:08:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>>
>>> Well, the implicit concern is appreciated, but if you poke around
>>> you'll see I have done this before and (not pokable) I was actually
>>> making decent money at it /without/ the Internet to help with
>>> marketing, and with C instead of Lisp I was still able to get some
>>> good results:
>>
>>
>> I can see what it looks like, but I actually wasn't trying to imply I
>> thought you'd fail.
>
> I'll report back in ten days, meanwhile this NG is all yours. Please get
> the hounds out for some exercise now and again.
Reasonably good results. Zero pushback, lotsa raves, a couple of major
metros want to do pilots, a major textbook publisher said something
about partnering. Who knows, but no bartender school yet. Anywho..
I have a nice, cleanly-delimited, precisely-specifiable, milestoneable
chunk of work to outsource, in re the mechanics of application delivery
via download, installers on win and mac, including "Golly, a new version
is available. Want it?" update. User login mechanics. Extremely light
persistence, cl-s3, interface to an e-commerce package. First task is to
establish a list of folks interested in bidding, then I will send them a
nicely detailed spec (which it will be OK to argue with <g>). Due by
July 1 or so.
Please send me an email if you are interested in bidding.
kzo
From: Ken
Subject: Re: Lisp RFP, or Grander Delusions (was Re: Delusions of grandeur (was Re: cons to the same object))
Date:
Message-ID: <rVrNh.1252$Px4.1061@newsfe12.lga>
Ken wrote:
> Ken Tilton wrote:
>>
>>
>> Tim Bradshaw wrote:
>>> On 2007-03-16 01:08:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>>>
>>>> Well, the implicit concern is appreciated, but if you poke around
>>>> you'll see I have done this before and (not pokable) I was actually
>>>> making decent money at it /without/ the Internet to help with
>>>> marketing, and with C instead of Lisp I was still able to get some
>>>> good results:
>>>
>>>
>>> I can see what it looks like, but I actually wasn't trying to imply I
>>> thought you'd fail.
>>
>> I'll report back in ten days, meanwhile this NG is all yours. Please
>> get the hounds out for some exercise now and again.
>
> Reasonably good results. Zero pushback, lotsa raves, a couple of major
> metros want to do pilots, a major textbook publisher said something
> about partnering. Who knows, but no bartender school yet. Anywho..
>
> I have a nice, cleanly-delimited, precisely-specifiable, milestoneable
> chunk of work to outsource, in re the mechanics of application delivery
> via download, installers on win and mac, including "Golly, a new version
> is available. Want it?" update. User login mechanics. Extremely light
> persistence, cl-s3, interface to an e-commerce package. First task is to
> establish a list of folks interested in bidding, then I will send them a
> nicely detailed spec (which it will be OK to argue with <g>). Due by
> July 1 or so.
I meant "work completed by July 1". k
>
> Please send me an email if you are interested in bidding.
>
> kzo
From: Ken Tilton
Subject: Re: Lisp RFP, or Grander Delusions (was Re: Delusions of grandeur (was Re: cons to the same object))
Date:
Message-ID: <CrtNh.2$EM4.1@newsfe12.lga>
Ken wrote:
> Ken Tilton wrote:
>
>>
>>
>> Tim Bradshaw wrote:
>>
>>> On 2007-03-16 01:08:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>>>
>>>> Well, the implicit concern is appreciated, but if you poke around
>>>> you'll see I have done this before and (not pokable) I was actually
>>>> making decent money at it /without/ the Internet to help with
>>>> marketing, and with C instead of Lisp I was still able to get some
>>>> good results:
>>>
>>>
>>>
>>> I can see what it looks like, but I actually wasn't trying to imply I
>>> thought you'd fail.
>>
>>
>> I'll report back in ten days, meanwhile this NG is all yours. Please
>> get the hounds out for some exercise now and again.
>
>
> Reasonably good results. Zero pushback, lotsa raves, a couple of major
> metros want to do pilots, a major textbook publisher said something
> about partnering. Who knows, but no bartender school yet. Anywho..
>
> I have a nice, cleanly-delimited, precisely-specifiable, milestoneable
> chunk of work to outsource, in re the mechanics of application delivery
> via download, installers on win and mac, including "Golly, a new version
> is available. Want it?" update. User login mechanics. Extremely light
> persistence, cl-s3, interface to an e-commerce package. First task is to
> establish a list of folks interested in bidding, then I will send them a
> nicely detailed spec (which it will be OK to argue with <g>). Due by
> July 1 or so.
>
> Please send me an email if you are interested in bidding.
Just found this: http://wiki.alu.org/Consultant
And it occurs to me that I can post this on a web page since there is
nothing application-specific going on. This will be a commercial "Hello
World" app that displays Hello, asks you to login or buy, then displays
world. More soon.
kt
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
From: Vassil Nikolov
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <yy8vhcsk4l0h.fsf@eskimo.com>
On Fri, 16 Mar 2007 02:01:33 +0000, Tim Bradshaw <···@tfeb.org> said:
| ...
| I find it very hard to motivate people that algebra is interesting enough
| to spend time on (even very smart, well-taught people), and my `you'll
| *really* need to be fluent at this stuff when you're solving non-linear
| PDEs in general relativity' approach probably doesn't work too well
| for most people.
But when it works, it works spectacularly well.
I remember how the second-year ODE course (not even PDE) was an
eye-opener with regards to understanding why people had come up with
all that stuff we had studied in the first-year course in linear
algebra.
In any case, algebra is hard (just think of what Galois may have
produced had he not been killed so young...) and then what high
school calls "algebra" has little to do with what algebra _is_.
To a programmer, one might explain algebra as being to mathematics
what the art of abstract data types is to programming (except that
seeing how people think nothing of trespassing across abstraction
boundaries, that might not work very well, either...). To a
musician, I imagine that "The Art of the Fugue" might be a good
analogy, but then not many fugues are written these days.
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
On Mar 17, 3:16 am, Vassil Nikolov <···············@pobox.com> wrote:
>
> I remember how the second-year ODE course (not even PDE) was an
> eye-opener with regards to understanding why people had come up with
> all that stuff we had studied in the first-year course in linear
> algebra.
>
Yes. I think I'm fortunate in that the only person I'm helping learn
algebra (school algebra) is (a) very smart, and (b) good at maths &
physics, so the `you'll need to be fluent in this' argument works
reasonably well & will work better once they get on to doing non-
trivial physics.
> In any case, algebra is hard (just think of what Galois may have
> produced had he not been killed so young...) and then what high
> school calls "algebra" has little to do with what algebra _is_.
> To a programmer, one might explain algebra as being to mathematics
> what the art of abstract data types is to programming (except that
> seeing how people think nothing of trespassing across abstraction
> boundaries, that might not work very well, either...). To a
> musician, I imagine that "The Art of the Fugue" might be a good
> analogy, but then not many fugues are written these days.
That's a good example, but I don't think it needs to be that abstruse
(this is the wrong term, I can't find the right one at this time of
the morning). Even musicians who play quite low-art music spend quite
a lot of time becoming fluent in fundamental things, because that
turns out to matter. For example guitarists spend a lot of time
learning scale patterns and how various scales work. For people
interested in the blues there's a lot more to this than might appear,
because for a given `conventional' scale (not just major/minor but
modal scales too) there are maybe three or four blues variants, and
all of this has to be fitted onto the fretboard in various places (and
then do the whole thing again for each non-standard tuning you care
about). That sort of thing is the high-school algebra of music, and
you *have* to be fluent.
--tim
>>>>> "TB" == Tim Bradshaw <··········@tfeb.org> writes:
TB> That would be an interesting book. Probably unfortunately
TB> will end up annoyingly jurisdiction-specific (the details of
TB> solving many of the same issues change so much from place to
TB> place - we had huge confusions when dealing with some
TB> Americans who just could not understand that in the UK even
TB> non-public companies must make their accounts public), but
TB> interesting none-the-less: there is shit loads of stuff that
TB> no one tells you how to do.
When I looked into setting up a corporation, there was a helpful
bureaucrat at city hall who knew every hoop I had to jump through and
explain the whys and wherefores. This is, alas, extremely
jurisdiction-specific; in this state, fictitious name certificates and
some business registrations are handled locally, and so each town or
city has its own set of requirements and deadlines.
A lot of the local confusions involve tradeoffs: if you take one path,
you must do A and B and C, but not D; while if you take another path,
it costs you $1000 more but doing D doesn't cause the same problems.
But you can't take the first path if you're in a particular zone of
the city, while the second path trumps local zoning ordinances unless
you have employees....
The basic business advice I'd give to anyone in any jurisdiction is to
find a good lawyer, a good accountant, and a helpful bureaucrat, and
don't do anything unless the advice all three give you lines up.
Charlton
--
Charlton Wilbur
·······@chromatico.net
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <HdfKh.516$gN5.445@newsfe12.lga>
Charlton Wilbur wrote:
>>>>>>"TB" == Tim Bradshaw <··········@tfeb.org> writes:
>
>
> TB> That would be an interesting book. Probably unfortunately
> TB> will end up annoyingly jurisdiction-specific (the details of
> TB> solving many of the same issues change so much from place to
> TB> place - we had huge confusions when dealing with some
> TB> Americans who just could not understand that in the UK even
> TB> non-public companies must make their accounts public), but
> TB> interesting none-the-less: there is shit loads of stuff that
> TB> no one tells you how to do.
>
> When I looked into setting up a corporation, there was a helpful
> bureaucrat at city hall who knew every hoop I had to jump through and
> explain the whys and wherefores. This is, alas, extremely
> jurisdiction-specific; in this state, fictitious name certificates and
> some business registrations are handled locally, and so each town or
> city has its own set of requirements and deadlines.
>
> A lot of the local confusions involve tradeoffs: if you take one path,
> you must do A and B and C, but not D; while if you take another path,
> it costs you $1000 more but doing D doesn't cause the same problems.
> But you can't take the first path if you're in a particular zone of
> the city, while the second path trumps local zoning ordinances unless
> you have employees....
>
> The basic business advice I'd give to anyone in any jurisdiction is to
> find a good lawyer, a good accountant, and a helpful bureaucrat, and
> don't do anything unless the advice all three give you lines up.
You clowns are ruining my book, and clearly have missed the point. Next
I expect to hear someone agonizing over handling different sales tax
rates in different states. The story of the solo entrepreneur is about a
huge sweep of activities from direct mailing (which breaks down to about
ten subcategories) to... oh, what's the point?
Pearls. Swine. Please note order.
kt
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
>>>>> "KT" == Ken Tilton <···@theoryyalgebra.com> writes:
KT> You clowns are ruining my book, and clearly have missed the
KT> point. Next I expect to hear someone agonizing over handling
KT> different sales tax rates in different states. The story of
KT> the solo entrepreneur is about a huge sweep of activities from
KT> direct mailing (which breaks down to about ten subcategories)
KT> to... oh, what's the point?
If we wanted the Grand Huge Sweep of Entrepreneurial Individuality,
we'd go off and read some Ayn Rand and fantasize about how superior We
are to all the unwashed masses, and how if it weren't for Them, We
would rule the world.
(Substitute c.l.l for Rand as desired.)
Charlton
--
Charlton Wilbur
·······@chromatico.net
On 2007-03-15 17:18:31 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> You clowns are ruining my book, and clearly have missed the point. Next
> I expect to hear someone agonizing over handling different sales tax
> rates in different states. The story of the solo entrepreneur is about
> a huge sweep of activities from direct mailing (which breaks down to
> about ten subcategories) to... oh, what's the point?
No, that's what I hoped you were going to write about (and it's the
interesting bit). Some of that stuff is still somewhat
jurisdiction-specific.
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <7OhKh.166$vM6.125@newsfe12.lga>
Tim Bradshaw wrote:
> On 2007-03-15 17:18:31 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> You clowns are ruining my book, and clearly have missed the point.
>> Next I expect to hear someone agonizing over handling different sales
>> tax rates in different states. The story of the solo entrepreneur is
>> about a huge sweep of activities from direct mailing (which breaks
>> down to about ten subcategories) to... oh, what's the point?
>
>
> No, that's what I hoped you were going to write about (and it's the
> interesting bit). Some of that stuff is still somewhat
> jurisdiction-specific.
You mean in England an RGB image whose blues look just fabulous on the
workstation come out fabulous when converted to CMYK for printing?
<sigh>
kzo
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On 2007-03-15 20:13:54 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> You mean in England an RGB image whose blues look just fabulous on the
> workstation come out fabulous when converted to CMYK for printing?
Yes. Or rather: probably not, but one's servants sort that sort of
issue out for one.
From: Ken Tilton
Subject: Re: Delusions of grandeur (was Re: cons to the same object)
Date:
Message-ID: <%2nKh.2630$gN5.1343@newsfe12.lga>
Tim Bradshaw wrote:
> On Mar 15, 3:33 pm, Ken Tilton <····@theoryyalgebra.com> wrote:
>
>>Tim Bradshaw wrote:
>
>
>>If I make it, the book I will write is "One-Man Show" about all the
>>tools and tricks and whatever it takes for one individual to do the
>>whole thing. Federal tax ID, state DBA, MYOB accounting, eventually Kagi ...
>
>
> That would be an interesting book. Probably unfortunately will end up
> annoyingly jurisdiction-specific (the details of solving many of the
> same issues change so much from place to place - we had huge
> confusions when dealing with some Americans who just could not
> understand that in the UK even non-public companies must make their
> accounts public),
If you think we are dense, hey, you are the one thinking an American
might feel bad about forgetting the world outside DubbyaLand.
Your other mistake is thinking I was planning a 500-page treatise
complete with suggested legal forms. I am an American, we have Cliff
Notes for haiku.
Peace, kzo.
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
On 2007-03-16 02:13:15 +0000, Ken Tilton <···@theoryyalgebra.com> said:
> If you think we are dense, hey, you are the one thinking an American
> might feel bad about forgetting the world outside DubbyaLand.
No. I just happen to have experience of US companies operating in the
UK, not the other way around. I'm quite sure it happens the other way.
("just could not understand" was perhaps too strong, I meant "were
astonished or something.)
> Your other mistake is thinking I was planning a 500-page treatise
> complete with suggested legal forms. I am an American, we have Cliff
> Notes for haiku.
Wrong. I think I've failed to get across what I was thinking but,
well, it's late and there's no more mileage to be had in this sub
thread, so I won't try and explain.
--tim
On Wed, 14 Mar 2007 23:32:58 +0100, Tim Bradshaw <···@tfeb.org> wrote:
> On 2007-03-14 21:45:02 +0000, Ken Tilton <···@theoryyalgebra.com> said:
>
>> Was the typo in "sleaves" a good alternate justification?
>
> No, typos are allowed. Especially for Americans, whose idea of English
> is pretty much one huge typo.
>
>> Right. Isn't object identity part of the definition in OO? We want to
>> be able to talk about "That Thing" -- keep track of it, know it when we
>> see it again, process it differently from "That Other Thing" that is
>> the same in all respects other than the "Other".
>
> I think so. But there is EQL and I'm not sure what to think about that
> - if we treat EQL as the identity operator are we OK?
>
> --tim
>
I think the reason for my question is that I don't associate eq with
object identity. To me it means are two objects at the same address in
memory.
I don't think this is in any way equivalent to object identity in OO.
So the real error is perhaps assuming that eq means object identity.
eq, after all, existed long before CLOS and is not directly related.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On 2007-03-14 22:55:33 +0000, "John Thingstad" <··············@chello.no> said:
> eq, after all, existed long before CLOS and is not directly related.
CLOS is not what makes Lisp an object oriented language...
Tim Bradshaw <···@tfeb.org> writes:
>> Right. Isn't object identity part of the definition in OO? We want
>> to be able to talk about "That Thing" -- keep track of it, know it
>> when we see it again, process it differently from "That Other
>> Thing" that is the same in all respects other than the "Other".
>
> I think so. But there is EQL and I'm not sure what to think about
> that - if we treat EQL as the identity operator are we OK?
I think so, yes. Basically if you treat EQ as the object identity
predicate (which, sadly, the spec does through it's use of
"identical") then it gets hairy to claim that "all values are objects
in CL" because there's no identiy predicate for characters and
numbers. On the other hand if we squint and treat EQL (which, per the
spec, tests whether objects are "the same") as the identity predicate
then all values are objects, with a meaningful identity.
FWIW, I didn't just make up this theory; I got it from Kent Pitman:
Message-ID: <···············@world.std.com>
But to understand EQ you must know things about the implementation
you were never intended to know. EQL should have been called EQ and
what is now EQ never should have been part of Common Lisp becuase
its effects are too unportable. It's one of those historical details
like FIXNUM that are there more out of fear than need.
-Peter
On Thu, 15 Mar 2007 15:24:10 -0700, Peter Seibel <·····@gigamonkeys.com> said:
| Tim Bradshaw <···@tfeb.org> writes:
||| Right. Isn't object identity part of the definition in OO? We want
||| to be able to talk about "That Thing" -- keep track of it, know it
||| when we see it again, process it differently from "That Other
||| Thing" that is the same in all respects other than the "Other".
||
|| I think so. But there is EQL and I'm not sure what to think about
|| that - if we treat EQL as the identity operator are we OK?
| I think so, yes. Basically if you treat EQ as the object identity
| predicate (which, sadly, the spec does through it's use of
| "identical") then it gets hairy to claim that "all values are objects
| in CL" because there's no identiy predicate for characters and
| numbers. On the other hand if we squint and treat EQL (which, per the
| spec, tests whether objects are "the same") as the identity predicate
| then all values are objects, with a meaningful identity.
| FWIW, I didn't just make up this theory; I got it from Kent Pitman:
| Message-ID: <···············@world.std.com>
| But to understand EQ you must know things about the implementation
| you were never intended to know. EQL should have been called EQ and
| what is now EQ never should have been part of Common Lisp becuase
| its effects are too unportable. It's one of those historical details
| like FIXNUM that are there more out of fear than need.
I think that the tradeoff here is more difficult to resolve. In
defence of good old EQ, let us note that:
1. It only breaks down for immutable objects, and to boldly
paraphrase, all objects need identity, but mutable objects need more
identity than immutable ones. (Formalize that!)
2. In the general case, only EQ is guaranteed to always be fast
(though, of course, in practice in the majority of the cases that is
of no consequence). Conceptually, we can certainly establish that
any integer is equal to the same integer in the blink of an eye, but
for any real computer, the blink is significantly shorter if the
integer fits in a machine word.
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
Vassil Nikolov <···············@pobox.com> writes:
> 2. In the general case, only EQ is guaranteed to always be fast
Fast compared to what, and why guaranteed?
My first CL port as an official Franz employee was to the Cray X/MP, a
64-bit machine with 24-bit word-address space. Because it was a
word-addressed machine, we had to put tagged pointers into (64-bit)
data registers, and we placed the tag/type in the upper byte. Fixnums
had two tags, #x00 and #xff, but only had magnitude of 24 significant
bits - the rest of the word was filled with the sign (the 24th bit)
which explains the two fixnum tags of 0 (for positive fixnums) and -1
(for negative fixnums).
Anyway, at one point we contemplated doing some special
architecture-specific work for Cray, which included the possibility of
cdr-coding lists. What this would have required, though, was some
usage of those extra bits between bit 24 and bit 56. But then, two
tagged pointers to the same cons cell would have not had the same bit
pattern, and an EQ test would have required a mask operation on both
values before the comparison instruction could be performed.
We made the decision to not go that way, but someone else might not
have done so.
Nope; no guarantee.
> (though, of course, in practice in the majority of the cases that is
> of no consequence). Conceptually, we can certainly establish that
> any integer is equal to the same integer in the blink of an eye, but
> for any real computer, the blink is significantly shorter if the
> integer fits in a machine word.
The only usefulness of EQ over EQL is that it is usually (but not
guaranteed to be :-) a single instruction, and yes, in order for the
single-instruction to be possible, it _must_ fit into a single word.
But note that in CL EQ is not the default test for funtions which
check for sameness; EQL is. There is a reason for that.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
On Thu, 15 Mar 2007 23:17:13 -0700, Duane Rettig <·····@franz.com> said:
| Vassil Nikolov <···············@pobox.com> writes:
|| 2. In the general case, only EQ is guaranteed to always be fast
| Fast compared to what, and why guaranteed?
Let me rephrase that. It is _possible_ to implement Common Lisp such
that EQ's execution time will be bounded and comparable to the time it
takes to test two machine words for equality (and many implementations
are indeed done in such a way). On the other hand, in any
implementation it is _impossible_, in the general case, to avoid EQL's
execution time growing with the size of its argument. In that sense,
EQ is fast (compared to EQL).
"Guaranteed to be fast" was a poor choice of words on my part, to be
sure; thanks for pointing that out.
| ...
| The only usefulness of EQ over EQL is that it is usually (but not
| guaranteed to be :-) a single instruction, and yes, in order for the
| single-instruction to be possible, it _must_ fit into a single word.
| But note that in CL EQ is not the default test for funtions which
| check for sameness; EQL is. There is a reason for that.
Indeed. I was arguing only that EQ should be kept in the service,
rather than discharged; I was not arguing that it should be promoted
to the same position and rank as EQL.
(And no, I do not have the habit of typing :TEST #'EQ to override
the default...)
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
On 2007-03-17 02:24:00 +0000, Vassil Nikolov <···············@pobox.com> said:
> On the other hand, in any
> implementation it is _impossible_, in the general case, to avoid EQL's
> execution time growing with the size of its argument.
If you mean that EQL will be slow for large bignums then, well, yes.
Otherwse, no.
On 2007-03-15 22:24:10 +0000, Peter Seibel <·····@gigamonkeys.com> said:
> I think so, yes. Basically if you treat EQ as the object identity
> predicate (which, sadly, the spec does through it's use of
> "identical") then it gets hairy to claim that "all values are objects
> in CL" because there's no identiy predicate for characters and
> numbers. On the other hand if we squint and treat EQL (which, per the
> spec, tests whether objects are "the same") as the identity predicate
> then all values are objects, with a meaningful identity.
But then I think you have horrible problems with (particularly, but
probably not only) bignums, where it becomes clear to you that the
system is almost certainly lying about two objects being identical.
However given immutability, those problems actually don't matter in the
sense that you can't call it on the lie. So may be that is OK.
Tim Bradshaw <···@tfeb.org> writes:
> On 2007-03-15 22:24:10 +0000, Peter Seibel <·····@gigamonkeys.com> said:
>
>> I think so, yes. Basically if you treat EQ as the object identity
>> predicate (which, sadly, the spec does through it's use of
>> "identical") then it gets hairy to claim that "all values are objects
>> in CL" because there's no identiy predicate for characters and
>> numbers. On the other hand if we squint and treat EQL (which, per the
>> spec, tests whether objects are "the same") as the identity predicate
>> then all values are objects, with a meaningful identity.
>
> But then I think you have horrible problems with (particularly, but
> probably not only) bignums, where it becomes clear to you that the
> system is almost certainly lying about two objects being identical.
> However given immutability, those problems actually don't matter in
> the sense that you can't call it on the lie. So may be that is OK.
I think it is because, as you say, you can't call in on the lie.
Imagine for the sake of argument that some implementation implemented
some other class (say vectors) such that instances might periodically
live in two places in memory simultaneously. Obviously to be Common
Lisp the implementation would have to arrange that modifications made
to one were made to the other as well and would have to implement EQ
such that it treated these two copies of the "identical" object as
being identical per EQ. I'm not saying I can think of any good reason
for such an implementation but it would be conforming. In some sense
EQ would be "lying" to you when it says that the values of two
variables that each hold a reference to one copy of the object are
identical but as long as you can't tell the difference, what does it
matter.
Another point is, it's not like you can reliably use EQ to tell that
two bignums *are* different. The spec simply says that (eq x y) can be
either true or false when x and y are numbers or characters--not that
it will reliably distinguish between EQL object that happen to live at
different places in memory.
The way I look at it, EQL's behavior with regard to numbers (and
characters) is a performance hack that allows the "object identity" of
numbers to correspond to their mathematical identity without the
implementation actually having to intern all numbers used by a
program.
-Peter
On Mar 16, 4:34 am, Peter Seibel <····@gigamonkeys.com> wrote:
> I think it is because, as you say, you can't call in on the lie.
> Imagine for the sake of argument that some implementation implemented
> some other class (say vectors) such that instances might periodically
> live in two places in memory simultaneously. Obviously to be Common
> Lisp the implementation would have to arrange that modifications made
> to one were made to the other as well and would have to implement EQ
> such that it treated these two copies of the "identical" object as
> being identical per EQ. I'm not saying I can think of any good reason
> for such an implementation but it would be conforming. In some sense
> EQ would be "lying" to you when it says that the values of two
> variables that each hold a reference to one copy of the object are
> identical but as long as you can't tell the difference, what does it
> matter.
I think this is somewhat parallel to cache-coherent multiprocessing
systems. They're allowed to copy the same chunk of memory around,
have it locally available for modification, etc., all they want -- as
long as they keep this hidden from us. Which is a great thing, we get
the illusion of having n processors all directly wired to the same
memory, and we get the advantage of processor caches. And I don't see
any reason why we can't have our cake and eat it when it comes to
numbers in CL. In fact, you kind of have to go out of your way
already, since everything built in (find, member, hash tables ...) use
eql by default.
(And performance is a complete nonsense red-herring that tends to get
thrown into the conversation. There are no performance issues with
eql when combined with a good implementation and a compiler with some
minimal amount of type inferencing. Without those two things, I
hardly think that eql is your greatest performance problem)
>
> Another point is, it's not like you can reliably use EQ to tell that
> two bignums *are* different. The spec simply says that (eq x y) can be
> either true or false when x and y are numbers or characters--not that
> it will reliably distinguish between EQL object that happen to live at
> different places in memory.
>
> The way I look at it, EQL's behavior with regard to numbers (and
> characters) is a performance hack that allows the "object identity" of
> numbers to correspond to their mathematical identity without the
> implementation actually having to intern all numbers used by a
> program.
>
> -Peter
On Mar 16, 10:05 am, "Thomas F. Burdick" <········@gmail.com> wrote:
> I think this is somewhat parallel to cache-coherent multiprocessing
> systems.
Yes. Or even actually single-processor machines with cache: where,
actually, *is* that object you're looking at? Probably it's in
several places (perhaps: cache, main memory, and the file that is
mapped to the memory) and if you've modified it those several places
may well not even be the same. But the system will lie to you that
they are, and then arrange life such that if you ever look then
actually, they are (actually, you likely have to give it some help
with the mapped file case).
Most modern computer architecture is the art of lying to the user in
such a way that they can't tell.
>
> (And performance is a complete nonsense red-herring that tends to get
> thrown into the conversation.
Exactly! Generally (but not here I think) by people who don't have
any idea what the performance characteristics of modern machine is.
--tim
On 16 Mar 2007 03:51:38 -0700, "Tim Bradshaw" <··········@tfeb.org> said:
| ...
| Exactly! Generally (but not here I think) by people who don't have
| any idea what the performance characteristics of modern machine is.
Especially those state-of-the-art aleph-zero-core CPUs that can
compute an undefined value in about 42 microseconds...
---Vassil.
P.S. This red herring is not to be construed as disagreement with
the points of the followed-up-to post.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
Tim Bradshaw <···@tfeb.org> writes:
> On 2007-03-14 18:44:37 +0000, "John Thingstad" <··············@chello.no> said:
>
>>
>> What do you mean exactly? They have type. The belong to a class. if
>> you mean (= a b) <==> (eq a b) then no and making it so would give
>> horrible performance penalties (but then you probaly know this)
>
> I was going to castigate Kenny for not understanding anything and
> generally needing a good melting down, but tragically he's right.
> The issue is that:
>
> (let ((x 1))
> (eq x x))
>
> is allowed to return NIL.
Which is why everyone but CL implementors (working within their own
implementation) should ignore the existence of EQ and use EQL.
-Peter
P.S. Newbies, this is not a universally shared opinion. Some will
argue that "it's better to use EQ because it says, 'I know these
values will never be characters or numbers'". Of course looking at a
random piece of code using EQ, you have to wonder whether the author
really meant that or just didn't think about the fact that EQ wouldn't
necessarily work for character and number values.
Peter Seibel wrote:
> Tim Bradshaw <···@tfeb.org> writes:
>
>
>>On 2007-03-14 18:44:37 +0000, "John Thingstad" <··············@chello.no> said:
>>
>>
>>>What do you mean exactly? They have type. The belong to a class. if
>>>you mean (= a b) <==> (eq a b) then no and making it so would give
>>>horrible performance penalties (but then you probaly know this)
>>
>>I was going to castigate Kenny for not understanding anything and
>>generally needing a good melting down, but tragically he's right.
>>The issue is that:
>>
>>(let ((x 1))
>> (eq x x))
>>
>>is allowed to return NIL.
>
>
> Which is why everyone but CL implementors (working within their own
> implementation) should ignore the existence of EQ and use EQL.
>
> -Peter
>
> P.S. Newbies, this is not a universally shared opinion. Some will
> argue that "it's better to use EQ because it says, 'I know these
> values will never be characters or numbers'". Of course looking at a
> random piece of code using EQ, you have to wonder whether the author
> really meant that or just didn't think about the fact that EQ wouldn't
> necessarily work for character and number values.
OK, the honeymoon is over. Nonsense! It could also mean, oh, look, the
person has read PCL and knows when EQ is OK. Using EQL when you know you
are looking for object identity (you are testing that Something Else is
the same symbol or CLOS object or struct or whatever) is just ignorance.
Why not learn the language?! Allowed exceptions being extra parens in C
rather than pray one has the precedence right.
This is perilously close to "don't use destructive list functions until
your second year of Lisp...."
kzo
--
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
"Algebra is the metaphysics of arithmetic." - John Ray
http://www.theoryyalgebra.com/
Peter Seibel wrote:
> Which is why everyone but CL implementors (working within their own
> implementation) should ignore the existence of EQ and use EQL.
However, eql in typical implementations is a rather more expensive
operation than eq in the false case. That is sufficient reason for
using eq when the arguments are known not to be numbers or characters.
On Mar 16, 6:43 am, Steven Haflich <····@alum.mit.edu> wrote:
> However, eql in typical implementations is a rather more expensive
> operation than eq in the false case.
I'd be interested in any non-artificial cases on architectures
implemented in the last 15 years where the performance difference was
in any sense significant.
It seems to me that in the cases where EQ is useful (in other words
not for numbers) the difference between it and EQL is that EQL needs
to typecheck its arguments, checking for some very specific,
statically-known types (namely number & character types, or actually
presumably the non-immediate variants of them). I guess the question
then is: does that check need to do additional fetches from memory?
I'm guessing it doesn't. In that case the whole extra overhead of EQL
ought to be some extra operations on registers, which really ought to
be very little.
I guess the case where the difference might show up would be when very
large numbers of objects are being compared, but presumably in that
case the performance will be hugely dominated by memory bandwidth /
latency, since those very large numbers of objects must be coming from
somewhere. (The artificial case would be a huge number of comparisons
on a very small number of objects, but, well.)
Of course EQL probably does generate more memory traffic in the case
where it actually has to do extra work, and EQ would then be faster.
But it's faster because it doesn't get the right answer, and I can
write code which is very fast indeed if the right answer is not a
requirement.
--tim
"Tim Bradshaw" <··········@tfeb.org> writes:
> It seems to me that in the cases where EQ is useful (in other words
> not for numbers) the difference between it and EQL is that EQL needs
> to typecheck its arguments, checking for some very specific,
> statically-known types (namely number & character types, or actually
> presumably the non-immediate variants of them). I guess the
> question then is: does that check need to do additional fetches from
> memory? I'm guessing it doesn't. In that case the whole extra
> overhead of EQL ought to be some extra operations on registers,
> which really ought to be very little.
I believe that many, if not most, implementations requre one extra
memory reference to do (typep x 'number), unless x is a fixnum.
From the point of view of an implementor, however, this observation
makes it interesting to allocate a separate lowtag for pointers to
numbers, precisely to avoid this extra memory reference in
EQL. Whether it's actually worth it, depends of course on the
frequency of such occurrences.. it would be interesting to see som
profiling data on this.
--
Frode Vatvedt Fjeld
On Mar 16, 11:04 am, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
>
> From the point of view of an implementor, however, this observation
> makes it interesting to allocate a separate lowtag for pointers to
> numbers, precisely to avoid this extra memory reference in
> EQL.
Also to make arithmetic on non-immediate numbers less awful. But
again, that may not be worth it, since presumably it's a better use of
implementor's time to arrange that such arithmetic doesn't happen very
often.
So I guess if you do need an extra fetch that might make EQL really
quite bad even in the good case as it must very often make an extra
memory reference per arg compared with EQ.
On Mar 16, 12:52 pm, "Tim Bradshaw" <··········@tfeb.org> wrote:
> On Mar 16, 11:04 am, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
>
>
>
> > From the point of view of an implementor, however, this observation
> > makes it interesting to allocate a separate lowtag for pointers to
> > numbers, precisely to avoid this extra memory reference in
> > EQL.
>
> Also to make arithmetic on non-immediate numbers less awful. But
> again, that may not be worth it, since presumably it's a better use of
> implementor's time to arrange that such arithmetic doesn't happen very
> often.
>
> So I guess if you do need an extra fetch that might make EQL really
> quite bad even in the good case as it must very often make an extra
> memory reference per arg compared with EQ.
Of course, if this code is actually important, performance wise, and
the programmer could not convince the implementation that neither
argument to EQL is a non-immediate number ... well, just like how I
never believe programmers who claim to know the bounds of their
arrays, I don't think it makes sense to trust them here.
On Mar 16, 11:04 am, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> > From the point of view of an implementor, however, this
> > observation makes it interesting to allocate a separate lowtag for
> > pointers to numbers, precisely to avoid this extra memory
> > reference in EQL.
"Tim Bradshaw" <··········@tfeb.org> writes:
> Also to make arithmetic on non-immediate numbers less awful. But
> again, that may not be worth it, since presumably it's a better use
> of implementor's time to arrange that such arithmetic doesn't happen
> very often.
I think such a pointer type will not be particularly helpful for the
arithmetic operators, unfortunately. Because, you need to look up
which particular numeric type you've got, unless you can afford one
low-tag per numeric type (which is rather unlikely). And besides,
you'll need to look at the actual contents of the value in any event,
presumably on the same cache line as the type information.
--
Frode Vatvedt Fjeld
On Mar 16, 2:00 pm, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> I think such a pointer type will not be particularly helpful for the
> arithmetic operators, unfortunately. Because, you need to look up
> which particular numeric type you've got, unless you can afford one
> low-tag per numeric type (which is rather unlikely). And besides,
> you'll need to look at the actual contents of the value in any event,
> presumably on the same cache line as the type information.
Yes. I was thinking that if there was a `this is a number' tag it
would help (EQL and) the arithmetic operators give up suitably early
if they had things that were not numbers. But that won't happen very
often and when it does who actually cares about the performance? So I
was just completely wrong, basically.
--tim
"Tim Bradshaw" <··········@tfeb.org> writes:
> On Mar 16, 2:00 pm, Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
>
>> I think such a pointer type will not be particularly helpful for the
>> arithmetic operators, unfortunately. Because, you need to look up
>> which particular numeric type you've got, unless you can afford one
>> low-tag per numeric type (which is rather unlikely). And besides,
>> you'll need to look at the actual contents of the value in any event,
>> presumably on the same cache line as the type information.
>
> Yes. I was thinking that if there was a `this is a number' tag it
> would help (EQL and) the arithmetic operators give up suitably early
> if they had things that were not numbers. But that won't happen very
> often and when it does who actually cares about the performance? So I
> was just completely wrong, basically.
Which makes me think there's one part of the modern CPU where there's
such a tag: the floating point unit, with NANs. What if we stored all
the non numeric types as NANs? :-)
--
__Pascal Bourguignon__
http://www.informatimago.com
http://pjb.ogamita.org
Steven Haflich <···@alum.mit.edu> writes:
> However, eql in typical implementations is a rather more expensive
> operation than eq in the false case. That is sufficient reason for
> using eq when the arguments are known not to be numbers or
> characters.
This was my conclusion also, the last time this was discussed here,
maybe a couple of years ago: Treat EQ as a shortcut for something
approximately like
(eql (the (not (or number character)) x)
(the (not (or number character)) y))
--
Frode Vatvedt Fjeld
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
+---------------
| Steven Haflich <···@alum.mit.edu> writes:
| > However, eql in typical implementations is a rather more expensive
| > operation than eq in the false case. That is sufficient reason for
| > using eq when the arguments are known not to be numbers or
| > characters.
|
| This was my conclusion also, the last time this was discussed here,
| maybe a couple of years ago: Treat EQ as a shortcut for something
| approximately like
| (eql (the (not (or number character)) x)
| (the (not (or number character)) y))
+---------------
Conversely, one may hope that the implementation of EQL is always
at *least* as good as this:
(or (eq x y)
(and (characterp x) (characterp y) (char= x y))
(and (numberp x) (numberp y) (= x y)))
which isn't actually all that slow except for the leaf cases
of "char=" with hugely-complex Unicode and "=" with bignums.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> (or (eq x y)
> (and (characterp x) (characterp y) (char= x y))
> (and (numberp x) (numberp y) (= x y)))
>
> which isn't actually all that slow except for the leaf cases
> of "char=" with hugely-complex Unicode and "=" with bignums.
But it's wrong. (eql 1.0 1) is false, but your implementation would
return t.
...Peder...
--
I wish a new life awaited _me_ in some off-world colony.
Peder O. Klingenberg <·····@news.klingenberg.no> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
|
| > (or (eq x y)
| > (and (characterp x) (characterp y) (char= x y))
| > (and (numberp x) (numberp y) (= x y)))
| >
| > which isn't actually all that slow except for the leaf cases
| > of "char=" with hugely-complex Unicode and "=" with bignums.
|
| But it's wrong. (eql 1.0 1) is false, but your implementation would
| return t.
+---------------
Yikes! Right you are! I'd forgotten all about that business of
"types" in numeric comparisons. *YUCK!*
So is this good enough?
(defun my-eql (x y)
(cond
((eq x y)
t)
((and (characterp x) (characterp y))
(char= x y))
((and (complexp x) (complexp y))
(and (my-eql (realpart x) (realpart y))
(my-eql (imagpart x) (imagpart y))))
((and (numberp x)
(numberp y)
(subtypep (type-of x) (type-of y))
(subtypep (type-of y) (type-of x)))
(= x y))
(t
nil))
It does at least satisfy the weird complex number example cases
at the bottom of CLHS "Function EQL"...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Fri, 16 Mar 2007 10:57:27 +0100, Rob Warnock <····@rpw3.org> wrote:
>
> So is this good enough?
>
> (defun my-eql (x y)
> (cond
> ((eq x y)
> t)
> ((and (characterp x) (characterp y))
> (char= x y))
> ((and (complexp x) (complexp y))
> (and (my-eql (realpart x) (realpart y))
> (my-eql (imagpart x) (imagpart y))))
> ((and (numberp x)
> (numberp y)
> (subtypep (type-of x) (type-of y))
> (subtypep (type-of y) (type-of x)))
> (= x y))
> (t
> nil))
>
> It does at least satisfy the weird complex number example cases
> at the bottom of CLHS "Function EQL"...
>
All I wanny do is compare the address of two cons cells and you force
me to do all this.. I need eq :)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
[Sorry for the belated reply... still catching
up from whatever the local cold/flu crud was...]
Vassil Nikolov <···············@pobox.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) said:
| | (defun my-eql (x y)
| | (cond
| | ((eq x y)
| | t)
| | ((and (characterp x) (characterp y))
| | (char= x y))
| | ((and (complexp x) (complexp y))
| | (and (my-eql (realpart x) (realpart y))
| | (my-eql (imagpart x) (imagpart y))))
| | ((and (numberp x)
| | (numberp y)
| | (subtypep (type-of x) (type-of y))
| | (subtypep (type-of y) (type-of x)))
| | (= x y))
| | (t
| | nil))
|
| You can use = for complex numbers as well.
+---------------
Uh... Actually, no you can't!! :-(
> (= #c(4 5) #c(4.0 5.0))
T
> (eql #c(4 5) #c(4.0 5.0))
NIL
>
Look at the bottom of the CLHS "Function EQL" page which
specifically discusses this case, and which is why I put
the test for COMPLEX before the test for NUMBER:
Two complex numbers are considered to be eql if their
real parts are eql and their imaginary parts are eql.
Compare with CLHS "Function =", which says:
Two complexes are considered equal by = if their real
and imaginary parts are equal according to =.
But EQL & "=" treat fixed & float equality differently:
> (= 4 4.0)
T
> (eql 4 4.0)
NIL
>
+---------------
| A bigger worry is the use of TYPE-OF, though---somehow,
| it lacks that proverbial warm, fuzzy feeling...
+---------------
I didn't like it either, but I couldn't think of any other way to
exactly match the semantics of the CLHS "Function EQL", which says:
2. If x and y are both numbers of the same type and the same value.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Fri, 23 Mar 2007 22:27:39 -0500, ····@rpw3.org (Rob Warnock) said:
| ...
| Vassil Nikolov <···············@pobox.com> wrote:
| ...
| | You can use = for complex numbers as well.
| +---------------
| Uh... Actually, no you can't!! :-(
|| (= #c(4 5) #c(4.0 5.0))
No, indeed not. My mistake of not paying enough attention.
---Vassil.
--
The truly good code is the obviously correct code.
On Wed, 14 Mar 2007 21:29:19 +0100, Tim Bradshaw <···@tfeb.org> wrote:
> On 2007-03-14 18:44:37 +0000, "John Thingstad"
> <··············@chello.no> said:
>
>> What do you mean exactly?
>> They have type. The belong to a class.
>> if you mean (= a b) <==> (eq a b) then no
>> and making it so would give horrible performance penalties
>> (but then you probaly know this)
>
> I was going to castigate Kenny for not understanding anything and
> generally needing a good melting down, but tragically he's right. The
> issue is that:
>
> (let ((x 1))
> (eq x x))
>
> is allowed to return NIL.
Well the above is almost certainly t.
But you are right that in the general case this is not true and
you can, or at least should not, rely on it.
I suggest you look at how it is doe in Python.
There - each number is allocated exactly once and all references to that
number
thus are to the same address. The downside of this is that Python's integer
performance sucks. This is probably recognised as one of the worst
decisions of
the Python design. So I feel Lisp's way is a reasonable trade-off.
Why is it so important that two numbers of the same value reside at the
the same address?
I feel calling it object identity kinda obfuscates the issue.
For instance insisting on object identity eliminates the possibility for
register optimisation.
Oddly I never missed it much so I fail to see why this is a big deal.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> What do you mean exactly?
> They have type. The belong to a class.
> if you mean (= a b) <==> (eq a b) then no
> and making it so would give horrible performance penalties
> (but then you probaly know this)
Object identity does not imply all equal objects have the same
identity. So you wouldn't have to intern all numbers. Rather,
it implies (eq a a), which currently is not guaranteed true for
numbers and characters. I suppose requiring this would still
prevent some optimizations, though:
(defvar *numbers* '())
(defun compute (number)
(when (zerop (random 100))
(push number *numbers*))
(atan number))
(defun repeat ()
(loop with number = (random 1.0d0)
repeat 1000
do (compute number)))
If these definitions are in a file that is compiled, then REPEAT
is known to call this version of COMPUTE, and the NUMBER
parameter can be passed in a register all the way to ATAN without
boxing. If COMPUTE decides to push the number to *NUMBERS*, it
must box it. If different runs of COMPUTE box the same number,
the objects pushed to *NUMBERS* are most likely not EQ. Now if
numbers had reliable object identity, then the objects would have
to be EQ, because they are all the same number that was returned
from (random 1.0d0) just once. To implement this, I suppose
either REPEAT should box the number regardless of whether the box
will actually be needed, or the calling convention should somehow
let COMPUTE communicate back to REPEAT whether it boxed the
number and where the box is... this latter scheme seems
perilously complex to implement.
Kalle Olavi Niemitalo <···@iki.fi> writes:
> "John Thingstad" <··············@chello.no> writes:
>
>> What do you mean exactly?
>> They have type. The belong to a class.
>> if you mean (= a b) <==> (eq a b) then no
>> and making it so would give horrible performance penalties
>> (but then you probaly know this)
>
> Object identity does not imply all equal objects have the same
> identity.
However, it should imply that objects do not lose their identity. Thus
if numbers are objects EQ is actually an object identity predicate
then:
(let ((x 1)) (eq x x))
should be true. But the spec allows it to be false. Which simply means
that at a user-level numbers are not objects with idenity under EQ.
But they do have identity under EQL. (See my other recent post in this
thread for a quote from Kent Pitman about how EQ should really be EQL
and what we call EQ shouldn't be in the language.)
> So you wouldn't have to intern all numbers. Rather, it implies (eq a
> a), which currently is not guaranteed true for numbers and
> characters. I suppose requiring this would still prevent some
> optimizations, though:
>
> (defvar *numbers* '())
>
> (defun compute (number)
> (when (zerop (random 100))
> (push number *numbers*))
> (atan number))
>
> (defun repeat ()
> (loop with number = (random 1.0d0)
> repeat 1000
> do (compute number)))
>
> If these definitions are in a file that is compiled, then REPEAT
> is known to call this version of COMPUTE, and the NUMBER
> parameter can be passed in a register all the way to ATAN without
> boxing. If COMPUTE decides to push the number to *NUMBERS*, it
> must box it. If different runs of COMPUTE box the same number,
> the objects pushed to *NUMBERS* are most likely not EQ. Now if
> numbers had reliable object identity, then the objects would have
> to be EQ, because they are all the same number that was returned
> from (random 1.0d0) just once. To implement this, I suppose
> either REPEAT should box the number regardless of whether the box
> will actually be needed, or the calling convention should somehow
> let COMPUTE communicate back to REPEAT whether it boxed the
> number and where the box is... this latter scheme seems
> perilously complex to implement.
Or EQ would be implemented like EQL is.
-Peter
* Peter Seibel <··············@gigamonkeys.com> :
| Kalle Olavi Niemitalo <···@iki.fi> writes:
|> Object identity does not imply all equal objects have the same
|> identity.
|
| However, it should imply that objects do not lose their identity. Thus
| if numbers are objects EQ is actually an object identity predicate
| then:
|
| (let ((x 1)) (eq x x))
|
| should be true. But the spec allows it to be false. Which simply means
| that at a user-level numbers are not objects with idenity under EQ.
| But they do have identity under EQL. (See my other recent post in this
| thread for a quote from Kent Pitman about how EQ should really be EQL
| and what we call EQ shouldn't be in the language.)
If you look at common lisp as a language implementor's language, i
don't think that argument is valid. I think Kalle's post is an
argument in support of that.
At the user level it can still matter to me whether (EQ X X) is T or
NIL in a particular implementation in a particular call to that form ,
regardless of the fact that (EQL X X) can be T while (EQ X X) is NIL
--- i.e. regardless of the guarantees cited above from the spec.
|> So you wouldn't have to intern all numbers. Rather, it implies (eq a
|> a), which currently is not guaranteed true for numbers and
|> characters. I suppose requiring this would still prevent some
|> optimizations, though:
|>
|> (defvar *numbers* '())
|>
|> (defun compute (number)
|> (when (zerop (random 100))
|> (push number *numbers*))
|> (atan number))
|>
|> (defun repeat ()
|> (loop with number = (random 1.0d0)
|> repeat 1000
|> do (compute number)))
|>
|> If these definitions are in a file that is compiled, then REPEAT
|> is known to call this version of COMPUTE, and the NUMBER
|> parameter can be passed in a register all the way to ATAN without
|> boxing. If COMPUTE decides to push the number to *NUMBERS*, it
|> must box it. If different runs of COMPUTE box the same number,
|> the objects pushed to *NUMBERS* are most likely not EQ. Now if
|> numbers had reliable object identity, then the objects would have
|> to be EQ, because they are all the same number that was returned
|> from (random 1.0d0) just once. To implement this, I suppose
|> either REPEAT should box the number regardless of whether the box
|> will actually be needed, or the calling convention should somehow
|> let COMPUTE communicate back to REPEAT whether it boxed the
|> number and where the box is... this latter scheme seems
|> perilously complex to implement.
|
| Or EQ would be implemented like EQL is.
I cannot see how to efficiently intern bignums which are not already
interned by an implementation if you exclude EQ. What am I missing?
--
Madhu
Madhu <·······@meer.net> writes:
> * Peter Seibel <··············@gigamonkeys.com> :
> | Kalle Olavi Niemitalo <···@iki.fi> writes:
>
> |> Object identity does not imply all equal objects have the same
> |> identity.
> |
> | However, it should imply that objects do not lose their identity. Thus
> | if numbers are objects EQ is actually an object identity predicate
> | then:
> |
> | (let ((x 1)) (eq x x))
> |
> | should be true. But the spec allows it to be false. Which simply means
> | that at a user-level numbers are not objects with idenity under EQ.
> | But they do have identity under EQL. (See my other recent post in this
> | thread for a quote from Kent Pitman about how EQ should really be EQL
> | and what we call EQ shouldn't be in the language.)
>
> If you look at common lisp as a language implementor's language, i
> don't think that argument is valid. I think Kalle's post is an
> argument in support of that.
I'm not sure how EQ is useful to language implementors working *in*
Common Lisp. And implementors *of* Common Lisp don't need a
spec-mandated function to provide any particular notion of equality or
identity or anything else--they're can use whatever internal functions
they've built into their implementation.
> At the user level it can still matter to me whether (EQ X X) is T or
> NIL in a particular implementation in a particular call to that form ,
> regardless of the fact that (EQL X X) can be T while (EQ X X) is NIL
> --- i.e. regardless of the guarantees cited above from the spec.
I'm not sure I understand how it can matter at the user level, at
least in portable code. The only way EQ has *any* meaning you can rely
on when applied to numbers and characters is by knowing details of the
specific implementation you are running on, i.e. non-portably. But if
you're writing non-portable code, you might as well use a non-portable
SYS:EQ, assuming CL:EQ didn't exist; you'd be no worse off. As it
stands, in portable code, the only possible difference between EQ and
EQL, once the code is running (i.e. leaving aside the issues of
allowing the programmer to convey their intent to other programmers)
is that EQ could be implemented very slightly more efficiently than
EQL since it doesn't have to check the type of its arguments.
> | Or EQ would be implemented like EQL is.
>
> I cannot see how to efficiently intern bignums which are not already
> interned by an implementation if you exclude EQ. What am I missing?
That you don't have to intern bignums to implement EQL--you just
compare their values. Thus given your original example code:
|> (defvar *numbers* '())
|>
|> (defun compute (number)
|> (when (zerop (random 100))
|> (push number *numbers*))
|> (atan number))
|>
|> (defun repeat ()
|> (loop with number = (random 1.0d0)
|> repeat 1000
|> do (compute number)))
Everything works fine, and no optimizations that you mentioned are
disallowed, if EQ happens to be implemented as:
(defun eq (a b) (eql a b))
which would be a conforming implementation.
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
On Fri, 16 Mar 2007 06:56:09 +0100, Peter Seibel <·····@gigamonkeys.com>
wrote:
>
>
> I'm not sure I understand how it can matter at the user level, at
> least in portable code. The only way EQ has *any* meaning you can rely
> on when applied to numbers and characters is by knowing details of the
> specific implementation you are running on, i.e. non-portably. But if
> you're writing non-portable code, you might as well use a non-portable
> SYS:EQ, assuming CL:EQ didn't exist; you'd be no worse off. As it
> stands, in portable code, the only possible difference between EQ and
> EQL, once the code is running (i.e. leaving aside the issues of
> allowing the programmer to convey their intent to other programmers)
> is that EQ could be implemented very slightly more efficiently than
> EQL since it doesn't have to check the type of its arguments.
>
Well in PAIP Norwig uses eq on several instances to improve performance.
I see it's use in finding if two pointers point to the same allocated list.
ie. given
(defparameter *sublis* '(5 6 7))
(defparameter *lis1* (append '(1 2 3 4) *sublis*)
(defparameter *lis2* (append '(1 2 3 4) *sublis*)
(defparameter *lis3* '(1 2 3 4 5 6 7))
Without knowing the declaration of lis* find out which share *sublis*?
(loop for list in (list *lis1* *lis2* *lis3*) collect
(loop for (a . d) on list
when (eq d *sublis*) return t))
returns (t t nil)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
* Peter Seibel <··············@gigamonkeys.com> :
|> If you look at common lisp as a language implementor's language, i
|> don't think that argument is valid. I think Kalle's post is an
|> argument in support of that.
|
| I'm not sure how EQ is useful to language implementors working *in*
| Common Lisp. And implementors *of* Common Lisp don't need a
| spec-mandated function to provide any particular notion of equality or
| identity or anything else--they're can use whatever internal functions
| they've built into their implementation.
As has been noted elsewhere the fundamental reason why a language
implementor *may* use EQ is to provide an efficient language delivered
on top of Common Lisp. I'm not talking of implementating Common Lisp.
| I'm not sure I understand how it can matter at the user level, at
| least in portable code. The only way EQ has *any* meaning you can rely
| on when applied to numbers and characters is by knowing details of the
| specific implementation you are running on, i.e. non-portably. But if
| you're writing non-portable code, you might as well use a non-portable
| SYS:EQ, assuming CL:EQ didn't exist; you'd be no worse off. As it
| stands, in portable code, the only possible difference between EQ and
| EQL, once the code is running
Assuming I'm writing non-portable code, and SYS:EQ didn't exist, I can
still use CL:EQ (after verifying it reasonablyimplements the
hypothetical SYS:EQ) and be no worse off.
(leaving aside the issue of language lawyering and portability
arguments from that viewpoint, I don't see any advantange in your
lobbying for it's removal)
|(i.e. leaving aside the issues of allowing the programmer to convey
|their intent to other programmers) is that EQ could be implemented
|very slightly more efficiently than EQL since it doesn't have to
|check the type of its arguments.
Which is another argument in favour of EQ :)
|> | Or EQ would be implemented like EQL is.
|>
|> I cannot see how to efficiently intern bignums which are not already
|> interned by an implementation if you exclude EQ. What am I missing?
|
| That you don't have to intern bignums to implement EQL--you just
| compare their values.
No, I meant, if an implementation does not intern bignums or big
characters, and my application demands that I intern them to avoid
consing based on some application specific usage pattern. (I'd use the
specific implementation's EQ of course)
--
Madhu
On Mar 16, 10:18 am, Madhu <·······@meer.net> wrote:
> As has been noted elsewhere the fundamental reason why a language
> implementor *may* use EQ is to provide an efficient language delivered
> on top of Common Lisp. I'm not talking of implementating Common Lisp.
Again: let's see a real example were there is a meaningful performance
difference.
"Tim Bradshaw" <··········@tfeb.org> writes:
> On Mar 16, 10:18 am, Madhu <·······@meer.net> wrote:
>
>> As has been noted elsewhere the fundamental reason why a language
>> implementor *may* use EQ is to provide an efficient language delivered
>> on top of Common Lisp. I'm not talking of implementating Common Lisp.
>
> Again: let's see a real example were there is a meaningful performance
> difference.
> (time (dotimes (j 100)
(dotimes (n 100000000)
(if (eq n ff)
(incf ff)))))
Evaluation took:
23.9 seconds of real time
22.82653 seconds of user run time
0.072989 seconds of system run time
0 calls to %EVAL
0 page faults and
70,184 bytes consed.
nil
> (time (dotimes (j 100)
(dotimes (n 100000000)
(if (eql n ff)
(incf ff)))))
Evaluation took:
23.557 seconds of real time
22.876522 seconds of user run time
0.021997 seconds of system run time
0 calls to %EVAL
0 page faults and
66,784 bytes consed.
nil
>
I've played around with the parameters a bit, and on SBCL it does appear
that EQL is .2% longer. I doubt that this is particularly worrisome, as
two-thousandths longer run time means that a month-long data simulation
would run an additional 40 minutes--hardly something to worry over-long
about.
--
Robert Uhl <http://public.xdi.org/=ruhl>
When you disarm your subjects you offend them by showing that either
from cowardliness or lack of faith, you distrust them; and either
conclusion will induce them to hate you.
--Niccolo Machiavelli, The Prince
On Mar 19, 4:03 pm, Robert Uhl <·········@NOSPAMgmail.com> wrote:
> "Tim Bradshaw" <··········@tfeb.org> writes:
>
> I've played around with the parameters a bit, and on SBCL it does appear
> that EQL is .2% longer. I doubt that this is particularly worrisome, as
> two-thousandths longer run time means that a month-long data simulation
> would run an additional 40 minutes--hardly something to worry over-long
> about.
That's a month-long simulation that spends its time entirely in an
inner loop with no non-cached (and probably no non-register)
references.
And, of course, the faster version is using EQ to compare numbers, so
probably doesn't wrk. That does seem to be a tradeoff many people are
willing to make, of course.
Do I need the :-)?
--tim
On 19 Mar 2007 10:07:33 -0700, "Tim Bradshaw" <··········@tfeb.org> said:
| ...
| And, of course, the faster version is using EQ to compare numbers, so
| probably doesn't work.
Let's see. (Of course, we could only argue if it worked or not if
we had said in advance what it was supposed to do, but we are just
fooling around now.)
Here is another variation on the same theme:
* (defconstant fixmany (* 5 (expt 10 8)))
FIXMANY
* (typep fixmany 'fixnum)
T
* (compile
(defun n-eq-calls (n)
(let ((ff 0))
(dotimes (i n ff)
(when (eq i ff) (incf ff))))))
N-EQ-CALLS
NIL
NIL
* (compile
(defun n-eql-calls (n)
(let ((ff 0))
(dotimes (i n ff)
(when (eql i ff) (incf ff))))))
N-EQL-CALLS
NIL
NIL
* (time (n-eq-calls fixmany))
Evaluation took:
6.357 seconds of real time
6.36 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
500000000
* (time (n-eql-calls fixmany))
Evaluation took:
7.624 seconds of real time
7.63 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
500000000
And still,
* (/ 7.63 6.36)
1.1996856
is about 20% longer...
Again: there's lies, damn lies, and benchmarking. By all means
Gabriel's book is required reading on this matter, it is very
instructive.
---Vassil.
--
The truly good code is the obviously correct code.
On Mon, 19 Mar 2007 10:03:41 -0600, Robert Uhl <·········@NOSPAMgmail.com> said:
|| (time (dotimes (j 100)
| (dotimes (n 100000000)
| (if (eq n ff)
| (incf ff)))))
| Evaluation took:
| 23.9 seconds of real time
| 22.82653 seconds of user run time
| 0.072989 seconds of system run time
| 0 calls to %EVAL
| 0 page faults and
| 70,184 bytes consed.
| nil
|| (time (dotimes (j 100)
| (dotimes (n 100000000)
| (if (eql n ff)
| (incf ff)))))
| Evaluation took:
| 23.557 seconds of real time
| 22.876522 seconds of user run time
| 0.021997 seconds of system run time
| 0 calls to %EVAL
| 0 page faults and
| 66,784 bytes consed.
| nil
||
| I've played around with the parameters a bit, and on SBCL it does appear
| that EQL is .2% longer. I doubt that this is particularly worrisome, as
| two-thousandths longer run time means that a month-long data simulation
| would run an additional 40 minutes--hardly something to worry over-long
| about.
There is this minor detail, however, that
* (typep 100000000 'fixnum)
T
So let's try something else. (NB: we are just fooling around here.
But, there is an excellent book by Gabriel which is quite relevant
to this matter, _Performance and Evaluation of Lisp Systems_; a must
to read.) That said:
* (defconstant many (expt 10 9))
MANY
* (typep many 'fixnum)
NIL
* (compile
(defun n-eq-calls (n)
(let ((ff 0))
(dotimes (i n)
(when (eq i ff) (incf ff))))))
N-EQ-CALLS
NIL
NIL
* (compile
(defun n-eql-calls (n)
(let ((ff 0))
(dotimes (i n)
(when (eql i ff) (incf ff))))))
N-EQL-CALLS
NIL
NIL
* (time (n-eq-calls many))
Evaluation took:
58.887 seconds of real time
58.2 seconds of user run time
0.22 seconds of system run time
[Run times include 1.72 seconds GC run time.]
0 calls to %EVAL
30 page faults and
11,115,125,296 bytes consed.
NIL
* (time (n-eql-calls many))
Evaluation took:
109.049 seconds of real time
108.33 seconds of user run time
0.45 seconds of system run time
[Run times include 3.91 seconds GC run time.]
0 calls to %EVAL
0 page faults and
22,230,269,432 bytes consed.
NIL
That's about 90% longer. Some other interesting numbers in TIME's
output, too. And 10^9 isn't really "many", is it...
Explaining what difference it makes if N in the body of each
function is replaced with a literal 1000000000 is left as an
exercise for the reader.
---Vassil.
--
The truly good code is the obviously correct code.
* Peter Seibel <··············@gigamonkeys.com> :
|> If you look at common lisp as a language implementor's language, i
|> don't think that argument is valid. I think Kalle's post is an
|> argument in support of that.
|
| I'm not sure how EQ is useful to language implementors working *in*
| Common Lisp. And implementors *of* Common Lisp don't need a
| spec-mandated function to provide any particular notion of equality or
| identity or anything else--they're can use whatever internal functions
| they've built into their implementation.
As has been noted elsewhere the fundamental reason why a language
implementor *may* use EQ is to provide an efficient language delivered
on top of Common Lisp. I'm not talking of implementating Common Lisp.
| I'm not sure I understand how it can matter at the user level, at
| least in portable code. The only way EQ has *any* meaning you can rely
| on when applied to numbers and characters is by knowing details of the
| specific implementation you are running on, i.e. non-portably. But if
| you're writing non-portable code, you might as well use a non-portable
| SYS:EQ, assuming CL:EQ didn't exist; you'd be no worse off. As it
| stands, in portable code, the only possible difference between EQ and
| EQL, once the code is running
Assuming I'm writing non-portable code, and SYS:EQ didn't exist, I can
still use CL:EQ (after verifying it reasonablyimplements the
hypothetical SYS:EQ) and be no worse off.
(leaving aside the issue of language lawyering and portability
arguments from that viewpoint, I don't see any advantange in your
lobbying for its removal)
|(i.e. leaving aside the issues of allowing the programmer to convey
|their intent to other programmers) is that EQ could be implemented
|very slightly more efficiently than EQL since it doesn't have to
|check the type of its arguments.
Which is another argument in favour of EQ :)
|> | Or EQ would be implemented like EQL is.
|>
|> I cannot see how to efficiently intern bignums which are not already
|> interned by an implementation if you exclude EQ. What am I missing?
|
| That you don't have to intern bignums to implement EQL--you just
| compare their values.
No, I meant, if an implementation does not intern bignums or big
characters, and my application demands that I intern them to avoid
consing based on some application specific usage pattern. (I'd use the
specific implementation's EQ of course)
--
Madhu
On Fri, 16 Mar 2007 05:56:09 GMT, Peter Seibel <·····@gigamonkeys.com> said:
| ...
| I'm not sure I understand how it can matter at the user level, at
| least in portable code. The only way EQ has *any* meaning you can rely
| on when applied to numbers and characters is by knowing details of the
| specific implementation you are running on, i.e. non-portably.
Why? It has a fully portable meaning, just not the meaning we may
have been used to.
In fact, _all_ values in Common Lisp do have proper object identity
under EQ, portably; it is just that for some specified types, all of
which are immutable (namely, numbers and characters), the
implementation is allowed to _make copies_ of objects at any time
without notice [1]. That is, EQ is actually not broken for any type,
even though we may refer to a "breakdown", for which our own
assumptions are (at least partly) to blame. The reason for seeing
breakage here is probably interference from our intuition about
numbers as mathematical object (a very different kind of beasts). I
am merely repeating what has already been written, of course:
(EQ _X_ _Y_) is true if and only if _X_ and _Y_ are the same
identical object. (Implementationally, _X_ and _Y_ are usually EQ if
and only if they address the same identical memory location.)
...
In Common Lisp ... the implementation is permitted to make "copies"
of characters and numbers at any time. [2]
Thus EQL tells whether two objects are _conceptually_ the same,
whereas _EQ_ tells whether two objects are _implementationally_
identical. [3]
(Note "usually" and also the choice of words, "same" and "identical".)
We also have an interesting note in the chapter on numbers (and a
similar one in the chapter on characters):
Rationale: This odd breakdown of EQ in the case of numbers allows the
implementor enough design freedom to produce exceptionally efficient
numerical code on conventional architectures. MacLisp requires this
freedom, for example, in order to produce compiled numerical code
equal in speed to FORTRAN. Common Lisp makes this same restriction,
if not for this freedom, then at least for the sake of
compatibility. [4]
(Note the last clause...)
[1] including the time between evaluating an argument and applying a
function to the value thus obtained
[2] _Common Lisp: the Language_, section 6.3; p. 77
[3] Ibid., p. 78
[4] Ibid., chapter 12; p. 193
| ...
| EQ could be implemented very slightly more efficiently than
| EQL since it doesn't have to check the type of its arguments.
In the general case, the difference is as that between O(1) and
O(n), which is not "very slightly"...
| ...
| Everything works fine, and no optimizations that you mentioned are
| disallowed, if EQ happens to be implemented as:
| (defun eq (a b) (eql a b))
| which would be a conforming implementation.
It would be against the spirit of the language, even if it conforms
to the letter of its specification!
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
Vassil Nikolov <···············@pobox.com> writes:
> On Fri, 16 Mar 2007 05:56:09 GMT, Peter Seibel <·····@gigamonkeys.com> said:
> | EQ could be implemented very slightly more efficiently than EQL
> | since it doesn't have to check the type of its arguments.
>
> In the general case, the difference is as that between O(1) and
> O(n), which is not "very slightly"...
Mmmm, I don't think so. Consider:
- Imagine a program where you currenly use EQ in various places. If
you value your sanity, EQ had better not ever be called upon to
test the EQness of numbers or characters because it can return
either true or false in some cases. (If your program works
correctly in either case and you really care about efficiency you
might as well just hard code it to be NIL--it will always be
correct when they are different objects and you might have gotten
it even when they were the same object but got copied at the last
minute under the covers, i.e. in the (eq x x) case.) Thus we can
assume that you happen to know that at those sites the values
passed to EQ are never going to be numbers or characters.
- Now, replace all calls to EQ with EQL. At those same sites, because
nothing else has changed, EQL will never be called with numbers or
characters. The extra cost born by EQL is paid whenever it compares
to non-EQ objects. In that case, after determining that they are
not EQ it has to check whether they might be numbers or characters
of the same type. Which we know, by the above, they are not. So in
the worst case, as Tim Bradshaw pointed out, this means a bit of
extra traffic to main memory to fetch type information so that it
can then safely declare them non-EQL. Now this extra traffic to
memory may or may not be sufficiently bad to care about but it's
still O(1).
Obviously in cases where you *do* want to compare numbers or
characters then the EQL test can be O(n) in the size of the
representation of the values but that's the price you pay for actually
wanting to compare those types.
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
On Sat, 17 Mar 2007 05:16:18 +0100, Peter Seibel <·····@gigamonkeys.com>
wrote:
>
> - Imagine a program where you currenly use EQ in various places. If
> you value your sanity, EQ had better not ever be called upon to
> test the EQness of numbers or characters because it can return
> either true or false in some cases. (If your program works
> correctly in either case and you really care about efficiency you
> might as well just hard code it to be NIL--it will always be
> correct when they are different objects and you might have gotten
> it even when they were the same object but got copied at the last
> minute under the covers, i.e. in the (eq x x) case.) Thus we can
> assume that you happen to know that at those sites the values
> passed to EQ are never going to be numbers or characters.
>
But.. Why?
If you are maintaining a graph you know that the input to eq are nodes.
ALWAYS.
Why use char= or = when you can use eql? (For that matter string= instead
of equal.)
Same as you put a check-type in a function.
Not everything is generic. If it is generic then there are operations
that can handle that.
The only issue I see is that the standard claims it is object identity.
As has been throughly demonstrated this is not true.
So you change the specification but keep the function.
* Define eql to be object identity.
* eq now means addr=.
Computationally eq makes perfect sense, just not mathematically.
I guess my C++ past shines through.. I don't see any point in making this
more inefficient just to satisfy a mathematical ideal. In fact isn't that
what separates Common Lisp from Scheme? CL is full of such compromises
where
simplicity and well-defined'ness (ugh!) take a back seat to efficiency.
If you want non-compromising adherence to the underlying mathematical
abstraction
you will love Haskel. But it is difficult to get things efficient there.
What I like about lisp is that gets the amount of abstraction about right.
It is generic and high level, but it also allows for low level hacking
when required.
All apps I have come across have required this at some point. CFFI is a
(extreme) example.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On 2007-03-17 09:21:57 +0000, "John Thingstad" <··············@chello.no> said:
> I guess my C++ past shines through.. I don't see any point in making thi s
> more inefficient just to satisfy a mathematical ideal.
I think that's exactly the issue. C/C++ people spend a huge amount of
time futilely optimising things which (a) don't need to be optimised
and (b) it turns out that the optimisation, while an improvement on a
PDP11, actually isn't any more.
On Sat, 17 Mar 2007 19:06:12 +0100, Tim Bradshaw <···@tfeb.org> wrote:
> On 2007-03-17 09:21:57 +0000, "John Thingstad"
> <··············@chello.no> said:
>
>> I guess my C++ past shines through.. I don't see any point in making
>> thi s
>> more inefficient just to satisfy a mathematical ideal.
>
> I think that's exactly the issue. C/C++ people spend a huge amount of
> time futilely optimising things which (a) don't need to be optimised and
> (b) it turns out that the optimisation, while an improvement on a PDP11,
> actually isn't any more.
>
>
And Lispers waste endless amount of time debating non-issues.
eq in it's current form is here to stay.
If you don't like it just forget it ever existed and use eql.
As you have already said it will work everywhere eq would.
Lisp is about choice. You work in the style you are comfortable with.
Referring to the place something is stored as opposed to what it's
value is with just isn't a big issue with me. I'd go so far as to
say eq is more concise. It says I am working with composite structures.
Perhaps it should just signal a (continuable) error it encounters a atom?
That wouldn't inflict on how I use it.
(declaim (inline composite-p)) ; dumb C++ habbit
(defun composite-p (elt)
(not (atomp elt)))
(deftype composite `(satisfies composite-p))
(defun my-eq (ref1 ref2)
(check-type ref1 composite)
(check-type ref2 composite)
(eq ref1 ref2))
(untested)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On 2007-03-17 19:11:03 +0000, "John Thingstad" <··············@chello.no> said:
> And Lispers waste endless amount of time debating non-issues.
> eq in it's current form is here to stay.
> If you don't like it just forget it ever existed and use eql.
> As you have already said it will work everywhere eq would.
I think you mistake me for someone else: I have no interest in removing
EQ from the language. I'm not sure why you think I do: perhaps you
misunderstood the Gedankenexperiment I proposed to Kenny to persuade
him that, in fact, numbers do have identity in CL, just not under EQ,
for a serious suggestion. If so you can't have read it very carefully,
since I ended up reintroducing EQ, albeit two levels of toy universe
down (fortunately many implementations can optimize tail-universes
away).
Of course what I was actually writing about in the article to which you
responded was the spurious concern of many programmers with
"efficiency", almost always based on a nearly complete lack of
understanding of what the performance characteristics of modern[*]
machines and the codes they run actually are, in even the broadest
terms. You may think that's a non-issue: you would be wrong.
--tim
[*] Say anything designed int he last 25 years, and many things
designed before that.
On Fri, 16 Mar 2007 21:16:18 -0700, Peter Seibel <·····@gigamonkeys.com> said:
| Vassil Nikolov <···············@pobox.com> writes:
|| On Fri, 16 Mar 2007 05:56:09 GMT, Peter Seibel <·····@gigamonkeys.com> said:
[A:]
|| | EQ could be implemented very slightly more efficiently than EQL
|| | since it doesn't have to check the type of its arguments.
||
|| In the general case, the difference is as that between O(1) and
|| O(n), which is not "very slightly"...
| Mmmm, I don't think so. Consider:
[B:]
| - Imagine a program where you currenly use EQ in various places. If
| you value your sanity, EQ had better not ever be called upon to
| test the EQness of numbers or characters because it can return
| either true or false in some cases. (If your program works
| correctly in either case and you really care about efficiency you
| might as well just hard code it to be NIL
1. Not if the types of the arguments are only known at run-time...
(Not to mention that this is rather excessive, especially with
regards to what typical implementations actually do. If it will be
NIL, at least I want to hear this from the implementation, not to
pre-empt its answer.)
| --it will always be
| correct when they are different objects and you might have gotten
| it even when they were the same object but got copied at the last
| minute under the covers, i.e. in the (eq x x) case.) Thus we can
| assume that you happen to know that at those sites the values
| passed to EQ are never going to be numbers or characters.
| - Now, replace all calls to EQ with EQL. At those same sites, because
| nothing else has changed, EQL will never be called with numbers or
| characters. The extra cost born by EQL is paid whenever it compares
| to non-EQ objects. In that case, after determining that they are
| not EQ it has to check whether they might be numbers or characters
| of the same type. Which we know, by the above, they are not.
2. Are we comparing the efficiency of EQ to the efficiency of EQL
(as in [A] above) or the efficiency of a program using EQ to the
efficiency of one using EQL (as in [B] above)? Both comparisons
are interesting, but they are not quite the same comparison...
3. I think that there are cases where using EQ makes sense. Finding
a more involved example needs more time than I have, but I hope this
simple one may also help. Take this (non-original) way of writing a
function which tabulates its most recent argument and value (if we
want more such pairs tabulated, we might e.g. hash on EQ):
(flet ((workhorse (x) ...)) ;no side effects!
(let ((last-arg nil)
(last-val (workhorse nil)))
(defun foo (x)
(unless (eq x last-arg)
(setf last-val (workhorse x))
(setf last-arg x)) ;assume no abnormal termination from here
last-val)))
This works correctly whether or not an implementation arbitrarily
copies numbers (and characters). Besides, we'll hardly want to test
the types before calling EQ, and return NIL for numbers or
characters here. Then, consider a second variant in which the only
change is of EQ to EQL. The relative speed of each depends on two
factors: (1) the implementation, and (2) the distribution of values
for the argument. In general, for some combinations of (1) and (2),
the EQ variant will be faster; for others, the EQL variant, but
neither variant will be a clear winner if all cases are considered.
(For example, one case in which the EQ variant will win is a typical
implementation and a lot of bignum arguments. Another case where
they might be about equal is a distribution in which the same (EQL
but not EQ) bignum is often supplied for consecutive calls, but the
workhorse function is very fast.)
| So in
| the worst case, as Tim Bradshaw pointed out, this means a bit of
| extra traffic to main memory to fetch type information so that it
| can then safely declare them non-EQL. Now this extra traffic to
| memory may or may not be sufficiently bad to care about but it's
| still O(1).
4. The O(n) I was referring to is, of course, about bignums
(including bignum rationals and unlimited-precision floating point
numbers), where n is (roughly) the number of bits in the value,
i.e. the size.
---Vassil.
--
The truly good code is the obviously correct code.
Vassil Nikolov <···············@pobox.com> writes:
> On Fri, 16 Mar 2007 21:16:18 -0700, Peter Seibel <·····@gigamonkeys.com> said:
> | So in the worst case, as Tim Bradshaw pointed out, this means a
> | bit of extra traffic to main memory to fetch type information so
> | that it can then safely declare them non-EQL. Now this extra
> | traffic to memory may or may not be sufficiently bad to care about
> | but it's still O(1).
>
> 4. The O(n) I was referring to is, of course, about bignums
> (including bignum rationals and unlimited-precision floating point
> numbers), where n is (roughly) the number of bits in the value,
> i.e. the size.
Okay, so I'll slightly revise my position vis a vis EQ. There are, I
think, two places one can legitimately use EQ. The first I've always
acknowledged though I prefer to to use EQL even there. They are:
1. When you know that the objects that will be compared will never
in fact be numbers or characters. A simple examples is using an EQ
hashtable when you know the keys are all going to be symbols. The
advantage, such as it is, of using EQ in this case, is that in the
case where two objects are not EQ, it doesn't waste any time,
compared to EQL, checking their types to see if it needs to do any
more work. In this case the extra work is still O(1) because it will
never actually end up doing a bignum comparison because we know, a
priori, that we're only comparing non-number, non-character objects.
2. When you may be comparing numbers or characters but can live with
the consequences of two EQL numbers being considered non-EQ. Your
memoization example is a good example of this kind of usage. When EQ
returns NIL for objects for which EQL would return T you just end up
calling WORKHORSE in a case where you didn't really need to.
In the second case EQL might do O(n) work to determine that two
bignums are EQL where EQ would determine that they are not EQ in O(1).
I suspect I'd still use EQL in this case--if the cost of WORKHORSE is
worth memoizing in the first place it's probably worth the cost of
actually comparing two bignums properly to avoid calling it
needlessly. Of course in actual practice, only profiling can tell us
which is the right choice.
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
On 2007-03-20 17:54:22 +0000, Peter Seibel <·····@gigamonkeys.com> said:
> In the second case EQL might do O(n) work to determine that two
> bignums are EQL where EQ would determine that they are not EQ in O(1).
Again, this is a terribly misleading statement. That n is the number
of bits in the bignum. *Addition* of bignums is O(n) in that n, and in
fact the mere creation of them is as well. In fact: almost any
arithmetically useful operation on them is at least O(n) in that n
(exceptions might be computing sign & a few other things).
On Wed, 21 Mar 2007 10:16:02 +0000, Tim Bradshaw <···@tfeb.org> said:
| ...
| *Addition* of bignums is O(n) in that n, and
| in fact the mere creation of them is as well. In fact: almost any
| arithmetically useful operation on them is at least O(n) in that n
| (exceptions might be computing sign & a few other things).
(Such as INTEGER-LENGTH, perhaps.)
Right.
Now, a similar statement can be made about lists (most of the
interesting operations on them are at least O(n) in the length of
the list(s)). However, unlike bignums, EQL "doesn't do lists", and
it is a moderately interesting question why:
(a) because lists are mutable;
(b) because lists can share structure (with all implications thereof);
(c) because lists do not have the same status as mathematical
objects like numbers do;
(d) for historical reasons;
(e) all of the above;
(f) none of the above.
(Answers and discussions are not provided in order to reward the
proverbial industrious reader...)
---Vassil.
--
The truly good code is the obviously correct code.
On 2007-03-22 03:20:45 +0000, Vassil Nikolov <···············@pobox.com> said:
> Now, a similar statement can be made about lists (most of the
> interesting operations on them are at least O(n) in the length of
> the list(s)).
However long lists are much more common than very large bignums. For
instance it takes time proportional to n to make a list of length n,
but it takes exponentially longer to count to a bignum of length n.
> However, unlike bignums, EQL "doesn't do lists", and
> it is a moderately interesting question why:
>
> (a) because lists are mutable;
> (b) because lists can share structure (with all implications thereof);
> (c) because lists do not have the same status as mathematical
> objects like numbers do;
> (d) for historical reasons;
> (e) all of the above;
> (f) none of the above.
Or, in fact, because EQL is meant to compare object identity in a
useful way, which is where we came in.
On Thu, 22 Mar 2007 09:34:18 +0000, Tim Bradshaw <···@tfeb.org> said:
| On 2007-03-22 03:20:45 +0000, Vassil Nikolov <···············@pobox.com> said:
| ...
|| However, unlike bignums, EQL "doesn't do lists", and
|| it is a moderately interesting question why:
|| (a) because lists are mutable;
|| (b) because lists can share structure (with all implications thereof);
|| (c) because lists do not have the same status as mathematical
|| objects like numbers do;
|| (d) for historical reasons;
|| (e) all of the above;
|| (f) none of the above.
| Or, in fact, because EQL is meant to compare object identity in a
| useful way, which is where we came in.
I think we are quite in agreement here; the purpose of my little
multiple-choice exercise (for the group at large) is to say
specifically what makes EQL's comparison useful the way it is
defined, and why. (The answer is in fact contained in this
thread...)
---Vassil.
--
The truly good code is the obviously correct code.
Tim Bradshaw <···@tfeb.org> writes:
> On 2007-03-20 17:54:22 +0000, Peter Seibel <·····@gigamonkeys.com> said:
>
>> In the second case EQL might do O(n) work to determine that two
>> bignums are EQL where EQ would determine that they are not EQ in
>> O(1).
>
> Again, this is a terribly misleading statement. That n is the number
> of bits in the bignum. *Addition* of bignums is O(n) in that n, and
> in fact the mere creation of them is as well. In fact: almost any
> arithmetically useful operation on them is at least O(n) in that n
> (exceptions might be computing sign & a few other things).
Yes. I didn't mean to be misleading--I assumed anyone still following
this discussion knew what the N was counting. (Are you worried that
people thought N was the value of the bignum? Or just some generalized
N that made O(n) sound terribly awful?) But it is true--is it
not--that comparing two bignums is more or less O(n) in the number of
bits (or maybe in the number of bigits which comes out to the same
thing for large enough N)?
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
On Thu, 22 Mar 2007 03:19:39 GMT, Peter Seibel <·····@gigamonkeys.com> said:
| ...
| (Are you worried that
| people thought N was the value of the bignum? Or just some generalized
| N that made O(n) sound terribly awful?)
Most often, the "n" in "O(n)", in the context of algorithms, refers
to the _value_ of some natural number, which is a parameter of the
problem, rather than to the "size" of that number, so there is
(some) risk of confusion.
(On the other hand, and as a rule of thumb only, O(n) per se is
rather tame (of course, O(log n) is better, not to mention O(1)),
and even O(n log n) is not awful yet, while O(n^2) is a cause for
alarm, polynomial of a higher degree is a cause for serious alarm,
and exponential is a disaster.)
| ...
| comparing two bignums is more or less O(n) in the number of
| bits (or maybe in the number of bigits which comes out to the same
| thing for large enough N)?
Pedantically speaking, the last four words are redundant, since that
is already included in the definition of the big-oh notation.
---Vassil.
--
The truly good code is the obviously correct code.
On Mar 22, 4:19 am, Peter Seibel <····@gigamonkeys.com> wrote:
> Tim Bradshaw <····@tfeb.org> writes:
> > On 2007-03-20 17:54:22 +0000, Peter Seibel <····@gigamonkeys.com> said:
>
> >> In the second case EQL might do O(n) work to determine that two
> >> bignums are EQL where EQ would determine that they are not EQ in
> >> O(1).
>
> > Again, this is a terribly misleading statement. That n is the number
> > of bits in the bignum. *Addition* of bignums is O(n) in that n, and
> > in fact the mere creation of them is as well. In fact: almost any
> > arithmetically useful operation on them is at least O(n) in that n
> > (exceptions might be computing sign & a few other things).
>
> Yes. I didn't mean to be misleading--I assumed anyone still following
> this discussion knew what the N was counting. (Are you worried that
> people thought N was the value of the bignum? Or just some generalized
> N that made O(n) sound terribly awful?) But it is true--is it
> not--that comparing two bignums is more or less O(n) in the number of
> bits (or maybe in the number of bigits which comes out to the same
> thing for large enough N)?
True, EQL on bignums is O(n), but with modern vector units n should be
something like the number of 128-bit words. So on a G4, the sequence
to successfully compare two = but not EQ bignums could go something
like: compare the pointers, check for bignum tagbits in the pointers,
load the lengths, compare them, start the quadword comparison loop.
So you're talking a dozen instructions of constant overhead, plus a
sequence of about five instructions (load, permute, load, permute,
compare) for each quadword in the bignum's content, plus a few
instructions to setup the misaligned access. Unless the bignums are
really really really big, this is going to be massively dominated by
the load from memory. If an implementor were really concerned about
that, they could soft-intern bignums beyond a certain length. That
would be in the noise compared to the creation of such bignums.
On 2007-03-22 03:19:39 +0000, Peter Seibel <·····@gigamonkeys.com> said:
> Yes. I didn't mean to be misleading--I assumed anyone still following
> this discussion knew what the N was counting. (Are you worried that
> people thought N was the value of the bignum? Or just some generalized
> N that made O(n) sound terribly awful?)
Yeah, basically, I'm worrying that people will see O(n) and make all
sorts of wrong assumptions about EQL
On 2007-03-17 03:07:06 +0000, Vassil Nikolov <···············@pobox.com> said:
> In the general case, the difference is as that between O(1) and
> O(n), which is not "very slightly"...
But that n is the *log* of the magnitude of the numbers involved. And,
importantly, EQ does not actually work in that case.
On Sat, 17 Mar 2007 18:04:27 +0000, Tim Bradshaw <···@tfeb.org> said:
| On 2007-03-17 03:07:06 +0000, Vassil Nikolov <···············@pobox.com> said:
|| In the general case, the difference is as that between O(1) and
|| O(n), which is not "very slightly"...
| But that n is the *log* of the magnitude of the numbers involved.
Yes---the size of the data (roughly, the number of digits of these
numbers), as usual. (I hope I didn't say anywhere that n in O(n) is
a number being compared.)
| And, importantly, EQ does not actually work in that case.
Well, it works---according to its mandate, i.e. to compare two
objects implementationally, not two numbers mathematically (except
that this kind of objects being a model of a kind of immutable
mathematical objects, we have licensed the implementation to also
make copies of those at will and without notice, and then the scope
of the license is much wider than the way it is typically taken
advantage of in actuality...).
I think our "number intuition", based on mathematical knowledge and
training, very heavily interferes with out "computer thinking" here,
and a result our expectations are "torn apart". Well, maybe not, of
course, but there seems to be some underlying cognitive phenomenon
at play here that is causing more trouble than usual.
Maybe one is coming to a point where one would say about EQ that it
is important to know that it is there even if one doesn't call it,
like Sir Humphrey Appleby about going to art galleries...
---Vassil.
--
The truly good code is the obviously correct code.
On 2007-03-20 11:13:52 +0000, Vassil Nikolov <···············@pobox.com> said:
> Yes---the size of the data (roughly, the number of digits of these
> numbers), as usual. (I hope I didn't say anywhere that n in O(n) is
> a number being compared.)
I don't think you did. However it's difficult to think of a program
where EQL vs EQ could make a difference between O(1) and O(n)
performance, and it's even harder to think of a program which would use
the difference to do anything but tell you about the implementation.
--tim
Tim Bradshaw <···@tfeb.org> writes:
> On 2007-03-20 11:13:52 +0000, Vassil Nikolov <···············@pobox.com> said:
>
>> Yes---the size of the data (roughly, the number of digits of these
>> numbers), as usual. (I hope I didn't say anywhere that n in O(n) is
>> a number being compared.)
>
> I don't think you did. However it's difficult to think of a program
> where EQL vs EQ could make a difference between O(1) and O(n)
> performance, and it's even harder to think of a program which would
> use the difference to do anything but tell you about the
> implementation.
Well, if you had EQ O(1) and EQL O(n), that'd mean there's a flaw in the implementation.
One expects: (defun eql (a b) (or (eq a b) (do-some-lengthy-O\(n\)-comparizon a b)))
If you lack the (or (eq a b) part, you've got a bug...
--
__Pascal Bourguignon__
http://www.informatimago.com
http://pjb.ogamita.org
On 14 Mar 2007 05:17:06 -0700, "Tim Bradshaw" <··········@tfeb.org> said:
| ...
| Just to clarify what someone else said: numbers *are* objects in CL,
| they are just immutable objects. To achieve what you want you need to
| put the number inside some object which is mutable (a cons would be an
| easy choice:
| (let ((x (cons 1 nil)))
| (cons x x))
| (setf (car (car ...)) 2)
| Of course the ideologically sound way to do this would be to have some
| explicit box type rather than just using a cons.)
My personal favorite for the purpose is a zero-dimensional array, as
this strongly emphasizes that we have a single value (a structure
could (be modified to) have more fields).
No, I am not claiming that it is reasonable to expect that a typical
implementation will represent that as efficiently as "half a cons",
but at least at source level everything is nice since the element type
can be supplied and possibly declared as well.
| Contrast this to Java where numbers are *not* objects, but there are
| classes like Integer whose sole purpose is to box integers. I think
| that these classes are in fact themselves immutable in Java - at least
| there are no methods to set the value being boxed. Recent Java (5)
Immutable, yes. Now, if they were internable as well...
| specifications provide for a lot of automatic boxing and unboxing of
| numbers which obfuscates this distinction somewhat.
(And then people point out that the equally recent format facility
is slow...)
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
Szabolcs Szucs wrote:
> This is about objects. But with numbers (how can I pack a number as an
> object?):
I've never heard of invisible references in CL. You can make a cons
as Alex said, or you could define your own struct with one slot:
(defstruct ref val)
and use the slot accessor (REF-VAL in this case) to access your number.
--
Dan
www.prairienet.org/~dsb
On Wed, 14 Mar 2007 11:04:10 +0100, Szabolcs Szucs wrote:
> Hi,
>
> ······@gmail.com writes:
>
>>> How can I create a cons which points with its car and cdr to the
>>> same object? Therefore if I change the car the cdr will change too..
>> You can do it by, well, doing it:
>>
>> CL-USER> (defparameter initial-value (list 1 2 3))
>> INITIAL-VALUE
>> CL-USER> (defparameter mycons (cons initial-value initial-value))
>> MYCONS
>> CL-USER> mycons
>> ((1 2 3) 1 2 3)
>> CL-USER> (setf (car (car mycons)) 42)
>> 42
>> CL-USER> mycons
>> ((42 2 3) 42 2 3)
>> CL-USER>
>>
>>
>> This is what you asked for, although there's a chance this is not what
>> you wanted.
>>
>
> This is about objects. But with numbers (how can I pack a number as an
> object?):
>
> [1]> (defparameter i 1)
> I
> [2]> i
> 1
> [3]> (defparameter k (cons i i))
> K
> [4]> k
> (1 . 1)
> [5]> (setf i 3)
> 3
> [6]> k
> (1 . 1)
>
Maybe:
(defun mkptr-to (value)
"Make a \"pointer\" to `value'."
(list value))
(defun value-of (ptr-to-value)
"Dereference `ptr-to-value'."
(first ptr-to-value))
(defun (setf value-of) (new-value ptr-to-value)
(setf (first ptr-to-value) new-value))
(let* ((number (mkptr-to 1))
(list-of-values (list number number)))
(setf (value-of number) 2)
(loop :for ptr-to-value :in list-of-values
:collect (value-of ptr-to-value)))
=> (2 2)
--
Lars Rune Nøstdal
http://nostdal.org/
(message (Hello 'Szabolcs)
(you :wrote :on '(Wed, 14 Mar 2007 11:04:10 +0100))
(
SS> This is about objects. But with numbers (how can I pack a number as an
SS> object?):
numbers are immutable in Common Lisp. that won't work.
the only way to do this is to wrap number into some mutable object.
simpliest mutable object is CONS.
so you can make (cons 1 nil), that is same as (list 1), and use that mutable
object --
CL-USER> (defparameter mc (let ((c (cons 1 nil)))
(cons c c))
)
MC
CL-USER> (setf (car (car mc)) 2)
2
CL-USER> mc
((2) 2)
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"?? ???? ??????? ?????")
On Mar 14, 1:11 am, Szabolcs Szucs <····@elte.hu> wrote:
> Hi,
>
> How can I create a cons which points with its car and cdr to the
> same object? Therefore if I change the car the cdr will change too..
What you are asking for doesn't make any sense whatsoever.
Firstly, CAR and CDR do not point. Loosely speaking, we understand
these to be /names/ of two distinct memory locations within a cons
cell object. These two places hold values.
When we ``change the CDR'', we overwrite the previous value in the CDR
place with a new value. This has absolutely no effect on the CAR,
which is a different memory location. It also has no effect on any
other copy of the object which was previously stored in the CDR.
When you define a cons using the expression
(cons i i)
that does not establish any relationship between the resulting cell,
and the memory location denoted by I. The expression I is evaluated by
pulling out a copy of the contents of the denoted memory location.
Then this value is passed as both arguments of the CONS function,
causing it to be separately stored into the CAR and CDR of the newly
constructed cell.
So in the end, there are three distinct memory locations: the CAR, the
CDR and the variable I. Changing one of them has absolutely no effect
on the other two. The CAR and CDR are only associated to the extent
that they are located in the same object. Otherwise, all three are
completely distinct and independent.
Clearly, this hack you are thinking of is part of some larger problem
that you are trying to solve. The solution you are thinking of, to
that larger problem, has led you to a sub-problem that cannot be
solved. You might want to back out and ask the newsgroup about the
larger problem.
And in the meanwhile, also go through some introductory textbook or
two on Lisp and computer science in general to get a grasp on the
semantics of symbolic variables, etc.
Kaz Kylheku wrote:
> On Mar 14, 1:11 am, Szabolcs Szucs <····@elte.hu> wrote:
>> How can I create a cons which points with its car and cdr to the
>> same object? Therefore if I change the car the cdr will change too..
> What you are asking for doesn't make any sense whatsoever.
It would make sense in C. There, a reference is basically an invisible
pointer. You can change the value in the remote location by assigning
a new value to the reference variable.
> Firstly, CAR and CDR do not point.
> These two places hold values.
But those values can be object references.
If the OP is willing to use some variant of
(setf (location-of-value the-object) ...)
where the-object is (car the-cons) or (cdr the-cons),
then it works okay.
> Clearly, this hack you are thinking of is part of some larger problem
> that you are trying to solve. The solution you are thinking of, to
> that larger problem, has led you to a sub-problem that cannot be
> solved. You might want to back out and ask the newsgroup about the
> larger problem.
That might be a good idea. There could be stylist reasons for taking
a different approach to whatever the OP is working on.
--
Dan
www.prairienet.org/~dsb
Dnia 14.03.2007 Dan Bensen <··········@cyberspace.net> napisa�/a:
>> What you are asking for doesn't make any sense whatsoever.
>
> It would make sense in C. There, a reference is basically an invisible
> pointer. You can change the value in the remote location by assigning
> a new value to the reference variable.
For the record -- there is no such thing as "reference" in C. I presume
you meant C++.
--
Daniel 'Nathell' Janus, GG #1631668, ············@nathell.korpus.pl
create_initial_thread(initial_function);
lose("CATS. CATS ARE NICE.\n");
-- Steel Bank Common Lisp, sbcl/runtime/runtime.c:425
Daniel Janus wrote:
> For the record -- there is no such thing as "reference" in C.
> I presume you meant C++.
Ooh, you're right. I've hardly used straight C at all since
the mid 90s. Thanks for pointing that out.
--
Dan
www.prairienet.org/~dsb
Hi,
"Kaz Kylheku" <········@gmail.com> writes:
> On Mar 14, 1:11 am, Szabolcs Szucs <····@elte.hu> wrote:
>> Hi,
>>
> [...]
> And in the meanwhile, also go through some introductory textbook or
> two on Lisp and computer science in general to get a grasp on the
> semantics of symbolic variables, etc.
Thank you for your advice.
>
>
--
kotee