Pragmatics of local, Part 2

Next: Pragmatics of localPart Up: Organizing Programs with local Previous: Pragmatics of localPart

Pragmatics of local, Part 2

Suppose we need a function that produces the last occurrence of some item in a list. To be precise, assume we have lists of records of rock stars. For simplicity, each star is represented as a pair of values:

(define-struct star (name instrument))

A star (record) is a structure:

(make-star s t) where s and t are symbols.

Here is an example:

(define alos 
  (list (make-star 'Chris 'saxophone) 
        (make-star 'Robby 'trumpet) 
        (make-star 'Matt 'violin) 
        (make-star 'Wen 'guitar) 
        (make-star 'Matt 'radio)))

This list contains two occurrences of 'Matt. So, if we wanted to determine the instrument that goes with the last occurrence of 'Matt, we would want 'radio. For 'Wen, on the other hand, our function would produce 'guitar. Of course, looking for the instrument of 'Kate should yield false to indicate that there is no record for 'Kate.

Let's write down a contract, a purpose statement, and a header:

;; last-occurrence : symbol list-of-star -> star or false
;; to find the last star record in alostars that contains s in name field 
(define (last-occurrence s alostars) ...)

The contract is unusual because it mentions two classes of data to the right of the arrow: star and false. Although we haven't seen this kind of contract before, its meaning is obvious. The function may produce a star or false.

We have already developed some examples, so we can move directly to the template stage of our design recipe:

(define (last-occurrence s alostars)
  (cond 
    [(empty? alostars) ...] 
    [else ... (first alostars) ... (last-occurrence s (rest alostars)) ...]))

The real problem with this function, of course, shows up only when we want to fill in the gaps in this template. The answer in the first case is false, per specification. How to form the answer in the second case is far from clear. Here is what we have:

(first alostars) is the first star record on the given list. If its name field is equal to s, it may or may not be the final result. It all depends on the records in the rest of the list.
(last-occurrence s (rest alostars)) evaluates to one of two things: a star record with s as the name field or false. In the first case, the star record is the result; in the second case, the result is either false or the first record.

The second point implies that we need to use the result of the natural recursion twice, first to check whether it is a star or a boolean, and second, to use it as the answer if it is a star.

The dual-use of the natural recursion is best expressed with a local-expression:

(define (last-occurrence s alostars)
  (cond 
    [(empty? alostars) false] 
    [else (local ((define r (last-occurrence s (rest alostars)))) 
            (cond 
              [(star? r) r] 
              ...))]))

The nested local-expression gives a name to the result of the natural recursion. The cond-expression uses it twice. We could eliminate the local-expression by replacing r with the right-hand side:

(define (last-occurrence s alostars)
  (cond 
    [(empty? alostars) false] 
    [else (cond 
            [(star? (last-occurrence s (rest alostars))) 
             (last-occurrence s (rest alostars))] 
            ...)]))

But even a superficial glance shows that reading a natural recursion twice is difficult. The version with local is superior.

From the partially refined template it is only a short step to the full definition:

;; last-occurrence : symbol list-of-star -> star or false
;; to find the last star record in alostars that contains s in name field 
(define (last-occurrence s alostars) 
  (cond 
    [(empty? alostars) false] 
    [else (local ((define r (last-occurrence s (rest alostars)))) 
            (cond 
              [(star? r) r] 
              [(symbol=? (star-name (first alostars)) s) (first alostars)] 
              [else false]))]))

The second clause in the nested cond-expression compares the first record's name field with s if r is not a star record. In that case, there is no record with the matching name in the rest of the list, and, if the first record is the appropriate one, it is the result. Otherwise, the entire list does not contain the name we're looking for and the result is false.

Exercises

Exercise 18.1.11

Evaluate the following test by hand:

(last-occurrence 'Matt
  (list (make-star 'Matt 'violin) 
        (make-star 'Matt 'radio)))

How many local-expressions are lifted? Solution

Exercise 18.1.12

Consider the following function definition:

;; max : non-empty-lon -> number
;; to determine the largest number on alon 
(define (max alon) 
  (cond 
    [(empty? (rest alon)) (first alon)] 
    [else (cond 
            [(> (first alon) (max (rest alon))) (first alon)] 
            [else (max (rest alon))])]))

Both clauses in the nested cond-expression compute (max (rest an-inv)), which is therefore a natural candidate for a local-expression. Test both versions of max with

(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

Explain the effect. Solution

Exercise 18.1.13

Develop the function to-blue-eyed-ancestor. The function consumes a family tree (ftn) (see section ) and produces a list that explains how to get to a blue-eyed ancestor. If there is no blue-eyed ancestor, the function produces false.

The function's contract, purpose statement, and header are as follows:

;; to-blue-eyed-ancestor : ftn -> path or false 
;; to compute the path from a-ftn tree to a blue-eyed ancestor 
(define (to-blue-eyed-ancestor a-ftn) ...)

A path is a list of 'father and 'mother, which we call a direction. Here are the two data definitions:

A direction is either

the symbol 'father or
the symbol 'mother .

A path is either

empty or
(cons s los) where s is a direction and los is a path.

The empty path indicates that a-ftn has 'blue in the eyes field. If the first item is 'mother, we may search in the mother's family tree for a blue-eyed ancestor using the rest of the path. Similarly, we search in the father's family tree if the first item is 'father and use the rest of the path for further directions.

Examples:

(to-blue-eyed-ancestor Gustav) produces (list 'mother) for the family tree in figure ;
(to-blue-eyed-ancestor Adam) produces false in the same setting; and
if we added (define Hal (make-child Gustav Eva 'Gustav 1988 'hazel)) then (to-blue-eyed-ancestor Hal) would yield (list 'father 'mother).

Build test cases from these examples. Formulate them as boolean expressions, using the strategy of section

. Solution

Backtracking: The functions last-occurrence and to-blue-eyed-ancestor produce two kinds of results: one to indicate a successful search and another one to indicate a failure. Both are recursive. If a natural recursion fails to find the desired result, each tries to compute a result in a different manner. Indeed, to-blue-eyed-ancestor may use another natural recursion.

This strategy of computing an answer is a simple form of BACKTRACKING. In the world of data that we have dealt with so far, backtracking is simple and just a device to save computing steps. It is always possible to write two separate recursive functions that accomplish the same purpose as one of the backtracking functions here.

We will take an even closer look at backtracking in section . Also, we will discuss counting computing steps in intermezzo 5.

Exercise 18.1.14

Discuss the function find from exercise in terms of backtracking. Solution

Next: Pragmatics of localPart Up: Organizing Programs with local Previous: Pragmatics of localPart

PLT