Scheme

Scheme is a minimalist, multi-paradigm programming language and a dialect of Lisp, created in 1975 by Guy L. Steele Jr. and Gerald Jay Sussman at the MIT Artificial Intelligence Laboratory. It was the first Lisp dialect to use lexical scope by default, the first to require tail call optimization in its language definition, and one of the first languages to expose first-class continuations ^[1][13]. Scheme is governed by a deliberately tiny core specification, summarized by the design maxim that opens its standard reports: "Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary." ^[5][11]

Scheme began as a small Lisp interpreter that Steele and Sussman wrote to study Carl Hewitt's actor model of concurrent computation. In the course of building it they discovered that closures and lambda expressions were equivalent to actors and that both lay at the heart of programming language semantics. That insight, recorded in MIT AI Memo 349 (December 1975) and a series of follow-up papers known as the Lambda Papers, made Scheme one of the most theoretically influential languages of its era ^[1][2]. The R7RS report states the language's central claim plainly: a "very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language." ^[11]

The entire R5RS report fits in roughly 50 pages, a deliberate contrast to the roughly 1,100-page ANSI standard for Common Lisp ^[5][6]. The textbook Structure and Interpretation of Computer Programs (SICP) by Harold Abelson and Sussman, which used Scheme throughout, served as the text for MIT's introductory course 6.001 from 1984 until 2007 and became one of the most influential computer science textbooks of the late twentieth century, shaping a generation of programmers and AI researchers ^[3]. Although Scheme has never had the industrial reach of Common Lisp, Clojure, or Python, it remains a touchstone for language research, symbolic AI, and CS education. Its dialects, including Racket, Guile, Chicken Scheme, and Chez Scheme, continue to be developed and used in research, teaching, and some production systems.

When and why was Scheme created?

In autumn 1975, Sussman and Steele were studying Carl Hewitt's PLASMA language and the actor model that underlay it. Hewitt's actors were independent computational agents that communicated by message passing, and the formalism was being proposed as a foundation for concurrent computation and object orientation. To explore the model, Sussman and Steele built a tiny interpreter in MacLisp that supported actors, treating each actor creation as a procedure definition and each message send as a procedure call.

The interpreter was originally called "Schemer" in the style of earlier MIT Lisp dialects called Planner and Conniver, but the ITS operating system at MIT limited file names to six characters, so it became "Scheme." The initial implementation was about a thousand lines of MacLisp and is described in MIT AI Memo 349, "Scheme: An Interpreter for Extended Lambda Calculus," published in December 1975 ^[1].

What Sussman and Steele found surprised them. When they examined their actor implementation closely, they realized that the code they had written for actors was almost identical to the code they had written for ordinary procedure calls. Actors and closures, message sends and procedure invocations, turned out to be the same thing dressed in different syntax. That observation became the seed of a series of papers that reshaped how computer scientists thought about evaluation, compilation, and the nature of procedure calls.

The Lambda Papers, written between 1975 and 1980, included several landmarks. "Lambda: The Ultimate Imperative" (1976) showed that imperative control structures such as goto, while, and case could all be expressed as syntactic sugar over function application. "Lambda: The Ultimate Declarative" (1976) made the analogous case for declarative constructs. "Debunking the Expensive Procedure Call Myth, or, Lambda: The Ultimate GOTO" (1977) argued that with proper tail call handling, a procedure call is no more expensive than a goto, and that compilers should therefore implement loops and other control flow as ordinary calls. Steele's 1978 master's thesis, "Rabbit: A Compiler for SCHEME," turned these ideas into a working compiler that produced efficient native code ^[4].

The practical consequence was that Scheme programmers could write recursive procedures with the confidence that the compiler would not blow the stack on a tail recursion. The theoretical consequence was that lambda calculus, once viewed as an abstract mathematical formalism, was in fact a perfectly serviceable model of how real programming languages worked.

What are Scheme's defining features?

Scheme is dynamically typed, homoiconic, and based on s-expressions. Programs are written as nested parenthesized lists that are themselves valid data structures. The combination of homoiconicity and a small core gives Scheme a metaprogramming culture in which user-defined macros and embedded domain specific languages are routine.

Several design decisions distinguish Scheme from other Lisp dialects:

