.Open CS320 Lab 12 LISP Laboratory Number 2
. Check out New things on the Course Web Page
.See http://www.csci.csusb.edu/dick/cs320/
. Goal
This lab should teach you how to create and use
new arithmetic functions.  We will tackle LISP data structures
in the next lab.
. Deliverables
You should record your insights and confusions
in a new cs320 lab page and link it to you home/cs320/index page.

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.
. Hints
.Net
	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.
	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 test editor is good for LISP, but `vi` can help you track the parentheses.
	Put XLISP code in files that end ".lsp".
.Box
	In 'vi' you can track parentheses if you do the following
.As_is 		:set showmatch
.Set
	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)
.Close.Box
  Some browser 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.
.Close.Net
. Review
Start by rereading your last published page of notes!

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:
.As_is 		()
.As_is 		(+ 1 2)
.As_is 		(1 + 2)
.As_is 		(* (+ 1 2) (+ 3 4))
.As_is 		(+ 1 2 3 4)
.As_is 		(A B C)
.As_is 		'(A B C)
.As_is 		A
.As_is 		'A
.As_is 		(A)
If you get one wrong... you may need to go back to 
.See http://www.csci.csusb.edu/dick/cs320/lab/11.html
again.
. Creating new functions
Here is a function with no arguments:
.As_is 		( define  (a) 4321)
.As_is 		(a)
.As_is 		a
.As_is 		'a
.As_is 		(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`.

. Functions with a single parameter
Here is how we would define a LISP function with a single
argument that returns a list:
.As_is 		(DEFINE (square x)           (* x x))
Here is how you test it...
.As_is 		(square 3)
.As_is 		(square 4)
.As_is 		(square 5)

Here is how you can use it:
.As_is 		(square (+ 1 2 3))
.As_is 		(+ (square  3) (square 4) )
.As_is 		(+ 3 (square 3) )
Test the above!

Here is how XLISP can list it:
.As_is 		square
XLISP 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:
.As_is 		(DEFINE (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:
	n^4 = (n^2)^2.

Test it. And save it...
. Functions with two parameters
Functions of more arguments/parameters are done the same way
using the syntax
	( DEFINE (name w x y z ...) expression)

Here is a definition of a function with two arguments in LISP:
.As_is 		(DEFINE (pythagoras x y) (+ (square x) (square y)))
.As_is 		(pythagoras 3 4)
Some common errors
.As_is 		(pythagoras 4)
.As_is 		(pythagoras 1 3 4)
.As_is 		(pythagoras )
In our XLISP the value of the `function name` is an expression defining
a function:
.As_is 		pythagoras 

Here is a function that return the larger of two expressions:
.As_is 		(define (max2 a b) (if (> a b) a b))
.As_is 		(max2 1 17)
.As_is 		(max2 17 1)
.As_is 		(max2 (max2 3 5) (max2 4 1))
.As_is 		(max2 (square 3) (cube 2))

Define a function called min2 that returns the smallest of two
arguments.  Test it and save it....
. 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:
.List
	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.
.Close.List

.As_is (define (binroot target lo hi error )
.As_is 	(let (( mid (/ (+ lo hi) 2.0))) ; this saves the time to recalculate mid
.As_is 	 (if (<= (- hi lo) error)
.As_is 	     mid
.As_is 	     (if (< (square mid) target)
.As_is 	         (binroot target mid hi  error)
.As_is 	         (binroot target lo  mid error)
.As_is              )
.As_is 	 )
.As_is 	)
.As_is )
Here is how I tested it:
.As_is 		(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.

.Open Optional experiments if you have time
. 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.
.As_is 		(define (power x n)
.As_is 		   (cond
.As_is 			((= n 0) 1)
.As_is 			((= n 1) x)
.As_is 			(T (* x (power x (- n 1))))
.As_is 		   )
.As_is 		)
Here are two test cases
.As_is 		(power 2 3)
.As_is 		(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
	If n is 0 then power(x,n) = 1.
	If n is 1 then power(x,n) = x.
	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)).
.Close.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?

. Classic factorial
We now define a new function, command and kind of expression
that calculates the factorial of a positive integer.  The factorial
of the number 0 is 1, and for all other positive integers n you
work out n times the factorial of n-1.  In LISP we say:
.As_is 		(define (factorial n)
.As_is 		 (if (= n 0) 1 (* n ( factorial ( - n 1 ) ))
.As_is 		 )
.As_is 		)

Here you print out the definition of factorial:
.As_is 		factorial
Here you input expressions that apply factorial to
simple numbers:
.As_is 		(factorial 0)
.As_is 		(factorial 3)
.As_is 		(factorial 5)

Trace how it works:
.As_is 		(trace factorial)
.As_is 		(factorial 0)
.As_is 		(factorial 3)
.As_is 		(factorial 5)
.As_is 		(untrace factorial)

Below you can use `factorial` is more complicated ways:
.As_is 		(factorial (factorial 3))
.As_is 		(setq n 3)
.As_is 		(factorial n)
.As_is 		(setq f (factorial n))
.As_is 		f
.As_is 		(setq f (factorial f))
.As_is 		f

The problem with this factorial is that n! quite
a small n is too large
to be represented as an integer.  Worse n! when n<0
is infinitely small!  As a result we should define a safe factorial
that returns a string "error" when n<0 or n is too big.

Program and test this one.

. An example of top-down design in LISP
.See http://www/dick/cs320/lab/primes.html

.Close Optional experiments if you have time
. Leave LISP
To exit lisp, input the EOT character CTRL/D
.Close CS320 Lab 12 LISP Laboratory Number 2
. Check the Preparation for next class
.See ../13.html