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