Scheme encourages programmers to keep their eyes open for common patterns in their code -- procedure bodies, for example, that have the same structure, even if they carry out different specific operations and fulfill different purposes. It often happens that the common structure, once identified, can be ``abstracted'' and placed in a higher-order procedure. This simplifies the writing of subsequent expressions with the same structure.

The textbook illustrates this technique of procedural abstraction by identifying and abstracting a pattern that occurs in many of the flat-recursion procedures developed back in section 4.2. Because we have systematically added precondition tests and used named let-expressions rather than letrec-expressions, our flat-recursion procedures look a little different from the ones shown on page 213 of the textbook. For instance, here is how we would write apply-to-all (a curried version of map) and sum (which takes any list of numbers as its argument and returns their sum):

(define apply-to-all
  (lambda (proc)
    (lambda (ls)
      (if (not (list? ls))
          (error 'apply-to-all "The argument must be a list"))
      (let loop ((rest ls))
        (if (null? rest)
            '()
            (cons (proc (car rest)) (loop (cdr rest))))))))

(define list-of-numbers?
  (lambda (ls)
    (or (null? ls)
        (and (pair? ls)
             (number? (car ls))
             (list-of-numbers? (cdr ls))))))

(define sum
  (lambda (ls)
    (if (not (list-of-numbers? ls))
        (error 'sum "The argument must be a list of numbers"))
    (let loop ((rest ls))
      (if (null? rest)
          0
          (+ (car rest) (loop (cdr rest)))))))

1. Write the product procedure, which takes any list of numbers as its argument and returns their product, in the same style.

Because the inner lambda-expression of apply-to-all and the lambda-expressions in sum and product have the same structure, it is possible to abstract this common structure and give it a name:

(define flat-recur
  (lambda (pre-tester seed builder)
    (lambda (ls)
      (if (not (pre-tester ls))
          (error ':flat-recur "The precondition test failed"))
      (let loop ((rest ls))
        (if (null? rest)
            seed
            (builder (car rest) (loop (cdr rest))))))))

(The colon at the beginning of the symbol :flat-recur in the error message is a conventional indication that the error does not occur inside flat-recur itself, but inside the procedure that is returned as the value of a call to flat-recur.)

Now the definitions of apply-to-all, sum, and product can be simplified:

(define apply-to-all
  (lambda (proc)
    (flat-recur list? '()
                (lambda (first recursive-result)
                  (cons (proc first) recursive-result)))))

(define sum
  (flat-recur list-of-numbers? 0 +))

(define product
  (flat-recur list-of-numbers? 1 *))

2. Using flat-recur, define a procedure tally-symbols that takes any list as its argument and determines how many of the top-level elements of that list are symbols.

Here's another example of procedural abstraction. Over the past few weeks, we've written several very similar procedures to perform precondition tests:

(define list-of-numbers?
  (lambda (ls)
    (or (null? ls)
        (and (pair? ls)
             (number? (car ls))
             (list-of-numbers? (cdr ls))))))

(define list-of-symbols?
  (lambda (ls)
    (or (null? ls)
        (and (pair? ls)
             (symbol? (car ls))
             (list-of-symbols? (cdr ls))))))

(define list-of-natural-numbers?
  (lambda (ls)
    (or (null? ls)
        (and (pair? ls)
             (integer? (car ls))
             (not (negative? (car ls)))
             (list-of-natural-numbers? (cdr ls))))))

(define s-or-n-list?
  (lambda (ls)
    (or (null? ls)
        (and (pair? ls)
             (or (symbol? (car ls))
                 (number? (car ls)))
             (s-or-n-list? (cdr ls))))))

There's clearly a common structure here. The only thing that changes from one of these predicates to another is the nature of the test that is applied to each element of the list in turn. We can easily abstract the common structure, parameterizing the element test:

(define list-of
  (lambda (pred?)
    (letrec ((test-all (lambda (ls)
                         (or (null? ls)
                             (and (pair? ls)
                                  (pred? (car ls))
                                  (test-all (cdr ls)))))))
      test-all)))

This simplifies the definition of procedures like the ones shown above:

(define list-of-numbers? (list-of number?))

(define list-of-symbols? (list-of symbol?))

(define list-of-natural-numbers?
   (list-of (conjoin integer? (complement negative?))))
   ; (CONJOIN is defined in the lab on procedures as values,
   ;   and COMPLEMENT is given as an exercise in that lab.)

(define s-or-n-list?
  (list-of (lambda (obj) (or (symbol? obj) (number? obj)))))

But in many contexts one can simply bypass such definitions:

(define sum
  (flat-recur (list-of number?) 0 +))

3. Use list-of to define a procedure that tests whether its argument is a list containing only lower-case letters.

4. Develop an analogous procedure tree-of that takes any unary predicate pred? as its argument and returns a predicate that determines whether its argument is a tree in which all of the leaves satisfy pred?.

This document is available on the World Wide Web as

http://www.math.grin.edu/courses/Scheme/spring-1997/procedural-abstraction.html