preserves/canonical-binary.md

---
title: "Canonical Form for Binary Syntax"
---

  [spec]: preserves.html

When two `Value`s are written down in *canonical form*, comparing
their *syntax* for equivalence gives the same result as comparing them
*semantically* according to the equivalence defined in the
[Preserves specification][spec].[^equivalence-not-ordering]

  [^equivalence-not-ordering]: However, canonical form does *not*
    induce a match between lexicographic ordering on syntax and
    semantic ordering [as specified][spec]. It *only* induces a
    connection between equivalences.

That is, canonical forms are equal if and only if the encoded `Value`s
are equal.

This document specifies canonical form for the Preserves compact
binary syntax.

**General rules.**
Streaming formats ("format C") *MUST NOT* be used.
Annotations *MUST NOT* be present.
Whenever there is a choice between fixed-length ("format A") or
variable-length ("format B") formats, the fixed-length format *MUST* be
used.

**Sets.**
The elements of a `Set` *MUST* be serialized sorted in ascending order
following the total order relation defined in the
[Preserves specification][spec].

**Dictionaries.**
The key-value pairs in a `Dictionary` *MUST* be serialized sorted in
ascending order by key, following the total order relation defined in
the [Preserves specification][spec].[^no-need-for-by-value]

  [^no-need-for-by-value]: There is no need to order by (key, value)
    pair, since a `Dictionary` has no duplicate keys.

**Other kinds of `Value`.**
There are no special canonicalization restrictions on
`SignedInteger`s, `String`s, `ByteString`s, `Symbol`s, `Boolean`s,
`Float`s, `Double`s, `Record`s, or `Sequence`s.

<!-- Heading to visually offset the footnotes from the main document: -->
## Notes