Lab 9: Program Aesthetics; Loops

1. Program Aesthetics

The goal for this section is to define some guidelines on how code in the Student Languages should be formatted.

In one sense, none of this stuff is foundational to computer science; a typical computer will not discriminate between a horribly formatted program and a nicely formatted one.

But on the other hand, computer science is about people communicating with each other; you should take pride in how you present your code, because it is going to affect how people read it. Get in the good graces of your grader!

1.1 The Good, the Bad, and the Ugly

Consider the following definitions of create-address.

;; create-address: DBR -> string
;; create a three line address string from a db
(define(create-address DBR)
  (string-append (db-prefix DBR) " " (db-first DBR) " " (make-string 1 
(db-middle DBR)) " " (db-last DBR) "\n"
                 (db-street DBR) "\n"
                 (db-city DBR) " " (db-state DBR) " " (db-zip DBR)))

;; create-address: DBR -> string
;; create a three line address string from a db
(define (create-address DBR)
  (string-append (db-prefix DBR)                 " " 
                 (db-first DBR)                  " " 
                 (make-string 1 (db-middle DBR)) " " 
                 (db-last DBR)                   "\n"
                 (db-street DBR)                 "\n"
                 (db-city DBR)                   " " 
                 (db-state DBR)                  " " 
                 (db-zip DBR)))

• In the first definition, what is the last argument to the string-append function invocation? Is it (db-middle DBR), as in

    (string-append 
       (db-prefix DBR) " " (db-first DBR) " " (make-string 1
       (db-middle DBR))
  

• Which definition looks nicer? Why?

Compare the following definitions for convert-DBRs.

;; A LoDBR is One of:
;; - empty
;; - (cons DBR LoDBR)

;; A LoADD is one of:
;; - empty
;; - (cons String LoADD)

;; convert-DBRs: LoDBR -> LoADD
;; converts LoDBR into LoADD
(define (convert-DBRs a-LoDBR)
  (cons

        (string-append 
   (db-prefix (first a-LoDBR)) " "    (db-first (first a-LoDBR)) " " 
   (db-middle (first a-LoDBR)) " "    (db-last (first a-LoDBR)) "\n"
   (number->string(db-no (first a-LoDBR))) " " (db-street (first a-LoDBR)) "\n"
   (db-city (first a-LoDBR)) ", " (db-state (first a-LoDBR)) " "
   (number->string(db-zip (first a-LoDBR))) " " 
   (number->string(db-priority (first a-LoDBR))))

        (cond
     [(empty? (rest a-LoDBR)) empty]
     [else
      (convert-DBRs (rest a-LoDBR))])))

;; convert-DBRs: LoDBR -> LoADD
;; converts LoDBR into LoADD
(define (convert-DBRs a-LoDBR)
  (local ((define the-string
            (string-append (db-prefix (first a-LoDBR)) " " 
                           (db-first (first a-LoDBR)) " " 
                           (db-middle (first a-LoDBR)) " "    
                           (db-last (first a-LoDBR)) "\n"
                           (number->string (db-no (first a-LoDBR))) " " 
                           (db-street (first a-LoDBR)) "\n"
                           (db-city (first a-LoDBR)) ", " 
                           (db-state (first a-LoDBR)) " "
                           (number->string (db-zip (first a-LoDBR))) " " 
                           (number->string (db-priority (first a-LoDBR))))))
    (cond
     [(empty? (rest a-LoDBR)) 
      (cons the-string empty)]
     [else
      (cons the-string (convert-DBRs (rest a-LoDBR)))]))))

• Which definition was developed using the design recipe?
• How hard is it to tell whether each definition follows the design recipe? Why?
• Which one do you think is a correct definition? Which one would you prefer to modify?

1.2 Beautification 101: The Enter Key

Look at this definition for truncate.

;; truncate : [Listof String] -> [Listof String]
;; truncates all lines in LOL so that each is at most 80 characters wide.
(define (truncate LOL)
  (cond
    [(empty? LOL) empty]
    [(> (string-length (first LOL)) 80) (cons (substring (first LOL) 0 81) (truncate (rest LOL)))]
    [else (cons (first LOL) (truncate (rest LOL)))]
  )
)

         11111111112222222222333333333344444444445555555555666666666677777777778
12345678901234567890123456789012345678901234567890123456789012345678901234567890

