5. THE PROGRAM FEATURE

The LISP 1.5 program feature allows the user to write an Algol-like program containing LISP statements to be executed.

An example of the program feature is the function length, which examines a list and decides how many elements there are in the top level of the list. The value of length is an integer.

Length is a function of one argument l. The program uses two program variables u and v, which can be regarded as storage locations whose contents are to be changed by the program. In English the program is written.

        This is a function of one argument l. 
                It is a program with two program variables u and v. 
        Store 0 in v. 
        Store the argument l in u. 
A     If u contains NIL, then the program is finished, 
                and the value is whatever is now in v. 
        Store in u, cdr of what is now in u. 
        Store in v, one more than what is now in v. 
        Go to A.

We now write this program as an M-expression, with a few new notations. This corresponds line for line with the program written above.

length[l] = prog[[u;v]; 
        v:=0; 
        u:=l; 
A     [null[u] $\rightarrow$return[v]]; 
        u:= cdr[u]; 
        v:= v+1; 
        go [A]]

Rewriting this as an S-expression, we get the following program.

DEFINE (( 
(LENGTH (LAMBDA (L) 
(PROG (U V) 
        (SETQ V 0) 
        (SETQ U L) 
A     (COND ((NULL U) (RETURN V))) 
        (SETQ U (CDR U)) 
        (SETQ V (ADD1 V)) 
        (GO A) )))     )) 
LENGTH ((A B C D)) 
LENGTH (((X . Y) A CAR (N B) (X Y Z)))

The last two lines are test cases. Their values are four and five, respectively. The program form has the structure -

(PROG, list of program variables, sequence of statements and atomic symbols...) An atomic symbol in the list is the location marker for the statement that follows. In the above example, A is a location marker for the statement beginning with COND.

The first list after the symbol PROG is a list of program variables. If there are none, then this should be written NIL or ( ). Program variables are treated much like bound variables, but they are not bound by LAMBDA. The value of each program variable is NIL until it has been set to something else.

To set a program variable, use the form SET. To set variable PI to 3.14 write (SET (OUOTE PI) 3.14). SETQ is like SET except that it quotes its first argument. Thus (SETQ PI 3.14). SETQ is usually more convenient. SET and SETQ can change variables that are on the a-list from higher level functions. The value of SET or SETQ is the value of its second argument.

Statements are normally executed in sequence. Executing a statement means evaluating it with the current a-list and ignoring its value. Program statements are often executed for their effect rather than their value.

GO is a form used to cause a transfer. (GO A) will cause the program to continue at statement A. The form GO can be used only as a statement on the top level of a PROG or immediately inside a COND which is on the top level of a PROG.

Conditional expressions as program statements have a useful peculiarity. If none of the propositions are true, instead of an error indication which would otherwise occur, the program continues with the next statement. This is true only for conditional expressions that are on the top level of a PROG.

RETURN is the normal end of a program. The argument of RETURN is evaluated, and this is the value of the program. No further statements are executed.

If a program runs out of statements, it returns with the value NIL. The program feature, like other LISP functions, can be used recursively. The function rev, which reverses a list and all its sublists is an example of this.

rev[x] = prog[[y;z]; 
A     [null[x] $\rightarrow$return[y]; 
        z:= car[x]; 
        [atom[z] $\rightarrow$go[B]]; 
        z:= rev[z]; 
B     y:= cons[z,y]; 
        x:= cdr[x] 
        go[A]]

The function rev will reverse a list on all levels so that

rev[(A ((B C) D))] = ((D (C B)) A)