Announcements from last time:

Lecture 2 : Getting Conditioned

Consider our program from last time.

(define (owe s)
  (* 12 (/ s 8)))
We use the function by calling it with an argument: (owe 5). We call 5 the argument, and s the parameter.

Let's write another program. Suppose you share in pizza both Saturday and Sunday nights. Write a program owes-weekend that calcuates what you spent on pizza all weekend.

A note before writing the program. We've said that programs are how we communicate calculations to a computer. But humans, as well as computers, need to read programs. For example, you and a colleague may write programs for the same project and need to look at each other's programs. Furthermore, you yourself may look back at a program a week later and need to remember what calculation you wrote that program to do. In these cases, a summary of what the program does is usually sufficient. We therefore add documentation to programs.

This course requires two forms of documentation on all programs: a contract and a purpose. The contract summarizes what kinds of information the program consumes and produces. The purpose is a one sentence description (in english) of what the program does. For our owes-weekend program, we have the following contract and purpose:

; owes-weekend : num num -> num                            [contract] 
; Calculate amount owed for pizza over the weekend.        [purpose]
The ; at the front of each line indicate that a line of text is a comment. Scheme will ignore any text that follows ; on a line.

We might write either

(define (owes-weekend p-sat p-sun)
  (+ (owe p-sat) 
     (owe p-sun)))
or
(define (owes-weekend p-sa p-su)
  (owe (+ p-sat p-sun))
Is one of these better than the other? No.

We could also write
(define (owes-weekend p-sat p-sun
  (+ (* (/ 12 8) p-sat) 
     (* (/ 12 8) p-sun)))
How does this compare to the others? It's worse in two ways. First, if the price of the pizza changes, we have to alter the code in two places instead of one. Second, it's harder to read because it involves a nested subexpression. This repeats our first principle:

Once we've written a program, we need to test it to convince ourselves that it does what we intended it to do. We test a program by running it on some sample inputs and seeing whether the program produces the outputs that we expect.

      Test case          Expected Output       Actual Output
  ----------------------------------------------------------------
   (owes-weekend  2 3)          15/2                 15/2
   (owes-weekend  6 4)           15                   15
   (owes-weekend 10 0)           15                   15
Where do the contents of each column come from? We choose the test cases (more later in the course on how to choose them). We determine the expected outputs from the problem statement (not the program!). We get the actual outputs from DrScheme by running the program.

Note that we do NOT need the program to determine the test cases or the expected outputs. We can determine those from the header and the problem statement. You should always develop test cases and their expected outputs before you write the program. This has two benefits: first, figuring out the expected outputs helps you understand the problem: if you can't determine the expected outputs, you don't understand the problem and you can't write the program. Second, determining the expected outputs before you write the program saves you from the temptation of using the program to calculate the expected outputs (which would defeat the purpose); experience shows that this temptation can be hard to avoid in practice.

We've now developed a sequence of steps (a recipe) for developing programs:

  1. Write a contract, header, and purpose
  2. Develop examples
  3. Write the program body
  4. Test the program

Let's try this recipe out. A new problem: pizza from sam's club: owes-bulk. You get 20% off if you order ten or more pieces, and 10% of you order five or more (but less than ten).

  1. Write a contract, header, and purpose.
    ;; owes-bulk : num -> num
    ;; Purpose : calculate how much is owed,
    ;; if allowing a discount for bulk orders:
    ;; 20% off if you order ten or more pieces,
    ;; and 10% of you order five or more (but less than ten).
    ;;
    (define (owes-bulk s) 
       ...)
    
  2. Develop Examples
    What test cases should I use? Look at the problem statement. We can draw a number line and indicate where the divisions are between the cases. (A square bracket means that the boundary number is included in the interval; a parenthesis means that the boundary number is not included in the interval.)
    
    	----------)|[------------)|[--------
                       5             10 
    
    We can use this diagram to choose test cases. We need one test case within each interval, plus one for each boundary number. Let's choose the following test cases, and write down their expected values:
    (owes-bulk  1) =  1.50
    (owes-bulk  5) =  6.75
    (owes-bulk  8) = 10.80
    (owes-bulk 10) = 12.00
    (owes-bulk 16) = 21.60
    
    (Notice that in coming up with these tests, we are forced to think about how to approach the problem. Our solution will later reflect this approach.)
  3. Write the program body
    For this problem, we must determine whether some condition holds of the input. What conditions to we need? Whether s < 5, whether 5 <= s < 10, and whether 10 <= s.

    If we think of < being a function, then we can guess at how to express s < 5 in Scheme. We write (<= s 2). What kind of value does this return? Either true or false. These values, true and false, are called boolean values (named after Georges Boole, who in the late 1800s set forth the algebraic rules for computing with them).

    How do we express each of the two sub-requirements 5 < s and s <= 10 in Scheme? (< 2 s), (<= s 5). We want to form one condition from these Scheme expressions. Therefore, we need an operation that combines boolean values. We can use the operation called and. Thus, we express our conditions in Scheme as shown in the table below.
    Conditions to check for
    Arithmetic Scheme
    s < 5 (< s 5)
    5 <= s and s < 10 (and (<= 5 s) (< s 10))
    10 <= s (<= 10 s)
    How do we write programs with conditions in Scheme? We use an expression called cond, which has the following format ("syntax"):

    (cond [question-a answer-a]       ; You can call it "condition-a" instead
          [question-b answer-b]       ;    of "question-a", if you like.
          ...
          [question-z answer-z])
    

    Returning to owes-bulk What does the program body look like? Start by writing down the questions that distinguish the cases in the problem:

    ;; owes-bulk : num -> num
    ;; Purpose : calculate how much is owed,
    ;; if allowing a discount for bulk orders:
    ;; 20% off if you order ten or more pieces,
    ;; and 10% of you order five or more (but less than ten).
    ;;
    (define (owes-bulk s)
      (cond [(< s 5)                 ...]
            [(and (<= 5 s) (< s 10)) ...]
            [(<= 10 s)               ...]))
    
    What remains? Fill in the answers in each case:
    ;; owes-bulk : num -> num
    ;; Purpose : calculate how much is owed,
    ;; if allowing a discount for bulk orders:
    ;; 20% off if you order ten or more pieces,
    ;; and 10% of you order five or more (but less than ten).
    ;;
    (define (owes-bulk s)
      (cond [(< s 5)                 (owes s)]
            [(and (<= 5 s) (< s 10)) (* (owes s) 0.10)]     ; BUG!
            [(<= 10 s)               (* (owes s) 0.20)]))
    

  4. Test your function.
    Now, test the program on your chosen test cases. Oops, watch out for bugs! Test cases will catch.

Alternate version (only allude to in class, ian):

;; owes-bulk : num -> num
;; Purpose : calculate how much is owed,
;; if allowing a discount for bulk orders:
;; 20% off if you order ten or more pieces,
;; and 10% of you order five or more (but less than ten).
;;
(define (owes-bulk s)
  (* (owes s) (- 1 (cond [(< s 5)                 0.00]
                         [(and (<= 5 s) (< s 10)) 0.10]
                         [(<= 10 s)               0.20]))))
This works fine, though it takes a second to figure out. What is that whole cond doing? Ah, it's computing the discount-rate. What about the following:
;; owes-bulk : num -> num
;; Purpose : calculate how much is owed,
;; if allowing a discount for bulk orders:
;; 20% off if you order ten or more pieces,
;; and 10% of you order five or more (but less than ten).
;;
(define (owes-bulk s)
  (* (owes s) (- 1 (discount-rate s))))
Is this code clear? Is it correct? (Well, we still need to write discount-rate, but we're confident that once discount-rate's correct, then owes-bulk will be correct. A minor leap of faith. [This is a lead-in to the leap of faith taken for recursive functions.] ) Note how this version, with discount-rate, follows the principle of mirroring our thought pattern. (In fact, writing the code helped clarify how we really think of the problem!)

Following the design recipe is easy for discount-rate:

;; discount-rate: num -> num
;; Given a n slices of pizza, return what the discount amount
;; (ie, 20% off means a discount rate of 0.20).
;;
(define (discount-rate n)
  (cond [(< n 5)                 0.00]
        [(and (<= 5 n) (< n 10)) 0.10]
        [(<= 10 n)               0.20]))))

