[phylum]<3-LISP>course>manual>primer-b.bravo!2

Our next task, given a) some understanding of what 3-LISP expressions designate, and b) some understanding of what behaviour the 3-LISP processor exhibits, is to ask c) about how the 3-LISP processor works. This requires that we no longer speak extensionally, in terms of designated numbers, sequences, and functions, because the 3-LISP processor — a finite, physically realized, formal device — has not access to such abstract, "in-the-world" objects. Rather, it must deal with the expressions themselves, and with things it can make out of those expressions.

We have already talked some about expressions as such, and about a normalization relationship between them, and about the relationship between normalization and designation. In order to discuss the internal workings of 3-LISP, however, we must make yet another distinction: between 3-LISP expressions as notations — i.e., as strings of characters that can be printed on a page or on a terminal screen or edited in a buffer — and various internal structures inside the machine that the 3-LISP processor essentially translates those notations into. This distinction, between notations and internal structures, is like a distinction between a public language that a person speaks — say English — and an internal "mentalese" or brain-writing, in terms of which a person thinks.

Right away, we must emphasize that the ontological status of these internal structures — whether, for example, they are syntactic objects like notations, or whether they are more like set-theoretic or mathematical objects — is a matter of considerable dispute. One of the goals of the course is to convey intuitions about the status of these internal structures. But for the time being we will treat them rather simply. There are, in particular, internal structures that we call numerals, which correspond with the numeral expressions we have already seen. These internal numerals correspond one-to-one with the numbers they designate, but there can be more than one numeral expression corresponding to each numeral. For one thing, there are lots of occurences (tokens) of the same type of numeral expression (for example, there are several tokens of the numeral expression 16 in this primer — one in this sentence, several at the beginning of the first section, etc.). In addition, however, there are other types of numeral expression corresponding to the same number: XVI in Roman numerals, for example. There is, however, only a single internal numeral in 3-LISP for all of these.

You will have noticed that we have already started speaking as if internal structures designate, whereas earlier we said that expressions designate. In fact it was our earlier verbiage that was sloppy; henceforth (and throughout the manual, etc.), we will not say that expressions designate things directly; rather, expressions are internalized into internal structures (often just called structures), which in turn designate objects of many kinds. Similarly, internal structures can be externalized into expressions. So whereas we said that the 3-LISP processor was a "read-normalize-print" loop, it should more accurately be described as a "read-internalize-normalize-externalize-print" loop.

The issues relating expressions and internal structures form a complex subject in their own right; one we will examine in some detail in section 3 of the course. In general, however, it is convenient to ignore expressions and talk directly in terms of internal structures. Thus, we will from this point onwards, unless explicitly noted, we will talk as if 3 was an internal structure called a numeral, and as if $TRUE was an internal boolean constant. When we want to speak of notation directly, we will say such things as that ‘3’ is a numeral-expression that notates a numeral that in turn designates a number. Similarly, ‘=’ is an identifier that notates what is called an atom that designates the equality predicate (in the global context). Note the convention, which we have just now started, of using single quotes (as well as a sans-serif font) in our theoretic language to refer to 3-LISP expressions; the sans-serif font on its own will be used to refer to 3-LISP internal structures.

A variety of types of (internal) structure have already been implicitly involved in our discussions. The numerals have already been mentioned. Atoms were also mentioned; they are atomic (i.e., non-divisible) internal structures that are notated by identifiers of the sort we have seen: ‘Testing’, ‘+’, and ‘LAMBDA’. In fact we will from now on generally speak of atoms, not of the identifiers that notate them. Rails are internal structures that designate sequences, that are notated by a series of expressions enclosed in square brackets, such as: ‘[10 20 30]’, ‘[]’, and ‘[(= 2 3)]’. There are two internal structures called booleans — indivisible and context-independent constants designating truth and falsity, notated as ‘$TRUE’ and ‘$FALSE’. Pairs are the internal structures that represent function application; they are notated with parentheses, as in ‘(+ 1 2)’, ‘(IF (= 1 2) 3 4)’, and ‘(LAMBDA [X] Y)’. Strings and characters are designated by internal structures called stringers and charats that are notated with double quote marks and a hash sign, respectively; we have already seen such examples as ‘"lucky"’ and ‘#P’. Fortunately, stringers and charats are rather recherch́e objects — we won’t have much need to refer to them explicitly.

