Subject: [Cbor] FW: CBOR-BIS Terminology Refinement : Maps vs Objects, etc…

From: Burt Harris <[email-masked]>
Date: Sat, 19 May 2018 00:13:50 +0000

I’ve opened this as an issue at https://github.com/cbor-wg/CBORbis/issues/25, but following Francesca’s advice, forward the topic to the ML as well…
Terminology Refinement: Maps, Objects, etc…

To enhance clarity and extensibility in CBORbis, it might be beneficial to adjust some of the terminology and
definitions used. For example, instead of the current draft's:

Major type 5: a map of pairs of data items. Maps are also called tables, dictionaries, hashes, or objects (in JSON)...

let's consider saying something less loaded, like:

Major type 5/PAIRS - an ordered sequence of zero or more key-value pairs<https://infra.spec.whatwg.org/#pair>...

This illustrates a number of shifts in wording and intent which I propose:

  *   It's simpler and less restrictive. For example, it does not prevent multimaps from being represented with a properly tagged 5/PAIRS data item. Multimaps can be quite useful (HTTP and CoAP protocol headers are multimaps), but it is reasonable to limit them as a tagged extension to CBOR (see below.)
  *   Terms like maps, tables, dictionaries, hashes and objects are .abstract concepts that further restrict allowed content of the 5/PAIRS major type, they are not synonyms for it. The details of how those abstract types behave is subject to some ambiguity, so it's better not to use them in defining the major type. CBOR tags can be used to identify which abstract type is intended.
  *   CBOR major types should be visually distinct from the abstract types because major type alone does not determine the abstract type of an item; tags can modify the abstract type. Consistently using both the major type numeric value and an associated name (in caps) would help make the difference clear.
  *   Saying 5/PAIRS is ordered simply reflects reality, in a CBOR byte stream they must be in some order, because it is a serialization format. Eliminating the key uniqueness requirement from the major type allows encoding more types, e.g. multi-maps.

However, it would still be desirable to define how an untagged 5/PAIRS acts behave with greater specificity. For example, to address the issue of key equivalence and canonicalization, it could be very useful for an UNTAGGED 5/PAIRS to adopt the ECMAScript/JSON object restrictions that keys be limited to unique numbers and text strings. Highly constrained environments may have trouble supporting anything more general, but that should not restrict the content of a tagged 5/PAIRS collection, which might allow for the use of a Map tag that could imply full flexibility of encoding non-string/number keys, while a Map tagged object might obey different key-equivalence and canonicalization rules, with greater overhead, for example the byte wise lexicographic order now proposed.

ECMAScript object Canonicalization Order

Modern ECMAScript objects are defined with some little-known behavior that could really help bring to some of the thorny canonicalization issues. ECMAScript objects are not hashes, their properties are ordered. But the order can surprise some people, the keys (in order) are:

  1.  Non-negative numbers keys in ascending order; followed by
  2.  Strings keys (including negative numbers) in the order they were added to the object;
  3.  ECMAScript Symbols (which themselves would have to be tagged in COBAR)

By adopting the above rule as a SHOULD for canonical objects (UNTAGGED 5/PAIRS), we gain several advantages:

  *   In CBOR based standards for constrained environments [e.g. CBOR Object Signing and Encryption (COSE)], standardized non-negative integer keys sort first. A highly constrained implementation of COSE might choose to interpret only the non-negative integer keys in ascending order and skip out when other key types are detected.
  *   Uniqueness constraints and canonical order of keys made up of other types becomes an application-level concern. However, applications that handle existing data in a some existing canonical order, should be automatic because the order is preserved.

Most if not all dynamic languages use the ordered map for object properties (rather than unordered) because it can lead to much better performance using JIT compiler technology. Modern versions of ECMAScript has a separate Map type (since ES2016) with capacity for a wider variety of keys (e.g. objects and arrays can be used as keys), but interestingly it chooses to define equality and uniqueness constraints for map types to be based on reference equality (identity), not value equality.

