Lab 2
Writing Scheme Functions

Comp 210

Spring 1996

Contents

Stepping with Donkey

Homework 2, problem 1 asks you to determine how many calls are made to a function. (You should give the total number of calls, including the initial one.) Donkey can help you with this homework. One strategy is to just step through evaluation of the entire expression, noting when you reduce a function call. But there is an easier way.

In Donkey, pull down the Stop-at menu, then select apply. Now when you click on the Step button, Donkey will proceed until the next evaluation rather than stopping at every evaluation step. You can basically just count the number of times you click on Step.

Another way to do your homework is to reason about the programs: take a look at what they are doing, and try to figure out how they should behave.

The way that I did the homework was to write a program to compute the answers for me. A function to determine the number of calls made is only a trivial modification of the functions whose behavior you are examining. If you make just a few careful changes, you'll get a function that tells you how many calls the original function would have made. (Of course, the new function tells you nothing about what value the original function would have returned, but we're not interested in that.)

The Talking Computer

By loading a special set of Scheme procedures, you can make your computer talk. To load the Comp 210 sound library, evaluate the following expression (use DrScheme, not Donkey). 

  (load "/home/comp210/sounds/sound-library.ss")
The double quote marks set off a new type of value called a string. A string is somewhat like a symbol, in that it consists of any sequence of characters. Here, the string specifies the file containing the Scheme code.

This file defines the following Scheme variables:

