The Procedural Fascicle

2: Basic concepts

2.1: Variables, keywords, and regions

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 consists of the formals and body of that lambda expression. Every mention of an identifier refers to the binding of the identifier that establishes 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. If there is no binding for the identifier, it is said to be unbound.

Within the body of a library or top-level program, an identifier may 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 syntax 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 Macrological Fascicle, “Syntax transformation”.). An identifier that names a location is called a variable and is said to be bound to that location. At each point within a top-level program or a library, a specific, fixed set of identifiers is bound. The set of these identifiers, the set of visible bindings, 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.

A variable’s value can be accessed, which occurs when an expression which consists only of the variable’s name is evaluated (see section 3.1); and a variable’s value can be assigned, which occurs when a set! expression affecting the variable is evaluated (see section 4.3). A variable can also be referred to, which occurs when an expression which would, if evaluated, access or assign the value of that variable appears in code in that variable’s region, without necessarily evaluating that code. In some contexts, this report restricts the ability to refer to, access the value of, or assign the value of some variables. For example, it is not permitted for code within a library reference to bibliothecarial fascicle to attempt to assign the value of a variable which it has imported from another library, but that variable can be freely referred to and its value accessed in any context in that library. Likewise, in the context of a letrec or letrec* expression (see section 4.2), there is no restriction on referring to variables’ names, but an attempt to evaluate an expression which accesses or assigns the value of a variable bound by those expressions can cause an error to be signalled, if its value has not yet been determined according to the evaluation rules of those expressions. Finally, in the context of a body (see section 2.6), it can cause an error to be signalled if a variable is only referred to, if that variable’s definition occurs in a group of definitions which appears to the right of the expression which refers to it.

Certain expression types 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 lambda expression. Exported library bindings are also visible within the bodies of the libraries and top-level programs that import them.

2.2: Procedures

A procedure is an abstraction of an operation over objects. The operation thus abstracted over may be performed by a call to the procedure. When a procedure is called, it receives a number of inputs, referred to as its arguments. The procedure call processes those arguments either according to a specification defined in this report or by an implementation, or by evaluating some Scheme code which operates on those arguments, to perform the operation and produce its outputs. The procedure then returns its outputs to the continuation of the expression which called it. A procedure whose operation is defined by Scheme code is created by the lambda or case-lambda expressions: the arguments to the procedure are made available to that code as variables bound within the region of that code, which is a body (see section 2.6). Additional inputs to the procedure may come from variables whose region encompasses the corresponding lambda or case-lambda expression.

Scheme procedures are also objects in their own right. Procedures can be created dynamically, stored in data structures, returned as results of procedures, and so on. Many predefined operations of Scheme are provided not by syntax, but by variables whose values are procedures. The + operation, for example, which receives special syntactic treatment in many other languages, is just a regular identifier in Scheme, bound to a procedure that adds number objects.

All procedure objects in Scheme are conceptually associated with location tags, in order to make the eq? and eqv? procedures (section 4.6) work on procedures. The nature of this location tag is unspecified: the location tag itself cannot be directly treated as an object in Scheme; it is required only to have a defined equivalence relation for the purposes of the internal workings of eq? and eqv?.

Rationale: Besides their obvious uses, procedures have traditionally been used in some Scheme programs as a form of data abstraction for object-oriented programming and similar techniques (see for example [3] section 2.1.3). This makes it convenient to have a form of equivalence predicate defined over them, as for other Scheme data objects. However, treating lambda as a data constructor subject to the usual requirement to return a freshly-allocated object upon each evaluation (in the same way as, for example, the cons procedure) disallows some useful compiler optimizations for the more common case of using lambda to abstract a series of operations, rather than a collection of data.

A future fascicle will define a data constructor for procedures which guarantees that every evaluation creates a procedure object which is distinct from every other object in the sense of eqv? and eq?. A future Scheme report may then make the equivalence of all other procedures under eq? and eqv? unspecified. (The R⁶RS already made this change, but neglected to provide a suitable alternative for creating procedures which are actually used as data, so the change was reverted by the small language report.)

Every named procedure defined by this report has a single location tag distinct from the location tag of procedures with distinct names. The exception is if this report describes one procedure as an alias of another, in which case the two procedures may or may not have distinct location tags.

2.3: Expressions and definitions

All main forms in Scheme program and library code can be categorized as either definitions or expressions.

Definitions may appear directly within a program, a library cross-reference to bibliothecarial fascicle, or a body (see section 2.6). They may also appear within a begin form (see section 4.4) or other splicing form that appears within one of the contexts where a definition may appear. A definition has the effect of binding one or more identifiers to variables or syntax keywords within the region of that program, library, or body in which it is found, and within any environments created by extending the environment in place in that region. A definition which appears within a library or splicing form within a library has the effect of allowing the identifiers it names to be exported from that library cross-reference to bibliothecarial fascicle. A definition conceptually does not evaluate to any value or values, although a definition form which is passed to the eval procedure may cause that procedure call to return a value cross-reference to bibliothecarial fascicle.

Expressions evaluate to a value or values (see section 2.5). They may contain a region for an identifier or identifiers created by the expression itself, or by definitions which form part of the expression, but expressions do not create bindings in the region surrounding themselves. Expressions may occur within other expressions, as well as within definitions to specify the values of variables or the transformers for syntax keywords that are bound by the definition. All syntactic forms defined in this report are expressions unless explicitly stated to be definitions.

When an expression appears within a definition, or within a syntactic form or procedure call that changes the value of a variable or the value stored in some other location, the expression which denotes the new value to be stored in that location is said to be on the right-hand side of the definition, assignment form, or procedure call. The remaining subforms or arguments, which denote the location which is to have a new value stored in it, are said to be on the left-hand side.

When syntactic forms are specified in this report, the rule ⟨expression⟩ means any form which is an expression, and ⟨definition⟩ means any form which is a definition. ⟨Definition or expression⟩ means either a definition or an expression, although the final sequence of forms within any context where either is allowed must conform to the restrictions on definitions and expressions which apply within that context. For example, one such restriction which applies to all contexts where definitions are allowed is that no definition form may attempt to bind an identifier which another definition form in the same context also binds. It is a syntax violation to use a definition in a context where only expressions are allowed.

Some main forms in Scheme also contain auxiliary forms which are neither definitions nor expressions. Such auxiliary forms, unlike main forms, have no meaning or validity outside of by the main form to which they belong. Examples of such auxiliary forms include the ⟨formals⟩ clause of a lambda expression (see section 4.1), the left-hand side of define forms and the ⟨bindings⟩ clauses of let expressions (see section 4.2), and each ⟨cond clause⟩ of a cond expression (see section 4.5).

2.4: Continuations and dynamic extents

Note: This section will be extended by a future fascicle.

Whenever a Scheme expression is evaluated there is a continuation waiting for the result of the expression. The continuation represents an entire (default) future for the computation. For example, informally the continuation of 3 in the expression (+ 1 3) adds 1 to it.

Normally these ubiquitous continuations are hidden behind the scenes and programmers do not think much about them. However, one distinguishing feature of Scheme is that continuations, which in most other languages only operate behind the scenes, also have first-class status. Continuations may be captured in first-class procedure objects and returned to later by subsequent calls to these procedures. Using this mechanism, continuations in Scheme may never be returned to, or they may be returned to multiple times. Thus, the evaluation of any expression or sequence of expressions in Scheme can be interrupted and restarted multiple times by capture and return to a continuation.

For a procedure call, the time between when it is initiated and when it returns is called its dynamic extent. Capture of continuations allows re-entering a dynamic extent after its procedure call has returned. Thus, the dynamic extent of a call may not be a single, connected time period.

2.5: 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. For example, a continuation that accepts the argument to a procedure call is guaranteed to accept exactly one value (see section 3).

A number of forms in Scheme 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.

2.6: Bodies

Many syntactic forms in Scheme are specified as containing a body. (In order to distinguish bodies from the code inside of libraries and top-level programs, a body is sometimes referred to as a procedure body, because lambda is the fundamental form for the implementation of forms which use bodies.) A body is a region for keywords and variables created by definitions directly within the body, or inside of splicing constructs (such as begin, splicing-let-syntax, and splicing-letrec-syntax) within the body. A body is concluded with an expression and may also contain additional expressions before, between, or after the definitions.

Bodies are first processed by the expander according to the process defined in Macrological Fascicle, “Expansion process”, a process which also removes any splicing constructs by replacing them with their expanded subforms. The expander also takes note of the set of identifier names bound by syntax or variable definitions within the entire region of the body. It is a syntax violation if any definition attempts to bind the same identifier more than once, or attempts to bind the same identifier as another definition within the same body (including in any splicing constructs).

After this process, a body consists only of variable definitions and expressions in their fully expanded core forms. These are further processed for evaluation in groups as follows. An expanded ⟨body⟩ has the form

⟨variable definition–expression group⟩ … ⟨expression⟩

The ⟨expression⟩ is referred to as the final expression of the body. A ⟨variable definition–expression group⟩ has the form

