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 argument1 argument2 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 n1 n2) n1 to the n2 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

(/= n1 n2) test for not equal to

(< n1 n2) test for less than

(<= n1 n2) test for less than or equal to

(= n1 n2) test for equal to

(> n1 n2) test for greater than

(>= n1 n2) 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 nth item of e

(nthcdr n e) the nth cdr of e

(reverse e) reverse a list

Strings and Characters

(char e1 n) nth 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 e1) e2...) s in 0..e1-1

Blocks

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

(progn [e]... en) 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.