All of these are relatively straightforward. The complexities have to do with internal structures that designate functions. So far, we have used two kinds of expressions to "designate" functions: identifiers (notating atoms) and lambda-expressions. Neither of these, as it happens, can correspond very closely to the standard internal structures that designate functions (for reasons that will become clear as you get more familiar with the workings of the 3-LISP processor). Instead, there is a type of internal structure called a closure, for which there is no good standard notation. When closures are printed out, braces are used saying that this is a closure, but (unlike other cases) the notation carries far less information than is born by the closure itself. In particular, whereas from the notations for the other structures you can determine what structure is notated, and therefore what object is designated, from the notation used for a closure you cannot determine what closure it is, and therefore what function is designated. For this reason, closure notation is not accepted on input (i.e., there is no way to type a closure in to 3-LISP). But you can easily enough have closure notations printed out:

When we explore in detail how the 3-LISP processor works, we will examine the internals of closures; they basically contain the pattern and body expression that occur in the lambda expression, plus more information representing the context in which the defining lambda expression occured. For the time being, we needn’t bother with details.

In the last section we said that certain expressions were in normal-form, but as with much else that was strictly inaccurate; it is really internal structures that either are or are not in normal-form. What we called normal-form expressions were really externalizations of internal normal-form structures.

The following table summarizes the various sorts of structure, notation, and designation that we have discussed so far, and indicates which are in normal form. As indicated, some rails are normal form rails, and some are not; more specifically, a rail is in normal form just in case all of its elements are in normal form. Thus the rail [1 2 3] is in normal form, whereas the rail [1 2 (+ 3 4)] is not. The simplest way to think about normal-form structures is this: atoms (which serve as variables) and pairs (which represent function applications) are not; everything else is, except for rails, which defer the question entirely to their elements.

NumeralsNumbersYes sequence of digits123
BooleansTruth-ValuesYes $TRUE or $FALSE$TRUE
CharatsCharactersYes #character#a
StringersStringsYes "sequence of characters""Hello"
ClosuresFunctionsYes{ ... closure ... }{+ closure}
RailsSequencesSome[x1 x2 ... xn][10 20 30]
Atoms(Designation of Binding)Nosequence of alphanumericsFactorial
Pairs(Value of Application)No(x1 . x2)(+ . [1 2])

For us, as external theorists, to discuss how 3-LISP works, we need to mention 3-LISP structures directly; that was what the last section introduced. However, we will also need 3-LISP structures that themselves mention other 3-LISP structures; hence we need some kind of internal quotation mechanism. Such a mechanism, and its associated machinery, will be introduced here.

For every internal structure S, there is a unique indivisible internal structure that is a normal-form designator of S, called its handle. Since handles are themselves internal structures, this means that the 3-LISP structural field — the name we use for the whole assemblage of internal structures en masse — is infinite (this is no problem; an implementation can act as if the field is infinite, even if you couldn’t actually have an infinite field in a finite device). Handles are notated with a single quote mark followed by the notation for the structure of which they are a handle. Thus, since the numeral designating the number three is notated by the string ‘3’, the handle of that numeral is notated by the string ‘’3’. We will therefore refer to handles using that single quote mark directly; thus the handle of the atom IF is ’IF; the handle of the pair (+ 2 3) is ’(+ 2 3). Since handles are in normal form, if you type them into the 3-LISP processor (strictly: you type in their notations), you will get back exactly what you typed:

Handles enable us to mention atom names, which is a convenient mechanism that enables us to get around 3-LISP’s most enormous and blatant failure: it provides no disciplined way of refering to things in the world, other than mathematical abstractions. Suppose, for example, that you want to write a program about kinship relationships, and you define a procedure called FATHER that is meant (perhaps by looking up in a data-base) to return the name of the father of the person given to it as an argument. You might expect to define a function, in particular, supporting the following behaviour:

The problem is that this cannot be done! The reason is that CAITLIN is taken, by the 3-LISP processor, as an atom, and atoms serve essentially as variables; 3-LISP therefore tries to determine the normal-form designator of the entity (in this case, the woman herself) that that atom designates. But CAITLIN is a name for us, it is not a name for the 3-LISP processor, which knows nothing about people or their names. There just isn’t any well-defined notion of normal-form designators for people — in fact the notion of a normal-form designator is an extraordinarily restricted case of the general question of providing useful ways of referring to things in varieties of contexts. (So, when the foregoing input expression is typed into 3-LISP, it will almost undoubtedly produce an error, saying that CAITLIN is "unbound".)

