Data Domains
Vector 16:2, page 121
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 121
1. Towards a Definition¶
The domain of real numbers is denoted by ℝ.
It is unlikely that anyone would have a problem accepting this statement, although it is quite loaded. The use of the word "denoted" implies a Platonic (as opposed to a formalist) standpoint: even the use of the definite article as the first word reveals an assumption that (i) the domain of real numbers exists, and (ii) it is unique.
The really interesting word, however, is "domain". It is used in mediaeval history (where we were taught to spell it "demesne"), and also in permanent magnetism (a subject which still defies comprehension). The word crops up again in real analysis, where the "domain" and "range" of a function are matters of primary interest.
Data modelling makes much use of the term, and usage is increasing. Be warned, however, that the word is not used consistently. It has been used as a synonym for a column of a table in a relational database (i.e., all the actual values), for the set of actual values (i.e., after dropping out duplicates), and for the set of possible values which may occur in a column or columns. Sometimes the term is, implicitly or explicitly, restricted to "simple" domains (sometimes also called "primitive" or "atomic" domains), but most often, nowadays, it is used for "compound" or "structured" domains. (It used to be known as "designing the record layout"; nowadays it is known as "domain modelling" – only the name has been changed, to baffle the innocent.)
In formal semantics, a domain is something more than a set. Each element of a domain is deemed to be "tagged", so as to identify its original primitive domain. In set-theoretic terms, then, a domain is a set of ordered pairs – the first element being the tag, the second the "value". This models the situation inside the machine quite nicely, since the language processor will normally have some way of knowing the physical storage type of a variable, so that, for instance, 2 and 2.0 are distinguishable.
That serves the purposes of formal semantics very well, but for our purposes we shall use the simpler definitions:
- the domain of a variable is the set of all possible values that it is permitted to take;
- the domain of a function is the set of all inputs for which it is defined.
Implicit in the above is the restriction that we shall only be considering data domains.
2. The Primitive Data Domains¶
The primitive data domains are remarkably similar in all language.: in APL, they are as follows.
2.1 ℍ - characters and literals¶
The memory of Hermann Hollerith lives on! To be precise, in APL, this domain contains the character scalars: character vectors (strings) are not a primitive domain. APL seems to be alone in taking this stance: most other languages define strings as the primitive domain. It might be argued that a language which comes equipped both with strings and utilities for extracting individual characters is, implicitly, using characters rather than strings as the primitive domain, but this argument is really only valid if the language in question actually recognises single characters as qualitatively different from strings – most do not.
2.2 𝟚 - the logical values, 0 and 1¶
The spirit of Paul Halmos lives on! The rather convenient device of using a bold or double-struck 2 to denote the set <0,1> can be found in his Lectures on Boolean Algebras.
Some languages (e.g. C and APL) allow the logical values to be used in arithmetic, some (e.g. Basic and Pascal) do not.
2.3 ℕ - the natural numbers¶
Surely everybody knows the natural numbers: 0, 1, 2, etc, etc, ad infinitum?
2.4 ℤ - the integers¶
The sequence of integers is 0, 1, -1, 2, -2, etc. etc. ad infinitum.
(We could not possibly define the sequence by starting at "negative infinity", because (i) we have not yet established that this undefined "infinity" has a negative counterpart, and (ii) the sequence of natural numbers never actually reaches infinity, so we do not know how to count back from an infinite to a finite number.)
2.5 ℝ - the real numbers¶
This is the familiar "real number line". Obviously, with a finite machine, there are upper and lower limits to the numbers we can actually represent, and with a finite word size we are further restricted to a small set of rational numbers between those limits. These are only physical limits, however, and do not affect our considerations here.
2.6 ℂ - the complex numbers¶
Not all languages support complex numbers. No matter: they are not necessary for the purposes of this discussion.
3. Operations on Domains¶
3.1 membership¶
Perhaps the most fundamental operation we can perform using a domain is a test of membership:
or not, as the case may be:
which have the usual semantics.
3.2 domain sum¶
New domains may be obtained by combining existing domains in various ways. The simplest of these is the domain sum, written
which contains all the elements from domain A and all the elements from domain B. An element X is a member of the domain A⊕B, if
3.3 domain product¶
A more powerful way of combining domains is the domain product (or cross product, or Cartesian product), written
whose elements are ordered pairs, the first element of each pair being drawn from domain A, the second element being drawn from domain B.
The domain product is a new construct: it is not merely iterated application of domain sum. It differs, in this respect, from the foundations of mathematics, where multiplication is introduced as a syntactically convenient way of representing repeated addition, and addition itself is only a syntactically convenient way of representing repeated application of the successor function.
There are many similarities between arithmetic addition and multiplication, on the one hand, and domain sum and domain product on the other: A⊕B and B⊕A are identical, for instance. A⊗B and B⊗A, however, are not. The order in the elements of A⊗B means that the results of the two expressions are isomorphic, but not identical, so domain product is not commutative, so the two algebras are not identical. The symbols for the domain operations are (for the time being) enclosed in circles, to remind us of that fact.
3.4 tuples¶
The domain ℝ⊗ℝ consists of all possible ordered pairs of real numbers.
The domain ℝ⊗ℝ⊗ℝ consists of all possible ordered triples of real numbers.
We shall use the notation ℝ*K (called domain repetition) as a syntactically convenient way to denote all possible k-tuples of real numbers: that is to say, all real vectors of length k.
(The enclosing circle has been dropped at this point because the circle-star combination has already been appropriated for other uses. The chances of confusion are (hopefully) reduced by the use of the asterisk, which floats above the line, as opposed to the APL exponentiation symbol, which is vertically centred.)
3.5 simple vectors¶
We can generalise the notation a little, by allowing the exponent to be a set, with the following definition:
With this definition, we can see that
A*N = (A*0) the (unique) empty vector
⊕ (A*1) all unit-length vectors
⊕ (A*2) all vectors of length 2
:
⊕ (A*K) all vectors of length k
:
etc., etc., . . .
and A*ℕ therefore denotes the domain consisting of all vectors of whatever length, whose elements are drawn from A.
3.6 simple arrays¶
We can generalise further. Each of the terms in the above infinite series has a single-element exponent, and is therefore a vector. We can re-express the definition of vectors, as follows:
and extend the definition thus:
ℝ*ℕ*2 all real-valued matrices
ℝ*ℕ*3 all 3-dimensional real-valued objects
:
ℝ*ℕ*K all k-dimensional real-valued objects
:
etc, etc, and in particular:
which leads inevitably into
4. Function Domains¶
4.1 Let us now consider functions – in particular, those functions which take an input and produce a result, without any side-effects. If the input is chosen from domain X and the result comes from domain A, we say that the function maps the domain A into domain X, which is written thus:
and this expression is known as the function mapping. (A function mapping is still a domain, of course, but we already have the domain of the left argument and the domain of the right argument to consider, and we need something distinctive in the way of terminology here.)
4.2 A function such as "negation" will return a real result when supplied with a real argument.
The same truth can be variously expressed as:
"negation" maps reals into reals;
"negation" is a member of the set of functions which map reals into reals;
the function mapping of "negation"∈ℝ↤ℝ.
Some more primitive monadic functions and their mappings are as follows:
plus-reduce: ℝ↤ℝ*ℕ
plus-scan: (ℝ*ℕ)↤ℝ*ℕ
iota: (ℕ*ℕ)↤ℕ (although (ℕ*ℕ)↤ℕ⊕ℕ*1 is normal practice)
rho: (ℕ*ℕ)↤(ℍ*ℕ*ℕ)⊕(ℝ*ℕ*ℕ)
ravel: ((ℍ*ℕ)↤ℍ*ℕ*ℕ)⊕((ℝ*ℕ)↤ℝ*ℕ*ℕ)
Note that the functions’ mappings are expressed for their simplest non-trivial arguments.
4.3 The domain of monadic ravel (strictly speaking, the domain of its right argument) is
while its range is
We could therefore specify its function mapping as
but this is less precise than the expression given in the preceding paragraph, because the earlier definition expresses the fact that the elements of the result of monadic ravel come from the same primitive domain as the elements of the right argument.
4.4 We might want to extend this idea, to make it is clear that an integer argument produces an integer result. The notation for this would be
and this could be extended to do the same for boolean arguments. It could be extended – but it won’t be. The stance taken here is that integer vs. real is a question of internal representation, and representation is a matter of implementation not semantics. We ask only that the implementation can distinguish the elements of the each primitive domain: precisely how it distinguishes these domains is an implementation concern, and can therefore be airily dismissed as irrelevant to this discussion. The domain of an object is not necessarily the same as its physical type.
Noting that, because we are using "untagged" domains, 𝟚⊂ℕ, ℕ⊂ℤ, ℤ⊂ℝ and ℝ⊂ℂ, a corollary of this stance is that the interpreter is assumed to be capable of "promoting" a boolean to integer, say, where the context requires an integer, and of "demoting" a real to an integer if the context requires an integer and the real value satisfies the appropriate integrality constraints.
4.5 More difficult to dismiss is the objection that the present syntax does not permit the expression of other important relationships, such as the fact that the result of plus-scan has the same shape as its argument, or that the length of the result of monadic iota is determined by its argument. This could be done: the conventional notation would be something like:
but, for the time being, let us simply admit it as a shortcoming of the present notation and accept it as such.
4.6 Dyadic functions require extensions to the notation.
4.7 Conformability and scalar extension and suchlike are a separate matter.
5. Three Special Domains¶
5.1 ∅ - the empty domain¶
Clearly, the empty domain contains no elements. It is, however, still a domain: it is not a null entity.
5.2 D - the domain of domains¶
The domain of domains is denoted by D. An object is an element of D if and only if:
(i) it is a primitive data domain, or
(ii) it can be constructed from members of D using the operations of domain sum, domain product, domain repetition and function mapping.
Testing whether an object X is a domain then becomes a simple matter of testing whether
5.3 U - the universal domain¶
Nested arrays require extensions to the notation, but a given first generation APL implementation may have an overall data space described by
or
or
It is convenient to represent the overall data space by U, known as the universal data domain (commonly, if inaccurately, abbreviated to the universal domain), a term which has the advantage of being implementation-independent.
The function mapping for monadic rho can then be simplified (and generalised) to:
6. Summary¶
For very little work, we have developed a powerful and attractive notation, which helps us to describe some of the characteristics of functions, in a clear, unambiguous and concise manner, by describing the data domains of the functions’ inputs and outputs.
References¶
7.1 R.D. Tennent, Principles of Programming Languages, Prentice Hall (1981)
The notation presented above is a very close copy of Tennent’s Chapter 3, except that here it has been re-interpreted, simplified and generalised.
7.2 John McCarthy, A basis for a mathematical theory of computation, in P. Braffort and D. Hirschberg (ed.), Computers and Formal Systems, North Holland, Amsterdam (1963)
Tennent quotes McCarthy’s paper as the earliest use of these constructions.
7.3 Dana Scott, Towards a Mathematical Theory of Computation, in Proc. 4th Annual Princeton Conference of Information Sciences and Systems. Dept. of Electrical Engineering, Princeton University (1970)
My own starting point, it made more sense after reading Tennent.