DON'T PANIC

An Introductory Guide to the 6.001 Computer System

Edition 2.1

August 27, 2006

by Eric Grimson

 

Table of contents

The 6.001 Lab and Scheme Implementations

Important Information

Please make special note of the following points:

  • If you are working on a project (as opposed to an online problem set) read the entire project BEFORE you begin your work. Often, a question you may have will be explained in a later section of the project, and this will provide clarity before you start answering questions.  As well, reading the entire project will give you a sense of the full range of problems you will be expected to solve, so you can plan your time accordingly.
  • PLEASE browse the 6.001 home web page regularly. It contains course handouts, announcements, Scheme software, documentation, advice on where to get help, and other useful information. It will also be the location where corrections to projects are posted, so you will want to check it regularly. The page is located at http://sicp.csail.mit.edu/.

Scheme Implementations for 6.001

The 6.001 Lab (34-501) is a space that is provided to give you an opportunity to work on your projects and problem sets, with access to computational and personnel resources. You'll find it convenient to work here because the Lab Assistants are available to help you, and you can share the warmth and camaraderie of your classmates while you work on problem sets and projects. If you use one of the 6.001 lab machines, you will automatically have access to the Scheme programming environment, as well as a web browser for linking to information on the course web site.  If you want to bring your own machine, the space is set up to support that, and again you will have access to the helpful Lab Assistants.  If you want to use your own computer, the 6.001 web site provides implementations of Scheme for a variety of platforms. See the course web page for software and installation instructions.  Note that you will be sharing this lab space with 6.004 students and students taking the new introductory courses to EECS.  We have tried to stagger due date times so that the lab is not overloaded, but you may still want to plan your time in the lab in advance.

 

For the Fall 2006 term, we are going continue our experiment, in which we use DrScheme as the base language for the course, as opposed to MIT Scheme, which has been used for many years prior to this.  As a consequence, there may be the occasional “glitch”, as legacy software may collide with minor language differences between the implementations.  Please bear with us if this happens.  Nonetheless, we expect to use DrScheme as the principal programming environment, and the 6.001 Lab is set up to support interactions using the DrScheme system.  If you choose to use one of the other versions of Scheme (such as MIT Scheme) you may, but we don’t guarantee that everything is consistent between the different versions.

 

The problem sets and projects are designed so that you can freely move from your home machine to the lab; for example you might start a project at home, then spend some time debugging it in the lab where the Lab Assistants can help you, and finally finish things up at home.

6.001 is not officially supported on Athena. The implementation of Scheme on Athena that runs on Linux machines should be compatible with other 6.001 implementations, although we do not guarantee that it can run all the projects.  Other versions of Scheme on Athena are likely not to be compatible with 6.001.

The lab machines are set up as Athena machines in the following manner, however.  They will automatically save all your work in your Athena home directory (in ~/u6001/work by default).  You can perform most Athena operations on these machines.  Please note that this is not a supported Athena platform, so don't bug IS&T employees with problems.  Send all bug reports, comments, and questions about the lab setup to 6001-lab@mit.edu.

Lab Location

The 6.001 lab is located in room 34-501. The easiest way to get there is by the elevator in building 36. Since the door outside the lab has an electronic lock, you will want to bring along the combination, which was given out in lecture and in recitation. Make sure you also bring your textbook, this guide, and a copy of the project if that is what you are planning to work on.

Lab Assistants

Lab Assistants (LAs) are an integral part of the 6.001 lab. They make sure that everything runs smoothly by maintaining hardware and fixing certain problems so that the lab is available to as many students as possible. However, LAs are not in the lab just to maintain hardware; their primary purpose is to offer you assistance on problems that you encounter while trying to do the projects and problem sets. If you get stuck, check the blackboard for the help queue status. If the queue is on, write the name of your machine in the next available space. If the queue is off, look for an LA walking around or using a computer to assist you.

Don't think that you must have a major problem to ask for help. Although the LAs are not there to write your code for you, they can assist you when you stop making progress on your problem set. The best way to make sure that all of your questions get answered is to get to the lab early. The night before the project or problem set is due is not a good time to ask an LA to explain a complicated issue. Instead, come to the lab early or make an office appointment with your recitation instructor or TA if you begin having difficulties. The lab will be very busy the night before the project is due.

