Next: Command-Line Debugger, Up: Debugging [Contents][Index]

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`

.

Next: Command-Line Debugger, Up: Debugging [Contents][Index]