-2

tl;dr - I've settled on the terminology Traversable for the container type which includes List and Dict but excludes str, and Atom for anything which is not traversable, e.g. cannot nest indefinitely. This makes the top-level type signature of json.loads something like Union[Traversable, Atom]. I still need to figure out the correct recursive definition, but that's a much more tightly scoped problem.

However, this question has been locked so I cannot add this as an answer.


I'm trying to define the type signature of a bunch of methods which operate on nested containers. Basically, what is the 'shape' of a container which is composed of dicts and lists, as well as primitives (including iterables which cannot nest, such as str). I can call the latter Atom, since it cannot be decomposed indefinitely. In other words, what is the common interface of dict and list? It's not Iterable, because that includes things like str, bytes, and other iterators which aren't containers (like infinite generators).

I am wondering if there is a terminology for the container data structure "isomorphic" to valid JSON, in other words, each item is one of:

  • array/list
  • object/dict/mapping
  • leaf: something really easy to serialize, like a string, number, boolean, or null. Complex data types e.g. images don't count.

JSON is built on two structures:

  • A collection of name/value pairs. In various languages, this is realized as an object, record, struct, dictionary, hash table, keyed list, or associative array.
  • An ordered list of values. In most languages, this is realized as an array, vector, list, or sequence.

I'm not looking for any particular serialization format, document type, or whatnot. I'm trying to get at "what is the name of the abstract thing which is the union of the two data structures named above".

Constraints: Lists are ordered and indexed by an integer. Objects are unordered and indexed by keys. Leaves/Keys must be strings or have a "stringer interface".

So, anything which could readily implement a .to_json() interface, e.g. JSON.stringify (js) or json.dump (python). But also most Protobuf messages would fit this criteria. If it were just a dict/object, I'd call it a mapping, or if it were just a list/tuple/array, I'd call it that. But this thing is a mixture of lists, dicts, and primitives.

Why? Because I use this interface in my line of work constantly, and I don't have a satisfying name for it. Again, quoting Douglas Crockford:

These are universal data structures. Virtually all modern programming languages support them in one form or another. It makes sense that a data format that is interchangeable with programming languages also be based on these structures.

Yet we don't have a name for the combined data structure.

I feel like this is a valuable abstraction to talk about, but it'd be inaccurate to call it "a JSON", since it doesn't really have to do with the JSON RFC, that's just a concrete implementation of this thing. Other valid impls are an object in JS, a dict in Python, some kinds of structs in Go, a protobuf message on the wire, a msgpack, etc. Yes you can technically serialize anything, but like, this structure implies not having to call any dedicated serializer on the leaves. A bitmap, a set, a numpy array, etc wouldn't count as valid leaves, without some massaging.

"Nest" perhaps? Naming things is hard.

9
  • 3
    Why does there need to be a name for this very specific kind of thing? Why does this version where arrays and key/value pairs are grammatically distinct entities get a name, while something that does the same thing but has no grammatical distinction between arrays and key/value pairs does not? Sep 23 '20 at 17:02
  • 3
    "Why does "monad" get a specific name?" Because it's a vital tool of composition in functional programming. JSON is just... a text format. A useful one yes, but it's specific peculiarities are not so widespread that it needs a name. If you don't feel that's the case, show some examples of widely-used text formats that have everything JSON does, but aren't JSON itself. Sep 23 '20 at 17:56
  • 1
    A monad is a thing that can be used in a very specific way; the name represents the way in which it can be used. You can't use all of "Protobuf, msgpack, cap'n proto, dataclass, argparse.Namespace, ROS messages, many types of interface{}." in the same way. A function which operates on data from argparse for example cannot be passed data directly from a JSON parser, nor a Protobuf, etc. Giving these things a single name would not in any way allow interop APIs between them. Monad defines the behavior of an interface; the only commonalities between these things are purely conceptual. Sep 23 '20 at 21:15
  • 3
    I'm not convinced the things you're listing have as much in common as you think they do. You place constraints on the leaf values, but in some languages, there is no boolean type, and in some serialisation formats all leaves are strings, so would they be covered by this name? Conversely, in some serialisation formats, number representations have an explicit precision; others have direct support for references, which JSON lacks. Ultimately, these are just "structured types", with widely varying constraints of which Crockford picked a set based on his favourite language.
    – IMSoP
    Sep 23 '20 at 21:42
  • 5
    I can see what connects them - they're all multi-dimensional structured types. What I'm not seeing is a universal set of constraints within that - Crockford's assertion is precisely that his definition is sufficiently general to cover a large range of structures, not that it's constraints are universally agreed. A record with pre-defined fields is not the same as a map of arbitrary key-value pairs; and an ordered list of integers is not the same as a collection of complex objects. JSON can represent all of the above, as can other serialization formats.
    – IMSoP
    Sep 24 '20 at 11:46