The formatting here is ironic, given the function's purpose statement.

Of course, truncate wasn't designed in a vacuum. It has tests as well:

(equal? (truncate (cons "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789"
                        (cons "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" empty)))
(cons "01234567890123456789012345678901234567890123456789012345678901234567890123456789"
      (cons "01234567890123456789012345678901234567890123456789012345678901234567890123456789" empty)))

(equal? (truncate (cons "01234567890123456789012345678901234567890123456789012345678901234567890123456789"
                        (cons "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" empty)))
(cons "01234567890123456789012345678901234567890123456789012345678901234567890123456789"
      (cons "01234567890123456789012345678901234567890123456789012345678901234567890123456789" empty)))

• Can you tell if these tests are valid examples, given truncate's purpose statement? (Can you even tell where the test expression ends and the expected result begins?)
• Can you come up with ways to make more readable tests that would still check the same functionality? (Hint: think string-append, make-string and/or build-list.)

Here is another example of poor choice of line-breaks and indentation.

;;evaluate: Expression -> number or false
;;evaluates the given Expression
;;produces number if Expression is numeric, false elsewise.
(define (evaluate exp)
  (cond [(numeric? exp) (cond [(add? exp) 
                               (cond [(or (add? (add-left exp))           
                                          (add? (add-right exp))
                                          (mul? (add-left exp))
                                          (mul? (add-right exp)))
                                      (+ (evaluate (add-left exp))
                                         (evaluate (add-right exp)))]
                                     [else (+ (add-right exp)
                                              (add-left exp))])]
                              [(mul? exp) 
                               (cond [(or (add? (mul-left exp))           
                                          (add? (mul-right exp))
                                          (mul? (mul-left exp))
                                          (mul? (mul-right exp)))
                                      (* (evaluate (mul-left exp))
                                         (evaluate (mul-right exp)))]
                                     [else (* (mul-right exp)
                                              (mul-left exp))])]
                              [else exp])]
        [else false]))

• Imagine if we had to add another cond to the far right; it would become unmanagable.
• How would you fix the above code?

Exercise 1: Practice fixing the line width and line breaks in the following file: lab9.deja3.scm.

1.3 Beautification 202: Parentheses

;; truncate : [Listof String] -> [Listof String]
;; truncates all lines in LOL so that each is at most 80 characters wide.
(define (truncate LOL)
  (cond
    [(empty? LOL) empty]
    [(> (string-length (first LOL)) 80) (cons (substring (first LOL) 0 81) (truncate (rest LOL)))]
    [else (cons (first LOL) (truncate (rest LOL)))]
  )
)

We already discussed problems with width of the lines of this function. The other thing that is wrong is more subtle: the closing parens appear on their own lines.

This is bad style for a parenthesized language like the Student Languages because we don't want to read the parentheses; it is faster for our eyes to rely on the indentation of the code to determine how it is structured.

By putting the parentheses on their own lines, you are making them stand out to the reader; but most of the time, we want to ignore the parentheses!

Exercise 2: Practice fixing the parenthesization issues in the following file: lab9.deja2.scm.

1.4 Beautification 303: Indentation

We pointed out in the discussion of truncate that it is faster for our eyes to use the indentation of the code in determining the roles of its subexpressions.

(Some programming languages do not use delimiters like { }, [ ] or ( ) to structure their expressions; they rely solely on indentation to determine how expressions are structured. Whether this is a good idea is debatable.)

Unfortunately, this technique breaks down when code isn't indented properly.

Here is an example of how poor indentation can lead one astray. (Warning: this program only "works" verbatim in the "Pretty Big" language, which is not one of the HtDP languages.)

;; recall : Symbol [Listof Symbol] -> [Listof Symbol]
;; produces a list with every toy in lst except a-toy
(define (recall a-toy lst)
   (cond
     [(empty? lst)"empty" ]
     [(symbol? a-toy) (first lst)
     (cond
     [ (recall a-toy (rest lst))]
     [else (cons (recall toy (rest lst)))])]))

• How many cond-clauses are there in the outermost cond expression above; 1, 2, 3, 4, or 5?
• How many sub-expressions are there in each cond-clause? How many sub-expressions are there supposed to be in a cond-clause?
• How would you fix this code to make it clearer what the clauses are?

