This page generated on Tue Jan 8 12:21:47 PST 2002.

- Introduction to LISP Second Lab: LISP Programming Tricks
- : Context
- : Hints
- : How LISP Programs are Made
- : Experiments
- : : Review last lab
- : : Add up all numbers in a list
- : : Tracing a function
- : : Find an atom in a simple list
- : : Decomposition and Composition
- : : Getting and Loading Existing Programs/Functions
- : : Higher Order Functions
- : : Other Higher Order Functions
- : : Making a Function More Reusable
- : : Sebesta 13.5.2
- : : Simple Stats in LISP
- : : Another way to sum the squares of a list of numbers
- : : Scheme and Sebesta
- : : Common LISP and Sebesta
- : : If you have time
- : Dirty LISP
- : Next lab
- Index of defined terms etc.

- The CS320 Reference Manual (Keep open beside you).
- Sebesta Chapter 13 (read first, and work from).
- On Blaze
- Scheme (see Sebesta 13.5) (old edn 13.3 corrected, 13.4.1)
- SML (see Sebesta 13.7)

- On the other machines we have
- XLISP = Common LISP + Objects (See Sebesta 13.6)(old 13.4.2)

- A directory full of sample functions/programs
[ http://www.csci.csusb.edu/dick/cs320/lisp/ ]
http://www/dick/cs320/lisp/

- The source code (in C) is in
[ http://www.csci.csusb.edu/dick/cs320/lisp/src/ ]
http://www/dick/cs320/lisp/src/

- A file that lists all the functions in XLISP that you can search for key words using your WWW browser: [ lisp.functions ] and a [ lookup320 ] form for finding out about CS320 technical terms and topics.
- Forget about efficiency. Keep It Simple and Make It Work.
- Remember that everything in LISP is a list.
- Divide and Conquer:
- Break up the given problems into smaller problems, top-down.
- Solve each problem, bottom-up, as a function that:
- divides the data into
*special cases*and solve each one in turn, - divide the data into
*pieces*, work on each piece in turn, - divide the a complex function into a composition of smaller functions,
- assembles the results of solving the parts of the problem.

- divides the data into
- Let the user run the functions they want to help them solve their problems.

- The code's structure reflects how you divide up the problem.
- Be very very careful about counting parentheses.
- 'vi' can help you track parentheses if you do the following in 'vi'
:set showmatch

- Take notes....
- Watch the BBS and post questions and answers.
- All LISP programs are functions that have lists as arguments and return a list.
- There are many primitive ready made functions.
- Numeric: +, -, *, /, sqrt, ....
- List: car, cdr, cons, list,...
- Tests: nullp, atom, numberp, ...
- Booleans: and, or, not, ...
- ...
- See your CS320 Languages Reference Manual for a pretty complete
- list. Or (on some systems) try 'man lisp' at the UNIX prompt. Also, on the WWW: [ lisp.functions.html ] [ functions.lsp ] [ lisp.functions ]

- Functions are defined as expressions:
Sample Expressions
- (> (* b b) (* 4 a c) )
- (- (- b) (sqrt ( - (* b b) (* 4 a c)) ))
- (+ (- b) (sqrt ( - (* b b) (* 4 a c)) ))

- Expressions use functions and some special operators:
- (if condition expression expression)
- (cond (condition result) (condition result) ... )

- (adder ()) = 0
- (adder 1 ) = 1
- (adder (list 1 2 3)) = 6
- The adder of the items in the null (empty) list will be zero.
- The adder of a single number is that number.
- The adder of a non-numeric atom is zero.
- The adder of a pair is the sum of the adder of the first and the adder of the second part of the list.
- If x is NIL then (adder x) is 0.
- If x is a number then (adder x) is x.
- If x is an atom but not a number then (adder x) is 0.
- If x is a pair ( y . z ) then (adder x) is sum of (adder y) and (adder z).
- (find A NIL) is NIL because there are no B's
- (find A '(A ...) ) is A because there is an A in the B's
- (find A '(B1 B2...) ) may be an A or NIL depending on the B2s...
- if b is nil then nil
- else if a = the head of b then a
- else (find a (tail b))
- Make a list of all numbers from 1 to n
- Remove from this list all the non-prime numbers
- Removing composite numbers from a NULL list leaves a NUL lists.
- If the first item is composite, remove composites from the rest.
- else put this prime in front of a list with composites removed from rest
- http://www/dick/cs320/stats/ss.lsp
which shows a slightly more functional/high-level
approach to part of the problem:
summing squares

and squaring sums.

### Scheme and Sebesta

Rlogin to blaze and input all the example functions DEFINEd in Sebesta 13.5.3, 13.5.4, ...Then try to run them on any examples he gives.

### Common LISP and Sebesta

Back on your workstation try out the Common LISP function DEFUNned in sebesta 13.6### If you have time

Explore the various LISP examples inhttp://www/dick/cs320/lisp/

[ index.html ]*. . . . . . . . . ( end of section Experiments)*<<Contents | Index>>## Dirty LISP

It is possible to write LISP code that is full of loops and the equivalent of {...} and assignments. The key operators are: PROG, PROGN, DO, DO*,...You should resist the temptation to use these since your task is to learn functional thinking... which avoids these concepts.

## Next lab

Inventing, designing, and coding your own functions in LISP. [ lab3.html ]*. . . . . . . . . ( end of section Introduction to LISP Second Lab: LISP Programming Tricks)*<<Contents | Index>>

You need:

We have

()

(+ 1 2)

(1 + 2)

(* (+ 1 2) (+ 3 4))

(+ 1 2 3 4)

(A B C)

'(A B C)

A

'A

(list 'a 'b)

(car (list 'a 'b))

(cdr (list 'a 'b))

I use the following rules:

Or more formally:

Here is the definition in LISP, input it:

(define (adder x)

(cond ((null x) 0)

((numberp x) x)

((atom x) 0)

(T (+ (adder (car x) ) ( adder (cdr x)))

)

)

);end define

Check that the definition exists:

adder

Check that it works according to the rules:

(adder ())

(adder 1)

(adder 2)

(adder 'hello)

(adder '(1 2 3))

(adder '((1 2 3) (4 5 6) (((7)))))

(trace adder)and redo the above expressions...then turn the trace off:

(untrace adder)

Analysis

Design of

(find a b):

Code

(define (find a b)

(if (null b) NIL

(if (eq a (car b)) a

(find a (cdr b) )

) )

)

As an example consider the problem of listing the
primes less than or equal to n you might decompose this into

Net

(End of Net)

In LISP:

(Define (Primes N) (RemoveComposite(ListNumbers 1 N)))You can input this first... but it won't work until you define the two subfunctions

(primes 10)

Next step define one of the subfunctions:

(define (ListNumbers I J)

(if (> I J) NIL

(if (= I J) (list I)

(cons I (ListNumbers (+ 1 I) J))

) ) )Input this and test it like this

ListNumbers

(ListNumbers 1 10)

(trace ListNumbers)

(ListNumbers 5 10)

(untrace ListNumbers)Does this fix 'primes'? Test

Now we need the function *RemoveComposite* to remove composite numbers.
Decompose this into two steps/functions: A function that tests for
a composite number and one to to remove numbers that we don't want.
Here is the filter to remove the non-primes:

(removecomposite L):

Net

(End of Net)

(define (RemoveComposite L)

(if (NULL L) NIL

(if (composite (car L)) (RemoveComposite (cdr L))

(cons (car L) (RemoveComposite (cdr L)))

) ) )

Again you can test this... and find that *composite* is not defined.

How can you see if a number is composite? You need to find out if it is divisible by any of the numbers from 2 up to some number less than that number.

The word *any* above is a clue to the need for a new function that
doesn't just try numbers from 2 to *n*, but numbers from *I* to *n* for any
*I*. Suppose this function is called (hasdivisor I N) then we can use it like this to define *composite*

(define (composite n) (hasdivisor 2 N) )

And if *N* has a divisor between *I* and *N*-1 inclusive then it is
either *I* itself or it is a divisor between *I*+1 and *N*-1 inclusive.
Further if the square of *I* is greater than *N* then we know that there
can be NO divisors...

(define (hasdivisor I N)

(if (> (* I I) N) NIL

(if (divides I N) T

(hasdivisor (+ 1 I) N)

) ) )

Again if you test this you may find that *divides* is not defined...
This is a standard hack: divide and multipy and check for lost
remainders:

(define (divides I N) (= (* I (/ N I)) N))Again add this definition and test

Note.... If you actually develop code like this, you can easily
lose track of what you have defined and what is needed and so on. It
is best to use an editor to develop the code in a file *name*.lsp
and use *lisp name.lsp* to test it as it develops.

Note... You might decompose this problem in a different way and still get a working program. It may be faster, smaller, smarter, longer, shorter, and etc... This decomposition was created solely to demonstrate the decompose/compose for LISP.

lisp primes.lspAnd you will load a LISP system with added functions for handling prime numbers...

Can you work out how to use *mapcar* to list the squares of
a list of numbers?

Here is a more complex problem: You a given a list of pairs like this: ((x1 . y1) (x2 . y2) (x3 . y3) ...), generate a list of (x1 x2 x3 ... ).

Note: Such a list is called a pair-list or *plist*
for short. It is used to record properties (the y's) of things (the x's).

By combining functions like *mapcar*, *removecomposite*, and
so on you can develop complex solutions quickly.

(define (removecomposite L) (remove composite L))But in fact this means that

(define (removecomposite L) (remove 'composite L))Now, since we have a constant function

(define (Remove test L)

(if (NULL L) NIL

(if (funcall test (car L)) (Remove test (cdr L))

(cons (car L) (Remove test (cdr L)))

) ) )As a result we can also use remove like this:

(remove 'oddp '(1 2 3 4 5 6 7))

(remove 'null '(A () B () (C D)))and so on...

For a silly example if you have time: [ fun.lsp ]

Some may not work.... then

rlogin blazeand run

schemeand try them again. Then logout from blaze and back to your workstation.

http://www/dick/cs320/stats/stats.lspwhich shows your how the simplest statistics are programmed in LISP. You can download this (save as..) to your home directory and then run LISP with these functions added to it:

lisp stats.lspto run it. You can also use the normal UNIX operations on the file:

cat stats.lsp

head stats.lsp

tail stats.lsp

vi stats.lsp

File *stats.lsp* defines a series of functions that you should test

(mean '(1 2 3))for example.

Also run them with the trace turned on:

(trace sum) (mean '(1 2 3 4 5 6))for example.