= Unreduced rational representation
{title2=$\alpha(n,d)=n/d$}
Consider an original <abstract data type> whose values are <rational numbers>. Store an <ordered pair> $(n,d)$ of <integers>, interpreted as a <numerator> and a <denominator>. Use exact, unbounded <integer> <arithmetic> in this model. The storage space, <representation invariant> and <abstraction function> are
$$
R=\mathbb Z\times\mathbb Z,\qquad I(n,d)\iff d\ne0,\qquad R_{\mathrm{valid}}=\{(n,d)\in R:d\ne0\},\qquad \alpha:R_{\mathrm{valid}}\to\mathbb Q,\quad \alpha(n,d)=\frac nd.
$$
The <representation invariant> does not require a positive <denominator> or a <reduced fraction>. Consequently $(1,2)$, $(2,4)$ and $(-1,-2)$ are three different concrete states with the same abstract <rational number> $1/2$. Similarly, $(0,1)$ and $(0,-3)$ both represent zero. The <abstraction function> is a <surjection>: every <rational number> has an <integer> <numerator> and a nonzero <integer> <denominator>, so every abstract value has a representation.
\Image[/rational-abstraction-concrete-state-map.png]
{title=Several valid integer pairs represent one rational value; zero denominators have no abstract value}
Both $(1,0)$ and $(0,0)$ violate the <representation invariant>; neither has a value under this <abstraction function>. By contrast, $(2,4)$ is completely valid. Simplifying it to the <reduced fraction> $1/2$ may be a useful implementation choice, but is not a requirement of this representation. Strengthening the <representation invariant> to require a positive <denominator> and a <greatest common divisor> of one would choose a unique stored representative for each <rational number>; every constructor and operation would then need to establish that stronger condition.
Equality of abstract values is therefore different from equality of stored <ordered pairs>. For valid $(a,b)$ and $(c,d)$,
$$
\alpha(a,b)=\alpha(c,d)\iff ad=bc.
$$
This defines an <equivalence relation> on $R_{\mathrm{valid}}$: each <equivalence class> contains all representations of one <rational number>. An <API> equality operation can compare these cross-products using exact <integer> arithmetic. Comparing the two fields individually would incorrectly declare $(1,2)$ and $(2,4)$ unequal as <rational numbers>. The general reason is that an <abstraction function> may map several concrete values to one abstract value.<OCaml Programming: Correct + Efficient + Beautiful by Michael R. Clarkson and others/8.3 Module Documentation>[Section 8.3.1, Abstraction Functions: several concrete values mapping to one abstract value; Section 8.3.4, Representation Invariants: valid domain of AF]{ref}
Back to article page
