What’s the point of Scheme?

[This article is a concise introduction to Scheme. It is aimed at experienced programmers.]

Simplicity

The Scheme programming language is one of the main dialects in the Lisp family. Compared to other Lisp dialects such as Common Lisp and Clojure, Scheme stands out for its minimalism. Its syntax is simple even by Lisp standards, and the core language fits in 50 pages.

Many experienced programmers consider Scheme the most elegant programming language ever designed. Even its detractors concede that the 50-page R5RS specification is an exemplar of concise and elegant design.

Core

Scheme achieves its compatcness by supplying a very minimal set of highly general tools from which programmers may build more complicated ones as needed. These are:

  • Dynamic typing to mix different types of data without complicated rules and restrictions.

  • Homoiconic syntax to seamlessly turn data into code and code into data.

  • Pervasive use of recursion instead of iteration to express algorithms.

  • Carefully chosen tools for creating user-defined abstractions:

    • Higher-order procedures to package recursive algorithms into reusable combinators.

    • Macros to seamlessly blend user-defined abstractions into the syntax of the language itself.

    • Closures to let procedures keep state thereby create objects.

    • Continuations to implement arbitrary control structures (such as coroutines, backtracking, state machines, method dispatch, exception handling, or multitasking) in a single-threaded program.

Tail calls

All full-featured Scheme implementations do tail call optimization. This means that tail recursion is transformed by the compiler or interpreter into goto instructions. A procedure with a million levels of recursion does not actually need to allocate a million stack frames; it can re-use the same stack frame a million times.

Scheme optimizes not only tail recursion, where the last thing a procedure does is call itself with new arguments, but all tail calls. Even if a procedure calls some other procedure, that is optimized.

Scheme’s continuations look to programmers like callable procedures. Tail calls to continuations can be optimized the same was as tail calls to procedures. This makes it efficient to backtrack from a search, change the state of a state machine, or throw an exception.

Tail call optimization is a crucial enabler for doing away with iteration constructs and relying entirely on recursion.

Scheme culture

Scheme programmers are generally among the most competent in any group. The ability to handle recursion is a common litmus test for good programmers; Schemers solve everything recursively. An typical Scheme programmer makes daily use of tail recursion, mutual recursion, trees and immutable data types to solve problems. Rapid prototyping and agile development were the lifeblood of Scheme programming decades before they became mainstream.

Constraints

Due to its compactness, Scheme is often deployed in an environment with some kind of constraint on program speed, size or system dependencies. Scheme programmers are generally facile with analyzing computational complexity, designing algorithms and data representations with acceptable performance characteristics, finding and optimizing critical paths in programs, and designing programs and libraries with efficiency in mind from the start. Efficiency is a common topic of conversation in Scheme design work.

Subsetting

Scheme is a particularly easy language to take subsets out of. If you need a tailor-made language for a particular application, subsetting Scheme lets you take advantage of decades of design work.

Lifecycle

Scheme may be unique among programming languages in the depth of knowledge and experience paid to both abstraction and performance. Whereas most programming languages are significantly better at prototyping, abstraction or efficiency, Scheme excels at the entire lifecycle of a program from rapid prototyping to high-throughput or resource-constrained production deployments. This is a balance that has been with Scheme almost from the start, and the community has been wrestling with the problem for decades.

Contributing

doc.scheme.org is a community subdomain of scheme.org.