Subject: RE: Last Call: <draft-bormann-cbor-04.txt> (Concise Binary Object Representation (CBOR)) to Proposed Standard

From: Larry Masinter <[email-masked]>
Date: Mon, 19 Aug 2013 03:18:11 -0700

>>> parsers need to canonicalize maps to any depth in order to
>>> detect duplicates. This is "complex" by any definition of the word.

It isn't complex in terms of computational efficiency ... you can canonicalize in O(N log N) and do it while reading.
And the consequence of not using structure-equality in duplicate detection is complex.

> I think CBOR should be clear about how it handles sharing and equality.
agree. 

Larry
--
http://larry.masinter.net

(obscure footnote: Serializing structures with duplicate pointers is fun, you need some notation to signify back pointers and to drop anchors. Using hash tables and canonical values was part of the circlprint/hprint http://pdp-10.trailing-edge.com/decuslib20-01/01/decus/20-0004/21lisp.tty.html implementation.)

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 19 Aug 2013 09:29:20 -0400

On Mon, Aug 19, 2013 at 6:18 AM, Larry Masinter <[email-masked]> wrote:

> It isn't complex in terms of computational efficiency ... you can
> canonicalize in O(N log N) and do it while reading.

I don't see a need to declare them as maps at all.

In any data encoding / pickling type scheme there is data that is put out
on the wire and there is additional information which is needed to make
sense of it. Some encoding formats have more of the latter than others but
there is no schema language that is rich enough to completely express the
semantics of the messages so there is always some additional data.

JSON has a number of design choices that mean that there is rather more
additional information that needs to be added in than in XML or ASN.1. JSON
conflates lists and sets for example. It does not require data to be
serialized in a particular order. But this is not a problem as there is no
particular need to have that information on the wire. Sets, lists, bags,
arrays can all be expressed as lists as LISP demonstrates quite well.

These map encodings are essentially just a function definition which can be
represented as an array of 2-tuples with an additional constraint that the
mapping be a surjection (many to one). This is exactly how a surjection is
defined in Z.

Why force the constraint that the mapping be a surjection into the encoding
format? Why fetishize just surjections, what about bijections?

I much prefer the JSON approach. The only reason to need a fully self
describing data structure in a protocol is for debugging. And you don't
need a lot of structure information to make sense of the data.

There is a better case for an extensive schema in an encoding format for
experimental data and the like or for a document format. Dumping the schema
or the like into each file is polite. But that could just as easily be done
by reserving a tag for 'meta data follows, may be ignored'.

-- 
Website: http://hallambaker.com/