Designing Abstractions with Functions-as-Values

The combination of local-expressions and functions-as-values simplifies our recipe for creating abstract functions. Consider our very first example in figure  again. If we replace the contents of the boxes with rel-op, we get a function that has a free variable. To avoid this, we can either add rel-op to the parameters or we can wrap the definition in a local and prefix it with a function that consumes rel-op. Figure  shows what happnes when we use this idea with filter. If we also make the locally defined function the result of the function, we have defined an abstraction of the two original functions.

(define (filter2 rel-op) (local ((define (abs-fun alon t) (cond [(empty? alon) empty] [else (cond [( (first alon) t) (cons (first alon) (abs-fun (rest alon) t))] [else (abs-fun (rest alon) t)])]))) abs-fun)) Figure: Abstracting with local

Put differently, we follow the example of add in the preceding section. Like add, filter2 consumes an argument, defines a function, and returns this function as a result. The result remembers the rel-op argument for good as the following evaluation shows:

  (filter2 <)

= (local ((define (abs-fun alon t)
            (cond 
              [(empty? alon) empty] 
              [else 
                (cond 
                  [(< (first alon) t) 
                   (cons (first alon) 
                     (abs-fun (rest alon) t))] 
                  [else 
                     (abs-fun (rest alon) t)])]))) 
    abs-fun) 

= (define (below3 alon t)
    (cond 
      [(empty? alon) empty] 
      [else 
        (cond 
          [(< (first alon) t) 
           (cons (first alon) 
             (below3 (rest alon) t))] 
          [else 
            (below3 (rest alon) t)])])) 
   below3 

From the calculation, it follows that we can give the result of (filter2 <) a name and use it as if it were below. More succinctly,

(define below2 (filter2 <))

(define (below3 alon t)
    (cond 
      [(empty? alon) empty] 
      [else 
        (cond 
          [(< (first alon) t) 
           (cons (first alon) 
             (below3 (rest alon) t))] 
          [else 
            (below3 (rest alon) t)])]))

(define below2 below3) 

The example suggests a variant of the abstraction recipe from section :

The comparison:

The new recipe still requires us to compare and to mark the differences.

The abstraction:

The new step concerns the way we define the abstract function. We place one of the functions into a local-expression and use the name of the function as the body of the local:

(local ((define (concrete-fun x y z)
          ...    ...    ...)) 
  concrete-fun) 

From that, we can create the abstract function by listing the names in the boxes as parameters:

(define (abs-fun op1 op2)
  (local ((define (concrete-fun x y z) 
            ...    ...    ...)) 
    concrete-fun)) 

If op1 or op2 is a special symbol, say <, we name it something that is more meaningful in the new context.

The test:

To test the abstract function, we define the concrete functions again, as before. Consider the example of below and above. Obtaining below and above as instances of filter2 is now straightforward:

(define below2 (filter2 <))

(define above2 (filter2 >)) 

We simply apply filter2 to the contents of the box in the respective concrete function and that application produces the old function.

The contract:

The contract of an abstract function contains two arrows. After all, the function produces a function, and to describe this relationship the type to the right of the first arrow must contain another arrow.

Here is the contract for filter2:

;; filter2 : (X Y -> boolean) -> ((listof X) Y -> (listof X))

It consumes a comparison function and produces a concrete filter-style function.

The generalization of the contract works as before.

Exercise 22.2.1

Define an abstraction of the functions convertCF and names from section  using the new recipe for abstraction. Solution

Exercise 22.2.2

Define an abstract version of sort (see exercise ) using the new recipe for abstraction. Solution

Exercise 22.2.3

Define fold using the new recipe for abstraction. Recall that fold abstracts the following pair of functions:

;; sum : (listof number) -> number
;; to compute the sum of alon 
(define (sum alon) 
  (cond 
    [(empty? alon) 0] 
    [else (+ (first alon) 
             (sum (rest alon)))])) 

;; product : (listof number) -> number
;; to compute the product of alon 
(define (product alon) 
  (cond 
    [(empty? alon) 1] 
    [else (* (first alon) 
             (product (rest alon)))])) 

Solution