I have just started on the book Elements of Programming (2019) and after thinking about the definitions for value types in chapter 1, that in principle seem to link meaning (the abstract entities of a species) to a bit representation, I started wondering about the following quote (Section 1.2 "Values" p. 3):

Lemma 1.1 If a value type is uniquely represented, equality implies representational equality.

Lemma 1.2 If a value type is not ambiguous, representational equality implies equality.

If a value type is uniquely represented, we implement equality by testing that both sequences of 0s and 1s are the same. Otherwise we must implement equality in such a way that preserves its consistency with the interpretations of its arguments.

With the definition of equality in the book being:

Two values of a value type are equal if and only if they represent the same abstract entity. They are representationally equal if and only if their datums are identical sequences of 0s and 1s.

Doesn't this imply, that implementing equality by testing for representation equality is impossible for ambiguous value types? If that is the case, shouldn't the book require a value type to be uniquely represented and unambiguous, in order to implement equality? If a given value type is ambiguous, one could resolve the ambiguous-ness per contract, such that the comparison checks for equality under the assumption that the passed parameters are never ambiguously refer to different abstract entities, though that would probably not be enforceable at all.

I am probably nitpicking when reading that paragraph :)


Looking at the book, they give a really good example where representational equality doesn't imply equality. You have two unordered collections, which are equal if after sorting and removing duplicates, they are representationally equal. For example

Collection A:    5 5 2 3 1 1 1 1
Collection B:    1 5 5 5 3 3 3 2

Are representationally unequal. But if you sort them and remove duplicates...

Collection A:    1 2 3 5
Collection B:    1 2 3 5

And are now representationally equal. In this sense, they're originally representationally unequal, for the sake of easier processing perhaps. However, once you perform the operation which determines equality, they are indeed equal.

So no, they don't have to be representationally equal to be equal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.