__CS320 LISP__

On most servers and workstations we have a small LISP interpreter called XLISP. On Some servers and on the NECs we have an industry standard Common LISP system called Franz Lisp. This is more complex than XLISP. This is a quick introduction to XLISP with just enough LISP for CS320 laboratory sessions. Nearly all of the LISP works with the Franz Lisp on the new workstations. The details of editting and loading fucntions in Franz Lisp are different.

**Using XLISP**

**Startup**

To start XLISP type in the UNIX command

lisp

or

lisp *filename*...

LISP reads and executes the files. The user starts interacting with LISP. LISP takes over the shell window. The
user inputs LISP expressions. The *interpreter* that reads them and evaluates them. It responds to every expression
by producing a *value:*

* LISP.input*::=#*expression*.

* LISP.output*::=#*value*.

**Stopping** **XLISP**

The interpreter quits at an end-of-text (CTRL/D) input or when it tries to evaluate the expression

(exit)

Notice that the parentheses are needed. Otherwise LISP does not see an operation but a variable with no value!

**Expressions**

Almost all *expressions* apply an operator to some arguments and are written like this:

(*operator* *arguments*)

A simple example is

(- 1)

which outputs -1. More complex expressions also have the operator/operation first. For example

the following adds 2 and 2 and outputs 4:

(+ 2 2)

The following stands for *b***b*-4**a***c*

(- (* B B) (* 4 A C) )

The parentheses tell the interpreter the beginning and end of expressions.

**Values**

The idea behind LISP is to make LISt Processing easy. All LISP data is expressed as lists. A *list* is something like
this: (THE CAT SAT ON THE MAT)

or

(TOM (SPECIES CAT) (LEGS 4) (FUR BLACK) (GENDER MALE) (SIZE LARGE))

or

(+ (* X X) (* Y Y) (* Z Z))

Notice that LISP expressions are also *lists.*

**Programs**

All LISP code - programs, commands, subprograms, etc., are written as functions. These functions are encoded as
*lists*. LISP expressions define new functions that the user can use to solve problems...In LISP functions are
programs and all programs are functions. See the syntax later.

A XLISP program file defines a series of functions. Each is a program the user can run. The file should have a name that ends '.lsp'. When the XLISP program runs it can load '.lsp' files. It then waits for the user to input an expression to evaluate. This will normally be an expression calling one of the newly loaded functions. Here is a simple (useless) example:

(DEFUN hello() "Hello, World!")

This lets the user input (hello) and get "Hello, World!" back.

Here is a set of functions concerend with the Hailstone series:

(DEFUN a (n) (1+ (* 3 n)))

(DEFUN b (n) (/ n 2))