⟨variable definition⟩ … ⟨expression⟩

A ⟨variable definition⟩ is any implementation-dependent core form which is a definition form for variables. The ⟨expression⟩s of a ⟨variable definition–expression group⟩ are referred to as the non-final expressions of the body. It is a syntax violation if the expanded content of a body does not conform to these rules.

Each ⟨variable definition–expression group⟩ is converted into the equivalent of a letrec*-values (see section 4.2) for the ⟨variable definition⟩s in that group, although this letrec*-values does not contain a body itself but only a sequence of expressions, which are evaluated from left to right. The sequence of expressions consists of the ⟨expression⟩s within the respective ⟨variable definition–expression group⟩, followed by the corresponding conversion of the next ⟨variable definition–expression group⟩, or by the final ⟨expression⟩ if there are no further ⟨variable definition–expression group⟩s. Implementations should signal a syntax violation if the expansion of the right-hand side of any ⟨variable definition⟩, or the expansion of any ⟨expression⟩, refers to the name of any identifier which is a variable defined by a ⟨variable definition–expression group⟩ which is to the right of the ⟨variable definition–expression group⟩ in which it appears.

Rationale: Scheme has traditionally only allowed a single group of definitions at the head of a body, followed by at least one expression. Experience has shown that it is often useful to be able to mix the two types of forms in bodies, especially for error checking and logging of intermediate results. However, typical optimized implementation techniques for the semantics of the letrec or letrec* underlying a traditional Scheme body work only when the right-hand sides of definitions, and by extension the entire block of definitions, are free of side-effects or uses of first-class continuations. Since non-final expressions in a body are only useful for their side-effects or continuation invocations, simply incorporating expressions into the sequence of letrec* bindings invariably inhibits these optimizations. The compilation scheme described here provides the convenience of mixing definitions and expressions in any order, while ultimately grouping the definitions so that optimization can still happen as in implementations of previous revisions of this report. Since the expander still treats syntax keyword bindings throughout the whole body as belonging to a single region, and implementations should treat attempts at forward reference to a variable defined in a future group of definitions and expressions as a syntax violation, the property that a body is a single region for bindings is maintained: the only practical restriction is that it is not possible to create mutually-recursive definitions between distinct ⟨variable definition–expression group⟩s, which is necessary to ensure each letrec*-values equivalent form in the transformed body can still be optimized.

Issue: The syntax and semantics of bodies described above represent an initial attempt to find a satisfactory means of allowing Scheme programmers to mix definitions and expressions in any order within bodies, as requested by voters on the Stygian Blue ballot. They correspond to a variant of semantics originally proposed by Sergei Egorov in SRFI 251, adapted for the expansion order originally specified by R6RS and described in the macrological fascicle. There is also a permissive provision allowing implementations to adopt semantics more like those of SRFI 245 or R⁶RS program bodies, which do not restrict forward reference between different ⟨variable definition–expression group⟩s. This permissive provision is the “should” in the recommendation to signal a syntax violation in the case of a reference to a variable in a subsequent ⟨variable definition–expression group⟩.

Issue (2): The working group is unsatisfied with the creation of implicit lexical contours by ⟨variable definition–expression group⟩s, especially considering the behaviour of identifier syntax defined in the body (which may inadvertently flout good Scheme style by not behaving exactly like a variable) and the behaviour of macros which may expand to a combination of a definition and an expression. The R⁶RS program body semantics are also problematic for the optimization-related reasons described above in the rationale. Further, with semantics derived from those of R⁶RS program bodies, it would not be safely possible to use continuations to return twice from any expression in a body before that body’s final definition. (The R⁶RS encourages implementations to raise a violation exception in this case.) Note that the permissive provision above implies that implementations which take advantage of it cannot impose such a restriction on multiple return from expressions.

The working group is especially keen to receive feedback on this matter from the Scheme community.

Description

The continuations of all of the non-final expressions within a body (i.e. of the expanded expressions within the created letrec*-values equivalent) accept any number of values and discard them. The continuation of the final expression of a body accepts the same number of values as the continuation of the body itself, and passes the values to that continuation. (A body may be in tail context, in which case the continuation of the final expression is the same as the continuation of the body itself.)

2.7: Storage model

Note: This section will be extended by a future fascicle.

Variables and objects implicitly refer to locations or sequences of locations. A vector, for example, contains as many locations as there are elements in the vector. A new value may be stored into one of these locations using the vector-set! procedure, but the vector contains the same locations as before.

An object fetched from a location, by a variable access or by a procedure such as car, vector-ref, or string-ref, is equivalent in the sense of eqv? to the object last stored in the location before the fetch.

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 refer to them.

2.8: Active procedure calls

Implementations of Scheme must be properly tail-recursive. Procedure calls that occur in certain syntactic contexts called tail 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. Flow-control will include delimited continuations probably. In the absence of captured continuations, calls could return at most once and the active calls would be those that had not yet returned. 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 properly tail-recursive implementation, iteration can be expressed using the ordinary procedure-call mechanics, so that special iteration constructs are useful only as syntactic sugar.

A formal definition of proper tail recursion can be found in [8].

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.

Non-tail calls

Implementations of Scheme should also support a practically unbounded number of active calls which are not tail calls. The number of active non-tail calls should be bounded only by the amount of storage space available to the program. Any other behaviour is implementation-specified; however, implementations which do not support unbounded numbers of active non-tail calls should raise an exception with condition type &implementation-restriction upon an attempt to activate a non-tail call which breaks the implementation’s limit.

Rationale

The need to support unbounded numbers of non-tail calls is related to the requirement for safety xref to erroneous fascicle. Consider the following implementation of a simplified version of the map procedure xref to valued fascicle:

