MASSACHVSETTS INSTITVTE OF TECHNOLOGY

Department of Electrical Engineering and Computer Science

6.001 – Structure and Interpretation of Computer Programs

Spring Semester, 2007

Project 0

  • Issued: Tuesday, February 6
  • To Be Completed By: Friday, February 16, 6:00pm
  • Reading:
    • Read “6.001 General Information” found at the course web page http://sicp.csail.mit.edu/Spring-2007/generalinfo_st07.htm. Be especially sure to read the 6.001 policy on collaborative work, and to read the detailed information on collaboration on the course web page.
    • Browse the 6.001 Home Page on the web at http://sicp.csail.mit.edu/. All handouts (including this one) can be found there. The web page also contains announcements, Scheme software, projects, documentation, advice on where to get help, and other useful information. You should make a habit of looking at this page at least once a week during the semester. Note in particular that the calendar outlining the schedule of lectures may change during the term as the course content is adjusted, and you should check this regularly to know what is coming.

 

The purpose of Project 0 is to familiarize you with the Scheme programming environment and the resources available to you. The format of this project is different from the more substantive ones you will see later in the term. Those projects will focus on extended experience in creating and testing code, and integrating such code with existing computational frameworks. As a consequence, those projects will take a significant amount of time to complete. This project is really just a warm up, and is intended to get you up to speed on the mechanics of using Scheme and the course resources. This project is mostly reading – getting you to understand the environment you will be using during the term. We expect that this project should not take much time, and while we understand that some of the things we ask you to do seem fairly obvious, we want to make sure you get the mechanics down right. Don't worry; the later projects and problem sets will involve much more extensive thinking and coding!

 

Note that the first part of this material also appears as the Don't Panic handout, which is an introductory guide to using Scheme in 6.001. This can be found on the 6.001 web site, as well.  You may want to consult that manual often over the next few weeks as you are getting used to the Scheme computing system.  The actual work to be done for this project (which is quite small in size) appears under the “Your Turn” tab.

 

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.  As well, if the load becomes particularly bad, we have a backup plan to use some additional space as needed.  And the Lab Assistants are also accessible by email to answer questions – use 6001-help@mit.edu

 

For the Spring 2007 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.

Note that while it is often most effective to work in the lab, so you can ask questions of the LA present, if you are working elsewhere, you can send a note to 6001-help@mit.edu and an LA will respond as soon as they can get to it.  This provides another way to get help, though a direct conversation is typically more effective.

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, there are several options.  You can 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. However, we have had several problems with this option, which stores the file in a binary form.  Instead, we recommend that you click on the File tab, and then on Save Other and then on Save Definitions As Text and then proceed as above.

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 test 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.  Again, we recommend the latter format.

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'. 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. For larger sections of code or text, see below.

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 delete, 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. As we noted earlier, we recommend that you use the

Save Definitions As Text and the Save Interactions As Text options. 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.  When you set this language, you can also click on the “Show Details” tab.  This will allow you to set some parameters, in particular, we recommend that you do NOT use the case sensitive option.

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 a manner where you can control things.  Try the following.  Type these expressions into the definitions window.

(define (square x) (*x x))

(define (foobar x y) (+ (square x) (square y)))

Now press the “run” button to evaluate these definitions.  Now press the “debug” button and go to the “interactions” window and type (foobar 3 4), followed by “enter”.  You are now in a mode where you can carefully step through your code. 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 do this, you will see the evaluation progress until it tries to evaluate “*x”, which of course is an error (in this case a typographical error).  If you use the “Continue” button, the evaluation carries on without interruption, until you press the “Pause” button.  Notice when you reach an error, DrScheme displays information about the error in the interaction window, and also highlights the corresponding spot in the definitions window, so you can see the chain of evaluations that led to the error.  In addition, if you click on the “ladybug” icon, DrScheme will display information that will help you isolate the source of the bug.

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

 


Your Turn

There are several things that you need to do for this part: evaluate some simple Scheme expressions, use the provided tools to manipulate these expressions, and answer some documentation and administrative questions. The answers for all these parts should be submitted electronically on the tutor, using the Submit Project Files button. Remember that this is Project 0; when you have completed all the work and saved it in a file, you should upload that file and submit it for Project 0.   This is a simple project – the goal is primarily to get you used to using the DrScheme system so that you will be agile with this system when we get to the real programming projects later in the term!

 

Some background on interpreters

