CtrlK
Scheme is a minimalist, multi-paradigm programming language descended from Lisp. It was designed by Gerald Jay Sussman and Guy L. Steele Jr. at the MIT Artificial Intelligence Laboratory in 1975. The language began as a small Lisp interpreter that Sussman and Steele 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 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].
Scheme was the first widely known Lisp dialect to use lexical scope by default, the first to mandate tail call optimization in the language definition, and the first major language to expose first-class continuations through the call-with-current-continuation operator. It is also notable for its exceptionally small core specification: the entire R5RS report fits in roughly fifty pages, in deliberate contrast to the thousand-page reference manuals typical of larger languages. The textbook Structure and Interpretation of Computer Programs (SICP) by Harold Abelson and Sussman, which used Scheme throughout, became one of the most influential computer science textbooks of the late twentieth century and shaped a generation of programmers [3].
Although Scheme has never had the industrial reach of Common Lisp, Clojure, or Python, it remains a touchstone for language research 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.
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.
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:
let bindings, in part because of Scheme's influence.call-with-current-continuation, abbreviated call/cc.(map f xs) rather than (mapcar #'f xs). The Lisp-1 versus Lisp-2 question remains a long-running debate in the broader Lisp community.syntax-rules, a pattern-based macro system that automatically avoids accidental variable capture. R6RS added the more powerful syntax-case procedural macro system.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.
| Standard | Year | Editors | Notes |
|---|---|---|---|
| R0RS | 1978 | Steele & Sussman | The original Revised Report, distributed as MIT AI Memo 452. |
| R1RS | 1978 | Steele & Sussman | Minor revision; sometimes treated as a footnote to R0RS. |
| R2RS | 1985 | MIT and Indiana | Joined the MIT and Indiana traditions of Scheme. |
| R3RS | 1986 | Rees and Clinger (eds.) | Formalized the standardization process and committee model. |
| R4RS | 1991 | Clinger and Rees (eds.) | Added syntax-rules, the first standardized hygienic macro system. |
| IEEE 1178 | 1990 | IEEE working group | Independent industrial standard, reaffirmed 2008. |
| ANSI 1178 | 1994 | ANSI ratification | American adoption of the IEEE document. |
| R5RS | 1998 | Kelsey, Clinger, Rees (eds.) | The canonical "small" Scheme. Roughly 50 pages, widely used as a teaching reference [5]. |
| R6RS | 2007 | Sperber, Dybvig, Flatt, van Straaten (eds.) | Added libraries, modules, exceptions, Unicode strings, bytevectors, hash tables, records, and syntax-case. Substantially larger than R5RS [6]. |
| R7RS-small | 2013 | Shinn, Cowan, Gleckler (eds.) | Minimalist response to the R6RS reaction; restored a lean core. |
| R7RS-large | in progress | Cowan and successors | Working group producing layered libraries on top of R7RS-small. |
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.
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.
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.
Scheme has dozens of implementations, more than most languages of comparable popularity. 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.
| Implementation | Origin | Notes |
|---|---|---|
| MIT/GNU Scheme | MIT, 1980s | Direct descendant of the original MIT implementation. Native code compiler, integrated Edwin editor. |
| Chez Scheme | R. Kent Dybvig, 1985 | Originally commercial under Cadence Research Systems. Acquired by Cisco in 2012; open-sourced in 2016. Underlies Racket since Racket 8 [7]. |
| Chicken Scheme | Felix Winkelmann, 2000 | Compiles via C using the Cheney-on-the-MTA technique. Large "egg" library ecosystem. |
| Gambit Scheme | Marc Feeley, 1988 | High-performance compiler targeting C. Used to build Termite (Erlang-style messaging). |
| Guile | Aubrey Jaffer / FSF, 1995 | The official GNU extension language. Used by GnuCash, Lilypond, GNU TeXmacs. |
| Racket | PLT, 1995 | Started as PLT Scheme, renamed Racket in 2010. Now its own language family with #lang dialects. |
| Bigloo | Manuel Serrano, 1992 | Optimizing compiler producing C, JVM bytecode, and .NET CIL. |
| Larceny | Will Clinger and students, 1990s | Research compiler used as a vehicle for Clinger's work on flow analysis. |
| Chibi-Scheme | Alex Shinn, 2009 | Small embeddable interpreter. R7RS-small reference implementation. |
| Stalin | Jeffrey Mark Siskind, 1990s | Whole-program optimizer that produces C code beating handwritten C on certain benchmarks. |
| Ikarus | Abdulaziz Ghuloum, 2006 | First R6RS-conformant native code compiler. Later folded into Vicare. |
| Sagittarius | Takashi Kato, 2010 | R6RS and R7RS implementation with strong cryptography library. |
| Loko | Gwen Weinholt, 2019 | Bare metal Scheme that runs without an OS. |
| STklos | Erick Gallesio | Light Scheme with a CLOS-like object system. |
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.
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 switched its default runtime from a custom VM to Chez Scheme, gaining substantial performance improvements while preserving full compatibility.
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 1985 with a second edition in 1996. It served as the primary text for MIT's introductory CS course 6.001 from 1980 until 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 [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.
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 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.
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.
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.
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 2012 specifically to bring Chez Scheme and R. Kent Dybvig in-house. Chez is used at Cisco for prototyping networking products. Chez was open-sourced 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 One 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].
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 that programming was about ideas rather than syntax.
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.