Exercise: An Introduction to Scheme

• Getting Started in the MathLAN
  • Logging In
  • The Linux/Gnome Window Environment
• DrScheme
  • Starting DrScheme
  • DrScheme language options
  • DrScheme's Interactions Pane
  • DrScheme's Definitions Pane
• Lists in Scheme
  • Constructing Lists
  • Extracting Values
  • Common list procedures
• Defining Procedures
• Conditionals

Getting Started in the MathLAN

Please don't be intimidated! Although this lab contains many details which may seem overwhelming at first, these mechanics will become familiar rather quickly. To help the process along, you might want to spend some time on your own before the next class, working through the lab a few times, exploring various buttons, and experimenting with options. Feel free to talk to the instructor or with a MathLAN User Consultant if you have questions or want additional help!

Logging In

Short Version:

• Enter your name. Press Enter.
• Enter your password (which won't appear). Press Enter.
• Get help if those two steps don't work.

To use any of the computers in the Mathematics Local-Area Network, one must log in, identifying oneself by giving a user name and a password. You will have received a MathLAN user name and password from the instructor if you did not already have one. If you have not received a MathLAN user name and password, or if you have forgotten either one, please tell your instructor.

When it is not in use, a MathLAN workstation displays a login screen with a space into which one can type one's user name and, later, one's password. (If the workstation's monitor is dark, move the mouse a bit and the login screen will appear.) To begin, move the mouse onto any part of the box containing the login box. Type in your user name, in lower-case letters, and press the <Enter> key. The login screen will be redrawn to acknowledge your user name and to ask for your password; type it into the space provided and press <Enter>. (Because no one else should see your password, it is not displayed on screen as you type it in.)

At this point, a computer program that is running on the workstation consults a table of valid user names and passwords. If it does not find the particular combination that you have supplied, it prints a brief message saying that the attempt to log in was unsuccessful and then returns to the login screen -- inviting you to try again. Consult the instructor or the system administrator if your attempts to log in are still unsuccessful.

The Linux/Gnome Window Environment

Short Version:

• You'll see something that looks somewhat like Microsoft Windows, but also somewhat different.
• Icons at the bottom of the screen can be used to start programs.

Once you have logged in, a control panel will appear at the bottom of the screen. Some other windows also may be visible in other parts of your screen. All of these areas are managed by a special program, called a windowing system. On MathLAN, login chores and other administrivia are handled by a program or operating system, called Linux, and the windowing system is called Gnome. (While the Linux operating system supports many languages and environments, you may be interested to know that the Linux/Gnome windowing system itself is written in Scheme.)

DrScheme

Short Version:

• We use a programming language called Scheme and a programming enviornment called DrScheme.

Many of the fundamental ideas of computer science are best learned by reading, writing, and executing small computer programs that illustrate them. One of our most important tools, therefore, is a computer program designed specifically to make it easier to read, write, and execute other computer programs. In our introductory courses, we will often use a programming environment named DrScheme.

Starting DrScheme

Short Version:

• Click on the Lambda at the bottom of the screen.
• DrScheme has menus. Figure out how to quit.

To start DrScheme, click the mouse on the large, round, red icon containing the Greek letter lambda in the middle of the control panel. If you don't have that icon, click on the icon of a computer screen with a foot on it, Soon you'll see a grey window on the screen, type drscheme & in that window.

Shortly, DrScheme will start up and appear as a new window, with two white rectangular text areas against a dark gray background.

At the top of the window, just below the frame, is a menu bar, providing ways of activating various operations that DrScheme can perform. Eventually we'll explore a number of these, but for the moment let's just look at one that you're certain to need: the operation of shutting itself down.

Move the mouse pointer onto the word File at the left end of the menu bar and click the left mouse button. A small menu appears.

Move the mouse pointer onto the word Quit at the bottom of this menu and click the left mouse button. DrScheme responds by popping up a confirmation box of its own, the purpose of which is to make sure that you don't shut down DrScheme by mistake.

Move the mouse pointer onto the word Quit in the confirmation box and click the left mouse button. Both the confirmation box and the main DrScheme window disappear.

DrScheme language options

Short Version:

• Restart DrScheme
• Click on the Language menu
• Select the Choose Language ... option
• Click on the triangle next to PLT so that it points down
• Click on Graphical
• Click on OK
• Click on Execute

DrScheme can deal with computer programs written in a number of dialects of the Scheme programming language. When you start DrScheme for the first time, it expects you to use Beginning Student Scheme, which is a kind of training-wheels dialect that enables DrScheme to catch and diagnose some common mistakes of novice programmers.

Although you are novice programmers, we're going to proceed directly to Full Scheme, which is more nearly standard. To inform DrScheme of this decision, we'll need another of the operations accessed through the menu bar. If you exited from DrScheme, restart it now. When the window appears, move the mouse pointer onto the word Language on the menu bar and click the left mouse button to bring up the Language menu. Move the mouse pointer onto the phrase Choose Language... and click the left mouse button again to select that operation. Another window appears.

Move the mouse pointer over the triangle to the left of PLT and click on it until it points downward. You should see a few more words indented. Click on Graphical (MrEd, includes MzScheme).

Move the mouse pointer onto the word OK and click the left mouse button. The extra window disappears, leaving the DrScheme window. Next, move the mouse pointer onto the word Execute (next to a green arrow, just below the menu bar) and press the left mouse button. DrScheme now expects programs in the dialect it calls Graphical Full Scheme.

DrScheme retains the information that you prefer to use full Scheme, so that when you log in again tomorrow and start DrScheme again, it will automatically expect programs in that dialect. You won't need to use the Choose Language operation again unless you decide that you'd like to experiment with Beginning Student Scheme or some other dialect.

Make sure that all members of your group login and choose the appropriate dialect of Scheme before you go on to do any other work in Scheme.

DrScheme's Interactions Pane

Short Version:

• The lower text area is called the interactions pane.
• You type scheme commands there and DrScheme responds.
• Try typing (sqrt 137641)

Now you're ready to look at the parts of DrScheme.

In the interactions pane -- 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 pane 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 pane 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.

DrScheme's Definitions Pane

Short Version:

• The interactions pane is temporary. The top pane, called the definitions pane is more permanent.
• When you click Execute, the interactions pane is erased and the instructions in the definitions pane are executed.

The upper text area in the DrScheme window, which is called the definitions pane, 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 pane. If you never click on that button, fine -- your program is never executed.

As its name implies, the definitions pane usually contains definitions rather than commands, although either kind of expression can be written in either pane. 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 pane are erased. The idea is that executing the program in the definitions pane 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 pane before clicking on Execute.

Lists in Scheme

Constructing Lists

In addition to unstructured data types such as symbols and numbers, Scheme supports lists, which are structures that contain other values as elements. There is one list, the empty list, that contains no elements at all. Any other list is constructed by attaching some value, called the car of the new list, to a previously constructed list, which is called the cdr of the new list.

Scheme's name for the empty list is a pair of parentheses with nothing between them: (). When we refer to the empty list in a Scheme program, we have to put an apostrophe before the left parenthesis, so that Scheme won't mistake the parentheses for a procedure call:

> ()
()

Since this conventional name for the empty list is not very readable, our implementation of Scheme also provides a built-in name, null, for the empty list. We follow this usage and recommend it.

> null
()

The simplest way to build a list is with the list procedure. You tell Scheme to build a list by writing an open parenthesis, the procedure name list, the values you want in the list, and a close parnethesis.

> (list 1 2 3)
(1 2 3)
> (list 3 1 2 5 6)
(3 1 2 5 6)

You can name a list you've created with the define procedure.

> (define lst (list 1 2 3 4 5))
> lst
(1 2 3 4 5)

You can also add an element to the front of a list with cons. It takes two arguments and returns a list that is just like the second argument, except that the first argument has been added at the beginning, as a new first element. Once again, this change does not affect the original list.

> (define lst (list 1 2 3 4 5))
> lst
(1 2 3 4 5)
> (cons 6 lst)
(6 1 2 3 4 5)
> (define newlst (cons 0 lst))
> newlst
(0 1 2 3 4 5)
> lst
(1 2 3 4 5)

Task: Try this example!

You can even use cons to build up a list from nothing (or at least from null).

> (define singleton (cons 5 null))
> singleton
(5)
> (define doubleton (cons 8 singleton))
> doubleton
(8 5)
> (define tripleton (cons 0 doubleton))
> tripleton
(0 8 5)
> (cons 1 (cons 2 (cons 3 (cons 4 null))))
(1 2 3 4)

Task: Try this example!

Extracting Values

Once you've built a list, you can extract the first element with car and the rest of the list (all but the first element) with cdr. Neither operation affects the original list; they simply create a new value or list.

> (define lst (list 1 2 3 4 5))
> lst
(1 2 3 4 5)
> (car lst)
1
> (cdr lst)
(2 3 4 5)
> lst
(1 2 3 4 5)

Task: Try this example!

Task: Figure out how to get the second value in a list.

Common list procedures

Scheme provides several built-in procedures that operate on lists. Here are a few that are very frequently used:

The length procedure takes one argument, which must be a list, and computes the number of elements in the list.

Task: Play with length to make sure you understand it.

The reverse procedure takes a list and returns a new list containing the same elements, but in the opposite order.

> (reverse (list 1 2 3))
(3 2 1)

Defining Procedures

Scheme even lets you define your own procedures. Here's a simple procedure that gives you the second value in a list. You might want to enter it in the top half of the DrScheme window (the definitions pane).

(define (second lst)
  (car (cdr lst)))

Task:

• Enter that procedure in the definitions pane
• Try to find the second value in the list (4 5 6). In most cases, you'll fail.
• Click the Execute button at the top of the DrScheme window.
• Try to find the second value in the list (4 5 6).

Task: Write a procedure, (swap-first-two lst) that swaps the first two elements of a list. For example,

> (swap-first-two (list 1 2 3 4 5))
(2 1 3 4 5)
> (swap-first-two (list 10 100))
(100 10)

Conditionals

Scheme lets you write conditionals with the if procedure. It takes the form

(if test
    expression-to-use-if-test-holds
    expression-to-use-if-test-fails)

Scheme tests usually have the form

(test-operation val1 ... valn)

You can use the null? operation to determine if a list is empty.

> (null? (list 1 2 3))
#f
> (null? null)
#t
> (null? (cdr (list 1)))
#t

Task: Write a procedure, only-one? that determines if a list has only one element. (Try not to use length.) For example,

> (only-one? (list 1))
#t
> (only-one? null)
#f
> (only-one? (list 1 2 3 4 5))
#f

Scheme also provides five numeric tests, <, <=, >, >=, and =. For example, to check if x is less than y, I might use

> (< 4 6)
#t
> (< 6 -2)
#f
> (define x 10)
> (< x 4)
#f

Here's a simple use of if to find the smaller of two numbers.

(define (smaller num1 num2) 
  (if (< num1 num2)
      num1
      num2))

Task: Test this procedure.

Task: Update swap-first-two so that it does not crash when you try to swap the first two elements of a list with fewer than two elements.

History

Tuesday, 20 August 2002

• First version, based on a number of handouts from CS151 2001S.
• Deleted text from those handouts.
• Added new exercises.

Wednesday, 21 August 2002

• Added some Short Version introductions to the longer sections.
• Fixed some errors in the code created yesterday.
• Added more information on the basic truth operations.

Monday, 18 August 2003

• Added some examples to some probelms.
• Added a few more notes.