Programming with
Data Structures and Algorithms

Lab 1

Get Acquainted with DrScheme

For this lab and all others you will be pair programming. Both partners will need to complete the first part. After that, it doesn't matter which partner is logged in.

A programming environment is a workspace in which programmers create and run programs. Our programming environment, DrScheme, is the work of researchers (many of whom are students) at several universities, including this one.

Task: At the shell prompt, type drscheme &.

Note: The & tells the shell to open DrScheme in the background. If you don't include &, DrScheme will run in the foreground. This means you won't be able to use the shell until you close DrScheme. If you ever forget to use &, you can switch to the shell, press Ctrl+z to suspend DrScheme, and then run bg (or simply &) to move the DrScheme process to the background.

A window will appear with a patriotic lambda and a progress bar while DrScheme loads up various extensions. Soon this window will disappear and a large window will replace it. The top half of this large window is called the definitions window, and the bottom half is called the interactions window. When you click on the "Run" button (top right), DrScheme will evaluate everything in the definitions window, and the values computed will appear in the interactions window. You can also type expressions into the interactions window directly and press enter to evaluate them immediately.

Task: Set the language level.

  1. When DrScheme opens, go to the "Language" menu and select "Choose Language...". Open up the option for "How to Design Programs", and select "Advanced Student".
  2. If there is a button in the bottom of the Choose Language window that says "Show Details," press it. On the right side of the window are a number of options.
    1. Make sure the "Case sensitive" box is checked. This enforces case matching, guaranteeing that the TAs will also be able to run the code you write!
    2. Make sure that "Constructor" is selected for "Output style". This is the output style we teach in CS 19.
    3. For "Fraction Style", there are two options: "Mixed fractions" and "Repeating decimals". You may choose whichever you prefer.
    4. The "Insert newlines in printed values" and "Show sharing in values" boxes should also be checked, but leave "Enable tracing" unchecked.
    Click "OK".
  3. Finally, in the main DrScheme window, click "Run" to finish loading the language level.

Task: Now you're ready to try out DrScheme. Type (+ 4 3) into the definitions window and click "Run". You should see the number 7 followed by a propmt in the interactions window, something like this: 

7
This program should be tested.
>
You can ignore the note This program should be tested. for now. Soon we will teach you how to test your programs.

Practice Saving and Loading Files

Task: Now let's practice loading and saving files in the definitions window, and executing code in the interactions window.

Type the following expressions into DrScheme's definitions window. 

17
(+ 17 18)
(+ 4 4)
(* 2 3)
(quotient 11 2)
(remainder 11 2)
When you've finished typing, save the file by pressing the "Save" button or Ctrl+s. Save the file in /home/<your-login>/course/cs019/labs/ with the file name lab01.scm.

Now quit DrScheme (File -> Quit or Ctrl+q) and reopen it (remember the ampersand!). Use File -> Open or Ctrl+o to bring up the Open File dialog. Browse to the file you saved a moment ago and open it.

Click on the "Run" button or press Ctrl+t. DrScheme will then print the values of these expressions in the interactions window. Type another bit of arithmetic at the interactions window prompt and hit enter. Now hit "Run" again. The interactions window will be cleared, but you can always recover things you've typed in the interactions window with Ctrl+Up and Ctrl+Down.

Practice with Arithmetic Expressions

Task: Type the following expressions into DrScheme's interactions window one at a time. Some of them contain invalid syntax. Reformulate them so that DrScheme returns the desired value.

Note that in Scheme, arithmetic operators like + and * are not limited to exactly two arguments; in CS 19 Scheme they can take more, but not less. Even non-commutative operators like / can take as many arguments as you like. However, it's difficult to read an expression like (/ 5 4 3), so we recommend that you always use / and - with two arguments only.

Editing Tips

As in most text editors, Ctrl+Left and Ctrl+Right move the cursor left and right by a single word. DrScheme also provides another very useful shortcut - Alt+Right and Alt+Left move the cursor by one entire parenthesized expression. Type some expressions with nested parentheses and try it out. can also use Alt+Shift+Left and Alt+Shift+Right to select parenthesized code blocks.

One common annoyance in the interactions window is that when you press enter in the middle of a line, say because you made a mistake a line above and pressed Ctrl+Up, DrScheme will just insert a newline instead of running your code. This is the intended behavior, and is very useful when constructing complex expressions in the interactions window, but it can be bothersome at times. The End key is very useful here, but if you forget and hit enter, Ctrl+z is a much easier way to fix your mistake than hitting backspace a bunch of times.