Similarly, the 3-LISP processor is mandated always to return normal-form designators; in the case at hand, it should therefore return a normal-form designator of Caitlin’s father. And, by our own earlier admission, the name LLEWELYN cannot be a normal-form designator, because no atoms are in normal form. This is the same problem over again.

One possible solution is to introduce a new kind of structure into 3-LISP, rather like atoms, but taken by the processor to be normal-form designators of objects quite outside its ken (suppose, for example, that such structures were notated like atoms except with a leading ‘@’, giving us something like @CAITLIN and @LLEWELYN). However there is a problem here: if the processor knows nothing about such objects, it will have no way to know about their identity conditions, and therefore no way to know how to normalize structures such as (= @CAITLIN @LLEWELYN). In this case the result should clearly be $FALSE, but what about (= TULLY CICERO)?

The standard solution is to assume a) that all such constants designate different objects, and b) that all objects are designated by such constants — i.e., that there is nothing in the world you don’t have a name for. This pair of assumptions (described formally in terms of something called a Herbrand model) amount to this: we simply assume that the identity of the structures in question can serve in place of the identity of the things designated, for lack of any better information.

In designing 3-LISP we felt that this identification is serious (and probably ill-advised), and that it should therefore be reflected very explicitly. It is possible, therefore, to do everything one could do with constants merely by quoting atoms; in fact the proposal for using ‘@’ as an idenitfying character at the beginning of constants, and using the single quote mark for handles, are essentially identical. What the quote mark does it to make it apparent that it is structural identity, not identity of designation, that is being used in the calculations. It also makes it apparent that programs, by and large, are about representational structures, not about what those representational structures designate (this point will be taken up in considerably more detail in class).

The use of handles makes clear some other assumptions behind 3-LISP. For example, they enable us to see that 3-LISP functions are all (at least almost all) defined extensionally, in terms of the designation of their parameters. Consider TYPE, for example, which maps its arguments onto atoms that identify the argument’s type. (TYPE 3) g ’NUMBER, for example, because the function designated by the atom TYPE is given as an argument the number designated by the numeral 3. Therefore (TYPE 3) designates the atom NUMBER. The normal-form designator of that atom is the handle ’NUMBER, which is why (TYPE 3) returns it. Some more examples:

(TYPE 3)g’NUMBER
(TYPE ’3)g’NUMERAL
(TYPE $TRUE)g’TRUTH-VALUE
(TYPE ’$TRUE)g’BOOLEAN
(TYPE (= 1 2))g’TRUTH-VALUE
(TYPE ’(= 1 2))g’PAIR
(TYPE ’’(= 1 2))g’HANDLE
(TYPE =)g’FUNCTION
(TYPE ’=)g’ATOM
(TYPE [1 2 3])g’SEQUENCE
(TYPE ’[1 2 3])g’RAIL
(TYPE "exquisite")g’STRING
(TYPE ’"exquisite")g’STRINGER
(TYPE #a)g’CHARACTER
(TYPE ’#a)g’CHARAT

The 3-LISP processor is idempotent, meaning that once a structure is reduced to normal-form, no further reduction is possible. Thus, if the result of a normalization is normalized again, it will be its own result. It follows from this that no amount of normalizing of the handle ’3 will yield anything but the handle ’3; in particular, it will not turn it into the numeral 3. This exemplifies a very general and important property of the 3-LISP processor: it is what we call semantically flat, in the sense that it never crosses designation boundaries. But sometimes — such as when one has a handle designating a numeral, and wants the numeral itself — it is useful to be able to cross these levels of designation. Two primitive operators are provided in 3-LISP to do this, called UP (written ‘↑’) and DOWN (usually notated ‘↑’, or ‘\’ on terminals that don’t have a down-arrow character). These two operations are duals: ↑x designates the structure to which x normalizes, whereas ↑x normalises to the structure that x designates. There are some restrictions on the use of DOWN; its argument, in particular, must be a normal-form structure, rather than just a structure in general. In general, however, the way to remember UP and DOWN is that UP adds a quote, whereas DOWN removes one. Some examples: