[Index] [Schedule] [Syllabi] [Text] [Labs] [Projects] [Resources] [Search] [Grading]

Notes: [01] [02] [03] [04] [05] [06] [07] [08] [09] [10] [11] [12] [13] [14] [15] [16]

Tue May 18 12:17:04 PDT 2004

- CS620 LISP Laboratory Number 2
- : Check out New things on the Course Web Page
- : Goal
- : Deliverables
- : Hints
- : Review
- : Displaying the structure of a LISP value
- : Creating new functions
- : Functions with a single parameter
- : Functions with two or more parameters
- : From the book -- Association lists
- : A Binary Search
- : From the book -- Property lists
- : Optional experiments if you have time
- : : Higher powers
- : : An example of top-down design in LISP
- : Leave LISP
- Glossary
- Index of defined terms etc.

- 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.
- A comment in XLISP starts with a ";" and runs to the end of the line.
- Keep your handout on LISP open beside you and look in it for the rules of LISP. The XLISP manual is on the web at [ lisp.txt ] as a plain ASCII text file.
- Open many windows and use your hilight-and-paste feature to save time.
- Use an editor to write your functions and their test cases then either
- Any text editor is good for LISP, but
*vi*can help you track the parentheses. - Put XLISP code in files that end ".lsp".
- In 'vi' you can track parentheses if you do the following
:set showmatch

- Copy and paste into a window running XLisp to run them...
- or
- Save the version ( :w in vi) and run xlisp on it. (:!xlisp % in vi)

- In 'vi' you can track parentheses if you do the following
- Some browsers may panic if you link to a ".lsp" file. If you put source code in a ".txt" file every browser in the world will read it and your user's will love you.
- n^4 = (n^2)^2.
## Functions with two or more parameters

Functions of more arguments/parameters are done the same way using the syntax - ( defun name (w x y z ...) expression)
Here is a definition of a function with two arguments in LISP:

(defun pythagoras (x y) (+ (square x) (square y)))

(pythagoras 3 4)

Some common errors(pythagoras 4)

(pythagoras 1 3 4)

(pythagoras )

Here is a function that return the larger of two expressions:

(defun max2 (a b) (cond ((> a b) a) (T b)))

(max2 1 17)

(max2 17 1)

(max2 (max2 3 5) (max2 4 1))

(max2 (square 3) (cube 2))

Define a function called min2 that returns the smallest of two arguments. Test it and save it....

## From the book -- Association lists

XLISP has(assoc expression a-list)