• Lexical scope by default. Scheme was the first Lisp dialect to standardize on lexical scoping, in which a free variable refers to the binding visible at the place where the procedure was defined ^[13]. Earlier Lisps, including Emacs Lisp and original MacLisp, used dynamic scope. Common Lisp eventually adopted lexical scope for let bindings, in part because of Scheme's influence.
• First-class procedures. Procedures are values that can be passed as arguments, returned, and stored in data structures. Scheme has first-class functions.
• Mandatory tail call optimization. A procedure call in tail position must not consume any additional stack space. This is a language requirement, not an implementation detail, so programmers can rely on iterative procedures expressed as recursion to run in constant space ^[15].
• First-class continuations. Scheme exposes the current continuation of any expression as a first-class procedure through call-with-current-continuation, abbreviated call/cc. The name call-with-current-continuation was coined in 1982 by the implementors of Scheme 311 ^[13].
• Single namespace (Lisp-1). Scheme uses a single namespace for variables and procedures, in contrast to Common Lisp's separate function and value namespaces. One writes (map f xs) rather than (mapcar #'f xs). The Lisp-1 versus Lisp-2 terminology was coined in a 1988 paper by Richard P. Gabriel and Kent Pitman and remains a long-running debate in the broader Lisp community.
• Hygienic macros. Since R4RS, Scheme has standardized hygienic macros through syntax-rules, a pattern-based macro system that automatically avoids accidental variable capture. R6RS added the more powerful syntax-case procedural macro system.
• Numeric tower. Scheme defines a tower of numeric types (integer, rational, real, complex) with automatic promotion. Exact rational results remain exact unless the programmer explicitly converts to inexact.
• Garbage collection. All Scheme implementations use garbage collection.
• Interactive REPL. Scheme is typically used through a read-eval-print loop.

How are Scheme standards organized?

Scheme has an unusually rich standardization history. The series of Revised Reports (RnRS) has gone through seven major revisions, plus an IEEE standard and ANSI ratification. The reports are produced by an editor or small editorial committee, and major revisions have sometimes been contentious.

Scroll sideways for more →

In parallel with the formal reports, the Scheme Requests for Implementation (SRFI) process collects optional library specifications at srfi.schemers.org. SRFI 1 (list library), SRFI 9 (records), SRFI 13 (strings), and SRFI 41 (streams) are among the most widely implemented.

Why was R6RS controversial?

The R6RS report, ratified in 2007 after several years of work, attempted to bring Scheme up to date with features that working programmers expected from a modern language: a portable library system, defined exception handling, Unicode support, bytevectors, hash tables, sortable records, and procedural macros via syntax-case. The result was roughly 90 pages plus 70 pages of standard libraries, several times the size of R5RS ^[6].

The expansion was controversial. Critics argued that the bigger language betrayed Scheme's founding principle of minimalism, locked in design choices that ought to remain implementation-defined, and made the language harder to teach and harder to implement from scratch. Proponents responded that without a portable library system Scheme code could not be shared between implementations.

Well-known Scheme implementers including Will Clinger, Marc Feeley, and Robby Findler published critiques of specific R6RS decisions. Several major implementations declined to adopt the new standard. Chicken Scheme, Gambit Scheme, and MIT/GNU Scheme all stayed with R5RS as their default, supporting selected R6RS features only as add-on libraries. Racket, heavily involved in the R6RS process, eventually moved away from being a Scheme at all and developed its own language family.

The R7RS process, organized in 2009, was an explicit response to the controversy. The working group split the new standard into two layers. R7RS-small, finalized in 2013, is intended to be a clean, R5RS-sized core that any implementation can support. R7RS-large is a separate, ongoing effort to define libraries on top of that core, drawing heavily on SRFIs ^[11].

What are continuations and call/cc?

A continuation is a representation of "what happens next" in a program: the rest of the computation viewed as a function from the current expression's value to the program's eventual answer. Most languages keep continuations implicit, expressed only as the program counter and the call stack. Scheme exposes continuations as ordinary first-class values through call-with-current-continuation, abbreviated call/cc.

When call/cc is invoked, it captures the current continuation and passes it to the procedure given as its argument. The procedure can return normally, or it can invoke the continuation, in which case control jumps back to the original call site of call/cc and that call appears to return the value passed to the continuation. Because the continuation is a first-class value, it can be stored, passed around, and even invoked multiple times.

First-class continuations are extraordinarily powerful. They are sufficient to implement, as user-level libraries, every other control construct found in mainstream languages: exceptions, generators, coroutines, cooperative threads, and backtracking search. Racket's web server uses continuations to write web applications as ordinary single-threaded programs, with each HTTP request and response captured by call/cc so the program can suspend itself between user interactions.

Which Scheme implementations are most important?

