Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!rpi!crdgw1!uunet!mcsun!ukc!edcastle!aiai!jeff
From: jeff@aiai.ed.ac.uk (Jeff Dalton)
Newsgroups: comp.lang.lisp
Subject: Eternal fixnum question (was Re: GET / GETF warning.)
Message-ID: <4580@skye.ed.ac.uk>
Date: 30 Apr 91 18:08:26 GMT
References: <641@zogwarg.etl.army.mil>
Reply-To: jeff@aiai.UUCP (Jeff Dalton)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 109

In article <641@zogwarg.etl.army.mil> hoey@zogwarg.etl.army.mil (Dan Hoey) writes:
>The fact that GET/GETF use EQ instead of EQL needs to be emphasized
>more.  Such as a remark that it is an error to use a number as an
>indicator in the property list.
>
>It's all the worse that for many implementations EQL fixnums are EQ,
>so you don't see the bug until your problem gets into bignums.

I suppose this isn't the _best_ place to raise this question,
but when EQ, fixnums, and FAQ appear in the same place it's
almost irresistible.

As you all will recall, Common Lisp allows EQ to return false
for fixnums that are EQL.  Indeed, it can do so even in a case
like this:

[1]   (let ((x z) (y z)) (eq x y))  ; CLtL II p 288

or even:

[2]   (let ((x 5)) (eq x x))        ; CLtL II p 104

Indeed, at least one compiler (AKCL 1-505) has EQ always return
NIL when the arguments are known to be fixnums.  There is no 
significant efficiency reason for this.  EQL for known fixnums
compiles into the same code as EQ for objects: (x == y).  The
only difference is that x and y are C ints in the EQL case
and pointers in the EQ one.

A number of people find cases like [1] and especially [2] difficult to
understand, even if they are experienced users or even implementors of
Lisp.  They could understand if the reason were just to keep the rule
simple: EQ can _never_ be relied on for fixnums.  What's hard to see
is why in any reasonable implementation [1] or [2] would actually turn
out to be false.  And, as I will try to show below, the usual answers
to this are not very convincing.  I'm hoping there's a better answer 
and that someone can say what it is.

It's easy to understand a case like this one:

[3]   (eq 1 (- 3 2)) ==> ?

Why?  Well, in some implementations fixnums might be implemented
as pointers to locations that contain the actual values and new
fixnums might be allocated whenever a fixnum result is returned.
In [3], 1 and (- 3 2) might be pointers to different locations
that both contain 1; but since EQ compares only the pointers it
would return NIL.

So much for [3].  But we need a different argument to show why [1] or
[2] might return NIL, because if all fixnums were pointers-to, both
[1] and [2] would be true (unless we imagine that merely referring to
a fixnum causes a new one to be allocated, an implementation that
would be bizarre, to say the least).  Moreover, they would also be
true if all fixnums were always represented as tagged immediate
values, because they would have the same tag (fixnum) and the same
value.  Indeed, it's hard to imagine any reasonable representation
that, if used for all fixnums, would have [1] or [2] be false.

This suggests that the relevant case is when more than one
representation might be used.  The official reason (CLtL II p 288
again) seems to be that the "breakdown" of EQ for numbers is needed
for a compiler to be able to produce "exceptionally efficient
numerical code".  We can imagine an implementation that normally
allocated fixnums on the heap and represented them as pointers
to heap locations but also put fixnums directly in registers or
stack locations for manipulation by efficient compiled code.

But this isn't very convincing either.  KCL uses two representations
in the way suggested and could make [1] and [2] return true without
any efficiency loss -- unless you count the efficiency of being able
to skip the comparison altogether.  It is, moreover, hard to see why
KCL should be a special case.  If fixnum values are being used
directly, the compiler knows and can emit a direct compare.  If
the values are not direct, the compiler knows _that_ and can emit
a direct compare of the pointers.

This seems to account at least for [2], (let ((x 5)) (eq x x)), where
there is only one variable.  But what about [1], (let ((x z) (y z))
(eq x y))?  Maybe x is represented one way and y another.  But again
the compiler has to know this, because if it didn't it would also
be unable to handle cases such as

[4]  (let ((x z) (y z)) (+ x y))

So we seem to be left with the conclusion that there isn't an
efficiency reason after all.

There is still a conceptual argument, namely that if x and y are
different registers or stack locations they shouldn't count as EQ.
This will not work as-is, because it would imply that x and y should
not count as EQ when they contain other values such as (pointers to)
cons cells.  Instead, we'd have to say something like this: when
fixnum values are used directly, they aren't Lisp objects any more
and so it isn't meaningful to compare them with EQ.

That's better, but it still seems to be wrong.  This treatment of
fixnums is an optimization.  We should let optimizations have an
impact on the semantics only when some important efficiency gain is
obtained.  Otherwise, we leave the semantics alone and allow only
those optimizations that respect the semantics to the extent that any
violations have no impact on the behavior of programs.  That some
objects might be manipulated internally as non-objects is not in
itself a reason for saying they weren't objects in the first place.

It therefore seems that examples such as [1] and [2] are useful
only to make the problems due to examples such as [3] more universal.

-- jd