| Question | Mark |
| 1. Accessing elements in nested lists [8 marks] | |
| 2. Tail recursion and accumulators [8 marks] | |
| 3. List implementation, implications [8 marks] | |
| 4. Higher order functions, closures [8 marks] | |
| 5. Pure functional programming vs let blocks [8 marks] | |
| Exam Total [40 marks] |
Question 1: Accessing elements in nested lists [8]
Implement the accessElement function described below.
; returns the j'th element of the i'th sublist of L, indices are 0-based, e.g.
; (accessElement '((5 10 20) (4.5) ("one" "two")) 2 0) would return "one"
; in the event of an error (invalid parameters, no such element, etc)
; the function returns 'ERROR
(defun accessElement (L i j)
Sample Solution
;
(defun accessElement (L i j)
(cond
((not (listp L)) 'ERROR)
((not (integerp i)) 'ERROR)
((not (integerp j)) 'ERROR)
((or (< i 0) (< j 0)) 'ERROR)
((< (length L) i) 'ERROR)
(t (let ((row (nth i L)))
(if (< (length row) j) 'ERROR
(nth j row))))))
|
Question 2: Tail recursion and accumulators [8]
(i) In your own words, briefly describe how the use of tail recursion can improve the effiency of programs in execution.
(ii) In your own words, briefly describe the role of an "accumulator" to enable tail-recursive functions.
(iii) Rewrite the function below to be tail recursive, making use of an accumulator.
(defun factorial (N)
(cond
((not (integerp N)) nil)
((< N 2) 1)
(t (* N (factorial (- N 1))))))
Sample Solution
;
; (i) If recognized/supported by the compiler/interpretter,
; tail recursive function calls can re-use the exact stack frame
; from the current call, rather than pushing a new stack frame.
; The parameter and local variable offsets are exactly the same as for
; the current call, only the actual data values need to be overwritten.
; This allows the run time and stack space used by the recursive call
; to very closely match that of an iterative version of the function,
; eliminating some of the primary drawbacks of recursive functions.
; (ii) In a tail recursive function, we cannot do any computation with the
; value returned by a recursive call before we actually return the
; value, e.g. return (* N (factorial(- N 1))) can't be used, since the value
; we're returning is computed as N times the value of the recursive call.
;
; The accumulator is used to pass any necessary extra information to the
; recursive call as extra parameters, so the final recursive call is
; capable of computing and returning the final answer, rather than an
; intermediate calculation.
; (iii) here as we compute N * N-1 * ... * current * (current-1) * ... * 1
; we'll use the accumulator to compute the product of N*(N-1)*...*(current+1),
; so that by the time we reach the call to (factorial 1 someval)
; the "someval" will actually contain the desired computed factorial
(defun factorial (N &optional (sofar 1))
(cond
((not (integerp N)) nil)
((< N 2) sofar)
(t (factorial (- N 1) (* sofar N)))))
|
Question 3: List implementation, implications [8]
(i) What happens if we run the lisp code segment below, and why?
(defvar L '(1 2 3 4 5)) (setf (cdddr L) (cdr L)) (format t "~A" L)
Sample Solution ; ; It prints 1 2 3 2 3 2 3 ... and an infinite sequence of "2 3"s, ; because we have created a circular list: making the ; pointer to the tail-of-the-tail-of-the-tail of L ; actually point to the tail of L. ; ; format then gets stuck in an infinite display sequence as it ; works its way through the linked list. |
(ii) Explain why the first call to setf below does not change the content of list L, but the second call does change the content of L.
(defvar L '(1 2 3 4 5)) (defvar X L) (setf X '(1 2)) (defvar Y L) (setf (cdr Y) '(10))
Sample Solution ; (defvar L '(1 2 3 4 5)) (defvar X L) ; at this point X: (1 2 3 4 5), L: (1 2 3 4 5) ; X and L are essentially just pointers to the same list (setf X '(1 2)) ; now X: (1 2), L: (1 2 3 4 5) ; we've simply changed which list X points to (defvar Y L) ; now Y: (1 2 3 4 5), L: (1 2 3 4 5) ; again, Y and L are essentially just pointers to the same list (setf (cdr Y) '(10)) ; now Y: (1 10), L: (1 10) ; this time we've used Y to access the tail of the list it points at, ; changing the contents there, but since L is pointing at the same ; list the change is visible there too |
Question 4: Higher order functions, closures [8]
(i) Given functions f and g below,
give the value that would be returned by the call
(f 'g '((1 2) 3))
(defun f (x y) (map 'list x y)) (defun g (z) (funcall 'cons z (list z)))
Sample Solution ; ; since we are passing g to parameter x, where ; f is mapping g to the second parameter, ((1 2) 3), ; i.e. running g on (1 2), running g on 3, and forming a list of the results ; g's functionality is to (cons z (list z)), effectively creating a list (z z), thus ; for the first call, (g '(1 2)) creates ((1 2) (1 2)) ; and for the second (g 3) creates (3 3) ; thus giving the final result ; (((1 2) (1 2)) (3 3)) |
(ii) In the code segment below, variable h is assigned the function created/returned by builder.
As accurately as you can, show the parameter list and body of h's function after the call. (Don't worry about showing the lambda-closure symbol or the environment lists.)
(defun builder (X Y)
(cond
((or (not (integerp X)) (not (integerp Y))) nil)
(t (let ((Z (* X Y)))
(lambda (N)
(cond
((not (numberp N)) 'ERROR)
((< N Z) nil)
(t (format nil "~A" (- N Z)))))))))
(defvar h (builder 3 5))
Sample Solution ; ; the returned function would have parameter list (N), ; ; and the body would look like ; ; (COND ; ((NOT (NUMBERP N)) 'ERROR) ; ((< N 15) NIL) ; (T (FORMAT NIL ~A (- N 15)))) |
Question 5: Pure functional programming vs let blocks [8]
In your own words:
(i) describe the way(s) in which let blocks violate the "purity" of functional programming,
Sample Solution ; ; let blocks introduce both state and sequence, ; both of which are not functionally pure ; ; the state is introduced through the let block's local variables, ; while the sequential component is introduced by let allowing ; the inclusion of multiple lisp statements following the ; local variables, and guaranteeing it will execute them ; in the order provided |
(ii) describe how let-over-lambda introduces OO-like concepts of state into common lisp.
Sample Solution ; ; **As mentioned, this is treated as a bonus question worth up to 3 extra marks** ; ; lists are implemented on the heap in lisp, and are not deallocated ; until there are no further references to them ; this includes the lists of local variables in a let block ; ; if our let block returns a lambda function that in turn accesses the ; local variables from the let block, then the local variables cannot ; be released until the returned lambda function itself is deallocated, ; which means the lambda function has sole access to that local variable space ; somewhere on the heap - effectively creating a local variable space just ; for that one generated lambda function, and acting very much like the ; local variable space associated with instances of a class in OO languages |