Mirroring ECMAScript's ordering and uniqueness constraint rules for untagged 5/PAIRS might impose some additional overhead in implementations in other languages, but for the common cases (key isa string and key isa non-negative-integer) it provides a fairly low overhead approach implementable in most (if not all) environments.

Defining the CBOR Data Model in common Web Infrastructure terminology

I would also like to propose defining the CBOR data model in terms familiar to web developers. For this purpose, the WHATWG Infrastructure Living Standard<https://infra.spec.whatwg.org/> includes useful set of definitons<https://infra.spec.whatwg.org/#index-defined-here> that include most of the concepts needed. Referencing that document informationally, and selectively copying some of the definitions we need into CBORbis seems appropriate with regard to clarity and intellectual property. For example, the abstract concepts of the pair<https://infra.spec.whatwg.org/#pair>, tuple<https://infra.spec.whatwg.org/#tuple>, and struct<https://infra.spec.whatwg.org/#struct> that may be useful for both CBOR and CDDL already exist there. Furthermore more frequently used terms such as string<https://infra.spec.whatwg.org/#string> and byte sequence<https://infra.spec.whatwg.org/#byte-sequence>, and the definitions there have been carefully vetted regarding security concerns, for example, excluding surrogate code points in UTF-8.

---

From: Carsten Bormann <[email-masked]>
Date: Sat, 19 May 2018 17:17:20 +0200

Hi Burt,

thank you for all your input to the CBORbis effort.  I’m all for cleaning up the terminology (as long as we don’t confuse existing users too much).  But what you are proposing here goes way beyond terminology.

Replacing maps with alists (association lists, i.e. sequences of pairs) would have been a valid choice in 2013, when CBOR was standardized.  We thought a lot about this, and in the end staying close to JSON won out over the additional flexibility alists provide.

So in the generic data model of CBOR, we have maps. We indeed serialize them as sequences of pairs.  But CBOR is not just a syntax for serialization, it also comes with a processing model (which is what enables generic decoders).  Here, generic decoders are free to lose the serialization order of incoming maps and to be confused by duplicate keys and drop some of the pairs.

Changing that would be a significant change to CBOR.  It is also not really necessary, as we already have the array type for sequences.  So an alist can be represented by an array where the even numbered elements are keys and the odd numbered ones are values.  (The disadvantage is slightly less coding efficiency as the argument is twice as much as for maps, and the possibility to encode an odd number of elements which can’t be mapped into pairs.  Not really big problems in the majority of cases.)

Of course I like programming environments that provide ordered maps, multimaps etc.  CBOR provides many ways to serialize these (and maybe we need a few more tags to be unambiguous in this space).  But major type 5 is about (unordered) maps, specifically.

Grüße, Carsten

