An identifier may name a type of syntax, or it may namea location where a value can be stored. An identifier that names a typeof syntax is called asyntactic keywordand is said to bebound to that syntax. An identifier that names alocation is called avariable and is said to bebound to that location. The set of all visiblebindings in effect at some point in a program isknown as theenvironment in effect at that point. The valuestored in the location to which a variable is bound is called thevariable's value. By abuse of terminology, the variable is sometimessaid to name the value or to be bound to the value. This is not quiteaccurate, but confusion rarely results from this practice.
Certain expression types are used to create new kinds of syntaxand bind syntactic keywords to those new syntaxes, while otherexpression types create new locations and bind variables to thoselocations. These expression types are calledbinding constructs.Those that bind syntactic keywords are listed in section 4.3.The most fundamental of the variable binding constructs is thelambda expression, because all other variable binding constructscan be explained in terms oflambda expressions. The othervariable binding constructs arelet,let*,letrec,anddo expressions (see sections 4.1.4,4.2.2, and4.2.4).
Like Algol and Pascal, and unlike most other dialects of Lispexcept for Common Lisp, Scheme is a statically scoped language withblock structure. To each place where an identifier is bound in a programthere corresponds aregion of the program text within whichthe binding is visible. The region is determined by the particularbinding construct that establishes the binding; if the binding isestablished by alambda expression, for example, then its regionis the entirelambda expression. Every mention of an identifierrefers to the binding of the identifier that established theinnermost of the regions containing the use. If there is no binding ofthe identifier whose region contains the use, then the use refers to thebinding for the variable in the top level environment, if any(chapters 4 and6); if there is nobinding for the identifier,it is said to beunbound.
No object satisfies more than one of the following predicates:
boolean? pair?
symbol? number?
char? string?
vector? port?
procedure?
These predicates define the typesboolean,pair,symbol,number,char (orcharacter),string,vector,port, andprocedure. The empty list is a specialobject of its own type; it satisfies none of the above predicates.
Although there is a separate boolean type,any Scheme value can be used as a boolean value for the purpose of aconditional test. As explained in section 6.3.1, allvalues count as true in such a test except for#f.This report uses the word ``true'' to refer to anyScheme value except#f, and the word ``false'' to refer to#f.
An important concept in Scheme (and Lisp) is that of theexternalrepresentation of an object as a sequence of characters. For example,an external representation of the integer 28 is the sequence ofcharacters ``28'', and an external representation of a list consistingof the integers 8 and 13 is the sequence of characters ``(8 13)''.
The external representation of an object is not necessarily unique. Theinteger 28 also has representations ``#e28.000'' and ``#x1c'', and thelist in the previous paragraph also has the representations ``( 08 13)'' and ``(8 . (13 . ()))'' (see section 6.3.2).
Many objects have standard external representations, but some, such asprocedures, do not have standard representations (although particularimplementations may define representations for them).
An external representation may be written in a program to obtain thecorresponding object (seequote, section 4.1.2).
External representations can also be used for input and output. Theprocedureread (section 6.6.2) parses externalrepresentations, and the procedurewrite (section 6.6.3)generates them. Together, they provide an elegant and powerfulinput/output facility.
Note that the sequence of characters ``(+ 2 6)'' isnot anexternal representation of the integer 8, even though itis anexpression evaluating to the integer 8; rather, it is an externalrepresentation of a three-element list, the elements of which are the symbol+ and the integers 2 and 6. Scheme's syntax has the property thatany sequence of characters that is an expression is also the externalrepresentation of some object. This can lead to confusion, since it maynot be obvious out of context whether a given sequence of characters isintended to denote data or program, but it is also a source of power,since it facilitates writing programs such as interpreters andcompilers that treat programs as data (or vice versa).
The syntax of external representations of various kinds of objectsaccompanies the description of the primitives for manipulating theobjects in the appropriate sections of chapter 6.
Variables and objects such as pairs, vectors, and strings implicitlydenote locations or sequences of locations. A string, forexample, denotes as many locations as there are characters in the string. (These locations need not correspond to a full machine word.) A new value may bestored into one of these locations using thestring-set! procedure, butthe string continues to denote the same locations as before.
An object fetched from a location, by a variable reference or bya procedure such ascar,vector-ref, orstring-ref, isequivalent in the sense ofeqv? (section 6.1)to the object last stored in the location before the fetch.
Every location is marked to show whether it is in use.No variable or object ever refers to a location that is not in use.Whenever this report speaks of storage being allocated for a variableor object, what is meant is that an appropriate number of locations arechosen from the set of locations that are not in use, and the chosenlocations are marked to indicate that they are now in use before the variableor object is made to denote them.
In many systems it is desirable for constants (i.e. the values ofliteral expressions) to reside in read-only-memory. To express this, it isconvenient to imagine that every object that denotes locations is associatedwith a flag telling whether that object is mutable orimmutable. In such systems literal constants and the stringsreturned bysymbol->string are immutable objects, while all objectscreated by the other procedures listed in this report are mutable. It is anerror to attempt to store a new value into a location that is denoted by animmutable object.
Implementations of Scheme are required to beproperly tail-recursive.Procedure calls that occur in certain syntacticcontexts defined below are `tail calls'. A Scheme implementation isproperly tail-recursive if it supports an unbounded number of activetail calls. A call isactive if the called procedure may stillreturn. Note that this includes calls that may be returned from eitherby the current continuation or by continuations captured earlier bycall-with-current-continuation that are later invoked.In the absence of captured continuations, calls couldreturn at most once and the active calls would be those that had notyet returned.A formal definition of proper tail recursion can be foundin [8].
Rationale:Intuitively, no space is needed for an active tail call because thecontinuation that is used in the tail call has the same semantics as thecontinuation passed to the procedure containing the call. Although an improperimplementation might use a new continuation in the call, a returnto this new continuation would be followed immediately by a returnto the continuation passed to the procedure. A properly tail-recursiveimplementation returns to that continuation directly.
Proper tail recursion was one of the central ideas in Steele andSussman's original version of Scheme. Their first Scheme interpreterimplemented both functions and actors. Control flow was expressed usingactors, which differed from functions in that they passed their resultson to another actor instead of returning to a caller. In the terminologyof this section, each actor finished with a tail call to another actor.
Steele and Sussman later observed that in their interpreter the codefor dealing with actors was identical to that for functions and thusthere was no need to include both in the language.
Atail call is a procedure call that occursin atail context. Tail contexts are defined inductively. Notethat a tail context is always determined with respect to a particular lambdaexpression.
(lambda <formals>
<definition>* <expression>* <tail expression>)
(if <expression> <tail expression> <tail expression>)
(if <expression> <tail expression>)
(cond <cond clause>+)
(cond <cond clause>* (else <tail sequence>))
(case <expression>
<case clause>+)
(case <expression>
<case clause>*
(else <tail sequence>))
(and <expression>* <tail expression>)
(or <expression>* <tail expression>)
(let (<binding spec>*) <tail body>)
(let <variable> (<binding spec>*) <tail body>)
(let* (<binding spec>*) <tail body>)
(letrec (<binding spec>*) <tail body>)
(let-syntax (<syntax spec>*) <tail body>)
(letrec-syntax (<syntax spec>*) <tail body>)
(begin <tail sequence>)
(do (<iteration spec>*)
(<test> <tail sequence>)
<expression>*)
where
<cond clause> ---> (<test> <tail sequence>)
<case clause> ---> ((<datum>*) <tail sequence>)
<tail body> ---> <definition>* <tail sequence>
<tail sequence> ---> <expression>* <tail expression>
Certain built-in procedures are also required to perform tail calls.The first argument passed toapply and tocall-with-current-continuation, and the second argument passed tocall-with-values, must be called via a tail call.Similarly,eval must evaluate its argument as if itwere in tail position within theeval procedure.
In the following example the only tail call is the call tof.None of the calls tog orh are tail calls. The reference tox is in a tail context, but it is not a call and thus is not atail call.
(lambda ()
(if (g)
(let ((x (h)))
x)
(and (g) (f))))
Note: Implementations are allowed, but not required, torecognize that some non-tail calls, such as the call tohabove, can be evaluated as though they were tail calls.In the example above, thelet expression could be compiledas a tail call toh. (The possibility ofh returningan unexpected number of values can be ignored, because in thatcase the effect of thelet is explicitly unspecified andimplementation-dependent.)