What is eq? used for

2 views
Skip to first unread message

bobu...@yahoo.com

unread,
Jan 14, 2006, 8:57:14 AM1/14/06
to
RUNNING (In DRScheme)

(eq? 5 3) ==> #f
(eq? 5 5) ==> #t
(eq? 3/2 3/2) ==> #f
(eq? 3/2 6/4) ==> #f
(eq? 3.14 (+ 3.0 .14)) ==> #f

(eq? null '()) ==> #t
(eq? null ()) ==> #t
(eq? #t 't) ==> #f
(eq? "foo" 'foo) ==> #f

(eq? 3 3.0) ==> #f
(eq? 1+i 1+i) ==> #f

(let ((x (* 8 2))) (eq? x x)) ==> #t
(eq? #\a #\a) ==> #t

(eq? #t #t) ==> #t
(eq? #f #f) ==> #t
(eq? #t #f) ==> #f

(eq? (cdr '(a)) '()) ==> #t
(eq? 'a 'a) ==> #t
(eq? 'a (string->symbol "a")) ==> #t

(eq? "abc" "abc") ==> #f
(eq? car car) ==> #t
(eq? (lambda (x) x) (lambda (y) y)) ==> #f

It seems hard to guess when eq? will give true and when false. What is
the use of eq? and is there some simple rule or way of thinking to
conclude what answer eq? will give.

I've read somewhere that "it is possible to implement eq? much more
efficiently than eqv?, for example, as a simple pointer comparison".
Does this have to do with the concepts of "deep copy" and "shallow
copy"? But even if it's done for efficiency, it must be some simple way
to predict the behaviour. If not what's the use.

Bob

Lauri Alanko

unread,
Jan 14, 2006, 9:11:22 AM1/14/06
to
In article <1137247034....@g44g2000cwa.googlegroups.com>,

<bobu...@yahoo.com> wrote:
> I've read somewhere that "it is possible to implement eq? much more
> efficiently than eqv?, for example, as a simple pointer comparison".
> Does this have to do with the concepts of "deep copy" and "shallow
> copy"?

A little bit, yes. The elements of a shallow-copied object are eq? to
the corresponding elements of the original object, whereas the
elements of a deep-copied object are (typically) equal? but not
necessarily eq? to the elements of the original.

> But even if it's done for efficiency, it must be some simple way
> to predict the behaviour. If not what's the use.

R5RS says:

`Eq?' and `eqv?' are guaranteed to have the same behavior on
symbols, booleans, the empty list, pairs, procedures, and non-empty
strings and vectors.

In practice, eq? is used to compare symbols, or to discern low-level
"object identity" e.g. to detect cyclical lists.

It's funny, I don't think I have ever used eqv? for anything. Always
just eq?, equal? or one of the more specific comparison routines, e.g.
= or char=?


Lauri

Jens Axel Søgaard

unread,
Jan 14, 2006, 9:15:33 AM1/14/06
to
bobu...@yahoo.com wrote:

> I've read somewhere that "it is possible to implement eq? much more
> efficiently than eqv?, for example, as a simple pointer comparison".

Yep.

> RUNNING (In DRScheme)
>
> (eq? 5 3) ==> #f
> (eq? 5 5) ==> #t

Small numbers are called fixnums and are typically
represented as a pointer, where the first or last bit
indicates whether it a "real" pointer or a fixnum.
A value represented directly in a pointer is called
"unboxed".

Large numbers (bignums) are represented as pointer
to a structure containing, say, a list of "digits".
Values represented as a pointer to a stucture
are called "boxed". Thus two bignums can be equal
even if the pointers are different:

> (eq? 1000000000000
1000000000000)
#f

> (eq? 3/2 3/2) ==> #f
> (eq? 3/2 6/4) ==> #f

Same, fractions are represented as a pointer to
structure containing nominator and denominator.
So fractions are also boxed.

> (eq? 3.14 (+ 3.0 .14)) ==> #f

Floats are also boxed in DrScheme.

The lesson is thus to use eqv? if you want
comparisons to work on numbers.

> (eq? null '()) ==> #t
> (eq? null ()) ==> #t
> (eq? #t 't) ==> #f
> (eq? "foo" 'foo) ==> #f
>
> (eq? 3 3.0) ==> #f
> (eq? 1+i 1+i) ==> #f
>
> (let ((x (* 8 2))) (eq? x x)) ==> #t
> (eq? #\a #\a) ==> #t
>
> (eq? #t #t) ==> #t
> (eq? #f #f) ==> #t
> (eq? #t #f) ==> #f
>
> (eq? (cdr '(a)) '()) ==> #t
> (eq? 'a 'a) ==> #t

These you can explain yourself.

> (eq? 'a (string->symbol "a")) ==> #t

This is due to "interning" of symbols. All symbols
are kept in a table. If you make a symbol that already
exist in the system, a pointer to the same box as last
is returned. Thus determining whether two symbols are
the same symbol is just one pointer comparison.

> (eq? "abc" "abc") ==> #f

Strings are boxed.

> (eq? car car) ==> #t

Car evaluates to the same "box" (contating a procedure).

> (eq? (lambda (x) x) (lambda (y) y)) ==> #f

Here you produce two different "boxes".

--
Jens Axel Søgaard

Lauri Alanko

unread,
Jan 14, 2006, 9:32:20 AM1/14/06
to
In article <dqb0qa$4b5$1...@oravannahka.helsinki.fi>,

Lauri Alanko <l...@iki.fi> wrote:
> It's funny, I don't think I have ever used eqv? for anything. Always
> just eq?, equal? or one of the more specific comparison routines, e.g.
> = or char=?

Incidentally, I've often found it a bit peculiar that although there
are a number of comparison procedures that are essentially just eqv?
with a limited domain, there is no symbol=? in R5RS.

Of course eq? works just as fine, but oftentimes one expects the
compared values to both be symbols, and a dedicated procedure would
make this clearer in the code and might help in detecting errors (for
instance, a #f might accidentally be compared against).


Lauri

Message has been deleted

bobu...@yahoo.com

unread,
Jan 14, 2006, 9:57:25 AM1/14/06
to
Jens Axel Søgaard wrote

> Values represented as a pointer to a stucture
> are called "boxed"
..

> a pointer to the same box as last is returned.
..
>Strings are boxed.
..

> Car evaluates to the same "box" (contating a procedure).
..

>Here you produce two different "boxes".

What is a box? Is it an object in the Heap that has a pointer pointing
to it? Or is it something else?

--

Jens Axel Søgaard

unread,
Jan 14, 2006, 9:59:44 AM1/14/06
to
matteo d'addio 81 wrote:
> Jens Axel Søgaard ha scritto:

>
>>>(eq? 'a (string->symbol "a")) ==> #t
>>
>>This is due to "interning" of symbols. All symbols
>>are kept in a table. If you make a symbol that already
>>exist in the system, a pointer to the same box as last
>>is returned. Thus determining whether two symbols are
>>the same symbol is just one pointer comparison.
>
> I was playing with string->symbol and I found that
>
> (eq? 'hello 'Hello) gives #t
> (eq? 'hello (string->symbol "hello")) gives #t and
> (eq? 'hello (string->symbol "Hello")) gives #f but
> (eq? 'Hello (string->symbol "hello")) gives #t and
> (eq? 'Hello (string->symbol "Hello")) gives #f
>
> I can't figure out why.

You forgot to write which implementation and version,
you are using.

DrScheme was case insensitive in 20x and in the
30x series it is case-sensitive.

Before the reader saw 'Hello and converted it
automatically to 'hello.

So you had

; in 20x
> 'Hello
hello

thus in (eq? 'hello 'Hello) you were really
comparing 'hello and 'hello .

Now in 30x you get:

> (eq? 'hello 'Hello)
(eq? 'hello (string->symbol "hello"))
(eq? 'hello (string->symbol "Hello"))
(eq? 'Hello (string->symbol "hello"))
(eq? 'Hello (string->symbol "Hello"))

#f
#t
#f
#f
#t

--
Jens Axel Søgaard

matteo d'addio 81

unread,
Jan 14, 2006, 10:03:37 AM1/14/06
to

Jens Axel Søgaard ha scritto:

> > (eq? 'a (string->symbol "a")) ==> #t


>
> This is due to "interning" of symbols. All symbols
> are kept in a table. If you make a symbol that already
> exist in the system, a pointer to the same box as last
> is returned. Thus determining whether two symbols are
> the same symbol is just one pointer comparison.
>

I was playing with string->symbol and I found that

(eq? 'hello 'Hello) gives #t
(eq? 'hello (string->symbol "hello")) gives #t and
(eq? 'hello (string->symbol "Hello")) gives #f but
(eq? 'Hello (string->symbol "hello")) gives #t and
(eq? 'Hello (string->symbol "Hello")) gives #f

It seems that if a string contains an uppercase letter
a box is created, otherwise not. Is it for making possible
to reconvert back the symbol to the original string?

matteo

matteo d'addio 81

unread,
Jan 14, 2006, 10:16:48 AM1/14/06
to

You're right. My intention was to say that I'm using a
case-insensitive implementation (DrScheme 209).

> Now in 30x you get:
>
> > (eq? 'hello 'Hello)
> (eq? 'hello (string->symbol "hello"))
> (eq? 'hello (string->symbol "Hello"))
> (eq? 'Hello (string->symbol "hello"))
> (eq? 'Hello (string->symbol "Hello"))
>
> #f
> #t
> #f
> #f
> #t

There's no need for boxes is 30x, right?

>
> --
> Jens Axel Søgaard

Jens Axel Søgaard

unread,
Jan 14, 2006, 10:23:27 AM1/14/06
to
bobu...@yahoo.com wrote:
> Jens Axel Søgaard wrote
>> Values represented as a pointer to a stucture
>>are called "boxed"

> What is a box? Is it an object in the Heap that has a pointer pointing
> to it?

Yes.

--
Jens Axel Søgaard

Pascal Bourguignon

unread,
Jan 14, 2006, 10:29:58 AM1/14/06
to
bobu...@yahoo.com writes:

It's indeed related to the kind of copy.
http://www.nhplace.com/kent/PS/EQUAL.html

eq? compares the pointers that hide between some variables and values in lisp.

5 and 3 are fixnum, they can be held in one word along with their type
(fixnum), so we don't need to make pointers to them: we can store and
compare them directly.

For example:
31 3 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| fixnum value |type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


3/2 and 3/2 are rationals, they are stored as a record of two pointers
and a type. For example:

31 0
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| numerator |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| denominator |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

(The numerator or denominator themselves can be either fixnums like in
the case of 3/2, or bignums, in which case the numerator and/or
denominator will contain a pointer to the bignum).

Since two or more words cannot be held in a variable or register, we
put the rational record on the heap and keep a pointer to it in the
variable/register. eq? will then return #t only if the two variables
point to the same rational, not whe they point to two different
rationals that happen to be equal.

(eq? var var) is always #t.

Note that: (let ((r 3/2))
(let ((e (list 'eq? r r)))
(display e)
(eval e (SCHEME-REPORT-ENVIRONMENT 5))))
prints: (EQ? 3/2 3/2)
and returns: #t

but: (let ((e (list 'eq? 3/2 (/ 6 4))))
(display e)
(eval e (SCHEME-REPORT-ENVIRONMENT 5)))
prints: (EQ? 3/2 3/2)
and returns: #f

and: (let ((e (list 'eq? 3/2 3/2)))
(display e)
(eval e (SCHEME-REPORT-ENVIRONMENT 5)))
prints: (EQ? 3/2 3/2)
and can return either #t or #f depending on how the implementation
treats the literals 3/2 and 3/2.


> But even if it's done for efficiency, it must be some simple way
> to predict the behaviour. If not what's the use.

Just read the report! It's not even a multi-thousand page book like
the Common Lisp HyperSpec! Why don't you read the R5RS?

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_idx_216

Eq? and eqv? are guaranteed to have the same behavior on symbols,
booleans, the empty list, pairs, procedures, and non-empty strings

and vectors. Eq?'s behavior on numbers and characters is
implementation-dependent, but it will always return either true or
false, and will return true only when eqv? would also return
true. Eq? may also behave differently from eqv? on empty vectors
and empty strings.


Since part of the behavior is implementation dependant, to be able to
predict their behavior you'd have to know the specific implementation.

--
__Pascal Bourguignon__ http://www.informatimago.com/

"You cannot really appreciate Dilbert unless you read it in the
original Klingon"

bobu...@yahoo.com

unread,
Jan 14, 2006, 11:23:45 AM1/14/06
to
Actually I do read R5RS and I like it, whenever I understand it, but I
must confess I didn't do it this time. Actually my goal was something
else then understanding the rules. I wanted an opinion why the
designers of Scheme made it so complicated with eq?, eqv?, equal? (at
least it seems so to a newbie). It's the same feeling I got when I
first saw the let, let*, fluid-let, letrec and named let.

The first time I saw cons, car and cdr it was "love at first sight". I
can't say the same thing about eq? variants and let variants.

Bob

Brian Harvey

unread,
Jan 14, 2006, 12:48:34 PM1/14/06
to
bobu...@yahoo.com writes:
> I wanted an opinion why the
>designers of Scheme made it so complicated with eq?, eqv?, equal?

Although the details are messy, the principles aren't.

EQUAL? -> same value. In purely functional programming, in which we don't
care about how things are represented internally, EQUAL? would solve all
problems (although not necessarily as fast as possible).

EQ? -> same memory location. Computable in a single machine language
instruction, so not only Theta(1) asymptotic time, but tiny constant factor.
Implies that mutating one mutates the other, since there is no "other"!

EQV? -> (mutable and EQ?) or (immutable and EQUAL?), roughly. "Equal enough
to be usable interchangeably in the program."

------

Different explanation, hopefully equivalent: The important distinction is
really two-way: equal value vs. identical object. In an ideal world, there
would only be two equality predicates. Unfortunately, there are certain
kinds of equal values that implementations are allowed to make share memory
or make not share memory: numbers, empty vectors, empty strings. These are
immutable, and *ideally* for immutable things EQUAL implies EQ, but in fact
there might be multiple copies of the same number, for example. (The reason
this doesn't arise for symbols is that implementations are required to make
equal symbols EQ, except for nonstandard extensions in the fine print.)
So EQV means "EQ in the ideal implementation," sort of. "EQ as we wish it
worked."

------

For completeness, we should note that there is a fourth important equality
predicate, namely =, which is not a subset of any of the others because of
the issues about exactness of numbers. Two numbers with the same numeric
value, one exact and one inexact, are numerically equal (=) but not EQV.

bobu...@yahoo.com

unread,
Jan 14, 2006, 4:37:19 PM1/14/06
to
Good explaination but still confused. Running the little piece of code
below

(let ((f (lambda (x) x)) (g (lambda (y) y)))
(display (eq? f g))
(display (eqv? f g))
(display (equal? f g)))

produces #f #f #f

A human would say that f and g are the same function, but Scheme
appears to say no.

(I'm using
Welcome to DrScheme, version 300.
Language: Pretty Big (includes MrEd and Advanced Student).)

Bob

Lauri Alanko

unread,
Jan 14, 2006, 4:46:50 PM1/14/06
to
In article <1137274639.9...@f14g2000cwb.googlegroups.com>,

<bobu...@yahoo.com> wrote:
> (let ((f (lambda (x) x)) (g (lambda (y) y)))
> (display (eq? f g))
> (display (eqv? f g))
> (display (equal? f g)))
>
> produces #f #f #f
>
> A human would say that f and g are the same function, but Scheme
> appears to say no.

You are comparing two different closures that contain (modulo alpha)
the same code. They are different heap objects, and hence eq? returns
#f.

What should equal? test for? It would be pointless to check whether
the two closures contain exactly the same code, as different closures
may behave exactly the same. Should these two be considered equal or
not?

(lambda (x) (* x 2))
(lambda (x) (+ x x))

So, sensibly, equal? should test for whether the closures behave the
same, i.e. whether they are extensionally equivalent. Unfortunately,
as a corollary to Rice's Theorem, there is no way to test for such a
thing in general.

So, as far as procedures are concerned, equal? cannot really do
anything more than eq? does.


Lauri

H.

unread,
Jan 14, 2006, 5:01:19 PM1/14/06
to
Have you used Java? If so, think about the difference between == and
equals.

If not,
Let's say I put some value into Box A and some value into Box B. And I
say, tell me about these two boxes here, are they equal?

There are two different questions I could be asking with this imprecise
language.
1) I could be asking, are Box A and Box B the same box? Well, no.
2) I could be asking, Do Box A and Box B contain the same value? Well,
that depends on the values inside of the boxes.

eq? is asking question 1.
equal? is asking question 2.
eqv? is a little odd, in that it mostly asks question 1 but sometimes
asks question 2. Here is what I found on a Scheme tutorial:
"eqv? returns #t if obj1 and obj2 are both true or both false, if both
are symbols and spelled the same way, if both are numbers and
numerically equal, if both are characters and are the same character
according to char=?, if both are the empty list, if they are pairs,
lists or vectors that denote the same locations in the store or if they
are procedures whose location tags are equal. Practically, it does not
differ that much from eq?, but in cases where the behaviour of eq? is
not specified, eqv? should be used."

Honestly, I'm not sure what "if they are procedures whose location tags
are equal" means, so I'll punt that to someone else.

I know eqv is

H.

unread,
Jan 14, 2006, 5:06:07 PM1/14/06
to
>>I know eqv is.

Whoops. Didn't finish. I was going to say: "I know eqv? is mostly the
same thing as eq?, but I'm curious myself as to why it was added to the
list. This is my past experience with Those Other Languages shihing
through, because I can quickly say: "Oh, eq? is this thing, and and
equal? this other other, and eqv? - well, that's just weird."

Pascal Bourguignon

unread,
Jan 14, 2006, 5:16:18 PM1/14/06
to
bobu...@yahoo.com writes:

> Good explaination but still confused. Running the little piece of code
> below
>
> (let ((f (lambda (x) x)) (g (lambda (y) y)))
> (display (eq? f g))
> (display (eqv? f g))
> (display (equal? f g)))
>
> produces #f #f #f
>
> A human would say that f and g are the same function, but Scheme
> appears to say no.

Define "same"!

Did you read the paper I linked?


DrScheme says:

> (lambda (x) x)
#<procedure:4:2>

Where do you see a function?

Programs are not mathematical functions!

You say "same" because you've been indoctrinated by mathematicians.

But ask DrScheme again:

> (lambda (x) x)
#<procedure:4:2>
> (lambda (x) x)
#<procedure:6:2>
>

See? You've written twice the same text, but DrScheme has built two
different objects. How could it know that they're the same
mathematical function?

Equality of function in maths is defined as the equality of the values
on the domain. For functions with an infinite domain, it can be
rather hard to compute thise equality. You'd need to integrate a
theorem prover in lisp! And since in programs we can have functions
that don't implement algorithms, it would even be useless.


One more difficulty: when you write lambda in lisp, you don't get a
function, but a closure!

Are these two "functions" equal?
(let ((x 0)) (lambda (y) (set! x (+ x y))))
(let ((u 0)) (lambda (v) (set! u (+ u v))))

You guess it? They're not _functions_!

But for a given application, you can define your equality operator,
and thanks to lisp, work on the source sexpr easily:

(my-function-equal? '(lambda (x) x) '(lambda (y) y))


--
__Pascal Bourguignon__ http://www.informatimago.com/

"By filing this bug report you have challenged the honor of my
family. Prepare to die!"

bobu...@yahoo.com

unread,
Jan 14, 2006, 5:26:19 PM1/14/06
to
Thanks H. your Box A Box B analogy is good. In a previous post

Brian Harvey wrote:
>Although the details are messy, the principles aren't.

I have no problems with principles, but I do have problems with
details. Isn't it the responsibilty of whoever designed Scheme to make
the details clean. I mean God (or maybe von Neumann) gave him clean
principles but he gave us back messy details. I know I shouldn't say
such a thing since I'm probably wrong, but I can change my mind later
when I understand the trade offs that the designer had to do. Right now
I'm trying to make som simple rules to stick to when I program. I have
made four rules (wrong ones??)


; 1. Use = if you want to compare numbers
(eq? 3 3.0) ==> f
(eqv? 3 3.0) ==> f
(equal? 3 3.0) ==> f
(= 3 3.0) ==> t

; 2. eq? is useful for fast comparisons of non-numbers
(let ((x (cons 8 2))) (eq? x x)) ==> t

; 3. Use equal? if you want to make "deep" comparison of data
structures.
(let ((p (cons 1 2)) (q (cons 1 2)))
(display (eq? p q)) ==> f
(display (eqv? p q)) ==> f
(display (equal? p q))) ==> t

; 4. Never use eqv?


Bob

bobu...@yahoo.com

unread,
Jan 14, 2006, 6:39:14 PM1/14/06
to
Pascal Bourguignon wrote:
>Did you read the paper I linked?

I've try to read it but got headache from it. I've quoted a small
snippet below. C'mon even you have to admit that it sounds like
Aristotle. If every procedure in Scheme was complicated as eqv? I'd be
looking for a warmer place.

Bob

----------------- snippet from R5RS ----------------
The eqv? procedure returns #t if:

* obj1 and obj2 are both #t or both #f.

* obj1 and obj2 are both symbols and

(string=? (symbol->string obj1)
(symbol->string obj2))
===> #t

Note: This assumes that neither obj1 nor obj2 is an
``uninterned symbol'' as alluded to in section 6.3.3. This report does
not presume to specify the behavior of eqv? on implementation-dependent
extensions.

* obj1 and obj2 are both numbers, are numerically equal (see =,
section 6.2), and are either both exact or both inexact.

* obj1 and obj2 are both characters and are the same character
according to the char=? procedure (section 6.3.4).

* both obj1 and obj2 are the empty list.

* obj1 and obj2 are pairs, vectors, or strings that denote the same
locations in the store (section 3.4).

* obj1 and obj2 are procedures whose location tags are equal
(section 4.1.4).

The eqv? procedure returns #f if:

* obj1 and obj2 are of different types (section 3.2).

* one of obj1 and obj2 is #t but the other is #f.

* obj1 and obj2 are symbols but

(string=? (symbol->string obj1)
(symbol->string obj2))
===> #f

* one of obj1 and obj2 is an exact number but the other is an
inexact number.

* obj1 and obj2 are numbers for which the = procedure returns #f.

* obj1 and obj2 are characters for which the char=? procedure
returns #f.

* one of obj1 and obj2 is the empty list but the other is not.

* obj1 and obj2 are pairs, vectors, or strings that denote distinct
locations.

* obj1 and obj2 are procedures that would behave differently
(return different value(s) or have different side effects) for some
arguments.
--------------------- end of snippet ------------------------------

Joe Marshall

unread,
Jan 14, 2006, 7:04:18 PM1/14/06
to
> ; 1. Use = if you want to compare numbers
> (eq? 3 3.0) ==> f
> (eqv? 3 3.0) ==> f
> (equal? 3 3.0) ==> f
> (= 3 3.0) ==> t
>
> ; 2. eq? is useful for fast comparisons of non-numbers
> (let ((x (cons 8 2))) (eq? x x)) ==> t
>
> ; 3. Use equal? if you want to make "deep" comparison of data
> structures.
> (let ((p (cons 1 2)) (q (cons 1 2)))
> (display (eq? p q)) ==> f
> (display (eqv? p q)) ==> f
> (display (equal? p q))) ==> t
>
> ; 4. Never use eqv?

NO! You should almost always use EQV? instead of EQ?
EQ? is fast, but it is unpredictable for characters and numbers because
of implementation details. EQV? is almost as fast, but it `does the
right thing' for characters and numbers.

Use EQV? if you want to compare `structure' for `sameness', use EQUAL?
if you want to compare `structure' for `similarity'. Use `=` for
numbers. (Use EQ? only if you *know* you aren't comparing numbers or
chars)

Lauri Alanko

unread,
Jan 14, 2006, 7:15:21 PM1/14/06
to
In article <1137283458....@g49g2000cwa.googlegroups.com>,

Joe Marshall <eval....@gmail.com> wrote:
> NO! You should almost always use EQV? instead of EQ?
> EQ? is fast, but it is unpredictable for characters and numbers because
> of implementation details.

Do you often encounter a situation where you need to compare values
that may be either number or characters but not lists or vectors (or
if they are, then you are interested in their physical identity)? To
me this situation, the only one where eqv? makes sense, is pretty darn
rare.


Lauri

Jens Axel Søgaard

unread,
Jan 14, 2006, 7:36:56 PM1/14/06
to
bobu...@yahoo.com wrote:
> Good explaination but still confused. Running the little piece of code
> below
>
> (let ((f (lambda (x) x)) (g (lambda (y) y)))
> (display (eq? f g))
> (display (eqv? f g))
> (display (equal? f g)))
>
> produces #f #f #f
>
> A human would say that f and g are the same function, but Scheme
> appears to say no.

(define (s x)
(+ (* (cos x) (cos x))
(* (sin x) (sin x))))

(define (t x)
1.0)

Is s and t the same function?

--
Jens Axel Søgaard

H.

unread,
Jan 14, 2006, 8:11:24 PM1/14/06
to

>
> NO! You should almost always use EQV? instead of EQ?
> EQ? is fast, but it is unpredictable for characters and numbers because
> of implementation details. EQV? is almost as fast, but it `does the
> right thing' for characters and numbers.
>
> Use EQV? if you want to compare `structure' for `sameness', use EQUAL?
> if you want to compare `structure' for `similarity'. Use `=` for
> numbers. (Use EQ? only if you *know* you aren't comparing numbers or
> chars)

So I was thinking as EQ? as equivalent to == in Java. Where am I going
wrong? Is == really equivalent to EQV?, or does it have no equivalence?

What kind of implementation details in EQ? prevent it from working
predictably with characters and numbers? Can you give me an example
where it misbehaves?

Thanks. : ).

Pascal Bourguignon

unread,
Jan 14, 2006, 8:12:04 PM1/14/06
to

In Pseudo Scheme:

> (s 4.9885893)
0.99999994
> (not (= (s 4.9885893) (t 1)))
#t

In DrScheme:

> (s 0.24913715024140834)
0.9999999999999999
> (not (= (t 0.24913715024140834) (s 0.24913715024140834)))
#t


Therefore they're not the same.


--
__Pascal Bourguignon__ http://www.informatimago.com/

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.

H.

unread,
Jan 14, 2006, 8:17:00 PM1/14/06
to

>
> (define (s x)
> (+ (* (cos x) (cos x))
> (* (sin x) (sin x))))
>
> (define (t x)
> 1.0)
>
> Is s and t the same function?
>
> --
> Jens Axel Søgaard

I was taught that these are the same /function/ but different
/procedures/, and that the strict use of the word "function" concerns
input and output values. Procedure, on the other hand, is about the
individual steps within a function. Any function can be written in
infinite many ways. So my answer would be, yes, they are the same
function. What's your answer?

Lauri Alanko

unread,
Jan 14, 2006, 8:18:15 PM1/14/06
to
In article <1137287484....@z14g2000cwz.googlegroups.com>,

H. <hbe...@gmail.com> wrote:
> So I was thinking as EQ? as equivalent to == in Java.

No, but you are wrong thinking of Java's == as equivalent to = in
Scheme.

> What kind of implementation details in EQ? prevent it from working
> predictably with characters and numbers?

In Scheme, numbers can be arbitrarily large, and big numbers are
typically heap-allocated without interning, making it possible to have
two numbers that have the same value (making = return #t) but
different identity (making eq? return #f).

For instance, in mzscheme, on a 64-bit platform:

> (eq? (expt 2 61) (expt 2 61))
#t
> (eq? (expt 2 62) (expt 2 62))
#f

Here you can see the border between numbers that are stored directly
in the pointer and numbers that are stored in distinct heap-allocated
objects.


Lauri

Jens Axel Søgaard

unread,
Jan 14, 2006, 8:24:03 PM1/14/06
to
Pascal Bourguignon wrote:

>>(s 0.24913715024140834)
> 0.9999999999999999
>
>>(not (= (t 0.24913715024140834) (s 0.24913715024140834)))
> #t

Shh...

--
Jens Axel Søgaard

Kjetil S. Matheussen

unread,
Jan 14, 2006, 8:33:14 PM1/14/06
to
On Sat, 14 Jan 2006 bobu...@yahoo.com wrote:

> Good explaination but still confused. Running the little piece of code
> below
>
> (let ((f (lambda (x) x)) (g (lambda (y) y)))
> (display (eq? f g))
> (display (eqv? f g))
> (display (equal? f g)))
>
> produces #f #f #f
>
> A human would say that f and g are the same function, but Scheme
> appears to say no.
>

Well, here is a reason a human probably should not say that f and g
are the same function, as well.

The following block is the scheme-code for both f and g. Their code
are completely equivalent (of course), but may still contain different
data:

(lambda (x)
(lambda (y)
(set! x (+ y x))
x))


H.

unread,
Jan 14, 2006, 9:12:39 PM1/14/06
to

> Well, here is a reason a human probably should not say that f and g
> are the same function, as well.
>
> The following block is the scheme-code for both f and g. Their code
> are completely equivalent (of course), but may still contain different
> data:
>
> (lambda (x)
> (lambda (y)
> (set! x (+ y x))
> x))

I don't believe this is actually a function in in the "functional
paradigm" sense, because of the use of set! From a mathematical
standpoint, a function must always return the same value for the same
input. Therefore, neither f nor g are functions.

Kjetil S. Matheussen

unread,
Jan 14, 2006, 9:18:12 PM1/14/06
to

Hmm, well, I'm not in a very philosophical mood right now, but both f and
g are functions that return the same value for the same input. Here is
what both f and g return, no matter what input they get:

Kjetil S. Matheussen

unread,
Jan 14, 2006, 9:23:41 PM1/14/06
to

Eh, I take that back. They both return a closure, of course. But scheme is
not a pure functional language, so I don't see your point. Please clarify
how you think...

--

Pascal Bourguignon

unread,
Jan 14, 2006, 9:54:38 PM1/14/06
to
Lauri Alanko <l...@iki.fi> writes:

> In article <1137287484....@z14g2000cwz.googlegroups.com>,
> H. <hbe...@gmail.com> wrote:
>> So I was thinking as EQ? as equivalent to == in Java.
>
> No, but you are wrong thinking of Java's == as equivalent to = in
> Scheme.
>
>> What kind of implementation details in EQ? prevent it from working
>> predictably with characters and numbers?
>
> In Scheme, numbers can be arbitrarily large, and big numbers are
> typically heap-allocated without interning, making it possible to have
> two numbers that have the same value (making = return #t) but
> different identity (making eq? return #f).

Which makes me think that a smart implementation could update boxed
numbers references when they're equal:

(define x (compute-some-boxed-number 1))
(define y (list (compute-some-boxed-number 1)))

(eq? x (car y)) --> #f
(= x (car y)) --> #t
(eq? x (car y)) --> #t ; one of x or (car y) would have been updated.

If the place updated is systematically the one with the bigger pointer
for example, then progressivelly (as they're ='ed) all instances of =
numbers will be reduced to one.


Bah! That couldn't be implemented without an additional indirection for:
(let ((a x) (b x)) (= a y) (eq? a b))
must return #t :-(


--
__Pascal Bourguignon__ http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.

Pascal Bourguignon

unread,
Jan 14, 2006, 9:58:53 PM1/14/06
to
"H." <hbe...@gmail.com> writes:

Depends if you consider mathematics or informatics.

Mathematically, for all x, (= (+ (* (cos x) (cos x)) (* (sin x) (sin x))) 1.0)

In computers, the negation is true:

There exist some x such as
(not (= (+ (* (cos x) (cos x)) (* (sin x) (sin x))) 1.0))

On the other hand, if you translate the mathematical formula
_correctly_ into a computer program you can still have, in computer:

(define epsilon 0.001)
for all x, (< (abs (- (+ (* (cos x) (cos x)) (* (sin x) (sin x))) 1.0)) epsilon)

(The _correctly_ part is in avoiding = to compare floating point numbers).


--
__Pascal Bourguignon__ http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may

H.

unread,
Jan 14, 2006, 11:56:18 PM1/14/06
to

> > Hmm, well, I'm not in a very philosophical mood right now, but both f and g
> > are functions that return the same value for the same input. Here is what
> > both f and g return, no matter what input they get:
> >
> > (lambda (y)
> > (set! x (+ y x))
> > x))
> >
>
> Eh, I take that back. They both return a closure, of course. But scheme is
> not a pure functional language, so I don't see your point. Please clarify
> how you think...
>

Upon further thinking about it, I don't know what the answer is. Just
ignore what I said above, please, because I'm not even sure it makes
sense to *me* anywhere. ;-o

Brian Harvey

unread,
Jan 15, 2006, 12:22:04 AM1/15/06
to
"H." <hbe...@gmail.com> writes:
>I was taught that these are the same /function/ but different
>/procedures/, and that the strict use of the word "function" concerns
>input and output values.

For purposes of this discussion, the most important point for you to
remember about functions vs. procedures is that there aren't any functions
inside the computer -- only procedures! We human beings may have a function
in mind when we write a procedure, but the computer doesn't have anything in
"mind" except a prescribed sequence of steps and variable bindings.

Since there aren't any functions inside the computer, it doesn't make sense
to ask the computer whether two of them are the same. We can only ask whether
two procedures are the same.

I think if you read the fine print in R5RS it'll tell you that in a perfect
universe, (eqv? (lambda (x) x) (lambda (y) y)) would be true, but in this
imperfect universe we can't even tell in advance whether a procedure is going
to halt or not, let alone whether it behaves the same as some other procedure.
So the behavior of EQV? for procedures is documented as a compromise with
ugly reality.

I suppose a sufficiently clever implementation could determine that *some*
pairs of procedures are equivalent, by the same kind of program analysis
people use to try to prove programs correct, but since it can't be done in
general, afaik nobody even tries for special cases.

As other subthreads have explained, numbers are the other messy case, because
of things like bignums and floats, and because different implementations
choose different optimizations of number storage.

You'll notice, btw, that there seem to be two schools of thought about
testing for identity: (1) always use EQV? and (2) never use EQV?. I'm in
the second camp, personally; I've never found a use for EQV?. But this is
partly because I grew up in the old days, when there were just EQUALP and
EQ (these question marks are a neologism), and my habits formed early.
I suspect the really right answer is "if you are in a situation in which
EQ? and EQV? might give different answers, don't use either of them, but
instead use some more specific equivalence predicate."

Joe Marshall

unread,
Jan 15, 2006, 1:44:51 AM1/15/06
to

You forgot symbols, which is the interesting case. (that is, Yes, I
do, on occasion encounter situations where I need to compare values
that are either numbers, characters or symbols, but not lists or
vectors, and I want `logical eq-ness' not `implementation eq-ness'.)

Yes, it is rare.

EQ? has an obscure screw case that EQV? doesn't have, so it makes sense
to use EQV? unless there is a compelling reason.

Nils M Holm

unread,
Jan 15, 2006, 3:21:20 AM1/15/06
to
Lauri Alanko <l...@iki.fi> wrote:
> For instance, in mzscheme, on a 64-bit platform:
>
> > (eq? (expt 2 61) (expt 2 61))
> #t
> > (eq? (expt 2 62) (expt 2 62))
> #f

An implementation may even choose to use bignum arithmetics all the
time, giving

(eq? 5 5) => #f

(My Sketchy interpreter does so.)

--
Nils M Holm <n m h @ t 3 x . o r g> -- http://www.t3x.org/nmh/

Marcin 'Qrczak' Kowalczyk

unread,
Jan 15, 2006, 9:36:29 AM1/15/06
to
"H." <hbe...@gmail.com> writes:

> eqv? is a little odd, in that it mostly asks question 1 but sometimes
> asks question 2.

It's not odd.

In languages which Scheme-like semantics (not just Scheme, e.g. this
applies to Python too) generally there are 4 kinds of types:

1. Immutable: consisting of computed immutable values.

Scheme: numbers, characters.

2. Atomic: consisting of explicitly named immutable values,
usually a small number of them.

Scheme: booleans, the empty list, symbols.

3. Mutable: consisting of compound values with mutable fields.

Scheme: vectors, strings, pairs, ports.

4. Functions (called procedures in Scheme).

For immutable types there is a well-defined concept of equality.
Typical implementations represent at least some of these values as
pointers to objects, but identity of these objects is irrelevant,
as long as they represent equal values. In Scheme EQV? and EQUAL?
compute this equality.

Atomic types have the same properties, except that the natural
implementation represents each value as a unique object, so object
identity is not ignored but coincide with value equality. In Scheme,
in addition to EQV? and EQUAL?, also EQ? compares these values; the
intent is that on most implementations it can be implemented faster.
Symbols are unusual in that they can also be computed rather than
named explicitly (string->symbol), but typical implementations use
a central dictionary of all symbols so they are unique too.

For mutable types there is equality based on returning a fresh object
from each invocation of the constructor and on sharing of mutations
(Scheme EQV?), which has a natural implementation based on object
identity (Scheme EQ?). We can also consider equality which ignores
sharing and looks at current values of fields or elements of the
objects. Fields themselves could be compared using various equalities.
Scheme has only EQUAL? which descends into elements using also EQUAL?.

For functions there is no good and computable notion of equality.
In Scheme all equality predicates applied for procedures compare just
the identity of the object.

In Scheme it's unspecified whether empty vectors and empty strings
belong to category 1 or 3.

--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

Alan Grover

unread,
Jan 17, 2006, 8:37:47 AM1/17/06
to
matteo d'addio 81 wrote:

>
> Jens Axel Søgaard ha scritto:
>
>> > (eq? 'a (string->symbol "a")) ==> #t
>>
>> This is due to "interning" of symbols. All symbols
>> are kept in a table. If you make a symbol that already
>> exist in the system, a pointer to the same box as last
>> is returned. Thus determining whether two symbols are
>> the same symbol is just one pointer comparison.
>>
>
> I was playing with string->symbol and I found that
>
> (eq? 'hello 'Hello) gives #t
> (eq? 'hello (string->symbol "hello")) gives #t and
> (eq? 'hello (string->symbol "Hello")) gives #f but
> (eq? 'Hello (string->symbol "hello")) gives #t and
> (eq? 'Hello (string->symbol "Hello")) gives #f
>
> It seems that if a string contains an uppercase letter
> a box is created, otherwise not. Is it for making possible
> to reconvert back the symbol to the original string?

I believe your conclusion is wrong. According to your hypothesis, this would
give #f:

(eq? (string->symbol "Hello") (string->symbol "Hello"))

And I suspect you'll get #t.

I suspect that your REPL is canonicalizing symbols to lower case. When you
explicitly ask for "string->symbol', it does not canonicalize.

Aha: R5Rs says that would be the expected behavior. Specifically, "read"
canonicalizes to "the implementation's preferred standard case." Whereas
(symbol->string (string->symbol x)) is a case-preserving operation.

http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-9.html#%_sec_6.3.3
(see symbol->string and string->symbol, and the examples with them).

Reply all
Reply to author
Forward
0 new messages