CS 217: Scheme Introductory Lab

Work through the following lab, and finish up in your own time if you need it. Turn in your code from the end of Part 6 within a week. Keep in mind that in addition to this lab, there are Scheme resources linked on the course page if you need help. You may turn this in in pairs.

The questions that you find intermixed throughout the lab are for you to think about. Ask in lab or in class if the answers aren't in clear.

Part 1: Getting started in Scheme

Emacs is a really good editor to use when programming for this class. Most importantly, Emacs allows you to run a Linux shell, which is crucial for the various programming environments that we will use. You are welcome, of course, to use any editor you like; but I strongly recommend that you learn Emacs at least for running your programs.

Most of what we do below will be described via keyboard shortcuts. You can do most of it as well with the menus within Emacs, if you like - but you'll be much faster and more effective in the end if you learn the keyboard techniques.

Start up emacs by typing

emacs &

at a Linux prompt. The "&" means start it as a background job, so that you still have access to the command line if you want it.
In Emacs, most commands are proceeded by either ctrl-x or alt-x. We will first want to open up a Linux shell inside of Emacs. To do so, enter alt-x, and at the prompt at the bottom type the word shell.
Start up Scheme by typing

mzscheme

at the prompt. According to its website, MzScheme is actually pronounced "miz scheme," as in "Ms. Scheme."
Type in a very simple Scheme program just to try it out. For example, enter in the code

(+ 3 5)

This should add 3 to 5. In Scheme, + is a function. To call a function in Scheme (similar to a method in Java), you place the name of the function and its arguments, separated by spaces, inside parentheses. This takes a little getting used to! In Java and C++, function calls look something like this:

function(arg1, arg2, arg3)

In Scheme, function calls look like this:

(function arg1 arg2 arg3)
Change your program in some way. For example, re-type it as

(+ 3 7)
Experiment with the alt-p and alt-n keys, which allow you to move backwards and forwards through your command history.
To exit MzScheme, type ctrl-d. Type ctrl-d again at the Linux prompt. You should see a message that says "process shell finished". Finally, to exit Emacs, type ctrl-x, ctrl-c.

Last word of encouragement: Emacs is many, many times more powerful than gedit, nedit, pico, and most of the other editors floating around the system. It is likewise more difficult to learn. If you stick with it and learn the keyboard shortcuts, however, you will be able to edit your code considerably faster than when using the other tools (vi religion wars aside). It took me about a month of regular coding to feel comfortable in Emacs. I never went back!

Part 2: Basic Scheme Primitives

Start up Emacs and Scheme again. At the Scheme prompt, enter the following:

