Scheme

Scheme is a minimalist dialect of Lisp created in 1975 at MIT. Unlike Common Lisp’s “everything included” approach, Scheme embraces minimalism - its specification is famously short, yet the language is provably Turing-complete and has profoundly influenced programming language theory and design.

History & Origins

Scheme was born from an experiment. In 1975, Gerald Jay Sussman and Guy L. Steele Jr. at the MIT AI Laboratory wanted to understand Carl Hewitt’s Actor model of computation. They created a tiny Lisp interpreter to study actors, and in the process discovered something profound: actors and lambda expressions (closures) were mathematically equivalent.

This insight led to the “Lambda Papers” - a series of influential memos that established Scheme’s theoretical foundations and influenced programming language design for decades. The papers demonstrated that:

• Lambda expressions could model any control structure
• Actors and closures were fundamentally the same
• Tail-call optimization was essential for efficient recursion

The Name

The name “Scheme” was chosen because Sussman and Steele originally wanted to call it “Schemer” as a tribute to the Planner and Conniver AI languages. However, the ITS operating system at MIT limited filenames to 6 characters, so “Schemer” became “Scheme.”

Academic Influence

Scheme’s greatest impact may be in education. In 1984, Harold Abelson and Sussman wrote “Structure and Interpretation of Computer Programs” (SICP), using Scheme as the vehicle for teaching fundamental programming concepts. SICP became the textbook for MIT’s introductory computer science course (6.001) and influenced curricula at universities worldwide.

Core Features

Minimalism by Design

Scheme’s specification is deliberately small. R5RS (the most widely implemented standard) can be printed in about 50 pages. This minimalism means:

• Fewer concepts to learn
• Elegant, orthogonal design
• Implementation independence
• Focus on fundamentals

First-Class Procedures

Functions in Scheme are true first-class citizens:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

;; Functions can be passed as arguments
(define (apply-twice f x)
  (f (f x)))

(apply-twice (lambda (x) (* x 2)) 3)  ; Returns 12

;; Functions can return functions
(define (make-adder n)
  (lambda (x) (+ x n)))

(define add-5 (make-adder 5))
(add-5 10)  ; Returns 15

Proper Tail Calls

Scheme requires implementations to optimize tail calls, making recursive algorithms as efficient as loops:

1
2
3
4
5
6
7

;; This will not stack overflow, regardless of n
(define (factorial n)
  (define (fact-iter n acc)
    (if (= n 0)
        acc
        (fact-iter (- n 1) (* n acc))))
  (fact-iter n 1))

Lexical Scoping

Scheme pioneered lexical (static) scoping in Lisp, where variable bindings are determined by where they appear in the source code:

1
2
3
4
5
6
7
8
9

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

(define counter (make-counter))
(counter)  ; Returns 1
(counter)  ; Returns 2

Continuations

Scheme’s call/cc (call with current continuation) captures the “rest of the computation” as a first-class value:

1
2
3

(call/cc
  (lambda (escape)
    (+ 1 (escape 42) 999)))  ; Returns 42, skipping the + 1 and + 999

This powerful primitive can implement exceptions, generators, coroutines, and more.

Hygenic Macros

Scheme’s macro system (syntax-rules) automatically handles variable capture issues that plague traditional Lisp macros:

1
2
3
4

(define-syntax when
  (syntax-rules ()
    ((when test expr ...)
     (if test (begin expr ...)))))

Modern Implementations

GNU Guile

Guile is the official extension language of the GNU Project:

• Full R7RS support
• Fast compiler and VM
• Extensive library ecosystem
• Used in GIMP, GnuCash, Guix

Chez Scheme

One of the fastest Scheme implementations:

• Produces high-quality native code
• Open-sourced by Cisco in 2016
• Compiles to efficient machine code
• R6RS compliant

Chicken Scheme

Practical Scheme with excellent FFI:

• Compiles to C for portability
• Large egg (package) ecosystem
• Focus on real-world applications
• Active community

Racket

Originally PLT Scheme, now its own language:

• Excellent IDE (DrRacket)
• Great for education
• Language-oriented programming
• Extensive documentation

Other Implementations

• Gambit - High-performance, compiles to C
• MIT/GNU Scheme - Historic reference implementation
• Bigloo - Compiles to C, Java, and .NET
• S7 - Embedded in audio applications

Scheme vs Common Lisp

The R*RS Standards

Scheme has a unique standardization process through the “Revised^n Report on Scheme” (R*RS):

• R5RS (1998) - Most widely implemented, very stable
• R6RS (2007) - More features but controversial
• R7RS-small (2013) - Return to minimalism
• R7RS-large - In progress, modular expansion

The community split over R6RS led to two parallel paths: those wanting a small, pure language (R7RS-small) and those wanting practical features (R7RS-large).

Scheme’s Lasting Influence

Scheme’s ideas have spread far beyond its user base:

JavaScript

Brendan Eich was influenced by Scheme when creating JavaScript:

• First-class functions
• Closures
• Dynamic typing
• Prototype-based objects (from Self, influenced by Scheme)

Other Languages

• Ruby - First-class closures, blocks
• Clojure - Modern Lisp on JVM
• Lua - Minimalist design, closures
• Python - Lambda expressions, functional features
• Haskell - Continuation-passing style

Learning Scheme

Scheme remains an excellent teaching language because:

1. Few special cases - Almost everything is an expression
2. Consistent syntax - S-expressions for everything
3. Powerful abstractions - First-class functions from day one
4. Mathematical foundation - Lambda calculus made practical
5. SICP - One of the best CS textbooks ever written

The Community Today

The Scheme community is smaller but dedicated:

• schemers.org - Community hub and resources
• r/scheme - Reddit community
• comp.lang.scheme - Historic Usenet group
• IRC - #scheme on Libera.Chat
• Scheme Workshop - Annual academic conference

Each implementation also has its own community and resources.

Why Scheme Still Matters

In an era of complex, feature-rich languages, Scheme’s minimalism is a valuable counterpoint:

• Educational value - Teaches programming fundamentals without distraction
• Theoretical foundation - Connects to lambda calculus and CS theory
• Metaprogramming - Demonstrates the power of treating code as data
• Influence - Understanding Scheme helps understand modern languages
• Elegance - Proof that less can be more

Scheme shows that a language doesn’t need hundreds of features to be powerful. Its influence on JavaScript alone means billions of developers use Scheme’s ideas daily, whether they know it or not.