While this project is mostly intended to get you used to interacting with DrScheme, it is worth reviewing some of the concepts you have seen (or will see) in lecture about interpreters and evaluators.  At an abstract level, our goal is to interact with the machine in order to have it evaluate expressions, or in other words to determine values associated with expressions.  A simple example would be to write a piece of code that computes squares.

 

We can distinguish between the expression that captures this computational idea, and the process by which we apply the idea to different instances.  To capture the idea, we use a definition of a procedure:

 

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

 

How do we get the computer to use this concept?  First, we need to get the computer to “read” this expression, that is, accept each of the characters in the sequence above and convert that sequence into a set of words (sequences of characters separated by spaces, parentheses and other delimiters) that it recognizes.  Next, we want the computer to use the rules of Scheme to interpret this expression—these are the rules about which we have been talking in lecture.

 

In DrScheme we can get this interpretation to happen in two different ways.  First, we can pass the expression directly to the interpreter.  We do this by typing this expression in the bottom (or interpreter) window of DrScheme.  Once we hit “enter”, the system reads the expression, uses its rules of interpretation to decode the expression, and returns the value associated with the expression.  In this case, it would evaluate the lambda expression to create a procedure of one argument, whose body is the (* x x) expression.  Evaluation of the define expression causes the name square to be associated with this procedure object.  If we subsequently use square, as in (square 5), our substitution rules (described in lecture) will lead to a new evaluation in which this procedure is applied to the value 5.  In general, anything we type at the interpretation window is evaluated as soon as we complete the expression and hit “enter”.  A second method is to use the upper (or definitions) window.  Here, we are basically typing characters into a standard editor.  That is, we can correct things, change things, replace things, or add things.  Once we have completed entering our expressions into this window, pressing the Run button will cause each expression in this window to be read and interpreted in order, with the effects or results of that evaluation taking place in the interpretation window.  Typically in this setting, we will be typing definitions into the window, to be saved for later use; we can then use those definitions in the interpretation window to compute specific values.

 

We will explore both of these methods in the exercises below.

 

Part 1: Expressions to Evaluate

If you are working in the lab, you should simply follow the instructions above to login to the system using your Athena ID and password.  Athena login proceeds as normal.  To run Scheme, do

add 6.001
6001-drscheme &

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

In either case, start up DrScheme.  We recommend that you select PLT/Pretty Big as the language choice (use Ctl-L to select a language, or go to the Language tab).

 

Below is a sequence of Scheme expressions. Can you predict what the value of each expression would be when evaluated? Although it may seem like grunt work, please type in and evaluate each expression in the order it is presented.  Do this in the “interactions” window. In this case, evaluation simply means typing in each expression followed by a carriage return or enter.

 

-37 
 
(* 3 4)
 
(> 10 9.7)
 
(- (if (> 3 4)
       7
       10)
   (/ 16 10))
 

Note for the previous example, we have used “pretty printing”. You could just enter this as one big expression as in

(- (if (> 3 4)7 10) (/ 16 10))

However, this can quickly get unwieldy and hard to read.  To get code that is typeset in a uniform manner, you simply need to hit the enter button at the end of each line.  DrScheme will not evaluate the expression until you reach the end of the entire expression (i.e. have an appropriate number of close parentheses).  Also note how DrScheme helps you out by highlighting the entire expression every time you enter a close parenthesis.  Also, note the value returned by this last expression.  Pretty funky, huh?  Now try this one:

(- (if (> 3 4)
       7
       10)
   (/ 16.0 10))

Here are some more expressions to try:

(* (- 25 10)
   (+ 6 3))
 
+
 
(define double (lambda (x) (* 2 x)))
 
double
 
(define c 4)
 
c
 
(double c)
 
c
 
(double (double (+ c 5)))
 
(define times-2 double)
 
(times-2 c)
 
(define d c)
 
(= c d)
 
(cond ((>= c 2) d)
      ((= c (- d 5)) (+ c d))
      (else (abs (- c d))))
 

 

When you get to this stage, you should have a series of expressions and their values in the interactions buffer of DrScheme.  You need to save this away as a file. Save this file using a name that describes the content (e.g. project0_09_10.scm). In particular, use File then Save Other then Save Interactions links.  Saving in this manner will allow you to load that file into a fresh version of DrScheme and edit it to add annotations or other comments. 

 

Now, close DrScheme and restart it.  Open the file you just saved.  Using the mouse, outline the region of your interactions, and then using the mouse, click on Scheme and then on Comment out with semicolons.  Notice what this does.  Scheme’s protocol is to use a semicolon (;) as the beginning of a comment, and the remainder of that line is not evaluated.  For example:

 