Scheme has dozens of implementations, more than most languages of comparable popularity; community registries list more than 75 distinct Scheme systems ^[13]. The diversity is partly a consequence of the small core: a competent compiler writer can produce an R5RS-conformant implementation in a few thousand lines, and many graduate students have done so as a learning exercise.

Scroll sideways for more →

Most implementations support a substantial subset of R5RS, and several support R6RS or R7RS-small. Cross-implementation portability remains a concern, partly addressed by SRFIs.

How did Racket grow out of Scheme?

Racket began life in 1995 as PLT Scheme, founded by Matthias Felleisen at Rice University and developed primarily by Felleisen, Matthew Flatt, Robby Findler, and Shriram Krishnamurthi. The project's initial goal was to produce a teaching-oriented Scheme with a friendly IDE, DrScheme (later DrRacket), and a graduated series of teaching languages aligned with the textbook How to Design Programs (HtDP).

Over the next fifteen years PLT Scheme accumulated features that pushed it well beyond standard Scheme. The team added a module system, a contract system inspired by Eiffel, immutable lists by default, a new macro expander, native support for graphical programming, and an extensive standard library. By 2010 the language was sufficiently distinct from any traditional Scheme that the team renamed it Racket, in part to signal that its goals had diverged from R5RS or R6RS conformance.

A distinctive Racket feature is the #lang mechanism, which lets a single source file declare the language it is written in. The standard distribution ships with #lang racket (the default), #lang typed/racket (a gradually typed dialect), #lang scribble (a documentation language), #lang slideshow (for slide decks), #lang htdp/bsl (Beginning Student Language), and dozens of others. Users can write their own #lang languages, which Racket supports as a first-class concept under the heading of language-oriented programming.

Racket is widely used in CS education, including at Northeastern, Brown, Indiana, Northwestern, and Utah. The Bootstrap project, run by Krishnamurthi and Emmanuel Schanzer, brings Racket-based curricula to middle and high school students through algebra, physics, and data science modules. Beautiful Racket by Matthew Butterick is an accessible introduction to language-oriented programming using Racket. In 2021 Racket version 8.0 switched its default runtime from a custom bytecode virtual machine (Racket BC) to one built on Chez Scheme (Racket CS), gaining substantial performance and maintainability improvements while preserving full compatibility; the changeover replaced roughly 200,000 lines of C with about 150,000 lines of Scheme and Racket ^[7].

How did Scheme shape computer science education?

Few programming languages have shaped computer science education as deeply as Scheme. Two textbooks in particular set the tone.

Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman with Julie Sussman, was published by MIT Press in 1984 with a second edition in 1996. It served as the primary text for MIT's introductory CS course 6.001 from fall 1984 through its final offering in fall 2007 and was adopted by dozens of other universities. SICP teaches programming as the construction of abstractions, the design of evaluators, and the management of state and modularity. Its later chapters develop a metacircular evaluator (a Scheme interpreter written in Scheme), a register machine simulator, and a compiler. The second edition is freely available online from MIT Press under a Creative Commons license ^[3].

How to Design Programs (HtDP), by Felleisen, Findler, Flatt, and Krishnamurthi, takes a different approach. Where SICP emphasizes computational abstractions and the theoretical underpinnings of programming, HtDP teaches a step-by-step "design recipe" for constructing programs from data definitions. HtDP is paired with a sequence of teaching languages in DrRacket that gradually introduce features as students master earlier ones. The first edition appeared in 2001, with a second in 2018 ^[8].

Daniel Friedman and Matthias Felleisen's The Little Schemer (originally The Little LISPer, 1974) is an idiosyncratic introduction to recursion using a question-and-answer format. Its sequels include The Seasoned Schemer and The Reasoned Schemer. The series has remained in print for half a century.

For decades MIT's 6.001 was a rite of passage for incoming computer science students. The course shaped the style of curricula at many other institutions and produced a generation of programmers who internalized SICP's lessons about evaluation, environments, and abstraction. When MIT replaced 6.001 with a Python-based course in 2009, the change was widely debated. Sussman has argued that the shift reflected a change in the nature of programming itself, with library composition replacing first-principles construction as the dominant activity.

How is Scheme used in AI and CS research?

Scheme has had less direct industrial use in AI than Common Lisp, partly because Common Lisp standardized first and partly because Scheme's minimalism made certain AI features the user's responsibility. SICP nevertheless contains substantial symbolic AI material: a query-driven logic programming system in chapter 4, a non-deterministic evaluator using the amb operator, and a discussion of pattern matching and unification. Generations of MIT students wrote miniature John McCarthy-style logic systems as 6.001 problem sets, learning the core machinery of symbolic reasoning, search, and rule-based inference by building interpreters from scratch.

