This is an updated version of an article that first appeared in LISP Pointers 3:2-3-4 (April-June 1990), pp. 23-26 (ACM Press). It is a case study in "small scale" standards development.
This is a brief report of efforts to standardize the Scheme programming language. Scheme inherits Lisp's rich set of symbol manipulation primitives, latent storage allocation, dynamic type checking. and simple syntax. Scheme is distinguished from most Lisp dialects by a single variable environment, block structure with static scope, and uniform evaluation of the operator and operand positions of a procedure call. Since there is no storage penalty for tail-recursive procedure calls, they may be used to express iteration. Provision is made for a rich set of numerical types, and exact and inexact numbers are distinguished. The ability to create first-class escape procedures allows almost all known forms of sequential control to be expressed. Above all, Scheme achieves its expressive power through the simplicity and generality of its design, and not by the accumulation of features. (The standard is 51 pages long.) The reader may wish to consult books by Abelson and Sussman [1], Springer and Friedman [2], and Dybvig [3], among others, for tutorial introductions to Scheme.
Scheme was designed in 1975 by Gerald Sussman and Guy Steele as "a simple concrete experimental domain for certain issues of programming semantics and style." [4] In 1978, Sussman and Steele published "The Revised Report on Scheme: A Dialect of Lisp," [5] reflecting early evolution in the design of Scheme. By 1984, the use of Scheme in research, teaching, and system development had spread from MIT to several other universities and industrial laboratories. This was accompanied by a proliferation of Scheme implementations, developed in a spirit of innovation. To enhance code portability and consistency in the use of Scheme as a publication language, a workshop was held at Brandeis University in 1984. Participants included representatives for the Scheme implementations of MIT, Yale, Indiana University, and Texas Instruments. The consensus reached at this workshop, with further refinements through committee work and network discussions, was recorded in "The Revised Revised Report on Scheme" [6]. Further revisions, reflecting consensus reached largely through networked discussions, resulted in "The Revised3 Report on the Algorithmic Language Scheme," which appeared in SIGPLAN Notices in December, 1986.[7] The authors of this series of reports on Scheme, known as the RnRS, met again at MIT in the summer of 1987 and at the 1988 ACM Conference on Lisp and Functional Programming in Snowbird, Utah, where agreement was reached on further changes to be incorporated in a subsequent R4RS. Publication of this report is expected in the near future.
In March, 1988, a majority of the RnRS authors met as a study group at Indiana University with representatives of Institute of Electrical and Electronics Engineers (IEEE) and X3 standardization committees to consider initiation of a formal effort to standardize Scheme. It was concluded that a formal standard was desirable to improve code portability, publication uniformity, and language visibility. It was further recommended that this effort be initiated through the IEEE Microprocessor Standards Committee (MSC), which subsequently approved formation of a Working Group on Scheme with project authorization P1178. The MSC was chosen because it had experience with language standardization, and the IEEE's procedures for standardization working groups were less formal than those of X3 and oriented toward the participation of individuals, rather than organizations. Furthermore, IEEE standardization procedures are approved by the American National Standards Institute (ANSI), allowing many IEEE standards to become ANSI standards. (Smolin [8] reviews IEEE standardization procedures.)
The study group felt strongly that the RnRS authors should continue their language design work and publish further reports. While these reports are likely to form the basis for future revisions of the standard, they may be less conservative than is appropriate for a standard. They may, for example, include experimental features that should be withheld from standardization. The study group considered it essential that the publication of an IEEE standard based on the RnRS, and copyrighted by the IEEE, not compromise the public domain status of the RnRS. The IEEE indicated that this would not be a problem. Finally, the study group concluded that Scheme standardization would not conflict with standardization of other members of the Lisp family, such as X3J13's development of a Common Lisp standard and work on a Lisp standard by the international standards organization ISO.
The Working Group on Scheme has held four meetings, on July 27, 1988 (Snowbird), February 3, 1989 (MIT), July 7, 1989 (MIT), and January 19, 1990 (San Francisco). These meetings have been supplemented by extensive network discussions and subcommittee meetings. At the last meeting the draft standard was approved for submission to the MSC for ballotting. The ballot passed and the standard was approved by the IEEE Standards Board on December 10, 1990 as IEEE Std 1178-1990 and published early in 1991.
From the R3RS to the standard for Scheme
there have been a
large number of minor improvements, both in the language defined and
in its specification. Perhaps the most significant addition is a
distinction between exact and inexact numbers that is unique to
Scheme, and should enhance the robustness of numeric programs. [9] The
distinction between essential and inessential features in
R3RS has
been eliminated by making some of the inessential features essential
and dropping others. The empty list is now interpreted as a true
value, and must thus be distinct from the false value, #f.
The standard for Scheme is based in large part on a draft of the R4RS. The latter contains some additional primitive procedures, and an appendix that specifies a trial syntactic extension mechanism which may well become part of a future Scheme standard.
Reluctance to prematurely standardize a syntactic extension mechanism is characteristic of the Scheme standardization effort. It is intended that the Scheme standard encourage continued language design in a variety of areas, such as packaging and object-oriented programming facilities and interfaces for users and operating systems.
After approving the Scheme standard, the IEE promptly submitted it to ANSI and it became an ANSI standard a few months later. The Scheme working group and the ACM regretted that they were not informed of the ANSI submission by officers of the IEEE at the time the standard was sent to ANSI. The ANSI standard move appears to have been publicized only in some obscure ANSI newsletter that no one was following. This illustrates the need for careful liaison (formal communication) between standards groups.
Recently reaffirmation of the IEEE Scheme standard was recommended by the working group and passed by ballot.
The RnRS authors continue their work of extending and refining the specification of Scheme. An IEEE Working Group on Scheme will be reconstituted to revise the standard before another five years have elapsed. In all likelyhood a revised Scheme standard will be based on the continued work of the informal report authors. The most notable aspect of the Scheme standardization experience has been the manner in which a formal standard has been based on a high-quality unnofficial document developed by an informal group.
The rapid progress of the Working Group on Scheme was made possible by the high quality of the R4RS, which reflects several years of effort by its authors. Special acknowledgment is due the RnRS editors, William Clinger and Jonathan Rees, and the standard editors, Chris Hanson, James Miller, and David Bartley.