Comments and Indentation

In general, you want to make your code as legible as possible. Because people have to understand your code, you should add comments in clear English to your code. In Scheme you can do this using semicolons. Any text that appears after a semicolon on a line will be a comment and Scheme will not evaluate that text. For example, the following two Scheme expressions have the same value: 

19
19 ; this is the number 19
DrScheme handily colors comments orange so they are easy to identify.

It is considered good style to use two semicolons for explanatory comments and one when commenting out code.

Task: Type the following into DrScheme's definitions window, then add semicolons where necessary to separate the comments from the code. 

This is a very simple program.
(+ (* 2 3) It adds the product of two and three
   (* 4 5)) to the product of four and five
and should evaluate to twenty-six!

Sometimes you will want to comment out an entire expression or a block of code at the same time. This can be done quickly in several different ways.

Try using one of these methods to comment out all of your code from the previous task.

Indentation is another important way to make your code easier to understand and help you spot errors. DrScheme automatically indents the next line of code every time you press enter. If a line is indented incorrectly (if you changed the lines above it, for example) you can also press the Tab key with the cursor on that line, and DrScheme will automatically fix the indentation. Alternatively, you can press Ctrl+i to automatically fix the indentation in the entire file.

Task: Copy the following code into the definitions window and edit it so that it is more readable (readable indentation counts on your homework!). 

   (define-struct boa (name length food))

   ;; danger-to-rodents? : boa -> boolean
   ;; determines whether a boa eats rats, mice, or gerbils
   (define (danger-to-rodents? aboa) (or (equal? (boa-food aboa) "mice")(equal? (boa-food aboa) "rats")(equal? (boa-food aboa) "gerbils")))

Syntax Checking and Debugging

Task: To experiment with some of DrScheme's more powerful tools, copy the following program into the definitions window. This program has some errors which you will correct later on in the lab. 

;; babel : string -> string
;; produces word for hello in the given language
(define (babel lang)
  (cond [(equal? lang "spanish") (+ 4 "hola")]
        [(equal? lagn "french") "bonjour"]
        [(equal? lang "pig-latin") "ellohay"]))

DrScheme provides a built-in syntax checker to easily spot typos and other simple mistakes.

Task: Press the Check Syntax button.

Your program has been colored in purple, green, red, and blue. Built-in operators appear in purple. User-defined identifiers appear in blue. Constants appear in green. Identifiers that DrScheme doesn't recognize appear in red. One misspelled identifier should appear in red.

Move your cursor over the blue symbols. Notice that blue arrows pop up showing where each identifier is defined/used (except in define-structs). This is another tool that can help you locate errors in your programs. Note that Check Syntax does not find more sophisticated errors, such as type errors.

Task: Fix the error you found, and press Check Syntax. Now try running (babel "spanish"). What happens?

DrScheme comes with a more powerful tool, the debugger, to help you find errors like these. Like the syntax checker, the debugger only works on code in the definitions window; to use it, press the Debug button. When you do, some new buttons appear:

You can set breakpoints in your program while in debug mode by hovering the mouse over an open parenthesis. A red dot should appear. Right click (and hold down the right mouse button; this is a bug) on the dot and choose "Pause at this point". The red circle should darken and become permanent. Now when you click Go, execution will pause before evaluating the expression with the dot next to it, allowing you to begin stepping from that point.

Task: Put the line (babel "spanish") at the bottom of the definitions window. Run the debugger, and explore the behavior of the Step, Over, and Out buttons. Look at how the contents of the stack and variable environment change as you move through the program. Find the other error in this program and fix it. Save your work.

Handing In Assignments

CS 19 is a paperless class. You will be handing in all of your assignments electronically. We have written a handin script to facilitate this process. This script will hand in every file in the directory you are in.

Task: Hand in the Scheme file containing the work you've done in this lab.

Save the file you've been working on, then enter the following commands in a terminal: 

cd ~/course/cs019/lab1/
cs019-handin lab1
This will hand in the contents of the directory ~/course/cs019/labs/ for the assignment lab01. Each assignment will have a unique name, specified on the handout, that you must give as the argument to cs019-handin.

Congratulations! You've completed the first lab of CS 19. Ask a TA to look over your work and check that your handin was successful.