(define (map proc ls)
  (if (pair? ls)
      (cons (proc (car ls))
            (map proc (cdr ls)))
      '()))

Without a guarantee that practically unbounded numbers of non-tail calls may be active at any one time, it is unsafe to call this procedure on a list ls of any particular length, because a list longer than the number of allowed active non-tail calls would not behave in the expected way.

Description

The tail contexts in which tail calls occur are defined inductively. In general, any body or sequence of expressions has its final expression in a tail context if the body or sequence of expressions itself is part of the syntax of a syntactic form which itself is used in a tail context. This report usually notes when final expressions are in tail contexts, and always notes explicitly when final expressions are not required to be in a tail context. Implementations which provide libraries with additional syntactic forms in addition to those defined in this report must also document any case in which a body or sequence of expressions which forms part of a syntactic form is never in tail context, even if the syntactic form as a whole is in a tail context.

Certain built-in procedures must also perform tail calls. The first argument passed to apply and to call-with-current-continuation, and the second argument passed to call-with-values, must be called via a tail call. Implementations which provide libraries with additional procedures whose final result is the unmodified result of calling some other procedure given as an argument should document whether the arguments to those procedures are tail-called or not.

4: Foundational library

Note: This chapter will be extended by a future fascicle.

4.1: Procedures

4.1.1: `lambda`

(lambda ⟨formals⟩ ⟨body⟩) syntax

Syntax

⟨Body⟩ is a body as described by 2.6.

⟨Formals⟩ must have one of the following forms:

(⟨variable1₁⟩ …): The procedure takes a fixed number of arguments; when the procedure is called, the arguments are stored in the bindings of the corresponding variables.
⟨variable⟩: The procedure takes any number of arguments; when the procedure is called, the sequence of arguments is converted into a newly allocated list, and the list is stored in the binding of the ⟨variable⟩.
(⟨variable₁⟩ … ⟨variable_n⟩ . ⟨variable_n+1⟩): If a period . precedes the last variable, then the procedure takes n or more arguments, where n is the number of parameters before the period (there must be at least one). The value stored in the binding of the last variable is a newly allocated list of the arguments left over after all the other arguments have been matched up against the other parameters.

It is a syntax violation for a ⟨variable⟩ to appear more than once in ⟨formals⟩.

Semantics

A lambda expression evaluates to a procedure. The environment in effect when the lambda expression is evaluated is remembered as part of the procedure. When the procedure is later called with some arguments, the environment in which the lambda expression was evaluated is extended by binding the variables in the parameter list to fresh locations, and the resulting argument values are stored in those locations. Then, the forms in the body of the lambda expression (which may contain definitions and thus represent a letrec* form, see todo) are evaluated sequentially in the extended environment. The results of the last expression in the body are returned as the results of the procedure call; the last expression in the body is in tail context.

Each procedure created as the result of evaluating a lambda expression receives (conceptually) a fresh location tag, distinct from the location tags of all existing procedures. Implementations may avoid creating a new procedure object when evaluating a lambda expression if they can prove before doing so that the behaviour of the resulting procedure when called would be the same (returning the same values and having the same side effects) as an existing procedure, for all arguments to that procedure. In this case, the lambda expression will evaluate to that existing procedure, which will retain the same location tag it was given when created.

4.1.2: `case-lambda`

(case-lambda ⟨case-lambda clause⟩ …) syntax

Syntax

Each ⟨case-lambda clause⟩ must be of the form

⟨case lambda clause⟩: ::= (⟨formals⟩ ⟨body⟩)

⟨Formals⟩ must be as in a lambda form.

Semantics

A case-lambda expression evaluates to a procedure. This procedure, when applied, tries to match its arguments to the ⟨case-lambda clause⟩s in order from left to right. The arguments match a clause if one of the following conditions is fulfilled:

⟨Formals⟩ has the form (⟨variable⟩ …) and the number of arguments is the same as the number of formal parameters in ⟨formals⟩.
⟨Formals⟩ has the form (⟨variable₁⟩ … ⟨variable_n⟩ . ⟨variable_n+1⟩) and the number of arguments is at least n.
⟨Formals⟩ has the form variable.

For the leftmost clause matched by the arguments, the variables of the ⟨formals⟩ are bound to fresh locations containing the argument values in the same arrangement as with lambda.

The last expression of a ⟨body⟩ in a case-lambda expression is in tail context.

The procedure returned by case-lambda is given a location tag, under the same conditions as procedures returned by lambda.

Example

(define foo
  (case-lambda
   (() 'zero)
   ((x) (list 'one x))
   ((x y) (list 'two x y))
   ((a b c d . e) (list 'four a b c d e))
   (rest (list 'rest rest))))

(foo)⇒ zero

(foo 1)⇒ (one 1)

(foo 1 2)⇒ (two 1 2)

(foo 1 2 3)⇒ (rest (1 2 3))

(foo 1 2 3 4)⇒ (four 1 2 3 4 ())

Implementation

The case-lambda form can be defined in terms of the lambda procedure. We recommend implementing case-lambda as a primitive form, and implementing lambda in terms of case-lambda, because it is more efficient and easier to optimize.

(define-syntax case-lambda
  (syntax-rules ()
    ((case-lambda (params body0 ...) ...)
      (lambda args
        (let ((len (length args)))
          (letrec-syntax
            ((cl (syntax-rules ::: ()
                   ((cl)
                     (error "no matching clause"))
                   ((cl ((p :::) . body) . rest)
                    (if (= len (length '(p :::)))
                        (apply (lambda (p :::)
                                 . body)
                               args)
                        (cl . rest)))
                   ((cl ((p ::: . tail) . body)
                        . rest)
                    (if (>= len (length ’(p :::)))
                        (apply
                         (lambda (p ::: . tail)
                         . body)
                         args)
                        (cl . rest))))))
             (cl (params body0 ...) ...)))))))

4.1.3: `procedure?`

(procedure? obj) procedure

Returns #t if obj is a procedure; otherwise, returns #f.

(procedure? car)⇒ #t

(procedure? 'car)⇒ #f

(procedure? (lambda (x) (* x x)))⇒ #t

(procedure? (lambda (x) (* x x)))⇒ #f

4.1.4: `apply`

(apply proc arg₁ … rest-args) procedure

Requirements

rest-args must be a list. proc should accept n arguments, where n is the number of args plus the length of the list rest-args.

Description

The apply procedure calls proc with the elements of the list (append (list arg₁ …) rest-args) as the actual arguments. If a call to apply occurs in a tail context, the call to proc is also in a tail context. The dynamic environment of the call to proc is the same as the dynamic environment of the call to apply.

Examples

(apply + (list 3 4))⇒ 7

(define compose
  (lambda (f g)
    (lambda args
      (f (apply g args)))))

((compose sqrt *) 12 75)⇒ 30

4.1.5: `values`

(values obj …) procedure

Delivers all of its arguments to its continuation.

4.1.6: `call-with-values`

(call-with-values producer consumer) procedure

Requirements

producer must be a procedure which accepts zero arguments. consumer must be a procedure which accepts as many arguments as the number of values consumer returns when applied to zero arguments.

Description

The call-with-values procedure calls producer with no arguments and a continuation that, when passed some values, calls the consumer procedure with those values as arguments. The continuation for the call to consumer is the continuation of the call to call-with-values. It is a domain error if the consumer does not accept as many values as producer returned. The dynamic environment of the calls to producer and consumer is the same as the dynamic environment of the call to call-with-values.

If a call to call-with-values occurs in a tail context, the call to consumer is also in a tail context.

Examples

(call-with-values (lambda () (values 4 5))
                  (lambda (a b) b))⇒ 5

(call-with-values * -)⇒ -1

(call-with-values
 (lambda () (values 'a 'b))
 (case-lambda
   (() 'zero)
   ((x) (list 'one x))
   (xs (cons 'more xs))))⇒ (more a b)

4.2: Variable definition and binding forms

4.2.1: `define`

(define ⟨variable⟩ ⟨expression⟩) syntax
(define ⟨variable⟩) syntax
(define (⟨procedure spec⟩ ⟨formals⟩) ⟨body⟩) syntax
(define (⟨procedure spec⟩ . ⟨formal⟩) ⟨body⟩) syntax

Syntax

⟨Variable⟩ is an identifier. ⟨Procedure spec⟩ is either an identifier or one of the following:

⟨procedure spec⟩: ::= (⟨procedure spec⟩ ⟨formals⟩); ::= (⟨procedure spec⟩ . ⟨formal⟩)

⟨Formal⟩ is a variable. ⟨Formals⟩ is one of the following:

⟨formals⟩: ::= (⟨variable⟩ …); ::= (⟨variable₁⟩ ⟨variable₂⟩ … . ⟨variable_n⟩)

Within the ⟨formal⟩ and ⟨formals⟩, no ⟨variable⟩ may occur more than once, including in different ⟨procedure spec⟩s.

Semantics

Define is a definition form (see section 2.3) used to create variable bindings; it may appear anywhere other definitions may appear.

The first form of define evaluates the ⟨expression⟩ it is given, binds the identifier named by ⟨variable⟩ to a new location and assigns the value of the evaluation to that location. An assertion violation must be signalled if the ⟨expression⟩ returns zero values or more than one value. The continuation of the ⟨expression⟩ must not be returned to more than once: implementations should signal an assertion violation when they detect this has occurred.

The second form of define binds the identifier named by ⟨variable⟩ to a new location and assigns an unspecified value to that location.

The third and fourth variants of define are equivalent to a recursive transformation into a define expression of the first form. Define in these forms binds the identifier named by the innermost nested ⟨procedure spec⟩ to a procedure that may otherwise be expressed as a number of nested lambda expressions. The ⟨formal⟩ or ⟨formals⟩ on the left-hand side of the define form itself become the ⟨formals⟩ of the outermost lambda expression; those of the ⟨procedure spec⟩ nested within each subsequent level of nesting become the next most inner lambda expression ⟨formals⟩. The innermost lambda expression contains the ⟨body⟩ from the define form.

Note: The second form of define is allowed by R⁶RS but the small language report did not include it. The ability to define higher-order procedures by nesting list-structured forms on the left-hand side of define is new in this fascicle, and is not in the small language report nor in any previous Scheme report. The (scheme base) library must export the same binding as whatever large language library this ends up in.

Examples

The basic form of define may be used as follows.

(define three 3)
(define add3
  (lambda (x) (+ x three)))
(add3 3)⇒ 6

(define first car)
(first '(1 2))⇒ 1

The procedure-definition form of define may be used as follows.

(define (step u)
  (if (<= 0 u 1) 1 0))

(step -0.5)⇒ 0

(step 2/3)⇒ 1

(define ((equal?-proc x) y)
  (equal? x y))

(define three? (equal?-proc 3))

(three? 3)⇒ #t

(three? 4)⇒ #f

((equal-proc? 4) 4)⇒ #t

4.2.2: `define-values`

(define-values ⟨formals⟩ ⟨expression⟩) syntax

Syntax

⟨Formals⟩ is as for a lambda expression.

Semantics

define-values is a definition form used to create variable bindings from an expression whose evaluation may return multiple values.

The ⟨expression⟩ is evaluated, and the variables named by the ⟨formals⟩ are bound to the return values in the same way that the ⟨formals⟩ in a lambda expression are matched to the arguments in a procedure call. If the evaluation of the ⟨expression⟩ returns a number of values which cannot be reconciled with the ⟨formals⟩, an assertion violation is signalled.

Examples

(define-values (x y) (exact-integer-sqrt 17))
(list x y)⇒ (4 1)

(let ()
  (define-values (x y) (values 1 2))
  (+ x y))⇒ 3

(define-values vs (floor/ 14 8))
vs⇒ (1 6)

Implementation

This is an implementation of define-values in terms of define. It may be easier to implement define on top of define-values.

(define-syntax define-values
  (syntax-rules ()
    ((define-values () expr)
     (define dummy
       (call-with-values (lambda () expr)
                         (lambda args #f))))
    ((define-values (var) expr)
     (define var expr))
    ((define-values (var0 var1 ... varn) expr)
     (begin
       (define var0
         (call-with-values (lambda () expr)
                           list))
       (define var1
         (let ((v (cadr var0)))
           (set-cdr! var0 (cddr var0))
           v)) ...
       (define varn
         (let ((v (cadr var0)))
           (set! var0 (car var0))
           v))))
    ((define-values (var0 var1 ... . varn) expr)
     (begin
       (define var0
         (call-with-values (lambda () expr)
                           list))
       (define var1
         (let ((v (cadr var0)))
           (set-cdr! var0 (cddr var0))
           v)) ...
       (define varn
         (let ((v (cdr var0)))
           (set! var0 (car var0))
           v))))
    ((define-values var expr)
     (define var
       (call-with-values (lambda () expr)
                         list)))))

4.2.3: `define-alias`

(define-alias ⟨identifier₁⟩ ⟨identifier₂⟩) syntax

Semantics

Define-alias is a definition form which causes ⟨identifier₁⟩ to refer to the same binding as ⟨identifier₂⟩. Uses of ⟨identifier₁⟩ will, throughout the region of the definition, be the same as uses of ⟨identifier₂⟩ in the sense of free-identifier=?, but not in the sense of bound-identifier=? (see Macrological Fascicle, “Identifiers”). In particular, shadowing of ⟨identifier₁⟩ or ⟨identifier₂⟩ within regions nested inside the region where the define-alias has effect will locally cancel the effect of define-alias.

⟨Identifier₂⟩ may refer to any kind of binding, including a variable, syntax keyword, or a pattern variable. Because ⟨identifier₁⟩ receives the same binding as ⟨identifier₂⟩, its binding has the same binding type as ⟨identifier₂⟩. If ⟨identifier₂⟩ is a variable or pattern variable, it is bound to the same location as ⟨identifier₁⟩. If ⟨identifier₂⟩ is a syntax keyword, use of ⟨identifier₂⟩ within the region of the definition invokes the same transformer on the macro use as a use of ⟨identifier₁⟩ would. It is a syntax violation if the ⟨identifier₂⟩ is not already bound.

Examples

(define foo 3)
(define-alias bar foo)

(+ foo bar)⇒ 6

(let-syntax
    ((s (syntax-rules (foo)
          ((_ foo) #t)
          ((_ _) #f))))
  (values (s foo)
          (s bar)
          (s s)))⇒ #t #t #f

4.2.4: `let`

(let ⟨bindings⟩ ⟨body⟩) syntax
(let ⟨name⟩ ⟨bindings⟩ ⟨body⟩) syntax

Syntax

⟨Bindings⟩ has the form

⟨bindings⟩: ::= ((⟨variable₁⟩ ⟨init₁⟩) …)

where each ⟨init⟩ is an expression. Any variable must not appear more than once in the ⟨variable⟩s. ⟨Name⟩, if present, is an identifier.

Semantics

Let is a binding expression.

In the first form of, evaluation of a let expression proceeds as follows. The ⟨init⟩ expressions of the ⟨bindings⟩ are evaluated in an unspecified order in the current environment, the ⟨variable⟩s are bound to fresh locations holding the results, and the result of evaluating the ⟨body⟩ in this extended environment is returned. The ⟨body⟩ is evaluated in tail context if the let expression is in a tail context.

In the second form, commonly referred to as “named let”, the ⟨name⟩ is additionally bound as a variable within the evaluation of the ⟨body⟩ to a procedure whose parameters are the bound variables and whose body is ⟨body⟩. Thus the execution of ⟨body⟩ may be repeated by invoking the procedure named by ⟨variable⟩.

Examples

(let ((x 2) (y 3))
  (* x y))⇒ 6

(let ((x 2) (y 3))
  (let ((x 7)
        (z (+ x y)))
    (* z x)))⇒ 35

(let loop ((numbers '(3 -2 1 6 -5))
          (nonneg '())
          (neg '()))
  (cond ((null? numbers) (list nonneg neg))
        ((>= (car numbers) 0)
         (loop (cdr numbers)
               (cons (car numbers) nonneg)
               neg))
        ((< (car numbers) 0)
         (loop (cdr numbers)
               nonneg
               (cons (car numbers) neg)))))⇒ ((6 1 3) (-5 -2))

Implementation

(define-syntax let
  (syntax-rules ()
    ((_ ((var init) ...) body_0 body_1 ...)
     ((lambda (var ...) body_0 body_1 ...) init ...))
    ((_ name ((var init) ...) body_0 body_1 ...)
     ((rec (name var ...) body_0 body_1 ...) init ...))))

4.2.5: `let*`

(let* ⟨bindings⟩ ⟨body⟩) syntax

Syntax

⟨Bindings⟩ is as for let, except that the same variable can be named multiple times.

Semantics

The let* form is similar to let, but the ⟨init⟩s are evaluated and bindings created sequentially from left to right, with the region of each binding including the bindings to its right as well as ⟨body⟩. Thus the second ⟨init⟩ is evaluated in an environment in which the first binding is visible and initialized, and so on.

Example

(let ((x 2) (y 3))
  (let* ((x 7)
         (z (+ x y)))
    (* z x)))⇒ 70

Implementation

(define-syntax let*
 (syntax-rules ()
   ((let* () body1 body2 ...)
    (let () body1 body2 ...))
   ((let* ((name1 val1) (name2 val2) ...)
      body1 body2 ...)
    (let ((name1 val1))
      (let* ((name2 val2) ...)
        body1 body2 ...)))))

4.2.6: `let-values`

(let-values ⟨mv bindings⟩ ⟨body⟩) syntax

Syntax

⟨Mv bindings⟩ has the form

⟨mv bindings⟩: ::= ((⟨formals₁⟩ ⟨init₁⟩) …)

where each ⟨formals⟩ is as for a define-values definition and each ⟨init⟩ is an expression. Any variable must not appear more than once in the set of all ⟨formals⟩.

Semantics

The ⟨init⟩ expressions of the ⟨mv bindings⟩ are evaluated in an unspecified order as in let; and the variables occurring in the ⟨formals⟩ are bound to fresh locations containing the values returned by the ⟨init⟩s, where the ⟨formals⟩ are matched to the return values in the same way that the ⟨formals⟩ in a lambda expression are matched to the arguments in a procedure call. Then, the ⟨body⟩ is evaluated in the extended environment, and the values of the last expression of ⟨body⟩ are returned. Each binding of a variable has ⟨body⟩ as its region. If the ⟨formals⟩ do not match, an assertion violation is signalled.

Examples

(let-values (((a b) (values 1 2))
             ((c d) (values 3 4)))
  (list a b c d))⇒ (1 2 3 4)

(let-values (((a b . c) (values 1 2 3 4)))
  (list a b c))⇒ (1 2 (3 4))

(let ((a 'a) (b 'b) (x 'x) (y 'y))
  (let-values (((a b) (values x y))
               ((x y) (values a b)))
    (list a b x y)))⇒ (x y a b)

Implementation

(define-syntax let-values
 (syntax-rules ()
   ((let-values (binding ...) body0 body1 ...)
    (let-values "bind"
        (binding ...) () (begin body0 body1 ...)))
   
   ((let-values "bind" () tmps body)
    (let tmps body))
   
   ((let-values "bind" ((b0 e0)
        binding ...) tmps body)
    (let-values "mktmp" b0 e0 ()
        (binding ...) tmps body))
   
   ((let-values "mktmp" () e0 args
        bindings tmps body)
    (call-with-values 
      (lambda () e0)
      (lambda args
        (let-values "bind"
            bindings tmps body))))
    ((let-values "mktmp" (a . b) e0 (arg ...)
        bindings (tmp ...) body)
    (let-values "mktmp" b e0 (arg ... x)
        bindings (tmp ... (a x)) body))
   
   ((let-values "mktmp" a e0 (arg ...)
       bindings (tmp ...) body)
    (call-with-values
      (lambda () e0)
      (lambda (arg ... . x)
        (let-values "bind"
            bindings (tmp ... (a x)) body))))))

4.2.7: `let*-values`

(let*-values ⟨mv bindings⟩ ⟨body⟩) syntax

Syntax

⟨Mv bindings⟩ is as for let-values, except that a variable which appears in one ⟨formals⟩ can appear again in a subsequent ⟨formals⟩.

Semantics

The let*-values construct is similar to let-values, but the ⟨init⟩s are evaluated and bindings created sequentially from left to right, with the region of the bindings of each ⟨formals⟩ including the ⟨init⟩s to its right as well as ⟨body⟩. Thus the second ⟨init⟩ is evaluated in an environment in which the first set of bindings is visible and initialized, and so on.

Example

(let ((a 'a) (b 'b) (x 'x) (y 'y))
  (let*-values (((a b) (values x y))
                ((x y) (values a b)))
    (list a b x y)))⇒ (x y x y)

Implementation

(define-syntax let*-values
 (syntax-rules ()
   ((let*-values () body0 body1 ...)
    (let () body0 body1 ...))

   ((let*-values (binding0 binding1 ...)
        body0 body1 ...)
    (let-values (binding0)
      (let*-values (binding1 ...)
        body0 body1 ...)))))

4.2.8: `letrec`

(letrec ⟨bindings⟩ ⟨body⟩) syntax

Syntax

⟨Bindings⟩ is as for let.

Semantics

The ⟨variable⟩s are bound to fresh locations, the ⟨init⟩s are evaluated in the resulting environment (in some unspecified order), each ⟨variable⟩ is assigned to the result of the corresponding ⟨init⟩, the ⟨body⟩ is evaluated in the resulting environment, and the values of the last expression in ⟨body⟩ are returned. Each binding of a ⟨variable⟩ has the entire letrec expression as its region, making it possible to define mutually recursive procedures.

It must be possible to evaluate each ⟨init⟩ without assigning or referring to the value of any ⟨variable⟩. Implementations should signal an assertion violation if they detect that the value of a ⟨variable⟩ is accessed or assigned during the evaluation of any ⟨init⟩ (within the limitations of one particular evaluation order and order of evaluating the ⟨init⟩ expressions). In the most common uses of letrec, all the ⟨init⟩s are lambda expressions and the restriction is satisfied automatically.

The continuation of each ⟨init⟩ should not be invoked more than once. Implementations should detect this and signal an assertion violation.

The ⟨body⟩ is evaluated in tail context if the letrec expression as a whole is in tail context.

Example

(letrec ((even?
         (lambda (n)
           (if (zero? n)
               #t
               (odd? (- n 1)))))
        (odd?
         (lambda (n)
           (if (zero? n)
               #f
               (even? (- n 1))))))
(even? 66))⇒ #t

Implementation

This implements letrec on top of set! and let. We recommend implementing letrec as a primitive, to optimize for the common case of mutually recursive functions. See [4].

The following implementation catches uses of identifiers prior to all of them being initialized. It does this by binding each value to identifier syntax that translates references and assignments to function calls that check the restrictions of letrec dynamically.

(define-syntax letrec
  (lambda (stx)
    (syntax-case stx ()
      ((_ ((var init) ...) body_0 body_1 ...)
       (with-syntax (((temp ...) (generate-temporaries #'(var ...))))
         #'(let ((all-init? #f))
             (let ((temp
                    (let ((cell #f))
                      (case-lambda
                        (()
                         (unless all-init?
                           (assertion-violation 'letrec
                                                "variable used before all inits"
                                                (quote-syntax id)))
                         cell)
                        ((val initial?)
                         (unless (or initial? all-init?)
                           (assertion-violation 'letrec
                                                "variable set! before all inits"
                                                (quote-syntax id)))
                         (set! cell val))))) ...)
               (let-syntax ((var (identifier-syntax
                                   (_ (temp))
                                   ((set! _ val) (temp val #f)))) ...)
                 (temp init #t) ...
                 (set! all-init? #t)
                 (let () body_0 body_1 ...)))))))))

4.2.9: `letrec*`

(letrec* ⟨bindings⟩ ⟨body⟩) syntax

Syntax

⟨Bindings⟩ is as for let.

Semantics

The ⟨variable⟩s are bound to fresh locations, each ⟨variable⟩ is assigned in left-to-right order to the result of evaluating the corresponding ⟨init⟩ (interleaving evaluations and assignments), the ⟨body⟩ is evaluated in the resulting environment, and the values of the last expression in ⟨body⟩ are returned. Despite the left-to-right evaluation and assignment order, each binding of a ⟨variable⟩ has the entire letrec* expression as its region, making it possible to define mutually recursive procedures.

It must be possible to evaluate each ⟨init⟩ without accessing or assigning the value of the corresponding ⟨variable⟩ or of any ⟨variable⟩ whose binding follows it in ⟨bindings⟩. Implementations should signal an assertion violation if they detect that this restriction is violated.

Note: Letrec* differs from letrec in that the order of evaluation of ⟨init⟩ expressions is strictly defined as left-to-right, and the values of previously-bound variables may be accessed during the evaluation of ⟨init⟩. While implementations which do not follow this report’s recommendation to signal an assertion violation upon use of previously-bound variables in letrec are conforming, programmers cannot rely on this behaviour in portable code.

The difference between letrec and letrec* is not quite analogous to the difference between let and let*, because in let* (but not in let) the same variable can be named multiple times in different binding clauses, which is not allowed in letrec nor in letrec*.

The continuation of each ⟨init⟩ should not be invoked more than once. Implementations should detect this and signal an assertion violation.

The ⟨body⟩ is evaluated in tail context if the letrec* expression as a whole is in tail context.

Examples

(letrec* ((p
           (lambda (x)
             (+ 1 (q (- x 1)))))
          (q
           (lambda (y)
             (if (zero? y)
                 0
                 (+ 1 (p (- y 1))))))
          (x (p 5))
          (y x))
  y)⇒ 5

(define (means ton)
  (letrec*
    ((mean
      (lambda (f g)
        (f (/ (sum g ton) n))))
     (sum
      (lambda (g ton)
        (if (null? ton)
          0
          (if (number? ton)
              (g ton)
              (+ (sum g (car ton))
                 (sum g (cdr ton)))))))
     (n (sum (lambda (x) 1) ton)))
    (values (mean values values) ; arithmetic
            (mean exp log)       ; geometric
            (mean / /))))        ; harmonic

(means '(3 (1 4)))⇒ 8/3 2.289428... 36/19

Implementation

Refer to implementation of letrec for comments on this style of implementation and possible ways to implement it as a primitive.

(define-syntax letrec*
  (lambda (stx)
    (syntax-case stx ()
      ((_ ((var init) ...) body_0 body_1 ...)
       (with-syntax (((temp ...) (generate-temporaries #'(var ...))))
         #'(let ((temp
                  (let ((cell #f)
                        (set? #f))
                    (case-lambda
                      (()
                       (if set?
                           cell
                           (assertion-violation 'letrec*
                                                "variable used before assignment"
                                                (quote-syntax var))))
                      ((val safe?)
                       (when (and (not safe?) (not set?))
                         (assertion-violation 'letrec*
                                              "variable set! before initial assignment"
                                              (quote-syntax var)))
                       (set! set? #t)
                       (set! cell val)))))
                 ...)
             (let-syntax
                 ((var
                   (identifier-syntax
                    (_ (temp))
                    ((set! _ val) (temp val #f))))
                  ...)
               (temp init #t) ...
               (let () body_0 body_1 ...))))))))

4.2.10: `letrec-values`

(letrec-values ⟨mv bindings⟩ ⟨body⟩) syntax

Syntax

⟨Mv bindings⟩ is as for let-values.

Semantics

All the variables in the ⟨formals⟩ are bound to fresh locations, the ⟨init⟩s are evaluated in the resulting environment (in some unspecified order), and each variable of the ⟨formals⟩ is assigned to a corresponding value or list of values from the result of those ⟨formals⟩’s ⟨init⟩, the ⟨body⟩ is evaluated in the resulting environment, and the values of the last expression in ⟨body⟩ are returned.

The same restrictions on accessing or assigning the value of a variable named by the ⟨formals⟩ during the evaluation of any ⟨init⟩ expression, and on returning to the continuation of an ⟨init⟩ expression, which apply to letrec apply also to letrec-values. Implementation should signal an assertion violation if they detect that these restrictions are violated.

The ⟨body⟩ is evaluated in tail context if the letrec-values expression as a whole is in tail context.

Examples

(letrec-values
    (((even? odd?)
      (values (lambda (n)
                (or (zero? n)
                    (odd? (- n 1))))
              (lambda (n)
                (and (not (zero? n))
                     (even? (- n 1)))))))
  (even? 12))⇒ #t

Implementation

This implementation relies on letrec* to detect and raise errors when the program uses a bound variable in violation of the description above.

(define-syntax letrec-values
  (lambda (stx)
    (define (disentangle-formal formal)
      (syntax-case formal ()
        (((id ...) formals-tmp)
         (with-syntax (((ix ...) (iota (length #'(id ...)))))
           #'((id (vector-ref formals-tmp ix)) ...)))
        (((id ... . rest) formals-tmp)
         (with-syntax (((ix ...) (iota (length #'(id ...)))))
           #'((id (vector-ref (vector-ref formals-tmp 0) ix)) ...
              (rest (vector-ref formals-tmp 1)))))
        ((id formals-tmp) (identifier? #'id))
         #'((id formals-tmp))))

    (define (initialize-temp pair)
      (syntax-case pair ()
        ((formals-tmp init (id ...))        ; dotted formals
         #'(formals-tmp (call-with-values
                         (lambda () init)
                         vector)))
        ((formals-tmp init (id ... . rest)) ; normal formals
         #'(formals-tmp (call-with-values
                         (lambda () init)
                         (lambda (id ... . rest)
                           (vector (vector id ...) rest)))))))

    (syntax-case stx ()
      ((_ ((formals init) ...) body_0 body_1 ...)
       (with-syntax (((formals-tmp ...) (generate-temporaries
                                         #'(formals ...))))
         #`(letrec* (#,@(map initialize-temp #'((formals-tmp formals init)
                                                ...))
                     #,@(append-map disentangle-formal
                                    #'((formals formals-tmp) ...)))
             body_0 body_1 ...))))))

4.2.11: `letrec*-values`

(letrec*-values ⟨mv bindings⟩ ⟨body⟩) syntax

Syntax

⟨Mv bindings⟩ is as for let-values.

Semantics

All the variables in the ⟨formals⟩ are bound to fresh locations, each variable of the ⟨formals⟩ is assigned in left-to-right order to a corresponding value or list of values from the result of evaluating its ⟨formals⟩’ ⟨init⟩ (interleaving evaluations and assignments), the ⟨body⟩ is evaluated in the resulting environment, and the values of the last expression in ⟨body⟩ are returned.

The same restrictions on the evaluation of any ⟨init⟩ expression referring to variable named in the corresponding ⟨formals⟩ or in any ⟨formals⟩ to the right of it, and on returning to the continuation of an ⟨init⟩ expression, which apply to letrec* apply also to letrec*-values. Implementation should signal an assertion violation if they detect that these restrictions are violated.

The ⟨body⟩ is evaluated in tail context if the letrec*-values expression as a whole is in tail context.

Implementation

This implementation relies on letrec* to detect and raise errors when the program uses a bound variable in violation of the description above.

(define-syntax letrec*-values
  (lambda (stx)
    (define (disentangle-formal* formals)
      (syntax-case formals ()
        (((id ...) init)
         (with-syntax (((temp) (generate-temporaries #'(temp))))
           (with-syntax (((ix ...) (iota (length #'(id ...)))))
             #'((temp (call-with-values
                       (lambda () init)
                       vector))
                (id (vector-ref temp ix)) ...))))
         (((id ... . rest) init)
          (with-syntax (((temp) (generate-temporaries #'(temp))))
            (with-syntax (((ix ...) (iota (length #'(id ...)))))
              #'((temp (call-with-values
                        (lambda () init)
                        (lambda (id ... . rest)
                          (vector (vector id ...) rest))))
                 (id (vector-ref (vector-ref temp 0) ix)) ...
                 (rest (vector-ref temp 1))))))
         ((id init) (identifier? #'id)
          #'((id init)))))

    (syntax-case stx ()
      ((_ ((formals init) ...) body_0 body_1 ...)
       #`(letrec* #,(append-map disentangle-formal* #'((formals init) ...))
           body_0 body_1 ...)))))

4.2.12: `rec`

(rec ⟨variable⟩ ⟨expression⟩) syntax
(rec (⟨variable⟩ ⟨formals⟩) ⟨body⟩) syntax
(rec (⟨variable⟩ . ⟨formal⟩) ⟨body⟩) syntax

Syntax

⟨Formal⟩ and ⟨formals⟩ are as for define.

Semantics

Rec is a form for creating self-recursive expressions and procedures.

In the first form of rec, the ⟨expression⟩ is evaluated in an environment in which the ⟨variable⟩ is bound to a location which will eventually contain the result of evaluating that expression. If evaluation of the ⟨expression⟩ results in an attempt to access or assign the value of the ⟨variable⟩, or if the continuation of the evaluation of the ⟨expression⟩ is returned to more than once, an assertion violation should be signalled. This form of rec can be used to create self-recursive procedures or lazy data structures with delay, but not cyclical values.

The second and third forms of rec evaluate to a procedure whose environment contains a binding for the ⟨variable⟩ which refers to the procedure itself. The ⟨formals⟩ or ⟨formal⟩ give the arguments to the resulting procedure in the same way as in the left-hand side of define.

Note: This form is a combination of two historical forms, rec and named-lambda, which appeared in the RRRS but have not been included in any Scheme report since. Only the first form of rec in this report is compatible with the form which had the name rec in the RRRS; the other two forms correspond to named-lambda.

Examples

(car (rec s (cons 1 (delay s))))⇒ 1

(car (force (cdr (rec s (cons 1 (delay s))))))⇒ 1

(car (force (cdr (force (cdr (rec s (cons 1 (delay s))))))))⇒ 1

((rec (fact n)
   (if (<= n 1) 1
       (* n (fact (- n 1))))) 5)⇒ 120

Implementation

(define-syntax rec
  (syntax-rules ()
    ((_ (name . formals) body_0 body_1 ...)
     (letrec ((name (lambda formals
                      body_0 body_1 ...)))
       name))
    ((_ name expr)
     (letrec ((name expr))
       name))))

4.3: Assignments

4.3.1: `set!`

(set! ⟨variable⟩ ⟨expression⟩) syntax

Syntax

⟨Variable⟩ is a variable which is already bound to some value in some region enclosing the set! expression or at the top level. If ⟨variable⟩ is not bound, it is a violation of type &undefined. Implementations should report and detect this violation before evaluation begins in the same contexts in which they should detect other references to unbound variables (see 3.1).

Note: When the identifier on the left hand side of a set! expression is not a binding for a variable but for a syntax keyword, the set! expression is a macro use and its semantics are determined by the transformer associated with the syntax keyword, not by this entry.

Semantics

The ⟨expression⟩ is evaluated, and the resulting value is stored in the location to which the ⟨variable⟩ is bound. An unspecified value is returned.

Example

(let ((x 2))
  (+ x 1)
  (set! x 4)
  (+ x 1))⇒ 5

4.3.2: `set!-values`

(set!-values ⟨formals⟩ ⟨expression⟩) syntax

Syntax

⟨Formals⟩ is a formal arguments list (see lambda). It is a &undefined violation if any are not bound.

Semantics

The ⟨expression⟩ is evaluated, and the resulting values are matched to the the ⟨formals⟩ in the same way that the formals in a lambda expression are matched to the arguments in a procedure call. For each ⟨formal⟩ matched to a value ⟨value⟩, (set! ⟨formal⟩ ⟨value⟩) is expanded and evaluated in an unspecified order. The result of the set!-values expression is unspecified.

Note: The set!-values form may not bind a value to a location if one of the formals is bound to a variable transformer. See Macrological Fascicle, “Variable transformers”.

Implementation

The (if #f #f) expressions are used to force the form to return one unspecified value. The form check-unique-formals! is an auxiliary function to check that all identifiers in the list of formals are unique. See Appendix A.1 for an example implementation.

(define-syntax set!-values
  (lambda (stx)
    (syntax-case stx ()
      ((_ (id ...) expression)
       (check-unique-formals! 'set!-values stx #'(id ...))
       (with-syntax (((tmp ...) (generate-temporaries #'(id ...))))
         #'(let-values (((tmp ...) expression))
             (set! id tmp) ... (if #f #f))))
      ((_ (id ... . rest) expression)
       (check-unique-formals! 'set!-values stx #'(id ... rest))
       (with-syntax (((tmp ...) (generate-temporaries #'(id ...))))
         #'(let-values (((tmp ... . tmp-rest) expression))
             (set! id tmp) ...
             (set! rest tmp-rest)
             (if #f #f)))))))

Examples

(let ((x #f) (y #f))
  (set!-values (x . y) (values 'a 'b))
  (list x y))⇒ (a (b))

4.4: Sequences

4.4.1: `begin`

(begin ⟨definition or expression⟩ …) syntax
(begin ⟨expression₁⟩ ⟨expression₂⟩ …) syntax

When begin is invoked within a ⟨body⟩, ⟨library body⟩, or ⟨program body⟩, it has the first form, with the effect of splicing the ⟨definition or expression⟩ forms contained therein into the surrounding context, such that any definitions have effect for the whole of the corresponding body.

Define what begin does at the REPL (whether it locally causes R⁶RS top-level body semantics within itself or not). Probably in the fascicle on libraries which will define eval.

Rationale

The first form of begin is commonly used in the output of macros (see Macrological Fascicle, “The syntax-case system”) which need to generate multiple definitions and splice them into the context in which they are expanded. It is also used by macros which generate multiple expressions, some of which are side-effectual, which may be used in either a definition or an expression context.

Description

When begin is used in a context where definitions are not allowed, it has the second form, which is an ordinary expression. The ⟨expression⟩s are evaluated sequentially from left to right, and the values of the last ⟨expression⟩ are returned. The last ⟨expression⟩ is in tail context if the begin expression as a whole is in tail context. The continuations of the all expressions except the last one accept any number of values and discard them. This expression type is used to sequence side effects such as assignments or input and output.

Note: There is an additional form of begin used in define-library declarations cross-reference to bibliothecarial fascicle.

Examples

(let ()
  (define x 3)
  (begin
    (define y 4)
    (define z 5))
  (+ x y z))⇒ 12

(define x 1)
(+ (begin
     (set! x 2)
     (* x 3))
   4)⇒ 10

(+ (begin
     (define x 2)
     (* x 3))
   4)⇒ syntax violation

Perhaps allow extension which permits this?

4.5: Conditional and looping forms

4.5.1: `if`

(if ⟨test⟩ ⟨consequent⟩ ⟨alternative⟩) syntax
(if ⟨test⟩ ⟨consequent⟩) syntax

Syntax

⟨Test⟩, ⟨consequent⟩, and ⟨alternative⟩ must be expressions.

Semantics

An if expression is evaluated as follows: first, ⟨test⟩ is evaluated. If it yields a true value (see link to valued fascicle), then ⟨consequent⟩ is evaluated and its values are returned. Otherwise ⟨alternate⟩ is evaluated and its values are returned. If ⟨test⟩ yields #f and no ⟨alternate⟩ is specified, then the result of the expression is unspecified.

The ⟨consequent⟩ and ⟨alternate⟩ expressions are in tail context if the if expression itself is.

4.5.2: `and`

(and ⟨test₁⟩ …) syntax

Syntax

The ⟨test⟩s are expressions.

Semantics

If there are no ⟨test⟩s, #t is returned. Otherwise, the ⟨test⟩ expressions are evaluated from left to right until a ⟨test⟩ returns #f or the last ⟨test⟩ is reached. In the former case, the and expression returns #f without evaluating the remaining expressions. In the latter case, the last expression is evaluated and its values are returned.

The last ⟨test⟩ expression is in tail context if the and expression itself is.

Examples

(and (= 2 2) (> 2 1))⇒ #t

(and (= 2 2) (< 2 1))⇒ #f

(and 1 2 'c '(f g))⇒ (f g)

(and)⇒ #t

Implementation

(define-syntax and
  (syntax-rules ()
    ((and) #t)
    ((and test) test)
    ((and test1 test2 ...)
     (if test1 (and test2 ...) #f))))

4.5.3: `or`

(or ⟨test₁⟩ …) syntax

Syntax

The ⟨test⟩s are expressions.

Semantics

If there are no ⟨test⟩s, #f is returned. Otherwise, the ⟨test⟩ expressions are evaluated from left to right until a ⟨test⟩ returns a true value, or the last ⟨test⟩ is reached. In the former case, the or expression returns that value without evaluating the remaining expressions. In the latter case, the last expression is evaluated and its values are returned.

The last ⟨test⟩ expression is in tail context if the or expression itself is.

Examples

(or (= 2 2) (> 2 1))⇒ #t

(or (= 2 2) (< 2 1))⇒ #t

(or #f #f #f)⇒ #f

(or '(b c) (/ 3 0))⇒ (b c)

Implementation

(define-syntax or
  (syntax-rules ()
    ((or) #f)
    ((or test) test)
    ((or test1 test2 ...)
     (let ((x test1))
       (if x x (or test2 ...))))))

4.5.4: `cond`

(cond ⟨cond clause⟩ …) syntax
=> auxiliary syntax
else auxiliary syntax

Syntax

Each ⟨cond clause⟩ has one of the forms

⟨cond clause⟩: ::= (⟨test⟩); ::= (⟨test⟩ ⟨body⟩); ::= (⟨test⟩ => ⟨body⟩); ::= (⟨generator⟩ ⟨guard⟩ => ⟨body⟩)

The last ⟨cond clause⟩ may additionally have the form

⟨cond-clause⟩: ::= (else ⟨body⟩)

The ⟨test⟩, ⟨generator⟩, and ⟨guard⟩s are all expressions.

Note: The syntax of the second, third, and fourth ⟨cond clause⟩ types is not ambiguous because the auxiliary syntax keyword => is not a valid expression nor definition on its own.

Note: The clause form (⟨generator⟩ ⟨guard⟩ => ⟨expression⟩) is new in this fascicle, and is not in the small language report nor in any previous version of the Scheme report. Previous versions of the Scheme report only allowed expressions, and not definitions, in cond clauses of the second form and of the else form. The (scheme base) library must export the same binding as whatever large language library this ends up in.

Issue: In previous Scheme reports, (cond) was not a syntactically valid expression. It has been made one because it may be easier to write correct macros which expand into uses of cond when zero clauses are allowed, especially if the entire cond expression is being used only for side-effects in any case. This use of cond will always return an unspecified value. A similar change has been made to case. The Working Group is especially keen to hear feedback on this change.

Semantics

A cond expression is evaluated by checking the ⟨cond clause⟩s in order from left to right until the condition required by one of them is satisfied; then that clause is chosen to generate the result of evaluating the cond expression, which is returned. The condition required by each ⟨cond clause⟩, and how it generates the result, is determined by the syntax of each clause:

For clauses of the form ⟨test⟩, the condition for the clause is satisfied if the evaluating the ⟨test⟩ expression yields a true value. The result is the value that was returned by the evaluation of the ⟨test⟩ expression.
For clauses of the form (⟨test⟩⟨body⟩), the condition for the clause is satisfied if evaluating the ⟨test⟩ expression yields a true value. The result is generated by evaluating the ⟨body⟩. The ⟨body⟩ is in tail context if the cond expression as a whole is in tail context.
For clauses of the form (⟨test⟩ => ⟨expression⟩), the condition for the clause is satisfied if evaluating the ⟨test⟩ expression yields a true value. The result is generated by first evaluating the ⟨expression⟩. This evaluation must yield a procedure of one argument. This procedure is called with the result of the prior evaluation of the ⟨test⟩ expression to give the result for the clause. The procedure is called in tail context if the cond expression is in tail context.
For clauses of the form (⟨generator⟩ ⟨guard⟩ => ⟨expression⟩), the ⟨guard⟩ expression must evaluate to a procedure. The condition for the clause is satisfied if the result of calling this procedure with the values yielded by evaluating the ⟨generator⟩ expression is a true value. The result is generated by first evaluating the ⟨expression⟩. This evaluation must yield a procedure which takes as many arguments as there were values resulting from the prior evaluation of the ⟨generator⟩ expression. This procedure is then called with those values as arguments to give the result for the clause. The procedure is called in tail context if the cond expression is in tail context.
If the final clause is of the form (else ⟨body⟩), its condition is always satisfied. The result is generated by evaluating the ⟨body⟩. The ⟨body⟩ is in tail context if the cond expression as a whole is in tail context.

If none of the clauses have their conditions satisfied, the evaluation of the cond expression returns an unspecified value.

Implementation

(define-syntax cond
  (syntax-rules (else =>)
    ((_) (if #f #f))
    ((_ (else body_0 body_1 ...))
     (let () body_0 body_1 ...))
    ((_ (test => proc) clause ...)
     (let ((val test))
       (if val (proc val) (cond clause ...))))
    ((_ (generator guard => proc) clause ...)
     (let-values ((vals generator))
       (if (apply guard vals)
           (apply proc vals)
           (cond clause ...))))
    ((_ (test) clause ...)
     (let ((val test))
       (if val val (cond clause ...))))
    ((_ (test body_0 body_1 ...) clause ...)
     (if test (let () body_0 body_1 ...) (cond clause ...)))))

4.5.5: `when` and `unless`

(when ⟨test⟩ ⟨body⟩) syntax
(unless ⟨test⟩ ⟨body⟩) syntax

Syntax

⟨Test⟩ is an expression.

Note: Neither the R⁶RS nor the small language report allowed definitions inside of a when or unless, only expressions. R⁶RS specified that if the expressions were evaluated, the result of evaluating the when or unless expression would the result of evaluating the final expression. The small language report relaxed this to make the result of when and unless a single unspecified value in all cases, since it could not be depended on in any circumstance. However, this made the form difficult to implement such that it tail-called its body, and no implementation known to the Working Group returned precisely one unspecified value in all cases. The semantics have been changed to a compromise between the R⁶RS and R⁷RS-Small behavior, allowing for the behavior of both reports.

Semantics

A when or unless expression is evaluated by first evaluating the ⟨test⟩ expression. If ⟨test⟩ evaluates to a true value in a when expression, or a false value in an unless expression, the ⟨expression⟩s are evaluated in order from left to right. The final ⟨expression⟩ is in tail context if the when or unless form itself is in tail context. Unspecified values are returned.

Implementation

(define-syntax when
  (syntax-rules ()
    ((_ test body_0 body_1 ...)
     (if test (let () body_0 body_1 ...)))))

(define-syntax unless
  (syntax-rules ()
    ((_ test body_0 body_1 ...)
     (if (not test) (let () body_0 body_1 ...)))))

4.5.6: `case`

(case ⟨key⟩ ⟨case clause⟩ …) syntax
=> auxiliary syntax
else auxiliary syntax

Syntax

⟨Key⟩ is an expression. Each ⟨case clause⟩ has one of the forms

⟨case clause⟩: ::= ((⟨datum₁⟩ …) ⟨body⟩); ::= ((⟨datum₁⟩ …) => ⟨body⟩)

The last ⟨case clause⟩ may additionally have the one of the following forms

⟨final-case-clause⟩: ::= (else ⟨body⟩); ::= (else => ⟨expression⟩)

Note: In previous Scheme reports, (case ⟨key⟩) was not a syntactically valid expression. It has been made one because it may be easier to write correct macros which expand into uses of case when zero clauses are allowed, especially if the entire case expression is being used only for side-effects in any case. This use of case will always return an unspecified value. A similar change has been made to cond. The Working Group is especially keen to hear feedback on this change.

Semantics

A case expression is evaluated by first evaluating the ⟨key⟩ expression to produce a single value, called the key. The ⟨case clause⟩s are checked in order from left to right until one is found which contains a ⟨datum⟩ whose value as a literal is the same, in the sense of the eqv? procedure, as the key.

If the clause has the second form listed above, its ⟨expression⟩ is evaluated to produce a procedure of one argument. This procedure is called with a value which is eqv? to the key as its argument and the result of this procedure call is returned. The procedure is called in tail context if the case expression is in tail context.

If no other clause contains a suitable datum for the key and the last clause has the form (else ⟨body⟩), the ⟨body⟩ is evaluated and its result returned. The body is evaluated is in tail context if the case expression is in tail context.

If no clause contains a suitable datum for the key and there is no clause beginning with the else keyword, unspecified values are returned.

Note: Because of the use of eqv? to compare the key with the datums in case clauses, only booleans, identifiers, numbers, characters, and the empty list can sensibly be used as datums in clauses, as the semantics of eqv? for these types does not depend on their location in the store, which is unspecified for literal datums of other types.

Implementation

(define-syntax case
 (syntax-rules (else =>)
   ((case _) (if #f #f))
   ((case (key ...)
      clauses ...)
    (let ((atom-key (key ...)))
      (case atom-key clauses ...)))
   ((case key
      (else => result))
    (result key))
   ((case key
      (else result1 result2 ...))
    (let () result1 result2 ...))
   ((case key
      ((atoms ...) => result))
    (if (memv key '(atoms ...))
        (result key)))
   ((case key
      ((atoms ...) result1 result2 ...))
    (if (memv key '(atoms ...))
        (let () result1 result2 ...)))
   ((case key
      ((atoms ...) => result)
      clause clauses ...)
    (if (memv key '(atoms ...))
        (result key)
        (case key clause clauses ...)))
   ((case key
      ((atoms ...) result1 result2 ...)
      clause clauses ...)
    (if (memv key '(atoms ...))
        (let () result1 result2 ...)
        (case key clause clauses ...)))))

4.5.7: `do`

(do ((⟨variable₁⟩ ⟨init₁⟩ ⟨step₁⟩) …) (⟨test⟩ ⟨expression⟩ …) (⟨command⟩ …)) syntax

Syntax

The ⟨init⟩s, ⟨step⟩s, ⟨test⟩s, and ⟨command⟩s are expressions. The ⟨variable⟩s are distinct identifiers.

Semantics

The do expression is an iteration construct. It specifies a set of variables to be bound, how they are to be initialized at the start, and how they are to be updated on each iteration.

A do expression is evaluated as follows: The ⟨init⟩ expressions are evaluated (in some unspecified order), the ⟨variable⟩s are bound to fresh locations, the results of the ⟨init⟩ expressions are stored in the bindings of the ⟨variable⟩s, and then the iteration phase begins.

Each iteration begins by evaluating ⟨test⟩; if the result is a false value, then the ⟨command⟩s are evaluated in order for effect, the ⟨step⟩ expressions are evaluated in some unspecified order, the ⟨variable⟩s are bound to fresh locations holding the results, and the next iteration begins.

If ⟨test⟩ evaluates to a true value, the ⟨expression⟩s are evaluated from left to right and the values of the last ⟨expression⟩ are returned. The last ⟨expression⟩ is in tail context if the ⟨do⟩ expression is in tail context. If no ⟨expression⟩s are present, then the ⟨do⟩ expression returns unspecified values.

The region of the binding of a ⟨variable⟩ consists of the entire do expression except for the ⟨init⟩s.

A ⟨step⟩ may be omitted, in which case the effect is the same as if (⟨variable⟩ ⟨init⟩ ⟨variable⟩) had been written instead of (⟨variable⟩ ⟨init⟩).

If a do expression appears in a tail context, the ⟨expression⟩s are a ⟨tail sequence⟩ in the sense of xref, i.e., the last ⟨expression⟩ is also in a tail context.

Examples

(do ((vec (make-vector 5))
     (i 0 (+ i 1)))
    ((= i 5) vec)
  (vector-set! vec i i))⇒ #(0 1 2 3 4)

(let ((x '(1 3 5 7 9)))
  (do ((x x (cdr x))
       (sum 0 (+ sum (car x))))
      ((null? x) sum)))⇒ 25

Implementation

This definition of do uses a trick to expand the variable clauses.

(define-syntax do
  (syntax-rules ()
    ((_ ((var init . maybe-step) ...)
        (test expr ...)
        command ...)
     (let-syntax
         ((do-step
           (syntax-rules ()
             ((_ implicit-step) implicit-step)
             ((_ _ step) step))))
       (let loop ((var init) ...)
         (if test
             (begin
               ;; avoid an empty begin expression:
               (if #f #f)
               expr ...)
             (begin
               command ...
               (loop (do-step var . maybe-step) ...))))))))

4.6: Equivalence predicates

Note: Both this section, and the semantics of the procedures defined within it, will be extended by a future fascicle.

4.6.1: `eqv?`

(eqv? obj₁ obj₂) procedure

The eqv? procedure defines a useful equivalence relation on objects. Briefly, it returns #t if obj₁ and obj₂ should normally be regarded as the same object and #f otherwise. This relation is left slightly open to interpretation, but the following partial specification of eqv? must hold for all implementations.

If obj₁ and obj₂ are of distinct disjoint types (see valued fascicle), eqv? always returns #f. Otherwise, eqv? behaves according to the common disjoint type of obj₁ and obj₂:

Procedure: eqv? returns #t if the two procedures have the same location tag. It may also return #t if the implementation can prove that the two procedures would behave the same for all arguments, even if they have different location tags. Otherwise, it returns #f. Note that implementations are not required to make any particular effort to prove that two procedures have equivalent behavior.

Examples

(eqv? (lambda () 1)
      (lambda () 2))⇒ #f

(let ((p (lambda (x) x)))
  (eqv? p p))⇒ #t

(eqv? (lambda (x) x)
      (lambda (y) y))⇒ unspecified

4.6.2: `eq?`

(eq? obj₁ obj₂) procedure

The eq? predicate is similar to eqv? except that in some cases it is capable of discerning distinctions finer than those detectable by eqv?. It must always return #f when eqv? also would, but may return #f in some cases where eqv? would return #t.

On procedures, the eq? predicate returns #t if the procedures have the same location tag and #f otherwise.

4.6.3: `equal?`

(equal? obj₁ obj₂) procedure

The equal? predicate is a coarser equivalence predicate than eqv? or eq?. Like those procedures, it returns #f if its arguments are of distinct disjoint types. Otherwise, it returns #t if and only if the (possibly infinite) unfoldings of its arguments into regular trees are the same (in the sense of equal?) as ordered trees.

On procedures, the equal? predicate behaves the same as eqv?.

Revised7 Report on the Algorithmic Language SchemeThe Procedural Fascicle

Introduction to this fascicle

Changes to the R7RS

What Implementations Need To Do To Support These Changes

Requests for Comments

Editorial conventions

1: Introduction

Historical background

Copying

2: Basic concepts

2.1: Variables, keywords, and regions

2.2: Procedures

2.3: Expressions and definitions

2.4: Continuations and dynamic extents

2.5: Multiple return values

2.6: Bodies

Description

2.7: Storage model

2.8: Active procedure calls

Rationale

Non-tail calls

Rationale

Description

3: Basic expression types

3.1: Variables

3.1.1: Variable references

Syntax

Semantics

Unbound variables

Example

3.1.2: Procedure applications

Syntax

Semantics

4: Foundational library

4.1: Procedures

4.1.1: lambda

Syntax

Semantics

4.1.2: case-lambda

Syntax

Semantics

Example

Implementation

4.1.3: procedure?

4.1.4: apply

Requirements

Description

Examples

4.1.5: values

4.1.6: call-with-values

Requirements

Description

Examples

4.2: Variable definition and binding forms

4.2.1: define

Syntax

Semantics

Examples

4.2.2: define-values

Syntax

Semantics

Examples

Implementation

4.2.3: define-alias

Semantics

Examples

4.2.4: let

Syntax

Semantics

Examples

Implementation

4.2.5: let*

Syntax

Semantics

Example

Implementation

4.2.6: let-values

Syntax

Semantics

Examples

Revised⁷ Report on the Algorithmic Language Scheme
The Procedural Fascicle

Changes to the R⁷RS

4.1.1: `lambda`

4.1.2: `case-lambda`

4.1.3: `procedure?`

4.1.4: `apply`

4.1.5: `values`

4.1.6: `call-with-values`

4.2.1: `define`

4.2.2: `define-values`

4.2.3: `define-alias`

4.2.4: `let`

4.2.5: `let*`

4.2.6: `let-values`

4.2.7: `let*-values`

4.2.8: `letrec`

4.2.9: `letrec*`

4.2.10: `letrec-values`

4.2.11: `letrec*-values`

4.2.12: `rec`

4.3.1: `set!`

4.3.2: `set!-values`

4.4.1: `begin`

4.5.1: `if`

4.5.2: `and`

4.5.3: `or`

4.5.4: `cond`

4.5.5: `when` and `unless`

4.5.6: `case`