Program Design Guidelines

When we program, no matter whether the program be small or large, it's important to follow these design guidelines. This helps ensure that our program (1) works and works correctly, (2) is designed and written well, or, elegantly, and (3) is interpretable by other humans. The steps are as follows:
  1. Analyze and define your data.
  2. Form a contract and give a description and/or purpose statement.
  3. Give example input and output, including side-effects, that is, write some test cases.
  4. Outline your program -- create "templates."
  5. Actually write the program.
  6. Test.
Again, this applies to programs of any size, so that means it applies to even a single function. Remember in the first few classes when we talked about how programs are actually big problems broken down into smaller problems? (A program will call subprograms that will call other subprograms, etc.) We will use a single function that adds a list of numbers to give an example of these guidelines in practice. (Note: Sad to say, many professional programmers don't even follow these guidelines, as crucial as they are to the programming process! You can be different. Be a REAL programmer.)
Our Assignment: Write a function that sums a list of numbers.

  1. Analyze and define your data.

    First, we must analyze and define the data we'll be working with. Fortunate for us, in this case, not much analysis is needed, but we still need to define the data. Simple types, such as number and boolean need not be defined, but more complex, user-defined data such as structs and sometimes lists should be defined. It's a good idea to include this in your source files, so just comment it out and put it at the top of your file:
    A list-of-numbers is either
    • empty,
      • or
    • (cons number list-of-numbers)
    (Note that you type the part in this font verbatim, while the part written in this font is to be replaced with specific instances.)
    Let's go step-by-step, in working with our defined data, list-of-numbers.

  2. Form a contract and give a description and/or purpose statement.

    It's important to precisely define the type of input that your program (function) takes in and the type of output that it produces. We must also give a description of what the function actually does. We'll accomplish both of these things by writing a small comment before our function. We can also go ahead and write the first part of the function definition statement. The ... just means that we'll fill this part in later, you can leave it blank for now. 
    ;; my-sum: list-of-numbers --> number
;; Returns the sum of the numbers in the input list "nums".
(define (my-sum nums)
     ...))
  3. Give example input and output, including side-effects, that is, write some test cases.

    Now, we'd better write down some examples of list-of-numbers to use as sample inputs. Remember to think intellegently about your test cases to cover all possibilities in the data flow. 
    (define lon1 (cons 1 (cons 2 empty)))
(define lon2 (cons 7 empty))
(define lon3 empty)
    After we've done that, let's write the actual tests, to ensure that we will receive proper output. Think about what the test cases will evaluate to, then compare those values to the values that your function will return by using the predicate function "equal?" that tests for equality in all forms. If all these tests return true, then we know they worked, if we get a false, we go back and see what went wrong. 
    (equal? (my-sum lon1) 3)
(equal? (my-sym lon2) 7)
(equal? (my-sym lon3) #| ??? Discuss what should go here . . . |# )
  4. Outline your program -- create "templates."

    Since out program is only a one function program, there's not much to do here, but, normally this can involve writing "shells" or "templates" for multiple subprograms as well as our main program. Let's go ahead and write a basic template, based on our data. Our definition said there were two sorts of list: empty, and those made by cons. So our function should distinguish between these two cases (and no more): We'll use the built-in function empty?, which takes a list and returns true/false, depending on whether it's empty or not. 
    (define (my-sum nums)
     (if (empty? nums)
         ...
         ...))
    Now we just need to fill in the ...s :-).

  5. Actually write the program.

    Goodness, how will we make a function which handles any list-of-numbers? We will follow the structure of our data, and think recursively.

    If we have an empty list, what should my-sum return? It should return 0, right? So let's put 0 in the appropriate place. 
    (define (my-sum nums)
     (if (empty? nums)
         0
         ...))
    If nums isn't empty, that from our definition nums must be of the form (cons num lon), where lon is a list-of-numbers. Another baby-step: Before doing anything fancy, let's just extract those sub-parts of nums. How do you extract sub-parts of something built via cons? Yep -- first, rest! 
    (define (my-sum nums)
     (if (empty? nums)
         0
         ...(first nums)...(rest nums)...))
    We've simplified our program to just wondering, how do we combind the first number and the rest of the list, to get the sum of the original list?

    Okay, here's the mind-bending step: We know that (rest nums) is a list-of-numbers. What function can we call on a list-of-numbers? my-sum itself!?! 
    (define (my-sum nums)
     (if (empty? nums)
         0
         ...(first nums)...(my-sum (rest nums))...))
    This is weird.

    What sort of value is (first nums) -- a symbol, a number, a boolean, a list? Likewise, What sort of value is (my-sum (rest nums)) -- a symbol, a number, a boolean, a list? Ask a labbie if unsure. (Hint -- it's not a list. (rest nums) is a list, but not (my-sum (rest nums)). In fact, what sort of value does my-sum always return?)

    But for a moment, hold your doubt in abeyance, and suppose that (my-sum (rest nums)) will indeed correctly return the sum of the (rest nums). Then our question becomes:
    If we're handed the numbers (first nums) and the sum of (rest nums), how do we put them together to get the sum of the whole list? 
    (define (my-sum nums)
     (if (empty? nums)
         0
         (+ (first nums) (my-sum (rest nums)))))
    That's it!

  6. Test.

    7. Does this really work? Let's try it out. This is what we have written in our DrScheme definitions window at this point. 
    #|

Data Definitions:

a list-of-numbers is either
  -- empty, or
  -- (cons number list-of-numbers)

|#


;; my-sum: list-of-numbers --> number
;; Returns the sum of the numbers in the input list "nums".
(define (my-sum nums)
     (if (empty? nums)
         0
         (+ (first nums) (my-sum (rest nums)))))


;;testing my-sum

(define lon1 (cons 1 (cons 2 empty)))
(define lon2 (cons 7 empty))
(define lon3 empty)

(equal? (my-sum lon1) 3)
(equal? (my-sym lon2) 7)
(equal? (my-sym lon3) 0) ;; let's say we agreed that the 
                         ;; sum of an empty list was zero
    If all the results are true, then we know that our function works, otherwise, we need to pinpoint the failed test case and do something about it.

    Finally, to internalize what's going on, you can use the stepper. Keep yourself thinking, but telling your partner what's going to happen on each click of the stepper.