> On May 19, 2018, at 02:13, Burt Harris <[email-masked]> wrote:
> 
> Major type 5/PAIRS - an ordered sequence of zero or more key-value pairs...
>  
> 
> 	• It's simpler and less restrictive. For example, it does not prevent multimaps from being represented with a properly tagged 5/PAIRS data item. Multimaps can be quite useful (HTTP and CoAP protocol headers are multimaps), but it is reasonable to limit them as a tagged extension to CBOR (see below.)
> 	• Terms like maps, tables, dictionaries, hashes and objects are .abstract concepts that further restrict allowed content of the 5/PAIRS major type, they are not synonyms for it. The details of how those abstract types behave is subject to some ambiguity, so it's better not to use them in defining the major type. CBOR tags can be used to identify which abstract type is intended.
> 	• CBOR major types should be visually distinct from the abstract types because major type alone does not determine the abstract type of an item; tags can modify the abstract type. Consistently using both the major type numeric value and an associated name (in caps) would help make the difference clear.
> 	• Saying 5/PAIRS is ordered simply reflects reality, in a CBOR byte stream they must be in some order, because it is a serialization format. Eliminating the key uniqueness requirement from the major type allows encoding more types, e.g. multi-maps.
> However, it would still be desirable to define how an untagged 5/PAIRS acts behave with greater specificity. For example, to address the issue of key equivalence and canonicalization, it could be very useful for an UNTAGGED5/PAIRS to adopt the ECMAScript/JSON object restrictions that keys be limited to unique numbers and text strings. Highly constrained environments may have trouble supporting anything more general, but that should not restrict the content of a tagged 5/PAIRS collection, which might allow for the use of a Map tag that could imply full flexibility of encoding non-string/number keys, while a Map tagged object might obey different key-equivalence and canonicalization rules, with greater overhead, for example the byte wise lexicographic order now proposed.
> 
> 	• Non-negative numbers keys in ascending order; followed by
> 	• Strings keys (including negative numbers) in the order they were added to the object;
> 	• ECMAScript Symbols (which themselves would have to be tagged in COBAR)
> 	• In CBOR based standards for constrained environments [e.g. CBOR Object Signing and Encryption (COSE)], standardized non-negative integer keys sort first. A highly constrained implementation of COSE might choose to interpret only the non-negative integer keys in ascending order and skip out when other key types are detected.
> 	• Uniqueness constraints and canonical order of keys made up of other types becomes an application-level concern. However, applications that handle existing data in a some existing canonical order, should be automatic because the order is preserved.
> I would also like to propose defining the CBOR data model in terms familiar to web developers. For this purpose, the WHATWG Infrastructure Living Standard includes useful set of definitons that include most of the concepts needed. Referencing that document informationally, and selectively copying some of the definitions we need into CBORbis seems appropriate with regard to clarity and intellectual property. For example, the abstract concepts of the pair, tuple, and struct that may be useful for both CBOR and CDDL already exist there. Furthermore more frequently used terms such as string and byte sequence, and the definitions there have been carefully vetted regarding security concerns, for example, excluding surrogate code points in UTF-8.
> _______________________________________________
> CBOR mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/cbor

---

From: Michael Richardson <[email-masked]>
Date: Sat, 19 May 2018 11:22:40 -0400

Carsten Bormann <[email-masked]> wrote:
    > So in the generic data model of CBOR, we have maps. We indeed serialize
    > them as sequences of pairs.  But CBOR is not just a syntax for
    > serialization, it also comes with a processing model (which is what
    > enables generic decoders).  Here, generic decoders are free to lose the
    > serialization order of incoming maps and to be confused by duplicate
    > keys and drop some of the pairs.

And, it's also, from what I understand, what JSON specifies, so even if we
were to change this behaviour, I think we'd still want a structure that maps
1:1 with JSON maps.

    > Changing that would be a significant change to CBOR.  It is also not
    > really necessary, as we already have the array type for sequences.  So
    > an alist can be represented by an array where the even numbered
    > elements are keys and the odd numbered ones are values.  (The
    > disadvantage is slightly less coding efficiency as the argument is
    > twice as much as for maps, and the possibility to encode an odd number
    > of elements which can’t be mapped into pairs.  Not really big problems
    > in the majority of cases.)

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Burt Harris <[email-masked]>
Date: Tue, 22 May 2018 02:49:02 +0000

Thanks Carsten,   

Your probably right, it might have been better for me to separate my terminology suggestions from the trickier issues like key uniqueness, ordering and normalization, but they _are_ interrelated as long as we use terms like "map"  to describe CBOR major types.    

Let's back up and start with an easy terminology suggestion:   Can we avoid the word "string"  in naming major types 2 & 3.   The reason is that different runtime environments have different concepts of "string", e.g. some storing 8-bit values, some not;  some immutable, others not;  some are case sensitive, a few not.   Using the term 'byte string' just adds confusion to the already tricky topic of text representation.   Does using short distinct tokens like 2/TEXT and 3/BYTES to represent CBOR  appeal to you?

