Part of a series of posts explaining programming for the lay-person.
This is part of a series of posts; see the introduction to this series. This post builds on the idea of types and extends last week’s discussion of user-defined types and contiguity. and pointers.
Last week I discussed a little about pointers and contiguity and how data can be represented inside the computer. It is quite common for programmers to go for extended periods of time without thinking about these details at all. Instead, it is common to think about an abstraction of data structures that captures how we plan to use them rather than how they are implemented internally. Thus, it is common to talk about “numbers” instead of “64-bit IEEE 754-compatible floating-point”. The later term matters sometimes, but when we can ignore it we do.
An abstract data type is the combination of some storage and several subroutines that interact with that storage to achieve particular properties. For example, I might define “vehicle” as having embark, disembark, accelerate, decelerate, and turn methods; car and airplane might then be concrete realizations of this abstract data type. The actual steps required to disembark from a plane and a car are quite different, but for most uses we can treat it at the higher abstract level.
Over the past several decades four abstract data types have taken over a large portion of the programming world. These are number, string, list, and associative array. Numbers are pretty obvious; strings are text, ordered sequences of characters or glyphs; lists are ordered sequences of anything else; the only one that needs much discussion is associative arrays.
An associative array AAs are also called a map, dictionary, or table (amongst other names) is a set of pairs of values. One element of each pair is called the key and the other the value of that key. We say that the associative array maps a key to a value. Some mathematicians write “x maps to y” as x ↦ y. The methods attached to an associative array are to set and retrieve the value associated with a particular key.
Associative arrays are a common way for humans to organize information. Dictionaries map words to definitions. Phone books map names to telephone numbers. Libraries map call numbers to books. Sounds are mapped to words in speech.
It should be noted that, in general, associative arrays are one-way. That is to say, it is easy to find the definition of a word but hard to find the word of a definition. Partly this is just a matter of choice: we could have made a reverse telephone book just as easily as a forward telephone book. But it can also be a matter of necessity: I can easily look up a word in a dictionary, but looking up a definition is quite a bit harder because it’s not obvious how to put a definition “in alphabetical order”.
There are a lot of ways to implement associative arrays, each with its own benefits and difficulties. But again, the abstraction of the data type means that you don’t usually need to care how it was implemented.
JSON is an acronym for Javascript Object Notation. Mostly independent of the javascript language, it is a notation for the four most common abstract data types.
Numbers are, well, numbers: 3, 54.2, etc.
Strings are anything in double quotes: "hi", "1, two and 3", etc.
Lists are comma-separated things in square brackets: [1, 2], ["a", 7.3, [1, 2], []], etc.
Associative arrays (called “objects” in JSON terminology)
are bounded by curly braces and use colons to separate key and value:
{"x":3, "y":"you", "a":{"":0, " ":1}}, etc.
In official JSON there are a few other rules:
all keys must be strings, true and false are values for a boolean type, etc.
However, these rules are not universal in other near-JSON languages, such as Python.
Associative arrays and JSON-like notation seem to be here to stay. There’s nothing fancy about them, just a convenient way to talk about common abstract data types.
Looking for comments…