2019-10-08 12:27:35 +00:00
|
|
|
---
|
|
|
|
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.
|
|
|
|
|
2022-06-18 17:11:08 +00:00
|
|
|
This document specifies canonical form for the Preserves [machine-oriented
|
|
|
|
binary syntax](preserves-binary.html).
|
2019-10-08 12:27:35 +00:00
|
|
|
|
2020-12-28 22:25:02 +00:00
|
|
|
**Annotations.**
|
2019-10-09 14:58:02 +00:00
|
|
|
Annotations *MUST NOT* be present.
|
2019-10-08 12:27:35 +00:00
|
|
|
|
|
|
|
**Sets.**
|
2019-10-09 14:58:02 +00:00
|
|
|
The elements of a `Set` *MUST* be serialized sorted in ascending order
|
2020-12-28 22:25:02 +00:00
|
|
|
by comparing their canonical encoded binary representations.
|
2019-10-08 12:27:35 +00:00
|
|
|
|
|
|
|
**Dictionaries.**
|
2019-10-09 14:58:02 +00:00
|
|
|
The key-value pairs in a `Dictionary` *MUST* be serialized sorted in
|
2020-12-28 22:25:02 +00:00
|
|
|
ascending order by comparing the canonical encoded binary
|
|
|
|
representations of their keys.[^no-need-for-by-value]
|
2019-10-08 13:06:08 +00:00
|
|
|
|
|
|
|
[^no-need-for-by-value]: There is no need to order by (key, value)
|
|
|
|
pair, since a `Dictionary` has no duplicate keys.
|
2019-10-08 12:27:35 +00:00
|
|
|
|
|
|
|
**Other kinds of `Value`.**
|
2019-10-09 14:58:02 +00:00
|
|
|
There are no special canonicalization restrictions on
|
|
|
|
`SignedInteger`s, `String`s, `ByteString`s, `Symbol`s, `Boolean`s,
|
2021-05-17 12:54:06 +00:00
|
|
|
`Float`s, `Double`s, `Record`s, `Sequence`s, or `Embedded`s. The
|
2021-04-24 20:01:53 +00:00
|
|
|
constraints given for these `Value`s in the [specification][spec]
|
|
|
|
suffice to ensure canonicity.
|
2019-10-08 12:27:35 +00:00
|
|
|
|
|
|
|
<!-- Heading to visually offset the footnotes from the main document: -->
|
|
|
|
## Notes
|