<p>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</p>

<pre><code>Collection A:    5 5 2 3 1 1 1 1
Collection B:    1 5 5 5 3 3 3 2
</code></pre>

<p>Are representationally unequal. But if you sort them and remove duplicates...</p>

<pre><code>Collection A:    1 2 3 5
Collection B:    1 2 3 5
</code></pre>

<p>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.</p>

<p>So no, they don't have to be representationally equal to be equal.</p>

CC BY-SA 4.0
2020-03-02T03:12:36.823Z
2020-03-02T03:12:36.823Z
ian.p.swift
<p>I had the same question as the OP about Lemma 1.1.</p>
<p>The definition of value was given as:
&quot;... a datum together with its interpretation&quot;</p>
<p>The definition of a value type being uniquely represented was: &quot;A value type is uniquely represented IFF at most one value corresponds to each abstract entity.&quot;</p>
<p>I interpreted the term 'value' in this definition to mean a datum together with <em>some</em> interpretation, not a datum together with one single interpretation. Especially since we learned later in the definition of ambiguous value types that values could have more than one interpretation.</p>
<p>In other words, the value could have the same datum with some other interpretation and correspond to another entity, but as long as that entity only had that value corresponding to it, the value type was still uniquely represented. So then when I read the lemma, it seemed to me that it was missing the fact that the value type also needed to be unambiguous for equality to imply representational equality.</p>
<p>So my answer is, I <em>think</em> there must be some logical implication in the definition of unique representation (that I overlooked) that the values corresponding to at most one entity only have one interpretation in the context of that correspondence.</p>

CC BY-SA 4.0
2024-08-17T17:03:09.933Z
2024-09-07T14:21:27.540Z
2024-09-07T14:21:27.540Z
julieb
<p>I have just started on the book <a href="http://elementsofprogramming.com/" rel="nofollow noreferrer">Elements of Programming</a> (2019) and after thinking about the definitions for <em>value types</em> in chapter 1, that in principle seem to link meaning (the <em>abstract entities</em> of a <em>species</em>) to a bit representation, I started wondering about the following quote (Section 1.2 "Values" p. 3):</p>

<blockquote>
  <p>Lemma 1.1 If a value type is uniquely represented, equality implies representational equality.</p>
  
  <p>Lemma 1.2 If a value type is not ambiguous, representational equality
  implies equality.</p>
  
  <p>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.</p>
</blockquote>

<p>With the definition of equality in the book being:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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 <em>and</em> 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.</p>

<p>I am probably nitpicking when reading that paragraph :)</p>

<books>
Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?
Araeos
# Regarding Elements of Programming, is a uniqueness of the value type sufficient for equality testing?

(Asked by: username_0 on 2020-02-14)

I have just started on the book [Elements of Programming](http://elementsofprogramming.com/) (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 :)

**Tags:** books


---

## 2 answers

### Answer by username_1 on 2020-03-02. Score: 1

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.


---

### Answer by username_2 on 2024-08-17. Score: 0

I had the same question as the OP about Lemma 1.1.

The definition of value was given as:
"... a datum together with its interpretation"

The definition of a value type being uniquely represented was: "A value type is uniquely represented IFF at most one value corresponds to each abstract entity."

I interpreted the term 'value' in this definition to mean a datum together with *some* interpretation, not a datum together with one single interpretation. Especially since we learned later in the definition of ambiguous value types that values could have more than one interpretation.

In other words, the value could have the same datum with some other interpretation and correspond to another entity, but as long as that entity only had that value corresponding to it, the value type was still uniquely represented. So then when I read the lemma, it seemed to me that it was missing the fact that the value type also needed to be unambiguous for equality to imply representational equality.

So my answer is, I *think* there must be some logical implication in the definition of unique representation (that I overlooked) that the values corresponding to at most one entity only have one interpretation in the context of that correspondence.


---