(DEFUN c (n) (IF (oddp n) (b (a n)) (b n))

This allows the user to "play" with the sequence of numbers by inputting commands(expressions) like this

( C (C (C 17)))

**Editing and XLISP**

It is not possible to edit a function inside XLISP. A simple way to develop XLISP programs is to use 'vi' and 'Q'.
Use Q to save the file and load the interpreter with the file. In '*vi*' the '%' command jumps between matched
parentheses. Use it to check your typing. Also in *vi* the command

:set showmatch

makes '*vi*' show you how many parentheses you have closed....try it, you may like it.

**Syntax**

LISP uses a simple, rigid, and unambiguous syntax called "Cambridge Polish":

* expression*::=*constant * | *variable* | "(" *operator* #*expression* ")".

**Lexemes**

* word*::= # *word_char,*

*word_char* ::=`any character except spaces, parentheses, quotes, and commas`, -- a word can include a period.

* number*::= # *digit* O("." # *digit* ), -- most modern LISPs allow floating point numbers as well as integers.

* digit *::= "0" .. "9".

* string*::= *quote* #(*char * ~ *quote*) *quote*.

LISP ignores upper and lower case outside strings. White space is used to separate adjacent words and otherwise is
significant only inside strings. The meaning of a *word * is determined by its place in the expression.

**Constants**

Constants have the property that they equal their value... evaluation leaves them the same.

* constant*::=*number* | * string * | * *"NIL" | "T" |* quoted_list.*

NIL is used for False and is short for the empty list (),

T is a predefined atom used for True,

* quoted_list*::= "(QUOTE" *list*")" | "'" *list*.

The QUOTE operator stops the interpreter from evaluating QUOTE's arguments. So (+ 1 2) has value 3 but (QUOTE (+ 1 2)) has value (+ 1 2). The single `blip` "'" is an abbreviation: '(+ 1 2) ia short for (QUOTE (+ 1 2)).

**Lists**

A list can be empty (NIL), an atom (word, number, string), a pair, or a sequence of lists between parentheses.

* list*::= NIL | *atom* | CONS_*pair* | *linked_list*.

* atom*::= *string* | *number* | *word*.

* CONS_pair*::= "(" *list * "." *list* ")", a constructed pair.

* linked_list*::= "(" #*list* ")".

**Variables**

LISP allows you to bind a value to an *atom*. You can then use the atom in place of the value. The effect is that the
atom has become a *variable*. Normally, the binding is done when a function is called: the formal parameters or
arguments are bound to the *values* of the actual parameters. You can also change the values bound to an atom.
There are functions that bind a value to a variable as well as returning the value.

*variable*::=*word*.

Notice that inside a QUOTE an atom stands for itself and is never treated as a variable.

**Operators**

Expressions often start with an operator:

(*operator* *argument*1 *argument*2 *argument3* ...)

*operator*::= *function_name* | *macro_name*.

*argument* ::= *expression*.

Many operators evaluate all their arguments before they start to work and are called *functions*. Addition (+) and
multiplication (*) are typical functions. The rest of the operators are called *macros* or *functional forms*. QUOTE,
DEFUN, COND and IF are examples of macros. Macros must explicitly evaluate their arguments in their
definitions.

Functions and macros have the same kinds of names. The name can be any word: ADD and + for example. The meaning bound to the word determines whether it is a function, a macro, or a variable.

**Note**

The meaning of a word often depends on its context (where it is placed):

Inside a QUOTE a constant

After a parenthesis an operator

By itself a variable

For example (QUOTE +) outputs +, (+ ....) adds up the arguments, and + gives an error.

**Predefined Functions and Forms**

XLISP has many ready made functions. We keep a complete list online. There is a partial list later in this handout. The most important functions are in capitals. Never waste time defining a function if it already exists.

**Control Structures**

LISP has the usual complement of control structures: loops, selections, compound statements but the

are all expressions and return a value. Here are the most important ones

**Selection**

(COND (e1 e2 ) more) =

If value of e1 is | Not NIL | NIL |

return value of | e2 | (COND more) |

(if e1 e2 [e3]) if e1 then e2 else e

=(COND(e1 e2)(T e3))

**Iteration**

The LISP style is to use recursion rather than iteration but XLISP does have loops called:

DO DO* DOLIST DOTIMES

**Defining New Functions**

Functions are declared in two ways in LISP:

(DEFINE (*name* *args*) *expression*)

(DEFUN *name* (*args*) *expression*...)

Both create a global meaning for the name and allow it to be used as an operator:

(*Name* *actual_arguments*)

In the CSUSB version of XLISP we have both DEFINE and DEFUN-- but they are subtly different. See later.

**Some predefined LISP Functions**

**Notation: **Optional arguments are in square brackets. *e* is an expression, *t *any condition, *f* any functions, *s* is a
symbol, *n* is an arithmetical expressions. Important fucntison/forms are CAPITALIZED.

**Arithmetic** **expressions**

(* *n*...) multiply (+ *n*...) add

(- *n*...) subtract, negate (/ *n*...) divide

(1+ *n*) add one (1- *n*) subtract one

(abs *n*) the absolute value of a number

(cos *n*) (sin *n*) (tan *n*) trig functions

(exp *n*) exponential of *n*

(expt *n*1 *n*2) *n*1 to the *n*2 power

(float *n*) converts to a floating point

(max *n*...) (min *n*...) the largest/smallest

(random *n*) random number between 1 and n-1

(rem *n*...) remainder after division

(sqrt *n*) compute the square root of *n*

(truncate *n*) truncates float *n *to an integer

**Relational expressions**

(/= *n*1 *n*2) test for not equal to

(< *n*1 *n*2) test for less than

(<= *n*1 *n*2) test for less than or equal to

(= *n*1 *n*2) test for equal to

(> *n*1 *n*2) test for greater than

(>= *n*1 *n*2) test for greater than or equal to

**Boolean Expressions/Predicates**

(ATOM e) is this an atom?

(consp e) is this a non-empty list?

(eq e1 e2) (eql e1 e2) (equal e1 e2)

Various equality tests.

(evenp *n*) is *n* even?

(listp e) is this a list (not a null or atom)?

(member e1 e2) is e1 an item in e2?

(minusp *n*) is *n *negative?

(NULL e) is this an empty list?(sometimes NULLP)

(numberp e) is e a number?

(oddp *n*) is *n * odd?

(plusp *n*) is *n* positive?

(ZEROP *n* ) is *n* zero?

(AND [e]...) a logical and (short-circuited)

(NOT e) is e false? = (null e)!

(OR [e]...) logical or (short-circuited??)

NIL Constant with effect of false

T predefined constant with effect of true.

Any non-NIL value is treated as false.

**List Expressions**

(APPEND [e]...) append lists

(assoc e1 e2) Find pair (*x y*) in e2 with *x*=e1,and
return y.

(CAR e) return the first item of CONS-pair e

(CDR e) return the second item of Cons-pair e

(CONS e1 e2) construct a new Cons-pair

(*cxxr* e) cadr, caar, cdar, cddr

(*cxxxr* e) all *cxxxr* combinations(x::=a|d)

(*cxxxxr* e) all *cxxxxr* combinations

(last e) return the last node of list e

(length e) the length of a list or string

(LIST [e]...) constructs a list of values

(NTH *n* e) the *n*th item of e

(nthcdr n e) the *n*th cdr of e

(reverse e) reverse a list

**Strings and Characters**

(char e1 n) *n*th character in string e1

(strcat [e]...) concatenate strings

**Functional**

(apply f args) apply a f to args

(funcall f [args]...) call function with args

(mapc f e) (mapcar f e) (mapl f e) (maplist f e)

apply f to all (cars, cdrs, elements) in list e

**Printing**

(prin1 e ...) print e

(princ e ) print without quoting

(print e) print e on a new line

(terpri ) terminate the current print line

(write-char character) write a character

**Some Macros**

**Quotation**

'e::=(QUOTE e) return e unevaluated

#'e::= (function e) quote a function

#(e...) ::= an array

**Lambda Expressions**

(LAMBDA (args) e) a function from args to e.

**Assignment**

(setq s e) set the value of a symbol s to e

**Selection**

(COND [pair]...) select first pair=(t e) with* t* non-null
and evaluate *e*.

(case e [case]...) select by case

case::=(value [e]...)

(if e1 e2 [e3]) if e1 then e2 else e

**Iteration**

(do ([binding]...) (t) e...) loop

(do* ([binding]...) (t) e...) loop

(dolist (s list) e...) for s in list

(dotimes (s e_{1}) e_{2}...) s in 0..e1-1

**Blocks**

(LET ( (s e1)...) e2...) block{LIST s=e1;... .e2..}

(progn [e]... e_{n}) execute sequentially{...}

(prog ([binding]...) [e]...) begin...end/{...}

**Control**

(EXIT) exit XLISP

(return e) cause a *prog* to return value

**Files**

(LOAD filename [vflag [pflag]]) load a file

**Hints**

(1) **Let LISP do the work for you.**

(1a)__Forget efficiency__! Quickly break down complex problems into simple ones (top-down) in the *clearest* way
you can. Then code and test solutions to the simple problems bottom up. Once they works, and only if the user
complains you can speed it up.

(1b)__LISP is the main program!__ Aim for lots of useful but small functions. Give the user a wide choice of
"programs" to run. Use them yourself.

(1c)__LISP functions are often recursive.__

(1d)__Don't waste time on input/output.__ LISP functions are given lists as data by the interpreter and outputs a list
as a result to the standard output.

(2)**Forget assignments, sequences, and loops! ** Look for ways to classify the givens (COND, ATOM, NULL,
MINUSP...) plus ways to decompose them (CAR, CDR,...) plus ways to assemble the goal (+, CONS, LIST,
APPEND, ...)

(3) **Divide and conquer.** Look for known functions: predefined, defined later, or the function being defined.

(4) **Layout LISP carefully** and indent sub-lists. For example:

(DEFINE (length L)

(COND

((NULL L) 0)

((ATOM L) 1)

( T (+ 1 (length (CDR L)) ))

)

)

(6) Do you ant to store some results stored? Introduce a function with arguments to store them! For example when
solving a quadratic equation *a x*^2+*b x*+ *c* =0 the value of the discriminant (*b*^2-4 a c) and a denominator (2* a*) are
used several times so we might define three functions as follows:

(DEFINE (SOLVE A B C) (SOLVEQ A B C (DISC A B C)(/ 1.0 (* 2.0 A)) ) )

(DEFINE (DISC A B C) (- (* B B) (* 4.0 A B)))

(DEFINE (SOLVEQ A B C DISC DEN)

(COND

( ( > D 0) (LIST

(* ( - (- B) (SQRT DISC)) DEN)

(* ( + (- B) (SQRT DISC)) DEN)

) )

( (= D 0) (* (- B) DEN)

)

( T (CONS

(* (- B) DEN )

(* (SQRT (- DISC)) DEN )

)

)

)

)

(7) When the interpreter doesn't do anything after typing in an expression or definition..... add right parentheses.

(8) End all CONDs with an 'or-else' pair like this (T something).

**Semantic Details**

**Scoping**

Each function call/LET adds new local variables to the environment by (1) evaluating the actual arguments, and (2) binding them as values to the formal arguments. These local assignment are removed when the function returns.

The first LISP was defined by an interpreter - called EVALQUOTE. It used dynamic scoping with shallow binding and associated a "P-list"(Property List) with each atom. Nowadays LISPs (including Scheme) use static scoping. P-Lists are still a part of LISP thinking and programming.

XLISP provides both old fashioned functions and modern statically scoped ones.

A LAMBDA expression like

(LAMBDA (a1 a2 a3 ... an ) e)

represents an unamed function that expects to be given *n *arguments. These will be expressions that are evaluated
and bound to the formal arguments as values. This is a complete new set of variables a1..an. The formal arguments
a1..can appear in the expression e. Expression e is evaluated to give the value of the function. The variables a1...an
are then removed and the value is returned. Notice that any older versions of the variables now re-appear.

I added the

(DEFINE (*name* *args*) *expression*)

macro to XLISP. I stayed close to the original EVALQUOTE model and used the name's P-list to bind the name to
a LAMBDA expression. The result is that 'define' uses *dynamic* scoping.

(DEFINE (*N* *args*) *e*)

- Afterwards *N* means (LAMBDA (*args*) *e*) and so has dynamically scoped variables. Because *e* is
evaluated when called it's non-local variables are interpreted in the environment of the call... not the definition.

In our LISP (XLISP) the

(DEFUN *name* (*args*) *expression*)

macro defines the function and ensures static scoping by binding the environment of the definition into the function
code. This creates something called a *closure *that combines details of the definition and its environment.

(DEFUN *N* (*args*) *e*)

is similar but with static scoped variables. *N* is bound to a kind of a *compiled* function that is called like
this (*N args*). The compilation occurs in the environment of the definition and so non-local variables refer the
those defined at the time and place of definition.

The LISP block structure:

(LET ((*variable* *val*)...) *expression*...)

introduces a set of local variables with an initial value. These can not be accessed by expressions outside the block.
Each expression is executed in turn and can use the local variables. If an expression in the LET defines a function
by using (DEFUN ...) this function body has access to these variables. However, the function name in the DEFUN
has *global scope* and so can be called from outside the (LET ...). In effect, the LET introduces an object with
member functions to access it.

(LET (( X 1) (Y 2)) ( + X Y))

returns 3 the sum of 1 and 2.

**Axioms**

LISP is "logical" in the sense that its inventors wrote down a set of assumptions (axioms) that can be made about LISP expressions. They tried to make LISP implement the axioms. As a result you can predict the result of evaluating an expression mathematically. Here are some of the axioms:

For all LISP expressions x,y:

(CAR (CONS x y)) = x

and (CDR (CONS x y)) = y.

If *x* is a Cons-pair then

(CONS (CAR x) (CDR x) ) = x.

If the value of c is not NIL then (COND (c x) y ) = x.

If the value of c is NIL then (COND (c x) y ) = (COND y).

Abbreviations:

(CADR x) = (CAR (CDR x)),

(CDDR x) = (CDR (CDR x)),

(CDAR x) = (CDR (CAR x)),

(CAAR x) = (CAR (CAR x)),

and so on for CADDR, CADDDR, CDDDR, ...

(NTH 0 x) = (CAR x)

For n>0,

(NTH n x) = (NTH (- n 1) (CAR X))

**Implementing LISP**

The data in LISP is a list. Internally all lists are either empty, atomic or a CONS-pair (Constructed Pair)

*list* ::= *nil* | *atomic* | *Cons-pair*.

Internally these are (1) the null pointer, (2) a pointer to a string or a number, (3) a pointer to an object with two pointers called 'car' and 'cdr' respectively.

A CONS-pair is constructed by the CONS function:

(CONS 'A 'B )

This is a pair of pointers (the car and the cdr) that point to atoms A and B respectively, See the diagram.

The value is printed with a dot like this:

( A . B )

It is therefore called a "Dotted pair".

All lists (for example (A B C D) ) are constructed from dotted pairs. For example the expression

(LIST 'A 'B 'C 'D)

constructs this data structure

(A . (B . (C. (D . NIL))))

and returns it as its value. It is then printed as:

( A B C D )

**See Also**

There are many examples/tutorials/experiments that can be found from the CS320 resources page:

http://www.csci.csusb.edu/dick/cs320/resources.html#LISP

Here is a first rough UML model of the semantics of LISP:

Images of Rational Rose model: Main + Values Package + Expressions Package and the Rational Rose model:

http://www.csci.csusb.edu/dick/cs320/handouts/ch14lisp.mdl

Here is a page of pointers to many WWW pages on LISP:

http://www.csci.csusb.edu/dick/samples/lisp.html

The source code and documentation (in old fashioned C) for CSUSB XLISP is online:

http://www.csci.csusb.edu/dick/cs320/lisp/src/

It is easy to port to other operating systems. You may download, compile, use, and change this code for any non-profit purpose. Do not sell it - improve it and give it away.

**Review Questions**

1. What does a user input to a LISP interpreter? What does the interpreter do with the input? What does it output?

2. How do you terminate XLISP? What are the parentheses in this input for?

3. What is the first character and the last character of all expressions that have an operator? What follows the first character? What comes next?

4. Is LISP case sensitive? Is white space significant and if so, where? Name some characters that can be in a string but not in an word.

5. What is the value of LISP expressions: (+ 1 2), (* 3 (+ 1 2)), and (* (+ 1 2) (+ 2 5) ).

6. Write the C/C++ expressions in LISP: 1+2, 1+2*3, sqrt(4).

7. Consider a word like ALPHA. When it appears as the input expression to a LISP interpreter what does the interpreter expect it to be? How is it interpreted here: ( ALPHA .....)? How about here: (......ALPHA ....)

8. Fill in the blank in: Just about everything in LISP is a ____________ structure.

9. What are the values of (QUOTE (+ 1 2)), '(+ 1 2), (+ 1 2).

10. What happens if you don't close all the parentheses in a LISP expression as you input it?

11. What is the difference between a function and a macro in XLISP? Give an example of each.

12. Name two operators that are used to create new functions.

13. List half-a-dozen symbols that are used to represent arithmetic operators in XLISP.

13. List the 6 relational operators of XLISP.

14. What do the following operators do in XLISP: ATOM, NULL, ZEROP?

15. List the three boolean operators and the two Boolean values that are predefined in XLISP.

16. What is the CAR and the CDR of (x . y)?

17. What are the values of (CAR (CONS x y)) and (CDR (CONS x y)) respectively?

18. Explain the difference between the dotted pair (A . B) and the list (A B). What is the CAR and the CDR of (x y)?

19. How is (A B C) expressed using dotted pairs and NIL?

20. What is COND short for? Suppose *x*,*y*,*z* are LISP expressions, explain how the following expression is
evaluated in LISP: (COND ( *x y* ) (T *z*)).

21. Express (CADR x) and (CADDR x) in terms of CAR, CDR and expression x.

22. Consider (DEFINE (DELTA A B C) (- (* B B) (* 4.0 A C))). What is the name of the function? How many arguments does it have? What is (DELTA 1 2 3)? Rewrite the DEFINE using DEFUN.

23. Consider (DEFUN DIFF ( X Y ) (ABS (- X Y))). What is the name of the function? How many arguments does it have? What is the value of (DIFF 1 2)? Rewrite DEFUN using DEFINE.

24. What parameter passing methods are used in LISP functions?

25. Study this: (LET ((X 3)(Y 2)) (* X Y) ). What variables are declared and what are their values? What value is printed if the above is input?

26. What do you use the operator SETQ for?

27. Write the expressions ( -b + sqrt( b*b - 4 a c) )/(2*a) and ( -b + sqrt( b*b - 4 a c) )/(2*a) as LISP expressions.

28. Write the following C/C++ expression as a LISP COND expression: (delta(a,b,c) > 0? two_roots(a,b,c): two_parts(a,b,c) )

**Projects**

1. Add a macro (EDIT function_name) to our XLISP by hacking the source code

2. Find out about these two world famous LISP programs: Doctor and Eliza.