1.4 The LISP Meta-language

We have introduced a type of data called S-expressions, and five elementary functions of S-expressions. We have also discussed the following features of the metalanguage.

1. Function names and variable names are like atomic symbols except that they use lower case letters.

2. The arguments of a function are bound by square brackets and separated from each other by semicolons.

3. Compositions of functions may be written by using nested sets of brackets. These rules allow one to write function definitions such as

        third[x]=car[cdr[cdr[x]]]

This function selects the third item on a list. For example,

        third[(A B C D))=C

third is actually the same function as caddr.

The class of functions that can be formed in this way is quite limited and not very interesting. A much larger class of functions can be defined by means of the conditional expression, a device for providing branches in function definitions.

A conditional expression has the following form.

${[}p_{1}\rightarrow e_{1};p_{2}\rightarrow e_{2};\ldots ;p_{n}\rightarrow e_{n}{]},$

where each $p_{i}$ is an expression whose value may be truth or falsity, and each $e_{i}$ is any expression. The meaning of a conditional expression is: if $p_{1}$ is true, then the value of $e_{1}$ is the value of the entire expression. If $p_{1}$ is false, then if $p_{2}$ is true the value of $e_{2}$ is the value of the entire expression. The $p_{i}$ are searched from left to right until the first true one is found. Then the corresponding $e_{i}$ is selected. If none of the pi are true, then the value of the entire expression is undefined.

Each $p_{i}$ or $e_{i}$ can itself be either an S-expression, a function, a composition of functions or may itself be another conditional expression.

Example

[eq[car[x];A] $\rightarrow$cons[B;cdr[x]]; T $\rightarrow$x]

The atomic symbol T represents truth. The value of this expression is obtained if one replaces car of x by B if it happens to be A, but leaving x unchanged if car of it is not A.

The main application of conditional expressions is in defining functions recursively.

Example

ff[x]=[atom[x] $\rightarrow$x; T $\rightarrow$ff[car[x]]]

This example defines the function ff which selects the first atomic symbol of any given expression. This expression can be read. If x is an atomic symbol, then x itself is the answer. Otherwise the function ff is to be applied to car of x.

If x is atomic, then the first branch which is "x" will be selected. Otherwise, the second branch "ff[car[x]]" will be selected, since T is always true.

The definition of ff is recursive in that ff is actually defined in terms of itself. If one keeps taking car of any S-expression, one will eventually produce an atomic symbol; therefore the process is always well defined.

Some recursive functions may be well defined for certain arguments only, but infinitely recursive for certain other arguments. When such a function is interpreted in the LISP programming system, it will either use up all of the available memory, or loop until the program is halted artificially.

We shall now work out the evaluation of ff[((A . B) . C)]. First, we substitute the arguments in place of the variable x in the definition and obtain

ff[((A . B) . C)]= 
        [atom[((A . B) . C)] $\rightarrow$((A . B) . C); 
        T $\rightarrow$ff[car[((A . B) . C)]]]

but ((A . B) . C) is not atomic, and so we have

        = [T $\rightarrow$ff[car[((A . B) . C)]]] 
        = ff[car[((A . B) . C)]] 
        = ff[(A . B)]

At this point, the definition of ff must be used recursively. Substituting (A . B) for x gives

        = [atom[(A . B)] $\rightarrow$(A . B); T $\rightarrow$ff[car[(A . B)]]] 
        = [T $\rightarrow$ff[car[(A . B)]]] 
        = ff[car[(A . B)]] 
        = ff[A] 
        = [atom[A] $\rightarrow$A; T $\rightarrow$ff[car[A]]] 
        = A

The conditional expression is useful for defining numerical computations, as well as computations with S-expressions. The absolute value of a number can be defined by

         $\vert$x $\vert$ = [x<0 $\rightarrow$ -x; T $\rightarrow$x].

The factorial of a non-negative integer can be defined by

        n! = [n=0 $\rightarrow$l; T $\rightarrow$n $*$[n-1]!]