;; subst: Symbol Number SymbolicExp -> SymbolicExp
;; produces an expression where all occurances of V are replaced by N
(define (subst V N exp)
  (cond
    [(symbol? exp)
     (cond
       [(symbol=? V exp) N]
       [else exp])]
    [(number? exp) exp]
    [(add? exp)
           (make-add (subst V N (add-left exp))
                             (subst V N (add-right exp)))] 
    [(mul? exp)
           (make-mul (subst V N (mul-left exp))
                            (subst V N (mul-right exp)))]))

• What is the role of (subst V N (mul-right exp)) in the above program; is it being passed to subst or to make-mul?
• How would you make this clearer?

Exercise 3: Practice fixing the indentation issues in the following file: lab9.deja5.scm.

1.5 Beautification 404: Organization

The order in which you present things is also important. It can affect how you think about the problem.

Consider the following structure and data definitions from Homework 7.

(define-struct add (left right))
;; An add is a structure 
;;        (make-add left right) 
;; where left and right are numbers, symbols, sub, mul, or div
;;Examples:
(define 1add (make-add 1 1))
(define 2add (make-add 4 'x))
(define 3add (make-add 'x 4))

(define-struct sub (left right))
;; A sub is a structure 
;;        (make-sub left right) 
;; where left and right are numbers, symbols, add, mul, or div
;;Examples:
(define 1sub (make-sub 1 1))
(define 2sub (make-sub 4 'x))
(define 3sub (make-sub 'x 4))

(define-struct mul (left right))
;; A mul is a structure 
;;        (make-mul left right) 
;; where left and right are numbers, symbols, add, sub, or div
;;Examples:
(define 1mul (make-mul 1 1))
(define 2mul (make-mul 4 'x))
(define 3mul (make-mul 'x 4))

(define-struct div (left right))
;; A div is a structure 
;;        (make-div left right) 
;; where left and right are numbers, symbols, add, sub, or mul
(define 1div (make-div 1 1))
(define 2div (make-div 4 'x))
(define 3div (make-div 'x 4))

In the above structure and data definitions, the developer followed the pattern: "Structure Def; Data Def; Examples; Repeat as Necessary" That is not always the right model to have in mind when writing programs. In particular, when you have mutual references between Data Definitions, you are almost certainly better off using the following process:

1. Gather all of the related structure definitions, and put them at the top.
2. Next write down the data definition(s); see if you can eliminate redundancy by introducing a name for common patterns.
3. Finish with example elements from the class of data you have defined.

Here is a definition similar to the above, written in a more appropriate style.

(define-struct add (left right))
(define-struct sub (left right))
(define-struct mul (left right))
(define-struct div (left right))

;; An Expression is one of:
;; - Number
;; - Symbol
;; - (make-add Expression Expression)
;; - (make-mul Expression Expression)
;; - (make-sub Expression Expression)
;; - (make-div Expression Expression)

;; Examples:
(define 1add (make-add 1 1))
(define 2sub (make-sub 4 'x))
(define 3mul (make-mul 'x 4))
(define 4div (make-div 'x 'y))

• What is wrong with this set of examples? How would you fix it?
• You might notice that these do not define exactly the same class of data; which elements are included in the second data definition for Expression, but left out of the first data definition for add, mul, sub, and div?

In general:

• We expect code to be organized with
  • Problem Number labelled at the top.
  • Structure and Data Definitions relevant to the problem next
  • Each contract and purpose statement with its function definition
  • Function tests at the end.
• We expect all names that you use to be defined.
  • DrScheme forces you to define any name that you use in your code, so if your program runs, you're probably okay on this front.
  • However, DrScheme does not check that the names in your contracts and data definitions are also defined!
  • We give you Number, String, Symbol, Character, Boolean, and [Listof X] for free. To refer to any other class of data, you need to have a definition in your code (such a definition might have come from us, or you might have developed it yourself).

Exercise 4: Practice fixing the organization issues in the following file: lab9.connect-four.scm. Note that the program as-is spills blood when run, due to an incorrect reorganization attempted by a prior manager.

1.6 Style Rules

Here are some style rules motivated by the examples above. (Thanks to Richard Cobbe for codifying the majority of them.)

These are style guidelines that we expect every submission to follow. If you don not adhere to these guidelines, the homework server may reject your submission.

1. When writing up your solution to a particular problem, first provide the problem number (in comments), then structure definitions, then data definitions (again in comments), and finally function definitions.
2. Each line of code should be no more than 80 characters wide.
3. Non-local definitions start on the first column. This includes structure, data, and function definitions.
4. Contracts and purpose statements should be aligned with their corresponding function.
5. No whitespace on the "inner side" of a parenthesis. This disallows both (  func a) and (func a  ).
6. Let DrScheme do the indentation for you! Reindent often!
7. Each cond clause gets its own line.
8. Each local definition should gets its own line. In addition, the body expression for a local also starts on a new line.
9. Each test case gets its own line.


10. In addition, there a number of places where it is often a good idea to introduce a line break, though this rule is not as strict as the ones given above. In order of preference, you should consider putting line breaks:
    1. after the function header,
    2. after the keyword cond,
    3. between the question and result of a cond-clause,
    4. between the arguments to a function application (breaking lines at the lowest level of nesting possible),
    5. and, as a last resort, before the first argument to a function.

1.7 Cure the disease, not the symptoms

Often if code looks bad, it is a symptom of deeper problems in the development process. Consider the following definition:

;; numeric? : Expression -> Boolean
;; returns a boolean determining whether or not ex is numeric
(define (numeric? ex)
  (cond
    [(number? ex) true]
    [(sub? ex) (cond
                 [(and (number? (sub-right ex)) (number? (sub-left ex))) true]
                 [(and (number? (sub-right ex)) (not (number? (sub-left ex)))) (numeric? (sub-left ex))]
                 [(and (not (number? (sub-right ex))) (number? (sub-left ex))) (numeric? (sub-right ex))]
                 [(and (not (number? (sub-right ex))) (not (number? (sub-left ex)))) (and (numeric? (sub-right ex)) (numeric? (sub-left ex)))])]
    [(add? ex) (cond
                 [(and (number? (add-right ex)) (number? (add-left ex))) true]
                 [(and (number? (add-right ex)) (not (number? (add-left ex)))) (numeric? (add-left ex))]
                 [(and (not (number? (add-right ex))) (number? (add-left ex))) (numeric? (add-right ex))]
                 [(and (not (number? (add-right ex))) (not (number? (add-left ex)))) (and (numeric? (add-right ex)) (numeric? (add-left ex)))])]
    [(div? ex) (cond
                 [(and (number? (div-right ex)) (number? (div-left ex))) true]
                 [(and (number? (div-right ex)) (not (number? (div-left ex)))) (numeric? (div-left ex))]
                 [(and (not (number? (div-right ex))) (number? (div-left ex))) (numeric? (div-right ex))]
                 [(and (not (number? (div-right ex))) (not (number? (div-left ex)))) (and (numeric? (div-right ex)) (numeric? (div-left ex)))])]
    [(mul? ex) (cond
                 [(and (number? (mul-right ex)) (number? (mul-left ex))) true]
                 [(and (number? (mul-right ex)) (not (number? (mul-left ex)))) (numeric? (mul-left ex))]
                 [(and (not (number? (mul-right ex))) (number? (mul-left ex))) (numeric? (mul-right ex))]
                 [(and (not (number? (mul-right ex))) (not (number? (mul-left ex)))) (and (numeric? (mul-right ex)) (numeric? (mul-left ex)))])]
    [else false]))

• We know from our earlier beauty courses that these lines are too long. But rather than just adding line breaks to fix the problem, lets read the code a bit more carefully.
• From reading the first five or six lines above, which question do you think this developer skipped when writing down the template for the numeric? function?
• What effect did skipping that question have on the function?

Quiz

2. Loops

When designing a function, often one can use a pre-existing "abstract list function" (or loop) to do the bulk of the work. (You can find the specification for the important loops on page 313.)

2.1 Loop questions

But one must know how to select the proper loop for the job. You need to ask yourself questions about the problem:

• What is the function going to produce? What does the function consume?
  • This narrows down which functions you need to consider; you can filter many of them out based on their contracts alone.
• Assuming that the desired function has the contract [Listof A] -> [Listof B], (for some A and B),
  • Is the length of the output list sometimes smaller than the length of the input list, and never larger? In that case, consider using filter.
  • Is A a different class of data from B? In that case, consider using map.
• Do you need to construct a list, but you don't get one as input? In that case, consider using build-list.
• Do you need to produce a boolean? In that case, consider using andmap or ormap, depending on whether you're asking if a predicate holds for every item in the list, or only if there exists some item for which it holds.

Note that you may need to combine more than one loop together to get the desired effect.

2.2 Loop contracts

Once you have selected a loop function, you need to determine how to invoke it; that is, you need to figure out what kind of function you need to pass into the loop. The key to this step is to figure out what X and Y are in the contract for the loop. You can determine this based on the classes of data the loop is consuming and producing.

2.3 Example loop selection

For example, if we know that we want a [Listof String] as output, and we have a [Listof Symbol] as input, then we can consult page 313 and determine:

1. build-list has potential, because it produces a [Listof X]. But it takes a number as input, not a list. So that's not it.
2. filter takes a list as input and produces a list as output; much better!
   On closer inspection, the contract for filter is:

   filter : (X -> Boolean) [Listof X] -> [Listof X]

   So to get a [Listof String] out, we need to let X be String.
   But then that means that filter needs a [Listof String] as input, and all we have is a [Listof Symbol]. So that's not it.
3. quicksort has the same problem as filter; it only produces [Listof String] when it is given a [Listof String]. So that's not it.
4. map takes a [Listof X] and produces a [Listof Y]. This means that we can let Y be String, and we're still free to choose some other X to suit our needs; excellent!

We need to read the purpose statement for map to tell if it really is the right fit for our needs. For example, if we wanted the output list to be double the length of the input list, then map alone isn't going to be sufficient. Let us assume that map's specification suits the needs of our problem.

Now the only thing left is to determine what we need to feed to map for it to do its job. The contract for map is:

map : (X -> Y) [Listof X] -> [Listof Y]

map : (Symbol -> String) [Listof Symbol] -> [Listof String]

2.4 Loop exercises

Exercise 5: Determine what class of data each of the following expressions belongs to (assuming the contracts given in the comments are correct).

;; A Nat is a natural number (0, 1, 2, ...)

;; f : Nat -> String
(build-list 10 f) ;; : ???

;; g : Nat -> Boolean
(map g (list 1 2 3 4)) ;; : ???

;; h : Nat -> [Listof Symbol] 
(build-list 20 h) ;; : ???

;; i : String -> Boolean
(andmap i (list "hello" "world")) ;; : ???

;; j : String -> Boolean
(filter j (list "goodbye" "cruel" "world")) ;; : ???

;; k : (Number String -> String)
(foldr k "what me worry?" (list 1 2)) ;; : ???

Exercise 6: Determine what class of data each of question-marked contracts (i.e. the bits labelled ???) must describe in order for the associated loop expression to belong to the class of data ascribed to it.

;; z : ???
(quicksort (list 1 2 3) z) ;; : [Listof Number]

;; y : ???
;; x : Number -> String
(filter y (map x (list 10 9 8 7))) ;; : [Listof String]

;; w : ???
;; v : Symbol -> Number
(map w (build-list (v 'x) add1)) ;; : [Listof Symbol]

;; t : ???
;; s : ???
(ormap t (filter s (list "it's" "me" "mom"))) ;; : Boolean

Exercise 7: (recall recall) Using an appropriate loop, design the function recall to eliminate specific toys from a list. The function consumes the name of a toy, called ty, and a list of names, called lon, and produces a list of names that contains all components of lon with the exception of ty. For example,

(recall 'robot (cons 'robot (cons 'doll (cons 'dress empty))))
;; expected value: 
(cons 'doll (cons 'dress empty))

Exercise 8: (a substitute for substitute) Using an appropriate loop, design the function substitute. The new function consumes two symbols, called new and old, and a list of symbols. It produces a new list of symbols by substituting all occurrences of old by new. For example,

(substitute 'Barbie 'doll (cons 'robot (cons 'doll (cons 'dress empty))))
;; expected value: 
(cons 'robot (cons 'Barbie (cons 'dress empty)))

Exercise 9: (summarizing our knowledge with sum-num) Using an appropriate loop, design the function sum-num which takes a [Listof Number] and produces the sum of all the numbers in the list. For example,

(equal? (sum-num (list 1 2 3 4)) 10)

Exercise 10: (sum-str with knowledge our summarizing) Using an appropriate loop, design the function sum-str which takes a [Listof String] and produces a single string that is the result of appending all of the strings together in reverse order. For example,

(equal? (sum-str (list "Harry" "Potter" "Ice Cream")) "Ice CreamPotterHarry")