CSE 341 -- Recursion and Applicative Programming

These notes cover the following topics:

Recursion Introduction
Typical recursion templates
Three important classes of recursive list functions: mapping, reducing, filtering.
Higher order functions and applicative programming
Lexical closures

Simple examples of recursion:

(define factorial (n)
  (if (= 0 n) 
      1 
      (* n (factorial (- n 1)))))


;  (double-each '(1 3 4))  => (2 6 8)
(define (double-each s)
   (if (null? s)
      ()
      (cons (* 2 (car s))
            (double-each (cdr s)))))

Rules for writing recursive functions

Know when to stop (the base case)
Decide how to take one step towards the base case.
Phrase the solution in terms of one step, and a smaller version of the original problem.

For numbers, the base case is usually a small integer constant, and a smaller version of the problem is something like n-1.

For lists, the base case is usually the empty list, and a smaller version of the problem is usually the "cdr" of the list. Here is a template for most recursive functions you'll write:

(define (fn args)
  (if base-case?
      base-value
      (combine-result (fn (smaller args)))))

Recursion Templates

Augmenting Recursion

Many recursive functions build up their answer bit by bit. We'll call these augmenting recursive functions.

;; general form

(define (func x)
  (cond (end-test end-value)
        (#t (augmenting-function augmenting-value (func reduced-x)))))

Factorial is the classic example:

(define (factorial n)
  (cond ((= n 0) 1)
        (#t (* n (factorial (- n 1))))))

Many Scheme functions operate on lists, so we often see an important special case of augmenting recursion where our augmenting function is CONS and our base case is the empty list. These are sometimes called mapping functions, because they map a function onto every element of a list. Notice that because we are using CONS, we are actually constructing a brand new list and returning it. In other words, we are not changing the original list. Recall:

(define (double-each s)
  (cond ((null? s) nil)
        (#t (cons (* 2 (car s))
                  (double-each (cdr s))))))

With CONS augmenting recursion, our base value (the value returned when we reach the base case) isn't always the empty list:

;; still CONS as augmenting-function, but end-value is not the empty list

(define (my-append x y)
  (cond ((null? x) y)
        (#t (cons (car x) (my-append (cdr x) y)))))

A final important kind of augmenting recursion over lists is the class of reducing functions, because they reduce a list of elements to a single element.

;; sum the elements of a list

(define sumlist (x)
  (cond ((null? x) 0)
        (#t (+ (car x) (sumlist (cdr x))))))

Tail Recursion

In tail recursion, we don't build up a solution, but rather, just return a recursive call on a smaller version of the problem. Double-test tail recursion is the most common form:

;; general form:

(define (func x)
  (cond ((end-test-1 end-value-1)
         (end-test-2 end-value-2)
         (#t (func reduced-x)))))

;; example, are all elements of a list positive?

(define(all-positive x)
  (cond ((null? x) #t)
        ((<= (car x) 0) #f)
        (#t (all-positive (cdr x)))))

Some tail recursive functions will have more than one argument. All but one of the arguments are passed along unaltered.

;; example, member:

(define (my-member e x)
  (cond ((null? x) #f)
        ((equal? e (car x)) #t)
        (#t (my-member e (cdr x)))))

Tail recursion is important because it can be efficiently executed, by translating it into a loop.

Conditional augmentation (like augmenting recursion)

A final important template is conditional augmentation, where we don't necessarily augment on every step. These functions are sometimes called filtering functions, because they remove elements from a list that don't pass some test.

(define (func x)
  (cond (end-test end-value)
        (aug-test (augmenting-function augmenting-value (func reduced-x)))
        (#t (func reduced-x))))

;; example:  remove all non-positive numbers from a list

(define (positive-numbers x)
  (cond ((null? x) ())
        ((> (car x) 0) (cons (car x) (positive-numbers (cdr x))))
        (#t (positive-numbers (cdr x)))))

Example: Insertion Sort

;; variation on list-consing recursion

(define (insert x s)
   (cond ((null? s) (list x))
         ((< x (car s)) (cons x s))
         (#t (cons (car s) (insert x (cdr s))))))

;; augmenting recursion

(define (isort s)
   (cond ((null? s) ())
         (#t (insert (car s) (isort (cdr s))))))

Applicative Programming

Applicative programming uses higher order functions -- functions that take other functions as arguments, or that return functions as the result. Scheme gets much of its expressiveness and capacity for abstraction by supporting an applicative programming style. Scheme supports functions as first class citizens.

Mapping a function over a list

Let's start with an example. Look at the following functions:

;; here is a general function that adds N to every element of a list

(define (addN-to-list alist n)
  (cond ((null? alist) nil)
	(#t (cons (+ n (car alist)) (addN-to-list (cdr alist) n)))))

;; here is a function that takes the cdr of every element of a list

(define (getcdrs alist)
  (cond ((null? alist) nil)
	(#t (cons (cdr (car alist)) (getcdrs (cdr alist))))))

If we think about what these functions are doing at an abstract level, we see that they are applying some function to every element of a list, and returning the list of resulting values. Scheme provides us with a built-in function to support this idiom.

MAP is a built in Scheme function that takes a function and a list as an argument, and returns the list that results by applying that function to every element of the list.

(map function list)             ;; general form

(map null? '(3 nil nil 5))     => (#f #t #t #f)

(map round '(3 3.3 4.6 5))     => (3 3 5 5)

(map cdr '((1 2) (3 4) (5 6))  => ((2) (4) (6))

Lambda

We often find ourselves mapping little functions over lists that would be annoying to write a separate definition for. For instance, if we wanted to map the double function, we'd have to do the following:

(define (double x) (* 2 x))      

(map double '(3 4 5))         => (6 8 10)

We've already seen the special form LAMBDA. We've used it to define our own functions, and we can use it again to provide quick, inline definitions of helper functions.

(map (lambda (x) (* 2 x)) '(3 4 5))

Can you rewrite addN-to-list using map?

;; a better way to define addN-to-list

(define (addN-to-list alist n)
  (map (lambda (x) (+ n x)) alist))

Note that in the addN-to-list function, the body of the lambda function can refer to the variable n, which is in the lexical scope of the lambda expression.

How would we write our own version of map? It seems harder than it really is:

(define (my-map func alist)
  (if (null? alist)
    ()
    (cons (func (car alist))
          (my-map func (cdr alist)))))

Filtering the elements of a list

Another important idiom is to filter a list, that is, to remove the elements of a list that don't pass a certain test. Let's write our own higher-order function to do this for us:

(define (remove-if test? alist)
  (cond ((null? alist) ())
        ((test? (car alist)) (remove-if test? (cdr alist)))
        (#t (cons (car alist) (remove-if test? (cdr alist))))))

;;; It's easy to do the opposite too:

(define (remove-if-not test? alist)
  (remove-if (lambda (x) (not (test? x))) alist))

Reducing Lists

We often want to distill a list of elements into a particular value. Reduce takes a function that operates on two items and a list of those items and applies the functions to the items (left to right) and returns the result.

(define (reduce func base alist)
  (cond ((null? alist) base)
        (#t (func (car alist) (reduce func base (cdr alist))))))

;; add a list of numbers
(reduce + 0 '(1 2 3)) => 6 

;; add just the even numbers
(reduce + 0 (remove-if odd? '(2 3 4 5)))  => 6

;; what the heck does this do?
(reduce + 0 (map (lambda (x) 1) '(1 2 3 4 5 6 7)))

Lexical Closures

Now that we've looked at some higher order functions, we can talk about what makes LAMBDA so special. Lambda expressions evaluate to what we sometimes call a lexical closure, which is a coupling of code and a lexical environment (a scope, essentially). The lexical environment is necessary because the code needs a place to look up the definitions of symbols it references. For example, look again at addN-to-list below.

(define (addN-to-list alist n)
  (map (lambda (x) (+ n x)) alist))

When the lambda expression is actually applied in the body of map, it needs to know where to look up the variable name n. It can get the right value for n, because it retains its lexical environment. To illustrate this more graphically:

; this function takes two arguments a function and an arg and
; applies the function to the argument

(define (foo some-function x)
  (some-function x))

(define (bar x)
  (foo (lambda (y) (list y x)) 20))

(bar 10)    => (20 10)   ;; but why not (20 20) ??

The reason that (bar 10) returns (20 10) is because the x in the lambda expression is referenced in the environment of the lambda expression's definition (its lexical environment, which is in the definition of bar) rather than the environment of its execution (its dynamic environment, which is in foo). If the dynamic environment were used, then any caller of foo would have to be certain that her lambda expressions didn't reference any non-local names which also existed in foo, because in foo, they might possibly have different bindings.

Here's another example. We'll define a function that returns another function:

; return an incrementer function
(define (add-n n)
  (lambda (x) (+ x n)))

(add-n 10)      => the function that adds 10 to things

(define add10 (add-n 10))
(add10 14)      => 24

This example is pretty trivial, but imagine how hard it might be to do this in a language like C or Java. Closures are an extremely powerful concept, and can (for example) be used as the basis for a simple object system in Scheme. Our strategy will be to use a closure to encapsulate a set of "member" functions (and state) for an object. This closure is a function that dispatches to the appropriate function based on its name.

(define (make-point _x _y)
  (let* ((x (lambda () _x))                          ;; accessor functions
	 (y (lambda () _y))
	 (set-x! (lambda (new-x) (set! _x new-x)))   ;; setter functions
	 (set-y! (lambda (new-y) (set! _y new-y)))
	 (self (lambda (msg)                         ;; the dispatch function
		 (cond ((eq? msg 'x) x)
		       ((eq? msg 'y) y)
		       ((eq? msg 'set-x!) set-x!)
		       ((eq? msg 'set-y!) set-y!)
		       (#t 'error)))))
    self))

;;; Now we can use our point constructor to create new points...

(define p1 (make-point 10 20))
p1                                 => #<procedure:self>  
(p1 'x)                            => #<procedure:x>  
((p1 'x))                          => 10
((p1 'set-x) 25)                  
((p1 'x))                          => 25

The syntax leaves a lot to be desired, but it does have some of the basic qualities of an object system: encapsulation and dynamic dispatch.

dugan@cs.washington.edu (Last Update: )