Semantic concepts

4.1  Programs and libraries

A Scheme program consists of a top-level program together with a set of libraries, each of which defines a part of the program connected to the others through explicitly specified exports and imports. A library consists of a set of export and import specifications and a body, which consists of definitions, and expressions. A top-level program is similar to a library, but has no export specifications. Chapters 6 and 7 describe the syntax and semantics of libraries and top-level programs, respectively. Subsequent chapters describe various standard libraries provided by a Scheme system. In particular, chapter 9 describes a base library that defines many of the constructs traditionally associated with Scheme.

The division between the base library and other standard libraries is based on use, not on construction. In particular, some facilities that are typically implemented as “primitives” by a compiler or the run-time system rather than in terms of other standard procedures or syntactic forms are not part of the base library, but are defined in separate libraries. Examples include the fixnums and flonums libraries, the exceptions and conditions libraries, and the libraries for records.

4.2  Variables, keywords, and regions

In a library body or top-level program, an identifiermay name a kind of syntax, or it may name a location where a value can be stored. An identifier that names a kind of syntax is called a keyword, or syntactic keyword, and is said to be bound to that kind of syntax (or, in the case of a syntactic abstraction, a transformer that translates the syntax into more primitive forms; see section 6.3.2). An identifier that names a location is called a variableand is said to be bound to that location. A variable that names a piece of syntax in a syntactic abstraction is called a pattern variableand is said to be bound to that piece of syntax. The set of all visible bindingsin effect at some point in a top-level program or library body is known as the environment in effect at that point. The value stored in the location to which a variable is bound is called the variable’s value. By abuse of terminology, the variable is sometimes said to name the value or to be bound to the value. This is not quite accurate, but confusion rarely results from this practice.

Certain forms are used to create syntactic abstractions and to bind keywords to transformers for those new syntactic abstractions, while other forms create new locations and bind variables to those locations. Collectively, these forms are called binding constructs.Some binding constructs take the form of definitions, while others are expressions. With the exception of exported library bindings, a binding created by a definition is visible only within the body in which the definition appears, e.g., the body of a library, top-level program, or base-library lambda expression. Exported library bindings are also visible within the bodies of the libraries and top-level programs that import them (see chapter 6).

Expressions that bind variables include the base-library lambda, let, let*, letrec, letrec*, let-values, and let*-values forms along with the control-library do and case-lambda forms (see sections 9.5.2, 9.5.6, and library chapter on “Control structures”). Of these, lambda is the most fundamental. Sets of variable definitions appearing within the bodies of any of these constructs, or within the bodies of a library or top-level program, are treated as the equivalent of a set of letrec* bindings. For library bodies, however, some additional mechanism is required to allow the variables that are exported from the library to be referenced by importing libraries and top-level programs.

Expressions that bind keywords include the base-library let-syntax and letrec-syntax forms. (see section 9.19). A base-library define form is a definition that creates a variable binding (see section 9.3), and a base-library define-syntax form is a definition that creates a keyword binding (see section 9.3.2).

Scheme is a statically scoped language with block structure. To each place in a top-level program or library body where an identifier is bound there corresponds a region of code within which the binding is visible. The region is determined by the particular binding construct that establishes the binding; if the binding is established by a lambda expression, for example, then its region is the entire lambda expression. Every mention of an identifier refers to the binding of the identifier that established the innermost of the regions containing the use. If a use of an identifier appears in a place where none of the surrounding expressions contains a binding for the identifier, the use may refer to a binding established by a definition or import at the top of the enclosing library or top-level program (see chapter 6). If there is no binding for the identifier, it is said to be unbound.

4.3  Exceptional situations

A variety of exceptional situations are distinguished in this report, among them violations of syntax, violations of a procedure’s specification, violations of implementation restrictions, and exceptional situations in the environment. When an exception is raised, an object is provided that describes the nature of the exceptional situation. The report uses the condition system described in library section on “Conditions” to describe exceptional situations, classifying them by condition types.

