| Question | Mark |
| 1. tail recursion and parameter handling [8 marks] | |
| 2. list implementations and functional purity [8 marks] | |
| 3. let-over-lambda and higher order functions [8 marks] | |
| 4. macros [8 marks] | |
| Exam Total [40 marks] |
Question 1: tail recursion and lisp parameters [10]
(i) Provide a short definition of tail recursion and a short description of its significance in the context of the compilation and runtime efficiency of recursive functions.
(ii) Briefly describe what an accumulator is (in the context of tail recursive functions) and the role of optional parameters and default values for accumulators.
(iii) Provide an implementation of a simple tail-recursive function that utilizes an accumulator and clearly reflects your answers for (i) and (ii) above.
Sample solution
(i) A function is tail recursive if the results of every recursive call are immediately returned:
no processing is done between the recursive call completion and the caller's return.
This is significant because once the call is reached there is no further use for the
caller's stack frame, and it can be reused/overwritten to server as the called function's
stack frame. This removes the most crucial memory and running time efficiency issues
normally associated with deep recursion, but relies on the compiler's ability to both
recognize that the function is tail recursive and to reuse/overwrite the current stack
frame instead of creating a new one.
(ii) Accumulators are extra parameters often utilized by tail recursive functions as a place/way
to store partial (accumulated) data and solutions as the series of recursive calls progress.
This allows the final call in the chain to return the final computed answer without the need
for further processing as the recursion unwinds. This directly supports/enables easier
development of tail recursive functions.
Accumulators are often implemented as optional parameters whose default values are the
desired initial values for the accumulators (the starting points for the data/partial solutions),
and means the original call to the TR function can be made without any need for the caller
to even know of the existence of the accumulators.
(iii) The sample tail recursive function below returns the smallest number in a list (nil if there
isn't one) by using an accumulator to track the smallest number seen so far (and initialized
to nil, representing the idea that no number has been seent yet).
(defun smallest (L &optional (sofar nil))
(cond
((not (listp L)) sofar)
((null L) sofar)
((not (numberp (car L))) (smallest (cdr L) sofar))
((null sofar) (smallest (cdr L) (car L)))
((<= (car L) sofar) (smallest (cdr L) sofar))
(t (smallest (cdr L) (car L)))))
|
Question 2: list implementations and side effects [10]
**As noted during the midterm, there is a missing ( in the question, the > test should be (> (length L) 2) (i) Using the list '( 5 10 (20 30) 40) as an example, sketch and briefly describe how lists are implemented in common lisp.
(ii) For the code segment below, show the result of running the segment and clearly explain the role of list implementations on the behaviour of the code segment.
(defvar mylist `(5 10 (20 30) 40))
(defun q2 (L)
(if (and (listp L) (> length L) 2)
(setf (caddr L) 15)))
(q2 mylist)
(format t "~A~%" mylist)
Sample solution
(i) A list is a reference to the first in a series of (heap-allocated) cells,
each of which with two parts:
a head (car) which contains either a primitive value (integer, real, char, etc)
or a reference to another non-primitive object
a tail (cdr) which contains a reference to the next cell in the list
For (5 10 (20 30) 40) the series of cells would look like
5,---> 10,---> +,---> 40,nil
|
v
20,---> 30,nil
(ii) Parameters are passed by value in lisp, but because mylist is a reference
the parameter L is also a reference to the first cell in the same list.
Thus when the function enters and manipulates the contents of the individual
cells (accessed via L), it is changing the contents of the list mylist refers to.
mylist is (5 10 (20 30) 40), so is a list and has length > 2,
so within the function the 'if' conditions are satisfied and the setf is applied
(caddr L) is (car (cdr (cdr L)))
(cdr L) is (10 (20 30) 40)
(cdr (cdr L)) is ((20 30) 40)
(car (cdr (cdr L))) is the (20 30)
so the effect of the setf is to replace the cell's reference to (20 30)
with the primitive value 15
i.e. the list becomes
(5 10 15 40)
|
Question 3: let-over-lambda and higher-order functions [10]
(i) Explain the role of 'let-over-lambda' constructs in emulating object-like behaviour in common lisp, and how the returned lambda can function as a 'dispatcher' to manipulate the stored state of an object.
(ii) Illustrate your answer from (i) above by providing a short implementation of a let-over-lambda function and calls to at least two different commands through the returned lambda 'dispatcher'.
Sample solution
(i) All lists are dynamically allocated on the heap,
and persist as long as anything still references them.
This includes a let block's local variables within a let-over-lambda construct:
they continue to exist as long as the returned lambda function continues
to exist, thus the returned lambda has continuing access to the list of
local variables uniquely created in the function call that generated the lambda
This means the lambda can treat those variables as a persistent state, accessible only to it.
The lambda's parameters can be used as a means for the programmer to pass
messages/options to the lambda, instructing it on what forms of manipulation to apply
to this hidden data.
The lambda thus acts like a dispatcher, applying passed commands to the representation
of a hidden object.
(ii) bldPoint stores and manipulates a representation of a 2D point
using its x and y coordinates: right now it just allows the user
to initialize the point and pass commands to set new x,y values
or to print the current x,y values
(defun bldPoint (initX initY)
(let ((x 0) (y 0))
(labels ((set (nx ny) (when (and (numberp nx) (numberp ny))
(setf x nx)
(setf y ny)))
(prt () (format t "(~A,~A)" x y)))
(set initx inity) ; initialization with err checks
(lambda (cmd &optional (nx 0) (ny 0))
(cond
((equalp cmd 'SET) (set nx ny))
((equalp cmd 'PRT) (prt))
(t (format t "Invalid command ~A~%" cmd)))))))
(defvar P (bldPoint -1 7)) ; get a dispatcher, initialized for point (-1,7)
(funcall P 'PRT) ; have the dispatcher print the point
(funcall P 'SET 3 5) ; have the dispatcher change the point to (3,5)
(funcall P 'PRT) ; print it again
|
Question 4: macros [10]
(i) Explain the role of lisp macros in customizing syntax and how that can be used to improve readability and maintainability in code development.
(ii) To illustrate your answer to (i) above, write a short/simple lisp macro and a source code segment using that macro, and show the expanded code that would result after the macro was applied.
(iii) Summarize some of the disadvantages commonly associated with the use of macros in common lisp.
Sample solution
(i) macros act as a preprocessing step before compilation,
reading source code and using the macro's rules to rewrite it
the source code can thus use/contain syntax/features not normally
supported by core lisp, allowing the developer to write code using
simpler or more natural syntax (thus more readable and maintainable)
and have it automatically transformed into valid lisp
many common lisp features are actually such macros, e.g. let, when, unless,
cond, dolist, dotimes, loop, etc
(ii) Our swap example is used here:
(defmacro swap (x y)
(let ((tmpname (gensym)))
`(let ((,tmpname ,x))
(setf ,x ,y)
(setf ,y ,tmpname))))
(swap a b) ; original source
(let ((G123 a)) (setf a b) (setf b G123)) ; transformed code, where G123 would be
; whatever unique name gensym generated
(iii) The two biggest disadvantages are
1. the complexity of writing, debugging, and maintaining the macros themselves
2. the fact that compilation is based on the transformed code,
so any warnings/errors generated during compilation might be stated in terms
that the programmer finds difficult to relate to their original source code
|