%% -*- LaTeX -*-

\chapter{Debugging}
\label{debugging}

Even computer software that has been planned carefully and written well may
not always work correctly.  Mysterious creatures called {\it bugs} may creep
in and wreak havoc, leaving the programmer to clean up the mess.  Some have
theorized that a program fails only because its author made a mistake, but
experienced computer programmers know that bugs are always to blame.  This is
why the task of fixing broken computer software is called {\it debugging}.

It is impossible to prove the correctness of any non-trivial program; hence
the Cynic's First Law of Debugging:

\begin{quote}
Programs don't become more reliable as they are debugged; the bugs just get
harder to find.
\end{quote}

Scheme is equipped with a full complement of special software for finding and
removing bugs.  The debugging tools include facilities for tracing a program's
use of specified procedures, for examining Scheme environments, and for
setting {\it breakpoints}, places where the program will pause for inspection.

Many bugs are detected when programs try to do something which is impossible,
like adding a number to a symbol, or using a variable which does not exist;
this type of mistake is called an {\it error}.  Whenever an error occurs,
Edwin automatically describes the error in the Typein Window and asks whether
to start the debugging tools.  For example, using a nonexistent variable {\tt
foo} will cause Edwin to respond, ``{\tt Unbound Variable FOO -- Debug?}''
Typing \key{y} will start the debugging tools; \key{n} will return to Edwin.

Sometimes, a bug will never cause an error, but will still cause the program
to operate incorrectly.  For instance,

\begin{scheme}
(prime? 7) \ev \schfalse
\end{scheme}

In this situation, Scheme does not know that the program is misbehaving.  The
programmer must notice the problem and, if necessary, start the debugging
tools manually.

There are several approaches to finding bugs in a Scheme program:

\begin{itemize}
\item Inspect the original Scheme program.
\item Use the debugging tools described below to follow your program's progress.
\item Edit the program to insert checks and breakpoints.
\end{itemize}

\noindent Only experience can teach how to debug programs, so be sure to
experiment with all these approaches while doing your own debugging.  Planning
ahead is the best way to ward off bugs, but when bugs do appear, be prepared
to attack them with all the tools available.  Remember that the 6.001 Lab is
equipped with some of the most powerful Scheme debugging tools available --
6.001 TAs.  If you really get stuck, ask a TA for help.

\newpage
\section{Subproblems and Reductions}
\index{subproblems}
\index{reductions}