(discount-rate  4)  =  0.00
(discount-rate  5)  =  0.10
(discount-rate  8)  =  0.10
(discount-rate 10)  =  0.20
(discount-rate 99)  =  0.20

A couple of notes:

  1. Parentheses, in cond: note which parens bracket the question-answer-pair, which are part of the question, and which part of the answer. Note that the book uses round parentheses in both situations; I'll use square-brackets to set aside the question-answer pairs, and encourage you to do the same. (It's possible to to have the answer be a simple number, in which case there'd be no associated parens. E.g., perhaps less than 5 pieces is a flat $5, no matter what.)
  2. If I were running a store, I might conceive of this problem differently: I might think of have a function wholesale-price (which is low), and to determine prices I add an overhead-charge (with large orders adding less overhead). If that's how I conceive of the problem, that'd be the better way to approach it, by the Principle#2. Why is it better? Experience shows that in the long run, such a structure will be easier to maintain: if, as a merchant, wholesale-price and overhead-charge are the ways you've come to think about your business, then those concepts are more likely to be used in lots of functions dealing with your business. Modeling is always about finding the principles underlying your situation, and representing those underlying principles.

if time permits...

Let's move beyond numbers. Often, we want to compute over data other than numbers. People who study language processing, for example, need a way to represent words. In Scheme, we represent words using symbols. A symbol resembles a word, but has a quote mark on the front and can contain characters other than letters (but no spaces):

	'kathi 'Rice 'comp210 'class-of-2003
What operations can we perform on symbols? Does (+ 'kathi 3) make sense? No, because 'kathi isn't a number. The only thing we can do with symbols is compare them for equality. We do this using an operator called symbol=?:
	(symbol=? 'kathi 'kathi) = true
	(symbol=? 'kathi 'john)  = false
	(symbol=? 'kathi 'Kathi) = false

Write a program babel that takes the name of a language and produces the word for hello in that language if the language is spanish, french, or pig-latin. The program produces 'hello for any other language.

;; babel : symbol -> symbol
;; translate hello into the given language
(define (babel lang)
  (cond [(symbol=? lang 'spanish)   'hola]
        [(symbol=? lang 'french)    'bonjour]
        [(symbol=? lang 'pig-latin) 'ellohay]
        [else 'hello]))

;; test-cases
; (babel 'spanish) = 'hola
; (babel 'french) = 'bonjour
; (babel 'pig-latin) = 'ellohay
; (babel 'esperanto) = 'hello