Math 61 -- Notes LISP

Notes LISP

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

[Return to Math 61 Homepage | Return to Notes Listing Page]

Online LISP Tutorials/References
LISP: Preliminaries
Basic Data Structure
S-Expressions
List Notation
More List Notations Examples
LISP List Operations
Using LISP Functions
Examples
Brief Introduction to LISP: Common LISP Dialect

Online LISP Tutorials/References

LISP: Preliminaries

LISP is an acronym for LISt Processing language.
It was developed by McCarthy at MIT in 1959-60.
It is related to the lambda-calculus developed by Curry and Church in the late 1930's.
LISP was for many years "THE" language of those who worked in Artificial Intelligence.
LISP has led to several "children" languages, among which is SCHEME, which is (or has been) used as several universities as the first computer languages taught.

Major Points

LISP is interactive.
The basic data structure is a LIST!
Instructions mirror mathematical functional (prefix) notation.
Everything has a value (i.e. every complete expression returns a values).
No distinctions are made between program (instructions) and data.

For an article on LISP, cf. MAA Monthly, 9:1 (January 1984), pp 32-42, "What is LISP?" by Wand.

Basic Data Structure

The basic data structure is a list of nodes.

Each node can store a pointer to another node or to an "atom" or to another list.

An ATOM is a literal (i.e. string of letters and numbers)
or an integer (or large integer)
or a real number
or NIL.
A DOTTED PAIR (symbolically) is node of two fields which points to other nodes (or atoms), and is used to construct a list in LISP.

A node is represented as a dotted pair of atoms enclosed in parentheses.

	      |
	      |
 	 _____V_____		<==>      (X.Y)
	 |    |	   |
	 |/___|___\|			where X and Y are
    ____/	   \____		"atoms."
    |X |            | Y|
    |__|            |__|

S-Expressions

An S-EXPRESSION is any atom
or dotted pair of s-expressions
or list of s-expressions.

List Notation

LISP lists are equivalently interpreted as trees, rotated 45^o (counter-)clockwise.

I.e., in C++, we would write (diagram) a list as:

     _______     _______     _______
    |   |   |   |   |   |   |   |  /|
--->| X |  -|-->| Y |  -|-->| Z | / |
    |___|___|   |___|___|   |___|/__|

In LISP, we would diagram this (more correctly) as:

     _______     _______     _______
    |   |   |   |   |   |   |   |   |    _____
--->|   |  -|-->|   |  -|-->|   |  -|-->|_NIL_|
    |_|_|___|   |_|_|___|   |_|_|___|
      |           |           |
     _V_         _V_         _V_
    |_X_|       |_Y_|       |_Z_|

and this structure is a tree, i.e., when you rotate it clockwise 45^o, you get a tree with no contents in the interior (non-leaf) nodes.

	     |
	    / \
          X  / \
	    Y  / \
	      Z   nil

This structure is written as (X Y Z) or (in full "dot"-notation) (X.(Y.(Z.NIL))) NOTE: Whenever possible, the LISP interpreter will translate the longer "dot"-notation expressions into simpler "list" notation expressions. It should also be noted that each element of a list can itself be a list!

More List Notation Examples

(Or, how to translate from LIST NOTATION to DOTTED PAIR NOTATION by using the diagrams as the intermediate step).

EXAMPLE 1 - (X Y)







EXAMPLE 2 - ((X Y ) Z)















EXAMPLE 3 - (X.((Y.(Z.NIL)).NIL))

LISP List Operations

In LISP, the fundamental operations are related to lists. There are three basic functions, two of which subdivide a list and the third constructs (parts of) a list.

If we examine any list, one operation that we can imagine is the operation which removes the head of a list from the list (like POPping a stack implemented as a linked list). Another operation would be to take a list and give the rest (or tail) of the list minus the head node. A third operation would take a node and join it to another node by constructing a dotted pair node.

The three LISP functions which correspond to these operations are CAR, CDR, and CONS.

(In many LISP interpreters, commands may be entered either in UPPERCASE or lowercase characters.)

(CAR list) 	[Contents of Address Register - cf. IBM 704]
		returns first element of the list.

(CDR list)	[Contents of Decrement Register]
		returns tail of the list AS A LIST,
		i.e. the rest of the list with the CAR removed.
		[pronounced "could-ur"]

(CONS s-exp s-exp)	returns a new node, i.e. dotted pair,
		out of the two s-expressions given. 
		[abbreviation of CONStruct]

E.g.,
		CAR (A B C) --> A
		CDR (A B C) --> (B C)
		CONS A, (B C) --> (A.(B C)) = (A B C)

Since CAR and CDR are used often in conjunction with each other, there is a standard way to abbreviate compositions of these functions:

(C....R list)	where .... can be either A's or D's is the
		standard abbreviation for repeated uses
		of CAR and CDR.

