Lab: Verifying preconditions

Friday, Oct 5, 2018
Lab writeups are due at 10:30pm on the day of the next class meeting. For example, a Wednesday lab is due at 10:30pm on Friday. Each lab writeup will be announced at the end of class on a lab day.
In this laboratory, you will consider mechanisms for verifying the preconditions of procedures. You will also consider some issues in the documentation of such procedures.


Do the normal preparation for a lab. That is,

  • Start DrRacket.
  • Make sure that the csc151 package is up to date.
  • Add (require csc151) to the top of the definitions pane.


Exercise 1: Exploring preconditions

Consider a procedure, (greatest-of-list lst), that finds the largest number in a list.

(define greatest-of-list
  (lambda (lst)
    (reduce max lst)))

a. What preconditions should greatest-of-list have?

b. Discuss your list with a neighboring group.

Exercise 2: Checking the form of data

In the corresponding reading, we noted that in order to enforce the preconditions of northernmost-latitude, we needed a procedure, all-cities?, that verifies that a list contains only cities. In order to write such a procedure, we need two parts: (a) a procedure that, given a value, determines whether or not it’s a city and (b) a way to use that procedure to check all elements of a list.

Let’s start with the first. Write a procedure, city?, that takes a Scheme value as input and determines whether or not it corresponds to the standard “zip-first” format. (That is, a six-element list containing (0) zip-code, a string, (1) latitude, a real, (2) longitude, a real, (3) city, a string, (4) state, a string, and (5) county, a string.

For example,

> (city? 5)
> (city? (list)
> (city? (list 1 2 3 4 5 6))
> (city? (list "12345" 10 20 "Some" "Where" "A Place"))
> (city? (list "12345" "" 20 "Some" "Where" "A Place"))
> (city? (list "12345" 10 20 "Some" "Where" 1))
> (city? (list "00614" 18.429675 -66.674506))

Exercise 3: Checking all the elements in a list

You remember the mantra:

First solve for one/two then solve for many. That is, write something that works on a single element and then use map or reduce or sort or filter or … to apply it to all elements of the list.

Can we do that to check whether all of the elements of a list are of a particular type, such as all integers or all strings? It feels like we should be able to map a predicate onto the list to get a list of #t and #f and then reduce using and. Let’s try.

> (define nums (list 1 3.2 -5 8 23))
> (define odds (list 1 3 5 7 5 1 7 1))
> (define mixed (list "a" 23 'c 11))
> (map real? nums)
'(#t #t #t #t #t)
> (map real? odds)
'(#t #t #t #t #t #t #t #t)
> (map real? mixed)
'(#f #t #f #t)
> (map (conjoin integer? odd?) nums)
'(#t #f #t #f #t)
> (map (conjoin integer? odd?) odds)
'(#t #t #t #t #t #t #t #t)
> (map (conjoin odd? integer?) odds)
'(#t #t #t #t #t #t #t #t)
> (map (conjoin odd? integer?) odds)
'(#t #t #t #t #t #t #t #t)
> (map (conjoin odd? integer?) nums)
. . odd?: contract violation
  expected: integer
  given: 3.2
; Node: Order of parameters to `conjoin` is important.

Now, how do you convert a list of #t and #f values to a single value? That feels like a job for reduce.

> (reduce and (list #t #t #f #t #t))
> (reduce and (map real? nums))
> (reduce and (map real? mixed))

a. Do you think this strategy will work? Why or why not?

b. Check your answer experimentally.

Exercise 4: Checking all the elements in a list, continued

As you may have observed, you could not use reduce the list with and. Why not? Because and is a keyword, not a function. (You may recall that keywords look much like functions, but behave slightly differently. For example, while we evaluate all of the parameters to a procedure before applying the procedure, we evaluate the parameters to and one at a time.

a. Develop an alternative to (reduce and ...) to convert a list of Boolean values into a single Boolean value.

Hint: It may be useful to think about defining another procedure you can use with reduce.

b. Use that to write a procedure, all-real?, that takes a list as a parameter and returns #t if all of the elements in the list are real and #f if any of the elements is not real.

> (all-real? (list 1 2 3))
> (all-real? (list 1.4 2 7/2))
> (all-real? (list 3+4i 5))
> (all-real? (list 1 2 3 'four 5))

Exercise 5: Checking all the elements in a list, concluded

As you’ve discovered, you can write a procedure that checks whether all of the elements of a list are of a certain type. Here’s that approach.

(define all-real?
  (let ([my-and (lambda (a b) (and a b))])
    (lambda (lst)
       (reduce my-and (map real? lst))))

a. Verify that this strategy works.

It turns out that while this strategy is elegant and correct, it’s not particularly efficient. In particular, as soon as we find the first non-real element of the list, we can stop looking. To handle situations like this, either csc151 library contains a procedure, all, that takes two arguments: a predicate and a list of values, and determines if the predicate holds for all of the values in the list.

> (all real? (list 1 2 3 4/5 65.12345))
> (all (conjoin integer? odd?) (list 1 2 3 4/5 65.12345))
> (all (conjoin integer? odd?) (list 7 1 3 5 7 5 11 3 2.1))

b. Verify that this strategy works.

c. Which strategy do you prefer? Why?

d. Rewrite all-real? to use all.

Exercise 6: The northernmost latitude, revisited

a. Write a procedure, all-cities?, that takes a list as a parameter and returns try if each element of the list is a city.

b. Here’s the final northernmost-latitude code from the reading.

(define northernmost-latitude 
  (lambda (cities) 
      [(not (list? cities))
       (error "northernmost-latitude: requires a non-empty list of cities, received a non-list: " cities)]
      [(null? cities) 
       (error "northernmost-latitude: requires a non-empty list of cities, received the empty list")]
      [(not (all-cities? cities))
       (error "northernmost-latitude: requires a non-empty list of cities, received a list that includes at least one value in the wrong format: " cities)]
       (northernmost-latitude-kernel cities)])))

(define northernmost-latitude-kernel
  (lambda (cities)
    (reduce max (map cadr cities)))) 

Verify that it works as advertised.

Exercise 7: Checking preconditions

In an earlier problem, you wrote preconditions for a procedure, (greatest-of-list lst), that finds the largest number in a list.

(define greatest-of-list
  (lambda (lst)
    (reduce max lst)))

Rewrite the procedure so that it checks all of the preconditions you suggested, as well as others you have come up with along the way.

Exercise 8: Should we check preconditions?

Earlier, you wrote a procedure, all-cities?, that, given a list of values, determines if all of those values are cities.

a. What preconditions does all-cities? have?

b. Argue that all-cities? should not verify its preconditions.

c. Argue that all-cities? should verify its preconditions.

d. If you had to choose whether or not to have all-cities? verify its preconditions, what choice would you make?

For Those With Extra Time

Extra 1: Substitution

Consider a procedure, (list-substitute lst old new), that builds a new list by substituting new ... old whenever old appears in lst.

> (list-substitute (list "black" "red" "green" "blue" "black") "black" "white")
("white" "red" "green" "blue" "white")
> (list-substitute (list "black" "red" "green" "blue" "black") "yellow" "white")
("black" "red" "green" "blue" "black")
> (list-substitute null "yellow" "white")

a. Document this procedure, making sure to carefully consider the preconditions.

b. Write the husk for this procedure. (That is, just write the precondition tests. You can just return the original list for now.)