EQ newbie question

Discussion of Common Lisp
pepribal
Posts: 4
Joined: Wed Jul 27, 2011 1:03 am

EQ newbie question

Post by pepribal » Wed Jul 27, 2011 1:45 am

I've just started learning lisp, and I've encountered my first doubt: it's regarding EQ.

I undertand that, as lisp implementations have the freedom to make copies of numbers and characters at any time, you cannot assume, for instance, that (eq 3 3) will be true, as yo cannot assume the first object is the same object as the second, and not just a copy. Please correct me if I understood wrong.

On the other hand, I have made this test:

Code: Select all

(setq a 5)
(setq b 5)
(eq a b)
T
In returning true, EQ is actually saying that 'a' is the same object as 'b'. Due to my C/C++ background I feel that then, 'a' and 'b' must be pointers to the same object '5', meaning that they have not only the same value, but they are the same very object, pointed to by two different variables (pointers). Once more, please correct me if I'm wrong.

Finally, in case my last assumption is right, I also assume that implementations should have the freedom to do this (creating pointers to the same object), or not (creating two different objects with the same value). In that case, you couldn't make any assumption about the (eq a b) result.

Am I too lost?

Thanks,

Pep.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: EQ newbie question

Post by ramarren » Wed Jul 27, 2011 3:19 am

Lisp implementations are allowed, but not required, to store objects (mostly numbers) which are small enough to fit into the machine word with their associated type tag (mostly characters, fixnums, single-floats on 64-bit architectures), directly.

Since Common Lisp is call-by-value (even if the majority of values are references), when arguments are passed to any function, in particular EQ, for objects stored this way, the function receives only the bit pattern of the object, copied onto the stack, and so EQ has no way to tell if the original patterns were stored in different places.

And yes, an implementation is free to represent some instances of objects directly and some as references, which means that behaviour of EQ for those types of objects should not be relied on.

pepribal
Posts: 4
Joined: Wed Jul 27, 2011 1:03 am

Re: EQ newbie question

Post by pepribal » Wed Jul 27, 2011 6:12 am

Thanks for the reply, it makes me understand how it works.

As for the piece of code:

Code: Select all

(setq a 5)
(setq b 5)
(eq a b)
T
It makes sense that it returns true if:

1. This particular implementation stores references, and not the pattern '5'.
2. The implementation is using the very same memory address for both 'a' and 'b'.

Is that what is taking place exactly?

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: EQ newbie question

Post by sylwester » Wed Jul 27, 2011 6:31 am

1. Actually, a and b gets an association different objects in memory which is a fixnum with the bitpattern of 5. eq compares the type and bit-pattern of the two and returns T.
If you instead went over the fixnum limit, say stored 234567890123456 in place of 5, the bit-pattern would have been a pointer to an bignum object and the two
bit-patterns would have had the same type but different bit patterns even though the numbers has the same value. CLISP doesn't require ANY number that is not the same object to be EQ so you should not rely on this feature.
Use (= a b) instead,

An interesting thing about this is that. Iin GNU CLISP: (eq 123456789012345 123456789012345) will return T if you have a 64bit OS and NIL if you have a 32bit OS.

2. Some implementations allocate memory locations to small numbers so that in your case a and b would have pointed to the very same address area, but doing it with the whole fixnum space would wast a lot of memory.

pepribal
Posts: 4
Joined: Wed Jul 27, 2011 1:03 am

Re: EQ newbie question

Post by pepribal » Wed Jul 27, 2011 6:54 am

So, if I understand well, that means that when the bit pattern and the type are the same, then EQ returns T, even if the bit pattern represents a number and not an address. However, that is in contradiction with Ramarren's post, as he says:
Since Common Lisp is call-by-value (even if the majority of values are references), when arguments are passed to any function, in particular EQ, for objects stored this way, the function receives only the bit pattern of the object, copied onto the stack, and so EQ has no way to tell if the original patterns were stored in different places.
From which I understand that, even if the pattern is the same, EQ returns NIL, as it has no way to know if both objects are the same, i.e., stored in the same memory location.

Or perhaps I don't understand either one of the posts.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: EQ newbie question

Post by ramarren » Wed Jul 27, 2011 7:34 am

pepribal wrote:From which I understand that, even if the pattern is the same, EQ returns NIL, as it has no way to know if both objects are the same, i.e., stored in the same memory location.
What I meant and should have made clear is that this behaviour is unspecified by the standard, so the implementation of EQ is free to return anything, or, more exactly, a generalized boolean. Since any object other than the symbol NIL is true, and in this case EQ can return either true of false, this actually means anything.

The specification actually provides this in an example for EQ:

Code: Select all

(eq 3 3)
=>  true
OR=>  false
And there is no requirement for this to be even consistent per implementation, so it might change due to optimization settings, memory conditions, or anything. If the type and bit pattern are actually the same for non-pointers most implementation return true, since that is the most sane behaviour, but they are not required to.

pepribal
Posts: 4
Joined: Wed Jul 27, 2011 1:03 am

Re: EQ newbie question

Post by pepribal » Wed Jul 27, 2011 8:35 am

I see. Well, rather confusing on the part of the standard. I don't see the point in in this behaviour, but I guess this is the way the satandard goes.

Thanks a lot for your posts.

Pep.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: EQ newbie question

Post by ramarren » Wed Jul 27, 2011 9:43 am

As usual, it is a combination of historical and optimization reasons. EQ is allowed to operate without any typechecks at all. Admittedly for modern systems this doesn't really matter.

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: EQ newbie question

Post by nuntius » Wed Jul 27, 2011 9:49 am

I view EQ as one of the implementation details left in the standard.

There was a lot of old code using it on existing systems, so it had to stay in.
The existing implementations had inconsistent semantics, so it couldn't be well specified.

As is, EQ can be a useful optimization and is sometimes the correct intent, but it should generally be avoided. EQL, EQUAL, STRING=, =, etc. are usually more appropriate

sylwester
Posts: 133
Joined: Mon Jul 11, 2011 2:53 pm

Re: EQ newbie question

Post by sylwester » Fri Jul 29, 2011 7:23 pm

pepribal wrote:I see. Well, rather confusing on the part of the standard. I don't see the point in in this behaviour, but I guess this is the way the satandard goes.

Thanks a lot for your posts.

Pep.
EQ is one of the 7 operators defined by McCarthy in his original LISP-paper in 1960. That LISP only had symbols and EQ was T only for the same symbol or both (). It was undefined for the same object.
Another relic from that paper that is somewhat useless today but still part of CLISP is atom.

Post Reply