So it is a two-stage process. First we'll see how this LISP works, then we'll use it to program a Turing machine that accepts binary programs, not programs in LISP. And the size of those binary programs will be our official program-size measure, H(x).
In this book we are not interested in the size of LISP programs, only in using LISP to write and run the programs whose size we really care about.
LISP is a non-numerical programming language, and it's a functional, expression based language, not an imperative language. In LISP programs you don't indicate how to calculate with numbers, instead you define functions that deal with symbolic expressions, and then you apply these functions to specific arguments.
The symbolic expressions, or S-expressions, that we'll work with are abstract versions of algebraic expressions in which everything is fully parenthesized, and you can summarize the syntax of LISP by saying that the parentheses have to balance. For example, here are some typical S-expressions:
abracadabra (abc (def ghi) klm) (((wonderful))) ()LISP S-expressions are either ``atoms'' which are words, or they're lists. It's either-or, with one exception. The exception is the empty list (), which is also an atom. Otherwise a list consists of one or more atoms or sublists. Successive atoms in a list need to be separated by one or more blanks, but otherwise blanks are ignored. For example, here we need blanks to separate the successive elements of a list:
(x y z)and here we don't need any blanks:
((x)(y)(z))Note that, unlike a set, the elements in a list may be repeated, and there is a first element, a second element, and so forth. For example
(a b a)is a valid S-expression. Its first element is a, the second element is b, and the third element is also a.
In LISP you're given some primitive functions for dealing with S-expressions, and you have to define more elaborate functions from these primitive functions. The LISP notation for f(x, y, z), for the function f applied to the arguments x, y and z, is (f x y z).
Here is the general rule for evaluating an S-expression. If it is an atom, then its value is the current binding of that atom. Initially each atom is bound to itself, except for the atom nil, which is bound to () and gives us a name for the empty list. If an S-expression is not an atom, then its value is defined recursively in terms of the values of its elements. First evaluate the first element to determine the function to be applied, then evaluate the remaining elements (from left to right) to determine the values of the arguments, then apply the function to these arguments. And there are two pseudo-functions which do not evaluate all of their arguments: quote ' and if-then-else if.
What are the primitive functions for dealing with S-expressions?
The first is car, which gives you the first element of a list. For example, car of (a b c) is a and car of ((a a) (b b) (c c)) is (a a). The way you write this in LISP is
(car (' (a b c)))
(car (' ((a a) (b b) (c c))))
The first expression has value a, and the second expression has value (a a).
The reason you need the quote function ' in (car (' (a b c)))
is to indicate that the argument is literally (a b c), which would otherwise
be taken to mean that the function whose name is a should be applied to the value of
the variables b and c, which is not what we want.
In other words, quote separates the program from the data, it indicates where
evaluation stops.
Next comes cdr, which gives you the rest of a list, in other words, what is left when the first element is omitted. For example, cdr of (a b c) is (b c) and cdr of ((a a) (b b) (c c)) is ((b b) (c c)). So the LISP expressions
(cdr (' (a b c)))
(cdr (' ((a a) (b b) (c c))))
evaluate to
(b c)and to
((b b) (c c))respectively. And if you take the cdr of a list with only one element, then you are left with the empty list (). For example,
(car (' (abc)))
(cdr (' (abc)))
give, respectively, the values
abcand
()
The next primitive function for dealing with lists is cons, which reassembles lists that have been broken in two using car and cdr. In other words, cons is the inverse of car and cdr. For example,
(cons a (' (b c)))
gives (a b c) and
(cons (' (a a)) (' ((b b) (c c))))
gives ((a a) (b b) (c c)).
Note that in our first example we wrote a instead of (' a) because
a evaluates to a unless we are inside a defined function in which
we are using a as the name of an argument, in which case a gives us
the value of that argument.
Similarly,
(cons a (cons b (cons c nil)))gives us (a b c). This is called ``consing up a list,'' and could also be written
(cons a (cons b (cons c ())))or
(cons (' a) (cons (' b) (cons (' c) (' ()))))
So now we have a way to break a list into pieces, and to put the pieces back together again.
Then there are two predicates for examining S-expressions, atom and equal =. Atom tells us if an S-expression is an atom or not, and equal tells us if two S-expressions are identical. For example.
(atom (' a))
gives true,
(atom (' (a b c)))
is false, and
(atom (' ()))
(atom nil)
are both true.
Similarly,
(= (' (a b c)) (' (a b c)))
and
(= (' (a b c)) (' (a x c)))
give true and false, respectively.
Next there is the if-then-else pseudo-function if for using a predicate to choose between two expressions for a value. For example,
(if true X Y) (if false X Y)give X and Y, respectively. If-then-else is a pseudo-function, not a real function, because it only evaluates two of its three arguments. The unselected argument is not evaluated. The predicate is always evaluated. The other pseudo-function is quote, which never evaluates its one argument.
We've almost finished with the heart of pure LISP! We've seen quote ', car, cdr, cons, atom, equal =, and if-then-else if. What's missing is lambda, which is used for defining functions that are not supplied as primitive functions. For example, let's define the function that makes a list with its two arguments in reverse order:
((' (lambda (x y) (cons y (cons x nil)))) a b)
This gives us the value (b a). How does this work? Well, a defined function is
a triple of the form
(lambda (x y...) body)consisting of a list of argument names followed by the body of the function, which is an expression which gives the value of the function. Most important, note that within the body of the function the argument names are bound to the actual values of the arguments. These bindings are temporary, they only apply within the function body. So within
(cons y (cons x nil))x is bound with a and y is bound with b.
Here we're literally giving the function definition, it's quoted, but we could also give an arbitrary expression whose value is the function definition. For example, if f is bound to
(lambda (x y) (cons y (cons x nil)))then
(f a b)gives (b a).
Now here is a real LISP program. I'll show you how to append two lists. For example, if we append
(a b c)and
(d e f)we'll get
(a b c d e f)Let's call this function F. So we need to bind F to the definition of this function. And how can we define it? Well, recursively, like this. To append two lists x and y, first look at x. If x is an atom, then x is the empty list, and the result is simply the second list y. Otherwise, the result is obtained by consing the first element of x with the result of appending the rest of x with y. So we want to define F to be
(lambda (x y) (if (atom x) y (cons (car x) (F (cdr x) y))))Here's how we do it:
((' (lambda (F) (F (' (a b c)) (' (d e f)))))
(' (lambda (x y) (if (atom x) y (cons (car x) (F (cdr x) y)))))
)
This operation occurs so frequently, that we provide
the let-be-in macro[-operation] let which does this for us:
(let (F x y) (if (atom x) y (cons (car x) (F (cdr x) y)))
(F (' (a b c)) (' (d e f)))
)
Let is just syntactic sugar, it's just a convenient abbreviation for the more complicated
S-expression using two lambda's.
There's also a simpler version of let, which is used to assign a value to a variable. That's let x be v in e, which is written like this:
(let x v e)and expands to this:
((' (lambda (x) e)) v)
That's it! This is really everything essential in traditional LISP! For example, you don't need to have positive integers, you could define them as lists of bits and then program out addition, multiplication and exponentiation of binary numbers! And every expression that used an arithmetic operation would have to contain its definition, they would have to be repeated again and again.
So it would be very convenient to have a way of remembering function definitions permanently, and also to have primitive functions for doing decimal arithmetic. And there are far too many parentheses! So let's make our LISP more practical.
Here are the number of arguments which are understood: ', 1; car, 1; cdr, 1; cons, 2; atom, 1; =, 2; if, 3; lambda, 2; let, 3.
Also, to make life a little easier, we will make the quote function ' into a token delimiter like blank and parentheses, so we can always jam a quote against something without ambiguity. [Like quote, double-quote " is a delimiter, and can be jammed right up against something.]
So now we just write
cons a '(b c)to denote
(cons a (' (b c)))
whose value is the list (a b c).
And our list append example simplifies to this:
('lambda (F) (F '(a b c) '(d e f))
'lambda (x y) if atom x y
cons car x (F cdr x y)
)
If we use the let-be-in macro, this expression gets even simpler. It becomes:
let (F x y) if (atom x) y
cons car x (F cdr x y)
(F '(a b c) '(d e f))
Two other convenient macros that are provided are cadr and caddr: they expand into car of cdr and into car of cdr of cdr, respectively. Thus
car '(a b c d) cadr '(a b c d) caddr '(a b c d)expand to
(car (' (a b c d)))
(car (cdr (' (a b c d))))
(car (cdr (cdr (' (a b c d)))))
and evaluate to a, to b, and to c, respectively.
And let's throw in decimal numbers, unsigned integers, 0, 1, 2, ... And we'll provide two-argument addition +, subtraction -, multiplication *, and exponentiation ^, and extend equal = to also compare integers. E.g., the M-expression
+ * 2 3 * 4 5denotes the S-expression
(+ (* 2 3) (* 4 5))whose value is 26. So we are using prefix notation instead of the usual infix notation for arithmetic operators. We also throw in less-than <, greater-than >, less-than-or-equal <=, and greater-than-or-equal >=. And two one-argument primitive functions for converting between base 2 and base 10: base10-to-2 and base2-to-10.
And let's also add define, with two arguments, which is just like let-be-in, except that it gives a permanent binding, not a temporary one, and never evaluates any of its arguments. Define is not really in the language; we should always use let-be-in, which is really lambda binding, but it is convenient to allow define at the highest level of the interpreter so that definitions don't have to be repeated within an interpreter run. Define only works if it is the top level function given to the interpreter, it cannot be inside another expression.
So now we have something that begins to look like a fairly realistic programming language. Here's how factorial looks. Here's 5 factorial; 5! = 5 by 4 by 3 by 2 by 1 = 120:
define (factorial n)
[if n = 0, then 1, otherwise n times (n-1)!]
if = n 0 1 * n (factorial - n 1)
[try it!]
(factorial 5)
And the stuff in brackets are comments, which we had to have some way of including.
When you run this, the LISP interpreter will first indicate that
factorial is bound to
(lambda (n) (if (= n 0) 1 (* n (factorial (- n 1)))))and then that the value of (factorial 5) is 120.
At this point you should go to my LISP interpreter web page at one of these two URL's and try out all of this:
http://www.cs.umaine.edu/~chaitin/unknowable/lisp.html http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/lisp.htmlJust type M-expressions into the upper window, click on run, and the corresponding S-expressions and their values will appear in the lower window.
We'll be dealing with very long bit strings, which we'll represent as very long lists of 0's and 1's. These will be the self-delimiting binary programs that we'll feed to my universal Turing machine, and the size of these binary programs will give us our complexity measure H(x).
I showed you how to append two lists, but having this as a defined function is too inefficient. So we add a primitive function append that gives us the combined list if it's given two lists. We'll use append to assemble long binary programs from pieces. And the pieces will usually be produced by another new primitive function, bits, that converts the character string representation of an S-expression into an ASCII bit string, eight bits per character, plus eight more bits for an unprintable UNIX newline control character at the end.
And we'll want to count how long the resulting bit strings are. So for that we add a primitive function length that returns the number of elements in a list. If this list is a bit string, a list of 0's and 1's, that will be the number of bits in the bit string. There's also size, which gives us the number of characters in the character string representation of an S-expression. That's very useful if we're looking at the LISP program-size complexity of x, which is the number of characters in the smallest S-expression that has value x, which we did in The Unknowable and The Limits of Mathematics, but which we won't be doing in this book. Here we're only interested in the real thing: in the size in bits of the smallest self-delimiting binary program for x.
Next there's an identity function, display, which has the side-effect of displaying its argument. This is normally used for debugging, but we'll also use it to output infinite sets instead of only producing one result, the value of an expression. In other words, display will be used to enable non-halting LISP expressions to generate infinite sets of S-expressions as output.
Next there's eval, which may be thought of as the inverse of quote. What it really does is enable us to run LISP code that we've generated somehow. The argument of eval is evaluated in a fresh environment, in which each atom is bound to itself and nil is bound to (). If you eval an unending LISP expression then you lose control, you never get a result back. The way to deal with this is called try, which performs a time-limited evaluation and captures any displays. It also has another very important role, which is to provide the LISP expression that it's running with binary data on the side.
Try has three arguments: a time limit α, an expression to be evaluated β, and a list of 0's and 1's γ. The number α is either a time limit for evaluating β, or it's no-time-limit indicating that there is no time limit. As the S-expression β is evaluated, the arguments of all its display's are captured, and β can read in its binary data γ: either bit by bit using the zero-argument primitive function read-bit, or a complete S-expression at a time using the zero-argument primitive function read-exp. Read-exp reads in eight-bit ASCII characters until it finds a UNIX newline, and returns the S-expression whose character string representation it has read. Read-bit and read-exp both fail if they run off the end of the binary data γ. In that case the (try α β γ) fails due to running out of data. It can also fail by running out of time.
The value that try returns is a triple. The first element will either be success or failure. The second element will either be the value of β if the try was a success, or it will be out-of-time if the time limit α was exceeded or out-of-data if β ran out of binary data. These are the only two possible failure modes, because otherwise my LISP has very permissive semantics and will always go ahead and do something. And the third element of the value of a try is the chronological list of captured display's.
Note that like eval, try evaluates its argument β in a fresh environment. However, evaluating the argument of eval may have the side effect of reading in part of the current binary data (the binary data in the immediately containing try), while the argument β of a try reads in data from its own binary data γ and cannot touch any other try's binary data. [Other side-effects of an eval: eval may also do display's, which try cannot.]
Finally, let's throw in another identity function debug that also displays its argument, but which is not seen by the official display/try mechanism in which display throws intermediate results and try catches them.
Try is the real difference between my LISP and a normal LISP; it's what I had to add to LISP to do algorithmic information theory. The fundamental semantic notion in normal LISP is evaluation, which maps an S-expression and the current bindings into its value. In my LISP the fundamental semantic notion of evaluation maps an S-expression and associated binary data plus the current bindings into its value; the argument of evaluation is a triple, not a pair.
And the key self-delimiting feature of read-bit and read-exp needed in order to implement algorithmic information theory properly is that they are not allowed to run off the end of the binary data γ and peacefully return an ``end-of-file'' indication. Instead they abort, and they abort the containing S-expressions with them, which percolates up to the immediately containing try.
Note that it is very important that try's and eval's can be nested to arbitrary depth; if two try's are nested the most constraining time limit is in effect. And how are these time limits measured? Well, roughly speaking, they're measured via the interpreter push-down stack depth, as the depth of nested subroutine calls or nested function definitions in the LISP evaluation. More precisely (thanks to R.M. Solovay), the time limit bounds the number of pending re-evaluations due to eval, to try, and to defined functions (lambda expressions). [Solovay pointed out to me that my original formulation of try in the first printing of my 1987 Cambridge University Press monograph was not quite right; subsequent printings corrected this.] The important point is that if there is a time limit, then a try must terminate, either with the correct value or with a failure indication. Thus it is always perfectly safe to do a time-limited try.
Well that's all there is, it's all you need to run algorithmic information theory on the computer! In the next chapter I'll show you how.
cadr try no-time-limit 'eval read-exp pand then to
(car (cdr (try no-time-limit (' (eval (read-exp))) p)))
Try to figure out what this does;
it plays a key role in the next chapter. This macro is only provided in the Java applet
version of my LISP interpreter. Fix the Mathematica and the C versions of the interpreter so that
they also have run-utm-on. You can find the source code at these URL's:
http://www.cs.umaine.edu/~chaitin/lisp.m http://www.cs.umaine.edu/~chaitin/lisp.c http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.m http://www.cs.auckland.ac.nz/CDMTCS/chaitin/lisp.c
! p & p q | p qexpand to
(if p false true) (if p q false) (if p true q)respectively.
http://www.cs.umaine.edu/~chaitin/unknowable/lisp.html http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/lisp.htmlThe Java source code for this applet is at these URL's:
http://www.cs.umaine.edu/~chaitin/unknowable/lisp.java http://www.cs.umaine.edu/~chaitin/unknowable/Sexp.java http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/lisp.java http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unknowable/Sexp.java
[Was-read is an experimental primitive function that is only in the Java applet version of the interpreter; see Exercise 7 at the end of the next chapter.]