University of Toronto
                      Faculty of Arts and Science

             CSC324 -- Principles of Programming Languages
                              Spring 1998

		Department:		Computer Science
		Instructor:		John Mylopoulos
		Date:			January 13, 1998


				Assignment 1:
                    Functional Programming with Lisp

	   Due Dates
	       Part A:  6:10pm, Tuesday, January 27, 1998
	       Part B:  6:10pm, Tuesday, February 10, 1998

	       This assignment counts for 15% of the final grade


All programs should be written in Lisp and should be well documented and
thoroughly tested. Make sure you use good functional programming style; marks
will be deducted for programs that look like translated Turing or C.

Assignments should be handed in electronically  by sending a single ascii file
to jm@cs.toronto.edu. The file should include your answers to all questions of
the assignment (including text, programs and documentation), followed by all
test data. For submitted programs, your answer should include a listing of
program code, along with comments and other documentation. 

Part A [50 marks]

You are only allowed to use the basic functions of Lisp, i.e., car, cdr, cons,
eq (or other  equality  predicates), null, atom, listp cond, defun,  lambda
and (if  necessary) helping functions defined in terms of these. For questions
which require the definition of one or more functions, verify your answers by
running them before handing them in.

1. [5 marks] Consider the Lisp forms

   (list e1 e2)
   (cons e1 e2)
   (cons (car e1) (car e2))
   (cons (cdr e1) (cdr e2))
   (cons (car (car e1)) (cdr (car e2)))

where e's are forms.  For each of them, state what restriction is required
on the value of , and what the value of the form is in terms of the value
of . For example,

   (car e)		e must be a list, returns 1st element of val

2. [10 marks] Write a function count-atoms which takes as argument a list and
counts its atoms. For example, 

       (count-atoms '(a (b))			returns 2
       (count-atoms '(a nil (nil) (((b a))))	returns 5, etc.

3. [10 marks] Write a function flatten which takes as input a list and
RflattensS it by removing all parentheses within. For example, 

	   (flatten '(a (b))			      returns (a b)
	   (flatten '(a (b (a a)) (()) ((a)))) returns (a b a a nil a).

4. [10 marks] Write a function rm-duplicate of one argument (a list), which
returns the input list with all duplicate elements removed. For example, 

	(rm-duplicate '(a b a a (this) a (this))) returns (a b (this)).
	(rm-duplicate '(a b (a a (this)) a (this))) 
					   returns (a b (a a (this)) (this))

Note that removal of duplicates is only done at the top level of the argument
list.

5. [15 marks] Write a Lisp program which solves the pancake problem. Pancake
stacks are to be represented by a list of integers 1, 2, ..., n, e.g., (4 2 7
5 6 1 3), or ( 3 6 8 2 4 7 9 1 5). You may assume that the input list always
consists of n integers from 1 to n, in random order. The output of your
program should be an ordered list, e.g., (1 2 3 ... n).

To transform the input list, you are allowed to use the flip function which
takes a list and an integer i, and flips the top of the list up to and
including the ith element. For example,

	  (flip '(3 5 4 1 2) 3)	returns	(4 5 3 1 2)
	  (flip '(3 5 4 1 2) 4)	returns	(1 4 5 3 2)

You can now write the pancake function which takes as argument a unordered
list of integers and returns an ordered list by using only the flip operation.

     (pancake '(3 5 4 1 2))	returns	(1 2 3 4 5)
     (pancake '(3 5 7 4 1 6 2))	returns	(1 2 3 4 5 6 7)

Explain carefully how does the pancake algorithm work and what is its
computational complexity, given an input list of length N.

For this problem, you may use build-in Lisp functions such as append, reverse
and length.


Part B [100 marks]

/* To be handed out January 20.  */