A Quick Scheme Tutorial

How to run the Scheme interpreter

There are two basic ways to execute a program which you write: with an interpreter, or with a compiler. A compiler takes your program and translates it into a format which the computer can run directly. It outputs the translated program as an executable, which you can execute directly. In CS 2 up till now, you've been using cc, which stands for C Compiler. An interpreter, on the other hand, executes your program line by line, deciding what to do on the fly. An interpreter has the advantage that it can be interactive, meaning it can execute a program as you type it in. The disadvantage of interpreters is that they interpreted code runs more slowly than compiled code, since the interpreter has to decide what each line means before it can execute it.

For this lab, you'll be using a Scheme interpreter. To start the interpreter, type scheme48 in a shell window. This will start the Scheme interpreter, which will then show its prompt: 

bradbert-8: scheme48
Welcome to Scheme 48 0.36 (made by sethml on Fri Nov 18 03:12:22 PST 1994).
Copyright (c) 1993, 1994 by Richard Kelsey and Jonathan Rees.
Please report bugs to scheme-48-bugs@martigny.ai.mit.edu.
Type ,? (comma question-mark) for help.
>
At this point, anything that you type will be interpreted, and the result will be printed. To exit scheme48, type ",exit". The remainder of this tutorial will be a sample scheme session. You may want to start up scheme48 now, and follow along with the examples...

Atoms

An atom is a fundamental unit in Scheme. Numbers are atoms. Numbers evaluate to themselves: 
> ; Anything starting with a semicolon is a comment.
> 1					; An integer.
1
> -562
-562
> 23.78					; A floating-point number.
23.78
> 99999999999999999999999999999999999	; Integers have no limits.
99999999999999999999999999999999999
> 2/3					; We can even use fractions!
2/3
> 4/8
1/2
Strings are also atoms which evaluate to themselves: 
> "This is a string"
"This is a string"
There are also atoms called symbols. Symbols must be prefixed by a single quote, since otherwise they are interpreted as variables (see below): 
> 'a
'a
> 'this-is-an-atom
'this-is-an-atom
> 'ATOMS-are-CASE-insensitive
'atoms-are-case-insensitive
> 'I/contain-weird^characters+666!
'i/contain-weird^characters+666!
There are also two special atoms, #t and #f, which are the cannonical true and false values. They don't need to be quoted: 
> #t
#t
> #f
#f

Errors

At this point, it's a good idea for you to know what to do if you make a mistake. When you enter something that scheme48 can't evaluate, it tells you what the error was, and goes into a debugging mode. The debugging mode probably won't be useful to you. To get out of it, press control-D. You can also type ,levels off (notice the comma) when you start up scheme48 to prevent it from going into the debugging mode. Here's an example: 
> forgot-a-quote

Error: undefined variable
       forgot-a-quote
       (package user)
1> ^D
> ,levels off   
Won't push command level on errors
> forgot-a-quote

Error: undefined variable
       forgot-a-quote
       (package user)
>

Lists

