Scheme for Common Lispers

The Scheme dialect of Lisp was created in 1975 by Guy Steele and Gerry Sussman to explore ideas in programming-language semantics. They showed that a powerful language can be made ``not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary''. Scheme pioneered lexical scope in Lisp, first-class continuations, and tail recursion, and more recently added an advanced macro system. It's the best-known Lisp dialect after Common Lisp (which it influenced).

This note summarizes the differences from CL that might slow down a CL programmer trying to read a Scheme program; people without a CL background, or wanting to write programs of their own, should see the references.

Values, Functions, and Bindings

In CL each variable has a value binding and a function binding. In an expression like (foo bar), the evaluator uses FOO's function binding and BAR's value binding. If you wanted to use the value of BAR as the function, and the function FOO as its argument, you'd have to write (funcall bar #'foo) instead.

Scheme variables have only a value binding, and functions are just another kind of value. Thus (foo bar) and (bar foo) are equally acceptable. Scheme evaluates each subexpression in the same way (whether it's in function position or argument position), then applies the function to the arguments. Thus we get:

> ((if (= 0 0) * +) 5 2)
10
> ((if (= 1 0) * +) 5 2)
7

Top-level bindings are introduced with DEFINE:

> (define pi 3.14159)
PI
> (/ pi 2)
1.570795

Procedures are created with LAMBDA (no #' needed):

> (define circle-area
    (lambda (radius)
      (* pi radius radius)))
CIRCLE-AREA
> (circle-area 10)
314.159

There's a convenient abbreviation for creating and binding a procedure at the same time, like CL's DEFUN:

> (define (circle-area radius)
    (* pi radius radius))
CIRCLE-AREA

Now for an example of the kind of code this design makes possible:

> (define (derivative f dx)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x))
         dx)))
DERIVATIVE
> ((derivative sin 0.001) 0)
0.9999998333333416

As should be clear by now, Scheme is lexically scoped, like CL. Scheme tends to encourage more use of nested scopes. In particular, DEFINE can create new local bindings inside a function:

(define (blah)             ; come up with a better example...
  (define (foo) 55)
  (define (woo) 42)
  (+ (foo) (woo)))

This particular example could have been written with LABELS in CL; the internal definitions may be mutually recursive.

Control Structures

Scheme implementations are properly tail-recursive. This means that a function call in `tail position' is like a GOTO in that it pushes nothing on the stack. For example, we can write

(define (repeat-forever)
  (display "I will not play with Scheme in class.")
  (repeat-forever))

with complete confidence that a call to REPEAT-FOREVER won't cause a stack overflow. Since Scheme gives us this guarantee, it doesn't have to supply any other control structure; while it does have a few built-in iteration constructs, like DO, they're simply defined as macros that expand into function calls.

Tail-call optimization doesn't just simplify the language; it also makes it easier to structure some programs on a larger scale. For example, we can implement a virtual machine in a data-driven way:

(define (get-action instruction)           ; look up an action procedure
  ...)

(define (set-action! instruction action)   ; install an action procedure
  ...)

(define (go program-counter accumulator)   ; main loop of the simulator
  ((get-action (memory-fetch program-counter))
   (+ 1 program-counter)
   accumulator))

(set-action! increment                     ; define the increment instruction
  (lambda (program-counter accumulator)
    (go program-counter
        (+ 1 accumulator))))

(set-action! jump-if-zero                  ; define the jump-if-zero instruction
  (lambda (program-counter accumulator)
    (go (if (= 0 accumulator)
            (memory-fetch program-counter)
            (+ 1 program-counter))
        accumulator)))

; remaining instructions elided...

Note that GO makes a tail call to a handler function that's unknown at compile time, and each handler typically ends in a tail call back to GO. Without fully general tail-call optimization, we'd have to complicate the interface between GO and the handlers.

For nonlocal transfers of control, Scheme provides a special kind of procedure called a continuation. Continuations are created by the built-in procedure CALL-WITH-CURRENT-CONTINUATION, and invoked by calling them like any other procedure. The difference is, when invoked, a continuation abandons the current control context and replaces it with the context of its creation. This is sort of like CATCH and THROW in CL: CATCH captures a context, and THROW abandons the current context and goes back to an old one. The difference is, catch tags are dynamically scoped and `die' after returning, while continuations are first-class objects that live until they are garbage-collected. This extra flexibility makes it possible to express just about any control structure directly in Scheme, including threads, coroutines, and Prolog-style nondeterminism. The references explain these more sophisticated uses of continuations.

