CSCI 330 Quiz 1 Sample Solution: lisp I

Question 1 [6 marks]

Study the lisp function and defvars below, then for each of the two calls shown (parts a and b) briefly explain what the results will be (both side effects and returned value) and how that relates to the way lisp handles lists and parameter passing. (Reminder: setf's return value is the value it assigns.) 

(defun q1 (L)
   (cond
       ((not (listp L)) (setf L nil))
       ((null L) (setf L '()))
       ((< (length L) 2) (setf (car L) nil))
       (t (setf (cadr L) (car L)))))

(defvar L1 nil)
(defvar L2 '(5 10 15 20))
good grief, when I transferred the quiz to VIULearn on our snowy Monday I chopped out the two lines for (part a) and (part b) that showed the actual calls (q1 L1) and (q1 L2). Some of you assumed it was meant to be called on L1,L2, others answered what was literally asked: I'll accept either approach. 
(a) (q1 L1)

Sample Solution
L1 is nil, i.e. call is (q1 nil)
q1 sets its parameter L to nil,
   which it was anyway
since the L nil was just a copy of L1
   it has no effect on L1, which is also still nil


(b) (q1 L2)

Sample Solution
q1 is passed the reference to L2, the list (5 10 15 20)
   the list length is > 2 so the default case applies,
       setting the second element (cadr) equal to the first (car)
   thus the list is now (5 5 15 20)
and since q1 is working through a reference to L2
   this *is* changing the content of L2

Question 2 [6 marks]

Given the lisp function below and assuming we cannot trust the caller to pass valid parameters, add suitable type/range checking to catch errors and prevent potential run-time crashes. (You can assume the caller passes the correct number of parameters.) 
; original version
(defun q4 (L i)
   "returns the ith element of list L"
   (nth i L))

Sample solution

; ... you can probably tell from the q4 that I originally had this listed as question 4 ;)

(defun q4 (L i)
   "returns the ith element of list L"
   (cond
       ; make sure L and i have valid types before trying to work with them
       ((not (listp L)) (format t "Error: list expected, got ~A~%" L))
       ((not (integerp i)) (format t "Error: integer expected, got ~A~%" i))

       ; make sure i is in the valid range: 0..(length of L - 1)
       ((< i 0) (format t "Index, ~A, must be > 0~%" i))
       ((>= i (length L)) (format t "Error: index, ~A, must be < list length ~A~%" i (length L)))

       ; general (valid values) case
       (t (nth i L))))

Question 3 [6 marks]

The function in the provided pseudo-code is not tail recursive. Rewrite the function to be tail-recursive but still have the same output.
It must still be recursive (not using loops) and the answer can be written in pseudo-code. 
; original version

function q3(integer a, integer b)
begin
   if (a < b) then
      q3(a + 1, b - 1)
   endif
   print(a, b)
end

Sample solution

; solution would need to maintain a list or array of pairs queued up for printing,
; and the final/base case recursive call would print the accumulated list
;     from last to first
; since it's just pseudo-code I don't mind if you're pretty loose with
;     how you set up the list/array for the pairs


; my q3 will rely on a helper to do the recursion in a tail recursive fashion
function q3(integer a, integer b)
begin
    int pairs[Maxpairs][2]
    helper(a, b, pairs, 0)
end


function helper(integer a, integer b, integer pairsSoFar[][], integer numSoFar = 0)
begin
   if (a >= b) then
      printPairs(pairsSoFar, numSoFar-1)
   else
      pairsSoFar[numSoFar][0] = a
      pairsSoFar[numSoFar][1] = b
      helper(a+1, b-1, pairsSoFar, numSoFar+1)
   endif
end


; tail recursive helper function to do the printing at the end
function printPairs(integer pairsSoFar[][], integer index)
begin
   if (index >= 0) then
      print(pairsSoFar[index][0], pairsSoFar[index][1])
   endif
   if (index > 0) then
      printPairs(pairsSoFar, index-1)
   endif
end

Question 4 [6 marks]

The lisp function provided below is not functionally pure in the sense that it uses a local variable. Rewrite the function to eliminate the local variable either using helper function(s) or optional parameter(s).
Ensure the revised version still has the same functionality from the caller's perspective. 
; original version

(defun q4 ( )
   (let ((a nil) (b nil) (sum 0))
      (format t "Enter two integers~%")
      (setf a (read-line))
      (setf b (read-line))
      (if (realp a) (setf sum (+ sum a)))
      (if (realp b) (setf sum (+ sum b)))
      sum))

Sample solution
; the original code is actually kinda borked since read-line will return a string
;     (well, array of char) so realp will always fail and the sum will always be 0

; new version with helper function (here eliminating the sequencing aspects also)

(defun helper ( dummy a b sum )
    (+ 0 (if (realp a) a 0) (if (realp b) b 0)))

(defun fp4 ( )
   (helper (format t "Enter two integers~%") (read-line) (read-line) 0))