Beginning Scheme

• Algorithms and Programs
• Interacting with DrScheme
• Procedure calls
• Definitions
  • DrScheme's definitions window
    • Saving Windows to Files
  • More Procedures

Algorithms and Programs

Our main objectives in this course are to learn about algorithms -- step-by-step methods for solving problems -- and to learn how to direct computers to perform such algorithms for us. A programming language, such as Scheme, is a formal notation in which one can express algorithms so exactly that a computer can perform them without any other assistance from human beings. The expression of an algorithm in such a notation is called a program, and the computer is said to be executing the program when it is performing the algorithm as directed.

Although not all of the problems that we'd like computers to solve are arithmetical, the simplest examples belong to that category, and we'll start with a few of them. Here, for instance, is a program, written in Scheme, that directs the computer to find the answer to the question ``What is the square root of 137641?''

(sqrt 137641)

In order to make the Scheme envronment answer that question, you need to learn how to work with Scheme.

Interacting with DrScheme

The programming environment we use in the MathLAN is called DrScheme. It is also available for the Macintosh and PC. In the MathLAN, there are two ways to start DrScheme.

If your control pad has an icon with a lambda in it, you can click on that icon to start DrScheme.

Otherwise, you need to start DrScheme with the terminal emulator. If no terminal emulator appears automatically when you log on to a MathLan workstation, start one by clicking on the monitor-and-keyboard icon on the front panel. Type drscheme & at the shell prompt to start the DrScheme programming environment.

In the interactions window -- the lower of the two large text areas -- DrScheme displays a one-line greeting, a reminder of which dialect of Scheme it expects to see, and a prompt (in this case, a greater-than sign), indicating that DrScheme is ready to deal with any command that you type in.

To enter a Scheme program, move the mouse pointer to the right of the prompt, click the left mouse button, and type in the program. (If you prefer, you can select the program from another window by moving the mouse pointer to the beginning of the program, pressing and holding the left mouse button, dragging the mouse pointer to the end of the program, and releasing the left mouse button. The background color against which the text that you have selected changes during this process, so that you can see the boundaries of the selection clearly. You can then paste the selected text into the interactions window by moving the mouse pointer to the right of the prompt and clicking the middle mouse button.)

To get DrScheme to execute your program, press the <Enter> key after the right parenthesis. At this point, DrScheme examines your program, translates it into a sequence of instructions to the computer's central processor (the electronic circuit that directs the movement and transformation of data inside the computer), executes it, and prints out the result of its computation. Because this particular program is extremely simple, the result is printed immediately.

You may notice that DrScheme prints out another prompt after executing your program. This is because DrScheme cannot be sure that it has seen all the steps in the program. A program written in Scheme has a particularly simple structure: it is a sequence of definitions and commands -- any number of them, in any order. DrScheme reacts to each definition that you type into the interactions window by memorizing it and to each command by carrying out the command. (The expression (sqrt 137641) is a command -- ``Compute the square root of 137641!'') Because a program might contain several commands rather than just one, DrScheme has to be prepared to receive another after carrying out the first.

Procedure calls

The full Scheme language that DrScheme supports contains several hundred primitive procedures -- operations, such as finding the square root of a number, for which DrScheme can use prepackaged algorithms. Some programmers who are experts on square roots and on the idiosyncracies of our computers have figured out and written up a step-by-step method for computing the square root of any number, using only the very elementary transformations that the processor can perform. DrScheme recognizes sqrt as the name of this algorithm and knows where the processor instructions that carry it out are stored. When DrScheme receives a command to compute a square root, it recovers these instructions and arranges for the processor to follow them.

A procedure call is a command that directs DrScheme to activate a procedure such as sqrt. (Note: sqrt is the name of the procedure, and (sqrt 137641) is the procedure call.) In Scheme, every procedure call begins with a left parenthesis and ends with the matching right parenthesis. Within the parentheses, one always begins by identifying the procedure to be called and then continues by identifying the arguments -- the values that the procedure is supposed to operate on. The sqrt procedure takes only one argument -- the number of which you want the square root -- but other procedures take two or more arguments, and some need no arguments at all.

All arithmetic in Scheme is done with procedure calls. The primitive procedure + adds numbers together, the primitive procedure - subtracts one number from another. Similarly, the primitive procedure * performs multiplication, and the primitive procedure / performs division. The fact that in a procedure call the procedure is identified first makes calls to these procedures look different from ordinary arithmetic expressions: For instance, to tell DrScheme to subtract 68343 from 81722, one gives the command (- 81722 68343).

Other Scheme procedures include abs, and expt. The Scheme procedure abs computes the absolute value of its argument. The Scheme procedure for raising a number to some power is expt.

As you may have noted, the appropriate way to write a Scheme expression is

(operation argument1 ... argumentn)

It is harmless, though unproductive, to try to give DrScheme ordinary arithmetic expressions, in which the procedure is written between the operands.

Definitions

DrScheme can also learn new names for things by reading definitions. Here's what a definition looks like:

(define days-in-a-week 7)

Like a procedure call, a definition begins and ends with matching parentheses. To distinguish between definitions and procedure calls, DrScheme looks at what comes immediately after the left parenthesis. In a definition, the keyword define must appear at that point. Define is not the name of a procedure; it is part of the syntactic structure of the Scheme programming language. Its only role is to serve as the mark of a definition.

After the keyword define, a definition contains the name being defined and an expression that identifies the value that the name should stand for. In this example, the name is days-in-a-week. (Notice that in Scheme a name can, and often does, contain hyphens internally.) The value that it names is the number 7. Once DrScheme has seen this definition, it remembers that days-in-a-week stands for 7.

The value that gets a new name need not be a number; it can be anything, even a procedure. For example, if you don't like the name * for the multiplication procedure and would rather call it by the name multiply, just start each session with DrScheme by giving it the definition (define multiply *).

DrScheme's definitions window

The upper text area in the DrScheme window, which is called the definitions window, is used when you want to prepare a program ``off-line,'' that is, without immediately executing each step. Instead of processing what you type line by line, DrScheme waits for you to click on the button labelled Execute (the second button from the right, in the row just below the menu bar) before starting to execute the program in the definitions window. If you never click on that button, fine -- your program is never executed.

As its name implies, the definitions window usually contains definitions rather than commands, although either kind of expression can be written in either window. The difference is simply that we generally want an immediate response to a command, whereas definitions are usually processed in bulk.

Warning: When you click on the Execute button, the contents of the interactions window are erased. The idea is that executing the program in the definitions window may invalidate the results of previous interactions. Erasing the results that may now be inconsistent with the new definitions ensures that all visible interactions use the same vocabulary. This is actually a helpful feature of DrScheme, but it can take you by surprise the first time you see it happen. Just make sure that you have everything you need from the interactions window before clicking on Execute.

Saving Windows to Files

You can save the contents of either window in a file at any time by selecting Save Definitions As Text or Save Interactions As Text from the File menu. DrScheme pops up a window in which you can specify the name of the file:

Edit the contents of the white text field near the bottom of the pop-up window, adding a slash and the name of the file. Click on the OK button to dismiss the pop-up window.

More Procedures

At this point, I hope you're wondering what other useful and interesting procedures are built into Scheme. Section 6.2.5 of the Revised⁵ report on the algorithmic language Scheme contains a list of the ones that are mainly about numbers, and that's only one section of the full roster of standard Scheme procedures. Fortunately, most of the primitive procedures perform small, simple jobs and are easily learned.