The data model
One of the most important and distinctive features of Cell is the way it represents information. Every piece of information is represented as a value, and only as a value (as opposed to an "object"). All values, of all kinds, share a number of properties:
- Values do not expose their location in memory, or any other form of "identity". If, for example, the values contained in two different variables compare equal, there's no way to tell if the two variables are referring to the same location in memory, or if they are pointing to distinct memory locations that happen to have the same content. This is true for both atomic types, like booleans and integer or floating point numbers, and for composite types, like sequences or records.
- Every value has a literal, that is, a human-readable representation that can be used to denote that value in the code, and to display or store it in text form. Again, this is true for atomic values (
false,42,3.14159) and composite values ([0, 1, 2, 3],point(x: 12, y: 5)) alike. - There's no such thing as user-defined equality. The notion of equality is defined by the language itself (it is the most obvious one), for all values, and cannot be overridden. And if two values compare equal, then they can substitute each other in any expression, without changing its result (note that this is in general not true for user-defined equality, or for any kind of "deep" equality in a language with pointers or object ids). This is true even if those values are internally represented in different ways. The same (logical) sequence, for example, could be represented under the hood as an array or a list, depending on the circumstances, but those implementation details do not "leak" into the semantics of the language.
- Values don't have a type, yet the language is statically typed. That sounds a bit bizarre, I know. Everything will be explained in the next chapter.
- You cannot define new values. Yes, this too, sounds a bit bizarre. But all the values you can manipulate in Cell are predefined by the language, and developers can only choose from a universal set of values which ones to use. But don't worry, there's everything you need. The language provides you with a number of atomic values (integers, symbols and floating point numbers), and ways to aggregate these atomic values into composite ones, like sequences, sets and records. For an (imperfect) analogy, think of JSON in JavaScript or S-expressions in Lisp.
- There is no aliasing of any sort, and values are, conceptually at least, immutables entities. You can assign a new value to an existing variable, and, under some specific circumstances, the language will be able to produce a new value by actually updating, under the hood, an existing one, but updating a variable will never result in any observable change in the content of any other variable. An alternative way to put this is to say that the content of a variable can be updated in place, but the language has value semantics for all data structures, including composite ones, so the act of modifying the content of a particular variable never affects other variables.
With all that in mind, let's delve into the details.
Atomic values
Integer numbers are 64-bits wide and signed. There are no distinct 8/16/32 bit or unsigned integers, but the compiler is free to use a smaller integer size whenever it can determine that a certain variable will never hold a value that exceeds its bounds (if, for example, the compiler can determine that the range of values a certain variable will ever hold is between 0 and 255, then it's free to use a single byte to store them) and that can, to some extent, be controlled by the programmer with the use of the appropriate type declarations.
Then we have double-precision floating point numbers. They are the same as in any other language.
The third and last kind of atomic values is symbols. Lisp or Ruby programmers are not going to need any explanation here, but for those who are not familiar with those languages, symbols are sort of similar to enum values in languages like C/C++, the main difference being that you don't need to declare them before using them. The syntax is similar to that of Ruby, but is more restrictive: a colon, followed by a lowercase letter, followed by any number of lowercase letters, numbers and underscores. Uppercase letters are not allowed, as are multiple consecutive underscores or trailing ones. Here are a few examples of valid symbols:
:a
:a_symbol
:symb_3a
:ab12c_3de45
and invalid ones:
## :1ab // Invalid: starts with a number
## :_ab // Invalid: starts with an underscore
## :ab_ // Invalid: ends with an underscore
## :ab__cd // Invalid: two consecutive underscores
## :ABC // Invalid: uppercase letters
In some cases (basically wherever symbols cannot be confused with variable or constant names) the initial colon can be ommitted. (More on this in the following chapters).
Two symbols, :true and :false, are special, in that they are used to represent boolean values. Since they are ubiquitous, there’s no need to write the initial colon: they are just written true and false, respectively.
Symbols are internally represented by integer numbers, but the specific numbers used to represent each symbol vary all the time and are just an implementation detail that is hidden from the programmer.
Sequences
Sequences are more or less the equivalent of arrays or list in other languages. You can create a sequence by enumerating its elements separated by commas and enclosed by parenthesis. A few examples, starting with the empty sequence:
()
(0, 1, 2, 3)
(:a, :b, 3.14159, 100)
(:a, (1, 2, 3, (0.2)), (), (:b, :c))
As an aside, parentheses can also be used to specify the order of evaluation in a complex expression, and this creates an ambiguity in the case of expressions like (x + y), which could interpreted either as the one-element sequence containing the value x + y, or just a parenthesized sum. How the compiler resolves the ambiguity is explained in one of the next chapters, but if you wanted to force it to parse such an expression as a single-element sequence, one (admittedly ugly) way to do it is to add a comma just before the closing parenthesis, just like in Python or Perl: (x + y,). That's hardly ever necessary, though.
Like all collection types, sequences can hold any kind of values, and can therefore also be used as tuples, that is, fixed-length sequences of heterogeneous values.
Sets
Sets differ from sequences in that the order of the elements doesn't matter, and duplicates are eliminated. They are enclosed in brackets:
[] // The empty set
// Two different ways to write the same set.
// The order of the elements doesn't matter
[5, 12, 1, 6]
[12, 6, 1, 5]
// The set whose only element is the number 1
// Duplicates are ignored
[1, 1, 1]
// A set containing values of different types
[:a, (1, 2, 3), [0.51, :b], ([])]
Binary relations
A binary relation is an unordered collection of (ordered) pairs of values, or in a more mathematical parlance, it is a subset of the cartesian product of two arbitrary sets (the definition of both sets and relations in Cell is basically the same as the standard mathematical one, if we restrict our attention to finite data structures only). Just like with sets, duplicates are eliminated. They are written between brackets, with pairs separated by a semicolon and elements of each pair separated by a comma. The empty relation is denoted by an empty pair of brackets, and it is exactly the same entity as the empty set.
[] // The empty relation (and also the empty set)
// A relation between integers and symbols
[0, :zero; 0, :nil; 1, :one; 2, :two]
// A relation associating the numbers 1, 4
// and 9 with all their square roots
[1, 1; 1, -1; 4, 2; 4, -2; 9, 3; 9, -3]
One syntactical oddity is that, in order to distinguish them from a two-element set, binary relations that contain only one pair have to be written with a semicolon before the closing bracket:
[0, 1] // The two-element set containing 0 and 1
[0, 1;] // The binary relation containing the single pair 0, 1
Just like any other collection type, relations can contain any value, including composite ones:
[ :alice, (0, (1, (2, ())));
[1, 2, 3], (3, 2, [0, []]);
[:a, :b; :c, 3.14159], :bob;
[[:a, :alpha; :b, :bravo], [2.71828]], 0
]
Maps
Maps (or associative arrays) are an important special case of binary relations: a binary relation is a map if and only if no two pairs in the relation have the same left element, or, using the terminology of relational databases, if the first column is a key for the relation. Another way to say that is that a map is a set of key/value pairs where each key is unique, and that a generic binary relation is more like a "multimap", since it may associate more than one value to any given key.
One important thing to keep in mind is that you can apply to a map any operation that you would apply to a binary relation (since a map is a binary relation), but there are a few extra operations you can apply to a map that don't make sense in the more general case of a generic binary relations, such as looking up a value given its corresponding key.
Maps also have a special syntax, where you use an arrow to separated the key from the value and commas to separate pairs:
// A map from integer numbers to symbols
[0 -> :a, 1 -> :b, 2 -> :c, 3 -> :d]
// A map with just one entry
[:pi -> 3.14159]
The above notation is completely equivalent to [0, :a; 1, :b; 2, :c; 3, :d] and [:pi, 3.14159;], but it is used to guarantee that the value is actually a map in expressions containing variables: if w, x, y and z are variables, the two expressions [w, x; y, z] and [w -> x, y -> z] will produce exactly the same value if w is different from y, but the latter will fail if they are equal, while the former will succeed in either case.
Also note that every singleton binary relation is a map, so you can avoid the syntactic quirk for one-entry relations described above by using the map notation:
[0, 1] // The two-element set containing 0 and 1
[0, 1;] // The binary relation containing the single pair 0, 1
[0 -> 1] // Same as [0, 1;]
Records
Just like maps are a special case of binary relations, records are a special case of maps. A map is a record if (and only if) all of its keys are symbols. Since records are ubiquitous, they have their own syntactic sugar:
// Syntactic sugar for [:left -> -1.2, :right -> 7.5]
// and [:left, -1.2; :right -> 7.5]
(left: -1.2, right: 7.5)
// Same as [:x -> 15, :y -> 4, :z -> -7]
// and [:x, 15; :y, 4; :z, -7]
(x: 15, y: 4, z: -7)
// Same as [:ro -> 2.0, :theta -> 1.5708]
// and [:ro, 2.0; :theta, 1.5708]
(ro: 2.0, theta: 1.5708)
Note that they are enclosed in parenthesis (not brackets), that key and value are separated by a colon and that symbol keys are written without any preceding colon. Remember also that since records are maps, which in turn are relations, all the operations that can be applied to binary relations and maps can also be applied to records, but not vice versa.
Tagged values
The only type of composite value that is not a collection type is the tagged value. Tagged values are built by joining together a symbol (called the tag) and another value. The tag is written first, followed by the value enclosed in parentheses. A few examples:
:meters(200)
:seconds(3600)
:point((x: 10, y: 25))
:rectangle((left: -10, right: 20, top: 50, bottom: 30))
Just like for symbols, there are contexts (that will be described later) where the initial colon is not required. There's also a bit of syntactic sugar: when the value enclosed between parentheses is a sequence or a record, there's no need to type the second set of parentheses. Also, if the value being tagged is a record, and the second pair of parentheses is omitted, the colon preceding the tagging symbol has to be omitted as well (in all contexts). A few examples:
// Syntactic sugar for :point((x: 10, y: 25))
point(x: 10, y: 25)
// Syntactic sugar for :person([:name -> "John", :age -> 25])
person(name: "John", age: 25)
// Syntactic sugar for :vector_3d((0.5, 0.3, 1.2))
:vector_3d(0.5, 0.3, 1.2)
// Syntactic sugar for :a_tag((10, (:a, :b), []))
:a_tag(10, (:a, :b), [])
For reasons that we'll see later, when using records in Cell it's often necessary to tag them with a symbol (ideally one that describes their purpose).
Ternary relations
Ternary relations are just like binary relations, but they contain triples instead of pairs. The syntax is identical, including the same quirk for single-entry relations:
// Driving distances between cities, in kilometers
[ :new_york, :boston, 346;
:san_francisco, :los_angeles, 617;
:las_vegas, :phoenix, 479;
:seattle, :portland, 279;
:miami, :orlando, 380
]
[ "Usain Bolt", 100, 9.58;
"Usain Bolt", 200, 19.19;
"Wayde van Niekerk", 400, 43.03;
"David Rudisha", 800, 100.91
]
["Usain Bolt", 100, 9.58;] // Singleton ternary relation
Also, the empty ternary relation is the same entity as the empty set and the empty binary relation, that is, all unordered collection types share the same empty value:
[] // The empty set/relation, for any relation arity
The language is meant to provide, once it's fully implemented, relations of arbitrary arity, but for now unary (i.e. sets), binary and ternary relations are all there is.
Derived data types
All Cell values are created by combining the data types we've seen so far: integers, floating point numbers, symbols, sequences, sets, binary and ternary relations and tagged values. But there's also a number of other common data types that are treated a bit specially, in the sense that they have a standard representation and some syntactic sugar, even though they're built using the primitives described above. So far, there's four of them: strings, characters, dates and times, but more may be added in the future.
Strings and characters
Strings in Cell are just sequences of non-negative integers, where each number is the ASCII/Unicode code point of the corresponding character, tagged with the symbol :string. In their syntactically "sugared" representation, they are enclosed in double quotes. The following are different ways of writing exactly the same value:
"Hi there!\n"
string(72, 105, 32, 116, 104, 101, 114, 101, 33, 10)
:string((72, 105, 32, 116, 104, 101, 114, 101, 33, 10))
There are five special escape codes, \n, \t, \r \" and \\, and the generic numeric one, a backslash followed by exactly four hexadecimal digit, \XXXX, where the four digits represent the 16-bit code point of a character in the Basic Multilingual Plane.
There's no separate character type, and character are represented by a number, their unicode code point. There's a bit of syntactic sugar though: a character enclosed in backquotes is just another way to write its code point. The following expressions, for example, all evaluate to true:
`a` == 97
`Z` == 90
`4` == 52
`\n` == 10
`\t` == 9
`\\` == 92
`\`` == 96
`∞` == 8734
`€` == 8364
`海` == 28023
This is yet another way to write the string "Hi there!\n":
:string((`H`, `i`, ` `, `t`, `h`, `e`, `r`, `e`, `!`, `\n`))
Dates and time
Time in Cell is represented by integers tagged with the symbol :time. The integer is the UNIX Epoch time in nanoseconds, that is, the number of nanoseconds that have elapsed sinced 00:00:00 Thursday, 1 January 1970 (the UNIX Epoch), not counting leap seconds. Dates too are represented as tagged integers: the tag is the symbol :date and the integer is the number of days that have passed since 1 Jan 1970. In their syntactically sugared form they are enclosed in backquotes and use the `YYYY-MM-DD HH:MM:SS` format for time or `YYYY-MM-DD` for dates. Time literals can also specify the number of nanoseconds: `YYYY-MM-DD HH:MM:SS.NNNNNNNNN`. The following expressions all evaluate to true:
`1970-01-01` == :date(0)
`1970-01-02` == :date(1)
`1969-12-31` == :date(-1)
`1582-10-15` == :date(-141427) // First day of the Gregorian calendar
`2000-01-01` == :date(10957)
`1970-01-01 00:00:00` == :time(0)
`1970-01-02 12:00:00` == :time(129600000000000)
`1969-12-31 23:59:59` == :time(-1000000000)
`1999-12-31 23:59:59` == :time(946684799000000000)
`1970-01-01 00:00:00.000000001` == :time(1) // 1ns after the UNIX Epoch
`1970-01-01 00:00:00.002` == :time(2000000) // 2ms after the UNIX Epoch
`1969-12-31 23:59:59.995` == :time(-5000000) // 5ms before the UNIX Epoch
Since integers are 64-bits wide, the time range that can be represented using this format goes from `1677-09-21 00:12:43.145224192` to `2262-04-11 23:47:16.854775807`, inclusive.
Physical implementation
In the above description, we didn't say anything about how collection values are actually implemented under the hood, even though that's obviously important for the programmer to know. That's because the language itself does not prescribe any specific implementation, so that the compiler is free to choose between different data structures, with different performance characteristics and different time/space trade-offs, and to dynamically switch between them depending on how they are actually used.
Take, for example, sequences. The abstract concept of sequence, that is, a collection of values, some of them possibly repeated, that are arranged in a linear order, can be implemented as an array, or a linked list, or a rope, or a combination of them, or something else entirely. All those implementation are conceptually equivalent, and only differ in their performance characteristics.
Now, many of the design goals of Cell depend on it being a very data-oriented language, in the sense of having a simple, uniform, human-readable and ideally unique representation for (almost) any piece of information. And exposing all these implementation details (list vs rope vs array vs something else) obviously goes against those goals. So the task of choosing the actual implementation at any given time has to necessarily fall on the compiler and the language runtime, and the programmer can control it only indirectly by carefully choosing (if need be) which operations to use in his or her algorithms.
Sequences, for instance, are currently implemented as arrays, and consequently support fast random access and (functional) insertion at the end. But in the future the runtime will make use of either arrays or ropes, and will be able to switch dynamically between these two forms, depending on how these data structures are used. For example, if you are creating a long sequence by recursively concatenating smaller ones, the runtime might choose to represent them as ropes, in order to make concatenation O(1). But the moment you start accessing its elements by index, it might rearrange the content of the sequence into an array, in order to support fast random access. If you wanted, for example, to induce the runtime to use only arrays (for whatever reason), one way to do so would be to build that long sequence by only appending new elements at the end, an operation that can be performed efficiently with arrays.
That doesn't mean of course that you cannot implement you own data structures on top of the existing ones, if the circumstances require it. You could, for example, define a your own set or map types using the language provided types as primitives, if the native versions don't meet your needs, and there are indeed times when you would actually have to do so. But in all other cases, letting the compiler/runtime do the low-level work will make your code simpler, and your data easier to inspect and manipulate.
Another data structure (or, rather, set of data structures) that benefits greatly from a clear distinction between logical definition and physical implementation is records. Remember that records in Cell are just a special case of maps, which in turn are just a special case of binary relations. This provides the ability to treat records as generic maps and, for example, to merge them (in a type-safe way: more on this in another chapter) or to build them up dynamically. On the other hand, though, representing records as maps at the physical level is nowhere as efficient as using ad-hoc data structures. So the compiler creates (subject to a number of conditions that are discussed elsewhere) specific low-level data structures for all record types that are explicitly declared in your code, which are just as efficient as structs or classes in languages like C or Java, and transparently switches between the optimized and generic representations whenever needed.
Similar considerations apply to all other collection types as well. Sets and maps can be implemented as sorted arrays, balanced binary trees or a combination of the two. Sorted arrays are used when creating a set or map in just one go, but when you try to insert or remove an element or a key/value pair in an existing set or map, an operation that cannot be supported efficiently with arrays, the language switches to a hybrid representation that combines arrays and binary trees, so that such operations can be performed efficiently in O(log(N)).
As we'll see in another chapter, relational automata can contain "mutable" relation variables. Those variables contain, conceptually speaking, ordinary relation values, but they are restricted in the way they can be used, so that they can be updated in place without compromising the functional nature of the language. In that case, the compiler uses a completely different implementation approach, in order to support both efficient insertion of new tuples and deletion of existing ones.
One intrinsic limitation of both native sets and relations though is that they are unordered containers, and will never be able to support operations that require an ordering of the elements of the collections, except maybe in very specific cases, such as sets of integers, or maps with integer keys. That's because these data structures must be able to contain any type of value and to work even when no explicit ordering criteria has been provided, so even though they do, in some cases, keep their elements sorted, they have to rely on an internal notion of ordering that is not meaningful to the user. That's actually one of the cases in which you might need to use custom data structures.
Design rational
Before moving on to the subject of types, I wanted to offer some rational for the design of Cell's data model. The language makes a number of unusual choices for a statically typed language, and we are now going to examine some of the pros and cons that such choices involve. I'll avoid any mention of the role of relations (and the absence of pointers/object ids and aliasing), which is so important a subject that it deserves to be discussed at length elsewhere, and I'll focus here instead on the structural nature of the data model. To recap what we have learned so far:
- The set of all values the language can represent is fixed and cannot be extended.
- This universal set of values is defined structurally, starting from a set of atomic values that can be aggregated in various ways to form more complex, composite values.
- Composite values can always be "disaggregated" into their component parts.
- Logical definition and physical representation are distinct. Physical implementation details cannot be "observed" within the language.
The first interesting consequence is that it becomes possible, and actually relatively easy, to define universal functions that can operate on any value, without restrictions. Functions that, for example, calculate a hash code for any value, store it in an arbitrary binary format or generate its textual representation are both short and very easy to write. These functions know in advance all the possible cases they will ever have to deal with (since the set of values is fixed) and can easily disaggregate composite values into their constituent parts.
It is true, of course, that even commonly used languages like Java and C# can, to some extent, do similar things using their reflection/introspection API: it is more complicated, and it may not always work (what happens, for example, when a serialization function that makes use of the reflection API is applied to an object of a class (maybe one defined in the system libraries) that is either built-in, or partially defined in C? Will it still work?) but it can at least be made to work well enough in most situations.
Other cases, though, tend to be far more difficult for those languages to handle. Consider, for example, the problem of deserializing data. Writing in Cell a function that can build any value from its textual representation (or, more generally, from a serialized form) is a bit more complicated that writing the corresponding printing/serialization function (because parsing is intrinsically more complex than printing), but it is still straighforward and works 100% of the time.
This is not true for, say, Java or C#. What if, for example, the serialized data contains objects of a class that is not defined in the application that is trying to load that data? Or if that class is present, but has a different definition, maybe because the serialized data was created by an earlier version of the same application? Even the much simpler task of converting data from a relational database into native data structures, a process that is absolutely trivial in Cell, is a huge hassle in those languages.
In a language that supports features like orthogonal persistence and the ability to "replay" the execution of a program, any limitation in the ability to deal with data whose structure is unknown, or only partially known, would be too crippling (for reasons that will be extensively discussed in the following chapters) and a nominative data model/type system is just not an option.
The problems created by non-structural languages are not limited to the handling of persisted data. Consider, for instance, data manipulation operations like merging records, adding or removing fields from them, or performing the equivalent of relational algebra operations like "project" or "join". What they all have in common is that they implicitly create new "types" of data structures. Nominative languages that prevent you from using data structures you've not explicitly declared severly limit your ability to use those declarative and low-ceremony data manipulation operations.
There are, sure, some clumsy workarounds. C#, for example, has this weird notion of anonymous types (often used in LINQ expressions), which, being anonymous, cannot even be passed around to other functions in a type-safe way, and cannot have polymorphic methods. Many other languages provide tuple types, which inject limited structural capabilities into an otherwise nominative type system, and in some cases even structural records. But none of these workarounds can match the flexibility offered by a fully structural approach.
Of course, not all is perfect and wonderful in the land of structural types, and there are trade-offs to be accepted if one chooses to go down that way. Probably the most important one is the complete lack of encapsulation, at least in the conventional sense. In Cell, values are entirely transparent, and can be inspected and manipulated without restrictions. Only their physical representation is hidden from view. The language does provide an important abstraction mechanism, protocols, but that's more the equivalent of "programming against an interface" that real encapsulation. But anyway, encapsulation (or lack thereof) is such an important topic that it deserves to be discussed separately, once we have a full picture of the language.
Structural vs nominative debate aside, you might have noticed a major omission in the data model: closures. While the language does support closures, they cannot be mixed with normal data. The reason for this is simple enough: in Cell it must be possible to easily do things like serializing a value, recreating it from its stored form, sending it through a network connection to a different application, displaying it to the user in a human-readable format and even using it to exchange data with applications written in different languages, without resorting to some external, alien data format like JSON. But once you throw closures into the mix, all that becomes really hard. It's not just difficult to implement: it's also conceptually problematic. If, for instance, you store (or send through a pipe or network connection) a closure that calls other functions, which in turn call other functions and so on, you'll have to send the entire call graph, or different applications (or even different versions of the same application) may not be able to reconstruct it. And if you persistently store a closure (or a function that is, directly or indirectly, called by it), and that closure/function has a bug, how do you get rid of it? More generally, if you load a closure created by, say, an older version of your applications, and some of the functions stored within it have since changed, how will the different versions interact? Couldn't that be a potential source of really nasty bugs?
In addition to all that, closures and functions do not support any meaningful notion of equality, and that's a problem in a language where data structures that heavily rely on it, sets and relations, are so pervasive.
So, given that closures clearly have properties that differ drastically from those of normal data, the choice of segregating them in a separate cage seems to be the most sensible one, even though that certainly reduces the expressiveness of the language.