| Question | Mark |
| 1. Keyword parameters and dynamic scope [10 marks] | |
| 2. Closures [10 marks] | |
| 3. Tail recursion [10 marks] | |
| 4. Basic lisp [10 marks] | |
| 5. Pure functional programming [10 marks] | |
| Exam Total [50 marks] |
Question 1: Keyword parameters and dynamic scope [10]
(i) Rewrite function f below so that it uses positional parameter passing for x, keyword parameter passing for y and z, and accesses W as a dynamically-scoped variable rather than through a parameter.
(defun f (w x y z)
(let* ((a (if (and (numberp w) (numberp x) (/= x 0)) (/ w x) 1))
(b (if (integerp y) (/ y a) y)))
(format nil "~A~A" z b)))
|
(ii) For your revised function, show the return value of the following let block:
(let ((W 3/2)) (f 4 :z '(2 2) :y 6)) |
Sample solution
(i) With respect to the dynamic-scoping portion, the correct answer is
that the dynamically-scoped W needs to be declared externally
(e.g. with a (declare (special W)) or a defvar),
but if folks used the (declare (special W)) within the function
(as per the notes I gave you) I accepted that too.
For the x/y/z portion, it is simply a matter of changing the
first line of the function definition to
(defun f (x &key y z)
(ii) The return value from the function is the string built by
the format, i.e. "(2 2)16"
Reminder: /= is "not equals", and
let* does its local variable assignments in sequence,
so a=w/x, i.e. (3/2)/4, which is 3/8
and b=y/a, i.e. 6/(3/8), which is 48/3, i.e. 16
The function output is not required in the answer, but would be
a:3/8, b:16, w:3/2, x:4, y:6, z:(2 2)
|
Question 2: Closures [10]
(i) Given the builder function below, show the lambda function built/returned as a result of the call: (builder 3 9)
(defun builder (n e)
(let* ((Num (if (and (integerp n) (> n 0)) n 0))
(Rep (make-sequence 'list Num :initial-element e)))
(lambda (L)
(let ((Res nil))
(dolist (x L)
(setf Res (if (equalp x e) (append Res Rep)
(append Res (list x)))))
Res))))
|
(ii) Show the value that would be returned if the lambda function from part (i) was called on the list (4 "foo" 9 (9)).
Sample solution
(i) The full return value of the lambda function would be a lambda-closure,
three environment lists, and the body, e.g.:
(LAMBDA-CLOSURE
((REP (9 9 9)) (NUM 3) (E 9) (N 3)) () ((BUILDER BLOCK #<@someAddress>)) (L)
(LET ((RES NIL))
(DOLIST (X L)
(SETF RES (IF (EQUALP X E) (APPEND RES REP) (APPEND RES (LIST X)))))
RES))
but I'll accept answers along the line of
(lambda (L)
(let ((Res nil))
(dolist (x L)
(setf Res (if (equalp x 9) (append Res '(9 9 9))
(append Res '(9)))))
Res))
(ii) The effect of the lambda function is to replace any/all list elements
matching E with a list of N E's, so replacing the single 9 with (9 9 9),
hence the result is (4 foo 9 9 9 (9))
|
Question 3: [10]
(i) Briefly explain the role of accumulators in tail recursive functions.
(ii) Is the reduce function below tail recursive or not? Justify your answer.
(defun reduce (op first &rest r)
(cond
; base case
((null r) first)
(t (apply 'reduce
; form list of the operator,
; the result of op on first two values to process,
; and all the remaining values
(cons op (cons (funcall op first (car r)) (cdr r)))))))
; sample call
(format t "~A~%" (reduce '- 10 4 1 -2)) ; displays 7 i.e. (((10 - 4) - 1) - -2)
|
Sample solution
(i) Accumulators are an extra (often optional) parameter added to
a recursive function to permit partially-calculated values
to be passed to a recursive call, allowing the recursive call
to compute the final result to the overall computation (as
opposed to having the recursive call compute/return a partial
result, and having the caller then complete the computation),
thus in turn enabling the use of tail recursive solutions on
a wider range of problems.
(ii) The reduce function shown is indeed tail recursive, since the
result of the recursive call (i.e. of applying reduce to the
parameter list) is also the result to be returned from the
current call.
|
Question 4: [10] Basic lisp
Write a function named countSym that expects a symbol, S, and a list, L, as parameters and counts the number of times the symbol appears as an element of L or any sublist of L, including nested lists. If S is not a symbol or L is not a list the function should return 0.
For example, the following call should return 5:
(countSym 'foo '(foo (1 2 foo 3) (foo 10 20) (foo (foo 2 4))))
Sample solution
(defun countSym (S L)
(cond
; catch the error/base cases
((not (symbolp S)) 0)
((not (listp L)) 0)
((null L) 0)
; catch the case where we have a sublist to process
((listp (car L)) (+ (countSym S (car L)) (countSym S (cdr L))))
; catch the case where we've found an instance of symbol S
((equalp S (car L)) (+ 1 (countSym S (cdr L))))
; general case, neither a sublist nor the symbol S
(t (countSym S (cdr L)))))
|
Question 5: Pure functional programming [10]
(i) Explain why function f below would not be regarded as "pure" functional programming.
(ii) Rewrite the function so that it provides the same results, but produces them in a "pure" fashion. (You may create/use "pure" helper functions if needed, and can treat the use of defun as acceptable.)
(defun f (x)
(let ((a 1) (L '(nil)))
(if (listp x) (cons a x)
(cons x (cons a L)))))
|
Sample solution
(i) This isn't regarded as pure since it is using local variables to
maintain state.
If x is a list, this returns a list with 1 as car, x as cdr
otherwise it returns a list with x as car and (1) as cdr,
which can also be regarded as a side effect, involving x,
another "impurity".
(ii) We can eliminate the local variables by replacing them with a call
to an extra/hidden function, taking them (and the original x) as
parameters. The hidden function performs the body of the original
f, while the original f just sets up and calls the hidden function.
If x is actually a list, we can ensure the list we return uses
a copy of x, rather than the original, using copy-list
(defun hiddenF (x a L)
(if (listp x) (cons a (copy-list x))
(cons x (cons a L))))
(defun pureF (x)
(hiddenF x 1 '(nil)))
|