Scheme 编程语言（第四版）

Scheme programs are made up of keywords, variables, structured forms, constant data (numbers, characters, strings, quoted vectors, quoted lists, quoted symbols, etc.), whitespace, and comments.

Keywords, variables, and symbols are collectively called identifiers. Identifiers may be formed from letters, digits, and certain special characters, including ?, !, ., +, -, *, /, <, =, >, :, $, %, ^, &, _, ~, and @, as well as a set of additional Unicode characters. Identifiers cannot start with an at sign ( @ ) and normally cannot start with any character that can start a number, i.e., a digit, plus sign ( + ), minus sign ( - ), or decimal point ( . ). Exceptions are +, -, and ..., which are valid identifiers, and any identifier starting with ->. For example, hi, Hello, n, x, x3, x+2, and ?$&*!!! are all identifiers. Identifiers are delimited by whitespace, comments, parentheses, brackets, string (double) quotes ( " ), and hash marks( # ). A delimiter or any other Unicode character may be included anywhere within the name of an identifier as an escape of the form \xsv;, where sv is the scalar value of the character in hexadecimal notation.

There is no inherent limit on the length of a Scheme identifier; programmers may use as many characters as necessary. Long identifiers are no substitute for comments, however, and frequent use of long identifiers can make a program difficult to format and consequently difficult to read. A good rule is to use short identifiers when the scope of the identifier is small and longer identifiers when the scope is larger.

Identifiers may be written in any mix of upper- and lower-case letters, and case is significant, i.e., two identifiers are different even if they differ only in case. For example, abcde, Abcde, AbCdE, and ABCDE all refer to different identifiers. This is a change from previous versions of the Revised Report.

Structured forms and list constants are enclosed within parentheses, e.g., (a b c) or (* (- x 2) y). The empty list is written (). Matched sets of brackets ( [ ] ) may be used in place of parentheses and are often used to set off the subexpressions of certain standard syntactic forms for readability, as shown in examples throughout this book. Vectors are written similarly to lists, except that they are preceded by #( and terminated by ), e.g., #(this is a vector of symbols). Bytevectors are written as sequences of unsigned byte values (exact integers in the range 0 through 255) bracketed by #vu8( and ), e.g., #vu8(3 250 45 73).

Strings are enclosed in double quotation marks, e.g., "I am a string". Characters are preceded by #\, e.g., #\a. Case is important within character and string constants, as within identifiers. Numbers may be written as integers, e.g., -123, as ratios, e.g., 1/2, in floating-point or scientific notation, e.g., 1.3 or 1e23, or as complex numbers in rectangular or polar notation, e.g., 1.3-2.7i or -1.2@73. Case is not important in the syntax of a number. The boolean values representing true and false are written #t and #f. Scheme conditional expressions actually treat #f as false and all other objects as true, so 3, 0, (), "false", and nil all count as true.

Details of the syntax for each type of constant data are given in the individual sections of Chapter 6 and in the formal syntax of Scheme starting on page 455.

Scheme expressions may span several lines, and no explicit terminator is required. Since the number of whitespace characters (spaces and newlines) between expressions is not significant, Scheme programs should be indented to show the structure of the code in a way that makes the code as readable as possible. Comments may appear on any line of a Scheme program, between a semicolon ( ; ) and the end of the line. Comments explaining a particular Scheme expression are normally placed at the same indentation level as the expression, on the line before the expression. Comments explaining a procedure or group of procedures are normally placed before the procedures, without indentation. Multiple comment characters are often used to set off the latter kind of comment, e.g., ;;; The following procedures ....

Two other forms of comments are supported: block comments and datum comments. Block comments are delimited by #| and |# pairs, and may be nested. A datum comment consists of a #; prefix and the datum (printed data value) that follows it. Datum comments are typically used to comment out individual definitions or expressions. For example, (three #;(not four) element list) is just what it says. Datum comments may also be nested, though #;#;(a)(b) has the somewhat nonobvious effect of commenting out both (a) and (b).

Some Scheme values, such as procedures and ports, do not have standard printed representations and can thus never appear as a constant in the printed syntax of a program. This book uses the notation #<description> when showing the output of an operation that returns such a value, e.g., #<procedure> or #<port>.

Scheme’s naming conventions are designed to provide a high degree of regularity. The following is a list of these naming conventions:

Programmers should employ these same conventions in their own code whenever possible.

A standard procedure or syntactic form whose sole purpose is to perform some side effect is said to return unspecified. This means that an implementation is free to return any number of values, each of which can be any Scheme object, as the value of the procedure or syntactic form. Do not count on these values being the same across implementations, the same across versions of the same implementation, or even the same across two uses of the procedure or syntactic form. Some Scheme systems routinely use a special object to represent unspecified values. Printing of this object is often suppressed by interactive Scheme systems, so that the values of expressions returning unspecified values are not printed.

While most standard procedures return a single value, the language supports procedures that return zero, one, more than one, or even a variable number of values via the mechanisms described in Section 5.8. Some standard expressions can evaluate to multiple values if one of their subexpressions evaluates to multiple values, e.g., by calling a procedure that returns multiple values. When this situation can occur, an expression is said to return "the values" rather than simply "the value" of its subexpression. Similarly, a standard procedure that returns the values resulting from a call to a procedure argument is said to return the values returned by the procedure argument.

This book uses the words "must" and "should" to describe program requirements, such as the requirement to provide an index that is less than the length of the vector in a call to vector-ref. If the word "must" is used, it means that the requirement is enforced by the implementation, i.e., an exception is raised, usually with condition type &assertion. If the word "should" is used, an exception may or may not be raised, and if not, the behavior of the program is undefined.

The phrase "syntax violation" is used to describe a situation in which a program is malformed. Syntax violations are detected prior to program execution. When a syntax violation is detected, an exception of type &syntax is raised and the program is not executed.

The typographical conventions used in this book are straightforward. All Scheme objects are printed in a typewriter typeface, just as they are to be typed at the keyboard. This includes syntactic keywords, variables, constant objects, Scheme expressions, and example programs. An italic typeface is used to set off syntax variables in the descriptions of syntactic forms and arguments in the descriptions of procedures. Italics are also used to set off technical terms the first time they appear. In general, names of syntactic forms and procedures are never capitalized, even at the beginning of a sentence. The same is true for syntax variables written in italics.

In the description of a syntactic form or procedure, one or more prototype patterns show the syntactic form or forms or the correct number or numbers of arguments for an application of the procedure. The keyword or procedure name is given in typewriter font, as are parentheses. The remaining pieces of the syntax or arguments are shown in italics, using a name that implies the type of expression or argument expected by the syntactic form or procedure. Ellipses are used to specify zero or more occurrences of a subexpression or argument. For example, (or expr ...) describes the or syntactic form, which has zero or more subexpressions, and (member obj list) describes the member procedure, which expects two arguments, an object and a list.

A syntax violation occurs if the structure of a syntactic form does not match its prototype. Similarly, an exception with condition type &assertion is raised if the number of arguments passed to a standard procedure does not match what it is specified to receive. An exception with condition type &assertion is also raised if a standard procedure receives an argument whose type is not the type implied by its name or does not meet other criteria given in the description of the procedure. For example, the prototype for vector-set! is

and the description says that n must be an exact nonnegative integer strictly less than the length of vector. Thus, vector-set! must receive three arguments, the first of which must be a vector, the second of which must be an exact nonnegative integer less than the length of the vector, and the third of which may be any Scheme value. Otherwise, an exception with condition type &assertion is raised.

In most cases, the type of argument required is obvious, as with vector, obj, or binary-input-port. In others, primarily within the descriptions of numeric routines, abbreviations are used, such as int for integer, exint for exact integer, and fx for fixnum. These abbreviations are explained at the start of the sections containing the affected entries.

Most Scheme systems provide an interactive programming environment that simplifies program development and experimentation. The simplest interaction with Scheme follows a "read-evaluate-print" cycle. A program (often called a read-evaluate-print loop, or REPL) reads each expression you type at the keyboard, evaluates it, and prints its value.

With an interactive Scheme system, you can type an expression at the keyboard and see its value immediately. You can define a procedure and apply it to arguments to see how it works. You can even type in an entire program consisting of a set of procedure definitions and test it without leaving the system. When your program starts getting longer, it will be more convenient to type it into a file (using a text editor), load the file and test it interactively. In most Scheme systems, a file may be loaded with the nonstandard procedure load, which takes a string argument naming the file. Preparing your program in a file has several advantages: you have a chance to compose your program more carefully, you can correct errors without retyping the program, and you can retain a copy for later use. Most Scheme implementations treat expressions loaded from a file the same as expressions typed at the keyboard.

While Scheme provides various input and output procedures, the REPL takes care of reading expressions and printing their values. This frees you to concentrate on writing your program without worrying about how its results will be displayed.

The examples in this chapter and in the rest of the book follow a regular format. An expression you might type from your keyboard is given first, possibly spanning several lines. The value of the expression is given after the ⇒, to be read as "evaluates to." The ⇒ is omitted for definitions and when the value of an expression is unspecified.

The example programs are formatted in a style that "looks nice" and conveys the structure of the program. The code is easy to read because the relationship between each expression and its subexpressions is clearly shown. Scheme ignores indentation and line breaks, however, so there is no need to follow a particular style. The important thing is to establish one style and keep to it. Scheme sees each program as if it were on a single line, with its subexpressions ordered from left to right.

If you have access to an interactive Scheme system, it might be a good idea to start it up now and type in the examples as you read. One of the simplest Scheme expressions is a string constant. Try typing "Hi Mom!" (including the double quotes) in response to the prompt. The system should respond with "Hi Mom!"; the value of any constant is the constant itself.

Here is a set of expressions, each with Scheme’s response. They are explained in later sections of this chapter, but for now use them to practice interacting with Scheme.

Be careful not to miss any single quotes ( ' ), double quotes, or parentheses. If you left off a single quote in the last expression, you probably received a message indicating that an exception has occurred. Just try again. If you left off a closing parenthesis or double quote, the system might still be waiting for it.

Here are a few more expressions to try. You can try to figure out on your own what they mean or wait to find out later in the chapter.

As you can see, Scheme expressions may span more than one line. The Scheme system knows when it has an entire expression by matching double quotes and parentheses.

Next, let’s try defining a procedure.

The procedure square computes the square \(n^2\) of any number \(n\). We say more about the expressions that make up this definition later in this chapter. For now it suffices to say that define establishes variable bindings, lambda creates procedures, and * names the multiplication procedure. Note the form of these expressions. All structured forms are enclosed in parentheses and written in prefix notation, i.e., the operator precedes the arguments. As you can see, this is true even for simple arithmetic operations such as *.

Try using square.

Even though the next definition is short, you might enter it into a file. Let’s assume you call the file "reciprocal.ss."

This procedure, reciprocal, computes the quantity \(1/n\) for any number \(n \neq 0\). For \(n = 0\), reciprocal returns the string "oops!". Return to Scheme and try loading your file with the procedure load.

Finally, try using the procedure we have just defined.

In the next section we will discuss Scheme expressions in more detail. Throughout this chapter, keep in mind that your Scheme system is one of the most useful tools for learning Scheme. Whenever you try one of the examples in the text, follow it up with your own examples. In an interactive Scheme system, the cost of trying something out is relatively small---usually just the time to type it in.

The simplest Scheme expressions are constant data objects, such as strings, numbers, symbols, and lists. Scheme supports other object types, but these four are enough for many programs. We saw some examples of strings and numbers in the preceding section.

Let’s discuss numbers in a little more detail. Numbers are constants. If you enter a number, Scheme echoes it back to you. The following examples show that Scheme supports several types of numbers.

Scheme numbers include exact and inexact integer, rational, real, and complex numbers. Exact integers and rational numbers have arbitrary precision, i.e., they can be of arbitrary size. Inexact numbers are usually represented internally using IEEE standard floating-point representations.

Scheme provides the names +, -, *, and / for the corresponding arithmetic procedures. Each procedure accepts two numeric arguments. The expressions below are called procedure applications, because they specify the application of a procedure to a set of arguments.

Scheme employs prefix notation even for common arithmetic operations. Any procedure application, whether the procedure takes zero, one, two, or more arguments, is written as (procedure arg ...). This regularity simplifies the syntax of expressions; one notation is employed regardless of the operation, and there are no complicated rules regarding the precedence or associativity of operators.

Procedure applications may be nested, in which case the innermost values are computed first. We can thus nest applications of the arithmetic procedures given above to evaluate more complicated formulas.

These examples demonstrate everything you need to use Scheme as a four-function desk calculator. While we will not discuss them in this chapter, Scheme supports many other arithmetic procedures. Now might be a good time to turn to Section 6.4 and experiment with some of them.

Simple numeric objects are sufficient for many tasks, but sometimes aggregate data structures containing two or more values are needed. In many languages, the basic aggregate data structure is the array. In Scheme, it is the list. Lists are written as sequences of objects surrounded by parentheses. For instance, (1 2 3 4 5) is a list of numbers, and ("this" "is" "a" "list") is a list of strings. Lists need not contain only one type of object, so (4.2 "hi") is a valid list containing a number and a string. Lists may be nested (may contain other lists), so ((1 2) (3 4)) is a valid list with two elements, each of which is a list of two elements.

You might notice that lists look just like procedure applications and wonder how Scheme tells them apart. That is, how does Scheme distinguish between a list of objects, (obj1 obj2 ...), and a procedure application, (procedure arg ...)?

In some cases, the distinction might seem obvious. The list of numbers (1 2 3 4 5) could hardly be confused with a procedure application, since 1 is a number, not a procedure. So, the answer might be that Scheme looks at the first element of the list or procedure application and makes its decision based on whether that first element is a procedure or not. This answer is not good enough, since we might even want to treat a valid procedure application such as (+ 3 4) as a list. The answer is that we must tell Scheme explicitly to treat a list as data rather than as a procedure application. We do this with quote.

The quote forces the list to be treated as data. Try entering the above expressions without the quote; you will likely receive a message indicating that an exception has occurred for the first two and an incorrect answer (7) for the third.

Because quote is required fairly frequently in Scheme code, Scheme recognizes a single quotation mark ( ' ) preceding an expression as an abbreviation for quote.

Both forms are referred to as quote expressions. We often say an object is quoted when it is enclosed in a quote expression.

A quote expression is not a procedure application, since it inhibits the evaluation of its subexpression. It is an entirely different syntactic form. Scheme supports several other syntactic forms in addition to procedure applications and quote expressions. Each syntactic form is evaluated differently. Fortunately, the number of different syntactic forms is small. We will see more of them later in this chapter.

Not all quote expressions involve lists. Try the following expression with and without the quote wrapper.

The symbol hello must be quoted in order to prevent Scheme from treating hello as a variable. Symbols and variables in Scheme are similar to symbols and variables in mathematical expressions and equations. When we evaluate the mathematical expression \(1 - x\) for some value of \(x\), we think of \(x\) as a variable. On the other hand, when we consider the algebraic equation \(x^2 - 1 = (x - 1)(x + 1)\), we think of \(x\) as a symbol (in fact, we think of the whole equation symbolically). Just as quoting a list tells Scheme to treat a parenthesized form as a list rather than as a procedure application, quoting an identifier tells Scheme to treat the identifier as a symbol rather than as a variable. While symbols are commonly used to represent variables in symbolic representations of equations or programs, symbols may also be used, for example, as words in the representation of natural language sentences.

You might wonder why applications and variables share notations with lists and symbols. The shared notation allows Scheme programs to be represented as Scheme data, simplifying the writing of interpreters, compilers, editors, and other tools in Scheme. This is demonstrated by the Scheme interpreter given in Section 12.7, which is itself written in Scheme. Many people believe this to be one of the most important features of Scheme.

Numbers and strings may be quoted, too.

Numbers and strings are treated as constants in any case, however, so quoting them is unnecessary.

Now let’s discuss some Scheme procedures for manipulating lists. There are two basic procedures for taking lists apart: car and cdr (pronounced could-er). car returns the first element of a list, and cdr returns the remainder of the list. (The names "car" and "cdr" are derived from operations supported by the first computer on which a Lisp language was implemented, the IBM 704.) Each requires a nonempty list as its argument.

The first element of a list is often called the "car" of the list, and the rest of the list is often called the "cdr" of the list. The cdr of a list with one element is (), the empty list.

The procedure cons constructs lists. It takes two arguments. The second argument is usually a list, and in that case cons returns a list.

Just as "car" and "cdr" are often used as nouns, "cons" is often used as a verb. Creating a new list by adding an element to the beginning of a list is referred to as consing the element onto the list.

Notice the word "usually" in the description of cons's second argument. The procedure cons actually builds pairs, and there is no reason that the cdr of a pair must be a list. A list is a sequence of pairs; each pair’s cdr is the next pair in the sequence.

The cdr of the last pair in a proper list is the empty list. Otherwise, the sequence of pairs forms an improper list. More formally, the empty list is a proper list, and any pair whose cdr is a proper list is a proper list.

An improper list is printed in dotted-pair notation, with a period, or dot, preceding the final element of the list.

Because of its printed notation, a pair whose cdr is not a list is often called a dotted pair. Even pairs whose cdrs are lists can be written in dotted-pair notation, however, although the printer always chooses to write proper lists without dots.

The procedure list is similar to cons, except that it takes an arbitrary number of arguments and always builds a proper list.

Section 6.3 provides more information on lists and the Scheme procedures for manipulating them. This might be a good time to turn to that section and familiarize yourself with the other procedures given there.

Let’s turn to a discussion of how Scheme evaluates the expressions you type. We have already established the rules for constant objects such as strings and numbers: the object itself is the value. You have probably also worked out in your mind a rule for evaluating procedure applications of the form (procedure arg1 ... argn). Here, procedure is an expression representing a Scheme procedure, and arg1 ... argn are expressions representing its arguments. One possibility is the following.

For example, consider the simple procedure application (+ 3 4). The value of + is the addition procedure, the value of 3 is the number 3, and the value of 4 is the number 4. Applying the addition procedure to 3 and 4 yields 7, so our value is the object 7.

By applying this process at each level, we can find the value of the nested expression (* (+ 3 4) 2). The value of * is the multiplication procedure, the value of (+ 3 4) we can determine to be the number 7, and the value of 2 is the number 2. Multiplying 7 by 2 we get 14, so our answer is 14.

This rule works for procedure applications but not for quote expressions because the subexpressions of a procedure application are evaluated, whereas the subexpression of a quote expression is not. The evaluation of a quote expression is more similar to the evaluation of constant objects. The value of a quote expression of the form (quote object) is simply object.

Constant objects, procedure applications, and quote expressions are only three of the many syntactic forms provided by Scheme. Fortunately, only a few of the other syntactic forms need to be understood directly by a Scheme programmer; these are referred to as core syntactic forms. The remaining syntactic forms are syntactic extensions defined, ultimately, in terms of the core syntactic forms. We will discuss the remaining core syntactic forms and a few syntactic extensions in the remaining sections of this chapter. Section 3.1 summarizes the core syntactic forms and introduces the syntactic extension mechanism.

Before we go on to more syntactic forms and procedures, two points related to the evaluation of procedure applications are worthy of note. First, the process given above is overspecified, in that it requires the subexpressions to be evaluated from left to right. That is, procedure is evaluated before arg1, arg1 is evaluated before arg2, and so on. This need not be the case. A Scheme evaluator is free to evaluate the expressions in any order---left to right, right to left, or any other sequential order. In fact, the subexpressions may be evaluated in different orders for different applications, even in the same implementation.

The second point is that procedure is evaluated in the same way as arg1 ... argn. While procedure is often a variable that names a particular procedure, this need not be the case. Exercise 2.2.3 had you determine the value of the expression ((car (list + - * /)) 2 3). Here, procedure is (car (list + - * /)). The value of (car (list + - * /)) is the addition procedure, just as if procedure were simply the variable +.

Suppose expr is a Scheme expression that contains a variable var. Suppose, additionally, that we would like var to have the value val when we evaluate expr. For example, we might like x to have the value 2 when we evaluate (+ x 3). Or, we might want y to have the value 3 when we evaluate (+ 2 y). The following examples demonstrate how to do this using Scheme’s let syntactic form.

The let syntactic form includes a list of variable-expression pairs, along with a sequence of expressions referred to as the body of the let. The general form of a let expression is

We say the variables are bound to the values by the let. We refer to variables bound by let as let-bound variables.

A let expression is often used to simplify an expression that would contain two identical subexpressions. Doing so also ensures that the value of the common subexpression is computed only once.

Brackets are often used in place of parentheses to delimit the bindings of a let expression.

Scheme treats forms enclosed in brackets just like forms enclosed in parentheses. An open bracket must be matched by a close bracket, and an open parenthesis must be matched by a close parenthesis. We use brackets for let (and, as we’ll see, several other standard syntactic forms) to improve readability, especially when we might otherwise have two or more consecutive open parentheses.

Since expressions in the first position of a procedure application are evaluated no differently from other expressions, a let-bound variable may be used there as well.

The variables bound by let are visible only within the body of the let.

This is fortunate, because we would not want the value of + to be the multiplication procedure everywhere.

It is possible to nest let expressions.

When nested let expressions bind the same variable, only the binding created by the inner let is visible within its body.

The outer let expression binds x to 1 within its body, which is the second let expression. The inner let expression binds x to (+ x 1) within its body, which is the expression (+ x x). What is the value of (+ x 1)? Since (+ x 1) appears within the body of the outer let but not within the body of the inner let, the value of x must be 1 and hence the value of (+ x 1) is 2. What about (+ x x)? It appears within the body of both let expressions. Only the inner binding for x is visible, so x is 2 and (+ x x) is 4.

The inner binding for x is said to shadow the outer binding. A let-bound variable is visible everywhere within the body of its let expression except where it is shadowed. The region where a variable binding is visible is called its scope. The scope of the first x in the example above is the body of the outer let expression minus the body of the inner let expression, where it is shadowed by the second x. This form of scoping is referred to as lexical scoping, since the scope of each binding can be determined by a straightforward textual analysis of the program.

Shadowing may be avoided by choosing different names for variables. The expression above could be rewritten so that the variable bound by the inner let is new-x.

Although choosing different names can sometimes prevent confusion, shadowing can help prevent the accidental use of an "old" value. For example, with the original version of the preceding example, it would be impossible for us to mistakenly refer to the outer x within the body of the inner let.

In the expression (let ([x (* 3 4)]) (+ x x)), the variable x is bound to the value of (* 3 4). What if we would like the value of (+ x x) where x is bound to the value of (/ 99 11)? Where x is bound to the value of (- 2 7)? In each case we need a different let expression. When the body of the let is complicated, however, having to repeat it can be inconvenient.

Instead, we can use the syntactic form lambda to create a new procedure that has x as a parameter and has the same body as the let expression.

The general form of a lambda expression is

The variables var ... are the formal parameters of the procedure, and the sequence of expressions body1 body2 ... is its body. (Actually, the true general form is somewhat more general than this, as you will see later.)

A procedure is just as much an object as a number, string, symbol, or pair. It does not have any meaningful printed representation as far as Scheme is concerned, however, so this book uses the notation #<procedure> to show that the value of an expression is a procedure.

The most common operation to perform on a procedure is to apply it to one or more values.

This is no different from any other procedure application. The procedure is the value of (lambda (x) (+ x x)), and the only argument is the value of (* 3 4), or 12. The argument values, or actual parameters, are bound to the formal parameters within the body of the lambda expression in the same way as let-bound variables are bound to their values. In this case, x is bound to 12, and the value of (+ x x) is 24. Thus, the result of applying the procedure to the value 12 is 24.

Because procedures are objects, we can establish a procedure as the value of a variable and use the procedure more than once.

Here, we establish a binding for double to a procedure, then use this procedure to double three different values.

The procedure expects its actual parameter to be a number, since it passes the actual parameter on to +. In general, the actual parameter may be any sort of object. Consider, for example, a similar procedure that uses cons instead of +.

Noting the similarity between double and double-cons, you should not be surprised to learn that they may be collapsed into a single procedure by adding an additional argument.

This demonstrates that procedures may accept more than one argument and that arguments passed to a procedure may themselves be procedures.

As with let expressions, lambda expressions become somewhat more interesting when they are nested within other lambda or let expressions.

The occurrence of x within the lambda expression refers to the x outside the lambda that is bound by the outer let expression. The variable x is said to occur free in the lambda expression or to be a free variable of the lambda expression. The variable y does not occur free in the lambda expression since it is bound by the lambda expression. A variable that occurs free in a lambda expression should be bound, e.g., by an enclosing lambda or let expression, unless the variable is (like the names of primitive procedures) bound outside of the expression, as we discuss in the following section.

What happens when the procedure is applied somewhere outside the scope of the bindings for variables that occur free within the procedure, as in the following expression?

The answer is that the same bindings that were in effect when the procedure was created are in effect again when the procedure is applied. This is true even if another binding for x is visible where the procedure is applied.

In both cases, the value of x within the procedure named f is sam.

Incidentally, a let expression is nothing more than the direct application of a lambda expression to a set of argument expressions. For example, the two expressions below are equivalent.

In fact, a let expression is a syntactic extension defined in terms of lambda and procedure application, which are both core syntactic forms. In general, any expression of the form

is equivalent to the following.

See Section 3.1 for more about core forms and syntactic extensions.

As mentioned above, the general form of lambda is a bit more complicated than the form we saw earlier, in that the formal parameter specification, (var …​), need not be a proper list, or indeed even a list at all. The formal parameter specification can be in any of the following three forms:

In the first case, exactly n actual parameters must be supplied, and each variable is bound to the corresponding actual parameter. In the second, any number of actual parameters is valid; all of the actual parameters are put into a single list and the single variable is bound to this list. The third case is a hybrid of the first two cases. At least n actual parameters must be supplied. The variables var1 ... varn are bound to the corresponding actual parameters, and the variable varr is bound to a list containing the remaining actual parameters. In the second and third cases, varr is sometimes referred to as a "rest" parameter because it holds the rest of the actual parameters beyond those that are individually named.

Let’s consider a few examples to help clarify the more general syntax of lambda expressions.

In the first two examples, the procedure named f accepts any number of arguments. These arguments are automatically formed into a list to which the variable x is bound; the value of f is this list. In the first example, the arguments are 1, 2, 3, and 4, so the answer is (1 2 3 4). In the second, there are no arguments, so the answer is the empty list (). The value of the procedure named g in the third example is a list whose first element is the first argument and whose second element is a list containing the remaining arguments. The procedure named h is similar but separates out the second argument. While f accepts any number of arguments, g must receive at least one and h must receive at least two.

The variables bound by let and lambda expressions are not visible outside the bodies of these expressions. Suppose you have created an object, perhaps a procedure, that must be accessible anywhere, like + or cons. What you need is a top-level definition, which may be established with define. Top-level definitions, which are supported by most interactive Scheme systems, are visible in every expression you enter, except where shadowed by another binding.

Let’s establish a top-level definition of the double-any procedure of the last section.

The variable double-any now has the same status as cons or the name of any other primitive procedure. We can use double-any as if it were a primitive procedure.

A top-level definition may be established for any object, not just for procedures.

Most often, though, top-level definitions are used for procedures.

As suggested above, top-level definitions may be shadowed by let or lambda bindings.

Variables with top-level definitions act almost as if they were bound by a let expression enclosing all of the expressions you type.

Given only the simple tools you have read about up to this point, it is already possible to define some of the primitive procedures provided by Scheme and described later in this book. If you completed the exercises from the last section, you should already know how to define list.

Also, Scheme provides the abbreviations cadr and cddr for the compositions of car with cdr and cdr with cdr. That is, (cadr list) is equivalent to (car (cdr list)), and, similarly, (cddr list) is equivalent to (cdr (cdr list)). They are easily defined as follows.

Any definition (define var expr) where expr is a lambda expression can be written in a shorter form that suppresses the lambda. The exact syntax depends upon the format of the lambda expression’s formal parameter specifier, i.e., whether it is a proper list of variables, a single variable, or an improper list of variables. A definition of the form

may be abbreviated

while

may be abbreviated

and

may be abbreviated

For example, the definitions of cadr and list might be written as follows.

This book does not often employ this alternative syntax. Although it is shorter, it tends to mask the reality that procedures are not intimately tied to variables, or names, as they are in many other languages. This syntax is often referred to, somewhat pejoratively, as the "defun" syntax for define, after the defun form provided by Lisp languages in which procedures are more closely tied to their names.

Top-level definitions make it easier for us to experiment with a procedure interactively because we need not retype the procedure each time it is used. Let’s try defining a somewhat more complicated variation of double-any, one that turns an "ordinary" two-argument procedure into a "doubling" one-argument procedure.

doubler accepts one argument, f, which must be a procedure that accepts two arguments. The procedure returned by doubler accepts one argument, which it uses for both arguments in an application of f. We can define, with doubler, the simple double and double-cons procedures of the last section.

We can also define double-any with doubler.

Within double and double-cons, f has the appropriate value, i.e., + or cons, even though the procedures are clearly applied outside the scope of f.

What happens if you attempt to use a variable that is not bound by a let or lambda expression and that does not have a top-level definition? Try using the variable i-am-not-defined to see what happens.

Most Scheme systems print a message indicating that an unbound- or undefined-variable exception has occurred.

The system should not, however, complain about the appearance of an undefined variable within a lambda expression, until and unless the resulting procedure is applied. The following should not cause an exception, even though we have not yet established a top-level definition of proc2.

If you try to apply proc1 before defining proc2, you should get a undefined exception message. Let’s give proc2 a top-level definition and try proc1.

When you define proc1, the system accepts your promise to define proc2, and does not complain unless you use proc1 before defining proc2. This allows you to define procedures in any order you please. This is especially useful when you are trying to organize a file full of procedure definitions in a way that makes your program more readable. It is necessary when two procedures defined at top level depend upon each other; we will see some examples of this later.

So far we have considered expressions that perform a given task unconditionally. Suppose that we wish to write the procedure abs. If its argument x is negative, abs returns -x; otherwise, it returns x. The most straightforward way to write abs is to determine whether the argument is negative and if so negate it, using the if syntactic form.

An if expression has the form (if test consequent alternative), where consequent is the expression to evaluate if test is true and alternative is the expression to evaluate if test is false. In the expression above, test is (< n 0), consequent is (- 0 n), and alternative is n.

The procedure abs could be written in a variety of other ways. Any of the following are valid definitions of abs.

The first of these definitions asks if n is greater than or equal to zero, inverting the test. The second asks if n is not less than zero, using the procedure not with <. The third asks if n is greater than zero or n is equal to zero, using the syntactic form or. The fourth treats zero separately, though there is no benefit in doing so. The fifth is somewhat tricky; n is either added to or subtracted from zero, depending upon whether n is greater than or equal to zero.

Why is if a syntactic form and not a procedure? In order to answer this, let’s revisit the definition of reciprocal from the first section of this chapter.

The second argument to the division procedure should not be zero, since the result is mathematically undefined. Our definition of reciprocal avoids this problem by testing for zero before dividing. Were if a procedure, its arguments (including (/ 1 n)) would be evaluated before it had a chance to choose between the consequent and alternative. Like quote, which does not evaluate its only subexpression, if does not evaluate all of its subexpressions and so cannot be a procedure.

The syntactic form or operates in a manner similar to if. The general form of an or expression is (or expr ...). If there are no subexpressions, i.e., the expression is simply (or), the value is false. Otherwise, each expr is evaluated in turn until either (a) one of the expressions evaluates to true or (b) no more expressions are left. In case (a), the value is true; in case (b), the value is false.

To be more precise, in case (a), the value of the or expression is the value of the last subexpression evaluated. This clarification is necessary because there are many possible true values. Usually, the value of a test expression is one of the two objects #t, for true, or #f, for false.

Every Scheme object, however, is considered to be either true or false by conditional expressions and by the procedure not. Only #f is considered false; all other objects are considered true.

The and syntactic form is similar in form to or, but an and expression is true if all its subexpressions are true, and false otherwise. In the case where there are no subexpressions, i.e., the expression is simply (and), the value is true. Otherwise, the subexpressions are evaluated in turn until either no more subexpressions are left or the value of a subexpression is false. The value of the and expression is the value of the last subexpression evaluated.

Using and, we can define a slightly different version of reciprocal.

In this version, the value is #f if n is zero and 1/n otherwise.

The procedures =, <, >, <=, and >= are called predicates. A predicate is a procedure that answers a specific question about its arguments and returns one of the two values #t or #f. The names of most predicates end with a question mark ( ? ); the common numeric procedures listed above are exceptions to this rule. Not all predicates require numeric arguments, of course. The predicate null? returns true if its argument is the empty list () and false otherwise.

The procedure cdr must not be passed anything other than a pair, and an exception is raised when this happens. Common Lisp, however, defines (cdr '()) to be (). The following procedure, lisp-cdr, is defined using null? to return () if its argument is ().

Another useful predicate is eqv?, which requires two arguments. If the two arguments are equivalent, eqv? returns true. Otherwise, eqv? returns false.

As you can see, eqv? returns true if the arguments are the same symbol, boolean, number, pair, or string. Two pairs are not the same by eqv? if they are created by different calls to cons, even if they have the same contents. Detailed equivalence rules for eqv? are given in Section 6.2.

Scheme also provides a set of type predicates that return true or false depending on the type of the object, e.g., pair?, symbol?, number?, and string?. The predicate pair?, for example, returns true only if its argument is a pair.

Type predicates are useful for deciding if the argument passed to a procedure is of the appropriate type. For example, the following version of reciprocal checks first to see that its argument is a number before testing against zero or performing the division.

By the way, the code that uses reciprocal must check to see that the returned value is a number and not a string. To relieve the caller of this obligation, it is usually preferable to report the error, using assertion-violation, as follows.

The first argument to assertion-violation is a symbol identifying where the message originates, the second is a string describing the error, and the third and subsequent arguments are "irritants" to be included with the error message.

Let’s look at one more conditional expression, cond, that is often useful in place of if. cond is similar to if except that it allows multiple test and alternative expressions. Consider the following definition of sign, which returns -1 for negative inputs, +1 for positive inputs, and 0 for zero.

The two if expressions may be replaced by a single cond expression as follows.

A cond expression usually takes the form

though the else clause may be omitted. This should be done only when there is no possibility that all the tests will fail, as in the new version of sign below.

These definitions of sign do not depend on the order in which the tests are performed, since only one of the tests can be true for any value of n. The following procedure computes the tax on a given amount of income in a progressive tax system with breakpoints at 10,000, 20,000, and 30,000 dollars.

In this example, the order in which the tests are performed, left to right (top to bottom), is significant.

We have seen how we can control whether or not expressions are evaluated with if, and, or, and cond. We can also perform an expression more than once by creating a procedure containing the expression and invoking the procedure more than once. What if we need to perform some expression repeatedly, say for all the elements of a list or all the numbers from one to ten? We can do so via recursion. Recursion is a simple concept: the application of a procedure from within that procedure. It can be tricky to master recursion at first, but once mastered it provides expressive power far beyond ordinary looping constructs.

A recursive procedure is a procedure that applies itself. Perhaps the simplest recursive procedure is the following, which we will call goodbye.

This procedure takes no arguments and simply applies itself immediately. There is no value after the ⇒ because goodbye never returns.

Obviously, to make practical use out of a recursive procedure, we must have some way to terminate the recursion. Most recursive procedures should have at least two basic elements, a base case and a recursion step. The base case terminates the recursion, giving the value of the procedure for some base argument. The recursion step gives the value in terms of the value of the procedure applied to a different argument. In order for the recursion to terminate, the different argument must be closer to the base argument in some way.

Let’s consider the problem of finding the length of a proper list recursively. We need a base case and a recursion step. The logical base argument for recursion on lists is nearly always the empty list. The length of the empty list is zero, so the base case should give the value zero for the empty list. In order to become closer to the empty list, the natural recursion step involves the cdr of the argument. A nonempty list is one element longer than its cdr, so the recursion step gives the value as one more than the length of the cdr of the list.

The if expression asks if the list is empty. If so, the value is zero. This is the base case. If not, the value is one more than the length of the cdr of the list. This is the recursion step.

Many Scheme implementations allow you to trace the execution of a procedure to see how it operates. In Chez Scheme, for example, one way to trace a procedure is to type (trace name), where name is the name of a procedure you have defined at top level. If you trace length as defined above and pass it the argument '(a b c d), you should see something like this:

The indentation shows the nesting level of the recursion; the vertical lines associate applications visually with their values. Notice that on each application of length the list gets smaller until it finally reaches (). The value at () is 0, and each outer level adds 1 to arrive at the final value.

Let’s write a procedure, list-copy, that returns a copy of its argument, which must be a list. That is, list-copy returns a new list consisting of the elements (but not the pairs) of the old list. Making a copy might be useful if either the original list or the copy might be altered via set-car! or set-cdr!, which we discuss later.

See if you can define list-copy before studying the definition below.

The definition of list-copy is similar to the definition of length. The test in the base case is the same, (null? ls). The value in the base case is (), however, not 0, because we are building up a list, not a number. The recursive call is the same, but instead of adding one, list-copy conses the car of the list onto the value of the recursive call.

There is no reason why there cannot be more than one base case. The procedure memv takes two arguments, an object and a list. It returns the first sublist, or tail, of the list whose car is equal to the object, or #f if the object is not found in the list. The value of memv may be used as a list or as a truth value in a conditional expression.

Here there are two conditions to check, hence the use of cond. The first cond clause checks for the base value of (); no object is a member of (), so the answer is #f. The second clause asks if the car of the list is the object, in which case the list is returned, being the first tail whose car contains the object. The recursion step just continues down the list.

There may also be more than one recursion case. Like memv, the procedure remv defined below takes two arguments, an object and a list. It returns a new list with all occurrences of the object removed from the list.

This definition is similar to the definition of memv above, except remv does not quit once it finds the element in the car of the list. Rather, it continues, simply ignoring the element. If the element is not found in the car of the list, remv does the same thing as list-copy above: it conses the car of the list onto the recursive value.

Up to now, the recursion has been only on the cdr of a list. It is sometimes useful, however, for a procedure to recur on the car as well as the cdr of the list. The procedure tree-copy defined below treats the structure of pairs as a tree rather than as a list, with the left subtree being the car of the pair and the right subtree being the cdr of the pair. It performs a similar operation to list-copy, building new pairs while leaving the elements (leaves) alone.

The natural base argument for a tree structure is anything that is not a pair, since the recursion traverses pairs rather than lists. The recursive step in this case is doubly recursive, finding the value recursively for the car as well as the cdr of the argument.

At this point, readers who are familiar with other languages that provide special iteration constructs, e.g., while or for loops, might wonder whether similar constructs are required in Scheme. Such constructs are unnecessary; iteration in Scheme is expressed more clearly and succinctly via recursion. Recursion is more general and eliminates the need for the variable assignments required by many other languages' iteration constructs, resulting in code that is more reliable and easier to follow. Some recursion is essentially iteration and executes as such; Section 3.2 has more to say about this. Often, there is no need to make a distinction, however. Concentrate instead on writing clear, concise, and correct programs.

Before we leave the topic of recursion, let’s consider a special form of repetition called mapping. Consider the following procedure, abs-all, that takes a list of numbers as input and returns a list of their absolute values.

This procedure forms a new list from the input list by applying the procedure abs to each element. We say that abs-all maps abs over the input list to produce the output list. Mapping a procedure over a list is a fairly common thing to do, so Scheme provides the procedure map, which maps its first argument, a procedure, over its second, a list. We can use map to define abs-all.

We really do not need abs-all, however, since the corresponding direct application of map is just as short and perhaps clearer.

Of course, we can use lambda to create the procedure argument to map, e.g., to square the elements of a list of numbers.

We can map a multiple-argument procedure over multiple lists, as in the following example.

The lists must be of the same length, and the procedure should accept as many arguments as there are lists. Each element of the output list is the result of applying the procedure to corresponding members of the input list.

Looking at the first definition of abs-all above, you should be able to derive, before studying it, the following definition of map1, a restricted version of map that maps a one-argument procedure over a single list.

All we have done is to replace the call to abs in abs-all with a call to the new parameter p. A definition of the more general map is given in Section 5.4.

Although many programs can be written without them, assignments to top-level variables or let-bound and lambda-bound variables are sometimes useful. Assignments do not create new bindings, as with let or lambda, but rather change the values of existing bindings. Assignments are performed with set!.

Many languages require the use of assignments to initialize local variables, separate from the declaration or binding of the variables. In Scheme, all local variables are given a value immediately upon binding. Besides making the separate assignment to initialize local variables unnecessary, it ensures that the programmer cannot forget to initialize them, a common source of errors in most languages.

In fact, most of the assignments that are either necessary or convenient in other languages are both unnecessary and inconvenient in Scheme, since there is typically a clearer way to express the same algorithm without assignments. One common practice in some languages is to sequence expression evaluation with a series of assignments, as in the following procedure that finds the roots of a quadratic equation.

The roots are computed according to the well-known quadratic formula,

which yields the solutions to the equation \(0 = ax^2 + bx + c\). The let expression in this definition is employed solely to establish the variable bindings, corresponding to the declarations required in other languages. The first three assignment expressions compute subpieces of the formula, namely \(-b\), \(\sqrt{b^2 - 4ac}\), and \(2a\). The last two assignment expressions compute the two roots in terms of the subpieces. A pair of the two roots is the value of quadratic-formula. For example, the two roots of \(2x^2 - 4x - 6\) are \(x = 3\) and \(x = -1\).

The definition above works, but it can be written more clearly without the assignments, as shown below.

In this version, the set! expressions are gone, and we are left with essentially the same algorithm. By employing two let expressions, however, the definition makes clear the dependency of root1 and root2 on the values of minusb, radical, and divisor. Equally important, the let expressions make clear the lack of dependencies among minusb, radical, and divisor and between root1 and root2.

Assignments do have some uses in Scheme, otherwise the language would not support them. Consider the following version of cons that counts the number of times it is called, storing the count in a variable named cons-count. It uses set! to increment the count; there is no way to achieve the same behavior without assignments.

Assignments are commonly used to implement procedures that must maintain some internal state. For example, suppose we would like to define a procedure that returns 0 the first time it is called, 1 the second time, 2 the third time, and so on indefinitely. We could write something similar to the definition of cons-count above:

This solution is somewhat undesirable in that the variable next is visible at top level even though it need not be. Since it is visible at top level, any code in the system can change its value, perhaps inadvertently affecting the behavior of count in a subtle way. We can solve this problem by let-binding next outside of the lambda expression:

The latter solution also generalizes easily to provide multiple counters, each with its own local counter. The procedure make-counter, defined below, returns a new counting procedure each time it is called.

Since next is bound inside of make-counter but outside of the procedure returned by make-counter, each procedure it returns maintains its own unique counter.

If a state variable must be shared by more than one procedure defined at top level, but we do not want the state variable to be visible at top level, we can use let to bind the variable and set! to make the procedures visible at top level.

Variables must be defined before they can be assigned, so we define shhh and tell to be #f initially. (Any initial value would do.) We’ll see this structure again in Section 3.5 and a better way to structure code like this as a library in Section 3.6.

Local state is sometimes useful for caching computed values or allowing a computation to be evaluated lazily, i.e., only once and only on demand. The procedure lazy below accepts a thunk, or zero-argument procedure, as an argument. Thunks are often used to "freeze" computations that must be delayed for some reason, which is exactly what we need to do in this situation. When passed a thunk t, lazy returns a new thunk that, when invoked, returns the value of invoking t. Once computed, the value is saved in a local variable so that the computation need not be performed again. A boolean flag is used to record whether t has been invoked and its value saved.

The syntactic form begin, used here for the first time, evaluates its subexpressions in sequence from left to right and returns the value of the last subexpression, like the body of a let or lambda expression. We also see that the alternative subexpression of an if expression can be omitted. This should be done only when the value of the if is discarded, as it is in this case.

Lazy evaluation is especially useful for values that require considerable time to compute. By delaying the evaluation, we might avoid computing the value altogether, and by saving the value, we avoid computing it more than once.

The operation of lazy can best be illustrated by printing a message from within a thunk passed to lazy.

The first time p is invoked, the message Ouch! is printed and the string "got me" is returned. Thereafter, "got me" is returned but the message is not printed. The procedures display and newline are the first examples of explicit input/output we have seen; display prints the string without quotation marks, and newline prints a newline character.

To further illustrate the use of set!, let’s consider the implementation of stack objects whose internal workings are not visible on the outside. A stack object accepts one of four messages: empty?, which returns #t if the stack is empty; push!, which adds an object to the top of the stack; top, which returns the object on the top of the stack; and pop!, which removes the object on top of the stack. The procedure make-stack given below creates a new stack each time it is called in a manner similar to make-counter.

Each stack is stored as a list bound to the variable ls; set! is used to change this binding for push! and pop!. Notice that the argument list of the inner lambda expression uses the improper list syntax to bind args to a list of all arguments but the first. This is useful here because in the case of empty?, top, and pop! there is only one argument (the message), but in the case of push! there are two (the message and the object to push onto the stack).

As with the counters created by make-counter, the state maintained by each stack object is directly accessible only within the object. Each reference or change to this state is made explicitly by the object itself. One important benefit is that we can change the internal structure of the stack, perhaps to use a vector (see Section 6.9) instead of a list to hold the elements, without changing its external behavior. Because the behavior of the object is known abstractly (not operationally), it is known as an abstract object. See Section 12.8 for more about creating abstract objects.

In addition to changing the values of variables, we can also change the values of the car and cdr fields of a pair, using the procedures set-car! and set-cdr!.

We can use these operators to define a queue data type, which is like a stack except that new elements are added at one end and extracted from the other. The following queue implementation uses a tconc structure. A tconc consists of a nonempty list and a header. The header is a pair whose car points to the first pair (head) of the list and whose cdr points to the last pair (end) of the list.

The last element of the list is a placeholder and not considered part of the queue.

Four operations on queues are defined below: make-queue, which constructs a queue; putq!, which adds an element to the end of a queue; getq, which retrieves the element at the front of a queue; and delq!, which removes the element at the front of a queue.

All are simple operations except for putq!, which modifies the end pair to contain the new value and adds a new end pair.

As we saw in Section 2.5, the let syntactic form is merely a syntactic extension defined in terms of a lambda expression and a procedure application, both core syntactic forms. At this point, you might be wondering which syntactic forms are core forms and which are syntactic extensions, and how new syntactic extensions may be defined. This section provides some answers to these questions.

In truth, it is not necessary for us to draw a distinction between core forms and syntactic extensions, since once defined, a syntactic extension has exactly the same status as a core form. Drawing a distinction, however, makes understanding the language easier, since it allows us to focus attention on the core forms and to understand all others in terms of them.

It is necessary for a Scheme implementation to distinguish between core forms and syntactic extensions. A Scheme implementation expands syntactic extensions into core forms as the first step of compilation or interpretation, allowing the rest of the compiler or interpreter to focus only on the core forms. The set of core forms remaining after expansion to be handled directly by the compiler or interpreter is implementation-dependent, however, and may be different from the set of forms described as core here.

The exact set of syntactic forms making up the core of the language is thus subject to debate, although it must be possible to derive all other forms from any set of forms declared to be core forms. The set described here is among the simplest for which this constraint is satisfied.

The core syntactic forms include top-level define forms, constants, variables, procedure applications, quote expressions, lambda expressions, if expressions, and set! expressions. The grammar below describes the core syntax of Scheme in terms of these definitions and expressions. In the grammar, vertical bars ( | ) separate alternatives, and a form followed by an asterisk ( * ) represents zero or more occurrences of the form. <variable> is any Scheme identifier. <datum> is any Scheme object, such as a number, list, symbol, or vector. <boolean> is either #t or #f, <number> is any number, <character> is any character, and <string> is any string. We have already seen examples of numbers, strings, lists, symbols, and booleans. See Chapter 6 or the formal syntax description starting on page 455 for more on the object-level syntax of these and other objects.

The grammar is ambiguous in that the syntax for procedure applications conflicts with the syntaxes for quote, lambda, if, and set! expressions. In order to qualify as a procedure application, the first <expression> must not be one of these keywords, unless the keyword has been redefined or locally bound.

The "defun" syntax for define given in Section 2.6 is not included in the core, since definitions in that form are straightforwardly translated into the simpler define syntax. Similarly, the core syntax for if does not permit the alternative to be omitted, as did one example in Section 2.9. An if expression lacking an alternative can be translated into the core syntax for if merely by replacing the missing subexpression with an arbitrary constant, such as #f.

A begin that contains only definitions is considered to be a definition in the grammar; this is permitted in order to allow syntactic extensions to expand into more than one definition. begin expressions, i.e., begin forms containing expressions, are not considered core forms. A begin expression of the form

is equivalent to the lambda application

and hence need not be considered core.

Now that we have established a set of core syntactic forms, let’s turn to a discussion of syntactic extensions. Syntactic extensions are so called because they extend the syntax of Scheme beyond the core syntax. All syntactic extensions in a Scheme program must ultimately be derived from the core forms. One syntactic extension, however, may be defined in terms of another syntactic extension, as long as the latter is in some sense "closer" to the core syntax. Syntactic forms may appear anywhere an expression or definition is expected, as long as the extended form expands into a definition or expression as appropriate.

Syntactic extensions are defined with define-syntax. define-syntax is similar to define, except that define-syntax associates a syntactic transformation procedure, or transformer, with a keyword (such as let), rather than associating a value with a variable. Here is how we might define let with define-syntax.

The identifier appearing after define-syntax is the name, or keyword, of the syntactic extension being defined, in this case let. The syntax-rules form is an expression that evaluates to a transformer. The item following syntax-rules is a list of auxiliary keywords and is nearly always (). An example of an auxiliary keyword is the else of cond. (Other examples requiring the use of auxiliary keywords are given in Chapter 8.) Following the list of auxiliary keywords is a sequence of one or more rules, or pattern/template pairs. Only one rule appears in our definition of let. The pattern part of a rule specifies the form that the input must take, and the template specifies to what the input should be transformed.

The pattern should always be a structured expression whose first element is an underscore ( _ ). (As we will see in Chapter 8, the use of _ is only a convention, but it is a good one to follow.) If more than one rule is present, the appropriate one is chosen by matching the patterns, in order, against the input during expansion. It is a syntax violation if none of the patterns match the input.

Identifiers other than an underscore or ellipsis appearing within a pattern are pattern variables, unless they are listed as auxiliary keywords. Pattern variables match any substructure and are bound to that substructure within the corresponding template. The notation pat ... in the pattern allows for zero or more expressions matching the ellipsis prototype pat in the input. Similarly, the notation expr ... in the template produces zero or more expressions from the ellipsis prototype expr in the output. The number of pats in the input determines the number of exprs in the output; in order for this to work, any ellipsis prototype in the template must contain at least one pattern variable from an ellipsis prototype in the pattern.

The single rule in our definition of let should be fairly self-explanatory, but a few points are worth mentioning. First, the syntax of let requires that the body contain at least one form; hence, we have specified b1 b2 ... instead of b ..., which might seem more natural. On the other hand, let does not require that there be at least one variable/value pair, so we were able to use, simply, (x e) .... Second, the pattern variables x and e, though together within the same prototype in the pattern, are separated in the template; any sort of rearrangement or recombination is possible. Finally, the three pattern variables x, e, and b2 that appear in ellipsis prototypes in the pattern also appear in ellipsis prototypes in the template. This is not a coincidence; it is a requirement. In general, if a pattern variable appears within an ellipsis prototype in the pattern, it cannot appear outside an ellipsis prototype in the template.

The definition of and below is somewhat more complex than the one for let.

This definition is recursive and involves more than one rule. Recall that (and) evaluates to #t; the first rule takes care of this case. The second and third rules specify the base case and recursion steps of the recursion and together translate and expressions with two or more subexpressions into nested if expressions. For example, (and a b c) expands first into

then

and finally

With this expansion, if a and b evaluate to a true value, then the value is the value of c, otherwise #f, as desired.

The version of and below is simpler but, unfortunately, incorrect.

The expression

should return the value of (/ 1 x) when x is not zero. With the incorrect version of and, the expression expands as follows.

The final answer if x is not zero is #t, not the value of (/ 1 x).

The definition of or below is similar to the one for and except that a temporary variable must be introduced for each intermediate value so that we can both test the value and return it if it is a true value. (A temporary variable is not needed for and since there is only one false value, #f.)

Like variables bound by lambda or let, identifiers introduced by a template are lexically scoped, i.e., visible only within expressions introduced by the template. Thus, even if one of the expressions e2 e3 ... contains a reference to t, the introduced binding for t does not "capture" those references. This is typically accomplished via automatic renaming of introduced identifiers.

As with the simpler version of and given above, the simpler version of or below is incorrect.

The reason is more subtle, however, and is the subject of Exercise 3.2.6.

In Section 2.8, we saw how to define recursive procedures using top-level definitions. Before that, we saw how to create local bindings for procedures using let. It is natural to wonder whether a let-bound procedure can be recursive. The answer is no, at least not in a straightforward way. If you try to evaluate the expression

it will probably raise an exception with a message to the effect that sum is undefined. This is because the variable sum is visible only within the body of the let expression and not within the lambda expression whose value is bound to sum. We can get around this problem by passing the procedure sum to itself as follows.

This works and is a clever solution, but there is an easier way, using letrec. Like let, the letrec syntactic form includes a set of variable-value pairs, along with a sequence of expressions referred to as the body of the letrec.

Unlike let, the variables var ... are visible not only within the body of the letrec but also within expr .... Thus, we can rewrite the expression above as follows.

Using letrec, we can also define mutually recursive procedures, such as the procedures even? and odd? that were the subject of Exercise 2.8.6.

In a letrec expression, expr ... are most often lambda expressions, though this need not be the case. One restriction on the expressions must be obeyed, however. It must be possible to evaluate each expr without evaluating any of the variables var .... This restriction is always satisfied if the expressions are all lambda expressions, since even though the variables may appear within the lambda expressions, they cannot be evaluated until the resulting procedures are invoked in the body of the letrec. The following letrec expression obeys this restriction.

while the following does not.

In this case, an exception is raised indicating that x is not defined where it is referenced.

We can use letrec to hide the definitions of "help" procedures so that they do not clutter the top-level namespace. This is demonstrated by the definition of list? below, which follows the "hare and tortoise" algorithm outlined in Exercise 2.9.8.

When a recursive procedure is called in only one place outside the procedure, as in the example above, it is often clearer to use a named let expression. Named let expressions take the following form.

Named let is similar to unnamed let in that it binds the variables var ... to the values of expr ... within the body body1 body2 .... As with unnamed let, the variables are visible only within the body and not within expr .... In addition, the variable name is bound within the body to a procedure that may be called to recur; the arguments to the procedure become the new values for the variables var ....

The definition of list? has been rewritten below to use named let.

Just as let can be expressed as a simple direct application of a lambda expression to arguments, named let can be expressed as the application of a recursive procedure to arguments. A named let of the form

can be rewritten in terms of letrec as follows.

Alternatively, it can be rewritten as

provided that the variable name does not appear free within expr ....

As we discussed in Section 2.8, some recursion is essentially iteration and executes as such. When a procedure call is in tail position (see below) with respect to a lambda expression, it is considered to be a tail call, and Scheme systems must treat it properly, as a "goto" or jump. When a procedure tail-calls itself or calls itself indirectly through a series of tail calls, the result is tail recursion. Because tail calls are treated as jumps, tail recursion can be used for indefinite iteration in place of the more restrictive iteration constructs provided by other programming languages, without fear of overflowing any sort of recursion stack.

A call is in tail position with respect to a lambda expression if its value is returned directly from the lambda expression, i.e., if nothing is left to do after the call but to return from the lambda expression. For example, a call is in tail position if it is the last expression in the body of a lambda expression, the consequent or alternative part of an if expression in tail position, the last subexpression of an and or or expression in tail position, the last expression in the body of a let or letrec in tail position, etc. Each of the calls to f in the expressions below are tail calls, but the calls to g are not.

In each case, the values of the calls to f are returned directly, whereas the calls to g are not.

Recursion in general and named let in particular provide a natural way to implement many algorithms, whether iterative, recursive, or partly iterative and partly recursive; the programmer is not burdened with two distinct mechanisms.

The following two definitions of factorial use named let expressions to compute the factorial, \(n!\), of a nonnegative integer \(n\). The first employs the recursive definition \(n! = n × (n - 1)!\), where \(0!\) is defined to be 1.

The second is an iterative version that employs the iterative definition \(n! = n × (n - 1) × (n - 2) × ... × 1\), using an accumulator, a, to hold the intermediate products.

A similar problem is to compute the nth Fibonacci number for a given n. The Fibonacci numbers are an infinite sequence of integers, 0, 1, 1, 2, 3, 5, 8, etc., in which each number is the sum of the two preceding numbers in the sequence. A procedure to compute the nth Fibonacci number is most naturally defined recursively as follows.

This solution requires the computation of the two preceding Fibonacci numbers at each step and hence is doubly recursive. For example, to compute (fibonacci 4) requires the computation of both (fib 3) and (fib 2), to compute (fib 3) requires computing both (fib 2) and (fib 1), and to compute (fib 2) requires computing both (fib 1) and (fib 0). This is very inefficient, and it becomes more inefficient as n grows. A more efficient solution is to adapt the accumulator solution of the factorial example above to use two accumulators, a1 for the current Fibonacci number and a2 for the preceding one.

Here, zero is treated as a special case, since there is no preceding value. This allows us to use the single base case (= i 1). The time it takes to compute thennth Fibonacci number using this iterative solution grows linearly with n, which makes a significant difference when compared to the doubly recursive version. To get a feel for the difference, try computing (fibonacci 35) and (fibonacci 40) using both definitions to see how long each takes.

We can also get a feel for the difference by looking at a trace for each on small inputs. The first trace below shows the calls to fib in the non-tail-recursive version of fibonacci, with input 5.

Notice how there are several calls to fib with arguments 2, 1, and 0. The second trace shows the calls to fib in the tail-recursive version, again with input 5.

Clearly, there is quite a difference.

The named let examples shown so far are either tail-recursive or not tail-recursive. It often happens that one recursive call within the same expression is tail-recursive while another is not. The definition of factor below computes the prime factors of its nonnegative integer argument. The first call to f is not tail-recursive, but the second one is.

A trace of the calls to f, produced in Chez Scheme by replacing let with trace-let, in the evaluation of (factor 120) below highlights the difference between the nontail calls and the tail calls.

A nontail call to f is shown indented relative to its caller, since the caller is still active, whereas tail calls appear at the same level of indentation.

During the evaluation of a Scheme expression, the implementation must keep track of two things: (1) what to evaluate and (2) what to do with the value. Consider the evaluation of (null? x) within the expression below.

The implementation must first evaluate (null? x) and, based on its value, evaluate either (quote ()) or (cdr x). "What to evaluate" is (null? x), and "what to do with the value" is to make the decision which of (quote ()) and (cdr x) to evaluate and to do so. We call "what to do with the value" the continuation of a computation.

Thus, at any point during the evaluation of any expression, there is a continuation ready to complete, or at least continue, the computation from that point. Let’s assume that x has the value (a b c). We can isolate six continuations during the evaluation of (if (null? x) (quote ()) (cdr x)), the continuations waiting for

The continuation of (cdr x) is not listed because it is the same as the one waiting for (if (null? x) (quote ()) (cdr x)).

Scheme allows the continuation of any expression to be captured with the procedure call/cc. call/cc must be passed a procedure p of one argument. call/cc constructs a concrete representation of the current continuation and passes it to p. The continuation itself is represented by a procedure k. Each time k is applied to a value, it returns the value to the continuation of the call/cc application. This value becomes, in essence, the value of the application of call/cc.

If p returns without invoking k, the value returned by the procedure becomes the value of the application of call/cc.

Consider the simple examples below.

In the first example, the continuation is captured and bound to k, but k is never used, so the value is simply the product of 5 and 4. In the second, the continuation is invoked before the multiplication, so the value is the value passed to the continuation, 4. In the third, the continuation includes the addition by 2; thus, the value is the value passed to the continuation, 4, plus 2.

Here is a less trivial example, showing the use of call/cc to provide a nonlocal exit from a recursion.

The nonlocal exit allows product to return immediately, without performing the pending multiplications, when a zero value is detected.

Each of the continuation invocations above returns to the continuation while control remains within the procedure passed to call/cc. The following example uses the continuation after this procedure has already returned.

The continuation captured by this invocation of call/cc may be described as "Take the value, bind it to x, and apply the value of x to the value of (lambda (ignore) "hi")." Since (lambda (k) k) returns its argument, x is bound to the continuation itself; this continuation is applied to the procedure resulting from the evaluation of (lambda (ignore) "hi"). This has the effect of binding x (again!) to this procedure and applying the procedure to itself. The procedure ignores its argument and returns "hi".

The following variation of the example above is probably the most confusing Scheme program of its size; it might be easy to guess what it returns, but it takes some thought to figure out why.

The value of the call/cc is its own continuation, as in the preceding example. This is applied to the identity procedure (lambda (x) x), so the call/cc returns a second time with this value. Then, the identity procedure is applied to itself, yielding the identity procedure. This is finally applied to "HEY!", yielding "HEY!".

Continuations used in this manner are not always so puzzling. Consider the following definition of factorial that saves the continuation at the base of the recursion before returning 1, by assigning the top-level variable retry.

With this definition, factorial works as we expect factorial to work, except it has the side effect of assigning retry.

The continuation bound to retry might be described as "Multiply the value by 1, then multiply this result by 2, then multiply this result by 3, then multiply this result by 4." If we pass the continuation a different value, i.e., not 1, we will cause the base value to be something other than 1 and hence change the end result.

This mechanism could be the basis for a breakpoint package implemented with call/cc; each time a breakpoint is encountered, the continuation of the breakpoint is saved so that the computation may be restarted from the breakpoint (more than once, if desired).

Continuations may be used to implement various forms of multitasking. The simple "light-weight process" mechanism defined below allows multiple computations to be interleaved. Since it is nonpreemptive, it requires that each process voluntarily "pause" from time to time in order to allow the others to run.

The following light-weight processes cooperate to print an infinite sequence of lines containing "hey!".

See Section 12.11 for an implementation of engines, which support preemptive multitasking, with call/cc.

As we discussed in the preceding section, a continuation waits for the value of each expression. In particular, a continuation is associated with each procedure call. When one procedure invokes another via a nontail call, the called procedure receives an implicit continuation that is responsible for completing what is left of the calling procedure’s body plus returning to the calling procedure’s continuation. If the call is a tail call, the called procedure simply receives the continuation of the calling procedure.

We can make the continuations explicit by encapsulating "what to do" in an explicit procedural argument passed along on each call. For example, the continuation of the call to f in

conses the symbol b onto the value returned to it, then returns the result of this cons to the continuation of the call to g. This continuation is the same as the continuation of the call to h, which conses the symbol d onto the value returned to it. We can rewrite this in continuation-passing style, or CPS, by replacing these implicit continuations with explicit procedures.

Like the implicit continuation of h and g in the preceding example, the explicit continuation passed to h and on to g,

conses the symbol d onto the value passed to it. Similarly, the continuation passed to f,

conses b onto the value passed to it, then passes this on to the continuation of g.

Expressions written in CPS are more complicated, of course, but this style of programming has some useful applications. CPS allows a procedure to pass more than one result to its continuation, because the procedure that implements the continuation can take any number of arguments.

(This can be done with multiple values as well; see Section 5.8.) CPS also allows a procedure to take separate "success" and "failure" continuations, which may accept different numbers of arguments. An example is integer-divide below, which passes the quotient and remainder of its first two arguments to its third, unless the second argument (the divisor) is zero, in which case it passes an error message to its fourth argument.

The procedure quotient, employed by integer-divide, returns the quotient of its two arguments, truncated toward zero.

Explicit success and failure continuations can sometimes help to avoid the extra communication necessary to separate successful execution of a procedure from unsuccessful execution. Furthermore, it is possible to have multiple success or failure continuations for different flavors of success or failure, each possibly taking different numbers and types of arguments. See Sections 12.10 and 12.11 for extended examples that employ continuation-passing style.

At this point you might be wondering about the relationship between CPS and the continuations captured via call/cc. It turns out that any program that uses call/cc can be rewritten in CPS without call/cc, but a total rewrite of the program (sometimes including even system-defined primitives) might be necessary. Try to convert the product example on page 75 into CPS before looking at the version below.

In Section 2.6, we discussed top-level definitions. Definitions may also appear at the front of a lambda, let, or letrec body, in which case the bindings they create are local to the body.

Procedures bound by internal definitions can be mutually recursive, as with letrec. For example, we can rewrite the even? and odd? example from Section 3.2 using internal definitions as follows.

Similarly, we can replace the use of letrec to bind race with an internal definition of race in our first definition of list?.

In fact, internal variable definitions and letrec are practically interchangeable. The only difference, other than the obvious difference in syntax, is that variable definitions are guaranteed to be evaluated from left to right, while the bindings of a letrec may be evaluated in any order. So we cannot quite replace a lambda, let, or letrec body containing internal definitions with a letrec expression. We can, however, use letrec*, which, like let*, guarantees left-to-right evaluation order. A body of the form

is equivalent to a letrec* expression binding the defined variables to the associated values in a body comprising the expressions.

Conversely, a letrec* of the form

can be replaced with a let expression containing internal definitions and the expressions from the body as follows.

The seeming lack of symmetry between these transformations is due to the fact that letrec* expressions can appear anywhere an expression is valid, whereas internal definitions can appear only at the front of a body. Thus, in replacing a letrec* with internal definitions, we must generally introduce a let expression to hold the definitions.

Another difference between internal definitions and letrec or letrec* is that syntax definitions may appear among the internal definitions, while letrec and letrec* bind only variables.

The scope of a syntactic extension established by an internal syntax definition, as with an internal variable definition, is limited to the body in which the syntax definition appears.

Internal definitions may be used in conjunction with top-level definitions and assignments to help modularize programs. Each module of a program should make visible only those bindings that are needed by other modules, while hiding other bindings that would otherwise clutter the top-level namespace and possibly result in unintended use or redefinition of those bindings. A common way of structuring a module is shown below.

The first set of definitions establish top-level bindings for the variables we desire to export (make visible globally). The second set of definitions establish local bindings visible only within the module. The expressions init-expr ... perform any initialization that must occur after the local bindings have been established. Finally, the set! expressions assign the exported variables to the appropriate values.

An advantage of this form of modularization is that the bracketing let expression may be removed or "commented out" during program development, making the internal definitions top-level to facilitate interactive testing. This form of modularization also has several disadvantages, as we discuss in the next section.

The following module exports a single variable, calc, which is bound to a procedure that implements a simple four-function calculator.

This example uses a case expression to determine which operator to apply. case is similar to cond except that the test is always the same: (memv val (key ...)), where val is the value of the first case subform and (key ...) is the list of items at the front of each case clause. The case expression in the example above could be rewritten using cond as follows.

At the end of the preceding section, we discussed a form of modularization that involves assigning a set of top-level variables from within a let while keeping unpublished helpers local to the let. This form of modularization has several drawbacks:

An alternative that does not share these drawbacks is to create a library. A library exports a set of identifiers, each defined within the library or imported from some other library. An exported identifier need not be bound as a variable; it may be bound as a keyword instead.

The following library exports two identifiers: the variable gpa->grade and the keyword gpa. The variable gpa->grade is bound to a procedure that takes a grade-point average (GPA), represented as a number, and returns the corresponding letter grade, based on a four-point scale. The keyword gpa names a syntactic extension whose subforms must all be letter grades and whose value is the GPA computed from those letter grades.

The name of the library is (grades). This may seem like a funny kind of name, but all library names are parenthesized. The library imports from the standard (rnrs) library, which contains most of the primitive and keyword bindings we have used in this chapter and the last, and everything we need to implement gpa->grade and gpa.

Along with gpa->grade and gpa, several other syntactic extensions and procedures are defined within the library, but none of the others are exported. The ones that aren’t exported are simply helpers for the ones that are. Everything used within the library should be familiar, except for the apply procedure, which is described on page 107.

If your Scheme implementation supports import in the interactive top level, you can test the two exports as shown below.

Chapter 10 describes libraries in more detail and provides additional examples of their use.

Any identifier appearing as an expression in a program is a variable if a visible variable binding for the identifier exists, e.g., the identifier appears within the scope of a binding created by define, lambda, let, or some other variable-binding construct.

It is a syntax violation for an identifier reference to appear within a library form or top-level program if it is not bound as a variable, keyword, record name, or other entity. Since the scope of the definitions in a library, top-level program, lambda, or other local body is the entire body, it is not necessary for the definition of a variable to appear before its first reference appears, as long as the reference is not actually evaluated until the definition has been completed. So, for example, the reference to g within the definition of f below

is okay, but the reference to g in the definition of q below is not.

The lambda syntactic form is used to create procedures. Any operation that creates a procedure or establishes local variable bindings is ultimately defined in terms of lambda or case-lambda.

The variables in formals are the formal parameters of the procedure, and the sequence of subforms body1 body2 ... is its body.

The body may begin with a sequence of definitions, in which case the bindings created by the definitions are local to the body. If definitions are present, the keyword bindings are used and discarded while expanding the body, and the body is expanded into a letrec* expression formed from the variable definitions and the remaining expressions, as described on page 292. The remainder of this description of lambda assumes that this transformation has taken place, if necessary, so that the body is a sequence of expressions without definitions.

When the procedure is created, the bindings of all variables occurring free within the body, excluding the formal parameters, are retained with the procedure. Subsequently, whenever the procedure is applied to a sequence of actual parameters, the formal parameters are bound to the actual parameters, the retained bindings are restored, and the body is evaluated.

Upon application, the formal parameters defined by formals are bound to the actual parameters as follows.

When the body is evaluated, the expressions in the body are evaluated in sequence, and the procedure returns the values of the last expression.

Procedures do not have a printed representation in the usual sense. Scheme systems print procedures in different ways; this book uses the notation #<procedure>.

A Scheme lambda expression always produces a procedure with a fixed number of arguments or with an indefinite number of arguments greater than or equal to a certain number. In particular,

accepts exactly n arguments,

accepts zero or more arguments, and

accepts n or more arguments.

lambda cannot directly produce, however, a procedure that accepts, say, either two or three arguments. In particular, procedures that accept optional arguments are not supported directly by lambda. The latter form of lambda shown above can be used, in conjunction with length checks and compositions of car and cdr, to implement procedures with optional arguments, though at the cost of clarity and efficiency.

The case-lambda syntactic form directly supports procedures with optional arguments as well as procedures with fixed or indefinite numbers of arguments. case-lambda is based on the lambda* syntactic form introduced in the article "A New Approach to Procedures with Variable Arity" [11].

A case-lambda expression consists of a set of clauses, each resembling a lambda expression. Each clause has the form below.

The formal parameters of a clause are defined by formals in the same manner as for a lambda expression. The number of arguments accepted by the procedure value of a case-lambda expression is determined by the numbers of arguments accepted by the individual clauses.

When a procedure created with case-lambda is invoked, the clauses are considered in order. The first clause that accepts the given number of actual parameters is selected, the formal parameters defined by its formals are bound to the corresponding actual parameters, and the body is evaluated as described for lambda above. If formals in a clause is a proper list of identifiers, then the clause accepts exactly as many actual parameters as there are formal parameters (identifiers) in formals. As with a lambda formals, a case-lambda clause formals may be a single identifier, in which case the clause accepts any number of arguments, or an improper list of identifiers terminated by an identifier, in which case the clause accepts any number of arguments greater than or equal to the number of formal parameters excluding the terminating identifier. If no clause accepts the number of actual parameters supplied, an exception with condition type &assertion is raised.

The following definition for make-list uses case-lambda to support an optional fill parameter.

The substring procedure may be extended with case-lambda to accept either no end index, in which case it defaults to the end of the string, or no start and end indices, in which case substring is equivalent to string-copy:

It is also possible to default the start index rather than the end index when only one index is supplied:

It is even possible to require that both or neither of the start and end indices be supplied, simply by leaving out the middle clause:

let establishes local variable bindings. Each variable var is bound to the value of the corresponding expression expr. The body of the let, in which the variables are bound, is the sequence of subforms body1 body2 ... and is processed and evaluated like a lambda body.

The forms let, let*, letrec, and letrec* (the others are described after let) are similar but serve slightly different purposes. With let, in contrast with let*, letrec, and letrec*, the expressions expr ... are all outside the scope of the variables var .... Also, in contrast with let* and letrec*, no ordering is implied for the evaluation of the expressions expr .... They may be evaluated from left to right, from right to left, or in any other order at the discretion of the implementation. Use let whenever the values are independent of the variables and the order of evaluation is unimportant.

The following definition of let shows the typical derivation of let from lambda.

Another form of let, named let, is described in Section 5.4, and a definition of the full let can be found on page 312.

let* is similar to let except that the expressions expr ... are evaluated in sequence from left to right, and each of these expressions is within the scope of the variables to the left. Use let* when there is a linear dependency among the values or when the order of evaluation is important.

Any let* expression may be converted to a set of nested let expressions. The following definition of let* demonstrates the typical transformation.

letrec is similar to let and let*, except that all of the expressions expr ... are within the scope of all of the variables var .... letrec allows the definition of mutually recursive procedures.

The order of evaluation of the expressions expr ... is unspecified, so a program must not evaluate a reference to any of the variables bound by the letrec expression before all of the values have been computed. (Occurrence of a variable within a lambda expression does not count as a reference, unless the resulting procedure is applied before all of the values have been computed.) If this restriction is violated, an exception with condition type &assertion is raised.

An expr should not return more than once. That is, it should not return both normally and via the invocation of a continuation obtained during its evaluation, and it should not return twice via two invocations of such a continuation. Implementations are not required to detect a violation of this restriction, but if they do, an exception with condition type &assertion is raised.

Choose letrec over let or let* when there is a circular dependency among the variables and their values and when the order of evaluation is unimportant. Choose letrec* over letrec when there is a circular dependency and the bindings need to be evaluated from left to right.

A letrec expression of the form

may be expressed in terms of let and set! as

where temp ... are fresh variables, i.e., ones that do not already appear in the letrec expression, one for each (var expr) pair. The outer let expression establishes the variable bindings. The initial value given each variable is unimportant, so any value suffices in place of #f. The bindings are established first so that expr ... may contain occurrences of the variables, i.e., so that the expressions are computed within the scope of the variables. The middle let evaluates the values and binds them to the temporary variables, and the set! expressions assign each variable to the corresponding value. The inner let is present in case the body contains internal definitions.

A definition of letrec that uses this transformation is shown on page 310.

This transformation does not enforce the restriction that the expr expressions must not evaluate any references of or assignments to the variables. More elaborate transformations that enforce this restriction and actually produce more efficient code are possible [31].

letrec* is similar to letrec, except that letrec* evaluates expr ... in sequence from left to right. While programs must still not evaluate a reference to any var before the corresponding expr has been evaluated, references to var may be evaluated any time thereafter, including during the evaluation of the expr of any subsequent binding.

A letrec* expression of the form

may be expressed in terms of let and set! as

The outer let expression creates the bindings, each assignment evaluates an expression and immediately sets the corresponding variable to its value, in sequence, and the inner let evaluates the body. let is used in the latter case rather than begin since the body may include internal definitions as well as expressions.

let-values is a convenient way to receive multiple values and bind them to variables. It is structured like let but permits an arbitrary formals list (like lambda) on each left-hand side. let*-values is similar but performs the bindings in left-to-right order, as with let*. An exception with condition type &assertion is raised if the number of values returned by an expr is not appropriate for the corresponding formals, as described in the entry for lambda above. A definition of let-values is given on page 310.

In the first form, define creates a new binding of var to the value of expr. The expr should not return more than once. That is, it should not return both normally and via the invocation of a continuation obtained during its evaluation, and it should not return twice via two invocations of such a continuation. Implementations are not required to detect a violation of this restriction, but if they do, an exception with condition type &assertion is raised.

The second form is equivalent to (define var unspecified), where unspecified is some unspecified value. The remaining are shorthand forms for binding variables to procedures; they are identical to the following definition in terms of lambda.

where formals is (var1 ...), varr, or (var1 var2 ... . varr) for the third, fourth, and fifth define formats.

Definitions may appear at the front of a library body, anywhere among the forms of a top-level-program body, and at the front of a lambda or case-lambda body or the body of any form derived from lambda, e.g., let, or letrec*. Any body that begins with a sequence of definitions is transformed during macro expansion into a letrec* expression as described on page 292.

Syntax definitions may appear along with variable definitions wherever variable definitions may appear; see Chapter 8.

A set of definitions may be grouped by enclosing them in a begin form. Definitions grouped in this manner may appear wherever ordinary variable and syntax definitions may appear. They are treated as if written separately, i.e., without the enclosing begin form. This feature allows syntactic extensions to expand into groups of definitions.

Many implementations support an interactive "top level" in which variable and other definitions may be entered interactively or loaded from files. The behavior of these top-level definitions is outside the scope of the Revised⁶ Report, but as long as top-level variables are defined before any references or assignments to them are evaluated, the behavior is consistent across most implementations. So, for example, the reference to g in the top-level definition of f below is okay if g is not already defined, and g is assumed to name a variable to be defined at some later point.

If this is then followed by a definition of g before f is evaluated, the assumption that g would be defined as a variable is proven correct, and a call to f works as expected.

If g were defined instead as the keyword for a syntactic extension, the assumption that g would be bound as a variable is proven false, and if f is not redefined before it is invoked, the implementation is likely to raise an exception.

set! does not establish a new binding for var but rather alters the value of an existing binding. It first evaluates expr, then assigns var to the value of expr. Any subsequent reference to var within the scope of the altered binding evaluates to the new value.

Assignments are not employed as frequently in Scheme as in most other languages, but they are useful for implementing state changes.

Assignments are also useful for caching values. The example below uses a technique called memoization, in which a procedure records the values associated with old input values so it need not recompute them, to implement a fast version of the otherwise exponential doubly recursive definition of the Fibonacci function (see page 69).

Procedure application is the most basic Scheme control structure. Any structured form without a syntax keyword in the first position is a procedure application. The expressions expr0 and expr1 ... are evaluated; each should evaluate to a single value. After each of these expressions has been evaluated, the value of expr0 is applied to the values of expr1 .... If expr0 does not evaluate to a procedure, or if the procedure does not accept the number of arguments provided, an exception with condition type &assertion is raised.

The order in which the procedure and argument expressions are evaluated is unspecified. It may be left to right, right to left, or any other order. The evaluation is guaranteed to be sequential, however: whatever order is chosen, each expression is fully evaluated before evaluation of the next is started.

apply invokes procedure, passing the first obj as the first argument, the second obj as the second argument, and so on for each object in obj ..., and passing the elements of list in order as the remaining arguments. Thus, procedure is called with as many arguments as there are objs plus elements of list.

apply is useful when some or all of the arguments to be passed to a procedure are in a list, since it frees the programmer from explicitly destructuring the list.

The expressions expr1 expr2 ... are evaluated in sequence from left to right. begin is used to sequence assignments, input/output, or other operations that cause side effects.

A begin form may contain zero or more definitions in place of the expressions expr1 expr2 ..., in which case it is considered to be a definition and may appear only where definitions are valid.

This form of begin is primarily used by syntactic extensions that must expand into multiple definitions. (See page 101.)

The bodies of many syntactic forms, including lambda, case-lambda, let, let*, letrec, and letrec*, as well as the result clauses of cond, case, and do, are treated as if they were inside an implicit begin; i.e., the expressions making up the body or result clause are executed in sequence, with the values of the last expression being returned.

The test, consequent, and alternative subforms must be expressions. If test evaluates to a true value (anything other than #f), consequent is evaluated and its values are returned. Otherwise, alternative is evaluated and its values are returned. With the second, "one-armed," form, which has no alternative, the result is unspecified if test evaluates to false.

not is equivalent to (lambda (x) (if x #f #t)).

If no subexpressions are present, the and form evaluates to #t. Otherwise, and evaluates each subexpression in sequence from left to right until only one subexpression remains or a subexpression returns #f. If one subexpression remains, it is evaluated and its values are returned. If a subexpression returns #f, and returns #f without evaluating the remaining subexpressions. A syntax definition of and appears on page 62.

If no subexpressions are present, the or form evaluates to #f. Otherwise, or evaluates each subexpression in sequence from left to right until only one subexpression remains or a subexpression returns a value other than #f. If one subexpression remains, it is evaluated and its values are returned. If a subexpression returns a value other than #f, or returns that value without evaluating the remaining subexpressions. A syntax definition of or appears on page 63.

Each clause but the last must take one of the forms below.

The last clause may be in any of the above forms, or it may be an "else clause" of the form

Each test is evaluated in order until one evaluates to a true value or until all of the tests have been evaluated. If the first clause whose test evaluates to a true value is in the first form given above, the value of test is returned.

If the first clause whose test evaluates to a true value is in the second form given above, the expressions expr1 expr2 ... are evaluated in sequence and the values of the last expression are returned.

If the first clause whose test evaluates to a true value is in the third form given above, the expression expr is evaluated. The value should be a procedure of one argument, which is applied to the value of test. The values of this application are returned.

If none of the tests evaluates to a true value and an else clause is present, the expressions expr1 expr2 ... of the else clause are evaluated in sequence and the values of the last expression are returned.

If none of the tests evaluates to a true value and no else clause is present, the value or values are unspecified.

See page 305 for a syntax definition of cond.

These identifiers are auxiliary keywords for cond. Both also serve as auxiliary keywords for guard, and else also serves as an auxiliary keyword for case. It is a syntax violation to reference these identifiers except in contexts where they are recognized as auxiliary keywords.

For when, if test-expr evaluates to a true value, the expressions expr1 expr2 ... are evaluated in sequence, and the values of the last expression are returned. If test-expr evaluates to false, none of the other expressions are evaluated, and the value or values of when are unspecified.

For unless, if test-expr evaluates to false, the expressions expr1 expr2 ... are evaluated in sequence, and the values of the last expression are returned. If test-expr evaluates to a true value, none of the other expressions are evaluated, and the value or values of unless are unspecified.

A when or unless expression is usually clearer than the corresponding "one-armed" if expression.

when may be defined as follows:

unless may be defined as follows:

or in terms of when as follows:

Each clause but the last must take the form

where each key is a datum distinct from the other keys. The last clause may be in the above form or it may be an else clause of the form

expr0 is evaluated and the result is compared (using eqv?) against the keys of each clause in order. If a clause containing a matching key is found, the expressions expr1 expr2 ... are evaluated in sequence and the values of the last expression are returned.

If none of the clauses contains a matching key and an else clause is present, the expressions expr1 expr2 ... of the else clause are evaluated in sequence and the values of the last expression are returned.

If none of the clauses contains a matching key and no else clause is present, the value or values are unspecified.

See page 306 for a syntax definition of case.

This form of let, called named let, is a general-purpose iteration and recursion construct. It is similar to the more common form of let (see Section 4.4) in the binding of the variables var ... to the values of expr ... within the body body1 body2 ..., which is processed and evaluated like a lambda body. In addition, the variable name is bound within the body to a procedure that may be called to recur or iterate; the arguments to the procedure become the new values of the variables var ....

A named let expression of the form

can be rewritten with letrec as follows.

A syntax definition of let that implements this transformation and handles unnamed let as well can be found on page 312.

The procedure divisors defined below uses named let to compute the nontrivial divisors of a nonnegative integer.

The version above is non-tail-recursive when a divisor is found and tail-recursive when a divisor is not found. The version below is fully tail-recursive. It builds up the list in reverse order, but this is easy to remedy, if desired, by reversing the list on exit.

do allows a common restricted form of iteration to be expressed succinctly. The variables var ... are bound initially to the values of init ... and are rebound on each subsequent iteration to the values of update .... The expressions test, update ..., expr ..., and result ... are all within the scope of the bindings established for var ....

On each step, the test expression test is evaluated. If the value of test is true, iteration ceases, the expressions result ... are evaluated in sequence, and the values of the last expression are returned. If no result expressions are present, the value or values of the do expression are unspecified.

If the value of test is false, the expressions expr ... are evaluated in sequence, the expressions update ... are evaluated, new bindings for var ... to the values of update ... are created, and iteration continues.

The expressions expr ... are evaluated only for effect and are often omitted entirely. Any update expression may be omitted, in which case the effect is the same as if the update were simply the corresponding var.

Although looping constructs in most languages require that the loop iterands be updated via assignment, do requires the loop iterands var ... to be updated via rebinding. In fact, no side effects are involved in the evaluation of a do expression unless they are performed explicitly by its subexpressions.

See page 313 for a syntax definition of do.

The definitions of factorial and fibonacci below are straightforward translations of the tail-recursive named-let versions given in Section 3.2.

The definition of divisors below is similar to the tail-recursive definition of divisors given with the description of named let above.

The definition of scale-vector! below, which scales each element of a vector v by a constant k, demonstrates a nonempty do body.

When a program must recur or iterate over the elements of a list, a mapping or folding operator is often more convenient. These operators abstract away from null checks and explicit recursion by applying a procedure to the elements of the list one by one. A few mapping operators are also available for vectors and strings.

map applies procedure to corresponding elements of the lists list1 list2 ... and returns a list of the resulting values. The lists list1 list2 ... must be of the same length. procedure should accept as many arguments as there are lists, should return a single value, and should not mutate the list arguments.

While the order in which the applications themselves occur is not specified, the order of the values in the output list is the same as that of the corresponding values in the input lists.

map might be defined as follows.

No error checking is done by this version of map; f is assumed to be a procedure and the other arguments are assumed to be proper lists of the same length. An interesting feature of this definition is that map uses itself to pull out the cars and cdrs of the list of input lists; this works because of the special treatment of the single-list case.

for-each is similar to map except that for-each does not create and return a list of the resulting values, and for-each guarantees to perform the applications in sequence over the elements from left to right. procedure should accept as many arguments as there are lists and should not mutate the list arguments. for-each may be defined without error checks as follows.

The lists list1 list2 ... must be of the same length. procedure should accept as many arguments as there are lists and should not mutate the list arguments. If the lists are empty, exists returns #f. Otherwise, exists applies procedure to corresponding elements of the lists list1 list2 ... in sequence until either the lists each have only one element or procedure returns a true value t. In the former case, exists tail-calls procedure, applying it to the remaining element of each list. In the latter case, exists returns t.

exists may be defined (somewhat inefficiently and without error checks) as follows:

The lists list1 list2 ... must be of the same length. procedure should accept as many arguments as there are lists and should not mutate the list arguments. If the lists are empty, for-all returns #t. Otherwise, for-all applies procedure to corresponding elements of the lists list1 list2 ... in sequence until either the lists each have only one element left or procedure returns #f. In the former case, for-all tail-calls procedure, applying it to the remaining element of each list. In the latter case, for-all returns #f.

for-all may be defined (somewhat inefficiently and without error checks) as follows:

The list arguments should all have the same length. procedure should accept one more argument than the number of list arguments and return a single value. It should not mutate the list arguments.

fold-left returns obj if the list arguments are empty. If they are not empty, fold-left applies procedure to obj and the cars of list1 list2 ..., then recurs with the value returned by procedure in place of obj and the cdr of each list in place of the list.

The list arguments should all have the same length. procedure should accept one more argument than the number of list arguments and return a single value. It should not mutate the list arguments.

fold-right returns obj if the list arguments are empty. If they are not empty, fold-right recurs with the cdr of each list replacing the list, then applies procedure to the cars of list1 list2 ... and the result returned by the recursion.

vector-map applies procedure to corresponding elements of vector1 vector2 ... and returns a vector of the resulting values. The vectors vector1 vector2 ... must be of the same length, and procedure should accept as many arguments as there are vectors and return a single value.

While the order in which the applications themselves occur is not specified, the order of the values in the output vector is the same as that of the corresponding values in the input vectors.

vector-for-each is similar to vector-map except that vector-for-each does not create and return a vector of the resulting values, and vector-for-each guarantees to perform the applications in sequence over the elements from left to right.

string-for-each is similar to for-each and vector-for-each except that the inputs are strings rather than lists or vectors.

Continuations in Scheme are procedures that represent the remainder of a computation from a given point in the computation. They may be obtained with call-with-current-continuation, which can be abbreviated to call/cc.

These procedures are the same. The shorter name is often used for the obvious reason that it requires fewer keystrokes to type.

call/cc obtains its continuation and passes it to procedure, which should accept one argument. The continuation itself is represented by a procedure. Each time this procedure is applied to zero or more values, it returns the values to the continuation of the call/cc application. That is, when the continuation procedure is called, it returns its arguments as the values of the application of call/cc.

If procedure returns normally when passed the continuation procedure, the values returned by call/cc are the values returned by procedure.

Continuations allow the implementation of nonlocal exits, backtracking ([14],[29]), coroutines [16], and multitasking ([10],[32]).

The example below illustrates the use of a continuation to perform a nonlocal exit from a loop.

Additional examples are given in Sections 3.3 and 12.11.

The current continuation is typically represented internally as a stack of procedure activation records, and obtaining the continuation involves encapsulating the stack within a procedural object. Since an encapsulated stack has indefinite extent, some mechanism must be used to preserve the stack contents indefinitely. This can be done with surprising ease and efficiency and with no impact on programs that do not use continuations [17].

dynamic-wind offers "protection" from continuation invocation. It is useful for performing tasks that must be performed whenever control enters or leaves body, either normally or by continuation application.

The three arguments in, body, and out must be procedures and should accept zero arguments, i.e., they should be thunks. Before applying body, and each time body is entered subsequently by the application of a continuation created within body, the in thunk is applied. Upon normal exit from body and each time body is exited by the application of a continuation created outside body, the out thunk is applied.

Thus, it is guaranteed that in is invoked at least once. In addition, if body ever returns, out is invoked at least once.

The following example demonstrates the use of dynamic-wind to be sure that an input port is closed after processing, regardless of whether the processing completes normally.

Common Lisp provides a similar facility (unwind-protect) for protection from nonlocal exits. This is often sufficient. unwind-protect provides only the equivalent to out, however, since Common Lisp does not support fully general continuations. Here is how unwind-protect might be specified with dynamic-wind.

Some Scheme implementations support a controlled form of assignment known as fluid binding, in which a variable takes on a temporary value during a given computation and reverts to the old value after the computation has completed. The syntactic form fluid-let defined below in terms of dynamic-wind permits the fluid binding of a single variable x to the value of an expression e within a the body b1 b2 ....

Implementations that support fluid-let typically extend it to allow an indefinite number of (x e) pairs, as with let.

If no continuations are invoked within the body of a fluid-let, the behavior is the same as if the variable were simply assigned the new value on entry and assigned the old value on return.

A fluid-bound variable also reverts to the old value if a continuation created outside of the fluid-let is invoked.

If control has left a fluid-let body, either normally or by the invocation of a continuation, and control reenters the body by the invocation of a continuation, the temporary value of the fluid-bound variable is reinstated. Furthermore, any changes to the temporary value are maintained and reflected upon reentry.

A library showing how dynamic-wind might be implemented were it not already built in is given below. In addition to defining dynamic-wind, the code defines a version of call/cc that does its part to support dynamic-wind.

Together, dynamic-wind and call/cc manage a list of winders. A winder is a pair of in and out thunks established by a call to dynamic-wind. Whenever dynamic-wind is invoked, the in thunk is invoked, a new winder containing the in and out thunks is placed on the winders list, the body thunk is invoked, the winder is removed from the winders list, and the out thunk is invoked. This ordering ensures that the winder is on the winders list only when control has passed through in and not yet entered out. Whenever a continuation is obtained, the winders list is saved, and whenever the continuation is invoked, the saved winders list is reinstated. During reinstatement, the out thunk of each winder on the current winders list that is not also on the saved winders list is invoked, followed by the in thunk of each winder on the saved winders list that is not also on the current winders list. The winders list is updated incrementally, again to ensure that a winder is on the current winders list only if control has passed through its in thunk and not entered its out thunk.

The test (not (eq? save winders)) performed in call/cc is not strictly necessary but makes invoking a continuation less costly whenever the saved winders list is the same as the current winders list.

The syntactic form delay and the procedure force may be used in combination to implement lazy evaluation. An expression subject to lazy evaluation is not evaluated until its value is required and, once evaluated, is never reevaluated.

The first time a promise created by delay is forced (with force), it evaluates expr, "remembering" the resulting value. Thereafter, each time the promise is forced, it returns the remembered value instead of reevaluating expr.

delay and force are typically used only in the absence of side effects, e.g., assignments, so that the order of evaluation is unimportant.

The benefit of using delay and force is that some amount of computation might be avoided altogether if it is delayed until absolutely required. Delayed evaluation may be used to construct conceptually infinite lists, or streams. The example below shows how a stream abstraction may be built with delay and force. A stream is a promise that, when forced, returns a pair whose cdr is a stream.

delay may be defined by

where make-promise might be defined as follows.

With this definition of delay, force simply invokes the promise to force evaluation or to retrieve the saved value.

The second test of the variable set? in make-promise is necessary in the event that, as a result of applying p, the promise is recursively forced. Since a promise must always return the same value, the result of the first application of p to complete is returned.

Whether delay and force handle multiple return values is unspecified; the implementation given above does not, but the following version does, with the help of call-with-values and apply.

Neither implementation is quite right, since force must raise an exception with condition type &assertion if its argument is not a promise. Since distinguishing procedures created by make-promise from other procedures is impossible, force cannot do so reliably. The following reimplementation of make-promise and force represents promises as records of the type promise to allow force to make the required check.

While all Scheme primitives and most user-defined procedures return exactly one value, some programming problems are best solved by returning zero values, more than one value, or even a variable number of values. For example, a procedure that partitions a list of values into two sublists needs to return two values. While it is possible for the producer of multiple values to package them into a data structure and for the consumer to extract them, it is often cleaner to use the built-in multiple-values interface. This interface consists of two procedures: values and call-with-values. The former produces multiple values and the latter links procedures that produce multiple-value values with procedures that consume them.

The procedure values accepts any number of arguments and simply passes (returns) the arguments to its continuation.

producer and consumer must be procedures. call-with-values applies consumer to the values returned by invoking producer without arguments.

In the second example, values itself serves as the producer. It receives no arguments and thus returns no values. list is thus applied to no arguments and so returns the empty list.

The procedure dxdy defined below computes the change in x and y coordinates for a pair of points whose coordinates are represented by (x . y) pairs.

dxdy can be used to compute the length and slope of a segment represented by two endpoints.

We can of course combine these to form one procedure that returns two values.

The example below employs multiple values to divide a list nondestructively into two sublists of alternating elements.

At each level of recursion, the procedure split returns two values: a list of the odd-numbered elements from the argument list and a list of the even-numbered elements.

The continuation of a call to values need not be one established by a call to call-with-values, nor must only values be used to return to a continuation established by call-with-values. In particular, (values e) and e are equivalent expressions. For example:

Similarly, values may be used to pass any number of values to a continuation that ignores the values, as in the following.

Because a continuation may accept zero or more than one value, continuations obtained via call/cc may accept zero or more than one argument.

The behavior is unspecified when a continuation expecting exactly one value receives zero values or more than one value. For example, the behavior of each of the following expressions is unspecified. Some implementations raise an exception, while others silently suppress additional values or supply defaults for missing values.

Programs that wish to force extra values to be ignored in particular contexts can do so easily by calling call-with-values explicitly. A syntactic form, which we might call first, can be defined to abstract the discarding of more than one value when only one is desired.

Since implementations are required to raise an exception with condition type &assertion if a procedure does not accept the number of arguments passed to it, each of the following raises an exception.

Since producer is most often a lambda expression, it is often convenient to use a syntactic extension that suppresses the lambda expression in the interest of readability.

If the consumer is also a lambda expression, the multiple-value variants of let and let* described in Section 4.5 are usually even more convenient.

Many standard syntactic forms and procedures pass along multiple values. Most of these are "automatic," in the sense that nothing special must be done by the implementation to make this happen. The usual expansion of let into a direct lambda call automatically propagates multiple values produced by the body of the let. Other operators must be coded specially to pass along multiple values. The call-with-port procedure (Section 7.6), for example, calls its procedure argument, then closes the port argument before returning the procedure’s values, so it must save the values temporarily. This is easily accomplished via let-values, apply, and values:

If this seems like too much overhead when a single value is returned, the code can use call-with-values and case-lambda to handle the single-value case more efficiently:

The definitions of values and call-with-values (and concomitant redefinition of call/cc) in the library below demonstrate that the multiple-return-values interface could be implemented in Scheme if it were not already built in. No error checking can be done, however, for the case in which more than one value is returned to a single-value context, such as the test part of an if expression.

Multiple values can be implemented more efficiently [2], but this code serves to illustrate the meanings of the operators and may be used to provide multiple values in older, nonstandard implementations that do not support them.

Scheme’s eval procedure allows programmers to write programs that construct and evaluate other programs. This ability to do run-time meta programming should not be overused but is handy when needed.

If obj does not represent a syntactically valid expression, eval raises an exception with condition type &syntax. The environments returned by environment, scheme-report-environment, and null-environment are immutable. Thus, eval also raises an exception with condition type &syntax if an assignment to any of the variables in the environment appears within the expression.

environment returns an environment formed from the combined bindings of the given import specifiers. Each import-spec must be an s-expression representing a valid import specifier (see Chapter 10).

version must be the exact integer 5.

null-environment returns an environment containing bindings for the keywords whose meanings are defined by the Revised⁵ Report on Scheme, along with bindings for the auxiliary keywords else, =>, ..., and _.

scheme-report-environment returns an environment containing the same keyword bindings as the environment returned by null-environment along with bindings for the variables whose meanings are defined by the Revised⁵ Report on Scheme, except those not defined by the Revised⁶ Report: load, interaction-environment, transcript-on, transcript-off, and char-ready?.

The bindings for each of the identifiers in the environments returned by these procedures are those of the corresponding Revised⁶ Report library, so this does not provide full backward compatibility, even if the excepted identifier bindings are not used.

constant is any self-evaluating constant, i.e., a number, boolean, character, string, or bytevector. Constants are immutable; see the note in the description of quote below.

'obj is equivalent to (quote obj). The abbreviated form is converted into the longer form by the Scheme reader (see read).

quote inhibits the normal evaluation rule for obj, allowing obj to be employed as data. Although any Scheme object may be quoted, quotation is not necessary for self-evaluating constants, i.e., numbers, booleans, characters, strings, and bytevectors.

Quoted and self-evaluating constants are immutable. That is, programs should not alter a constant via set-car!, string-set!, etc., and implementations are permitted to raise an exception with condition type &assertion if such an alteration is attempted. If an attempt to alter an immutable object is undetected, the behavior of the program is unspecified. An implementation may choose to share storage among different constants to save space.

`obj is equivalent to (quasiquote obj), ,obj is equivalent to (unquote obj), and ,@obj is equivalent to (unquote-splicing obj). The abbreviated forms are converted into the longer forms by the Scheme reader (see read).

quasiquote is similar to quote, but it allows parts of the quoted text to be "unquoted." Within a quasiquote expression, unquote and unquote-splicing subforms are evaluated, and everything else is quoted, i.e., left unevaluated. The value of each unquote subform is inserted into the output in place of the unquote form, while the value of each unquote-splicing subform is spliced into the surrounding list or vector structure. unquote and unquote-splicing are valid only within quasiquote expressions.

quasiquote expressions may be nested, with each quasiquote introducing a new level of quotation and each unquote or unquote-splicing taking away a level of quotation. An expression nested within n quasiquote expressions must be within n unquote or unquote-splicing expressions to be evaluated.

unquote and unquote-splicing forms with zero or more than one subform are valid only in splicing (list or vector) contexts. (unquote obj ...) is equivalent to (unquote obj) ..., and (unquote-splicing obj ...) is equivalent to (unquote-splicing obj) .... These forms are primarily useful as intermediate forms in the output of the quasiquote expander. They support certain useful nested quasiquotation idioms [3], such as ,@,@, which has the effect of a doubly indirect splicing when used within a doubly nested and doubly evaluated quasiquote expression.

unquote and unquote-splicing are auxiliary keywords for quasiquote. It is a syntax violation to reference these identifiers except in contexts where they are recognized as auxiliary keywords.

This section describes the basic Scheme predicates (procedures returning one of the boolean values #t or #f) for determining the type of an object or the equivalence of two objects. The equivalence predicates eq?, eqv?, and equal? are discussed first, followed by the type predicates.

In most Scheme systems, two objects are considered identical if they are represented internally by the same pointer value and distinct (not identical) if they are represented internally by different pointer values, although other criteria, such as time-stamping, are possible.

Although the particular rules for object identity vary somewhat from system to system, the following rules always hold.

eq? cannot be used to compare numbers and characters reliably. Although every inexact number is distinct from every exact number, two exact numbers, two inexact numbers, or two characters with the same value may or may not be identical.

Since constant objects are immutable, i.e., programs should not modify them via vector-set!, set-car!, or any other structure mutation operation, all or portions of different quoted constants or self-evaluating literals may be represented internally by the same object. Thus, eq? may return #t when applied to equal parts of different immutable constants.

eq? is most often used to compare symbols or to check for pointer equivalence of allocated objects, e.g., pairs, vectors, or record instances.

eqv? is similar to eq? except eqv? is guaranteed to return #t for two characters that are considered equal by char=? and two numbers that are (a) considered equal by = and (b) cannot be distinguished by any other operation besides eq? and eqv?. A consequence of (b) is that (eqv? -0.0 +0.0) is #f even though (= -0.0 +0.0) is #t in systems that distinguish -0.0 and +0.0, such as those based on IEEE floating-point arithmetic. This is because operations such as / can expose the difference:

Similarly, although 3.0 and 3.0+0.0i are considered numerically equal, they are not considered equivalent by eqv? if -0.0 and 0.0 have different representations.

The boolean value returned by eqv? is not specified when the arguments are NaNs.

eqv? is less implementation-dependent but generally more expensive than eq?.

Two objects are equal if they are equivalent according to eqv?, strings that are string=?, bytevectors that are bytevector=?, pairs whose cars and cdrs are equal, or vectors of the same length whose corresponding elements are equal.

equal? is required to terminate even for cyclic arguments and return #t "if and only if the (possibly infinite) unfoldings of its arguments into regular trees are equal as ordered trees" [24]. In essence, two values are equivalent, in the sense of equal?, if the structure of the two objects cannot be distinguished by any composition of pair and vector accessors along with the eqv?, string=?, and bytevector=? procedures for comparing data at the leaves.

Implementing equal? efficiently is tricky [1], and even with a good implementation, it is likely to be more expensive than either eqv? or eq?.

boolean? is equivalent to (lambda (x) (or (eq? x #t) (eq? x #f))).

null? is equivalent to (lambda (x) (eq? x '())).

These predicates form a hierarchy: any integer is rational, any rational is real, any real is complex, and any complex is numeric. Most implementations do not provide internal representations for irrational numbers, so all real numbers are typically rational as well.

The real?, rational?, and integer? predicates do not recognize as real, rational, or integer complex numbers with inexact zero imaginary parts.

These predicates are similar to real?, rational?, and integer?, but treat as real, rational, or integral complex numbers with inexact zero imaginary parts.

As with real?, rational?, and integer?, these predicates return #f for all non-numeric values.