CSCI 330 Quiz 2: 2024

CSCI 330 Quiz 2: lisp II Sample Solutions

Question 1 [4 marks]

This question has two parts (part b is on the reverse side of the page).

Part a: higher order functions

Suppose we have the following function (body left blank for the moment):

   (defun f (x L)
      ; body would be here
   )

Assuming x was a passed function and L was a passed data value, provide a single lisp statement for the body of f that would run x on L
```
Sample solution

 (funcall x L)
```
Assuming x was a passed function and L was a passed list, provide a single lisp statement for the body of f that would run x on the elements of L, e.g. if L was (10 20 30) it would run the equivalent of (x 10 20 30).
```
Sample solution

(apply x L)
```
Assuming x was a passed function and L was a passed list, provide a single lisp statement for the body of f that would run x once on each of the elements of L, forming a list of the results, e.g. if L was (10 20 30) it would form and return a list from the results of (x 10) (x 20) (x 30).
```
Sample solution

(mapcar x L)
```

Part b: let over lambda

Study the function below before answering questions (i) and (ii).

(defun q3 (n d)
   (let ; local variables
       ((num 0) (denom 1))

       (labels (; local functions
           (scale (s) (if (realp s) (setf num (* num s))))
           (prod (pn pd)
              (when (and (realp pn) (realp pd))
                  (setf num (* num pn))
                  (setf denom (* denom pd))))
           (prt () (format t "(~A/~A)~%" num denom)))

        ; initialization
        (if (realp n) (setf num n))
        (if (realp d) (setf denom d))

        ; dispatcher
        (lambda (cmd &optional (arg1 0) (arg2 0))
           (cond
               ((equalp cmd 'scale) (scale arg1))
               ((equalp cmd 'prod) (prod arg1 arg2))
               ((equalp cmd 'print) (prt))
               (t (format t "Invalid command ~A~%" cmd)))))))

(i) For each of the four statements below, identify where/how the stored local variables num and denom are changed.

                               Sample solution
   (defvar f1 (q3 15 11))      stores 15 in num, 11 in denom,
                               done by the setfs in the initialization section


   (funcall f1 'scale 7)      runs the scale local function,
                              changing num to 7*num, i.e. 105


   (funcall f1 'prod 2 3)     runs the prod local function,
                              multiplies num by 2 and denom by 3, so 210 and 33


   (funcall f1 'print)        displays 210/33 but doesn't change anything

(ii) Add code for a 'lookup command, that simply returns the current num/denom value. (Feel free to write the code below and draw arrows to where it belongs.)

Sample solution

  ; to be added in the dispatcher's cond:
  ((equalp cmd 'lookup) (/ num denom))

Question 2 List implementations [4 marks]
Study the function below then answer questions 1 and 2 based on that function.
(defun q2 (v L) (setf (caddr L) v))

Explain what values x and L would have after the following call to q2 and why.
(defvar x 17) (defvar L '(1 2 3 4)) (q2 x L) Sample solution First observe that the effect of (q2 v L) is to set the third element of list L to value v Given that, the impact of this segment is to change the 3 to 17 within L, x is still 17 L is now (1 2 17 4)

Explain what the contents of L would be after the following call to q2 and why.
(defvar L '(1 2 3 4)) (q2 (car L) L) Sample solution This time, the value we're passing to v is the first value in L, i.e. 1, so the effect is to change L to (1 2 1 4) (x is not involved so is unchanged)

Explain what the contents of L would be after the following call to q2 and why.
(defvar L '(1 2 3 4)) (q2 (cdr L) L) Sample solution This one is a bit more complex, as what we're passing as v is the tail of L, effectively a reference/pointer to the second cell of L Thus the third data value in L becomes a reference to the second cell in L, L is now (1 2 [a pointer to the second element] 4)

Question 3 Tail recursion [4 marks]
The C function below uses a loop to calculate and eventually return a final result.
float q3(float x, float y) { float tmp = 0; while (x > y) { tmp = tmp + (x - y); x = x/3; y = y/2; } return tmp; }

Following the logic used by the C function, provide a tail-recursive lisp function to calculate and return the result, then briefly explain how your function works and why it is tail recursive.
Sample solution (defun q3 (x y &optional (tmp 0)) (cond ((< = x y) tmp) (t (q3 (/ x 3) (/ y 2) (+ tmp (- x y)))))) To do a generalized conversion from the iterative to the tail recursive: (1) for each local variable in the original we add a new optional parameter to the tail recursive version, initialized to the same value as in the original, thus we get the optional tmp=0 (2) for the tail recursive base case, i.e. when not to recurse, we use the opposite of the continuation condition in the original loop and return what the original returns after exiting the loop, thus if x is less than or equal to y we want to return tmp (3) in the general case for the tail recursion we want to make a recursive call where the values passed to each parameter mimic the changes made to the corresponding variable in the original loop, i.e. in the original x changes to x/3, so in the recursion we pass (/ x 3), in the original y changes to y/2, so in the recursion we pass (/ y 2), in the original tmp changes to tmp + (x - y), so in the recursion we pass (+ tmp (- x y))