(car '(apple orange pineapple))
(cdr '(apple orange pineapple))
(car (apple orange pineapple))

What do car and cdr do? Why is the single quote necessary? What does it do?
Write sequences of cars and cdrs that will pick the symbol pear out of the following expressions:

(apple orange pear grapefruit)
(((apple) (orange) (pear) (grapefruit)))
(apple (orange) ((pear)) (((grapefruit))))
Execute the following statements. What do the functions cons, append, and list do?

;; This is a comment, by the way!
(cons 'x '(1 2))
(cons '(1 5) '(2 3))
(append '(1) '(2 3))
(append '(1 5) '(2 3))
(list '1 '2 '3 '(4 5))
Execute the following code. What do length and reverse do?

(length '(plato socrates aristotle))
(reverse '(plato socrates aristotle))
(member 'socrates '(plato socrates aristotle))
(member 'raphael '(plato socrates aristotle))
Exit Scheme and Emacs as described earlier.

Part 3: Saving your code

Entering your code interactively is fun, but not a good idea for creating large programs. A better way to go is to create a file with your code, save it, then run it inside MzScheme. Here's how to do it.

In the terminal window, make a directory to store your code for this class in. For example, you can type

mkdir cs217

from your home directory. Then change to this directory by typing

cd cs217

Create a subdirectory from here by typing

mkdir scheme

Then change to this directory by typing

cd scheme
Open an Emacs window by typing

emacs &

at the terminal window command prompt.
To start working on a program, type ctrl-x, ctrl-f (the f means find), and provide Emacs with a filename. For example, I might type prog1.scm. Emacs will open up this file if it exists, or will present you a new blank file.
Start typing in some Scheme code. Use any of the above examples that you wish. When finished, save your program by typing ctrl-x, ctrl-s (the s means save).
Open up a second window inside emacs by typing ctrl-x, 2 (the 2 indicates two windows). To switch between windows, you can either use the mouse or enter the command ctrl-x, o (the o means "other"). Switch to the bottom window, enter alt-x, and at the command prompt type the word shell. Change to the directory in which you stored your Scheme program. For example, if I stored my Scheme program in the directory ~/cs217/scheme, I would type

cd ~/cs217/scheme
Startup MzScheme by typing mzscheme in the shell window.
Run your program. To do this, type

(load "prog1.scm")

(or substitute here whatever you named your program).

You should generally use this approach for entering and running Scheme code, but entering code directly into the shell window is good for testing out quick ideas.

Part 4: Conditionals

Scheme has a number of different predicates for testing equality.

In the shell window, type

(define x '(hi there))
(define y '(hi there))
(equal? x y)
(eq? x y)

What kind of responses do you get? Why?
In the shell window, type

(define x 'hi)
(define y 'hi)
(equal? x y)
(eq? x y)

What kind of responses do you get? How are equal? and eq? different?
Enter the following code into a Scheme file, save it, then load it as in Part 4:
```
;; The function = can be used on numbers

(define x 5)
(define y 0)
(if (= x 3)
   (set! y 9)
   (set! y 10))
```
What value is assigned to y? What does it mean to have two statements after an if? How are define and set! different?
The following code achieves the same purpose, and is much cleaner. Why does it work?
```
(define x 5)
(define y (if (= x 3) 9 10))
```
Enter the following code:
```
(define x 8)
(define y (cond ((= x 3) (+ 3 8))
                ((= x 8) 12)
                (else (* 6 3))))
```
Can you change the value of x to get different values of y? What does the cond function do?

Part 5: Defining functions

In a new Scheme file, enter in the following code, save it, then run it.
```
(lambda (x)
  (+ x 1))
```
What does Scheme return? The lambda function returns a procedure (function) without a name. In this case, you have defined a procedure to that takes one argument and adds 1 to it.
A procedure without a name is useless, as it is immediately garbage collected. Try this instead:
```
(define add-one
  (lambda (x)
    (+ x 1)))
```
Save this code, run it, then type (add-one 5) in the shell window. The define statement created a pointer, called add-one, which points to the function you just created.
The above can be entered via shorthand as
```
(define (add-one x)
  (+ x 1))
```
Try it! Remember, this is just shorthand for the slightly longer code above.
Try this out:
```
(define another-add-one add-one)
(another-add-one 5)
```
At the pointer level, what is happening here? Draw a picture on this paper indicating what is happening.
You can declare "local" variables in Scheme via the use of the let function. For example, run the following code:
```
(define a 5)
(define b 6)
(define c 7)
(let ((a 1) (b 2))
  (set! a 7)
  (set! c (+ a b)))
```
After executing this code, what are the values of a, b, and c? Why?

Part 6: Recursion

Enter and load the following function. What does it do? Why?
```
(define (mystery L)
  (if (null? L)
      L
  (append (mystery (cdr L))
          (list (car L)))))
```
Note that there is no return statement here, as you would find in a similar function in other languages you may know. Why? How is the return value determined in the above function?
To trace your program, add
```
(require (lib "trace.ss"))
```
to the top of your program (in the definitions window), then save and re-load it.

Now type (in the shell window)
```
(trace mystery)
(mystery '((1 2) (3 4) 5 6))
(untrace mystery)
```
Write a recursive function, keep-first-n, that returns a list of the first n elements in a list. You may assume that there are at least n elements.

Example:
```
> (keep-first-n 3 '(a b c d e f g h i))
(a b c)
```
Submit your code in a file called scheme_lab.scm.

Part 7: Iteration and printing

Enter and load the following code. What does it do? Why?
```
(let loop ((count 0))
  (display "Count = ")
  (display count)
  (newline)
  (if (< count 10) (loop (+ count 1))))
```
loop is being called as if it were a function. What does this mean? Is this iteration or recursion?

Enter the following code:

(define x 8)
(define y 0)
(define z 0)
(if (= x 8)
   (begin (set! y 2)
          (set! z 3))
   (begin (set! y 7)
          (set! z 9)))

What purpose does begin serve?