MIT's introductory artificial intelligence course 6.034 used Scheme through the 1990s, and MIT's compilers and programming languages courses continued to assume Scheme literacy for many years. The MIT AI Laboratory was the principal home of Scheme research through the 1980s, with Sussman, Marvin Minsky, and several generations of graduate students contributing to the language. Because Scheme programs are themselves s-expressions, the language is a natural fit for the program-as-data manipulation at the heart of classical symbolic AI, where systems reason over, transform, and generate code and logical expressions.

In programming language research, Scheme has been a workhorse for decades. The Felleisen group at Rice and Northeastern used PLT Scheme as the substrate for foundational work on contracts, soft typing, gradual typing, and macro hygiene. Will Clinger's flow analysis research ran through Larceny. Olin Shivers's PhD thesis on control-flow analysis (1991) was carried out in Scheme. R. Kent Dybvig's work on macro systems produced the design of syntax-case ^[9]. PLT Redex and the Rosette solver-aided language are also Scheme-based.

What about industrial use of Scheme?

Scheme's industrial footprint is small but real. It tends to appear as an embedded extension language, as a teaching tool that survived into production, or as the core of a niche technical product.

The extension language pattern is exemplified by Guile, the official GNU extension language. GnuCash uses Guile for its reports and scripting, GNU TeXmacs for editor extensions, and Lilypond, the music engraving system, for much of its layout logic. GNU Make 4.0 added Guile integration for advanced build scripts.

Apple shipped notable Scheme integrations in the early 1990s. The Macintosh Common Lisp environment included a Scheme dialect called MacScheme, and Apple's MPW (Macintosh Programmer's Workshop) shipped with a Scheme interpreter for system scripting. Apple's Newton platform used a dynamic dialect called NewtonScript that drew heavily on Scheme's design.

Cisco Systems acquired Cadence Research Systems in 2011 specifically to bring Chez Scheme and R. Kent Dybvig in-house. Chez is used at Cisco for prototyping networking products. Chez was open-sourced under the Apache 2.0 license in 2016 and now serves as the runtime for Racket ^[7].

In education, Racket powers the Bootstrap curriculum used in secondary schools across the United States and parts of Europe. Brown University's introductory programming sequence has been built on Racket for many years, and Northeastern's CS curriculum continues to use it.

NASA's Deep Space 1 mission used a Lisp-based onboard control system called the Remote Agent in 1999. While the core was Common Lisp, parts of the surrounding mission planning toolchain were written in Scheme variants. The Remote Agent is frequently cited as one of the most ambitious uses of any Lisp dialect in spacecraft control ^[10].

Is Scheme still relevant today?

Scheme's active community is smaller than that of Python or JavaScript, but it remains lively and productive. The R7RS-large working group continues to ratify new libraries, the SRFI process accepts new submissions every few months, and Racket, Chicken, Guile, Gambit, and Chez Scheme are all under active development as of the mid-2020s.

In web development, Racket's web server pioneered the continuation-based style in which an entire user session is captured as a call/cc and resumed when the user submits a form. The technique influenced later frameworks such as Seaside in Smalltalk. In education, Racket and HtDP continue to underpin curricula at major universities, and Bootstrap reaches tens of thousands of secondary students each year. SICP, though no longer used at MIT, is still adopted elsewhere and read by individual learners; the second edition is freely available online.

In programming language research, Scheme's role has narrowed slightly as Haskell, OCaml, and Rust have absorbed some of its mindshare for type system experimentation, but Scheme remains the substrate of choice for macro and module-system research. The continued development of Chez gives the Scheme world a native code compiler that compares favorably with Java and C# on many workloads ^[7]. Scheme also retains a cultural role as the language of "the Wizard Book," the affectionate nickname for SICP, and as the language that taught a generation of computer scientists, including many who went on to AI research, that programming was about ideas rather than syntax.

How does Scheme differ from Common Lisp?

Scheme and Common Lisp are the two most influential surviving branches of the Lisp family, but they embody opposite design philosophies. Scheme, created in 1975, pursues minimalism: a tiny core in which expressive power comes from removing restrictions rather than adding features. Common Lisp, standardized as ANSI X3.226 in 1994, is a large multi-paradigm synthesis of earlier Lisps, with an extensive standard library and the Common Lisp Object System (CLOS) built in.

Scroll sideways for more →

In short, Scheme optimizes for a small, theoretically clean core suited to teaching and language research, while Common Lisp optimizes for a batteries-included industrial environment. Many programmers learn Scheme first for its conceptual clarity and reach for Common Lisp when building large applications.

