While thinking about the recent discussion of EQ vs EQL, it occured to
me that I don't have a very clear picture of what kind of
optimizations are allowed by virtue of letting
(let ((x 1)) (eq x x))
evaluate to NIL. Can anyone explain it to me, preferably in terms of
how EQ might be implemented and how the expression above would be
compiled such that they combine to yield a NIL result for that
expression.
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
Peter Seibel <·····@gigamonkeys.com> wrote:
> While thinking about the recent discussion of EQ vs EQL, it occured to
> me that I don't have a very clear picture of what kind of
> optimizations are allowed by virtue of letting
>
> (let ((x 1)) (eq x x))
>
> evaluate to NIL. Can anyone explain it to me, preferably in terms of
> how EQ might be implemented and how the expression above would be
> compiled such that they combine to yield a NIL result for that
> expression.
Consider an implementation for the JVM with two alternative
representations for fixnums: an unboxed one that's implemented as a
primitive int or long, and a boxed one implemented by wrapping that
primitive in an object (in the style of Integer). Obviously having the
former representation is desirable for performance, while the latter
is needed for parameter passing in a sane JVM-based implementation.
And finally, let's assume that EQ is implemented using == in Java,
and for one reason or another not inlined by the implementation in
this case. So the implementation needs to box X. Thus the code might
look like this:
int x = 1;
eq(LispInteger.new(x), LispInteger.new(x));
(Of course a less naive implementation would only box X once, but it'd
be pretty strange for the spec to mandate implementation at that detail
level.)
--
Juho Snellman
Juho Snellman <······@iki.fi> writes:
> Peter Seibel <·····@gigamonkeys.com> wrote:
>> While thinking about the recent discussion of EQ vs EQL, it occured to
>> me that I don't have a very clear picture of what kind of
>> optimizations are allowed by virtue of letting
>>
>> (let ((x 1)) (eq x x))
>>
>> evaluate to NIL. Can anyone explain it to me, preferably in terms of
>> how EQ might be implemented and how the expression above would be
>> compiled such that they combine to yield a NIL result for that
>> expression.
>
> Consider an implementation for the JVM with two alternative
> representations for fixnums: an unboxed one that's implemented as a
> primitive int or long, and a boxed one implemented by wrapping that
> primitive in an object (in the style of Integer). Obviously having the
> former representation is desirable for performance, while the latter
> is needed for parameter passing in a sane JVM-based implementation.
>
> And finally, let's assume that EQ is implemented using == in Java,
> and for one reason or another not inlined by the implementation in
> this case. So the implementation needs to box X. Thus the code might
> look like this:
>
> int x = 1;
> eq(LispInteger.new(x), LispInteger.new(x));
>
> (Of course a less naive implementation would only box X once, but
> it'd be pretty strange for the spec to mandate implementation at
> that detail level.)
Right. Nice example. I was almost there, thinking about somehow
comparing an unboxed to a boxed version of "the same" number but
couldn't see any reason why evaluating X would produce one kind of
value one time and the other the other. But this is nice and simple.
Thanks.
-Peter
--
Peter Seibel : ·····@gigamonkeys.com
Gigamonkeys Consulting : http://www.gigamonkeys.com/
Peter Seibel <·····@gigamonkeys.com> writes:
> While thinking about the recent discussion of EQ vs EQL, it occured to
> me that I don't have a very clear picture of what kind of
> optimizations are allowed by virtue of letting
>
> (let ((x 1)) (eq x x))
>
> evaluate to NIL. Can anyone explain it to me, preferably in terms of
> how EQ might be implemented and how the expression above would be
> compiled such that they combine to yield a NIL result for that
> expression.
I cannot think of any optimization where this will happen, since they either
will be assigned the same value or be the same object in most ways interpretes
and conpilers can be interpreted. But now if you write something like:
(let ((x 1)
(y 1))
(eq x y))
Then some extremly unoptimized interpreter could allocate a different
cell for x and y, and return NIL. Since fixnums are required to be a
supertype of (signed-byte 16), (eq x y) in the above expression will
probably never return NIL as long as both x and y are fixnums in any
reasonable implementation. Now I cannot find anywhere in the hyperspec a
requirement that two fixnums compared with eq must return a true value,
but it may be that I have not looked the right place.
--
Gisle Sælensminde, Phd student, Scientific programmer
Computational biology unit, BCCS, University of Bergen, Norway,
Email: ·····@cbu.uib.no
The best way to travel is by means of imagination
+ Peter Seibel <·····@gigamonkeys.com>:
| While thinking about the recent discussion of EQ vs EQL, it occured to
| me that I don't have a very clear picture of what kind of
| optimizations are allowed by virtue of letting
|
| (let ((x 1)) (eq x x))
|
| evaluate to NIL. Can anyone explain it to me, preferably in terms of
| how EQ might be implemented and how the expression above would be
| compiled such that they combine to yield a NIL result for that
| expression.
I am by no means an expert, but let me give it a shot.
If it goes down in flames, all the merrier:
First, the compiler might notice that a constant is assigned to x, and
that no other assignment is ever assigned to (the same binding of) x,
so it might as well forego the binding and replace every x in the code
by the constant, essentially replacing the above code by
(eq 1 1)
Second, the two 1s might not be the same because two EQL fixnums might
not be EQ. In fact, the compiler might evaluate the whole constant
expression and finally replace the original form by NIL in the
compiled code. Ouch.
BTW, searching comp.lang.lisp at google groups for "eq x x" (including
quotes) reveals a long thread on this issue from 2003. The answer to
your question might be buried there.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell
On Sun, 18 Mar 2007 10:09:29 -0700, Peter Seibel <·····@gigamonkeys.com> said:
| ...
| what kind of optimizations are allowed by virtue of letting
| (let ((x 1)) (eq x x))
| evaluate to NIL.
Since MacLisp is given in the literature as an example (_the_
example?) of an implementation that does things in such a way, I
wonder if the following is more than just a speculation about a
possible implementation strategy:
All integers are boxed. (As I have read, MacLisp interned the
integers that fit in 10 bits.) Then, if I is a local variable
declared to be a fixnum, a compiler might decide to generate code
for (SETQ I (...)) that, instead of boxing a new fixnum object,
replaces the value in the existing box. For that to be possible,
the box must not be shared, so, if I is a formal parameter, its
function needs "call by value-in-referenced-box", rather than "call
by value-of-reference" (Lisp's usual). (Any similarities to FORTRAN
are not coincidental...)
---Vassil.
--
The truly good code is the obviously correct code.