CSC151 2010S, Class 30: Preconditions, Revisited

Overview:
* Questions on the exam.
* Stuff from yesterday.
* Verifying preconditions.
  * The error procedure.
  * Husk and Kernel programming.
* Lab

Admin:
* Reading for tomorrow: Local Procedure Bindings.
* It's still Not National Pipe Cleaner Day Day.
* EC for Thursday's CS Extra.
* EC for Friday's CS Table.

Questions on the Exam
* When is the exam due?
  * Friday at 5pm
* Do we have to do the steps of problem 4 in the same order you suggested?
  * No

Stuff from Yesterday
* Thinking about largest.  
  * Sample solution.
    (define largest
      (lambda (lst)
        (if (null? (cdr lst))
            (car lst)
            (max (car lst) (largest (cdr lst))))))
  * What happens if you give it the null list?
    * It crashes
    * We make it a precondition that the list must have at least one element
    ;;; Procedure:
    ;;;   largest
    ;;; Parameters:
    ;;;   lst, a list of real numbers
    ;;; Purpose:
    ;;;   Find the largest element of the list.
    ;;; Produces:
    ;;;   l, a number
    ;;; Preconditions:
    ;;;   lst must have at least one element
    ;;; Postconditions:
    ;;;   For any value, x, in lst
    ;;;    (>= l x)
    ;;;   l is an element of lst
  * Can we give a nicer error message than
    "Can't find the cdr of null?"
  * Yes, if we're willing to check the precondition
  * What if the parameter isn't a list
    * We've failed to meet the preconditions
    * But, hey, we can check those, too

(define largest
  (lambda (lst)
    (if (not (list? lst))
        (error "Dillon says 'That's not a list!'")
        (if (null? lst)
            (error "Can't you read?  largest does not accept empty lists.")
            (if (null? (cdr lst))
                (car lst)
                (max (car lst) (largest (cdr lst))))))))
  * Problem: Doesn't make sure that everything is a real number
    * "This is left as an exercise for the reader."
  * Problem: We spend a lot of effort checking useless stuff (if we start with a list of real numbers, and take its cdr, we end up with a list of real numbers, so we don't need to check again).
  * Strategy: Write two procedures
    * The first checks the preconditions and calls the second
   * The second does the real work (e.g., the recursion)
   * Husk and Kernel









  * Potentially clearer version of the same code
    (define largest
      (lambda (lst)
        (if (null? (cdr lst))
            (car lst)
            (let ((largest-in-cdr (largest (cdr lst))))
              (max (car lst) largest-in-cdr)))))
  * Same problem , using helper recursion
    (define largest
      (lambda (lst)
        (largest-helper (car lst) (cdr lst))))
    (define largest-helper
      (lambda (largest-so-far remaining)
        (if (null? remaining)
            largest-so-far
            (largest-helper (max largest-so-far (car remaining))
                            (cdr remaining)))))
  * Alternate version of original strategy
    (define largest
      (lambda (lst)
        (cond
          ((null? (cdr lst)) 
           (car lst))
          ((> (car lst) (largest (cdr lst)))
           (car lst))
          (else
           (largest (cdr lst))))))

Checking Preconditions