CSE 341 - Programming Languages - Autumn 2008

Recursion and Applicative Programming

These notes cover the following topics:
  1. Typical recursion templates
  2. Three important classes of recursive list functions: mapping, reducing, filtering.
  3. Tail recursion
  4. Higher order functions and applicative programming
  5. Lexical closures


Use the "debug" button DrScheme to debug programs, and also to understand how recursive functions are operating

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)
  (if end-test
      (augmenting-function augmenting-value (func reduced-x))))
Factorial is the classic example:

(define (factorial n)
  (if (= n 0)
      (* 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. 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.

(define (double-each s)
  (if (null? s) 
      (cons (* 2 (car s)) (double-each (cdr s)))))

Our base value (the value returned when we reach the base case) isn't always ():
(define (my-append x y)
  (if (null? x) y
      (cons (car x) (my-append (cdr x) y))))
A final important kind of 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)
  (if (null? x) 0
      (+ (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)
        (else (func reduced-x))))

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

(define (all-positive x)
  (cond ((null? x) #t)
        ((<= (car x) 0) #f)
        (else (all-positive (cdr x)))))
;; (all-positive '(3 5 6))  => #t
;; (all-positive '(3 5 -6))  => #f
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)
        (else (my-member e (cdr x)))))
A less commonly seen form is single-test tail recursion.

Scheme compilers handle tail recursion very efficiently, as efficiently as a program that just uses loops instead of recursion. (In particular, tail recursive functions don't use stack space for every recursive call.)

Using Accumulators to Make a Function Tail-recursive

Sometimes you can use an accumulator -- an additional parameter to a function that accumulates the answer -- to convert a non-tail recursive function into a tail recursive one. For example, the previous definition of factorial isn't tail-recursive. Here is one that is:
(define (factorial n)
  (acc-factorial n 1))

;; auxiliary function that takes an additional parameter (the accumulator,
;; i.e. the result computed so far)
(define (acc-factorial n sofar)
  (if (zero? n)
      (acc-factorial (- n 1) (* sofar n))))
Mini-exercise: Define a tail recursive version of a sumlist function to find the sum of the numbers in a list. (Hint: you can define an auxiliary function if needed.)

Simultaneous Recursion on Several Variables

;; test whether two lists have the same length

(define (same-length x y)
  (cond ((and (null? x) (null? y)) #t)
        ((null? x) #f)
        ((null? y) #f)
        (else (same-length (cdr x) (cdr y)))))

;; do these two objects have the same shape?
(define (same-shape x y)
  (cond ((and (pair? x) (pair? y))
         (and (same-shape (car x) (car y))
              (same-shape (cdr x) (cdr y))))
	((or (pair? x) (pair? y)) #f)
	(else #t)))
Mini-exercise: Define a function addlists that takes two lists of numbers, and adds the corresponding elements of each. Ignore extra elements if one of the lists is longer than the other. For example
(addlists '(1 2 3) '(10 11 12))  =>  '(11 13 15)

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)))
        (else (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))))
        (else (positive-numbers (cdr x)))))
Mini-exercise: Scheme has a builtin function filter that takes a predicate and a list s, and returns a new list consisting of all elements of s for which the predicate is true. For example
(filter even? '(1 2 3 4 5))  => (2 4)
Define your own version myfilter.

Example: Insertion Sort

;; variation on list-consing recursion
(define (insert x s)
   (cond ((null? s) (list x))
         ((< x (car s)) (cons x s))
         (else (cons (car s) (insert x (cdr s))))))

;; augmenting recursion
(define (isort s)
   (if (null? s) '()
       (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

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 () () 5))        => (() T T ())

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

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


Scheme provides us with the special form lambda to define an anonymous function. lambda really is special, because it actually creates a lexical closure, which is a bundling of code and a lexical environment. We'll see why this is important later.
(map (lambda (x) (* 2 x)) '(3 4 5))

;; the right way to define addN-to-list
(define (addN-to-list alist n)
  (map (lambda (x) (+ n x)) alist))
Please 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.

map can also be used with functions that take more than one argument. Examples:

(map + '(1 2 3) '(10 11 12))   => (11 13 15)
(map (lambda (x y) (list x y)) '(a b c) '(j k l))   => ((a j) (b k) (c l))

Defining Higher-Order Functions

Suppose we wanted to define the 1-argument version of map ourselves. We can do it like this:
(define (my-map func alist)
   (if (null? alist)
       (cons (func (car alist)) (my-map func (cdr alist)))))

Lexical Closures

Now that we have the code for my-map, we can talk about what makes lambda special. Remember that a lambda expresssion evaluates to 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)
  (my-map (lambda (x) (+ n x)) alist))
When the lambda expression is used in my-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.

Nested Scopes

You can have arbitrarily nested scopes (scopes within scopes within scopes ...). Further, since function names are bound like any other variable, function names also obey the scope rules.

As an example, let's define a simple function test:

(define (test x)
   (+ x 1))
Evaluating (test 10) gives 11.

However, if we evaluate

(let ((test (lambda (x) (* x 2)))
     (test 10))
we get 20 -- within the let, test is rebound to a different function.