r7rs-small-texinfo

basic-concepts.texinfo (14915B)

---

 @node Basic concepts
 @chapter Basic concepts
 
 @c XXX: How do I insert commas into menu items?
 @menu
 * Variables syntactic keywords and regions::
 * Disjointness of types::
 * External representations basic::
 * Storage model::
 * Proper tail recursion::
 @end menu
 
 @node Variables syntactic keywords and regions
 @section Variables, syntactic keywords, and regions
 
 @cindex identifier
 @cindex syntactic keyword
 @cindex variable
 @cindex binding
 @cindex global environment
 
 An identifier can name either a type of syntax or a location where
 a value can be stored. An identifier that names a type of syntax is
 called a @define{syntactic keyword} and is said to be @define{bound} to
 a transformer for that syntax. An identifier that names a location
 is called a @define{variable} and is said to be @define{bound} to that
 location. The set of all visible bindings in effect at some point
 in a program is known as the @define{environment} in effect at that
 point. The value stored in the location to which a variable is bound
 is called the variable's value. By abuse of terminology, the variable
 is sometimes said to name the value or to be bound to the value. This
 is not quite accurate, but confusion rarely results from this practice.
 
 @cindex binding construct
 
 Certain expression types are used to create new kinds of syntax and to
 bind syntactic keywords to those new syntaxes, while other expression
 types create new locations and bind variables to those locations. These
 expression types are called @define{binding constructs}. Those
 that bind syntactic keywords are listed in @ref{Macros}. The most
 fundamental of the variable binding constructs is the @code{lambda}
 expression, because all other variable binding constructs (except
 top-level bindings) can be explained in terms of @code{lambda}
 expressions. The other variable binding constructs are @code{let},
 @code{let*}, @code{letrec}, @code{letrec*}, @code{let-values},
 @code{let*-values}, and @code{do} expressions (see @ref{Procedures},
 @ref{Binding constructs}, and @ref{Iteration}).
 
 @cindex bound
 
 Scheme is a language with block structure. To each place where an
 identifier is bound in a program there corresponds a @define{region}
 of the program text within which the binding is visible. The region
 is determined by the particular binding construct that establishes
 the binding; if the binding is established by a @code{lambda}
 expression, for example, then its region is the entire @code{lambda}
 expression. Every mention of an identifier refers to the binding
 of the identifier that established the innermost of the regions
 containing the use. If there is no binding of the identifier whose
 region contains the use, then the use refers to the binding for the
 variable in the global environment, if any (@ref{Expressions} and
 @ref{Standard procedures}); if there is no binding for the identifier,
 it is said to be @define{unbound}.
 
 @node Disjointness of types
 @section Disjointness of types
 
 @cindex type
 
 No object satisfies more than one of the following predicates:
 
 @c Yes, this is a table in the PDF, but it's semantically a list.
 @itemize
 
 @item
 @code{boolean?}
 
 @item
 @code{bytevector?}
 
 @item
 @code{char?}
 
 @item
 @code{eof-object?}
 
 @item
 @code{null?}
 
 @item
 @code{number?}
 
 @item
 @code{pair?}
 
 @item
 @code{port?}
 
 @item
 @code{procedure?}
 
 @item
 @code{string?}
 
 @item
 @code{symbol?}
 
 @item
 @code{vector?}
 
 @end itemize
 
 and all predicates created by @code{define-record-type}.
 
 @cindex empty list
 
 These predicates define the types @define{boolean}, @define{bytevector},
 @define{character}, the empty list object, @define{eof-object}, @define{number},
 @define{pair}, @define{port}, @define{procedure}, @define{string}, @define{symbol},
 @define{vector}, and all record types.
 
 @cindex true
 @cindex false
 
 Although there is a separate boolean type, any Scheme value can be used
 as a boolean value for the purpose of a conditional test. As explained
 in @ref{Booleans}, all values count as true in such a test except for
 @code{#f}. This report uses the word ``true'' to refer to any Scheme
 value except @code{#f}, and the word ``false'' to refer to @code{#f}.
 
 @node External representations basic
 @section External representations (basic)
 
 An important concept in Scheme (and Lisp) is that of the @define{external
 representation} of an object as a sequence of characters. For example,
 an external representation of the integer 28 is the sequence of
 characters @samp{28}, and an external representation of a list
 consisting of the integers 8 and 13 is the sequence of characters
 @samp{(8 13)}.
 
 The external representation of an object is not necessarily unique. The
 integer 28 also has representations @samp{#e28.000} and @samp{#x1c},
 and the list in the previous paragraph also has the representations
 @samp{( 08 13 )} and @samp{(8 . (13 . ()))} (see @ref{Pairs and
 lists}).
 
 Many objects have standard external representations, but some, such as
 procedures, do not have standard representations (although particular
 implementations may define representations for them).
 
 An external representation can be written in a program to obtain the
 corresponding object (see @code{quote}, @ref{Literal expressions}).
 
 External representations can also be used for input and output. The
 procedure @code{read} (@ref{Input}) parses external representations,
 and the procedure @code{write} (@ref{Output}) generates them. Together,
 they provide an elegant and powerful input/output facility.
 
 Note that the sequence of characters @samp{(+ 2 6)} is @emph{not}
 an external representation of the integer 8, even though it @emph{is}
 an expression evaluating to the integer 8; rather, it is an external
 representation of a three-element list, the elements of which are
 the symbol @code{+} and the integers 2 and 6. Scheme's syntax has the
 property that any sequence of characters that is an expression is also
 the external representation of some object. This can lead to confusion,
 since it is not always obvious out of context whether a given sequence
 of characters is intended to denote data or program, but it is also
 a source of power, since it facilitates writing programs such as
 interpreters and compilers that treat programs as data (or vice versa).
 
 The syntax of external representations of various kinds of objects
 accompanies the description of the primitives for manipulating the
 objects in the appropriate sections of @ref{Standard procedures}.
 
 @node Storage model
 @section Storage model
 
 @cindex location
 
 Variables and objects such as pairs, strings, vectors, and bytevectors
 implicitly denote locations or sequences of locations. A string,
 for example, denotes as many locations as there are characters in the
 string. A new value can be stored into one of these locations using
 the @code{string-set!} procedure, but the string continues to denote
 the same locations as before.
 
 An object fetched from a location, by a variable reference or by a
 procedure such as @code{car}, @code{vector-ref}, or @code{string-ref},
 is equivalent in the sense of @code{eqv?} (@ref{Equivalence
 predicates}) 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 newly allocated for
 a variable or object, what is meant is that an appropriate number
 of locations are chosen from the set of locations that are not in
 use, and the chosen locations are marked to indicate that they
 are now in use before the variable or object is made to denote
 them. Notwithstanding this, it is understood that the empty list
 cannot be newly allocated, because it is a unique object. It is also
 understood that empty strings, empty vectors, and empty bytevectors,
 which contain no locations, may or may not be newly allocated.
 
 @cindex mutable
 @cindex immutable
 
 Every object that denotes locations is either mutable
 or immutable. Literal constants, the strings returned by
 @code{symbol->string}, and possibly the environment returned by
 @code{scheme-report-environment} are immutable objects. All objects
 created by the other procedures listed in this report are mutable. It
 is an error to attempt to store a new value into a location that is
 denoted by an immutable object.
 
 These locations are to be understood as conceptual, not
 physical. Hence, they do not necessarily correspond to memory
 addresses, and even if they do, the memory address might not be
 constant.
 
 @rationale{}
 @cindex constant
 
 In many systems it is desirable for constants (i.e. the values
 of literal expressions) to reside in read-only memory. Making it
 an error to alter constants permits this implementation strategy,
 while not requiring other systems to distinguish between mutable and
 immutable objects.
 
 @node Proper tail recursion
 @section Proper tail recursion
 
 @cindex proper tail recursion
 @cindex tail call
 
 Implementations of Scheme are required to be @define{properly
 tail-recursive}.  Procedure calls that occur in certain syntactic
 contexts defined below are @define{tail calls}. A Scheme implementation
 is properly tail-recursive if it supports an unbounded number of active
 tail calls. A call is @define{active} if the called procedure might still
 return. Note that this includes calls that might be returned from
 either by the current continuation or by continuations captured earlier
 by @code{call-with-current-continuation} that are later invoked. In
 the absence of captured continuations, calls could return at most
 once and the active calls would be those that had not yet returned. A
 formal definition of proper tail recursion can be found in [@ref{propertailrecursion}].
 
 @rationale{}
 
 Intuitively, no space is needed for an active tail call because the
 continuation that is used in the tail call has the same semantics as
 the continuation passed to the procedure containing the call. Although
 an improper implementation might use a new continuation in the call,
 a return to this new continuation would be followed immediately by
 a return to the continuation passed to the procedure. A properly
 tail-recursive implementation returns to that continuation directly.
 
 Proper tail recursion was one of the central ideas in Steele and
 Sussman's original version of Scheme. Their first Scheme interpreter
 implemented both functions and actors. Control flow was expressed
 using actors, which differed from functions in that they passed their
 results on to another actor instead of returning to a caller. In the
 terminology of this section, each actor finished with a tail call to
 another actor.
 
 Steele and Sussman later observed that in their interpreter the code
 for dealing with actors was identical to that for functions and thus
 there was no need to include both in the language.
 
 A @define{tail call} is a procedure call that occurs in a @define{tail
 context}. Tail contexts are defined inductively. Note that a tail
 context is always determined with respect to a particular lambda
 expression.
 
 @itemize
 @item
 The last expression within the body of a lambda expression, shown as
 <tail expression> below, occurs in a tail context. The same is true of
 all the bodies of @code{case-lambda} expressions.
 
 @lisp
 (lambda @svar{formals}
   @svar{definition}* @svar{expression}* @svar{tail expression})
 
 (case-lambda (@svar{formals} @svar{tail body})*)
 @end lisp
 
 @item
 If one of the following expressions is in a tail context, then the
 subexpressions shown as @svar{tail expression} are in a tail context.
 These were derived from rules in the grammar given in @ref{Formal
 syntax and semantics} by replacing some occurrences of @svar{body} with
 @svar{tail body}, some occurrences of @svar{expression} with @svar{tail
 expression}, and some occurrences of @svar{sequence} with @svar{tail
 sequence}. Only those rules that contain tail contexts are shown here.
 
 @lisp
 (if @rsvar{expression} @rsvar{tail expression} @rsvar{tail expression})
 (if @rsvar{expression} @rsvar{tail expression})
 
 (cond @rsvar{cond clause}@sup{@r{+}})
 (cond @rsvar{cond clause}@r{*} (else @rsvar{tail sequence}))
 
 (case @rsvar{expression}
   @rsvar{case clause}@sup{+})
 (case @rsvar{expression}
   @rsvar{case clause}@r{*}
   (else @rsvar{tail sequence}))
 
 (and @rsvar{expression}@r{*} @rsvar{tail expression})
 (or @rsvar{expression}@r{*} @rsvar{tail expression})
 
 (when @rsvar{test} @rsvar{tail sequence})
 (unless @rsvar{test} @rsvar{tail sequence})
 
 (let (@rsvar{binding spec}@r{*}) @rsvar{tail body})
 (let @rsvar{variable} (@rsvar{binding spec}@r{*}) @rsvar{tail body})
 (let* (@rsvar{binding spec}@r{*}) @rsvar{tail body})
 (letrec (@rsvar{binding spec}@r{*}) @rsvar{tail body})
 (letrec* (@rsvar{binding spec}@r{*}) @rsvar{tail body})
 (let-values (@rsvar{mv binding spec}@r{*}) @rsvar{tail body})
 (let*-values (@rsvar{mv binding spec}@r{*}) @rsvar{tail body})
 
 (let-syntax (@rsvar{syntax spec}@r{*}) @rsvar{tail body})
 (letrec-syntax (@rsvar{syntax spec}@r{*}) @rsvar{tail body})
 
 (begin @rsvar{tail sequence})
 
 (do (@rsvar{iteration spec}@r{*})
     (@rsvar{test} @rsvar{tail sequence})
   @rsvar{expression}@r{*})
 @end lisp
 
 where
 
 @lisp
 @rsvar{cond clause} @expansion{} (@rsvar{test} @rsvar{tail sequence})
 @rsvar{case clause} @expansion{} ((@rsvar{datum}@r{*}) @rsvar{tail sequence})
 @rsvar{tail body} @expansion{} @rsvar{definition}@r{*} @rsvar{tail sequence}
 @rsvar{tail sequence} @expansion{} @rsvar{expression}@r{*} @rsvar{tail expression}
 @end lisp
 
 @item
 If a @code{cond} or @code{case} expression is in a tail context, and
 has a clause of the form @code{(}@svar{expression@sub{1}} @code{=>}
 @svar{expression@sub{2}}@code{)} then the (implied) call to the
 procedure that results from the evaluation of @svar{expression} is in a
 tail context. @svar{expression} itself is not in a tail context.
 
 @end itemize
 
 Certain procedures defined in this report are also required to
 perform tail calls. The first argument passed to @code{apply} and to
 @code{call-with-current-continuation}, and the second argument passed
 to @code{call-with-values}, must be called via a tail call. Similarly,
 @code{eval} must evaluate its first argument as if it were in tail
 position within the @code{eval} procedure.
 
 In the following example the only tail call is the call to
 @code{f}. None of the calls to @code{g} or @code{h} are tail calls. The
 reference to @code{x} is in a tail context, but it is not a call and
 thus is not a tail call.
 
 @lisp
 (lambda ()
   (if (g)
       (let ((x (h)))
         x)
       (and (g) (f))))
 @end lisp
 
 Note: Implementations may recognize that some non-tail calls, such
 as the call to @code{h} above, can be evaluated as though they were
 tail calls. In the example above, the @code{let} expression could be
 compiled as a tail call to @code{h}. (The possibility of @code{h}
 returning an unexpected number of values can be ignored, because
 in that case the effect of the @code{let} is explicitly unspecified
 and implementation-dependent.)