This section gives an overview of Scheme's semantics. A detailed informal semantics is the subject of chapters section Basic concepts through section Standard procedures. For reference purposes, section section Formal semantics provides a formal semantics of Scheme.
Following Algol, Scheme is a statically scoped programming language. Each use of a variable is associated with a lexically apparent binding of that variable.
Scheme has latent as opposed to manifest types. Types are associated with values (also called objects) rather than with variables. (Some authors refer to languages with latent types as weakly typed or dynamically typed languages.) Other languages with latent types are APL, Snobol, and other dialects of Lisp. Languages with manifest types (sometimes referred to as strongly typed or statically typed languages) include Algol 60, Pascal, and C.
All objects created in the course of a Scheme computation, including procedures and continuations, have unlimited extent. No Scheme object is ever destroyed. The reason that implementations of Scheme do not (usually!) run out of storage is that they are permitted to reclaim the storage occupied by an object if they can prove that the object cannot possibly matter to any future computation. Other languages in which most objects have unlimited extent include APL and other Lisp dialects.
Implementations of Scheme are required to be properly tail-recursive. This allows the execution of an iterative computation in constant space, even if the iterative computation is described by a syntactically recursive procedure. Thus with a tail-recursive implementation, iteration can be expressed using the ordinary procedure-call mechanics, so that special iteration constructs are useful only as syntactic sugar.
Scheme procedures are objects in their own right. Procedures can be created dynamically, stored in data structures, returned as results of procedures, and so on. Other languages with these properties include Common Lisp and ML.
One distinguishing feature of Scheme is that continuations, which in most other languages only operate behind the scenes, also have "first-class" status. Continuations are useful for implementing a wide variety of advanced control constructs, including non-local exits, backtracking, and coroutines. See section section Control features.
Arguments to Scheme procedures are always passed by value, which means that the actual argument expressions are evaluated before the procedure gains control, whether the procedure needs the result of the evaluation or not. ML, C, and APL are three other languages that always pass arguments by value. This is distinct from the lazy-evaluation semantics of SASL, or the call-by-name semantics of Algol 60, where an argument expression is not evaluated unless its value is needed by the procedure.
Scheme employs a parenthesized-list Polish notation to describe programs
and (other) data. The syntax of Scheme, like that of most Lisp
dialects, provides for great expressive power, largely due to its
simplicity. An important consequence of this simplicity is the
susceptibility of Scheme programs and data to uniform treatment by other
Scheme programs. As with other Lisp dialects, the
parses its input; that is, it performs syntactic as well as lexical
decomposition of what it reads.
It is required that every implementation of Scheme support features that are marked as being essential. Features not explicitly marked as essential are not essential. Implementations are free to omit non-essential features of Scheme or to add extensions, provided the extensions are not in conflict with the language reported here.
When speaking of an error situation, this report uses the phrase "an error is signalled" to indicate that implementations must detect and report the error. If such wording does not appear in the discussion of an error, then implementations are not required to detect or report the error, though they are encouraged to do so. An error situation that implementations are not required to detect is usually referred to simply as "an error."
For example, it is an error for a procedure to be passed an argument that the procedure is not explicitly specified to handle, even though such domain errors are seldom mentioned in this report. Implementations may extend a procedure's domain of definition to include other arguments.
If the value of an expression is said to be "unspecified," then the expression must evaluate to some object without signalling an error, but the value depends on the implementation; this report explicitly does not say what value should be returned.
Chapters section Expressions and section Standard procedures are organized into entries. Each entry describes one language feature or a group of related features, where a feature is either a syntactic construct or a built-in procedure. An entry begins with one or more header lines of the form
if the feature is an essential feature, or simply
if the feature is not an essential feature.
If category is "syntax", the entry describes an expression type, and the header line gives the syntax of the expression type. Components of expressions are designated by syntactic variables, which are written using angle brackets, for example, <expression>, <variable>. Syntactic variables should be understood to denote segments of program text; for example, <expression> stands for any string of characters which is a syntactically valid expression. The notation
indicates zero or more occurrences of a <thing>, and
<thing1> <thing2> ...
indicates one or more occurrences of a <thing>.
If category is "procedure", then the entry describes a procedure, and the header line gives a template for a call to the procedure. Argument names in the template are italicized. Thus the header line
indicates that the essential built-in procedure vector-ref takes two arguments, a vector vector and an exact non-negative integer k (see below). The header lines
indicate that in all implementations, the append procedure must be defined to take two arguments, and some implementations will extend it to take zero or more arguments.
It is an error for an operation to be presented with an argument that it is not specified to handle. For succinctness, we follow the convention that if an argument name is also the name of a type, then this implies a restriction on the type of that argument to the procedure. For example, the header line for vector-ref given above dictates that first argument to vector-ref must be a vector. The following naming conventions also imply type restrictions:
- any object
- z, z1, ... zj, ...
- complex, real, rational, integer
- x, x1, ... xj, ...
- real, rational, integer
- y, y1, ... yj, ...
- real, rational, integer
- q, q1, ... qj, ...
- rational, integer
- n, n1, ... nj, ...
- k, k1, ... kj, ...
- exact non-negative integer
The symbol "=>" used in program examples should be read "evaluates to." For example,
(* 5 8) ==> 40
means that the expression (* 5 8) evaluates to the object 40. Or, more precisely: the expression given by the sequence of characters "(* 5 8)" evaluates, in the initial environment, to an object that may be represented externally by the sequence of characters "40". See section section External representations for a discussion of external representations of objects.
Go to the first, previous, next, last section, table of contents.