Please use the alphabetical Index, Contents List, and your browsers search feature to find what you need.

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.


Contents


    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

  1. Forget about efficiency in this lab.
  2. Define a collection of functions that can be used individually and together to solve a set of problems - like stats.lsp.
  3. Do one function at a time.
  4. Give functions meaningful names
  5. Use (help name) to see if it exists before you write it!
  6. Arguments can be one character long.
  7. 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.
  8. 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:

      1. Input this command to UNIX:
         			Q setup
      2. Down load/Save this file as text: [ show.lsp ]
      3. Run this UNIX command:
         			vi show.lsp
      4. Look at it... and then just tap the 'q' key...
      5. Watch what happens...
      6. Try these command:
         			SHOW
         			(show '(a b))
         			(show '(a b c))
         			(show '(a b c d))
         			(show '((a b)(c d)))
      7. 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:
    1. day: an integer
    2. month: an integer
    3. 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:
    1. (Day x)::= the day in date x
    2. (Month x)::= the month in date x
    3. (Year x)::= the year of date x.

    Define these functions (they are very simple!) and test that they fit the following rules:
    1. (Day (date x y z) ) is x
    2. (month (date x y z) ) is y
    3. (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
  9. (div? x y)::= #t if x divides y and #f otherwise and in LISP
  10. (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:
  11. (divn? x y)::scheme=#t iff any number from 2 up to x divides y else false
  12. (divnp x y)::LISP=T iff some integer from 2 to x inclusive divides y.

    Hint: forget loops look for recursion!


    1. (divnp 2 y) = (divp 2 y)
    2. (divnp 3 y) = (divp 3 y) or else (divnp 2 y)
    3. (divnp 4 y) = (divp 4 y) or else (divnp 3 y)
    4. (divnp 5 y) = (divp 5 y) or else (divnp 4 y)
    5. So...

    Test for Number being Prime

    Define a function that tests for primality/primeness
  13. (prime? p)::scheme= p is NOT divisible by any number except 1 and p.
  14. (primep p)::LISP= p is NOT divisible by any number except 1 and p.

    Hint 1:

  15. (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
    1. tree::= NIL | leaf | pair,
    2. pair::= (car . cdr),
    3. leaf::=atom,
    4. car::=tree,
    5. 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

  16. height(tree)::=following

      If tree is null then 0
    1. else if the tree is an atom then 1
    2. 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


    1. The size of nil is zero
    2. The size of an atom is 1
    3. 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.
    1. The leaves in nil are zero
    2. The leaves in an atom are one
    3. 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)
    1. The sum of nil is zero
    2. The sum of an atom is the atom (assumed to be a number)
    3. 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)
    1. a nil is not complete
    2. an atom is complete
    3. 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:
    1. expression::=number | "(" expression operator expression ")",
    2. 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


    1. No graphics in a list.
    2. Files exist but you don't have time to learn them.
    3. Keep the input/output simple... layouts are not part of the LISP way of life.
    4. 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:
    1. '(0) means 0
    2. '(1) means 1
    3. ...
    4. '(9) means 9
    5. '(1 0) means 10
    6. '(1 1) means 11
    7. ...
    8. '(1 0 0) means one hundred
    9. ...
    10. '(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!

  17. (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.
  18. Eg:
    1. (SIGMA 1 n (Lambda (i) i)) = n*(n+1)/2.
    2. (Sigma 1 n (lambda (i) (* i i i)))=(n*(n+1)/2)^2.
  19. 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:

    1. (D 'X)::=1
    2. (D 'C)::=0 (C is any atom but X)
    3. (D '(* C X)) ::=C
    4. (D '(+ U V)) ::=(+ (D U) (D V)) (U and V are expressions themselves).
    5. (D '(* U V)) ::=(+ (* (D U) V) (* U (D V)))
    and so on.... (don't spend more than 3 weeks polishing this) :-)

Labels and Definitions in Alphabetical Order