More generally, let's choose naming conventions that distinguish between "kinds" of types:

  1. Syntax types: called major types in CBOR.   

  2. Semantic types.   I think this is what you are talking about when you say a "processing model", but to me that's where it gets tricky.  

  3. Abstract types, specific to a runtime environment.  Interfaces, generics, or abstract types, e.g. 
	- `IDictionary`, `IOrderedDictionary`, `ISortedDictionary`  (interfaces C#), 
	- ` Dictionary` and HashMap' (abstract classes java.util),
	- ` Map<K,V>`  and `Object` (interfaces in TypeScript)
	-  Abstract types may not have much relevance to CBOR, but are conceptually a little different from semantic types.

  4. Concrete types realizable in a particular runtime environment e.g. 
	- `Hashtable` in Java
	- `Map` and `Object` (classes in JavaScript)
	- `string` referring to text in most languages
	- These are clearly very relevant to CBOR, decisions to map from semantic type to concrete type.

The term "association list" is a great example of why separating terminology for these is important; in functional languages runtimes like LISP, Scheme, OCaml and Haskell, association lists are an immutable concrete type with runtime operations quite different from map/dictionary/object/hashtable of imperative programming languages.   So even though I know of association lists, I wouldn't want to overload the term as a name for major type 5.  I'd suggest eight consistent notations like: 0/UINT, 1/NEGINT, 2/BYTES, 3/TEXT, 4/SEQ, 5/PAIRS, 6/TAG, 7/OTHER benefits clarity of the spec without changing anything about how these codes are parsed under RFC7049.

When untagged 4/SEQ obviously is treated as an array, but with a leading tag might represent something else.   For example if prefixed with TAG 4, the major type 4 is interpreted as a 2-tuple representing a scalar rational number, not an array, right?     That is in my mind the difference between syntax types and semantic types.

I'll continue  the ordered vs unordered map matter in a separate thread...

-----Original Message-----
From: Carsten Bormann <[email-masked]> 
Sent: Saturday, May 19, 2018 8:17 AM
To: Burt Harris <[email-masked]>
Cc: [email-masked]
Subject: Re: [Cbor] CBOR-BIS Terminology Refinement : Maps vs Objects, etc…

Hi Burt,

Grüße, Carsten

> I’ve opened this as an issue at 
> https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgith
> ub.com%2Fcbor-wg%2FCBORbis%2Fissues%2F25&data=02%7C01%7C%7C0753eadb1b6
> a43d7951d08d5bd9ba046%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636
> 623398459354011&sdata=4l743mLDG02vI8SPziHgc9cT6ZWUoCs1Hi9i6yLjVoU%3D&r
> eserved=0, but following Francesca’s advice, forward the topic to the 
> ML as well… Terminology Refinement: Maps, Objects, etc…
>  
> To enhance clarity and extensibility in CBORbis, it might be 
> beneficial to adjust some of the terminology and definitions used. For example, instead of the current draft's:
> 
> 	• ECMAScript Symbols (which themselves would have to be tagged in 
> COBAR) By adopting the above rule as a SHOULD for canonical objects (UNTAGGED 5/PAIRS), we gain several advantages:
> 
> https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.
> ietf.org%2Fmailman%2Flistinfo%2Fcbor&data=02%7C01%7C%7C0753eadb1b6a43d
> 7951d08d5bd9ba046%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C6366233
> 98459354011&sdata=az0PbxxZ4zfyAxxlyOa%2BPUsIU%2B2JGBuFxjaNdnLZ8Ds%3D&r
> eserved=0

---

From: Burt Harris <[email-masked]>
Date: Sat, 26 May 2018 02:08:51 +0000

As I said before, I’d like to disavow any reading of my earlier suggestion that the ordered/unordered semantics change of major type 5 change for the purpose of this thread.   That should be a separate conversation from this one on terminology.     Any perception I’m trying to redefine CBOR is simply a bug in my own writing down thoughts on improving CBOR terminology.

I am in agreement with Jeffrey Yasskin on one point: the current names of the major types aren’t a _big_ problem, but that doesn’t mean they can’t be _improved_ in the CBOR-BIS document.    My motivation for suggesting terminology changes is specific confusion I’ve actually seen in communications between experienced developers about CBOR, particularly developers of diverse backgrounds but who are experienced in data serialization and knowledge representation.

The notation changes I’ve suggested for major types are NOT for the benefit of a newcomer reading the document, yet obviously they SHOULD NOT confuse a newcomer, nor should they seem a big deal to anyone familiar with CBOR through RFC 7049.
An example of confusing based on current terminology:  in an e-mail exchange with an experienced CBOR implementor, he said something that didn’t make sense to me:

  *   However, keep in mind that it doesn't matter whether JSON has a text string type or not - the question here is whether it is permissible to convert JSON strings into CBOR binary strings, and the answer is obviously that it is permissible, at least by IETF standards.

Without naming him, I respect the author’s intent in saying it, but I can’t agree in detail.    Here’s my logic for wanting CBOR-BIS to unambiguously make his statement false:

  1.  JSON text is encoded as UTF-8 (default), UTF-16 or UTF-32.   (RFC 7159, section 8.1, clarified in RFC 8259 section 8.1)
  2.  JSON strings are composed entirely of Unicode characters (RFC 8259 section 8.2)
  3.  CBOR major type 2 is for bytes, without any implied encoding. (RFC 7049, section 2.1.)
  4.  CBOR major type 3 is for UNICODE text encoded as UTF-8. (RFC 7049, section 2.1.)
  5.  CBOR treats JSON text is a sequence of characters, not encoded bytes (RFC 7049, section 4, confirming #2 above.)

IETF standards are generally very specific about things like character encodings.  Yet an experienced CBOR developer is telling me it’s perfectly OK to lose the character encoding information by converting JSON strings as CBOR binary strings.   (Now if the CBOR binary string were preceded by a tag (major type 6) indicating a specific character encoding, such as ISO/IEC 8859-1:1998, I could accept the argument, but we don’t have such string encoding tags specified yet.)   It may seem a small point to a person working in some specific programming language, but when international and polyglot concerns are taken into effect, loosing character encoding information is a very bad thing, but I think he overgeneralized because of his language background

So, after substantial reflection, I understand why the original author said what he did: he was thinking in terms of a venerable old language: Perl 5.   (Perl is so old, it predates Unicode.)   The problem in Perl is there are no native binary (bytes) type, but it’s a common practice to store binary data in “strings”.   The Perl language CBOR-XS package offers a configurable option on how to encode Perl strings in CBOR, and the default setting to encoding Perl strings as 2 rather than 3.   To a Perl programmer, strings are a place to store either.    This sort of confusion would be reduced by eliminating “string” from the names of the major types.

For non-ASCII cases, character encoding matters, but often overlooked in simple examples.  I think the euro currency sign (JSON “\u20a0”) is a good example.   It SHOULD be encoded as CBOR hex 63 E2 82 A0, because U+20A0 is in UTF-8 E2 82 A0. It SHOULD NOT be encoded as CBOR hex 61 80, nor 41 80, even though hex 80 has been assigned to the euro currency sign is hex 80 in a commonly used code page.

The “Map” term for major type 5 is can be similarly filled with conflicting nuance across a polyglot community.    Some programming environments have a very specific interpretation of Map which may not match those of CBOR.   For example, modern ECMAScript specifications and JavaScript implementations have a native Map type that (like CBOR) supports non-primitive keys (like an array).   Problem here is that but unlike RFC 7049, a JavaScript Map does not attempt to define value-equality of such non-primitive keys, setting instead for object identity equality.

Terminology wise, selecting a platform-neutral term with minimal implied meaning for the existing semantics of message 5,  I still suggest “PAIRS” is better than “Map” for the same reason I’d like to use “BYTES” instead of “byte string”.  The lexical convention of writing each major type numeric value with both a number and mnemonic is to further distinguish the words like UNICODE in text from usage as a major type.    Thus combining other feedback, I’ll update my suggestions to:

                0/UNSIGNED

                1/NEGATIVE

                2/BYTES

                3/UNICODE

                4/ITEMS

                5/PAIRS

                6/TAG

                7/OTHER

This: a) avoids abbreviations in the abbreviations in mnemonics, and b) uses proper singular/plural casing.   I’m not particularly happy with 4/ITEMS, and only updated it from 4/SEQ to address the consistency point, anyone have a better idea?

