2.1 Raw Material

The purpose of this section is to instill some basic concepts about the way information is stored or communicated by the virtual machine, which may be necessary for an understanding of subsequent sections.

The virtual machine represents both programs and data as members of a semantic domain that is straightforward to describe. Lisp users and functional programmers may recognize familiar concepts of atoms and lists in this description. However, these terms are avoided for the moment, in order to keep this presentation self contained and to prevent knowledgeable readers from inferring any unintended meanings.

As a rule, it is preferable to avoid overspecifying any theoretical artifact. In this spirit, the set of entities with which the virtual machine is concerned can be defined purely in terms of the properties we need it to have.

A distinguished element

A particular element of the set is designated, arbitrarily or otherwise, as a distinguished element. Given any element of the set, it is always possible to decide whether or not it is the distinguished element. The set is non-empty and such an element exists.

A binary operator

A map from pairs of elements of the set to elements of the set exists and meets these conditions.

• It associates a unique element of the set with any given ordered pair of elements from the set.
• It does not associate the distinguished element with any pair of elements.

For the sake of concreteness, an additional constraint is needed: the set has no proper subset satisfying the above conditions. Any number of constructions remain within these criteria, but there is no need to restrict them further, because they are all equivalent for our purposes.

To see that these properties provide all the structure we need for general purpose computation, we may suppose some given set S and an operator cons having them are fixed, and infer the following points.

• S contains at least one element, the distinguished element. Call it nil.
• The pair (nil,nil) is a pair of elements of S, so there must be an element of S that cons associates with it. We can denote this element cons(nil,nil).
• As no pair of elements is associated with the distinguished element, cons(nil,nil) must differ from nil, so S contains at least two distinct elements.
• The pair (nil,cons(nil,nil)) therefore differs from (nil,nil), but because it is yet another pair of elements from S, there must be an element associated with it by the operator. We can denote this element as cons(nil,cons(nil,nil)).
• Inasmuch as the operator associates every pair of elements with a unique element, cons(nil,cons(nil,nil)) must differ from the element associated with any other pair of elements, so it must differ from cons(nil,nil), and we conclude that nil, cons(nil,nil) and cons(nil,cons(nil,nil)) constitute three distinct elements of the set S.
• By defining cons(cons(nil,nil),nil) and cons(cons(nil,nil),cons(nil,nil)) analogously and following a similar line of reasoning, one may establish the existence of two more distinct elements of S.

It is not difficult to see that an argument in more general terms could show that the inclusion of infinitely many elements in S is mandated by the properties of the cons operator. Furthermore, every element of S other than nil owes its inclusion to being associated with some other pair of elements by cons, because if it were not, its exclusion would permit a proper subset of S to meet all of the above conditions. We can conclude that S contains exactly nil and the countable infinitude of elements of the form cons(x,y), where x and y are either nil or something of the form cons(…) themselves.

Some specific examples of sets and operators that have the required properties are as follows.

• the set of natural numbers, with 0 as the distinguished element, and the cons operator defined by cons(x,y) = ((x+y)(x+y+1))/2 + y + 1
• a set of balanced strings of parentheses, with () as the distinguished element, and cons defined as string concatenation followed by enclosure in parentheses
• a set of ordered binary trees, with the empty tree as the distinguished element, and the cons operator as that which takes an ordered pair of trees to the tree having them as its descendents
• a set containing only its own Cartesian product and an arbitrary but fixed element nil, with cons being the identity function

Each of these models may suggest a different implementation, some of which are more practical than others. The remainder of this document is phrased somewhat imprecisely in terms of a combination of the latter two. The nature of the set in question is not considered further, and elements of the set are described as “trees” or “lists”. The distinguished element is denoted by nil and the operator by cons. Where no ambiguity results, cons(x,y) may be written simply as (x,y). These terms should not be seen as constraints on the implementation.

This document was generated on November 8, 2012 using texi2html 1.82.