;;;; Assignment 1, Rewrites and Recursion
;;;;
;;;; File:         asst1.txt
;;;; Author:       CS 51 (walton@deas)
;;;; Version:      4

This assignment has two parts, a theory part, and a
coding part.  In the theory part you must solve some
problems from Chapter 1 of Introduction to Symbolic
Computing.  In the coding part you must write several
short functions to be found in the file functions.lsp.
You must test your function code using the file
functions.in.

========================================================

The specific things you must do are:

(0) Do assignment 0, which prepares you to do
    assignment 1.

    You should read Chapters 2 and 3 of Graham's book
    and Chapter 1 of Introducton to Symbolic Computing.

(1) For the theory part, do the following exercises
    from Introduction to Symbolic Computing:

	1.5.2.2(g)
	1.5.3.1(d)
	1.5.3.3(d1)
	1.5.4.1(a)
	1.5.4.1(c)
	1.5.4.2(f)  (due to typo this is (e) at top of
		     second column)

    It is easiest to handwrite your answers.  Staple
    this theory part separately as it is to be turned
    in separately from the coding part and the two parts
    will be graded by separate graders.

(2) Write (type into functions.lsp) the rewrite rules
    (RR) for the functions:

	fibonacci
	copy-types
	my-intersection
	look-into

    This is the design part of this assignment.

(3) Write the code for the above functions (type it
    into functions.lsp).

    You are NOT permitted to use SETF or DO in this
    code.  You MUST use PURE LISP and RECURSION.  If
    you do this you will find these functions are very
    short.

    You are NOT permitted to use functions not described
    in Chapter 1 of Introduction to Symbolic Computing.
    In particular, you must not use the COMMONLISP
    INTERSECTION function to implement MY-INTERSECTION.

    You MUST indent your code in a proper readable
    fashion.  Learn to use == and =% in vi.

(4) Test the code by running:

	make functions.out

    and looking at the results.

(5) When you have finished all the above, submit
    electronically by executing

	make submit

    Then print a copy for the grader by executing

	make sprint

    If your laser printer budget has not been
    established by the time assignment 1 is due, use

	make print

    instead of `make sprint'.

(6) Turn in the theory part of the assignment and
    the output of `make sprint' at the class after
    the assignment due date listed in the syllabus.

    Do NOT staple the theory part and the `make sprint'
    output together.  These two parts go to separate
    graders.


========================================================

The theory part is worth 25 points, the rewrite rules
in functions.lsp are worth 10 points, and the code
code is worth 25 points.  Should you omit a
function (or need to copy it from someone: be sure to
comment that you have done so), points will be
subtracted as follows:

	fibonacci		5
	copy-types		6
	my-intersection		7
	look-into		6

These points happen to equal the number of lines of
code containing a `)' in a well written version of
the function (they also happen to add to almost 25).

========================================================


Hints:

(0) Do the theory before you write functions whose
    definition depends on the theory.

    Discuss related but UNASSIGNED exercises with
    other students or instructors.

(1) You can do this assignment one function at a time.
    START EARLY.

    You can do the fibonacci function before you have
    finished reading about symbolic data.

    It is usually most efficient to write the rewrite
    rules on paper first and then a rough draft of the
    function on paper.

(2) The lectures on arithmetic and rewrite rules, and
    on symbolic data, contain the basic information
    required to do this assignment.  The LOOK-INTO
    function requires knowlege of FUNCALL.

    You should read as much of Graham's book as you need
    to understand the COMMONLISP required by this
    assignment.

(3) We suggest you write the RR for a function first,
    then write the code, then test, all before going
    on to the next function.  After you get the hang
    of it you can try several functions at once, but
    until you do, one function at a time is best.

(4) FIBONNACI.  We give you the mathematical form of
    the rewrite rules.  YOU are expected to give
    us the LISP form of the rewrite rules.

(5) COPY-TYPES.  This function mostly copies an
    s-expression.  To copy an s-expression you look at
    the input: if it is an atom, you output an atom, and
    if it is a cons cell, you make copies of the car and
    cdr of the cons cell and put the copies together
    with the cons function.  For each atom you find, you
    need to output 'symbol or 'number if the atom is not
    NIL.  The SYMBOLP and NUMBERP functions are helpful.

(6) MY-INTERSECTION.  This is a matter of copying the
    first list and is somewhat like APPEND.  However, an
    element is NOT copied to the output if it is not a
    MEMBER of the second list.

(7) LOOK-INTO.  This is just a matter of exploring an
    s-expression and testing each atom.  If the input
    is NIL, you output NIL.  If it is a non-NIL atom,
    you apply the predicate to the atom to get the
    output.  If the input is a cons cell, you test the
    car and the cdr of the input, and if either is true,
    you output true, but if both are false (NIL), you
    output false (NIL).  The OR function is helpful.

Good Luck!