Jonathan S. Shapiro wrote:
Okay, this one is going to get fur flying!
It seems clear that for primary types (int32, char, and friends), the definition of (equals x y) should be obvious.
It seems equally clear that if S is a composite type, all of whose members consist of primary types, then two elements of type S are equal exactly if they are memberwise equal.
The introduction of mutability does not alter the above rules.
However...
Note that "tuple" is a reference type. What should
(equal? (tuple #\c) (tuple #\c))
return? If we say that reference type equality is based on identity, then the answer is #f. If we say that equality is defined by recursive memberwise equality, then the answer is #t.
I agree, they are functionally equivalent, but have distinct identities.
My feeling is that the language specification cannot decide this. There are compelling pragmatic examples where either interpretation of equality might be demanded. Given which, I am proposing that our primitive operations should be
equal? (recursive) structural equality
eq? identity equality, which is defined as value equality for primary types and identity for reference types
This does seem to capture the two distinct "equality" flavours I've encountered. However, I'd be inclined to drop the over-used "equal" terminology entirely and adopt more descriptive names:
equiv? equivalence, ie. (recursive) structural equality
ident? identity equality (or perhaps ref-eq? or ref-equiv?)
I'm uncertain whether identity is the same for two equivalent value types though. I believe the above two definitions are in keeping with your approach however, but their meaning is more explicit than the generic "equal" operator.
Note that equal? does not admit equality on lambda forms, but eq? *could* admit identity testing on closures. This would violate the expectation that
(implies (eq? x y) (equal? x y))
and I am therefore inclined to disallow it. Unfortunately, there is a problem if it is disallowed.
Consider implementation of a set of objects or a generic collection. In order to implement fast membership checks and a fast union operation, every object must have not just an equality check, but a magnitude check. If we want fast, generic collection implementations, we somehow need to address this, and it would be really nice NOT to pass a function pointer to a type-specific magnitude comparator function.
Theoretically, the size only needs to be extracted once for each typed collection, doesn't it? It's not so bad if that's the case.
So if I'm understanding the collections issue correctly, the problem is that you want one operator that can be used to check equality/identity/equivalence over both value types and reference types, but the above definitions lend themselves to:
Membership checks for ref types: (ident? item tofind)
Membership checks for value types where each tracked item is "boxed": (equiv? (deref item) tofind)
Membership checks for value types tracked by copy: (equiv? item tofind)
I can't think of a general solution to this issue that would be valid in every scenario.
This raises the following somewhat ugly question: do we need to support magnitude comparison on reference types? What about closures?
Isn't the magnitude of a reference type simply the magnitude of the pointer? The pointer is what is used in constructing types after all, so its contribution to the size of the constructed type is the size of the pointer.
Perhaps I'm just misunderstanding the use cases. How were you thinking these generic collections would store their values? Would each item be "boxed", or would each item be copied by value and held internally?
Sandro _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
