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. Scheme demonstrates that 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 that is flexible enough to support most of the major programming paradigms in use today.
Scheme was one of the first programming languages to incorporate first class procedures as in the lambda calculus, thereby proving the usefulness of static scope rules and block structure in a dynamically typed language. Scheme was the first major dialect of Lisp to distinguish procedures from lambda expressions and symbols, to use a single lexical environment for all variables, and to evaluate the operator position of a procedure call in the same way as an operand position. By relying entirely on procedure calls to express iteration, Scheme emphasized the fact that tail-recursive procedure calls are essentially gotos that pass arguments. Scheme was the first widely used programming language to embrace first class escape procedures, from which all previously known sequential control structures can be synthesized. A subsequent version of Scheme introduced the concept of exact and inexact numbers, an extension of Common Lisp’s generic arithmetic. More recently, Scheme became the first programming language to support hygienic macros, which permit the syntax of a block-structured language to be extended in a consistent and reliable manner.
The first description of Scheme was written by Gerald Jay Sussman and Guy Lewis Steele Jr. in 1975 [43]. A revised report by Steele and Sussman [42] appeared in 1978 and described the evolution of the language as its MIT implementation was upgraded to support an innovative compiler [40]. Three distinct projects began in 1981 and 1982 to use variants of Scheme for courses at MIT, Yale, and Indiana University [34, 32, 19]. An introductory computer science textbook using Scheme was published in 1984 [1]. A number of textbooks describing and using Scheme have been published since [14].
As Scheme became more widespread, local dialects began to diverge until students and researchers occasionally found it difficult to understand code written at other sites. Fifteen representatives of the major implementations of Scheme therefore met in October 1984 to work toward a better and more widely accepted standard for Scheme. Participating in this workshop were Hal Abelson, Norman Adams, David Bartley, Gary Brooks, William Clinger, Daniel Friedman, Robert Halstead, Chris Hanson, Christopher Haynes, Eugene Kohlbecker, Don Oxley, Jonathan Rees, Guillermo Rozas, Gerald Jay Sussman, and Mitchell Wand. Kent Pitman made valuable contributions to the agenda for the workshop but was unable to attend the sessions. Their report [7], edited by Will Clinger, was published at MIT and Indiana University in the summer of 1985. Further revision took place in the spring of 1986 [9] (edited by Jonathan Rees and Will Clinger), and in the spring of 1988 [11] (also edited by Will Clinger and Jonathan Rees). Another revision published in 1998, edited by Richard Kelsey, Will Clinger and Jonathan Rees, reflected further revisions agreed upon in a meeting at Xerox PARC in June 1992 [26].
Attendees of the Scheme Workshop in Pittsburgh in October 2002 formed a Strategy Committee to discuss a process for producing new revisions of the report. The strategy committee drafted a charter for Scheme standardization. This charter, together with a process for selecting editorial committees for producing new revisions for the report, was confirmed by the attendees of the Scheme Workshop in Boston in November 2003. Subsequently, a Steering Committee according to the charter was selected, consisting of Alan Bawden, Guy L. Steele Jr., and Mitch Wand. An editors’ committee charged with producing this report was also formed at the end of 2003, consisting of Will Clinger, R. Kent Dybvig, Marc Feeley, Matthew Flatt, Richard Kelsey, Manuel Serrano, and Mike Sperber, with Marc Feeley acting as Editor-in-Chief. Richard Kelsey resigned from the committee in April 2005, and was replaced by Anton van Straaten. Marc Feeley and Manuel Serrano resigned from the committee in January 2006. Subsequently, the charter was revised to reduce the size of the editors’ committee to five and to replace the office of Editor-in-Chief by a Chair and a Project Editor [37]. R. Kent Dybvig served as Chair, and Mike Sperber served as Project Editor. Parts of the report were posted as Scheme Requests for Implementation (SRFIs) and discussed by the community before being revised and finalized for the report [22, 6, 13, 21, 16]. Jacob Matthews and Robby Findler wrote the operational semantics for the language core.
We intend this report to belong to the entire Scheme community, and so we grant permission to copy it in whole or in part without fee. In particular, we encourage implementors of Scheme to use this report as a starting point for manuals and other documentation, modifying it as necessary.
To help guide the standardization effort, the editors have adopted a set of principles, presented below. Like the Scheme language defined in Revised5 Report on the Algorithmic Language Scheme [26], the language described in this report is intended to:
allow programmers to read each other’s code, and allow development of portable programs that can be executed in any conforming implementation of Scheme;
derive its power from simplicity, a small number of generally useful core syntactic forms and procedures, and no unnecessary restrictions on how they are composed;
allow programs to define new procedures and new hygienic syntactic forms;
support the representation of program source code as data;
make procedure calls powerful enough to express any form of sequential control, and allow programs to perform non-local control operations without the use of global program transformations;
allow interesting, purely functional programs to run indefinitely without terminating or running out of memory on finite-memory machines;
allow educators to use the language to teach programming effectively, at various levels and with a variety of pedagogical approaches; and
allow researchers to use the language to explore the design, implementation, and semantics of programming languages.
In addition, this report is intended to:
allow programmers to create and distribute substantial programs and libraries, e.g., SRFI implementations, that run without modification in a variety of Scheme implementations;
support procedural, syntactic, and data abstraction more fully by allowing programs to define hygiene-bending and hygiene-breaking syntactic abstractions and new unique datatypes along with procedures and hygienic macros in any scope;
allow programmers to rely on a level of automatic run-time type and bounds checking sufficient to ensure type safety; and
allow implementations to generate efficient code, without requiring programmers to use implementation-specific operators or declarations.
While it was possible to write portable programs in Scheme as described in Revised5 Report on the Algorithmic Language Scheme, and indeed portable Scheme programs were written prior to this report, many Scheme programs were not, primarily because of the lack of substantial standardized libraries and the proliferation of implementation-specific language additions.
In general, Scheme should include building blocks that allow a wide variety of libraries to be written, include commonly used user-level features to enhance portability and readability of library and application code, and exclude features that are less commonly used and easily implemented in separate libraries.
The language described in this report is intended to also be backward compatible with programs written in Scheme as described in Revised5 Report on the Algorithmic Language Scheme to the extent possible without compromising the above principles and future viability of the language. With respect to future viability, the editors have operated under the assumption that many more Scheme programs will be written in the future than exist in the present, so the future programs are those with which we should be most concerned.
We would like to thank the following people for their help: Lauri Alanko, Eli Barzilay, Alan Bawden, Michael Blair, Per Bothner, Trent Buck, Thomas Bushnell, Taylor Campbell, Ludovic Court?s, Pascal Costanza, John Cowan, George Carrette, Andy Cromarty, David Cuthbert, Pavel Curtis, Jeff Dalton, Olivier Danvy, Ken Dickey, Ray Dillinger, Blake Coverett, Jed Davis, Bruce Duba, Carl Eastlund, Sebastian Egner, Tom Emerson, Marc Feeley, Andy Freeman, Ken Friedenbach, Richard Gabriel, Martin Gasbichler, Peter Gavin, Arthur A. Gleckler, Aziz Ghuloum, Yekta Gürsel, Ken Haase, Lars T Hansen, Ben Harris, Dave Herman, Robert Hieb, Nils M. Holm, Paul Hudak, Stanislav Ievlev, James Jackson, Aubrey Jaffer, Shiro Kawai, Alexander Kjeldaas, Michael Lenaghan, Morry Katz, Felix Klock, Donovan Kolbly, Marcin Kowalczyk, Chris Lindblad, Thomas Lord, Bradley Lucier, Mark Meyer, Jim Miller, Dan Muresan, Jason Orendorff, Jim Philbin, John Ramsdell, Jeff Read, Jorgen Schaefer, Paul Schlie, Manuel Serrano, Mike Shaff, Olin Shivers, Jonathan Shapiro, Jens Axel Søgaard, Pinku Surana, Julie Sussman, Mikael Tillenius, Sam Tobin-Hochstadt, David Van Horn, Andre van Tonder, Reinder Verlinde, Oscar Waddell, Perry Wagle, Alan Watson, Daniel Weise, Andrew Wilcox, Jon Wilson, Henry Wu, Ozan Yigit, and Chongkai Zhu. We thank Carol Fessenden, Daniel Friedman, and Christopher Haynes for permission to use text from the Scheme 311 version 4 reference manual. We thank Texas Instruments, Inc. for permission to use text from the TI Scheme Language Reference Manual [44]. We gladly acknowledge the influence of manuals for MIT Scheme [32], T [35], Scheme 84 [23], Common Lisp [41], Chez Scheme [15], PLT Scheme [20], and Algol 60 [2].
We also thank Betty Dexter for the extreme effort she put into setting this report in TEX, and Donald Knuth for designing the program that caused her troubles.
The Artificial Intelligence Laboratory of the Massachusetts Institute of Technology, the Computer Science Department of Indiana University, the Computer and Information Sciences Department of the University of Oregon, and the NEC Research Institute supported the preparation of this report. Support for the MIT work was provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-80-C-0505. Support for the Indiana University work was provided by NSF grants NCS 83-04567 and NCS 83-03325.