For most of the exceptional situations described in this report, portable programs cannot rely upon the exception being continuable at the place where the situation was detected. For those exceptions, the exception handler that is invoked by the exception should not return. In some cases, however, continuing is permissible, and the handler may return. See library section on “Exceptions”.

Implementations must raise an exception when they are unable to continue correct execution of a correct program due to some implementation restriction. For example, an implementation that does not support infinities must raise an exception with condition type &implementation-restriction when it evaluates an expression whose result would be an infinity.

Some possible implementation restrictions such as the lack of representations for NaNs and infinities (see section 9.8.2) are anticipated by this report, and implementations typically must raise an exception of the appropriate condition type if they encounter such a situation.

4.4  Argument and subform checking

Many procedures specified in this report or as part of a standard library restrict the arguments they accept. Typically, a procedure accepts only specific numbers and types of arguments. Many syntactic forms similarly restrict the values to which one or more of their subforms can evaluate. These restrictions imply responsibilitiesfor both the programmer and the implementation. Specifically, the programmer is responsible for ensuring that the values indeed adhere to the restrictions described in the specification. The implementation must check that the restrictions in the specification are indeed met, to the extent that it is reasonable, possible, and necessary to allow the specified operation to complete successfully. The implementation’s responsibilities are specified in more detail in section 5.2 and throughout the report.

Note that it is not always possible for an implementation to completely check the restrictions set forth in a specification. For example, if an operation is specified to accept a procedure with specific properties, checking of these properties is undecidable in general. Similarly, some operations accept both lists and procedures that are called by these operations. Since lists can be mutated by the procedures through the (rnrs mutable-pairs (6)) library (see library chapter on “Mutable pairs”), an argument that is a list when the operation starts may become a non-list during the execution of the operation. Also, the procedure might escape to a different continuation, preventing the operation from performing more checks. Requiring the operation to check that the argument is a list after each call to such a procedure would be impractical. Furthermore, some operations that accept lists only need to traverse these lists partially to perform their function; requiring the implementation to traverse the remainder of the list to verify that all specified restrictions have been met might violate reasonable performance assumptions. For these reasons, the programmer’s obligations may exceed the checking obligations of the implementation.

Moreover, the subforms of a special form usually need to obey certain syntactic restrictions. These subforms may be subject to macro expansion, which may not terminate, thus making the question of whether they obey the specified restrictions undecidable.

When an implementation detects a violation of a restriction for an argument or the value of a subform, it must raise an exception with condition type &assertion in a way consistent with the safety of execution as described in the next section.

4.5  Safety

The standard libraries whose exports are described by this document are said to be safe libraries. Libraries and top-level programs that import only from safe libraries are also said to be safe.

As defined by this document, the Scheme programming language is safe in the following sense: The execution of a safe top-level program cannot go so badly wrong as to crash or to continue to execute while behaving in ways that are inconsistent with the semantics described in this document, unless the execution first encounters some implementation restriction or other defect in the implementation of Scheme that is executing the program.

Violations of an implementation restriction must raise an exception with condition type &implementation-restriction, as must all violations and errors that would otherwise threaten system integrity in ways that might result in execution that is inconsistent with the semantics described in this document.

The above safety properties are guaranteed only for top-level programs and libraries that are said to be safe. In particular, implementations may provide access to unsafe libraries in ways that cannot guarantee safety.

4.6  Boolean values

Although there is a separate boolean type, any Scheme value can be used as a boolean value for the purpose of a conditional test. In a conditional test, all values count as true in such a test except for #f. This report uses the word “true” to refer to any Scheme value except #f, and the word “false” to refer to #f.

4.7  Multiple return values

A Scheme expression can evaluate to an arbitrary finite number of values. These values are passed to the expression’s continuation.

