Assignment 1: Part B [100 marks]
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 using the 'submit'
command available on CDF machines. The submission should be a single ascii
file. 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 B [100 marks]
6. [20 marks] The Tower of Hanoi problem is defined as follows: There are
three stacks A, B and C containing a total of N disks of unequal
size. Initially the disks are all in stack A sorted according to size
(smallest at the top), and stacks B and C are empty. The problem is to move
all the disks to stack C, again sorted according to size (again smallest at
the top), using only one operation move such that
move(X,Y) moves the top disk of stack X to the top of stack Y,
provided the top disk of X is smaller than the top disk of Y, or Y is
empty
, where X and Y can be any of the three stacks.
Assuming that we start with A = [1 2 3], B = [], C = [] and that disk 1 is
smallest and at the top of stack A, here is a sequence of moves that solves
the Tower of Hanoi problem for N = 3:
move disk 1 from A to C
move disk 2 from A to B
move disk 1 from C to B
move disk 3 from A to C
move disk 1 from B to A
move disk 2 from B to C
move disk 1 from A to C
Write a Lisp function tower-of-hanoi(n) which solves the problem for any
number of disks n. Estimate the complexity of your algorithm and estimate how
many function calls will be required to solve the problem for 64
disks. Justify carefully your estimations.
The output of your function should be a list of the moves made to solve the
problem, as shown above.
7. [30 marks] Suppose that an arithmetic expression is any functional form
using only plus and times as functions, and using only numbers, variables
(literal atoms), and (nested) arithmetic expressions as arguments. An example
is the following:
(plus x 3 5 (times (times x y z) 0) (plus 3))
Write a Lisp function simplify which takes an arithmetic expression and
returns it in simplified form. Your function ought to use the following
simplification rules:
(a) any subexpression consisting of the function times followed by a list of
arguments, one of which is 0, is replaced by 0,
(b) any occurrence of 1 as an argument to times is eliminated, and then if
possible, the occurrence of times is eliminated if it is left with a single
argument,
(c) any occurrence of 0 as an argument to plus is eliminated, and if only one
argument remains the occurrence of plus is eliminated,
(d) If plus or times sub-expressions have several constant arguments, these
are summed or multiplied out to reduce the number of operands within each
subexpression.
(e) if the s-expression does not conform to the syntax described above,
simplify returns an error.
For example,
(simplify '(plus x 3 5 (times (times x y z) 0) (plus 3)))
returns (plus x 11)
(simplify '(plus (times 2 0) (3 5))) returns error.
8. [20 marks] A rational number may be represented by a dotted pair (n . d)
of integers where n is the numerator and d is the denominator. Write the
following Lisp functions, which accept rational numbers as their arguments.
The resulting rational should be in simplified form.
(a) add-rationals computes the sum of its one or more rational arguments.
(b) subtract-rationals subtracts the first argument from the other.
(c) multi-rationals computes the product ofone or more rationals.
(d) div-rationals divides its first arguments by the second.
For example,
(add-rationals '(1 . 3) '(2 . 3) '(4 . 5)) returns (9 . 5)
(add-rationals '(7 . 5) '(-3 . 15)) returns (6 . 5).
(subtract-rationals '(6 . 5) '(-3 . 15)) returns (7 5).
(multi-rationals '(-2 . 3) '(-3 . 7)) returns (2. 7).
(div-rationals '(1 . 3) '(0 . 3)) returns error.
(div-rationals '(2 . 3) '(-1 . -3)) returns (2 . 1)
9. [30 marks] Write a Lisp function rec-to-it which takes as argument an
s-expression which defines a simple recursive function and translates it to an
equivalent iterative one which uses the Lisp prog special form. For example,
(defun fact (n)
(cond ((= n 1) 1)
(t (* n (fact (- n 1))))))
is translated into
(defun fact (n)
(prog (aux)
(setf aux 1)
loop
(cond ((= n 1) (return aux)))
(setf aux (* aux n))
(setf n (- n 1))
(go loop) ))
You may assume that simple recursive functions have the form
(defun fcn (n)
(cond (simpleCase nonRecursiveValue)
(t f o recursiveCall). .))
where f is some subexpression, n is a positive integer or a list, and % is a
composition operator.
Bonus marks [10 marks] Generalize the solution of question 9 so that it works
for more general recursive functions having the form
(defun fcn (n)
(cond (simpleCase1 nonRecursiveValue1)
(simpleCase2 nonRecursiveValue2)
...
(hardCase1 f1 o recursiveCall1)
(hardCase2 f2 o recursiveCall2)
...
(t fn o recursiveCalln)))