Here is an example acting like CATCH and THROW, for a nonlocal exit:

(define (all-atoms-are-numeric? tree)
  (call-with-current-continuation
   (lambda (return)                     ;bind RETURN to the current cont

     (define (walk tree)
       (cond ((null? tree))
             ((pair? tree)              ;pair? is like consp
              (walk (car tree))
              (walk (cdr tree)))
             ((number? tree))
             (else (return #f))))       ;found a non-number -- return false

     (walk tree)
     #t)))                              ;else return true

Scheme's counterpart to UNWIND-PROTECT is called DYNAMIC-WIND, because it has to guard against not just unwinding but also rewinding.

CALL-WITH-CURRENT-CONTINUATION is often abbreviated to CALL/CC.

Datatypes

Most Scheme datatypes are in CL.

The most important difference is with CL's value NIL. In CL, NIL is the empty list, the false boolean value, and a symbol. In Scheme, these three roles are played by distinct objects: () is the empty list, #f the false value, and NIL an (ordinary) symbol. #t is the canonical true value, and T is just another symbol. In conditional tests, any value other than #f is considered true.

There is a rich tower of number types, along with an explicit distinction between exact and inexact numbers. Operations on exact numbers try to preserve exactness, while inexactness is contagious.

Scheme has only one-dimensional zero-based arrays, called vectors. Lists, vectors, and strings are separate types, not subtypes of a more general sequence type.

More Syntax

SET! is like CL's SETQ. The variable assigned to must already be bound, and the return value of the SET! expression is unspecified. (Mutator operations, by convention, have a name ending in !, like SET-CAR! for RPLACA, VECTOR-SET! for ASET, etc.) There is no standard SETF equivalent.

BEGIN is like PROGN.

COND and CASE can end with an ELSE-clause, like so:

(cond ((number? x) "A number.")
      ((string? x) "A string.")
      (else "Beats me!"))

Also COND has a special syntax for using the result of a test -- for example, in

(cond ((assoc key a-list) => cdr)
      (else #f))

if the call to ASSOC returns a pair, then we return the cdr of that pair, otherwise we return false. In place of CDR in this example, we could have any expression that evaluates to a function taking one argument.

LETREC is much like LABELS:

(letrec ((even? (lambda (n) (if (= n 0) #t (odd? (- n 1)))))
         (odd?  (lambda (n) (if (= n 0) #f (even? (- n 1))))))
  (even? 42))

would be, in CL:

(labels ((even? (n) (if (= n 0) t (odd? (- n 1))))
         (odd?  (n) (if (= n 0) nil (even? (- n 1)))))
  (even? 42))

Finally, there's a named-LET form for convenient iteration:

(let counting ((n 10))
  (cond ((< 0 n)
         (write n)
         (counting (- n 1)))))

This binds COUNTING as a local procedure, initializes its arguments with the LET-style binding-list that follows, and enters the rest of the LET-form as its body. It can be implemented as a macro that expands to:

((letrec ((counting (lambda (n)
                      (cond ((< 0 n)
                             (write n)
                             (counting (- n 1)))))))
   counting)
 10)

Multiple Arguments and Multiple Values

Scheme procedures can take a variable number of arguments, using an improper lambda-list. For example,

> (define (list . arguments) arguments)
LIST
> (list 1 2 3)
(1 2 3)
> (list)
()

The variable after the dot gets bound to a list of all remaining arguments, just like an &REST variable in CL.

Procedures can also return a variable number of values. VALUES is the built-in procedure for returning them, and CALL-WITH-VALUES is for binding the results in the caller. These two procedures are a recent addition to the language; another common idiom for returning multiple values is to pass them to a receiver:

> (define (divide numer denom receiver)
    (receiver (quotient numer denom)
              (remainder numer denom)))
DIVIDE
> (divide 22 7 list)
(3 1/7)

The receiver is often termed a continuation instead, with its name abbreviated to K, although it has nothing directly to do with CALL-WITH-CURRENT-CONTINUATION. (The relation is that the procedure CALL/CC creates can be thought of as a reified receiver from the underlying implementation, but if that sounds like gobbledygook it's not important.)

Macros

The standard macro system is high-level and hygienic: high-level in that macro transformers are written in a pattern-matching sublanguage, and hygienic in that variable-capture bugs can't happen. In this example we define a macro like the standard OR form:

(define-syntax my-or
  (syntax-rules ()
    ((my-or) #f)
    ((my-or e) e)
    ((my-or e1 e2 ...)
     (let ((temp e1))
       (if temp temp (my-or e2 ...))))))

There are three patterns, (my-or), (my-or e), and (my-or e1 e2 ...), each with a corresponding template. Naively we can think of it working this way: a pattern matches an expression if each keyword or constant in the pattern matches the corresponding content in the expression, each variable matches any subexpression, and ... means the preceding subpattern matches 0 or more successive subexpressions. MY-OR is a keyword in the pattern, and we can use other keywords by adding them to the empty list right after SYNTAX-RULES. Then a subsequent MY-OR expression gets replaced with the template for the first pattern that matches, with pattern variables instantiated from the original expression.

That naive view is wrong; the actual matching and replacement get done in an environment-sensitive way that eliminates all unintentional variable captures. The R5RS report goes into more detail.

Besides DEFINE-SYNTAX, there are also LET-SYNTAX and LETREC-SYNTAX for defining macros locally. There are lower-level macro systems that allow arbitrary computation and selective violation of hygiene, but none is standard.

What's Missing

Scheme lacks several standard facilities of a modern general-purpose language: modules, exception-handling, a rich standard library, and an object system. It's possible to build them all on top of the base language with little extra support from the implementation, but there's no consensus on what the resulting system should look like. Standard Scheme isn't likely to supplant CL for industrial-strength use; instead it's most useful for research and education and as a glue language for other systems.

Dictionary

An incomplete list of built-in functions whose meaning may not be instantly obvious:

assoc                 assoc :test equal
assq                  assoc :test eq
assv                  assoc
call-with-input-file  open an input file, call receiver with port, then close
call-with-output-file similar
char-ci<?             case-insensitive < for characters
char-ci=?, etc.       similar
display               princ
eof-object?           #t iff argument is a special object indicating end of file
eq?                   eq
eqv?                  eql
for-each              mapc
list-ref              nth
list-tail             nthcdr
map                   mapcar
member                member :test equal
memq                  member :test eq
memv                  member
newline               terpri
pair?                 consp
peek-char             read next character, then push it back
set-car!              rplaca
set-cdr!              rplacd
string-ci<?           case-insensitive < for strings
string-ci=?, etc.     similar
string-ref            aref on strings
string-set!           aset on strings
symbol->string        intern
vector-ref            aref
vector-set!           aset
write                 prin1

References

[R5RS] Kelsey, Clinger, and Rees, eds., Revised^5 Report on the Algorithmic Language Scheme.

Abelson and Sussman, Structure and Interpretation of Computer Programs, 2nd ed. MIT Press, Cambridge, 1996.

Sitaram, Teach Yourself Scheme in Fixnum Days.

http://www.schemers.org


Home   |   © 1994-2003 by Darius Bacon