Exercise: An Introduction to Scheme

• DrScheme
  • DrScheme's Interactions Pane
  • DrScheme's Definitions Pane
• Lists in Scheme
  • Constructing Lists
  • Extracting Values
  • Common list procedures
• Defining Procedures
• Conditionals

Please don't be intimidated! Although this lab contains many details which may seem overwhelming at first, these mechanics will become familiar rather quickly.

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.

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.