as a built in function. Example(assoc 2 '((1 a) (2 b) (3 c)))

Finds the value of the expression in the a-list and returns the pair.(2 b)

Test it out... it is not the one in the book.Define a new function called

*bookassoc*that does work like the one in the book and uses*assoc*to do the hard work.## A Binary Search

Here is a function that searches for the positive square root of a positive number. It uses the square function. It has four arguments:- target: the number for which you need a root. Must be >=0.
- lo: a number that is less than the root.
- hi: a number that is greater than the root.
- error: a number indicating the desired accuracy of the approximation.

(defun binroot (target lo hi error )

(let (( mid (/ (+ lo hi) 2.0))) ; this saves the time to recalculate mid

(if (<= (- hi lo) error)

mid

(if (< (square mid) target)

(binroot target mid hi error)

(binroot target lo mid error)

)

)

)

)

Here is how I tested it:(binroot 50 0 100 0.05)

Test it further and trace it.The above algorithm will find roots of any monotonic increasing function. Modify it to find cube roots and fourth roots of positive numbers.

## From the book -- Property lists

In XLISP we have:- (get symbol property) ; book's get
- (putprop symbol value property) ; almost book's put
- (remprop symbol property) ; remove a property
- (symbol-plist symbol) ;get the property list of a symbol

We don't have the book's

*put*function. Use one of the above functions to define the book's*put*function.## Optional experiments if you have time

- If n is even then n=2*k for some k and so power(x,n)=square(power(x,k)).
- If n is odd then n=2*k+1 for some k and so power(x,n)=x*square(power(x,k)).

### Higher powers

The following function works out the value of*x*to the power*n*when*n*is a whole number greater than or equal to 0.(defun power (x n)

(cond

((= n 0) 1)

((= n 1) x)

(T (* x (power x (- n 1))))

)

)

Here are two test cases(power 2 3)

(power 3 2)

Test with the*trace*function....However this is not a very fast way to calculate powers. There is another one based on these facts:

Net

(End of Net)

We have LISP function EVENP and ODDP to detect parity and (/ n 2) works out a k for us by rounding down.Can you figure out how to speed up the original power function?

### An example of top-down design in LISP

[ primes.html ]*. . . . . . . . . ( end of section Optional experiments if you have time)*<<Contents | Index>>## Leave LISP

To exit lisp, input the EOT character CTRL/D - BNF::="Backus-Naur Form", for syntax and grammar, developed by Backus and Naur.
- EBNF::="Extended "
*BNF*. - HTML::= "HyperText Markup Language", used on the
*WWW*. - HTML_page::syntax= "<HTML>" head body.
- Java::="An "
*OO*" Language from Sun". - LISP::= "LISt Processing Language".
- LRM::="Language Reference Manual".
- OO::="Object-Oriented".
- Prolog::="Programming in Logic".
- TBA::="To Be Announced".
- UML::="Unified Modeling Language".
- URL::=Universal_Resource_Locator,
- Universal_Resource_Locator::syntax=
*protocol*":"*location*, where

Net

(End of Net)

- WWW::= See http://www.csci.csusb.edu/dick/cs620/, index to web site for this class.
- XBNF::="eXtreme"
*BNF*, developed by the teacher from*EBNF*, designed to ASCII input of syntax, semantics, and other formal specifications.

To earn full credit the work must be done before the end of the lab and should contain a list of at least 3 notes. Each note is a short paragraph with one or two sentences and a new LISP function (or link to a file containing the function). The sentences should say what the function does and what you learned by writing it.

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

Net

(End of Net)

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

(A)

((1 . 2) . 3)The data looks like this (with a 'o' replacing the '.').

o

/ \

o 3

/ \

1 2

Net

(End of Net)

Down load/Save this file as text: [ show.lsp ]

Use this UNIX command to look inside the file:

cat show.lsp

Run this UNIX command in a terminal window:

xlisp show.lsp

Inside the running XLISP try these command:

(show '(a b))

(show '(a b c))

(show '(a b c d))

(show '((a b)(c d)))

This function (or something like it) is a handy
tool when you want to see the structure of a complex
list structure.... for example the value *show* itself.

SHOW

(show show)

( defun a () 4321)

(a)

a

'a

(a 1)

(+ a 1)

(+ (a) 1)Copy and paste the above XLISP commands into XLISP in a terminal window.

Then
define and test a new function called *answer*
that returns the value *42*.

(defun square (x) (* x x))Here is how you test it...

(square 3)

(square 4)

(square 5)

Here is how you can use it:

(square (+ 1 2 3))

(+ (square 3) (square 4) )

(+ 3 (square 3) )Test the above!

Here is how XLISP can list it:

squareXLISP does not let you edit a function however!

Do not leave LISP until you complete the next two steps.

Here is a function for the cube:

(defun cube (x) (* x (square x)))Test it.

Define a function called *fourth* that returns the
fourth power of a number. Use the fact that the
fourth power on n is the square of the square of n:

*. . . . . . . . . ( end of section CS620 LISP Laboratory Number 2) *<<Contents | Index>>

- BNF (Definition)
- car (Definition)
- cdr (Definition)
- EBNF (Definition)
- HTML (Definition)
- HTML_page (Declaration)
- Java (Definition)
- leaf (Definition)
- LISP (Definition)
- location (Definition)
- LRM (Definition)
- OO (Definition)
- pair (Definition)
- Prolog (Definition)
- protocol (Definition)
- TBA (Definition)
- tree (Definition)
- UML (Definition)
- Universal_Resource_Locator (Declaration)
- URL (Definition)
- WWW (Definition)
- XBNF (Definition)