Lecture Notes: CLII

1. Review HW

A. First+Last: Do easiest base case first and come back

B. Rmv - Will extend next week

C. Tree Recursion - Difference is algorithm, not iteration vs. recursion O(1.7N)

2. &optional/&rest/&key

A. SUM - illustrates &optional, &rest

B. Small &key examples. See FIND below for example of use.

3. Functions as first-class objects [for now passing functions. later creating on fly]

A. Recall apply/funcall

B. find/find-if/remove/remove-if/remove-if-not
Running example: ((Name Course-Num Grade) ...)

i. Review: All names (using mapcar). Hint: abstract it using "Name" accessor.

ii. Find 80 :key #'Grade {default #'Identity}

iii. Find C - below 80 -- :test #'>

iv. Find 0 (compare (find-if #'zerop ...))

v. Find all non-zeros (remove-if)

vi. Find all zeros (remove-if-not)

vii. Remember :test #'equal for strings/lists

C. Generality (Code Reuse)
i. Vector-Length: (sqrt (apply #'+ (mapcar #'Square List)))

ii. Vector-Dot-Product - (apply #'+ (mapcar #'* V1 V2))

iii. Vector-Angle

4. Recursion Revisited

A. Rev Two Ways

B. Without append or butlast

C. Square-Sum -

           (defun Square-Sum (Start End)
             (if
               (> Start End)
               0.0d0
               (+ (Square Start)
                  (Square-Sum (1+ Start) End))))

D. Pi-Sum -

           (defun Pi-Sum (Start End)
             (if
               (> Start End)
               0.0d0
               (+ (/ 8 (* Start (+ Start 2)))
                  (Pi-Sum (+ Start 4) End))))

5. Iteration "vs." Recursion - Extensibility Example

A. Fibonacci illustrated dangers of recursion. This illustrates benefits.

B. Compare the following for exponentiation:

6. Lambda Forms

A. ((lambda (X) (* X X)) 3)

B. (defun Add-N (List N)
(mapcar #'(lambda (X) (+ X N)) List))

7. Closures

A. "Downward Funarg Problem"

           (defun Add-N (List-of-Nums N)
             (mapcar #'(lambda (X) (+ X N))
                     List-of-Nums)

B. "Upward Funarg Problem"

           (defun Make-Counter (&key (Start 0) (Step 1))
             (setq Start (- Start Step))
             #'(lambda () (setq Start (+ Start Step))) )
           

           (setf (symbol-function 'Foo) (Make-Counter))
           (Foo)
           

C. Another example

           (defun Make-Fancy-Counter (&optional (Initial-Value 0))
             (list
               #'(lambda () Initial-Value)
               #'(lambda (New-Value) (setq Initial-Value New-Value)))))
           
           (defun Get-Value (Fancy-Counter)
             (funcall (first Fancy-Counter)))
           
           (defun Set-Value (Fancy-Counter New-Val)
             (funcall (second Fancy-Counter) New-Val))

Table of contents

1. - Review HW

2. - &optional/&rest/&key

3. - Functions as first-class objects [for now passing functions. later creating on fly]

4. - Recursion Revisited

5. - Iteration "vs." Recursion - Extensibility Example

6. - Lambda Forms

7. - Closures