Scheme is a minimalist, multi-paradigm programming language that is a dialect of Lisp. Developed in the 1970s by Guy L. Steele Jr. and Gerald Jay Sussman, Scheme is known for its clean, functional style, lexical scoping, and support for first-class procedures. It emphasizes simplicity and formal semantics, making it a popular choice for computer science education and research, while also influencing numerous other languages. Key features include a uniform syntax based on prefix notation, dynamic typing, and an efficient implementation of continuations.
1 History and Development
1.1 Origins in Lisp and the Lambda Papers
Scheme originated from efforts to develop a "Lisp of the future" that incorporated the lambda calculus and lexical scoping. In 1975, Gerald Jay Sussman and Guy L. Steele Jr. published a series of papers known as the Lambda Papers, which explored the semantics of lambda expressions in programming languages. These papers introduced the core ideas behind Scheme, including lexical scoping, first-class procedures, and continuations. The language was initially called "Schemer" but was later shortened to "Scheme" due to file system constraints.
1.2 Early Implementations (1970s–1980s)
The first implementation of Scheme was a Lisp interpreter written in MacLisp. Early implementations, such as MIT Scheme and MacScheme, demonstrated the feasibility of the language and its features. In the 1980s, Scheme gained popularity in academic settings, particularly at the Massachusetts Institute of Technology (MIT), where it was used in introductory computer science courses.
1.3 Standardization: RnRS Reports (R4RS, R5RS, R6RS, R7RS)
Scheme has been standardized through a series of reports known as the Revised^n Reports on the Algorithmic Language Scheme (RnRS). The first formal standard was R2RS in 1978, followed by R3RS, R4RS (1991), R5RS (1998), R6RS (2007), and R7RS (2013). Each report refined the language's specification, adding features while preserving its minimalist philosophy.
1.3.1 R5RS as the De Facto Standard
R5RS (Revised^5 Report on the Algorithmic Language Scheme) is widely regarded as the de facto standard for Scheme. It is concise, defining the language in roughly 50 pages, and emphasizes portability and simplicity. Many textbooks and educational materials based on scheme, such as *Structure and Interpretation of Computer Programs*, reference R5RS.
1.3.2 R6RS Controversy and R7RS Small
R6RS expanded the language significantly, introducing a formal module system, additional data types, and a larger standard library. This departure from minimalism sparked controversy within the Scheme community, leading to the development of R7RS Small. R7RS Small aims to maintain the simplicity of earlier versions while standardizing a core language that can be extended by implementations. It was finalized in 2013 and is supported by many modern Scheme implementations.
2 Core Language Features
2.1 Syntactic Structure
2.1.1 S-expressions and Parentheses
Scheme uses S-expressions (symbolic expressions) as its primary syntactic unit. An S-expression is either an atom (such as a number, symbol, or string) or a parenthesized list of zero or more S-expressions. Parentheses denote function application, as in (f x y). This uniform structure simplifies parsing and manipulation of code as data.
2.1.2 Prefix Notation and Macros (define-syntax)
All function and operator calls in Scheme use prefix notation: the operator appears first, followed by its arguments. For example, (+ 1 2 3) adds the numbers. Scheme also supports syntactic extension through hygienic macros. The define-syntax form allows programmers to define new syntactic constructs that are expanded into existing forms without capturing unintended identifiers.
2.2 Lexical Scoping and Closures
2.2.1 Block Structure via let and lambda
Scheme implements lexical scoping using let and lambda forms. A lambda expression creates a procedure that captures the enclosing environment. The let form introduces local bindings that are evaluated in the current scope. This allows the construction of nested block structures similar to those in ALGOL.
2.2.2 First-Class Procedures and Higher-Order Functions
Procedures in Scheme are first-class objects: they can be passed as arguments, returned from other procedures, and stored in data structures. This enables higher-order functions such as map, filter, and fold. The ability to create closures—procedures that retain access to their lexical environment—is a cornerstone of Scheme's expressive power.
2.3 Evaluation Model
2.3.1 Applicative-Order vs. Normal-Order
Scheme uses applicative-order evaluation (call-by-value) by default: arguments are evaluated before the procedure is applied. This contrasts with normal-order evaluation (call-by-name), where arguments are substituted unevaluated. Scheme provides special forms like delay and force to implement lazy evaluation selectively.
2.3.2 Strict Evaluation and Eager Arguments
All standard Scheme primitives and procedure calls are strict: every argument is computed completely before the call. This eager evaluation simplifies reasoning about performance and side effects, and is consistent with the language's emphasis on simplicity and determinism.
2.4 Data Types
2.4.1 Atomic Types: Numbers, Booleans, Symbols, Characters
Scheme provides atomic data types including integers, rationals, real numbers, and complex numbers; booleans (#t and #f); symbols (interned names used as identifiers); and characters (individual Unicode code points). These types are disjoint and checked at runtime.
2.4.2 Compound Types: Lists, Vectors, Strings
Compound data structures include linked lists (built from pairs), vectors (fixed-length arrays), and strings (sequences of characters). Lists are the fundamental aggregate type, used for both code and data. Vectors offer O(1) access, while strings are mutable in some implementations.
2.4.3 Procedural Data and Continuations
Procedures are themselves a data type in Scheme. They can be stored, passed, and created at runtime. Continuations—representations of the current control state—are also first-class objects, obtained via call-with-current-continuation (call/cc).
2.5 Special Forms and Macros
2.5.1 define, lambda, let, cond, if
These are the core special forms. define binds a variable to a value; lambda creates an anonymous procedure; let establishes local bindings; cond provides multi-branch conditional evaluation; and if provides a two-branch conditional. They are not functions, but syntactic constructs processed by the reader and evaluator.
2.5.2 Hygienic Macros (syntax-rules)
Scheme's hygienic macro system ensures that identifiers introduced by a macro do not inadvertently capture identifiers in the surrounding code. The syntax-rules form allows pattern-matching and template-based macro definitions. This system was pioneered in Scheme and is a key factor in the language's reputation for syntactic correctness.
2.6 Continuations and Call/cc
2.6.1 First-Class Continuations
A continuation is an abstract representation of the control state at a given point in a program. In Scheme, call/cc captures the current continuation as a procedure. When this procedure is invoked, the program resumes at the point of capture, effectively allowing non‑local jumps and sophisticated control flow.
2.6.2 Control Flow and Non-Local Exits
Continuations enable advanced control structures such as coroutines, cooperative multitasking, and exception handling. For example, a continuation can be captured to implement a break or return statement from a deep recursion. However, misuse of call/cc can lead to confusing code, and some implementations encourage more constrained alternatives.
3 Programming Paradigms in Scheme
3.1 Functional Programming
3.1.1 Recursion and Tail-Call Optimization
Recursion is the primary iteration mechanism in functional Scheme. The language specification requires tail‑call optimization: if the last expression of a procedure is a procedure call, the call is executed without consuming additional stack space. This makes tail‑recursive loops as efficient as iterative loops in other languages.
3.1.2 Map, Filter, Fold Operations
Scheme provides higher‑order list procedures such as map, filter, fold-left, and fold-right. These functions encapsulate common recursion patterns and are idiomatic in functional programming. They work seamlessly with first‑class procedures and closures.
3.2 Imperative Programming
3.2.1 Mutation with set! and Boxes
Scheme supports imperative programming through mutation operations. set! mutates an existing variable binding; vector-set! and string-set! mutate vectors and strings. Implementations may also provide boxes (mutable cells) for explicit mutation. These features allow for stateful computations and side effects.
3.2.2 Input/Output Ports
I/O operations in Scheme are performed through ports, which are abstractions for input and output channels. Standard procedures include read, write, display, and newline. Ports may be connected to files, strings, or network sockets, and can be manipulated programmatically.
3.3 Object-Oriented Programming
3.3.1 Simulating Objects with Closures
Before native object systems were added to Scheme, objects could be simulated using closures. A closure can encapsulate local state (mutable or immutable) and return a dispatcher procedure that responds to messages. This technique, known as "closure-based objects," demonstrates the expressive power of lexical scoping.
3.3.2 Record Types and Generative Structures
Later standards introduced record types for structured data. R6RS and R7RS provide define-record-type or define-record-type* that create named, disjoint types with accessors and constructors. Some implementations also support generative structures where types can be dynamically created at runtime.
3.4 Meta-Programming
3.4.1 Eval, Read, and Load
Scheme provides eval to evaluate an arbitrary S-expression as code in a given environment, and read to parse S-expressions from input. The load function reads and evaluates a file. These capabilities allow programs to construct and execute new code at runtime, facilitating meta‑programming.
3.4.2 Syntax-Case Macros
In addition to syntax-rules, some implementations (notably Racket and Chez Scheme) offer syntax-case macros. This more powerful system allows the macro writer to manipulate patterns and templates with the full computational power of Scheme, including conditionals and recursive expansion.
4 Implementations and Environments
4.1 Major Implementations
4.1.1 MIT/GNU Scheme
Developed at the Massachusetts Institute of Technology, MIT/GNU Scheme is one of the oldest implementations. It features a compiler, a debugger, and an integrated development environment (called Edwin). It supports the full R5RS standard and several extensions.
4.1.2 Chez Scheme
Chez Scheme is a high‑performance implementation originally developed by Cadence Research Systems and later by Cisco. It includes an incremental compiler that produces efficient native code. Chez Scheme supports R6RS and many additional libraries, and is known for its speed and reliability.
4.1.3 Chicken Scheme
Chicken Scheme compiles Scheme to C, then to native code. It is highly portable and supports a large ecosystem of eggs (libraries). Chicken aims to be a practical tool for scripting and application development, bridging Scheme and the C world.
4.1.4 Racket (formerly PLT Scheme)
Racket is a descendant of PLT Scheme that evolved into a language‑oriented programming platform. It includes a rich set of tools, a powerful macro system, and the ability to design new languages on top of the base implementation.
4.1.4.1 Racket's Language-Oriented Extensions
Racket extends Scheme with a language‑oriented approach: programmers can define new language constructs via patterns and libraries. The Racket ecosystem includes frameworks for web development, graphics, and parsing. It also provides a contract system and a class‑based object system.
4.2 Development Tools
4.2.1 REPL (Read-Eval-Print Loop)
Most Scheme implementations provide a REPL, an interactive environment where expressions are read, evaluated, and printed. This facilitates incremental development and exploration. The REPL is a core tool for learning Scheme and debugging code.
4.2.2 Debugging and Tracing
Scheme implementations offer debugging tools such as stack traces, breakpoints, and tracing. For example, MIT/GNU Scheme includes a stepper and a debugger that can inspect continuations. Racket provides a sophisticated DrRacket IDE with a debugger and profiler.
4.2.3 Libraries and Package Managers
Various Scheme implementations have their own library systems. Chicken has "eggs", Racket has "packages" via the Racket package catalog, and Chez Scheme uses libraries conforming to the R6RS library system. These repositories enable code reuse and distribution.
5 Applications and Use Cases
5.1 Education and Academic Research
5.1.1 Structure and Interpretation of Computer Programs (SICP)
The textbook *Structure and Interpretation of Computer Programs* (SICP), by Harold Abelson and Gerald Jay Sussman, uses Scheme as its teaching language. SICP covers fundamental concepts of computation, abstraction, and programming paradigms, and has influenced generations of computer science students.
5.1.2 Teaching Programming Language Concepts
Scheme's minimal syntax and powerful semantics make it an ideal vehicle for teaching programming languages, interpreters, compilers, and formal semantics. Many universities use Scheme in courses on programming language design and implementation.
5.2 Scripting and Rapid Prototyping
Because of its concise syntax and interactive REPL, Scheme is used for scripting tasks and rapid prototyping in research and hobby projects. Implementations like Chicken and Gambit Scheme are particularly well‑suited for this, as they can interface with C libraries and generate standalone executables.
5.3 Embedded Systems and Domain-Specific Languages
Scheme's small footprint and metaprogramming capabilities allow it to be embedded in larger systems or used as a scripting language within applications. The Racket platform, for instance, enables the creation of domain‑specific languages (DSLs) for tasks such as generative art, games, and data analysis.
6 Influence and Legacy
6.1 Impact on Other Languages
6.1.1 Common Lisp and Clojure
Scheme's lexical scoping and first‑class procedures influenced later Lisp dialects, including Common Lisp (which adopted lexical closures with the lexical-let form in some implementations) and Clojure (which emphasizes functional programming and persistent data structures). Clojure also draws inspiration from Scheme's macro system.
6.1.2 JavaScript, Python, and Ruby (lexical closures)
Lexical closures became widely popular in the 1990s after Scheme's demonstration of their utility. JavaScript implemented closures from its inception; Python added them via nested scopes in version 2.1; Ruby has supported closures since its early versions. Scheme's clear exposition of closures influenced the design of these languages.
6.2 Scheme in the History of Programming Languages
Scheme is historically significant as one of the first languages to fully embrace lexical scoping, tail‑call optimization, and first‑class continuations. It served as a proof of concept for many ideas later adopted by mainstream languages. Its standardization process also influenced how language specifications are written and maintained. Today, Scheme remains a vibrant platform for education, research, and experimental programming.