---

From: Thiago Macieira <[email-masked]>
Date: Tue, 29 May 2018 07:07:06 -0500

On Friday, 25 May 2018 12:55:15 CDT Jeffrey Yasskin wrote:
> FWIW, I don't think the names of the major types are a significant problem
> in newcomers (which I was a year ago) understanding their meanings.
> 
> While "string" would be ambiguous, "byte string" and "text string" are
> pretty clear about their meanings. The remaining ambiguity is about the
> encoding of a "text string", for which "utf-8 string" would be more
> precise, but I don't think this is a big problem. Programmers are used to
> having to look up which encoding(s) strings have in any particular
> language.

I tend to agree here. One of the reasons to use "string" in "byte string" is 
that low-level programmers (C and C++) are used of thinking of strings as an 
arbitrary sequence of bytes. Even the C++ type std::string is used like that, 
despite having some text-like functions.

On the other hand, whenever we see "text", we think of human text, not 
arbitrary bytes. And more often than not, there's an association with Unicode. 
It's just a question of which of the UTFs is the one in use.

So by contrasting to "text string", it's clear what "byte string" means.

-- 
Thiago Macieira - thiago.macieira (AT) intel.com
  Software Architect - Intel Open Source Technology Center

---

From: Thiago Macieira <[email-masked]>
Date: Tue, 29 May 2018 07:18:34 -0500

