CSC151 2007S, Class 25: Documenting Programs and Procedures Admin: * EC: Talk on the Gimp by your beloved TA, 4:30, 3821. * Reading for tomorrow: Verifying Preconditions. * Assignment 11 remains due at 4 p.m. tomorrow. Overview: * Recursion with Accumulators and Helpers * The general strategy * Watching it go * Documentation * The need for documentation. * The Six P's - a strategy for documenting procedures. * Practice. /More about recursion/ * One of the big complaints about recursion: There's a lot of delayed work built up * Irritating * Confusing * Potentially slower * Can we still use recursion, but not build up "work to do later"? * Yes! * Key idea: Use a helper in which we pass along an intermediate result that gets updated at each step. * When we reach the base case, we use a form of the intermediate result Two examples: * preserve-odds and count-odds (define count-odds (lambda (lst) (count-odds-helper 0 lst))) (define count-odds-helper (lambda (count remaining) (if (null? remaining) count (count-odds-helper (if (odd? (car remaining)) (+ 1 count) count) (cdr remaining))))) (define preserve-odds (lambda (lst) (preserve-odds-helper null lst))) (define preserve-odds-helper (lambda (um remaining) (write (list 'preserve-odds-helper um remaining)) (newline) (if (null? remaining) ; Because we have been prepending values as we pass from ; left to right, the accumulated list is backwards. We ; fix that issue with reverse. (reverse um) (preserve-odds-helper (if (odd? (car remaining)) (cons (car remaining) um) um) (cdr remaining))))) ; Keep the car of the list when its odd /DOCUMENTATION/ * The problem: Humans, as well as computers, read computer programs * Not all code is obvious. Two weeks from now, none of us will remember why there's a reverse up there, or why we called the parameter "um" * When you have to fix the code, understanding why funny parts are there is important * Not all code need to be obvious. When someone else *uses* rather than modifies our code, she cares just about what the code does. * Good programmers document for their clients * Students in Sam's classes document for their clients, no matter what their moral state, because Sam requires it * What do we need to communicate? * What the procedure is supposed to do (informally) * How you call the procedure - the order and types of the parameters * But coding is like law: Precision is important * Formally specify restrictions on parameters * Formally specify results * How Sam likes you to communicate * Six P's * Procedure - Name it * Parameters - List and name them * Purpose - Informal description of what the procedure does * Produces - THe name and type of the result * Preconditions - An attempt to formalize requirements * Postconditions - An attempt to formalize what the procedure does (usually in the form of the result) count-odds ;;; Procedure: ;;; count-odds ;;; Parameter: ;;; lst, a list ;;; Purpose: ;;; Count the number of odd integers in lst ;;; Produces: ;;; count, an integer ;;; Preconditions: ;;; lst must be a lst. ;;; Every element of lst must be an integer ;;; (Every element of lst must be exact) ;;; Postconditions: ;;; count is the number of odd integers in lst ;;;