CSCI 330 Quiz 2: lisp II Sample Solutions

Question 1 Higher order functions [8 marks]

(i) Implement the lisp function f below as per its specifications.

(ii) Briefly explain how your function works and why it does (or does not) constitute a "higher order" function. 
; assuming fList is a list of function and i is an integer,
;    f applies the i'th function in the list to the R list of arguments
; e.g. (f 1 '(f1 f2 f3 f4) x y z) would run (f2 x y z)
;      (f 2 '(sqrt sin cos) 1.234) would run (cos 1.234)
;      (f 0 '(foo)) would run (foo)
; the only type checks you are required to perform are that
;     fList is a list and i is an integer in the range 0 to length(fList)-1
; f simply returns nil in the event of an invalid fList or i
(defun f (i fList &rest R)


Sample solution:
(defun f (i fList &rest R)
   (cond
      ; make sure they're the right types first
      ((not (listp fList)) nil)
      ((not (integerp i)) nil)
      ; then check 0 <= i < length(flist)
      ((< i 0) nil)
      ((<= (length fList) i) nil)
      ; then we need to use apply so it runs with the elements of R as individual args
      (t (apply (nth i fList) R))))

Question 2 Let over lambda [8 marks]

(i) Complete the implementation of the strManager function below as per its specifications
(the choice of whether or not to use a labels block is left to you).

(ii) Suppose we were to issue the commands (defvar S1 (strManager "foo")) and (defvar S2 (strManager "other"))
Briefly explain how/why the strings that could be manipulated through S1 and S2 are completely independent of one another. 
; using let-over-lambda, strManager stores a copy of s formatted as a string
;    and a dispatch function providing the user with the following commands:
;        'getI i: returns the ith char of s (nil if i is invalid)
;        'setI i c: sets the ith char of s to c (no action if i or c are invalid)
;        'content: returns the currently stored string
;        'size: returns the length of the currently stored string
;    the dispatcher prints an error message if an invalid command is passed
; thus some sample calls could be:
;    (defvar S (strManager "some text"))
;    (funcall S 'content) would return "some text"
;    (funcall S 'setI 4 #\r) would  change the stored content to "somertext"
(defun strManager (s)
   ; initializes str as a string of the original s
   (let ((str (format nil "~A" s)))


Sample solution:
; I found this easiest with labels functions, but they aren't required
(defun strManager (s)
   ; initializes str as a string of the original s
   (let ((str (format nil "~A" s)))
        (labels (
                  (validI (i) (and (integerp i) (>= i 0) (< i (length str))))
                  (getIth (i) (if (validI i) (char str i)))
                  (setIth (i c) (if (and (validI i) (characterp c)) (setf (char str i) c)))
                )
             ; need optional params for position i and character c
             (lambda (cmd &optional (i 0) (c #\-))
                (cond
                    ((equalp cmd 'content) str) ; just returning current string content
                    ((equalp cmd 'size) (length str)) ; # of chars in str
                    ((equalp cmd 'getI) (getIth i)) ; do the work in the labels function
                    ((equalp cmd 'setI) (setIth i c)) ; (same)
                    (t (format t "Invalid command ~A~%" cmd)))))))


(ii) explanation:

   - lists are dynamically allocated in the heap and maintained as long as something still
     references them
   - let block local variables are lists referenced by the returned dispatcher (lambda function)
   - one dispatcher (with its corresponding let block list) is stored in S1
   - another dispatcher (with its corresponding let block list) is stored in S2
   Thus we effectively get two different stored spaces being managed: one space accessed
   through the S1 lambda function and one space accessed through the S2 lambda function.
   These persist for as long as S1 and S2's values are still the lambdas.

Question 3 Macros [8 marks]

Provide an implementation of the applyInTurn macro described below.
then briefly describe how your macro carries out the rewrite of

(applyInTurn 14.3 sqrt log -) 
; applyInTurn is a recursive macro expecting to be passed a data value
;    followed by zero or more unary functions,
; and it then applies rewrites as follows:
;    (applyInTurn x) is rewritten as x
;    (applyInTurn x f) is rewritten as (f x)
;    (applyInTurn x f1 f2) is rewritten as (f2 (f1 x))
;    (applyInTurn x f1 f2 ... fk) is rewritten as (fk ... (f2 (f1 x))...)
; e.g.
;    (applyInTurn 265 sqrt log - floor)
;          is rewritten into (floor (- (log (sqrt 265))))
(defmacro applyInTurn (x &rest fList)


Sample solution:

Explanation (and answer to second part of question)

If we're given (applyInTurn 14.3 sqrt log -) we're trying to get the rewrite working
   from the inside out, e.g.
     ==> (applyInTurn (sqrt 14.3) log -)
     ==> (applyInTurn (log (sqrt 14.3)) -)
     ==> (applyInTurn (- (log (sqrt 14.3))) )
     ==> (- (log (sqrt 14.3)))
Thus at each stage we want to replace x with (f x) where f is the first function in fList
and remove f from fList for the recursive call.  When we get down to just (applyInTurn something)
we'll simply write out the something.

(defmacro applyInTurn (x &rest fList)
   (cond
      ((null fList) x) ; the base case
      (t `(applyInTurn ( ,(car fList) ,x ) ,@(cdr fList)))))

notes: the ` is needed for our recursive macro rewrite, so we'll need the commas and ,@ inside
       the ( ,(car fList) ,x ) is what produces our (f x)
       and the ,@(cdr fList) is what embeds all functions except f as individual arguments
           in the recursive call