If you notice hardware problems, you should contact one of the LAs on duty. If one is not in the room, place a note by the computer that explains what you think the problem is and when you noticed it. If an extreme problem occurs (like a fire) when an LA is not around, contact someone at the equipment desk located outside of the lab.

The Scheme of Things

The 6.001 text book describes how to program in Scheme but it gives none of the details of how these programs are entered into the computer, tested and changed. This section describes the basic things that occur when you use the computer to write and evaluate code written in Scheme.

Flow of Control

Control of the computer begins with you. You can direct the computer by moving the mouse or by typing at the keyboard. These keystrokes and mouse actions are first inspected by a program called the "window manager" to see if you are requesting that it perform some operation. The window manager then passes your keystrokes to the application that has the focus (the highlighted window has the focus). Ordinarily, the only application that you see is the DrScheme window, a user interface for entering code, editing files, and running Scheme programs.  You will usually want DrScheme to have the focus. You can tell the window manager to give DrScheme the focus by clicking the mouse on the border surrounding the DrScheme window. This should make the border a different color (whatever the default is for your machine – typically this will turn it from a pale blue to a dark blue) and allow DrScheme to receive your keystrokes.

DrScheme acts, in part, as a text editor, that is as a program that allows you to compose text (programs, memos, letters, books, etc.) much as you would with a typewriter. Unlike a typewriter, DrScheme will allow you to modify text that you have already written so that you don't have to type it in all over again. DrScheme also allows you to work on more than one piece of text at a time, each in its own buffer.   Thus, you can open files you have previously saved by using the mouse to click on the File tab, and then on Open, or by simply typing Ctl-o (that is, the “control” key followed by the “O” key).  In either case, use the mouse to select the file you want from the list shown, or click on the arrow next to the Look in window to select some other directory in which to find your file.  Note that there is also an Open recent option, which shows you links to files you have recently opened.  Clicking on one of these will allow you to open a recently visited file.

To save your files, you can either again click on the File tab, and then on Save Definitions or Save Definitions As.  In the former case, the file will save as the latest version of whatever name the file had when you opened it.  If the file is a new one that you have created in DrScheme, the system will prompt you for a location and name under which to store the file.  In the latter case, you are explicitly asking to save the file under a new name.  Now, why does the command say Save Definitions? When you first start up DrScheme, you will notice that it provides you with a window containing two parts.  The upper part is the “definitions” window.  This is where you will typically enter your code – each subprogram is typically a definition, as you will discover in lecture.  The lower part is the interaction window.  This is where you will enter expressions that you want to evaluate, and where the Scheme interpreter will print out results associated with evaluating expressions.  For your projects you will often want to save examples of your code running on tests cases.  You can do this by opening the File tab, and the clicking on Save Other followed by Save Interactions or Save Interactions As or Save Interactions as Text.  The latter is particularly useful, as we will see later in this handout.

Be sure to save your files before quitting.  Otherwise your work will be lost.  Note that if you try to exit DrScheme without having saved all of your files, it will prompt you about this.

Once you have written your programs using DrScheme, you can instruct DrScheme to send them to the Scheme interpreter and record the results. You can do this by clicking on the Run tab at the top of the window.  You can also (as we describe below) enter expressions directly into the interaction window, such as for example evaluating your procedures on different input values.

Standard Conventions

We have already told you enough about communicating with the window manager to get you started on 6.001. Obviously, much more will be said about communicating with DrScheme and thus the Scheme interpreter.

Normally, pressing an alphanumeric key tells DrScheme to insert a character in the current buffer. However, you can press special keys in combination with normal keys to give DrScheme commands. Most of these keys are now standard parts of keyboards.  Thus, the Control key is located next to the `a' key. It works like the shift key meaning that you should hold it down while pressing another key. For example, when we say C-x we mean: hold down the key labeled CTRL while you press `x'. The Meta key also works like the shift key. If this is not explicitly labeled as Meta then it will typically be the Alt key, located to the left of the keyboard. When we say M-x, we mean hold down the Meta key while you press `x'. Sometimes it is necessary to hold down both CTRL and META at the same time. When we want you to do this, we will say C-M-x. Note that many of the control sequences follow standard conventions of other text editors and window based interfaces (e.g. C-o to open a file, C-s to save a file, C-w to close a file, etc.).

