Question 1: tail recursion [8]
Describe a general process by which a tail recursive function can be developed from an iterative (loop-based) one, and provide a short code example to illustrate your approach.
Sample solution
Each of the local variables in the original iterative solution becomes
an optional parameter in the tail recursive one,
with a default value that matches the initialization value in the original
The base case/termination condition for the tail recursive solution is
the opposite of the continuation condition for the original loop,
The return value for the base case matches the post-loop return value
from the original
The general case for the tail recursive version is simply a recursive call,
but the value passed for each parameter represents the collected modifications
made to the corresponding variable in the body of the original loop
int f(int N) int f(int N, int i=1, int sum=0)
{ {
int sum = 0; if (i >= N) {
for (int i = 1; i < N; i++) { return sum;
sum = sum + i; } else {
} return f(N, i+1, sum+i);
return sum; }
} }
|
Question 2: list implementations [8]
Breifly outline the way common lisp implements lists, then discuss the impact this has on list copy operations (shallow/deep) and how that in turn might impact recursive functions passing lists as parameters.
Sample solution
List implements lists as a linked list of cells, each with two elements:
the cell data (the car)
a reference to the next cell (the cdr)
A list variable is actually a reference/pointer to the first cell
Shallow copies are performed whenever we use a defvar, setf, or pass a list as
a parameter to another function. These simply copy/pass the pointer/reference,
rather than building an entirely separate duplicate of the original list.
(The latter would be deep copies: specific functions exist to create deep copies
when desired, but these must be explicitly called if needed.)
When making a shallow copy, only the pointer value needs to be replicated,
which can be performed in constant time and takes constant space.
A deep copy, on the other hand, would require creating and storing an entirely
separate duplicate version, requiring time and space proportional to the
size of the original list.
The effect is particularly noticable in recursive functions that pass lists as
parameters, since with deep copy each recursive call would need to
duplicate and store the list.
In terms of behaviour, shallow copies introduce the possibility of side effects:
if multiple variables or parameters hold pointers/references to the same
stored list then if any of them change the content of the list then the
impact is observable by all of them: they're all accessing the same shared data.
|
Question 3: let-over-lambda [8]
(i) Discuss how let-over-lambda could be considered to provide object-oriented-like constructs in common lisp.
(ii) Could let-over-lambda work without the use of higher order functions? Justify your answer.
Sample solution
(i) The variables in the let block are uniquely associated with the specific
call to the construction function and the lambda dispatcher it returns.
This gives each dispatcher control over its own stored state, much like
an object has control over its own collection of stored fields.
The lambda dispatcher allows a caller to request access to or manipulation
of the stored state through a collection of fixed commands/messages, just as
an OO system uses messages/methods to request access to/manipulation of the
stored state of an object.
The construction function determines how the stored state is initially set,
based on the parameters passed to it. This acts much like the constructor
for a traditional object.
In theory, we could tweak our construction function to accept other
construction functions as parameters: e.g. if we had a 'buildVehicle'
construction function we could pass it (along with whatever other data)
to a 'buildBicycle' construction function. The buildBicycle could
pull the necessary components from the buildVehicle to allow a form
of inheritance. (It wouldn't be pretty, but it could be done.)
(ii) By definition, let-over-lambda returns a lambda function that controls
access to the stored internal state. That lambda function cannot be run,
and hence the stored state cannot be accessed, without the use of some
higher order function.
|
Question 4: pure functional languages [8]
Discuss the various ways in which let-over-lambda would not be regarded as functionally pure.
Sample solution The most glaring example of functional impurity is in the necessity of stored state: The idea of stored state is antithetical to the concept of pure functional programming, but LOL's entire scheme for representing objects revolves around having a unique and persistent stored state associated with each individual object/dispatcher (coming from the let block within the original construction function). Generally speaking, this stored state is intended to be manipulated through the commands sent to the dispatcher and the resulting code it runs on the let block variables. This means that the dispatcher function must have side effects, which is again in direct opposition to a pure functional approach. I would probably argue that the capability for let blocks to support sequencing is not a direct issue with the LOL approach vs functional purity, as there is no reason the LOL programmer has to adopt an impure approach here: the body of the let block could simply be a single function call whose return value is the constructed lambda function. |
Question 5: macros [8]
The recursive variadic macro below is intended to operate somewhat like the reduce function, but reducing across the set of arguments passed to the function instead of reducing across the contents of a list.
(defmacro reduceArgs (f x1 x2 &rest others)
(if (null others) `(,f ,x1 ,x2)
`(reduceArgs ,f (,f ,x1 ,x2) ,@others)))
|
Sample solution
**Unintended glitch in the question that was caught by at least one person:
the 'list in the sample calls should have just been list, e.g. (reduceArgs list 3 4 5 6)
Other than the glitch in the call examples,
the macro does, in fact, work as intended.
The macro's base case, e.g. (reduceArgs list x y), would indeed
generate (foo x y) since others would be null
The macro's general case takes the x1 and x2 two data values
and transforms them into a single element, i.e. (f x1 x2),
which will be the x1 in the recursive call.
The current first element of others then becomes the x2 value
for the recursive call, thus peeling off one more argument
with each layer of recursion.
The construction thus layers:
(f x1 x2)
(f (f x1 x2) x3)
(f (f (f x1 x2) x3) x4)
etc.
Thus a call like (reduceArgs list 3 4 5 6) becomes
(list (list (list 3 4) 5) 6)
|