Using Kyoto Common Lisp on the math HP Unix server, a maximum of five intermediate A's or D's are permitted between the initial C and final R.

For example,

        (CDAR list) <=> (CDR (CAR list))
	(CDDDR list) <=> (CDR (CDR (CDR list)))

Using LISP Functions

First, a couple of useful functions:

        +          <==>	addition
	*          <==>	multiplication
	SETQ	   <==>	assignment of values, or :=
	QUOTE or ' <==>	leaves the following s-expression
			UNevaluated, i.e., a literal.

To use functions in LISP, one write the desired expression:

in PREFIX order
as a LIST (in the more common LISP mode).

Thus, data in LISP is written as lists, and program operations are also written as lists.

LISP is free format, so that it is up to the programmer to determine how much or how little is put on a line and whether or not to use indentation. As a matter of style, it is always good to indent substructures, and put new expressions on new lines.

Examples

	(CAR '(A B C))
	(+ 2 3)
	(* 3 4)
	(SETQ A 2)

One can always "nest" functions, e.g.,

	(SETQ A (+ (* 2 3) (* 5 2)))

Brief Introduction to LISP -- Common LISP Dialect

Using Kyoto Common LISP (as on the math HP Unix server), integer constant are entered without a decimal point (or with a decimal point and no following digits). A real (float) number needs a decimal point and at least one digit to the right of the decimal point.

Arithmetic Functions:

(+ x y)	returns x+y		[OTHER LISPs may use PLUS]
(* x y)	returns x*y		[OTHER LISPs may use TIMES]
(- x y)	returns x-y		[OTHER LISPs may use DIFFERENCE]
(/ x y)	returns x/y		[OTHER LISPs may use QUOTIENT]

NOTE: With Kyoto LISP, if both x and y are integers, the result from a division is given as an integer or as an integer fraction. To convert the value to a real number, one needs to multiply it by 1.0 or use real numbers as arguments.

(1+ x)	returns x+1		[OTHER LISPs may use ADD1]
(1- x)	returns x-1		[OTHER LISPs may use SUB1]

(SETQ atom value)   set atom to value and returns value

(QUOTE s-exp) or 's-exp    forces NON-evaluation of s-exp,
		i.e. s-exp is retained in literal form.

List Functions:

(LIST a b c ... d)	returns the list (a b c ... d)

(LAST list)	returns last dotted pair of list

(LENGTH list)	returns the length of list

(NCONC a b)	concatenates a and b together into one list,
		destroying the old a and b.

(APPEND a b)	creates a new list which is the concatenation
		of a and b without changing a and b.

(REVERSE list)	creates a new list which is the reverse of list.

(NREVERSE list)	reverses pointers in old list -- old list is
		destroyed.

(RPLACA list y)	replaces (CAR list) with y.

(RPLACD list y)	replaces (CDR list) with y.

Predicate (Boolean/Logical) Functions: (all return NIL or a non-NIL value [usually T])

(ODDP n)	returns T if n is an odd integer.

(ATOM a)	returns T if a is an atom, i.e. not an
		s-expression or a list.

(NUMBERP a)	returns T if a is a number.

(ZEROP n)	returns T if n = 0.

(PLUSP n)	returns T if n > 0.

(NULL a)	returns T if a = NIL.

(MEMBER x list)	if x is an element of list, this returns a
		list in which x is the first element.

(EQ x y)	returns T if x and y are EXACTLY the same object, 
                i.e., if they point to the same memory locations.

(EQUAL x y)	returns T if x and y have the same structure
		(e.g., same appearance when printed out).

Recently Introduced Operators

(> x y)         returns T if number x is greater than number y

(>= x y)        returns T if number x is greater than or equal to
        	number y

(< x y)         returns T if number x is less than number y

(<= x y)        returns T if number x is less than or equal to
        	number y

(= x y)		return T if number x and y are equal

Special Functions:

(EVAL a)	interprets (i.e. evaluates) a (an s-expression)
		as if it were a top level command.

Control:

-->Generalized IF..THEN..ELSE/CASE/Conditional:

(COND (condition1 action1)
      (condition2 action2)
      (condition3 action3)
      ...
      (condition-m action-m) )

The first condition that evaluates to T has its action performed-- all others are ignored.

The last condition can be replaced by T or (COMMON LISP) omitted.
COMMON LISP allows more than one action per condition.
NOTE: Parentheses are usually needed for the CONDITION and ACTION as required by the expressions,
e.g. (EQ A B) or (SETQ C 3)--a second set surrounds each condition-action line.

-->Function definition:

(DEFUN function_name input_var_list action)

This defines a new function. Equivalent to DEFINE or DEF in other implementations. COMMON LISP allows more than one action here also--merely list them in order.

"Ancient" LISP Constructs:

(PROG local_variable_list action1 action2 ... action-m)

One way (older LISP) of associating many actions where only one was allowed by definition. This somewhat imitates the BEGIN...END construction in Pascal which is needed where the language only allows one statement, and more than one is desired by the code. PROG returns NIL as its value unless one uses a RETURN function inside (see next entry).

(RETURN a)	returns the value of  a  as the value of the
		PROG expression in which it is found.  If RETURN
		is NOT used within a PROG construction, then the
		final value returned by the PROG is a NIL.

(GO loop)	GO TO statement.  loop is the label placed
		immediately before the action referred to.
		GO can be used ONLY within a PROG expression.

Modern LISP Constructs:

Generalized DO

   (DO (
         (var_1  init_val_1  step_1)
         (var_2  init_val_2  step_2)
	 ...
         (var_n  init_val_n  step_n)   )

       ( end_test
            end_action_1
	    end_action_2
	    ...
	    end_action_k
	    return_value   )
       body_action_1
       body_action_2
       ...
       body_action_m
       )

This DO construct is common in most dialects of MACLISP and Common LISP. It is a looping structure which eliminates the need for the PROG and GO structures of "ancient" LISP.

The DO construct consist of three major sections:

The first section initializes and changes local variables. Each variable var_i is assigned an initial value init_val_i and, in subsequent iterations in the loop, is assigned the value determined by step_n.
The second section starts with a logical expression. If the expression evaluates to a non-NIL value, all the end_actions are performed (if any) and the expression returns the value determined by return_value.
The third section consists of action expression(s) to be done each time through the loop.

DOTIMES loop

   (DOTIMES 
        (loop_var  end_value  opt_return_value)
	body_action_1
        body_action_2
        ...
        body_action_m
    )

This DOTIMES construct is available in most dialects of Common LISP. It is a counted loop in which the actions indicated in the body of the loop are performed the number of times determined by the limit indicated for the loop_var. When the actions in the loop are being executed, the value of loop_var begins with 0 and goes up to but does not include end_value. As soon as loop_var reaches the value of end_value the structure is exited with the value of the structure being that of opt_return_value (which is optional).

Generalized LOOP

LOOP is a generic infinite loop available in most recent versions of Common LISP. To exit, one must also include an appropriate clause, such as a WHERE action with a return value.

The WHERE construct's structure is as follows:

     (WHERE predicate_expression (RETURN return_value))

The predicate_expression could be any test that evaluates to T or NIL.

The LOOP contruct itself has this structure:

     (LOOP
       body_action_1
       body_action_2
       ...
       body_action_m
      )

The LOOP executes all body_actions in the order listed repeatedly. One of the body_actions must be some sort of test (such as the WHERE) in order to break out of the loop.

Input/Output Functions:

(PRINT a)	prints the value of a (on the terminal)

(TERPRI)	induces a carriage return (on the terminal)

To OPEN file FOO.LSP in your directory and prepare it as an INPUT file:

(SETQ IN1 (OPEN "FOO.LSP" :DIRECTION :INPUT))	where IN1 can
be any local atom.

Then to READ from file FOO.LSP, use:

(READ IN1)	reads one s-expression

(READ-CHAR IN1)	reads one character

To CLOSE the file:

(CLOSE IN1)

To OPEN file BAR.LSP in your directory and prepare it as an OUTPUT file:

(SETQ OUT1 (OPEN "BAR.LSP" :DIRECTION :OUTPUT))

Then to PRINT to BAR.LSP, use:

(PRINT s-exp OUT1)	prints in form which can later be used by
		READ with a preceding NEWLINE and followed by SPACE
		(i.e., with escape characters).

(PRIN1 s-exp OUT1)	prints in form which can later be used by
		READ without any surrounding spaces (i.e., with escape
		characters).

(PRINC s-exp OUT1)	like PRIN1 except special characters are
		printed without other marks (i.e., NO escape
		characters). 

(TERPRI OUT1)	forces a carriage return in file OUT1.

Property Lists:

(SETF (GET x z) y)	(gives x the z-property value of y.
		[OTHER LISPs may use (PUTPROP x y z)]
		If x and z are atoms (used as names), they
		should be preceeded by a quote mark.

(GET x z)	gets the value of the z-property of x.
		If x and z are atoms (used as names), they
		should be preceeded by a quote mark.

Additional Information:

-->TO LOAD in a file of LISP functions, say, FOO.LSP

(LOAD "FOO.LSP")

-->COMMENTS: use ; and rest of the line is ignored.

-->TO EXIT:

(BYE)

-->TO RESET after errors:

:q

-->To force a GARBAGE COLLECTION:

(GBC NIL)    (to collect cells only)  --or--
(GBC T)      (to collection everything)