4

It’s called a JSON document. JSON has restrictions like numbers cannot be Infinity or NaN, but they can be have large numbers of decimals. How you implement it is up to you.

There are plenty of different data structures with slightly different or very different rules. For example, MacOS property lists are very similar to JSON documents, but not exactly the same.

3

I think the only term that covers all the cases you list would be something broad like "composite type", or "collection", perhaps clarifying that it should be multi-dimensional. Some of the constraints you place on the format aren't imposed by your examples, and other constraints not listed are imposed by some not others.

Consider that a common way of defining a type is by listing both the constraints on allowed values, and the available operations.

Let's look at the map / dictionary part in a few of the examples you've given:

  • JSON has unbounded ordered lists where the keys cannot be defined, and dictionaries with string keys which can be interpreted as ordered (since it's a serialization format, not a data model)
  • an object in JS explicitly does not have ordered keys
  • a dict in Python can have keys of any "hashable" type, including tuples; entries have a defined order
  • a protobuf message on the wire does not allow arbitrary key-value pairs as an intrinsic type, since all key names are part of the format definition; defining a "map" type is sugar for defining a list of two-value tuples, and is constrained not to contain other maps

Certainly, these types have things in common, leading to Crockford's assertion that there is some "universal" concept underpinning them, but the details vary wildly. If we expand our survey to also look at the available list/array types, and the "leaf" types that these structures allow, we'll end up with a long list of differing restrictions.

We could pick some set of common features - as serialization formats do - and emulate others - as encoders and parsers do - but we would have to make some arbitrary decisions, and come up with a name for our decisions.

If we don't do that, where do we draw the line - you say you would exclude sets, but it's not obvious why that should be excluded, but both ordered dictionaries and fixed-key structs should be included - particularly since a set can be trivially converted to a list.

3
  • Best answer so far. I think the Protobuf-on-wire is the biggest stretch, I may be pushing the abstraction too far there. Something along "Structured Type" definitely has the right feel I'm looking for. I think another way of expressing what I'm trying to drill down to would be the python type Union[Union[List, Tuple], Mapping]. Sep 24 '20 at 16:16
  • "Multi-dimensional structured type" doesn't Google, so I call shenanigans. We're just making up words now. The closest thing I found was Multidimensional Structure Array; is that the term you're looking for? Sep 24 '20 at 17:18
  • 1
    @RobertHarvey You're right, "composite type" is what I was actually thinking of, and I meant "multi-dimensional" as just a plain adjective, not a part of the jargon term. I've re-worded.
    – IMSoP
    Sep 24 '20 at 17:30
2

If we wanted an official name for this in relation to JSON, we would need to look to Douglas Crockford's original description on JSON.org or the official standards ECMA-404, or RFC 8259.

The closest JSON.org comes is this:

JSON is built on two structures:

  • A collection of name/value pairs. In various languages, this is realized as an object, record, struct, dictionary, hash table, keyed list, or associative array.
  • An ordered list of values. In most languages, this is realized as an array, vector, list, or sequence.

Similarly, RFC 8259 says:

JSON can represent four primitive types (strings, numbers, booleans, and null) and two structured types (objects and arrays).

It does come close by defining the term "JSON value" as part of the grammar:

A JSON value MUST be an object, array, number, or string, or one of the following three literal names:

  • false
  • null
  • true

But note that "object" and "array" here refer to other tokens in the grammar, not data structures per se.

Unlike, for instance, XML, JSON is not specified in terms of an abstract model which is then serialized; rather, JSON is explicitly a serialization format intended to map to differing internal representations. This is spelled out in ECMA-404 thus:

The goal of this specification is only to define the syntax of valid JSON texts. Its intent is not to provide any semantics or interpretation of text conforming to that syntax. It also intentionally does not define how a valid JSON text might be internalized into the data structures of a programming language. There are many possible semantics that could be applied to the JSON syntax and many ways that a JSON text can be processed or mapped by a programming language.

Since there is no official restriction on what data structures can be serialized to JSON, there can be no official name for that restricted set.

2
  • If it helps clarify things, I care more about the idea of the abstract model vs the actual serialization. Sep 23 '20 at 20:32
  • 1
    @DeusXMachina Right, but like I say in the answer, there is no abstract model, there's whatever each language or library decides is the closest idiomatic fit or the most useful in context. In PHP, for instance, the "array" data type can hold the result of unserializing any JSON string; but you could also map JSON objects to generic PHP objects; or, you could use a convention within the JSON string to indicate specific class names. That flexibility has been part of the appeal of JSON from day one.
    – IMSoP
    Sep 23 '20 at 21:31
0

What you're talking about is basically JSON document object model (i.e. DOM), or sometimes just object model. When people talk about DOM, they usually talk about XML's because XML invented/popularised the term for the abstract representation of a serialisation format. However, while not as widespread as XML DOM, from time to time you see the term used for other formats as well in limited contexts, e.g. 1, 2, 3, often in languages that don't actually have dict/list as native data types. Indeed, the term DOM itself is used in XML because most programming languages don't have a straightforward mapping between their built-in data types and XML.

However, you really can't divorce the JSON DOM (or any other such abstract representation) from their respective serialisation format. While there are plenty of serialisation formats that have superficially similar DOM to JSON, they are all slightly different and they are not interchangeable. Some formats differs in what kind of floating point edge cases (e.g. NaN, negative zeros) they are allowed to store, some only permits strings as scalar data type, some extends the list of basic data types (e.g. date/time in TOML), some allows recursive/cyclic data (e.g. YAML references), some allows recursive scheme but not recursive data (e.g. Protobuf), some requires that the top level object just be of specific type (e.g. TOML). The devil is in the details.

All these little variants makes a single, non-serialisation specific term not very useful for communication, and why such a term is unlikely to be universally accepted.

7
  • 1
    DOM has a really specific connotation though. Sep 24 '20 at 17:16
  • @DeusXMachina: all technical terms have very specific connotations that people who aren't familiar with the jargon would unlikely get or understand the specifics, even if the jargon is based on a more widely accepted term. If you're writing a book/documentation/library/company jargon or whatever where you need such a term, just pick the term you like best and define what you mean when you used the term in the document. Ultimately, for linguistics purpose, words means whatever you used them for, and maybe one day a single term will catch on if enough people use the term the same way you do.
    – Lie Ryan
    Sep 24 '20 at 17:31
  • As I made clear in this answer, there is no single "object model" for JSON, it is explicitly and quite deliberately an abstract serialization of whatever the user wants to serialize. Any attempt to define a "JSON DOM" would be defining a completely new concept, and would not match how JSON is used in the real world.
    – IMSoP
    Sep 24 '20 at 17:32
  • @IMSoP: agreed, maybe I should have clarified that the JSON spec itself never used the term DOM anywhere. If you want to avoid associating too much with XML's DOM, I'd suggest using a variant like "object model" or "document model", which likely will invoke some sense of familiarity with XML DOM, while still avoiding the word "DOM" itself.
    – Lie Ryan
    Sep 24 '20 at 17:39
  • @LieRyan I wasn't talking about the term, I was talking about the concept itself - JSON is only a serialization format, and the specs go out of their way to avoid supplying any meaning whatsoever. For instance, RFC 8259 simply states "A JSON parser transforms a JSON text into another representation." - it places no constraints or even recommendations on what that other representation might be. So I think comparing any interpretation of JSON to the XML DOM would be misleading, because XML has very specifically defined semantics beyond its serialization format in a way that JSON does not.
    – IMSoP
    Sep 24 '20 at 18:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.