Next: Command-Line Debugger, Previous: Debugging, Up: Debugging

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`

.