Introduction to LISP and functional programming - part 3
In this lab you will practice inventing and coding families
of LISP functions that help you achieve various effects.
You need to keep the list of LISP functions in the CS320
Reference manual open when you do this work. It may
also pay to do some thinking about the problems before
you start trying to code them.
Hints
Advice
- Forget about efficiency in this lab.
- Define a collection of functions that can be used
individually and together to solve a set
of problems - like stats.lsp.
- Do one function at a time.
- Give functions meaningful names
- Use (help name) to see if it exists before you write it!
- Arguments can be one character long.
- You can not save a function in LISP. You need to
develop the set of functions in a file. When ready ask the
LISP interpreter to load them lisp filename. Use .lsp.
- Have this file open in a window
and use copy/paste operations.
Use 'vi' to write the functions, and 'q' to test them out.
VI
In vi, start by typing this command
:set showmatch
and it will show you the matching parenthesis
whenever you input a closing parenthesis, brace or bracket.
Very useful.
If your file is called 'something.lsp' and you can program
a hot key in vi to load it into the LISP interpreter... See the CS320 PL Ref Manual..
Example:
- Input this command to UNIX:
Q setup
- Down load/Save this file as text:
[ show.lsp ]
- Run this UNIX command:
vi show.lsp
- Look at it... and then just tap the 'q' key...
- Watch what happens...
- Try these command:
SHOW
(show '(a b))
(show '(a b c))
(show '(a b c d))
(show '((a b)(c d)))
- CTRL/D back to vi
What might you use 'show' to do?
Review
If you would like to review the kind of thinking that
is used in functional programming see
[ sort.html ]
or the previous lab
[ lab2.html ]
Structs in LISP
You are planning to write some programs in LISP that
involve dates - for example developing a family tree. In
C/C++/Ada/Pascal you would define a struct, class, or
record type called 'Date' with three fields/components:
- day: an integer
- month: an integer
- year: an integer
Constructor
LISP does not have any structs/records.... it just has lists.
In this case use a list of three items:
'(15 4 1996) means
the 15th of april 1996.
Define a function (DATE dd mm yyyy) that constructs a 3 item list.
(Hint: ignore the possibility of errors for the moment and this is
a very very simple function!)
Test it:
€ (DATE 12 13 1996)
€ (SETQ THISYEAR 1998)
€ (SETQ TODAY (Date 26 01 THISYEAR))
€ TODAY
€ (car TODAY )
€ (cadr TODAY )
€ (caddr TODAY )
Access functions
To get the effect of things like d.day, d.month, d.year
in LISP we can use functions:
- (Day x)::= the day in date x
- (Month x)::= the month in date x
- (Year x)::= the year of date x.
Define these functions (they are very simple!)
and test that they fit the following rules:
- (Day (date x y z) ) is x
- (month (date x y z) ) is y
- (year (date x y z) ) is z
Symbolic months
Now define a function to map the number of the month into
its three letter abbreviation:
Hint: it might start like this
(define (mon mm) (if (= mm 01) 'jan ...))
or
(define (mon mm) (cond ((= mm 01) 'jan) ...))
Making months simpler to use
Can you invent a SIMPLE way for people to use
(date 12 jan 1945)
as a valid date. Hint: there are two simple tricks... (at least).
Bullet Proofed Dates
Now redefine date so that it returns a NIL
when the month is invalid, or the date impossible. Do not
output any error messages. Just return NIL.
Optional experiment
You can print a message and also return a different value
by (1) Using the (progn expr1 expr2 ... exprn value ) form
plus (2) (princ string) -- print string without its quotes
plus (3) (terpri) -- terminate print line
like the following:
(progn (princ "Not a date") (terpri) NIL)
Use this to get a traditional error message processing into
your date constructor.
Summary
By creating a set of functions we can simulate a record
structure or an object.
Factors and Primes
Here you develop a set of functions -- bottom-up -- that can help a person do
experiments in elementary number theory.
Divisibility
The first function simply tests whether one argument
divides the other. In Scheme you define
- (div? x y)::= #t if x divides y and #f otherwise
and in LISP
- (divp x y)::= T when x divides y and NIL otherwise.
Divisibillity by range of numbers
The next function tests a range of values to see if
they divide a number. Call it either divn? or divnp:
- (divn? x y)::scheme=#t iff any number from 2 up to x divides y else false
- (divnp x y)::LISP=T iff some integer from 2 to x inclusive divides y.
Hint: forget loops look for recursion!
- (divnp 2 y) = (divp 2 y)
- (divnp 3 y) = (divp 3 y) or else (divnp 2 y)
- (divnp 4 y) = (divp 4 y) or else (divnp 3 y)
- (divnp 5 y) = (divp 5 y) or else (divnp 4 y)
- So...
Test for Number being Prime
Define a function that tests for primality/primeness
- (prime? p)::scheme= p is NOT divisible by any number except 1 and p.
- (primep p)::LISP= p is NOT divisible by any number except 1 and p.
Hint 1:
- (prime p) = its not true that a number between 2 and ... divides p,
and Reuse what you have written already.
Hint 2:
Make something work first, then worry about the speed
if you have the time and interest.
Trees
LISP data is stored in what is called a binary tree: each item
of data is a "leaf"(an atom), empty (NIL) or a pair (car . cdr).
We call the car and cdr of a pair the branches:
((1 . 2) . 3)
.
/ \
. 3
/ \
1 2
- tree::= NIL | leaf | pair,
- pair::= (car . cdr),
- leaf::=atom,
- car::=tree,
- cdr::=tree.
Here are some functions that are used to describe the properties
of a tree. Program each one in the most obvious way you can think of
so that it fits the rules given below.
Hint: This is an exercise in keeping your code simple. Just translate
each rule into a branch in a cond/if...
Height of a Tree
- height(tree)::=following
If tree is null then 0
- else if the tree is an atom then 1
- else one more than the maximum of the heights
of the two branches (the car and the cdr).
Examples to test
> (height nil)
0
> (height 'a)
1
> (height '(a.b))
2
> (height '((1 . 2) . (3 . (4 . 5))))
4
Hint:
(define (height tree) (cond ((Null tree) 0) ...
Size of a Tree
- The size of nil is zero
- The size of an atom is 1
- The size of a pair is the sum of the sizes of each branch.
Code the above in LISP.... and test it.
Leaves on a Tree
The number of leaves in a tree are the number of non-nil atoms
at the end of the branches
(leaves '(Leaves (of Grass)) )
has value 3.
- The leaves in nil are zero
- The leaves in an atom are one
- The leaves in a pair are the sum of the leaves in the branches.
Sum on a Tree
(Add up all the leaves assuming all leaves are numbers)
- The sum of nil is zero
- The sum of an atom is the atom (assumed to be a number)
- The sum of a pair is the sum of the sums of the branches.
Complete Tree
(a tree is complete if it has no NILs)
- a nil is not complete
- an atom is complete
- a pair is complete if the first branch is complete and so is the
other branch.
Hint: (AND whatever duh)
Infix notation
Develop an interpreter CALC for simple arithmetic expressions, like
the following:
( 1 + 2 )
( 1 + ( 3 * 2))
( (4 - 3) + ( 3 * 2))
with the following XBNF grammar:
- expression::=number | "(" expression operator expression ")",
- operator::= "+" | "-" | "*" | "/".
You would test it like this
(CALC '( (4 - 3) + ( 3 * 2)))
Don't for get the "'" above.
Hint: There are two approaches to this problem. One is simpler
because it uses more advanced LISP.
Choose your own Problem
See if you can think of a simple problem that
is a matter of manipulating data in list format.
(If you can't think of one see
[ Optional Exercises ]
below ).
Have a go at the problem... Develop it a function at a time and
allow time for your brain to work as you go...
Hints
- No graphics in a list.
- Files exist but you don't have time to learn them.
- Keep the input/output simple... layouts are not part of the
LISP way of life.
- Is there an intriguing function listed in the CS320 PLRM?
Learn to use it.
On the WWW
Use your favorite WWW Search engine to find some
examples of LISP in the internet. See if you can figure
out how they work.
[ Search in info1 ]
Prepare your LISP portfolio.
You are required to prepare an HTML file that describes and
lists the various things you have done with LISP and Scheme in this
class. You can get a template from
[ template.html ]
I'll be grading these at the end of the quarter so you
can always come back and polish today's draft.
Optional exercises
Long Arithmetic
LISP makes it easy to store and manipulate lists of numbers. Suppose
that we need to do "infinite length arithmetic" - positive numbers
with any number of decimals. We could choose to represent number like
this in LISP:
- '(0) means 0
- '(1) means 1
- ...
- '(9) means 9
- '(1 0) means 10
- '(1 1) means 11
- ...
- '(1 0 0) means one hundred
- ...
- '(1 2 3 4 5 6) means 1 million, two hundred and thirty four thousand,...
Can you quickly and simple write a function that takes two of these
numbers and adds them up: (LADD '(1 2 3) '(1 9 0)) = '(3 1 3)
You can take this all the way to subtraction, multiplication, division,
primes, factorials, and so on.... if you have 10 weeks to spare!
Hints: it helps to use '(reverse l)' and elementary school addition
with carries: (Long_add_reversed_with_carry carry_digit rev_num1 rev_num2).
SIGMA
Here you want to help a mathematician sum lots of different series.
You want a function called SIGMA that is like a mathematical \Sigma!
- (SIGMA first last formula)::= the sum with first..last of formula.
The formula must describe how to calculate any term.... it must therefore
take an argument (i) and return the value of the term. So it must be,
in LISP a lambda expression.
- Eg:
- (SIGMA 1 n (Lambda (i) i)) = n*(n+1)/2.
- (Sigma 1 n (lambda (i) (* i i i)))=(n*(n+1)/2)^2.
- Hint. I found (apply f (list n)) to be very helpful.
Differential Calculus
I did this while in line waiting for lunch when
I was an undergraduate.
Given a LISP expression that contains an atom X that represents
a simple differentiable function of X, output the LISP
expression that represents the differential of the function:
- (D 'X)::=1
- (D 'C)::=0 (C is any atom but X)
- (D '(* C X)) ::=C
- (D '(+ U V)) ::=(+ (D U) (D V)) (U and V are expressions themselves).
- (D '(* U V)) ::=(+ (* (D U) V) (* U (D V)))
and so on.... (don't spend more than 3 weeks polishing this) :-)