| Question | Mark |
| 1. Recursion, tail recursion [10 marks] | |
| 2. Lists and side effects [10 marks] | |
| 3. Higher order functions [10 marks] | |
| 4. Let over lambda [10 marks] | |
| 5. Macros and expansion [10 marks] | |
| Exam Total [50 marks] |
Question 1: Recursion, tail recursion [10]
(i) Provide a recursive solution to complete the sumpos function below.
; sumpos returns the sum of all its numeric arguments ; (0 if it has no numeric arguments) ; e.g. ; (sumpos 3.5 "foo" 20) ; returns 23.5 ; (sumpos) ; returns 0 (defun sumpos (&rest args) # ..... )(ii) Answer the following question: is your solution to part (i) tail recursive, almost-tail-recursive, or neither? Justify your answer.
Sample Solution
(defun sumpos (&rest args)
(cond
; the sum of nothing is 0
((null args) 0)
; if the front element isn't a number ignore it and return the sum of the rest
((not (numberp (car args))) (apply 'sumpos (cdr args)))
; if the list contains just a single number then return that number
((null (cdr args)) (car args))
; if the second thing isn't a number then cut it out and get the sum of the rest
((not (numberp (cadr args))) (apply 'sumpos (cons (car args) (cddr args))))
; otherwise add the front two elements together and recurse with the sum in front of the rest
; (using the front of the list to keep track of the sum so far)
(t (apply 'sumpos (cons (+ (car args) (cadr args)) (cddr args))))))
Yes, this is tail recursive, since the result of any recursive call to sumpos
is immediately returned as the result of the current call.
|
Question 2: Lists and side effects [10]
In the script below, function f1 does not have side effects, but function f2 does have side effects.
In terms of the underlying implementation of lists in our version of lisp, explain why this is the case.
#! /usr/bin/gcl -f (defun f1 (L) (if (and (listp L) (not (null L))) (setf L '()))) (defun f2 (L) (if (and (listp L) (not (null L))) (setf (cdr L) '()))) (defvar L '(1 2 3)) (f1 L) (format t "After (f1 L), L is ~A~%" L) (f2 L) (format t "After (f2 L), L is ~A~%" L) ; ----- resulting output ---- ; After (f1 L), L is (1 2 3) ; After (f2 L), L is (1)
Sample Solution
A list variable is actually represented as a reference to that list
(i.e. the address of the front of the list in memory)
Each element of the list is repesented in two parts:
the element value and a reference to the rest of the list
We thus have L--> 1,--> 2,--> 3,NULL
When we call (f1 L), the value of L (i.e. the pointer)
is copied to f1's parameter, L (same name, but a local value)
Inside f1, when we set L=nil, we're setting the local parameter L to nil,
but that doesn't change the original list,
For clarity, if we had used (defun f1 (tmp) ....
we'd be setting tmp to nil, but not the original L
When we call (f2 L), however,
f2 is following the pointers into the inner chain of L,
and altering one of those internal pointers,
i.e. when we set (cdr L)=nil what we're changing L to is
L--> 1,NULL
|
Question 3: Higher order functions [10]
Write a higher-order function, deepmap, which takes two parameters: a list of lists, LL, and a unary function, f.
deepmap applies function f to every non-list element contained in LL or any of its sublists (at any level of nesting), and composing a corresponding list of lists as the result.
For example,
e.g. (deepmap '- '( 1 2 (( 3 4) 5 ( 6 7))))
would return
(-1 -2 ((-3 -4) -5 (-6 -7)))
Your deepmap implementation is not required to check that f and the elements of LL are type-compatible.
Sample Solution
(defun deepmap (f L)
(cond
; if f isn't a function we can't do anything useful with it, just return L
((not (functionp f)) L)
; if L is an element, not a list, apply f to it and return the result
; (important for use in the recursive calls)
((not (listp L)) (funcall f L))
; if L is empty we're done
((null L) nil)
; in general, we need to call recursively on both the front element
; and the rest of the list, and cons the results back together,
; to maintain the overall structure of the list
(t (cons (deepmap f (car L)) (deepmap f (cdr L))))))
|
Question 4: Let over lambda [10]
Complete the time function described below using a let over lambda approach, i.e. time returns a lambda function that processes user commands of the forms shown below.
time is used to store/update times-of-day, represented using integer values for the hours and minutes and a 24-hour clock, i.e. times go from 0 0 to 23 59.
The user can provide an initial time as part of the instantiation process, otherwise a default value of 0 0 is used.
"Methods" are supported to get the current time as a list (gettime),
increment the current time by one minute (tick),
or set a new time (settime h m)
Examples of the correct use of time and its methods are shown below.
(defvar t1 (time 12 58)) ; initializes a time of 12 58, stores the lambda function in t1 (funcall t1 'tick) ; internal time adjusts to 12 59 (funcall t1 'gettime) ; returns (12 59) (funcall t1 'tick) ; internal time adjusts to 13 0 (funcall t1 'settime 10 13 ; sets the internal time to 10 13
Sample Solution
(defun time ( &optional (hh 0) (mm 0))
; use local variables to remember the current hour, minute, default to 0
(let ((hour 0) (min 0))
(labels
; increase the time by 1 minute
((tick ()
; add 1 minute
(setf min (+ 1 min))
; see if we've reached the top of the hour
(if (= 60 min)
(block AdjTime
(setf min 0)
; see if we've reached midnight
(setf hour (if (= 23 hour) 0 (+ 1 hour))))))
; return the current time
(gettime () (list hour min))
; set the current time, ignoring any invalid values
(settime (hh mm)
(if (and (integerp hh) (< hh 24) (>= hh 0)) (setf hour hh))
(if (and (integerp mm) (< mm 60) (>= mm 0)) (setf min mm))))
; --- end of labels local function defs ---
; inititalize hour and min from (mytime hh mm)
(settime hh mm)
; set up the dispatcher to handle user requests
(lambda (cmd &optional (hh 0) (mm 0))
(cond
((equalp cmd 'tick) (tick))
((equalp cmd 'gettime) (gettime))
((equalp cmd 'settime) (settime hh mm))
(t (format t "Error: invalid command ~A~%" cmd)))))))
|
Question 5: Macros and expansion [10]
(i) show the result of (eval (list (+ 1 2) (* 3 4)))
(ii) show the result of (eval '((+ 1 2) (* 3 4)))
(iii) explain why `(x y z) evaluates to '(x y z)
whereas `(x ,y z) evaluates to (list 'x y 'z)
(iv) show the result of the macro expansion below
(defmacro f (e L) `(if (listp ,L) (list ,e ,@L) (list ,e ,L))) (macroexpand-1 '(f 10 (20 x)))
Sample Solution
(i) (list (+ 1 2) (* 3 4)) evaluates to (3 12),
and then (eval (3 12)) crashes, complaining 3 is not a function
(ii) '((+ 1 2) (* 3 4)) evaluates to ((+ 1 2) (* 3 4)),
and then (eval ((+ 1 2) (* 3 4))) crashes, complaining (+ 1 2) is not a function
(iii) `(x y z) wants (x y z) returned verbatim,
and the simplest way to do that is simply to quote it
`(x ,y z) wants the contents of parameter y substituted
in the middle position, but x and z used verbatim,
hence the choice of (list 'x y 'z) which builds a list
from 'x, the value of y, and 'z
(iv) expanded macro is as follows:
(IF (LISTP (20 X)) (LIST 10 20 X) (LIST 10 (20 X)))
note that L is (20 x),
embedded as the list (20 X) for ,L
and the list contents embedded for ,@L
|