Understanding the concepts of {\it reduction} and {\it subproblem} is
essential to good use of the debugging tools.  The Scheme interpreter
evaluates an expression by {\it 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 {\it subexpression} of
the given expression, or by {\it 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 {\tt (+ 5 6)} and {\tt (+ 7 9)} are subproblems of the
following combination:

\begin{scheme}
(* (+ 5 6) (+ 7 9))
\end{scheme}

If {\tt (prime? n)} is true, then {\tt (cons 'prime n)} is a reduction for the
following expression:

\begin{scheme}
(if (prime? n)
    (cons 'prime n)
    (cons 'not-prime n))
\end{scheme}

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

\newpage
The {\it subproblem level} is a number representing how far back in the
history of the current computation a particular evaluation is.  Consider {\tt
factorial}:

\begin{scheme}
(define (factorial n)
  (if (< n 2)
      1
      (* n (factorial (- n 1)))))
\end{scheme}

\noindent If we stop {\tt factorial} in the middle of evaluating {\tt (- n
1)}, the {\tt (- n 1)} is at subproblem level 0.  Following the history of the
computation ``upwards,'' {\tt (factorial (- n 1))} is at subproblem level 1,
and {\tt (* n (factorial (- n 1)))} is at subproblem level 2.  These
expressions all have {\it reduction number} 0.  Continuing upwards, the {\tt
if} combination 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 {\tt
Debug}.

\newpage
\section{Debug (The Continuation Browser)}
\index{Debug}
\index{Continuation Browser}

Debug, otherwise known as the Continuation Browser, is the debugging tool
which starts when an error occurs and you answer \key{y} to Edwin's question,
``{\tt Debug?}'' When Debug starts, it records all the information necessary
to continue running the Scheme program which caused the error, and lets the
programmer inspect this information -- hence the name ``Continuation
Browser.''

Debug runs in the Edwin buffer {\tt *Debug}, which is automatically displayed
in an Edwin window when Debug starts.  A typical starting Debug display looks
like this:

\begin{scheme}
Subproblem Level: 0  Reduction Number: 0
Expression:
FOB
within the procedure FIB
applied to (10)
\end{scheme}

\noindent This tells us that the error occurred while trying to evaluate the
expression {\tt FOB} while running {\tt (FIB 10)}.  When it starts, Debug always
displays the expression which caused the error; this expression is reduction
number 0 at subproblem level 0.

\noindent
\begin{minipage}[t]{\linewidth}

Several keys have special functions when the cursor is in the {\tt *Debug}
buffer:

\noindent
{\smalltype
\begin{tabular}[l]{p{1in}p{4in}}

\noindent \key{b} & Move to the next reduction. \\

\noindent \key{d} & Move down to the next subproblem. \\

\noindent \key{e} & Pop up a window (buffer {\tt *Eval*} for evaluating
Scheme expressions in the current environment. \\

\noindent \key{f} & Move to the previous reduction. \\

\noindent \key{g} & Move to a particular subproblem/reduction. \\

\noindent \key{h} & Pop up a menu of subproblems to be chosen among in buffer
{\tt *Subproblem-Menu}. \\

\noindent \key{p} & Display a pretty-printed version of the procedure which
created the current environment in buffer {\tt *Procedure*}. \\

\noindent \key{q} & Leave the Continuation Browser, killing its buffer. \\

\noindent \key{u} & Move up to the previous subproblem. \\

\noindent \key{v} & Evaluate a single Scheme expression in the current
environment, prompting for it in the Typein Window. \\

\noindent \key{w} & Browse the current environment in buffer {\tt
*Environment} (using Where, described below). \\

\end{tabular}
}
\end{minipage}

Now, imagine that you are debugging a Scheme program to compute Fibonacci
numbers.  You want procedure {\tt fib} to accept an integer as its single
parameter, returning the corresponding Fibonacci number.  But when you run
{\tt (fib 10)}, Edwin displays the error message {\tt ``Unbound Variable FOO
-- Debug?''}  When you answer by pressing \key{y}, Edwin starts Debug, which
displays the following:

\begin{scheme}
Subproblem Level: 0  Reduction Number: 0
Expression:
FOB
within the procedure FIB
applied to (10)
\end{scheme}

This tells you that the error occurred while trying to evaluate the expression
{\tt FOB} while running {\tt (FIB 10)}.  Now suppose this error confuses you,
because you don't recognize the variable {\tt FOB} -- after all, you were
running your Fibonacci number program, which looks like this:

\begin{scheme}
(define (fib n)
  (if (< n 2)
      1
      (+ (fib (- n 1))
	 (fob (- n 2)))))
\end{scheme}

(It turns out that you made a typo, entering ``fob'' where you wanted ``fib,''
but you haven't noticed this yet.)

You wonder what Scheme was doing (evaluating) when it encountered {\tt fob},
so you press \key{u}, telling Debug to move up one subproblem level.  The {\tt
*Debug} buffer changes to:

\begin{scheme}
Subproblem Level: 1  Reduction Number: 0
Expression:
(FOB (- N 2))
within the procedure FIB
applied to (10)
\end{scheme}

Still confused, you go up one more subproblem level by pressing \key{u} again:

\begin{scheme}
Subproblem Level: 2  Reduction Number: 0
Expression:
(+ (FIB (- N 1)) (FOB (- N 2)))
within the procedure FIB
applied to (10)
\end{scheme}

But now, you notice that this code looks suspiciously like your Fibonacci
procedure.  Returning to the Edwin buffer where you defined it, you see your
typo, correct it, and try {\tt (FIB 10)} again.  Now, the Fibonacci procedure
works.

In this imaginary scenario, only the \key{u} command was needed to solve the
problem, but let's try \key{h} to see a summary of evaluation history, anyway:

{\scriptsize
\begin{verbatim}
Sub Prb.      Procedure Name    Expression

0   0                    FIB    FOB
1   0                    FIB    (FOB (- N 2))
2   0                    FIB    (+ (FIB (- N 1)) (FOB (- N 2)))
3                               (WRITE-LINE (EVAL-WITH-HISTORY (WITH-INPUT-FROM
4   0                           (WITH-OUTPUT-TO-CURRENT-POINT (LAMBDA () (WRITE
5   0         ^G-INTERCEPTOR    (LET ((VALUE (CALL-WITH-CURRENT-CONTINUATION (L
6        COMMAND-READER-LOOP    (LET ((VALUE (CALL-WITH-CURRENT-CONTINUATION (L
7        COMMAND-READER-LOOP    (BEGIN (LET ((VALUE (CALL-WITH-CURRENT-CONTINUA
\end{verbatim}
}

The first column in the history lists the subproblem level of each Expression,
and the second column lists the reduction number.  The Procedure Name column
lists the procedure in which the Expression appears.

In this history, subproblems 0, 1, and 2 give the evaluation history of the
{\tt fib} procedure.  In order to evaluate subproblem 2, Scheme had to
evaluate subproblem 1, and in order to evaluate subproblem 1, Scheme had to
evaluate subproblem 0, which caused the error.  Subproblems 3 through 7 are
parts of the history of the Scheme Read-Eval-Print (REP) loop, which is
responsible for interpreting your typing, evaluating it, and displaying the
results.  While debugging your programs, you can ignore the subproblems for
the Scheme REP loop.

\newpage
\section{Where (The Environment Browser)}
\index{Where}
\index{Environment Browser}

Where, the Environment Browser, is the Scheme debugging tool for examining and
changing variables in environments.  Where is particularly useful for
examining the state of a Scheme program when an error occurs, because it can
display the current values of all variables in the program's environments.

Start Where from the Debug debugging tool by pressing \key{w} while the cursor
is in the {\tt *Debug} buffer.

The buffer in which Where starts shows the environment which was being
examined in Debug, and is called {\tt *Environment}.  An {\tt
Environment-Browser} buffer is created for each environment being browsed with
Where.  All Where buffers display ``{\tt (Environment-Browser)}'' on the mode
line, indicating their major mode.

These keys have special functions when the cursor is in an {\tt
Environment-Browser} buffer:

\noindent
\begin{minipage}[t]{\linewidth}
{\smalltype
\begin{tabular}[l]{p{1in}p{4in}}

\noindent \key{e} & Pop up a window (buffer {\tt *Eval*}) for evaluating
Scheme expressions in the environment being browsed. \\

\noindent \key{f} & Browse the environment which is the value of the variable
that the point is on. \\

\noindent \key{p} & Browse the parent environment of this environment,
creating a new {\tt Environment-Browser} buffer. \\

\noindent \key{q} & Leave the current {\tt Environment-Browser} buffer,
killing it. \\

\noindent \key{v} & Evaluate a single expression in the current environment,
prompting for it in the Typein Window. \\

\noindent \key{w} & Browse an environment, prompting for it in the typein
window and creating a new {\tt Environment-Browser} buffer. \\

\end{tabular}
}
\end{minipage}

\newpage
\section{Trace}
\index{Trace}

Trace is a family of debugging procedures for following the usage of
particular procedures in a Scheme program.

\begin{entry}{%
\proto{trace-entry}{ procedure}{procedure}
\proto{trace-exit}{ procedure}{procedure}
\proto{trace-both}{ procedure}{procedure}
\proto{trace}{ procedure}{procedure}
\proto{untrace}{ }{procedure}
\proto{untrace}{ \var{procedure}}{procedure}}

{\tt Trace-entry} causes Scheme to display a message whenever \var{procedure}
is entered.  {\tt Trace-exit} causes Scheme to display a message whenever
\var{procedure} returns.  {\tt Trace-both} performs both {\tt trace-entry} and
{\tt trace-exit}.  {\tt Trace} is the same as {\tt trace-entry}.

{\tt Untrace} removes any trace messages set for \var{procedure}.  With no
argument, it removes traces from all procedures.
\end{entry}

{\small
\begin{verbatim}
==> (define (factorial n) (if (< n 2) 1 (* n (factorial (- n 1)))))
FACTORIAL

==> (trace-entry factorial)

==> (trace-exit factorial)

==> (factorial 4)
[Entering <#[COMPOUND-PROCEDURE FACTORIAL] 3>]
[Entering <#[COMPOUND-PROCEDURE FACTORIAL] 2>]
[Entering <#[COMPOUND-PROCEDURE FACTORIAL] 1>]
6

==> (untrace factorial)

==> (trace-exit factorial)
\end{verbatim}
\newpage
\begin{verbatim}
==> (factorial 4)
[1 <== <#[COMPOUND-PROCEDURE FACTORIAL] 1>]
[2 <== <#[COMPOUND-PROCEDURE FACTORIAL] 2>]
[6 <== <#[COMPOUND-PROCEDURE FACTORIAL] 3>]
[24 <== <#[COMPOUND-PROCEDURE FACTORIAL] 4>]
24

==> (untrace factorial)

==> (factorial 5)
120

==> (trace-both factorial)

==> (factorial 2)
[Entering <#[COMPOUND-PROCEDURE FACTORIAL] 2>]
[Entering <#[COMPOUND-PROCEDURE FACTORIAL] 1>]
[1 <== <#[COMPOUND-PROCEDURE FACTORIAL] 1>]
[2 <== <#[COMPOUND-PROCEDURE FACTORIAL] 2>]
2

==> _
\end{verbatim}
}

\newpage
\section{Break}
\index{Break}

Break is a family of debugging procedures for causing particular procedures in
a Scheme program to stop for inspection whenever they are used.

Unforunately, in this release of the 6.001 course software, Break does
not work under Edwin; it pays no attention to the careful organization of the
Edwin screen, but haphazardly writes its own information over Edwin's.
Therefore, before using Break on any procedures, it is recommended that
you leave Edwin, entering the ``outside'' Scheme REP loop; do this by typing
\ctrl \key{x} \key{z}.

The outside REP loop operates similarly to the Edwin Interaction-mode buffer,
except that no Edwin commands work; use \key{back space} to correct your
typing, and \key{enter} to send your typing to Scheme.  The grey \key{edit}
key will return you safely to Edwin.  We recommend that you stay within Edwin
at all times, except when you want to use Break.

Both Debug and Where work in the outside REP loop, but not exactly the same as
in Edwin.  However, once you learn how to use them in Edwin, the differences
will be easy to overcome.  To start Debug, type {\tt (debug)} at Scheme.

When the outside Scheme detects an error, it displays a message describing the
error, and switches the prompt from the standard {\tt ==>} to {\tt 2
Error->}, but continues as if nothing had happened.  At this point, either
type \ctrl \key{u} to return to the standard prompt, or {\tt (debug)} to start
Debug.

If you start Debug, the prompt will change to {\tt 3 Debug-->}, and Debug will
wait for you to type a one-key command, just like the Debug in Edwin.  To see
a list of the possible commands, press \key{?}.  Type \ctrl \key{u} to stop
the Debug, returning to the {\tt 2 Error->} prompt.

The \key{w} key in Debug starts Where, whose prompt is {\tt 4 Where-->}.
Where accepts one-key commands, as well; press \key{?} to list them.  From
Where, press \ctrl \key{u} to stop Where, returning to Debug.

\newpage
Here is a simple demonstration of the outside REP loop and its debugging
tools:

{\small
\begin{verbatim}
==> foo
Unbound Variable FOO

2 Error-> (debug)
Subproblem Level: 0  Reduction Number: 0
Expression:
FOO
within a MAKE-ENVIRONMENT special form
applied to ()
Debugger

3 Debug--> w
Environment Inspector

4 Where--> c
Frame created by a MAKE-ENVIRONMENT special form
Depth (relative to starting frame): 0
Has bindings:

FACTORIAL = #[COMPOUND-PROCEDURE FACTORIAL]
FIB = #[COMPOUND-PROCEDURE FIB]

4 Where--> _
\end{verbatim}
}

\begin{entry}{%
\proto{break-entry}{ procedure}{procedure}
\proto{break-exit}{ procedure}{procedure}
\proto{break-both}{ procedure}{procedure}
\proto{break}{ procedure}{procedure}
\proto{unbreak}{ procedure}{procedure}}

{\tt Break-entry} causes Scheme to enter a breakpoint whenever \var{procedure}
is entered.  {\tt Break-exit} enters a breakpoint whenever \var{procedure}
returns.  {\tt Break-both} performs both {\tt break-entry} and {\tt
break-exit}.  {\tt Break} is the same as {\tt break-entry}.  {\tt Unbreak}
removes breakpoints from \var{procedure}; with no parameter, it removes
breakpoints from all procedures.
\end{entry}

When a Scheme procedure with a breakpoint is used, it runs normally, except
that Scheme creates a simple REP loop when the breakpoint is encountered
(either on entering the procedure, or leaving it, or both, depending on how
the breakpoint was set).  When the REP loop starts, Scheme displays a message
which includes the actual parameters to the procedure and, for {\tt
break-exit} and {\tt break-both}, the value the procedure is returning.

  The prompt for the REP loop is {\tt 2 Bkpt}.  At
this prompt, any normal Scheme expression is acceptable, including the special
expression {\tt (proceed)}, which tells Scheme to continue running the
procedure as if the breakpoint had never happened.

Here is a simple demonstration of the use of breakpoints in the outside REP
loop:

{\small
\begin{verbatim}
==> (define (factorial n) (if (< n 2) 1 (* n (factorial (- n 1)))))
FACTORIAL

==> (break-entry factorial)

==> (factorial 3)
[Entering <#COMPOUND-PROCEDURE FACTORIAL] 3>]
Breakpoint on entry

2 Bkpt-> (proceed)
[Entering <#COMPOUND-PROCEDURE FACTORIAL] 2>]
Breakpoint on entry

2 Bkpt-> (proceed)
[Entering <#COMPOUND-PROCEDURE FACTORIAL] 1>]
Breakpoint on entry

2 Bkpt-> (proceed)
6

==> (unbreak factorial)

==> (break-exit factorial)

==> (factorial 2)
[1 <== <#[COMPOUND-PROCEDURE FACTORIAL] 1>]
Breakpoint on exit

2 Bkpt-> n
1

2 Bkpt-> (proceed)
[2 <== <#[COMPOUND-PROCEDURE FACTORIAL] 2>]
Breakpoint on exit

2 Bkpt-> (proceed)
6

==> _
\end{verbatim}
}

\section{Error and Breakpoint Procedures}

The procedures Scheme uses for signalling errors and breakpoints are available
for use in Scheme programs.

\begin{entry}{%
\proto{bkpt}{ \var{message} \var{object}}{\exprtype}}

Sets a breakpoint.  Displays \var{message} and \var{object} and enters a
breakpoint read-eval-print loop in the current environment.

\end{entry}


\begin{entry}{%
\proto{breakpoint-procedure}{ message irritant environment}{procedure}}

Invokes a breakpoint, displaying string \var{message} followed by
\var{irritant}, giving the debugger \var{environment}.  Used by the special
form \ide{bkpt}.

\end{entry}


\begin{entry}{%
\proto{error}{ \vari{exp} \varii{exp} \dotsfoo}{\exprtype}}

Signals an error.  Displays all the expressions and creates a debugging
breakpoint.

\end{entry}


\begin{entry}{%
\proto{error-procedure}{ message irritant environment}{procedure}}

Invokes an error, displaying string \var{message} followed by \var{irritant},
giving the debugger \var{environment}.  Used by the special form \ide{error}.

\end{entry}
