Extended Exercise: Accumulators on Trees

(define-struct child (father mother name date eyes)) A node in a family tree (short: ftn) is either empty, or (make-child f m na da ec) where f and m are ftns, na and ec are symbols, and da is a number. ;; all-blue-eyed-ancestors : ftn -> (listof symbol) ;; to construct a list of all blue-eyed ancestors in a-ftree (define (all-blue-eyed-ancestors a-ftree) (cond [(empty? a-ftree) empty] [else (local ((define in-parents (append (all-blue-eyed-ancestors (child-father a-ftree)) (all-blue-eyed-ancestors (child-mother a-ftree))))) (cond [(symbol=? (child-eyes a-ftree) 'blue) (cons (child-name a-ftree) in-parents)] [else in-parents]))])) Figure: Collecting family trees with blue-eyed-ancestor?

Figure  recalls the structure and data definitions of family trees from section  where we developed the function blue-eyed-ancestor?, which determined whether an ancestor family tree contained a blue-eyed family member. In contrast, all-blue-eyed-ancestors, the function in figure , collects the names of all blue-eyed family in a given family tree.

The function's structure is that of a tree-processing function. It has two cases: one for the empty tree and another one for a child node. The latter clause contains two self-references: one per parent. These recursive applications collect the names of all blue-eyed ancestors from the father's and the mother's family tree; append combines the two lists into one.

The append function is a structurally recursive function. Here it processes the two lists that the natural recursions of all-blue-eyed-ancestors produce. According to section , this observation suggests that the function is a natural candidate for a transformation into accumulator-style.

Let's get started:

;; all-blue-eyed-ancestors : ftn -> (listof symbol)
;; to construct a list of all blue-eyed ancestors in a-ftree 
(define (all-blue-eyed-ancestors a-ftree0) 
  (local (;; accumulator ... 
          (define (all-a a-ftree accumulator) 
            (cond 
              [(empty? a-ftree) ...] 
              [else 
               (local ((define in-parents 
                         (all-a ... (child-father a-ftree) ... 
                                ... accumulator ...) 
                         (all-a ... (child-mother a-ftree) ... 
                                ... accumulator ...))) 
                 (cond 
                   [(symbol=? (child-eyes a-ftree) 'blue) 
                    (cons (child-name a-ftree) in-parents)] 
                   [else in-parents]))]))) 
    (all-a a-ftree0 ...))) 

Our next goal is the formulation of an accumulator invariant. The general purpose of the accumulator is to remember knowledge about a-ftree0 that all-a loses as it traverses the tree. A look at the definition in figure  shows two recursive applications. The first one processes (child-father a-ftree), which means this application of all-blue-eyed-ancestors loses knowledge about the mother of a-ftree. Conversely, the second recursive application has no knowledge of the father of a-ftree as it processes the mother's family tree.

At this point, we have two choices:

1. The accumulator could represent all blue-eyed ancestors encountered so far, including those in the mother's family tree, as it descends into the father's tree.
2. The alternative is to have the accumulator stand for the lost items in the tree. That is, as all-a processes the father's family tree, it remembers the mother's tree in the accumulator (and everything else it hasn't seen before).

Initially, all-a has not seen any of the nodes in the family tree, so accumulator is empty. As all-a is about to traverse the father's family tree, we must create a list that represents all blue-eyed ancestors in the tree that we are about to forget, which is the mother's tree. This suggests the following accumulator invariant formulation:

;; accumulator is the list of blue-eyed ancestors
;; encountered on the mother-side trees of the path in 
;; a-ftree0 to a-ftree 

To maintain the invariant for the natural recursion, we must collect the ancestors on the mother's side of the tree. Since the purpose of all-a is to collect those ancestors, we use the expression

(all-a (child-mother a-ftree) accumulator)

(local ((define in-parents 
          (all-a (child-father a-ftree) 
            (all-a (child-mother a-ftree) 
              accumulator)))) 
  (cond 
    [(symbol=? (child-eyes a-ftree) 'blue) 
     (cons (child-name a-ftree) in-parents)] 
    [else in-parents])) 

;; all-blue-eyed-ancestors : ftn -> (listof symbol) ;; to construct a list of all blue-eyed ancestors in a-ftree (define (all-blue-eyed-ancestors a-ftree) (local (;; accumulator is the list of blue-eyed ancestors ;; encountered on the mother-side trees of the path in ;; a-ftree0 to a-ftree (define (all-a a-ftree accumulator) (cond [(empty? a-ftree) accumulator] [else (local ((define in-parents (all-a (child-father a-ftree) (all-a (child-mother a-ftree) accumulator)))) (cond [(symbol=? (child-eyes a-ftree) 'blue) (cons (child-name a-ftree) in-parents)] [else in-parents]))]))) (all-a a-ftree empty))) Figure: Collecting blue-eyed ancestors, accumulator-style (version 1)

For the second version, we want the accumulator to represent a list of all of the family trees that haven't been processed yet. Because of the different intention, let us call the accumulator parameter todo:

;; todo is the list of family trees 
;; encountered but not processed  

(local ((define in-parents 
          (all-a (child-father a-ftree) 
            (cons (child-mother a-ftree) todo)))) 
  (cond 
    [(symbol=? (child-eyes a-ftree) 'blue) 
     (cons (child-name a-ftree) in-parents)] 
    [else in-parents])) 

The problem now is that when all-a is applied to the empty tree, todo does not represent the result but what is left to do for all-a. To visit all those family trees, all-a must be applied to them, one at a time. Of course, if todo is empty, there is nothing left to do; the result is empty. If todo is a list, we pick the first tree on the list as the next one to be processed:

(cond
  [(empty? todo) empty] 
  [else (all-a (first todo) (rest todo))]) 

;; all-blue-eyed-ancestors : ftn -> (listof symbol) ;; to construct a list of all blue-eyed ancestors in a-ftree (define (all-blue-eyed-ancestors a-ftree0) (local (;; todo is the list of family trees encountered but not processed (define (all-a a-ftree todo) (cond [(empty? a-ftree) (cond [(empty? todo) empty] [else (all-a (first todo) (rest todo))])] [else (local ((define in-parents (all-a (child-father a-ftree) (cons (child-mother a-ftree) todo)))) (cond [(symbol=? (child-eyes a-ftree) 'blue) (cons (child-name a-ftree) in-parents)] [else in-parents]))]))) (all-a a-ftree0 empty))) Figure: Collecting blue-eyed ancestors, accumulator-style (version 2)

Figure  contains the complete definition for this second accumulator-style variant of all-blue-eyed-ancestors. The auxiliary definition is the most unusual recursive function definition we have seen. It contains a recursive application of all-a in both the first and the second cond-clause. That is, the function definition does not match the data definition for family trees, the primary inputs. While a function like that can be the result of a careful chain of development steps, starting from a working function developed with a design recipe, it should never be a starting point.

The use of accumulators is also fairly common in programs that process representations of programs. We encountered these forms of data in section , and like family trees, they have complicated data definitions. In intermezzo 3, we also discussed some concepts concerning variables and their mutual association, though without processing these concepts. The following exercises introduce simple functions that work with the scope of parameters, binding occurrences of variables, and other notions.

Exercise 32.1.1

Develop a data representation for the following tiny subset of Scheme expressions:

The subset contains only three kinds of expressions: variables, functions of one argument, and function applications.

Examples:

    
1. (lambda (x) y)

2. ((lambda (x) x) 
        (lambda (x) x))

3. (((lambda (y) 
           (lambda (x) 
             y)) 
         (lambda (z) z)) 
        (lambda (w) w)) 

Recall that lambda-expressions are functions without names. Thus they bind their parameter in the body. In other words, the scope of a lambda-expression's parameter is the body. Explain the scope of each binding occurrence in the above examples. Draw arrows from all bound occurrences to the binding occurrences.

If a variable occurs in an expression but has no corresponding binding occurrence, the occurrence is said to be free. Make up an expression in which x occurs both free and bound. Solution

Exercise 32.1.2

Develop the function

;; free-or-bound : Lam -> Lam 
;; to replace each non-binding occurrence of a variable in a-lam  
;; with 'free or 'bound, depending on whether the  
;; occurrence is bound or not. 
(define (free-or-bound a-lam) ...) 

Exercise 32.1.3

Develop the function

;; unique-binding : Lam -> Lam 
;; to replace variables names of binding occurrences and their bound 
;; counterparts so that no name is used twice in a binding occurrence 
(define (unique-binding a-lam) ...) 

Hint: The function gensym creates a new and unique symbol from a given symbol. The result is guaranteed to be distinct from all other symbols in the program, including those previously generated with gensym.

Use the technique of this section to improve the function. Hint: The accumulator relates old parameter names to new parameter names. Solution