Do some experiments with these procedures. For instance, try 

  (speak-list (cons 'artichokes (cons 'are (cons 'awesome null))))
We learned in lecture that the list function also creates lists, so the above is equivalent to 
  (speak-list (list 'artichokes 'are 'awesome))

Since the sound can be annoying to others in the lab, consider placing your hand over the speaker (over the holes on the front left of the machine) to muffle the sound.

In case of trouble

There are several potential sources of trouble when loading the file sound-library.ss. Check that you spelled the name of the file correctly: 

  (load "/home/comp210/sounds/sound-library.ss")
Also, make sure you use (load "...") and not DrScheme's File - Open... menu. For now, don't read big files into the DrScheme editing window; that's too slow. Also, load only works intermittently under Donkey, so don't run the load command from Donkey yet.

If you get the complaint 

  "/dev/audio": no such file
then maybe your machine doesn't have sound. The SPARCstation 5s in the front of Ryon 102 have sound, but the SPARCstation 4s in the back of Ryon 102 don't. To find out for sure, try running this command (from a command shell such as an xterm window, not from Scheme): 
  cat /home/comp210/sounds/bark.au > /dev/audio
If it makes a noise like a dog coughing, then your machine has sound. If not, move to another machine that says ``SPARCstation 5'' on the front.

If you enter the load command and Scheme just sits there for more than about a second, then another program may have control of the speaker. Only one program can use sound at a time. So, kill any other copies of DrScheme or Donkey (or anything else that uses sound). Even Web pages can contain sound, so you might have to kill Netscape, but that's probably not necessary. Also, it is possible in rare cases for a program to go into a dormant state (even if its windows is gone from the screen), in which case killing it is more involved. Try logging out and logging back in, or moving to a different machine if all else fails.

Chez Scheme

DrScheme and Donkey are sometimes unreliable; sound is particularly effective in frightening DrScheme (and causing the program to quit).

If you have this problem you might want to know about another implementation of Scheme called Chez Scheme. It is considerably more robust, though it lacks some of the features of DrScheme and Donkey. It does not run in its own window, does not step through expression evaluation, and does not permit convienient editing of previously-evaluated expressions.

To run Chez Scheme, type scheme at a command shell. (Don't put an ampersand (&) after the command.) You will shortly get a > prompt. At the prompt, you can type any Scheme expression. For instance, you could load the sound library, then call speak-word and speak-list.

In Chez Scheme, you may need to use the delete key (to the right of the main keyboard on the SPARCstation 5 keyboards) rather than the backspace key. To break out of whatever you are doing and get a new prompt, press control-c (hold down control, press and release c, let up on control). When you are done with Chez Scheme, execute the function exit to leave: 

  (exit)

In the next lab, we will see another way to edit programs, and to run Chez Scheme from that editor, somewhat like DrScheme.

Defining Recursive Scheme Functions

Recall from class the four-step method for defining Scheme procedures:

data definition
describes the input to your function, often in terms of itself (and some alternative that doesn't include itself)
program schema
is a skeleton or template for the function which shows the basic structure but omits the details. The schema for a particular data type is always the same, no matter what the function actually does.
fill it in
to add details about this particular function to the schema
test
the procedure by applying it to appropriate test cases which exercise all the procedure's functionality

In class, we followed these steps for the function member?, that takes a list l and a symbol s as input and determines whether or not the symbol appears in the list. Let's do the same for lingth, which returns the length of a list. (We won't call it length, because DrScheme already has a function of that name and is very protective of it. Chez Scheme is less picky and will let you use whatever name you like.)

A list is either

This definition is circular, but it's meaningful. The self-referential part is simpler than the whole--in the case of lists, the list tl is shorter than the list (cons hd tl). Similarly, when we write a function, the recursive call must given a simpler argument (such as a shorter list or a smaller number) than the current call got.

The corresponding schema for writing a rule R to process lists is 

  (define R
    (lambda (l)
      (if (null? l)
          ...
          ... (car l) ... (R (cdr l)) ... )))

The first ellipsis ... is an expression specifying what answer the rule produces for the empty list. (The expression doesn't include l because we already know everything there is to know about it--it is exactly the empty list.) The second expression ... (car l) ... (R (cdr l)) ... constructs the answer for a non-empty list l. This expression may invoke the rule R recursively to process (cdr l), and it may also examine the first element of the non-empty list l. (Either or both of these subexpressions may be omitted, if desired.) Note that the rule includes a recursive call to R for each recursive reference in the definition. One if is sufficient because there are only two possibilities for l; if there are more possibilities, we need more if expressions, or we can use a different operator called cond.

The rule defining the function lingth is an instance of the preceding schema: 

  (define lingth
    (lambda (l)
      (if (null? l)
          0
          (+ 1 (lingth (cdr l))))))

One way to think about recursive programming is in terms of wishful thinking. While writing lingth, at one point we said, ``I wish I had a function that I could use to determine the length of the cdr rest of the list; then I could use that to determine the length of the whole list.'' We just pretended that we already had such a thing--called lingth--and proceeded. Then, before we knew it, we really did have lingth!

Exercises

Type the definition of lingth and test it on some lists. You should get the same answers as from the built-in function length.

When doing the following exercises, remember to write a schema that follows the data definition for the input.

Define the function member-count, which is like member?, except that it returns a number indicating the number of times that the symbol appears in the list. For instance,

(member-count (list 'a 'b 'a 'c 'a) 'a) => 3
(member-count (list 'a 'b 'a 'c 'a) 'z) => 0
Challenge: Your solution probably contains an if and a call to +. Can you change the order of those operations?

Define the function nth, which returns the nth element in a list. For instance,

(nth (list 'a 'b 'c 'd 'e) 2) => 'b
(nth (list 'a 'b 'c 'd 'e) 5) => 'e

Write a function list-of-numbers? that takes a list as input and determines whether it is a list of numbers. The Scheme operation number? determines whether or not a Scheme datum is a number.

Scheme Program Layout

DrScheme makes it easy to express Scheme programs in a consistent, readable format. Your programs should conform to the indentation conventions supported by DrScheme. If a program definition is not properly indented, you can use the command Indent All on the Scheme menu to indent it properly, subject to the line breaks in the definition. Indent All will not change line breaks.

As you enter a program definition, DrScheme automatically indents each line properly, but there are a few conventions that you must observe in making line breaks to produce programs with the proper layout.

Inserting Line Breaks

The following rules provide simple guidelines for inserting line breaks. If you follow these rules, your code will be eaiser to read and understand. Don't forget to make the indentation right: in Donkey, DrScheme, or Emacs, just type TAB while the cursor is anywhere on a line, and that line will be correctly indented relative to the line just above it.

  1. In a function definition, insert a line break just after the function name, before the expression whose value is the function. For instance, in the definition of lingth, we put 
      (define lingth
    on a line by itself.
  2. In the expression defining the function, put the keyword lambda and the accompanying list of input variables on a separate line. 
      (define lingth
    (lambda (l)
  3. In an if expression, put line breaks after the condition and after the true consequent. 
      (define lingth
    (lambda (l)
      (if (null? l)
          0
          (+ 1 (lingth (cdr l))))))

    There is a separate set of rules for cond conditionals; we will introduce those next week when we learn about cond.

  4. In an ordinary function application, either put all the arguments on one line, or put each argument on its own line. If the arguments are long, take the second approach; this makes it easier to see where each argument starts and stops. If the arguments are short, take the former approach; this prevents your program from becoming unnecessarily long, with many very short lines. Whether to put the first argument on the same line with the function itself is up to you; it depends on how much space is left on the line. You should always add line breaks when the code runs past the right margin of your text editor (or the paper).
  5. For cond, see next week's tutorial notes.

Additional Editing Commands

DrScheme has many useful editing commands that were not mentioned in the first laboratory. The Edit menu contains seven commands: Undo, Redo, Clear, Copy, Cut, Paste, and Find. Most of these commands involve selected text. You can select text in DrScheme by placing the cursor on the first character of the desired selection, pressing the left mouse button, moving the cursor just past the last character in the selection, and releasing the mouse button. The selection is highlighted whenever the mouse points to the DrScheme window.

The edit menu commands have the following functions:

Undo undoes the last edit command that changed the contents of the dictionary window. Executing
Undo N times will undo the last N changes.
Redo redoes the last undone command. If you perform the Undo command too many times, you can back up using the Redo command.
Clear deletes the selected text without copying it into the clipboard.
Copy copies the selected text into the clipboard. The clipboard holds a piece of text that can be inserted in any window--not just DrScheme.
Cut deletes the selected text and copies it into the clipboard.
Paste inserts the text in the clipboard at the point specified by the current mouse position.
Find pops up a new window that asks you to specify what you want to search for and where; it should be self-explanatory.

Try using each of these commands. Enter some garbage in your dictionary and use Undo to erase it. Try using Redo to reverse the process of undoing commands.

Keystroke Editing Commands

DrScheme also supports many commands that are invoked from the keyboard. Some useful keystroke commands are Tab, Control-f, Control-b, Control-n, Control-p, Control-a, Control-e, Control-d, and Control-k. The Control key is a form of ``shift key''. For example, Control-d is the character d typed while the Control-key is depressed. These keystroke commands have the following functions:

Save your dictionary and then experiment with these keystroke editing commands.

Coping with Errors

DrScheme catches two different forms of Scheme program errors. First, it notices when you try to load ill-formed programs from the dictionary window into the evaluation window. In this case, it pops up a window identifying the error and asking you what to do next. The obvious response is to click on the button that aborts loading the program text, then edit your dictionary to correct the specified error. The second form of error detection is more subtle. During program execution, a program operation can be applied to invalid data. Examples include peforming arithmetic on inputs that are not numbers, dividing by zero, and applying car or cdr to the empty list. In this case, DrScheme aborts program execution, prints a message explaining why, and places an ugly black square on the operation that is being applied to illegal data.

Load the file error.ss into the dictionary window and try following sequence of experiments:

  1. Try to load the contents of the dictionary window into the evaluation window using the Execute command. It should fail because the function definition for fact is ill-formed because it is missing a closing parenthesis. Fix the error and Execute the dictionary again.
  2. Evaluate (fact 5). Observe that execution aborts and identifies the culprit as the function application (* n (fact (sub1 n))) when n is 1 and (fact (sub1 n)) is the empty list.
  3. Correct the mistake in the definition of fact in the dictionary window, reload it in the evaluation window, and evaluate (fact 5) and (fact 500).

Aborting Infinite Loops!

If you inadvertently start executing a function that never terminates, you can usually break out of it by selecting the Stop Executing button at the top of the window. At this point, DrScheme will type a new prompt in the evaluation window 

  >
and wait for you to enter a new expression in the evaluation window or new definition in the dictionary window.

Edit the definition of fact by changing (sub1 n) to n. Load the dictionary into the evaluation window and try evaluating (fact 5). Use the Stop Executing button to stop execution.