CSCI 330 Quiz 2 (2025) Prep Notes

Preparation for CSCI 330 Quiz 2 (2025)

As per the exams page, the quiz will be closed book, closed notes, no electronics, and held in the lab during your scheduled lab section. You will have 50 minutes to complete the quiz.

You are permitted one double-sided 8.5x11" page of notes ('cheat sheet').

This second quiz is a mix of theory and applied/lisp coding, focused on the the lab and lecture material up to and including macros in lisp (lecture of Feb. 12th).

There will be three questions with an emphasis on the following:

Topic: higher order functions (conceptually and in lisp)

Sample question 1:
In the context of higher order functions, explain the workings of bubblsort and SLsorter in the common lisp code segment below.

; standard bubblesort, making N passes through a list of N elements,
;    swapping out-of-sequence adjacent elements on each pass
; expects a list, L,
;         a function to check an element is of the correct type, e.g. 'integerp
;     and a function to check if two elements are in the wrong order in the list, e.g. '<
(defun bubblesort (typeCheckerF outOfOrderF L)
   (if (and (listp L) (> (length L) 1))
       (dotimes (passNum (length L) passNum)
          (dotimes (epos (- (length L) 1) epos)
              (let ((first (nth epos L))
                    (second (nth (+ 1 epos) L)))
                   (if (and (funcall typeCheckerF first)
                            (funcall typeCheckerF second)
                            (funcall outOfOrderF first second))
                       (block swapFirstAndSecond
                           (setf (nth epos L) second)
                           (setf (nth (+ 1 epos) L) first))))))))



; bubblesorts given list whose elements are strings/lists, sorts the list by element lengths
(defun SLsorter (SL)
    (bubblesort (lambda (x) (or (listp x) (stringp x)))
                (lambda (a b) (> (length a) (length b)))
                SL))

; sample call
(defvar S '("hi" "there" (10 20 30 40) "bob" nil "bye" "?"))
(SLsorter S)

Sample question 2:
The 'myReduce' function below shows a possible implementation of a reduce function. First, briefly explain how and why this reduce works,
then write a revised version where the passed function expects three parameters and, as the new reduce works through all its arguments it replaces the first three arguments with the result of the current call. Thus (newReduce a b c d e f g) would effectively calculate
(newReduce (newReduce (newReduce a b c) d e) f g)

(defun myReduce (f x &rest R)
   (cond
       ((null R) x)
       (t (apply 'myRed (cons f
                              (cons (funcall f x (car R))
                                    (cdr R)))))))

(format t "~A~%" (myReduce '/ 120))            ; gives 120
(format t "~A~%" (myReduce '/ 120 3))          ; gives 40
(format t "~A~%" (myReduce '/ 120 3 0.5))      ; gives 80
(format t "~A~%" (myReduce '/ 120 3 0.5 -5))   ; gives -16

Topic: let-over-lambda in lisp

Sample question 1:
Briefly explain how the stackAccess function below allows the caller to store and manipulate the contents of a stack, and provide a sequence of lisp commands to:

call stackAccess on an initial list of '(10 5 "foo") and store the returned value
call top on the resulting dispatcher
push the value 7 through the dispatcher

(defun stackAccess (L)
   (let ((elements nil))
        (if (listp L) (setf elements (copy-list L)))
        (lambda (cmd &optional (e nil))
            (cond
               ((equalp cmd 'top) (if (not (null elements)) (car elements) nil))
               ((equalp cmd 'pop) (if (not (null elements)) (setf elements (cdr elements))))
               ((equalp cmd 'size) (length elements))
               ((equalp cmd 'push) (setf elements (cons e elements)))
               (t (format t "Invalid command ~A~%" cmd))))))

Sample question 2:
Briefly explain how the stackAccess function above allows the caller to store and manipulate the contents of a stack, and rewrite the function so that (using labels) it has local functions for pushing, popping, topping, and getting the size, and the dispatcher is modified to use the appropriate labels methods to carry out the desired functionality.

Topic: macros (conceptually and in lisp)
Sample question 1:
The code segment below shows a version of reduce written as a macro rather than as a function. Briefly explain how this macro works, showing the (sometimes recursive) rewrite steps it would go through for the following calls:
1. (myReduce / 120)
2. (myReduce / 120 3)
3. (myReduce / 120 3 0.5)
4. (myReduce / 120 3 0.5 -5)
(defmacro myReduce (f x &rest R) (cond ((null R) x) ((null (cdr R)) (list f x (car R))) (t `(myReduce ,f (,f ,x ,(car R)) ,@(cdr R)))))
Sample question 2:
In common lisp, 'or' can take any number of arguments, e.g. (or a b c d e), and returns t iff at least one of them is true.
Suppose we wanted a version, OR1, that returns t iff exactly one of them is true.
Write OR1 as a macro.
```
 hint:
      if given just x then it's true iff x is true
      if given x and 'the rest' then it's true if
            either x is true and all the rest are false
            or x is false and exactly one of the rest is true 
```