Code example

A simple Scheme procedure that computes a factorial:

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

(factorial 5)  ; => 120

A tail-recursive version that runs in constant stack space, as required by the standard:

(define (factorial n)
  (define (loop i acc)
    (if (= i 0)
        acc
        (loop (- i 1) (* acc i))))
  (loop n 1))

A short demonstration of call/cc used to implement an early exit from a loop:

(define (find-first-even lst)
  (call-with-current-continuation
    (lambda (return)
      (for-each
        (lambda (x)
          (if (even? x) (return x)))
        lst)
      #f)))

(find-first-even '(1 3 5 4 7))  ; => 4

The same pattern can be used to build exceptions, generators, coroutines, and backtracking search.

See also

• Lisp
• Common Lisp
• Clojure
• Racket
• Emacs Lisp
• Lambda calculus
• Actor model
• Symbolic AI
• SICP
• Lambda Papers
• Hygienic macros
• Tail call optimization
• Continuation

References

1. Sussman, G. J., & Steele, G. L. (1975). "Scheme: An Interpreter for Extended Lambda Calculus." MIT AI Memo 349. https://dspace.mit.edu/handle/1721.1/5794 ↩
2. Steele, G. L., & Sussman, G. J. (1976). "Lambda: The Ultimate Imperative." MIT AI Memo 353. https://dspace.mit.edu/handle/1721.1/5790 ↩
3. Abelson, H., & Sussman, G. J., with Sussman, J. (1996). *Structure and Interpretation of Computer Programs* (2nd ed.). MIT Press. https://mitpress.mit.edu/9780262510875/structure-and-interpretation-of-computer-programs/ ↩
4. Steele, G. L. (1978). "Rabbit: A Compiler for SCHEME." MIT AI-TR-474 (Master's thesis). https://dspace.mit.edu/handle/1721.1/6913 ↩
5. Kelsey, R., Clinger, W., & Rees, J. (Eds.). (1998). "Revised5 Report on the Algorithmic Language Scheme." *Higher-Order and Symbolic Computation*, 11(1). https://schemers.org/Documents/Standards/R5RS/ ↩
6. Sperber, M., Dybvig, R. K., Flatt, M., & van Straaten, A. (Eds.). (2007). "Revised6 Report on the Algorithmic Language Scheme." http://www.r6rs.org/ ↩
7. Dybvig, R. K. (2011). "Chez Scheme Version 8 User's Guide." Cadence Research Systems. https://www.scheme.com/csug8/ ↩
8. Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2018). *How to Design Programs* (2nd ed.). MIT Press. https://htdp.org/ ↩
9. Dybvig, R. K., Hieb, R., & Bruggeman, C. (1992). "Syntactic Abstraction in Scheme." *Lisp and Symbolic Computation*, 5(4), 295-326. https://www.cs.indiana.edu/~dyb/pubs/LaSC-5-4-pp295-326.pdf ↩
10. Bertrand, R., Pell, B., Gat, E., et al. (1998). "Remote Agent: To Boldly Go Where No AI System Has Gone Before." *Artificial Intelligence*, 103(1-2), 5-47. https://ti.arc.nasa.gov/m/pub-archive/archive/0290.pdf ↩
11. Shinn, A., Cowan, J., & Gleckler, A. (Eds.). (2013). "Revised7 Report on the Algorithmic Language Scheme." https://small.r7rs.org/attachment/r7rs.pdf ↩
12. IEEE Computer Society. (1990). "IEEE Standard for the Scheme Programming Language." IEEE Std 1178-1990. https://standards.ieee.org/ieee/1178/1283/
13. Wikipedia contributors. "Scheme (programming language)." Wikipedia. https://en.wikipedia.org/wiki/Scheme_(programming_language) ↩
14. Felleisen, M., Findler, R. B., Flatt, M., Krishnamurthi, S., Barzilay, E., McCarthy, J., & Tobin-Hochstadt, S. (2015). "The Racket Manifesto." *1st Summit on Advances in Programming Languages (SNAPL 2015)*. https://www2.ccs.neu.edu/racket/pubs/manifesto.pdf
15. Clinger, W. (1998). "Proper Tail Recursion and Space Efficiency." *Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation* (PLDI '98). https://www.cesura17.net/~will/Professional/Research/Papers/tail.pdf ↩
16. Felleisen, M., Findler, R. B., Flatt, M., et al. (2021). "Racket Compiler and Runtime Status: January 2021." Racket Blog. https://blog.racket-lang.org/2021/01/racket-status.html