A list consists of space-seperated objects between parenthes, and like a symbol, must be quoted. Since the entire list is quoted, symbols within the list don't have to be: 
> '(1 2 3)
'(1 2 3)
> '(list of symbols)
'(list of symbols)
> '((list 1) (list 2))
'((list 1) (list 2))
> '()                           ; The empty list.
'()
Note that lists (as well as procedure calls, see below) can contain new-lines (they're the same as any other white space). This means that if you forget the proper number of closing parentheses, the Scheme interpreter will just sit there, waiting for you to finish your list.

Procedures

A procedure call looks like a list. The first element is the name of the procedure to call; the remaining elements are the arguments to pass to the procedure. Every procedure returns a value. 
> (+ 2 3)
5
> (+ (/ 6 3) 2)			; Calculate 6 / 3 + 2.
4
> (list 1 2 3)			; list puts its arguments into a list.
'(1 2 3)
> (list 'a 'b 'c)
'(a b c)
> +				; Procedure names evaluate to procedures!
'#{Procedure 139 +}
> list
'#{Procedure 230 list}
You notice above that the name of a procedure evaluates to a #{Procedure...} object. How can we create these objects? We must use a form called lambda: 
> (lambda (x) (+ x x))			; A procedure to double a number...
'#{Procedure 6755}
> ((lambda (x) (+ x x)) 8)		; We can call this procedure!
16
> ((lambda (x y) (/ (+ x y) 2)) 16 20)	; This procedure takes 2 arguments.
18

Definitions

We can create variables using define: 
> (define six 6)
> six
6
> (define up 'down)
> up
'down
So, by using define and lambda, we can create named functions: 
> (define double (lambda (x) (+ x x)))
> (define average (lambda (x y) (/ (+ x y) 2)))
> (double 5)
10
> (average -10 4)
-3

Some Useful Procedures

Numerical procedures include +, -, *, and /. There are also numerical comparison procedures =, <, >, <=, and >=: 
> (+ 6 7)
13
> (+ 1 2 3 4 5)
15
> (* 999999 999999)
999998000001
> (/ 12345 54321)
4115/18107
> (/ 3.1415 2)
1.57075
> (= 3 4)
#f
> (= 3 3)
#t
> (< 1.1 2)
#t
> (>= 3 4)
#f
Some other random procedures: 
> (equal? 'a 'b)		; equal? compares two objects.
#f
> (equal? 'a 'a)
#t
> (equal? 1 1)
#t
> (equal? '(a b (c d)) '(a b (c d)))
#t
> (null? '(a))			; null? returns #t only on the empty list.
#f
> (null? '())
#t
> (not #t)
#f
> (not #f)
#t
> (string>? "abc" "def")	; Compare two strings.
#f
> (string>? "def" "abc")
#t
Some list procedures (these will become clearer in the section below): 
> (car '(a b c))	; car returns the first element in the list...
'a
> (cdr '(a b c))	; cdr returns the rest.
'(b c)
> (cdr '(b c))
'(c)
> (cdr '(c))
'()
> (cdr '())

Warning: argument type error
         (cdr '())
         (procedure wants: (:pair))
         (arguments are: (:null))

Error: exception
       (cdr '())
> (cons 'a '(b c))
'(a b c)
> (cons (car '(a b c)) (cdr '(a b c)))
'(a b c)
> (append '(first list) '(second list))
'(first list second list)

How Lists Work

You recall that when you created a singly-linked list in C, you created a data structure something like this: 
    struct list_element {
      void *data;
      struct list_element *next;
    }
You notice that the element structure essentially consists of two pointers. In Scheme, lists are also constructed of data structures consisting of two pointers, but the pointers are allowed to point to any type of object. These structures are called pairs. You could think of a pair as: 
    struct pair {
      void *car;
      void *cdr;
    }
(Historical footnote: the fields are named car and cdr since the IBM mainframe that Lisp was first implemented on used registers with those names to store the data. Unfortunately, the names stuck.)

A list consists of a sequence of pairs, each of which contains a pointer to a list element in its car, and a pointer to the next element in the list in its cdr. The cdr of the last element in the list points to the empty list. For instance, the list '(1 2 3) would be stored in memory as: 

      +-----+     /->+-----+     /->+-----+
      | car --> 1 |  | car --> 2 |  | car --> 3
      +-----+     |  +-----+     |  +-----+
      | cdr ------/  | cdr ------/  | cdr --> '()
      +-----+        +-----+        +-----+
Now car, cdr, and cons should make a little more sense. A list is just the first pair in the list. car returns the car field of a pair, cdr returns the cdr field of a pair, and cons returns a newly created pair, with the first argument in its car and the second argument in its cdr. Note that you can create malformed lists this way. For instance, (cons 'a 'b) creates the pair: 
      +-----+    
      | car --> 'a
      +-----+    
      | cdr --> 'b
      +-----+
This is represented as '(a . b) on the screen. Don't worry too much about malformed lists; you usually want to avoid them.

Conditionals

Now we need some mechanism to make decisions in our Scheme programs. This is provided by the cond form. The general form of a cond is: 
      (cond
	(condition1 result1)
	(condition2 result2) . . . )
result1 will be returned if condition1 is not #f, result2 will be returned if condition2 is not #f and condition1 was #f, etc... You always want at least one result, so you should always end your conds with a term with #t as the condition, so that term will be evaluated if all other conditions were false. Here are some examples of using cond: 
> (define zeroness
    (lambda (x)
      (cond
	((equal? 0 x) 'zero)
	(#t 'non-zero))))
> (zeroness 0)
'zero
> (zeroness 4)
'non-zero
> (define sign
    (lambda (n)
      (cond
	((> n 0) 1)
	((< n 0) -1)
	(#t 0))))
> (sign 67.3)
1
> (sign -12)
-1
> (sign 0)
0

Loading Files

For this assignment, you're going to want to save your functions in a file, both so that you can easily edit a function and re-load it and so that you can actually turn in the work you've done. Suppose you have a file, say fib.scm, containing: 
(define fib
  (lambda (n)
    (cond
      ((or (= n 0) (= n 1)) 1)
      (#t (+ (fib (- n 1)) (fib (- n 2)))))))
Now, in Scheme48: 
> (load "fib.scm")
fib.scm .
> (fib 20)
10946

Recursion

It turns out that you can do just about anything in Scheme with the parts of the language you've just learned about. 'How do I implement loops?' you wonder... The answer: you don't, you use recursion instead. Suppose we want to find a factorial... We know that 0! = 1 and n! = n * (n-1)!. That leads to the following recursive definition: 
> (define factorial
    (lambda (n)
      (cond
	((= 0 n) 1)
	(#t (* n (factorial (- n 1)))))))
> (factorial 0)
1
> (factorial 5)
120
> (factorial 50)
30414093201713378043612608166064768844377641568960512000000000000
Now for a procedure to find the length of a list. An empty list is of length 0. A non-empty list is one item longer than its cdr. This can be implemented as: 
> (define list-length
    (lambda (l)
      (cond
	((null? l) 0)
	(#t (+ 1 (list-length (cdr l)))))))
> (list-length '(a b c d e))
5
> (list-length '())
0
> (list-length 123)

Error: exception
       (cdr 123)
Now for a more powerful procedure: map. map takes a list and a function and returns a list of the return values of the function, when the function is applied to each element of the list. 
> (define map
    (lambda (f l)
      (cond
	((null? l) '())
	(#t (cons
	      (f (car l))
	      (map f (cdr l)))))))
> (map zero? '(1 0 3 0 6))	; zero? happens to be built-in...
'(#f #t #f #t #f)
> (map (lambda (n) (* 2 n)) '(1 2 3 4 5 6))
'(2 4 6 8 10 12)
By the way, map is actually built into Scheme, so if you try typing in the above it might give you some warnings about replacing a built-in procedure.

Yay!!!

You now know enough about Scheme to do this week's lab. Back to lab 8.

SML