Scheme

Scheme was created at MIT in 1975 by Guy Steele and Gerald Sussman as a small, clean Lisp. The language standard is a few dozen pages long, yet it offers closures, proper tail calls and continuations. It became the teaching language of Structure and Interpretation of Computer Programs.

Paradigm: Functional Programming

What Makes Scheme Special

  • Minimal core. A handful of forms (lambda, if, define, let, set! and a few more) are enough. Everything else is built from them.
  • Lexical closures. A function remembers the variables in scope where it was created, which is what makes counters, objects and callbacks possible.
  • Proper tail calls. The standard requires that a call in tail position reuses the current frame, so recursion is as cheap as a loop and needs no loop keyword.
  • First-class continuations. call/cc captures "the rest of the computation" as a value. Exceptions, generators and coroutines can be built from it.
  • Hygienic macros. syntax-rules macros avoid accidental name capture, so new syntax stays safe.

Example: A closure and a tail-recursive loop

(define (make-counter)
  (let ((n 0))
    (lambda ()
      (set! n (+ n 1))
      n)))

(define next! (make-counter))
(next!)                       ; => 1
(next!)                       ; => 2

(define (sum-to n acc)
  (if (= n 0)
      acc
      (sum-to (- n 1) (+ acc n))))

(sum-to 1000000 0)            ; => 500000500000

How It Works

  • make-counter returns a lambda that closes over the local variable n. Each counter has its own private state, as in an object with one field.
  • Calling next! twice returns 1 and then 2 because the closure mutates its captured variable.
  • sum-to calls itself as the very last action, a tail call. Scheme guarantees this runs in constant stack space, so a million iterations are safe.
  • There is no for or while anywhere: recursion is the loop.

History and Where It Is Used

Scheme is used to teach programming and language design, and implementations such as Chez Scheme, Guile (the GNU extension language), Chicken and Gambit are used in production. Racket, a descendant, is popular for education and language-oriented programming. See the PGP index for Racket in the hybrid languages.

Learn More