On Friday, 25 May 2018 21:08:51 CDT Burt Harris wrote:
> Without naming him, I respect the author’s intent in saying it, but I can’t
> agree in detail.    Here’s my logic for wanting CBOR-BIS to unambiguously
> make his statement false:
> 
> 1) JSON text is encoded as UTF-8 (default), UTF-16 or UTF-32.   (RFC 7159,
> section 8.1, clarified in RFC 8259 section 8.1)

Note that it's not just JSON strings you're talking about here. It's the 
entire JSON document. In other words, the encoding for "true" is 
	U+0074 U+0072 U+0075 U+0065

And that gets transformed into either 4 bytes in UTF-8, 8 bytes in UTF-16 or 
16 bytes with UTF-32. This wasn't a string.

> 2) JSON strings are composed entirely of Unicode characters (RFC 8259
> section 8.2) 
> 3) CBOR major type 2 is for bytes, without any implied encoding. (RFC 7049,
> section 2.1.
> 4) CBOR major type 3 is for UNICODE text encoded as UTF-8. (RFC 7049,
> section 2.1.)
> 5) CBOR treats JSON text is a sequence of characters, not encoded bytes (RFC
> 7049, section 4, confirming #2 above.)

If you put a JSON document inside a CBOR Text String, which requires UTF-8, 
you're expected to encode it in UTF-8, even if the source was UTF-16 or 
UTF-32. This transformation is lossless.

If you need to guarantee byte-level fidelity of your payload so, for example, 
you can validate a checksum or signature, you really want a CBOR Byte String, 
not a Text one. By placing your JSON document -- even if the original was 
UTF-8 encoded -- in a CBOR Text String and tagging it with one of the JSON 
descriptors, an intermediary could reprocess it and transform somehow, like 
sorting the keys in all JSON objects. This would destroy your ability to 
perform the signature checking, even if the semantics of the data were 
actually preserved.

> IETF standards are generally very specific about things like character
> encodings.  Yet an experienced CBOR developer is telling me it’s perfectly
> OK to lose the character encoding information by converting JSON strings as
> CBOR binary strings.   (Now if the CBOR binary string were preceded by a
> tag (major type 6) indicating a specific character encoding, such as
> ISO/IEC 8859-1:1998, I could accept the argument, but we don’t have such
> string encoding tags specified yet.)   It may seem a small point to a
> person working in some specific programming language, but when
> international and polyglot concerns are taken into effect, loosing
> character encoding information is a very bad thing, but I think he
> overgeneralized because of his language background

I think this is a matter for a higher-level decision. If your protocol needs 
to transport extra metadata such as the encoding associated with your bag of 
bytes, you should provide it in a field. It is probably a good idea to have a 
few tags for some common encodings, but your protocol should be designed to 
carry that in a text field of its own, as the encoding could be one for which 
there's no corresponding tag.