Higher-order procedures

Abstract

Since procedures are considered just another data type in Scheme, Scheme allows procedures to return new procedures. Procedures that return procedures are sometimes called higher-order procedures. One common use of these higher-order procedures is to define general templates for processing. Filling in a template then gives a procedure to perform a specific task.

For example, a higher-order procedure general-sort could provide a general template for sorting any type of data in any order. We then could use the template for defining specific sorting procedures. Here is a possible interaction:

(define general-sort
   (lambda (order-predicate)
      ...
   )
)
(define sort-numbers-ascending (general-sort <=))
(define sort-numbers-descending (general-sort >=))
(define sort-strings-ascending (general-sort string<=?))

(sort-numbers-ascending '(3 1 4 1 5 9 2)) ==> (1 1 2 3 4 5 9)
(sort-numbers-descending '(3 1 4 1 5 9 2)) ==> (9 5 4 3 2 1 1)
(sort-strings-ascending '("an" "the" "a") ==> ("a" "an" "the")

While the details of general-sort need to be filled in, the idea is that we can use that template for sorting any data by giving the appropriate predicate for determining when one item comes before another.

This reading supplies background for writing such templates.

Defining Templates

One kind of flexibility that Scheme programmers get from having procedures as values is the ability to fill in different arguments of a multi-argument procedure at different points in the computation. For example, consider the following substitute procedure, which takes three arguments -- old-lst, which should be a list, and old and new, which might be values of any type -- and returns a list just like old-lst except that new has been substituted for every element of old-lst that is equal to old (as determined by the equal? predicate):

(define substitute
  (lambda (old-lst old new)

    ;; precondition test
    (if (not (list? old-lst))
        (error 'substitute "The first parameter must be a list"))

    (let kernel ((rest old-lst)
                 (result '()))
      (if (null? rest)
          (reverse result)          ;; Reverse the final list, because the
                                    ;;   recursion builds it back to front.
          (let ((first (car rest)))
            (kernel (cdr rest)
                    (cons (if (equal? old first) new first) result)))))))

In many cases where this procedure might be applied, the values of old and new are obtained before the value of old-lst is even considered. One might, therefore, want to write a procedure that takes just old and new as arguments and returns a procedure that waits for the initial list:

(define sub
  (lambda (old new)
    (lambda (old-lst)
      (substitute old-lst old new))))

Now a definition like

(define year-replacer
  (sub 'year 1997))

makes year-replacer a substitution procedure that performs one specific substitution on any initial list:

> (year-replacer '(ear here year sheer year year beer tier here))
(ear here 1997 sheer 1997 1997 beer tier here)

> (year-replacer '(year month day))
(1997 month day)

> (year-replacer '(no replacement here))
(no replacement here)

Operator Sections

A procedure that is derived from another procedure by filling in some but not all of its arguments is called an "operator section." You don't need the "procedures as values" idea to create individual operator sections, if you know the values that you want to fill in when you're writing the program. A procedure as simple as

(define double
  (lambda (n)
    (* n 2)))

qualifies as an operator section, since it fills in the second argument to the * procedure with a particular value. The extra power that you get in Scheme is the ability to generalize the process of constructing operator sections, as in the sub procedure, which actually builds and returns a new operator section during the execution of the program. The programmer may not even know what will be substituted for what at run time (the values of the parameters old and new might, for instance, be read in from a file that is prepared long after the program is written and compiled); she can nevertheless direct the construction and use of an appropriate operator section without revising the program in any way.

Currying

To curry a procedure that has two or more arguments is to rewrite it, repeatedly using this mechanism for operator sectioning, so that each of its arguments is supplied separately:

(define curried-substitute
  (lambda (template)
    (lambda (old)
      (lambda (new)
        (substitute template old new)))))

> (((curried-substitute '(a b c b d b e)) 'b) 'f)
(a f c f d f e)

In other words: Applying the curried-substitute procedure to the list (a b c b d b e) yields a procedure which, when applied to the symbol b, yields another procedure which, when applied to the symbol f, finally returns the result list (a f c f d f e). Either of the intermediate procedures could easily be split out and given a name:

(define new-for-old
  (curried-substitute '(a b c b d b e)))

> ((new-for-old 'b) 'f)
(a f c f d f e)

(define new-for-b
  (new-for-old 'b))

> (new-for-b 'f)
(a f c f d f e)

One way of looking at this is to think of the intermediate procedures as being used for data storage: new-for-old is "remembering" the value of the filled-in parameter template, and new-for-b is remembering both the value of template and the value of old, so that the only parameter that remains to be supplied in the last call is new.

This process of writing a procedure that returns a procedure is called currying -- named after the logician Haskell B. Curry.

Sorting

The reading on the insertion sort showed how a procedure could be defined that returns a list of numbers in ascending order. In that lab, an ordering predicate (e.g., <= or =>) is used to compare specific data, but all of the rest of the code is independent of the type of data and the nature of the ordering required.

    (define sort-numbers-ascending (general-sort <=))

    (define sort-numbers-descending (general-sort >=))

Composing Procedures

A compose procedure may be defined that takes any two procedures f and g of arity 1 as arguments and returns a single procedure that is a composite of the two, in the sense that the value it returns can be obtained by applying g to its argument and then f to g's result.

(define compose
  (lambda (f g)
    (lambda (x)
      (f (g x)))))

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/reading-higher-order-proc.shtml

Henry M. Walker (walker@cs.grinnell.edu)

created April 2, 1997 by John David Stone last revised February 3, 2005 by Henry M. Walker
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.