.Open CS320 Lab/11 LISP Laboratory Number 1
. Check out New things on the Course Web Page
.See http://www.csci.csusb.edu/dick/cs320/
. Check out the final questions on LISP
.See ../11q.html
. How much LISP is on web?
.See http://www.google.com/search?hl=en&lr=&q=LISP+programming&btnG=Search
. Who uses Lambda Expressions?
.See http://www.developer.com/net/vb/article.php/3683331
. Goal
This lab should teach you the rudiments of LISP.
You should record your insights and confusions
in a new cs320 lab page.

As you do this laboratory take note of what you are
learning about LISP in another file.
(You can open a window to edit this file at the
same time as you run LISP in another terminal window, and
also browse pages in a third window)

Review, edit, check for speeling mistooks, and publish
the result.  Check out what it looks like and improve if necessary.

Let me know by
calling me across to your workstation when done.

To earn full credit the work must be done before the
end of the lab
and should contain a
list of at least
10 notes.  Each note is a short paragraph with one or two
sentences, some LISP expressions, and their values.
. LISP Versions and Commands
On the computers in JB359 the command `xlisp` should
run XLISP for you.  If it doesn't use this command
.As_is 		~dick/bin/lisp
On other servers use:
.As_is 		/share/bin/xlisp
(or add /share/bin to your PATH variable).

On the many workstations and servers the `lisp` command
will probably start up a different version of LISP.
The command
.As_is 		(exit)
will terminate it.

For beginning LISP, use the longer commands:
.As_is 		xlisp
or
.As_is 		~dick/bin/lisp
or
.As_is 		/share/bin/lisp
to run LISP.
. Hints
.Set
	To run LISP open a terminal window.  No source to edit..... in this lab!
	To leave XLISP send EOT by holding down CTRL and tapping D
	Parentheses (...) are the must important things in LISP.
	Keep your handout on LISP open beside you and look in it for
the rules of LISP.
	Use the online resources:
.See http://www/dick/samples/lisp.html
	Open many windows and use your hilight-and-paste feature to save time.
.See Multi-Window Working
below for help.
	Review the
.See Rules of LISP
below.
.Close.Set
.Open Elementary Constants
. Numbers
Decimal numbers are atoms with a defined meaning - a value
.As_is 		1
.As_is 		123445
.As_is 		-123
.As_is 		3.14159
Some LISPs don't have floating point numbers. The last expression/value
will test the interpreter for you.
. Strings
Strings are also elementary constants:
.As_is 		"This is a string"
.As_is 		")This is an ok string!"
.As_is 		":-)"
An error will happen with the following:
.As_is 			'This is a string'
. Booleans
The boolean `true` = "T" is also predefined in most LISPs:
.As_is 		T
The other `boolean` value is NIL.
.As_is 		NIL
LISP (like C) interprets a NIL as false.
.Close Elementary Constants

. Simple Arithmetic expressions
The operation comes first, followed by its arguments,
and the whole thing is put in parentheses:
.As_is 		( + 2 3 )
.As_is 		( * 2 3 )
Operators are atoms + - * / rem and other symbols.
.As_is 		(+ 1 2)
.As_is 		(+ 1 2 3 4 5 6 7 8 9)
Try a few of your own!

Now try some mistakes so you can see what various messages mean:
.As_is 		1*2
.As_is 		( 2 + 3 )
.As_is 		(*2 3)
. Constant Lists
The empty list = NIL is a predefined constant:
.As_is 		()
.As_is 		NIL
All inputs except constants are treated as function calls or variables.
The "function" "QUOTE" turns lists into constants however.
It returns a copy of its argument
with NO evaluation or changes.  Quote stops the evaluation process.
.As_is 		(quote example)
Omit the (QUOTE...) and the data is treated as a function or variable
often giving an error:
.As_is 		example
.As_is 		(example)
Quoted Lists:
.As_is 		(quote (all input is fed into an interpreter))
Quoted lists can contain sublists:
.As_is 		(quote (now is the time (he said) to come to the party))
Quoted lists inside quoted lists are ok.
.As_is 		(quote (quote stops the interepreter evaluating a list))
.As_is 		(quote a)
The blip '... is a short hand form.  Use it in place of (Quote ....)
.As_is 		'example
.As_is 		'(all input is fed into an interpreter)
.As_is 		'(quote stops the interepreter evaluating a list)
.As_is 		'(now is the time (he said) to come to the party)