Not all continuations accept any number of values: A continuation that accepts the argument to a procedure call is guaranteed to accept exactly one value. The effect of passing some other number of values to such a continuation is unspecified. The call-with-values procedure described in section 9.16 makes it possible to create continuations that accept specified numbers of return values. If the number of return values passed to a continuation created by a call to call-with-values is not accepted by its consumer that was passed in that call, then an exception is raised. A more complete description of the number of values accepted by different continuations and the consequences of passing an unexpected number of values is given in the description of the values procedure in section 9.16.

A number of forms in the base library have sequences of expressions as subforms that are evaluated sequentially, with the return values of all but the last expression being discarded. The continuations discarding these values accept any number of values.

4.8  Storage model

Variables and mutable objects such as mutable pairs, bytevectors, vectors, strings, and records implicitly denote locationsor sequences of locations. A mutable string, for example, denotes as many locations as there are characters in the string. A new value may be stored into one of these locations using the string-set! procedure, but the string continues to denote the same locations as before.

An object fetched from a location, by a variable reference or by a procedure such as car, vector-ref, or string-ref, is equivalent in the sense of eqv? (section 9.6) to the object last stored in the location before the fetch, whenever the behavior of eqv? is fully specified for the object.

Every location is marked to show whether it is in use. No variable or object ever refers to a location that is not in use. Whenever this report speaks of storage being allocated for a variable or object, what is meant is that an appropriate number of locations are chosen from the set of locations that are not in use, and the chosen locations are marked to indicate that they are now in use before the variable or object is made to denote them.

In many systems it is desirable for constants(i.e., the values of literal expressions) to reside in read-only memory. To express this, it is convenient to imagine that every object that could denote locations is associated with a flag telling whether that object is mutableor immutable. Literal constants, the strings returned by symbol->string, records with no mutable fields, and other values explicitly designated as immutable are immutable objects, while other objects that denote locations are mutable. An attempt to mutate an immutable object should raise an exception with condition type &assertion. An immutable object may not denote a specific set of locations, i.e., it may be copied at any time by the implementation so as to exist simultaneously in different sets of locations. This may be visible in the failure of eqv? or eq? (section 9.6) to recognize two occurrences of the object as equivalent.

4.9  Proper tail recursion

Implementations of Scheme are required to be properly tail-recursive. Procedure calls that occur in certain syntactic contexts are tail calls. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return. Note that this includes regular returns as well as returns through continuations captured earlier by call-with-current-continuation that are later invoked. In the absence of captured continuations, calls could return at most once and the active calls would be those that had not yet returned. A formal definition of proper tail recursion can be found in Clinger’s paper [8]. The rules for identifying tail calls in base-library constructs are described in section 9.21.

Rationale:  

Intuitively, no space is needed for an active tail call because the continuation that is used in the tail call has the same semantics as the continuation passed to the procedure containing the call. Although an improper implementation might use a new continuation in the call, a return to this new continuation would be followed immediately by a return to the continuation passed to the procedure. A properly tail-recursive implementation returns to that continuation directly.

Proper tail recursion was one of the central ideas in Steele and Sussman’s original version of Scheme. Their first Scheme interpreter implemented both functions and actors. Control flow was expressed using actors, which differed from functions in that they passed their results on to another actor instead of returning to a caller. In the terminology of this section, each actor finished with a tail call to another actor.

Steele and Sussman later observed that in their interpreter the code for dealing with actors was identical to that for functions and thus there was no need to include both in the language.

4.10  Dynamic environment

Some operations described in the report acquire information in addition to their explicit arguments from the dynamic environment. For example, call-with-current-continuation (section 9.16) accesses an implicit context established by dynamic-wind, and the raise procedure (library section on “Exceptions”) accesses the current exception handler. The operations that modify the dynamic environment do so dynamically, for the dynamic extent of a call to a procedure like dynamic-wind or with-exception-handler. When such a call returns, the previous dynamic environment is restored. The dynamic environment can be thought of as that part of a continuation that does not specify the destination of any returned values. Consequently, it is captured by call-with-current-continuation, and restored by invoking the escape procedure it creates.