4.1 Subproblems and Reductions

Understanding the concepts of reduction and subproblem is essential to good use of the debugging tools. The Scheme interpreter evaluates an expression by reducing it to a simpler expression. In general, Scheme’s evaluation rules designate that evaluation proceeds from one expression to the next by either starting to work on a subexpression of the given expression, or by reducing the entire expression to a new (simpler, or reduced) form. Thus, a history of the successive forms processed during the evaluation of an expression will show a sequence of subproblems, where each subproblem may consist of a sequence of reductions.

For example, both ‘(+ 5 6)’ and ‘(+ 7 9)’ are subproblems of the following combination:

(* (+ 5 6) (+ 7 9))

If ‘(prime? n)’ is true, then ‘(cons 'prime n)’ is a reduction for the following expression:

(if (prime? n)
    (cons 'prime n)
    (cons 'not-prime n))

This is because the entire subproblem of the if expression can be reduced to the problem ‘(cons 'prime n)’, once we know that ‘(prime? n)’ is true; the ‘(cons 'not-prime n)’ can be ignored, because it will never be needed. On the other hand, if ‘(prime? n)’ were false, then ‘(cons 'not-prime n)’ would be the reduction for the if expression.

The subproblem level is a number representing how far back in the history of the current computation a particular evaluation is. Consider factorial:

(define (factorial n)
  (if (< n 2)
      1
      (* n (factorial (- n 1)))))

If we stop factorial in the middle of evaluating ‘(- n 1)’, the ‘(- n 1)’ is at subproblem level 0. Following the history of the computation “upwards,” ‘(factorial (- n 1))’ is at subproblem level 1, and ‘(* n (factorial (- n 1)))’ is at subproblem level 2. These expressions all have reduction number 0. Continuing upwards, the if expression has reduction number 1.

Moving backwards in the history of a computation, subproblem levels and reduction numbers increase, starting from zero at the expression currently being evaluated. Reduction numbers increase until the next subproblem, where they start over at zero. The best way to get a feel for subproblem levels and reduction numbers is to experiment with the debugging tools, especially debug.