Logging In and Loading Project Code

Logging In

If you are in the 6.001 Lab, use your Athena username and password to log in. If you don't have an Athena account yet (e.g., because you have Special Student status, are cross-registered, etc.), go to the Athena Accounts office at building N42's front desk. Their phone number is 253-1325 and their hours are:

        Monday, Wednesday, Friday ......................         2:00pm -  5:00pm
        Tuesday, Thursday ..............................                9:00am - 12:00pm

Athena login proceeds as normal.  To run Scheme, do

add 6.001
6001-drscheme &

If you have downloaded DrScheme onto your home machine, the installation should have placed an icon for starting DrScheme on your desktop or as PLT Scheme under your Programs icon.

Loading Problem Sets

Normally, you will just use the online tutor to deal with problem sets.  You may find it convenient, however, to use your own Scheme environment to experiment with your answer.  In this case, you should be able to cut-and-paste your answer from your Scheme environment into the tutor's window for submission. In those cases where a problem set has supporting code, we will provide a link from the tutor page that will enable you to access that code.

Loading Project Code

Projects will involve more extensive coding that problem sets, and for this we will provide a mechanism for letting you get access to that code.  The easiest way to do this is to open a web browser, go the course web page (http://sicp.csail.mit.edu/), and find the code on the Projects page.  If you save versions of the code for each project in your Athena directory, you can then download onto the machine you are using in the Lab and use them.

If you are working on your own computer, and starting a new project, you'll need to download the project files to the correct directory on your own machine.

Editing Your Code

As noted above, DrScheme normally displays two subwindows:  the top window is for entering definitions that you plan to save in a file (or for editing an existing file), the bottom window is to display interactions with the Scheme interpreter.  You can hide (or expose) the definitions subwindow by typing C-d, and you can hide (or expose) the interactions window by typing C-e. Note that if you open a new file, you will get a new DrScheme window containing a copy of that file, displayed as a single subwindow.  If you click on the Run tab, the window will be split into two, displaying an interaction window at the bottom.

Loading a File

In order to modify a file or to create a new one, you must first instruct DrScheme to "open" the file. As noted, you can do this by clicking on the File and Open tabs, or by simply typing C-o and finding the file you want in the displayed directory structure.

Editing A File

Inserting Letters and Moving The Point

Once you are in the buffer you want to edit, typing characters causes text to be inserted into the buffer at the point (the little blinking vertical line), but nothing is overwritten. If you would like to delete a character or two use Back space to remove the character to the left of the point and Delete to delete to the right of the point. If you want to delete a whole line or a larger section of code, use the mouse to find the start of the section, then click the left button and hold it down while you move the mouse to the end of the section of code in which you are interested. This will highlight the entire section of code, which you can then either delete (using the Delete key) or cut (by either using the “Edit” and “Cut” tabs, or typing C-x) or copy (by either using the “Edit” and “Copy” tabs or typing C-c)  Note that “cut” means you will remove the entire section  in a form in which it can be retrieved, while “copy” means that a version of the code is saved in a form in which it can be retrieved but the initial code remains.  In either case, you can move the mouse to a new location, left click to insert the cursor, and then insert the saved text by either using the “Edit” and “paste” tabs, or typing C-v. If you make a mistake, you can often revert by typing C-z.

The cursor motion keys (the keys with triangles on them) allow you to move the point to a new location and begin inserting characters there.

Undoing Mistakes

If you make a mistake while editing your code, type C-z. In many cases DrScheme can undo the previous few edits that you have made, allowing you to restore your previous state.  This can also be done using the Edit and Undo tabs. Consecutive repetitions of C-z will cause DrScheme to undo older and older changes. Any command other than an undo breaks the sequence.

If you really mess up, it is sometimes desirable to restore the buffer to the way it was the last time you saved it. You can do this using the File tab followed by the Revert tab.  Note that DrScheme asks you if you really want to revert before doing this.

Using a Region to Copy or Move Text

If you want to copy or move a whole line or a larger section of code, use the mouse to find the start of the section, then click the left button and hold it down while you move the mouse to the end of the section of code in which you are interested. This will highlight the entire section of code, which you can then either delete (using the Delete key) or cut (by either using the Edit and Cut tabs, or typing C-x) or copy (by either using the Edit and Copy tabs or typing C-c)  Note that “cut” means you will remove the entire section  in a form in which it can be retrieved, while “copy” means that a version of the code is saved in a form in which it can be retrieved but the initial code remains.  In either case, you can move the mouse to a new location, left click to insert the cursor, and then insert the saved text by either using the Edit and Paste tabs, or typing C-v. If you make a mistake, you can often revert by typing C-z.

 

Saving A File

You should save your code files periodically so that if the computer crashes, you do not lose all your work. This is done by typing C-s. Also, be sure to save your files before you log out or quit the machine. We strongly recommend that you save your files with the .scm  extension, as this will enable DrScheme to recognize this as a Scheme file.  DrScheme only allows one file to be loaded into the “definitions” window at a time.  This means that you will need to make all your additions to the project code to a version of the file we provide.  In order to keep things clean, we recommend that you save versions of your code file under different names (e.g.  project1_month_day_version.scm as in project1_09_13_1.scm) so that you can always revert back to a prior version if you get messed up.

Managing Your Files

Generating all these files means that we will need some way to manage them. We recommend that you create a directory explicitly for your 6.001 files.  That way, when you use the Open tab in DrScheme, you will be able to see all of the files available to you.  Note that using the  scm” suffix, as in  filename.scm, will ensure that when DrScheme opens the file, it does so as a Scheme file.

Running and Testing Your Code

Evaluating Code

There are several different ways to interact with DrScheme’s evaluator.  The first is to write definitions of procedures and constants in the “definitions” window (these are typically expressions that you will want to save as a filename.scm file for future use).  When you press the “Run” button at the top of the DrScheme window, all of the definitions and other expressions in this window are evaluated by the Scheme evaluator, and are available for use in the “interaction” window (the bottom of the two subwindows).  This leads to the second way with which to interact with Scheme.  You can also type expressions in the interaction window, such that when you press the “enter” key, the expression is evaluated and its value is returned and printed in the interaction window.

We suggest that you develop a coding discipline, in which you keep all of your code in the “definitions” window, and use the “interaction” window for running test cases or other evaluation of your code.  Note that whenever you hit the Run tab, however, the environment associated with the “interaction” window is re-initialized so that values associated with any expressions evaluated previously in the “interaction” window are lost.  Thus, you may find it occasionally useful to create a definition in the “interaction” window, in order to be able to use the state of previous computations as a basis for further testing.  If you choose to do this, you should be sure to copy your new definitions into the “definitions” window before saving.

Your “interactions” window is also very valuable, especially for keeping a record of your test cases and evaluation of code that you write.  We recommend that you save these interactions (by hitting File then Save Other then Save Interactions or Save Interactions As) in a separate file.  When you are ready to submit your project, you can create a single file, interspersing your saved interactions with your saved code, for submission to your TA.

One major difference between MIT Scheme and DrScheme is that the latter provides a series of different versions of the Scheme language for use.  For the purposes of 6.001, we recommend that you select PLT/Pretty Big as the option.  You can do this either using the Language tab, or by typing Ctl-L.

Debugging

When testing your code you will find that often it doesn't work as expected. Sometimes your code will stop dead in its tracks and produce an error message on the screen, sometimes it will return an incorrect result, and sometimes it won't return anything at all because it is caught in an infinite (or at least an unreasonably long) loop. These mistakes in your code are called bugs and getting rid of them is an art-form known as debugging.

The first kind of bug is often the easiest to fix. Sometimes you have just misspelled a variable or procedure name, or have misplaced a parenthesis. Usually your typos are obvious when the computer points them out to you. At other times the computer screams at you when your program is trying to do an illegal operation (like trying to add two procedures!). In cases like this, it is useful to enter the debugger and see what you can learn about the bug. Questions you should ask yourself are:

  • How did my procedure get into this state?
  • Do any variables have values that they clearly should not?
  • Are all the procedures that I use in this procedure working correctly?
  • Do I have the arguments in the correct order?
  • Am I using the correct variables?
  • Does my procedure have a logical error?
  • Did I remember to evaluate all the changes that I made?
  • Did I do anything that would cause any old definitions to still be around?
  • Did I write this code?

These are useful questions to ask no matter what kind of bugs you have. Remember that even if your procedure seems to work with one or two test cases, you could still have errors in it. Make sure to test the boundary conditions (if you don't your TA will). For example, maybe you forgot to test your absolute value procedure with the number zero. Question: how many fence posts do you need to buy to make 100 feet of fence with a fence post every 10 feet? If you quickly answered 10, then you are especially susceptible to fence-post errors. Otherwise, see how many of your friends will fall for this one.

Only experience can help you become a master debugger. However, good discipline in trying to debug code can be very valuable experience.  Fortunately, DrScheme comes with several built in tools to help.  The first is the Debug button at the top of the window.  If you press this button, DrScheme will enter a mode in which it will evaluate expressions in the “definitions” window in turn.  If you use the “step” button, DrScheme will step to and execute the next evaluation, putting a small marker at the current point, and in many cases displaying the subexpression being evaluated at the top of the window next to the buttons.  This will let you walk your way through the code to spot where a problem may be occurring.  If you use the “Continue” button, the evaluation carries on without interruption, until you press the “Pause” button.

If the debugger doesn't give you the needed information, sometimes it is useful to put a display or display expression into your code to gather information. Also, you may make your procedures robust so that when they get illegal values, they give you information that the debugger wouldn't give you. These two methods are especially useful with the never-ending-procedure variety of bugs.

A more useful way to gather information is to use the procedure error. error displays its first argument which should be a string and then displays the rest of its arguments which are any objects of special concern to debugging. Then you are asked if you would like to enter the debugger. Here is an example:

(define (cube x)
  (if (not (number? x))
      (error "Argument should be a number instead of" x)
      (* x x x)))
 
(cube 'hi)
;Argument should be a number instead of hi

 

In this latter case, not only will you get an error message in your “interaction” window, but the corresponding piece of code in the “definitions” window will be highlighted (in pink) so you can see where it occurred.

 

Another handy tool provided by DrScheme is a syntax checker.  Pressing the “Check Syntax” button will cause DrScheme to scan through your definitions window, looking for illegal expressions.  Note that it won’t catch errors in which an incorrect value is passed in as an argument, since those occur at run time.  But it will catch errors in which expressions are incorrectly formed.  For example, if you type the following into your definitions window

 

(define square
   (lambda (x) (* y y)))

 

then the syntax checker will highlight the two variables “y” in red, in this case to indicate that these are not bound variables (i.e. they do not correspond either to a variable in the parameter list of the scoping lambda, nor are they bound by a top level definition elsewhere in the window). Checking syntax can often spot typos or other errors for you.

 

Note that if you want to find a particular definition to edit, you can use the tab labeled (define …) to get a list of all your definitions, from which you can select the one you want.

 

One of the best ways of debugging code is to get a lab assistant to help you. Even if they can't immediately find your bug, they can probably tell you whether what you are trying to do is a good idea. Another powerful debugging technique is to completely rewrite some of your code in an improved way. It is often easier to avoid bugs than to find them so use a clear design instead of clever or tricky code that is sure to fail during the next waning crescent. However, if you enjoy debugging code, feel free to make lots of mistakes so that you can find them later.

Using On-Line Documentation

DrScheme’s web site includes a number of useful sources of online documentation.  We recommend that you explore these to see what is available.

Printing

Printing A Buffer

You can print out your definitions window by selecting File followed by Print Definitions, or by simply entering Ctl-P.  Similarly, you can print out a copy of your interactions window by selecting File followed by Print Interactions. Remember to get your print-out right away or it may get lost in a huge heap of paper. The header has the machine name on it.

Alternatively, from a top level window, use the Linux commands to print a file:

cd ~/u6001/work
lpr project1.scm

will for example connect to your work directory, then print out the Scheme file (note the .scm extension) titled project1.

Making A Transcript

The easiest way to get a transcript is to save a copy of your “interactions” window.  You can insert comments or other annotations into this file, to help your TA understand your work.  For example, you should remove the test cases that you do not wish to keep and place your name and other information including the problem set number and the exercise at the top. You might also want to make special comments about some of the test cases. When you are done with the entire project, you can print out this buffer. It's a good idea to comment the transcript after each problem, while the details are still in your mind. Incrementally building your final transcript takes less effort than doing it all at the end. Note that if you want to edit the file, it is easiest to use the Save Interactions as Text option, and then Open this file in a new buffer.  You can then edit this using normal text editing commands, such as inserting comments into your examples.

Logging Out and Giving Feedback

Logging Out

To logout, make sure your have saved all of your files and then type Ctl-w. If you have forgotten to save any of your buffers, DrScheme will give you a chance to do it now. If you still don't save all of the buffers, DrScheme will ask one more time just to be sure. 

Feedback

If you find any bugs, or problems dealing with the lab, send mail to:

6001-lab@mit.edu

You can send email to the entire 6001 staff via the address 6001-staff@csail.mit.edu. For comments specific to the course you can send mail to 6001-lecturers@csail.mit.edu.

DrScheme won't respond to anything I type!

One cause of this is that DrScheme is not receiving any keystrokes from the window manager. If this is the case, the border around DrScheme will be light blue instead of dark blue. To fix this problem, click the left mouse button when the cursor is in the border of the DrScheme window.

How Can I Reach a "Steady State?"

Often times you will lose and just want to return to some sort of steady state so that you can continue to do your work. If all of a sudden you do something that seems to trash half of your buffer, stop and relax. The first thing that you should try is C-z, the undo command. If this fails to do any good, you might try performing a yank using C-v. If neither of these seems to work, use the Save As command, which will allow you to save the file under a different name. Now you can load up the old version. Next, visually compare these two buffers to see if you can recover any recent changes. You might also want to save your buffers often so that you can always restore to a steady state by doing a revert. If your problem is that DrScheme does not seem to be evaluating things properly, try hitting the Stop button. For really drastic problems, try saving all of your buffers that don't seem screwed up and logging out. When you log back in, things should be back to normal. If this doesn't help then it is time to talk to an LA.

 

Debugger

When an error occurs in your code, you will often see a bug display in the interaction window that highlights the type of error encountered.  A simple example helps highlight some of the key aspects of DrScheme’ debugger:

 

(define square (lambda (x) (* y y)))
 
(define my-fcn (lambda (x y) (+ (* x x) (square y))))
 

Now suppose we enter

 

(my-fcn 3 5)

 

followed by an “enter”.

 

This causes an error, which is highlighted with the bug message “reference to undefined identifier: y”, telling you what was the immediate cause of the error.  It also, however, shows you in the definitions window where this error occurred (try this to see for yourself).  Specifically, DrScheme shows an overlay of a set of red arrows indicating the sequence of subexpression evaluations that led to the error – in this case, it shows that while evaluating the body of my-fcn, an error occurred, specifically the call to the body of square.  This can be useful in unwinding the stages of computation to identify the source of the error.

 

This can also be found by using the Debugger directly.  Try entering the three expressions above into a definitions window, and then press the Debug button.  Now, “step” through the evaluation.  Note how for the last expression, the debugger shows you each step, using a green marker to indicate the stage of evaluation (placed at the beginning of a subexpression as it enters the subcomputation, then placed at the end of the expression when that subcomputation is completed and printing at the top of the window the actual expression and returned value).  Walk through this example to see the stages of  computation, and how the debugger lets you walk through these to isolate the error.

 

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 the reduction for the following expression:

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

This is because the entire subproblem of the if combination 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 combination.

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 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 debugger.