|
The report gives a defining description of the programming language
Scheme. Scheme is a statically scoped and properly tail-recursive
dialect of the Lisp programming language invented by Guy Lewis
Steele Jr. and Gerald Jay Sussman. It was designed to have an
exceptionally clear and simple semantics and few different ways to
form expressions. A wide variety of programming paradigms, including
imperative, functional, and message passing styles, find convenient
expression in Scheme.
The introduction offers a brief history of the language and of
the report.
The first three chapters present the fundamental ideas of the
language and describe the notational conventions used for describing the
language and for writing programs in the language.
Chapters Expressions and Program structure describe
the syntax and semantics of expressions, programs, and definitions.
Chapter Standard procedures describes Scheme's built-in
procedures, which include all of the language's data manipulation and
input/output primitives.
Chapter Formal syntax and semantics provides a formal syntax for Scheme
written in extended BNF, along with a formal denotational semantics.
An example of the use of the language follows the formal syntax and
semantics.
The report concludes with a list of references and an
alphabetic index.
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 goto's 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 in
1975 [Scheme75]. A revised report [Scheme78]
appeared in 1978, which described the evolution
of the language as its MIT implementation was upgraded to support an
innovative compiler [Rabbit]. Three distinct projects began in
1981 and 1982 to use variants of Scheme for courses at MIT, Yale, and
Indiana University [Rees82], [MITScheme], [Scheme311]. An introductory
computer science textbook using Scheme was published in
1984 [SICP].
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.
Their report [RRRS]
was published at MIT and Indiana University in the summer of 1985.
Further revision took place in the spring of 1986 [R3RS],
and in the spring of 1988 [R4RS].
The present report reflects further revisions agreed upon in a meeting
at Xerox PARC in June 1992.
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.
We would like to thank the following people for their help: Alan Bawden, Michael
Blair, George Carrette, Andy Cromarty, Pavel Curtis, Jeff Dalton, Olivier Danvy,
Ken Dickey, Bruce Duba, Marc Feeley,
Andy Freeman, Richard Gabriel, Yekta G"ursel, Ken Haase, Robert
Hieb, Paul Hudak, Morry Katz, Chris Lindblad, Mark Meyer, Jim Miller, Jim Philbin,
John Ramsdell, Mike Shaff, Jonathan Shapiro, Julie Sussman,
Perry Wagle, Daniel Weise, Henry Wu, and Ozan Yigit.
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[TImanual85].
We gladly acknowledge the influence of manuals for MIT Scheme[MITScheme],
T[Rees84], Scheme 84[Scheme84],Common Lisp[CLtL],
and Algol 60[Naur63].
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.
This section enumerates the changes that have been made to Scheme since
the ``Revised^4 report'' [R4RS] was published.
- The report is now a superset of the IEEE standard for Scheme
[IEEEScheme]: implementations that conform to the report will
also conform to the standard. This required the following changes:
- The empty list is now required to count as true.
- The classification of features as essential or inessential has been
removed. There are now three classes of built-in procedures: primitive,
library, and optional. The optional procedures are load,
with-input-from-file, with-output-to-file,
transcript-on, transcript-off, and
interaction-environment,
and - and / with more than two arguments.
None of these are in the IEEE standard.
- Programs are allowed to redefine built-in procedures. Doing so
will not change the behavior of other built-in procedures.
- Port has been added to the list of disjoint types.
- The macro appendix has been removed. High-level macros are now part
of the main body of the report. The rewrite rules for derived expressions
have been replaced with macro definitions. There are no reserved identifiers.
- Syntax-rules now allows vector patterns.
- Multiple-value returns, eval, and dynamic-wind have
been added.
- The calls that are required to be implemented in a properly tail-recursive
fashion are defined explicitly.
- `@' can be used within identifiers. `|' is reserved
for possible future extensions.
The Internet Scheme Repository at:
http://www.cs.indiana.edu/scheme-repository/
contains an extensive Scheme bibliography, as well as papers,
programs, implementations, and other material related to Scheme.
Integrate-system integrates the system
y'k = fk(y1, y2, ..., yn), k = 1, ..., n
of differential equations with the method of Runge-Kutta.
The parameter system-derivative is a function that takes a system
state (a vector of values for the state variables y1, ...,
yn)
and produces a system derivative (the values y'1, ...,
y'n). The parameter initial-state provides an initial
system state, and h is an initial guess for the length of the
integration step.
The value returned by integrate-system is an infinite stream of
system states.
(define integrate-system
(lambda (system-derivative initial-state h)
(let ((next (runge-kutta-4 system-derivative h)))
(letrec ((states
(cons initial-state
(delay (map-streams next
states)))))
states))))
|
Runge-Kutta-4 takes a function, f, that produces a
system derivative from a system state. Runge-Kutta-4
produces a function that takes a system state and
produces a new system state.
(define runge-kutta-4
(lambda (f h)
(let ((*h (scale-vector h))
(*2 (scale-vector 2))
(*1/2 (scale-vector (/ 1 2)))
(*1/6 (scale-vector (/ 1 6))))
(lambda (y)
;; y is a system state
(let* ((k0 (*h (f y)))
(k1 (*h (f (add-vectors y (*1/2 k0)))))
(k2 (*h (f (add-vectors y (*1/2 k1)))))
(k3 (*h (f (add-vectors y k2)))))
(add-vectors y
(*1/6 (add-vectors k0
(*2 k1)
(*2 k2)
k3))))))))
(define elementwise
(lambda (f)
(lambda vectors
(generate-vector
(vector-length (car vectors))
(lambda (i)
(apply f
(map (lambda (v) (vector-ref v i))
vectors)))))))
(define generate-vector
(lambda (size proc)
(let ((ans (make-vector size)))
(letrec ((loop
(lambda (i)
(cond ((= i size) ans)
(else
(vector-set! ans i (proc i))
(loop (+ i 1)))))))
(loop 0)))))
(define add-vectors (elementwise +))
(define scale-vector
(lambda (s)
(elementwise (lambda (x) (* x s)))))
|
Map-streams is analogous to map: it applies its first
argument (a procedure) to all the elements of its second argument (a
stream).
(define map-streams
(lambda (f s)
(cons (f (head s))
(delay (map-streams f (tail s))))))
|
Infinite streams are implemented as pairs whose car holds the first
element of the stream and whose cdr holds a promise to deliver the rest
of the stream.
(define head car)
(define tail
(lambda (stream) (force (cdr stream))))
|
The following illustrates the use of integrate-system in
integrating the system
C dvC / dt = -iL - vC / R
L diL / dt = vC
which models a damped oscillator.
(define damped-oscillator
(lambda (R L C)
(lambda (state)
(let ((Vc (vector-ref state 0))
(Il (vector-ref state 1)))
(vector (- 0 (+ (/ Vc (* R C)) (/ Il C)))
(/ Vc L))))))
(define the-states
(integrate-system
(damped-oscillator 10000 1000 .001)
'#(1 0)
.01))
|
- [SICP]
Harold Abelson and Gerald Jay Sussman with Julie Sussman.
Structure and Interpretation of Computer Programs, second edition.
MIT Press, Cambridge, 1996.
- [Bawden88]
Alan Bawden and Jonathan Rees.
Syntactic closures.
In Proceedings of the 1988 ACM Symposium on Lisp and
Functional Programming, pages 86--95.
- [howtoprint]
Robert G. Burger and R. Kent Dybvig.
Printing floating-point numbers quickly and accurately.
In Proceedings of the ACM SIGPLAN '96 Conference
on Programming Language Design and Implementation, pages 108--116.
- [RRRS]
William Clinger, editor.
The revised revised report on Scheme, or an uncommon Lisp.
MIT Artificial Intelligence Memo 848, August 1985.
Also published as Computer Science Department Technical Report 174,
Indiana University, June 1985.
- [howtoread]
William Clinger.
How to read floating point numbers accurately.
In Proceedings of the ACM SIGPLAN '90 Conference
on Programming Language Design and Implementation, pages 92--101.
Proceedings published as SIGPLAN Notices 25(6), June 1990.
- [R4RS]
William Clinger and Jonathan Rees, editors.
The revised^4 report on the algorithmic language Scheme.
In ACM Lisp Pointers 4(3), pages 1--55, 1991.
- [macrosthatwork]
William Clinger and Jonathan Rees.
Macros that work.
In Proceedings of the 1991 ACM Conference on Principles of
Programming Languages, pages 155--162.
- [propertailrecursion]
William Clinger.
Proper Tail Recursion and Space Efficiency.
To appear in Proceedings of the 1998 ACM Conference on Programming
Language Design and Implementation, June 1998.
- [syntacticabstraction]
R. Kent Dybvig, Robert Hieb, and Carl Bruggeman.
Syntactic abstraction in Scheme.
Lisp and Symbolic Computation 5(4):295--326, 1993.
- [Scheme311]
Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes.
Scheme 311 version 4 reference manual.
Indiana University Computer Science Technical Report 137, February 1983.
Superseded by [Scheme84].
- [Scheme84]
D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand.
Scheme 84 interim reference manual.
Indiana University Computer Science Technical Report 153, January 1985.
- [IEEE]
IEEE Standard 754-1985. IEEE Standard for Binary Floating-Point
Arithmetic. IEEE, New York, 1985.
- [IEEEScheme]
IEEE Standard 1178-1990. IEEE Standard for the Scheme
Programming Language. IEEE, New York, 1991.
- [Kohlbecker86]
Eugene E. Kohlbecker Jr.
Syntactic Extensions in the Programming Language Lisp.
PhD thesis, Indiana University, August 1986.
- [hygienic]
Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias Felleisen, and Bruce Duba.
Hygienic macro expansion.
In Proceedings of the 1986 ACM Conference on Lisp
and Functional Programming, pages 151--161.
- [Landin65]
Peter Landin.
A correspondence between Algol 60 and Church's lambda notation: Part I.
Communications of the ACM 8(2):89--101, February 1965.
- [MITScheme]
MIT Department of Electrical Engineering and Computer Science.
Scheme manual, seventh edition.
September 1984.
- [Naur63]
Peter Naur et al.
Revised report on the algorithmic language Algol 60.
Communications of the ACM 6(1):1--17, January 1963.
- [Penfield81]
Paul Penfield, Jr.
Principal values and branch cuts in complex APL.
In APL '81 Conference Proceedings, pages 248--256.
ACM SIGAPL, San Francisco, September 1981.
Proceedings published as APL Quote Quad 12(1), ACM, September 1981.
- [Pitman83]
Kent M. Pitman.
The revised MacLisp manual (Saturday evening edition).
MIT Laboratory for Computer Science Technical Report 295, May 1983.
- [Rees82]
Jonathan A. Rees and Norman I. Adams IV.
T: A dialect of Lisp or, lambda: The ultimate software tool.
In Conference Record of the 1982 ACM Symposium on Lisp and
Functional Programming, pages 114--122.
- [Rees84]
Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan.
The T manual, fourth edition.
Yale University Computer Science Department, January 1984.
- [R3RS]
Jonathan Rees and William Clinger, editors.
The revised^3 report on the algorithmic language Scheme.
In ACM SIGPLAN Notices 21(12), pages 37--79, December 1986.
- [Reynolds72]
John Reynolds.
Definitional interpreters for higher order programming languages.
In ACM Conference Proceedings, pages 717--740.
ACM,
1972.
- [Scheme78]
Guy Lewis Steele Jr. and Gerald Jay Sussman.
The revised report on Scheme, a dialect of Lisp.
MIT Artificial Intelligence Memo 452, January 1978.
- [Rabbit]
Guy Lewis Steele Jr.
Rabbit: a compiler for Scheme.
MIT Artificial Intelligence Laboratory Technical Report 474, May 1978.
- [CLtL]
Guy Lewis Steele Jr.
Common Lisp: The Language, second edition.
Digital Press, Burlington MA, 1990.
- [Scheme75]
Gerald Jay Sussman and Guy Lewis Steele Jr.
Scheme: an interpreter for extended lambda calculus.
MIT Artificial Intelligence Memo 349, December 1975.
- [Stoy77]
Joseph E. Stoy.
Denotational Semantics: The Scott-Strachey Approach to
Programming Language Theory.
MIT Press, Cambridge, 1977.
- [TImanual85]
Texas Instruments, Inc.
TI Scheme Language Reference Manual.
Preliminary version 1.0, November 1985.
The principal entry for each term, procedure, or keyword is listed
first, separated from the other entries by a semicolon.
|