This recursive definition does not terminate for negative arguments. A function that is defined only for certain arguments is called a partial function.

The Euclidean algorithm for finding the greatest common divisor of two positive integers can be defined by using conditional expressions as follows:

gcd[x;y]=[x>y $\rightarrow$ gcd[y,x]; 
        rem[y;x]=0 $\rightarrow$ x; 
        T $\rightarrow$gcd[rem[y;x];x]]

rem[u;v] is the remainder when u is divided by v.

A detailed discussion of the theory of functions defined recursively by conditional expressions is found in "A Basis for a Mathematical Theory of Computation" by J. McCarthy, Proceedings of the Western Joint Computer Conference, May 1961 (published by the Institute of Radio Engineers).

It is usual for most mathematicians - exclusive of those devoted to logic - to use the word "function" imprecisely, and to apply it to forms such as $y^{2}+x$. Because we shall later compute with expressions that stand for functions, we need a notation that expresses the distinction between functions and forms. The notation that we shall use is the lambda notation of Alonzo Church.^1.1

Let f be an expression that stands for a function of two integer variables. It should make sense to write $f{[}3;4{]}$ and to be able to determine the value of this expression. For example, $sum{[}3,4{]}=7$. The expression $y^{2}+x$ does not meet this requirement. It is not at all clear whether the value of $y^{2}+x{[}3;4{]}$ is 13 or 19. An expression such as $y^{2}+x$ will be called a form rather than a function. A form can be converted to a function by specifying the correspondence between the variables in the form and the arguments of the desired function.

If $Н$ is a form in the variables $x_{1};\ldots ;x_{n}$, then the expression $\lambda {[}{[}x_{1};\ldots ;x_{n}{]};Н{]}$ represents the function of $n$ variables obtained by substituting the $n$ arguments in order for the variables $x_{1};\ldots ;x_{n}$, respectively. For example, the function $\lambda {[}{[}x;y{]}; y_{2}+x{]}$ is a function of two variables, and $\lambda {[}{[}x;y{]};y^{2}+x{]}{[}3;4{]}=42+3=19$. $\lambda {[}{[}y;x{]};y^{2}+x{]}{[}3;4{]}=32+4=13$.

The variables in a lambda expression are dummy or bound variables because systematically changing them does not alter the meaning of the expression. Thus $\lambda {[}{[}u;v{]}; v^{2}+u{]}$ means the same thing as $\lambda {[}{[}x;y{]}; y^{2}+x{]}$.

We shall sometimes use expressions in which a variable is not bound by a lambda. For example, in the function of two variables $\lambda {[}{[}x;y{]}; x^{n}+y^{n}{]}$ the variable $n$ is not bound. This is called a free variable. It may be regarded as a parameter. Unless n has been given a value before trying to compute with this function, the value of the function must be undefined.

The lambda notation alone is inadequate for naming recursive functions. Not only must the variables be bound, but the name of the function must be bound, since it is used inside an expression to stand for the entire expression. The function ff was previously defined by the identity

        ff[x]=[atom[x] $\rightarrow$x; T $\rightarrow$ff[car[x]]].

Using the lambda notation, we can write

        ff= $\lambda$[[x]; [atom[x] $\rightarrow$x; T $\rightarrow$ff[car[x]]]]

The equality sign in these identities is actually not part of the LISP meta-language and is only a crutch until we develop the correct notation. The right side of the last equation cannot serve as an expression for the function ff because there is nothing to indicate that the occurrence of ff inside it stands for the function that is being defined.

In order to be able to write expressions that bear their own name, we introduce the label notation. If $\epsilon$ is an expression, and a is its name, we write $label{[}a; \epsilon {]}$.

The function ff can now be written without an equal sign:

        label[ff; $\lambda$[[x]; [atom[x] $\rightarrow$x; T $\rightarrow$ff[car[x]]]]]

In this expression, x, is a bound variable, and ff is a bound function name.