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

This page is part of the CS320: Programming Languages Course on the Computer Science Department's WWW Server at CalState, San Bernardino, California, USA. It was generated by Doc Dick Botting.

• 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.

Introduction to LISP Second Lab: LISP Programming Tricks

Context

You have had a tantalizing glimpse of how LISP works in Lab1 [ lab1.html] . This lab is on the tricks of the trade - also on two different implementations. In the next laboratory [ lab3.html ] you will need to use these to invent and code your own functions.

You need:

---

1. The CS320 Reference Manual (Keep open beside you).
2. Sebesta Chapter 13 (read first, and work from).

---

We have

---

1. On Blaze
   • Scheme (see Sebesta 13.5) (old edn 13.3 corrected, 13.4.1)
   • SML (see Sebesta 13.7)
2. On the other machines we have
   • XLISP = Common LISP + Objects (See Sebesta 13.6)(old 13.4.2)
3. A directory full of sample functions/programs [ http://www.csci.csusb.edu/dick/cs320/lisp/ ]

    		http://www/dick/cs320/lisp/

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

    		http://www/dick/cs320/lisp/src/

5. 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.

---

Hints

---

1. Forget about efficiency. Keep It Simple and Make It Work.
2. Remember that everything in LISP is a list.
3. Divide and Conquer:
   • Break up the given problems into smaller problems, top-down.
   • Solve each problem, bottom-up, as a function that:

     ---

     1. divides the data into special cases and solve each one in turn,
     2. divide the data into pieces, work on each piece in turn,
     3. divide the a complex function into a composition of smaller functions,
     4. assembles the results of solving the parts of the problem.

     ---

   • Let the user run the functions they want to help them solve their problems.
4. The code's structure reflects how you divide up the problem.
5. Be very very careful about counting parentheses.
6. 'vi' can help you track parentheses if you do the following in 'vi'

    		:set showmatch

7. Take notes....
8. Watch the BBS and post questions and answers.

---

How LISP Programs are Made

---

1. All LISP programs are functions that have lists as arguments and return a list.
2. 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 ]

3. 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)) ))
4. Expressions use functions and some special operators:
   • (if condition expression expression)
   • (cond (condition result) (condition result) ... )

---

Experiments

Review last lab

Here are some simple LISP expressions/commands. Load the LISP interpreter and input each in turn. Try to predict what each will return as a value before inputting it:

 		()

 		(+ 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))

Add up all numbers in a list

This defines a new function, command, and kind of expression that works out the sum of the numbers in a list structure. Call this the function 'adder'. For example:

---

1. (adder ()) = 0
2. (adder 1 ) = 1
3. (adder (list 1 2 3)) = 6

---

I use the following rules:

---

1. The adder of the items in the null (empty) list will be zero.
2. The adder of a single number is that number.
3. The adder of a non-numeric atom is zero.
4. The adder of a pair is the sum of the adder of the first and the adder of the second part of the list.

---

Or more formally:

---

1. If x is NIL then (adder x) is 0.
2. If x is a number then (adder x) is x.
3. If x is an atom but not a number then (adder x) is 0.
4. If x is a pair ( y . z ) then (adder x) is sum of (adder y) and (adder z).

---

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)))))

Tracing a function

Turn on tracing for function adder:

 		(trace adder)

and redo the above expressions...then turn the trace off:

 		(untrace adder)

Find an atom in a simple list

Suppose we want a function find that is given an atom A and a simple list B = ( B1 B2 B3 ... ) we want (find A B) to return A if A is in B and "NIL" otherwise.

Analysis

---

1. (find A NIL) is NIL because there are no B's
2. (find A '(A ...) ) is A because there is an A in the B's
3. (find A '(B1 B2...) ) may be an A or NIL depending on the B2s...

---

Design of
(find a b):

---

1. if b is nil then nil
2. else if a = the head of b then a
3. else (find a (tail b))

---

Code

 		(define (find a b)

 			(if (null b) NIL

 			    (if (eq a (car b)) a

 			        (find a (cdr b) )

 			)   )

 		)

Decomposition and Composition

Sometimes you may want to work top-down, breaking down a complex function into smaller steps. Here is a worked example of top-down development.

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

1. Make a list of all numbers from 1 to n
2. Remove from this list all the non-prime numbers

(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 RemoveComposite and ListNumbers. Try this!

 		(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 (primes 10).

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

1. Removing composite numbers from a NULL list leaves a NUL lists.
2. If the first item is composite, remove composites from the rest.
3. else put this prime in front of a list with composites removed from rest

(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 primes.

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.

Getting and Loading Existing Programs/Functions

Note.... I made three mistakes when I did the original code, and fixed them above... the complete code is in [ primes.lsp ] Download/save this file (as ASCII in file primes.lsp) and then run

 		lisp primes.lsp

And you will load a LISP system with added functions for handling prime numbers...

Higher Order Functions

See Sebesta's example of using mapcar to work out the cubes of all the atoms in a simple list in section 13.5.6.2. Make sure that it works on our LISP.

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.

Other Higher Order Functions

How else might you use mapcar? Are there other map* functions in our LISP? (See the CS320 Lang. Ref. Manual). [ mapcar.lsp ] [ maplist.lsp ]

Making a Function More Reusable

Have another look at removecomposite [ removecomposite L ] Suppose that we wanted a more general version (remove test l) where 'test' defines which items in L are not in the result. We could ideally do this then:

 		(define (removecomposite L) (remove composite L))

But in fact this means that composite is treated as a variable by LISP and evaluated. To stop this we would write

 		(define (removecomposite L) (remove 'composite L))

Now, since we have a constant function 'composite we need to tell the LISP interpreter that this is a function that is to be called with certain arguments. We use (funcall test arg)

 		(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 ]

Sebesta 13.5.2

Run LISP on your workstation and try out the examples in sebesta 13.5.2.

Some may not work.... then

 		rlogin blaze

and run

 		scheme

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

Simple Stats in LISP

Use netscape to access URL

 		http://www/dick/cs320/stats/stats.lsp

which 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.lsp

to 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.

Another way to sum the squares of a list of numbers

Use netscape to access URL
1. 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 in

    		http://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>>