nothing on the following line is evaluated
; (+ 1 2)  this is a comment

in the following line, the addition expression is evaluated, but nothing after
(+ 1 2)  ; this is a comment

and multiple semicolons don't matter
;;; this is a fine comment also

 

What this means is that anything following a semicolon is not seen by the Scheme interpreter, and is simply provided as textual comments for the reader.

 

In this version of the file, you can now add your own comments, using semicolons to begin each line.  Add some appropriate comments to your expressions and save the file.

 

Remember that your real-life flesh and bones tutor will be reading and grading your project. Commenting your code and otherwise explaining your work is an important part of your project submission -- it is a good habit to get into NOW! For example:

 
;;;
;;; The following test cases explore the evaluation of simple expressions.
;;;
 

Part 2: Using definitions

Now let’s try using the definitions window of DrScheme.   Start up a fresh version of DrScheme, and type some expressions into the interaction window, just as you did above.  Now, place the cursor in the definitions window (e.g. by placing the mouse over that window and clicking), and type the following expressions:

 

(define square (lambda (x) (* x x)))
 
(define abs (lambda (x) (if (< x 0) (- x) x)))
 
(define my-test (lambda (x y)
                  (if (> x y)
                      (+ (abs y) (square x))
                      (+ (square y) (abs x)))))
 
(my-test 5 -3)
 
(my-test -5 2)
 

Note that the first three expressions are definitions, assigning a name to a procedure (you will see what this means in lecture on September 12th).  The latter two expressions are simply combinations.  Now use the mouse to press the Run button.  Note what happens.  All of the previous output in your interactions window has disappeared (this is why we had you save it first).  In DrScheme, pressing the Run button always causes the environment of the evaluator to be reinitialized, and the expressions in the definitions window to be evaluated.  Also note what is printed out in the interactions window – any values associated with expressions are printed out, in order.

 

Now, we would like to create one file, which contains the evaluations from Part 1, with the definitions from Part 2.  There are several ways to do this, here is one.  An easy one is to use the mouse to highlight the values that resulted from each expression’s evaluation, and cut and paste those values below the expression in the definitions window (commenting out by use of a semicolon). Cut and paste is done by: selecting the text (e.g., using Ctl-a) and making a copy (e.g., using Ctl-c), which you then insert by placing the mouse at the desired point and using Ctl-v. This puts all of your work in one place, where you can add appropriate comments and then save. This now becomes a file that you can submit as your project 0.

Part 3 (Optional): Real printing

If you want to print your a hardcopy of your work (at the end of this project), you will need commands to do this. These commands are issued from an interface to the operating system. If you logged in at the 6.001 Lab, an xterm window opened up. Inside that window, you can issue commands for printing. To see what the printer queue looks like, use lpq (this automatically selects the first available printer among those physically in the lab).

To print, assume that you have saved your work in ~/u6001/work/project0.scm. Then go to xterm and type the following

cd ~/u6001/work   (to connect to this directory)
ls                (make sure the file you want is in fact there)
lpr project0.scm
lpq               (to check the status of your print job)

To remove a job, use lprm job-number.

If you are working on Athena (as opposed to in the 6.001 Lab), you may use cview printers to get a list of available printers. This can be done from an xterm window. To queue a print job, use

lpr -P printername filename

or if you prefer

 
lpr -P printername2 filename

which will print things two-sided rather than single-sided.

Part 4: Documentation and Administrative Questions

Explore the 6.001 webpages to find the answers to the following questions. Add your answers to these questions to your project 0 solutions write-up.

 

  1. Referring to the course policy on collaboration, describe the policy on the use of “bibles.”

 

  1. List three people with whom you might collaborate on projects this term. You are not required to actively collaborate with these people, we just want you to start thinking about what collaboration means in this course.

 

  1. Locate the list of announcements for the class. What do these announcements say about recitation attendance during the first week of classes?

 

  1. What are the three methods for controlling complexity described in the learning objectives section of the course objectives and outcomes? List one example from each category.

 

  1. If you go to the online version of the textbook, what year was this version published?

 

  1. What are the dates for the two quizzes this term?

 

Submission

Once you have completed this introductory project, your file should be submitted electronically on the tutor, using the Submit Project Files button. Remember that this is Project 0; when you are have completed all the work and saved it in a file, upload that file and submit it for Project 0.

Congratulations! You have reached the end of Project 0!