Here are some quick review questions.
Why do the expressions below work the way they do?
.As_is 		'NIL
.As_is 		NIL
.As_is 		'1
.As_is 		1
.As_is 		(+ 1 2)
.As_is 		'(+ 1 2)
.As_is 		'"(quote a)"
.As_is 		"(quote a)"
.As_is 		(quote a)
.As_is 		'a
.As_is 		a
.As_is 		(a)
.As_is 		'(a b c d)
.As_is 		(a b c d)
.As_is 		'(a b (c d))
.As_is 		(a b '(c d))
. Variables are atoms bound to values
The value of an atom is found when it is in the right context.
A value is bound to a global variable by using (setq variable expression).
Local variables are created when functions are called: each formal
argument is an atom bound to the value of the actual parameter.

Try these: some do not always work.... why?
.As_is 		a
.As_is 		(setq a 1234)
.As_is 		a
.As_is 		'a
.As_is 		(quote a)
.As_is 		(* a a)
.As_is 		(a + a)
.As_is 		(setq date '(9 May 2005))
.As_is 		date
. Functions
LISP thinks the first word in a list to be evaluated is a function.
The rest of the list are the arguments (if any).  Arguments
are evaluated by the same rule as the whole expression.
.As_is 		(+ 1 2)
.As_is 		(* 3 2)
.As_is 		(- 3 2)
.As_is 		(/ 24 2)
LISP thinks that a variable is a function, if it is the
first item in the list being evaluated:
.As_is 		a
.As_is 		(a)
.As_is 		(date)
. Arithmetic Expressions
Expressions like this and are evaluated inside out...
.As_is 		(+ (* 2 3) (- 3 2) )
.As_is 		(+ (/ 1.0 1.0 ) (/ 1.0 2.0) (/ 1.0 3.0) (/ 1.0 4.0) )
The innermost are evaluated before the outermost ones, like this:
.List
	(+ (* 2 3) (- 3 2))
	(+ 6       (- 3 2))
	(+ 6       1      )
	7
.Close.List
Watch this happen... first turn on tracing for the functions
involved and then type in the expressions:
.As_is 		(trace + * - / )
.As_is 		(+ (* 2 3) (- 3 2) )
.As_is 		(* 2  (+ (* 2 3) 1))
.As_is          (+ (/ 1.0 1.0 ) (/ 1.0 2.0) (/ 1.0 3.0) (/ 1.0 4.0) )
You can turn tracing off like this:
.As_is 		(untrace + * )
.As_is 		(untrace + * - )
.As_is 		(untrace + * - /)

Try enough different LISP expressions for the notation to become
a little more natural...  and then
try to express the following in LISP
.Box
	12*12 - 4 * 2 *3
	12*(12 - 4)*2 *3
	12+12-4*2*3
	1+2+3+4+5+6+7
	2*3*4*5*6*7
	(1+2)*(3+4)*(5+6)
.Close.Box

. Functions of lists
Lists are handled by functions that have one or more lists
as arguments and produce a single list as a result.  Here is a
list of the basic functions in Common LISP:
.Box
	atom	is T if parameter's value is an atom else returns NIL
	null	is T if parameter's value is a NIL else returns NIL
	cons	constructs a new list. It is pair of the value of the first parameter, and the value of the next parameter.	
	car	is the head of the list that is the value of the parameter
	cdr	is the tail of the list that is the value of the parameter
	list	is a new list, of any length constructed of the values of the parameters in the order that they occur.
	append	is a new list, formed by placing the second argument at the end of the first argument.
.Close.Box
Don't forget: Unless a list is quoted then it is evaluated, as a function
plus arguments.
ATOM::= Test for an atom,
.As_is 		(atom 'a)
.As_is 		(atom '(a b c))
.As_is 		(atom '())
NULL::= Test for an empty list or NIL,
.As_is 		(null '())
.As_is 		(null nil)
.As_is 		(null 'nil)
.As_is 		(null 'a))
.As_is 		(null '(a b))
CONS::= Construct a new dotted pair
.As_is 		(cons (quote a) (quote b))
.As_is 		(cons 'a 'b)
.As_is 		(cons 'b 'a)
.As_is 		(cons 'a)
.As_is 		(cons '(a b ))
CAR::=get the first of a dotted (CONSED) pair.
CDR::=get the second of a dotted (CONSed) pair.

In C++ we would have
	struct pair{ pair * car; pair*cdr; ...}
.As_is 		(cons 1 3)
.As_is 		(cdr '(1 . 3))
.As_is 		(cdr '(1 . 3))
.As_is 		(car '(a . b))
.As_is 		(cdr '(a . b))
.As_is 		(cons (car '(a . b)) (cdr '(a . b)))
.As_is 		(car (cons 1 2))
.As_is 		(cdr (cons 1 2))

LIST::= constructs lists with any number of elements:
.As_is 		(list 1)
.As_is 		(list 1 2)
.As_is 		(list 1 2 3)
.As_is 		(1 2 3)
.As_is 		(list 1 2 3 4 5 6 7 8 9 )
.As_is 		(list 'a 'b 'c)
.As_is 		(list 19 'feb 1999)
.As_is 		(list 'CS320 "Programming Languages" 4 ) 

. Variables and Lists
.As_is 		(setq x '(a . b))
.As_is 		x
.As_is 		'x
.As_is 		(atom x)
.As_is 		(car x)
.As_is 		(cdr x)
.As_is 		car (x)
.As_is 		'(car x)
.As_is 		(cons (car x) (cdr x))
.As_is 		(setq x (+ 1 2))
.As_is 		x
.As_is 		'x

The `list` function assembles lists for you:
.As_is 		(setq date (list  9 'may 2005))
.As_is 		(setq class (list 'CS320 "Programming Languages" 11 ) )
.As_is 		(list class 'on date )
You can extract any item in a list:
.As_is 		date
.As_is 		(car date)
CADR::= the CAR of the CDR:
.As_is 		(cadr date)
CADDR::= the CAR of the CDR of the CDR:
.As_is 		(caddr date)
The function `car` extracts the head or first item of a pair.
The function `cdr` is the tail of the pair, so cadr is the head of the
tail - the second item.  cddr is the cdr of the cdr and so the tail of the
tail.  So caddr is the 3rd item in a list.

Try the following expressions to
find out which functions (caddd*r ...) our LISP has, and which it does not have:
.As_is 		(setq x '(mary had a little lambda))
.As_is 		x
.As_is 		(car x)
.As_is 		(cdr x)
.As_is 		(cadr x)
.As_is 		(cddr x)
.As_is 		(caddr x)
.As_is 		(cdddr x)
.As_is 		(cadddr x)
.As_is 		(caddddr x)
Most modern versions of LISP have a function `nth` that extracts
one item from a list:  `(nth 12 x)` is the 12th item in `x`
starting with `zero`.
For example,  (nth 0 x) gives the same value as (car x).
.As_is 		(nth 0 x)
.As_is 		(nth 1 x)
.As_is 		(nth 2 x)
.As_is 		(nth 4 x)

Here is a very common error made by beginners:
.As_is 		(setq x (mary had a little lamb))
Rule 1: the first thing after a parenthesis is an operator.
And 'mary' is not an operator!
. Structure of a list of elements
A list of elements (a b c d ...) is stored as a pair like
this (a . (b c d ...) ).  In other words (car l) is always
the first element in the list and (cdr x) is always the rest of the
list.
.As_is 		(cons 1 nil)
.As_is 		(cons 1 (cons 2 nil))
.As_is 		(cons 1 (cons 3 (cons 4 nil)))

.As_is 		(cons 'a nil)
.As_is 		(cons 'a 'b)
.As_is 		(cons 'a (cons 'b nil))
.As_is 		(cons 'a (cons 'b (cons 'c nil)))
.As_is 		(cons 'a (cons 'b (cons 'c (cons d nil ))))
.As_is 		(cons (cons (cons 'a 'b) 'c) 'd)
.As_is 		(cons nil nil)
. How to construct new lists from old ones
Use (append ...).  Here I set up three variables with names
x,a, and b:
.As_is 		(setq x '(surprised))
.As_is 		(setq a '(mary had a little lambda))
.As_is 		(setq b '(the doctor was) )
Now I combine them into a single list:
.As_is 		(append a b x)

Be careful constructing lists:
The following are often written by mistake when (append ...)
is needed:
.As_is 		(a b x)
(Wrong!)
.As_is 		(quote a b x)
(Wrong!)
.As_is 		(cons a b x)
(Wrong!)
.As_is 		(list a b x)
(Wrong!)

But this works
.As_is 		(append a b x)
(Excellent!)
. Constructing Lists with back-quotations
Here is a wierd but elegant feature of LISP.

You know that LISP has double quoted strings:
.As_is 		"I am a string!"
You already know that a single quotation mark
stops the interpreter from evaluating a list.
.As_is 		'(+ 1 2)
.As_is 		(setq day 'wednsday)
.As_is 		'(Today is day)

A backquoted list has a
.Key backquote
(`) in front of it -- this is the "blip" near the top
left hand corner of the normal keyboard.
It is
treated as a constant list that contains expressions.
You put a comma(,) in front of the expressions.  For example:
.As_is 		`(Today is ,day)
(day is replaced by the value of the variable `day`)

Or
.As_is 		`((+ 1 2) = ,(+ 1 2))

Or
.As_is 		`( example1 ( (sqrt 4.0) = ,(sqrt 4.0) ) ( day = ,day))

. Review Examples of Constructing lists
Which is good and which bad and why?
.As_is 		(setq y (x x)) ; see Rule 1 above
.As_is 		(setq y '(x x)) ; Rule 2: A quoted list can't have any variables
.As_is 		(setq y (CONS x x)) ; Cons only constructs pairs, not lists.
.As_is 		(setq y (LIST x x)) ; Use list to make lists of lists
.As_is 		(setq y (LIST x x x))
.As_is 		(setq y (APPEND x x x)) ; use APPEND to concatenate lists
.As_is 		(setq y `(,x x ,x)) ; use Backquoting.
. Conditional expressions
(COND ....) is the earliest structured conditional statement:
.Box
	(COND (C1 E1) (C2 E2) (C3 E3) ...) means
	Try each Cn until one has a non-NIL value and return
		the value of the matching En.
.Close.Box
.As_is 		(COND (T 'a) (NIL 'b))
.As_is 		(COND (NIL 'a) (T 'b))
.As_is 		(COND (NIL 'a) (T 'b) (NIL 'c))
.As_is 		(COND (NIL 'a) (NIL 'b) (T 'c))

A three way comparison:
.As_is 		(setq a 1) (setq b 3)
.As_is 		(COND ((= a b) "a=b") ((< a b) "a<b") (T "a>b"))

.As_is 		(setq b (- b 2))
.As_is 		(COND ((= a b) "a=b") ((< a b) "a<b") (T "a>b"))

.As_is 		(setq a (+ 1 a))
.As_is 		(COND ((= a b) "a=b") ((< a b) "a<b") (T "a>b"))
. XLISP if_then_else
XLISP has an if.  It is shorthand for a COND:
.Box
	(if a b c) ::= (COND (a b) (T c)).
	If a is true then return value of b else return value of a.
.Close.Box
.As_is 		(if T 'a 'b)
.As_is 		(if NIL 'a 'b)
.As_is 		(if True 'a 'b)
.As_is 		(if (> 2 1) 2 1)
.As_is 		(if (> 1 2) 1 2)

. Creating new functions
Next lab!
.See ./12.html
. How To Leave LISP
To exit lisp, input the EOT character CTRL/D
or input the expression (exit).
.Close CS320 LISP Laboratory Number 1
. See Also
The WikiWikiWeb has some pages on LISP in Practice:
.See http://c2.com/cgi/wiki?CommonLisp
.See http://c2.com/cgi/wiki?SchemeLanguage
.See http://c2.com/cgi/wiki?LispLanguage

Also see the brilliant EverythingIsa page:
.See http://c2.com/cgi/wiki?EverythingIsa
on the WikiWikiWeb.
.Close CS320 Lab/11 LISP Laboratory Number 1
. Check the Preparation for next class
.See ../12.html