r7rs-small-texinfo

R7RS-small Scheme converted to Texinfo.
git clone https://kaka.farm/~git/r7rs-small-texinfo
Log | Files | Refs | README | LICENSE

basic-concepts.texinfo (14915B)


      1 @node Basic concepts
      2 @chapter Basic concepts
      3 
      4 @c XXX: How do I insert commas into menu items?
      5 @menu
      6 * Variables syntactic keywords and regions::
      7 * Disjointness of types::
      8 * External representations basic::
      9 * Storage model::
     10 * Proper tail recursion::
     11 @end menu
     12 
     13 @node Variables syntactic keywords and regions
     14 @section Variables, syntactic keywords, and regions
     15 
     16 @cindex identifier
     17 @cindex syntactic keyword
     18 @cindex variable
     19 @cindex binding
     20 @cindex global environment
     21 
     22 An identifier can name either a type of syntax or a location where
     23 a value can be stored. An identifier that names a type of syntax is
     24 called a @define{syntactic keyword} and is said to be @define{bound} to
     25 a transformer for that syntax. An identifier that names a location
     26 is called a @define{variable} and is said to be @define{bound} to that
     27 location. The set of all visible bindings in effect at some point
     28 in a program is known as the @define{environment} in effect at that
     29 point. The value stored in the location to which a variable is bound
     30 is called the variable's value. By abuse of terminology, the variable
     31 is sometimes said to name the value or to be bound to the value. This
     32 is not quite accurate, but confusion rarely results from this practice.
     33 
     34 @cindex binding construct
     35 
     36 Certain expression types are used to create new kinds of syntax and to
     37 bind syntactic keywords to those new syntaxes, while other expression
     38 types create new locations and bind variables to those locations. These
     39 expression types are called @define{binding constructs}. Those
     40 that bind syntactic keywords are listed in @ref{Macros}. The most
     41 fundamental of the variable binding constructs is the @code{lambda}
     42 expression, because all other variable binding constructs (except
     43 top-level bindings) can be explained in terms of @code{lambda}
     44 expressions. The other variable binding constructs are @code{let},
     45 @code{let*}, @code{letrec}, @code{letrec*}, @code{let-values},
     46 @code{let*-values}, and @code{do} expressions (see @ref{Procedures},
     47 @ref{Binding constructs}, and @ref{Iteration}).
     48 
     49 @cindex bound
     50 
     51 Scheme is a language with block structure. To each place where an
     52 identifier is bound in a program there corresponds a @define{region}
     53 of the program text within which the binding is visible. The region
     54 is determined by the particular binding construct that establishes
     55 the binding; if the binding is established by a @code{lambda}
     56 expression, for example, then its region is the entire @code{lambda}
     57 expression. Every mention of an identifier refers to the binding
     58 of the identifier that established the innermost of the regions
     59 containing the use. If there is no binding of the identifier whose
     60 region contains the use, then the use refers to the binding for the
     61 variable in the global environment, if any (@ref{Expressions} and
     62 @ref{Standard procedures}); if there is no binding for the identifier,
     63 it is said to be @define{unbound}.
     64 
     65 @node Disjointness of types
     66 @section Disjointness of types
     67 
     68 @cindex type
     69 
     70 No object satisfies more than one of the following predicates:
     71 
     72 @c Yes, this is a table in the PDF, but it's semantically a list.
     73 @itemize
     74 
     75 @item
     76 @code{boolean?}
     77 
     78 @item
     79 @code{bytevector?}
     80 
     81 @item
     82 @code{char?}
     83 
     84 @item
     85 @code{eof-object?}
     86 
     87 @item
     88 @code{null?}
     89 
     90 @item
     91 @code{number?}
     92 
     93 @item
     94 @code{pair?}
     95 
     96 @item
     97 @code{port?}
     98 
     99 @item
    100 @code{procedure?}
    101 
    102 @item
    103 @code{string?}
    104 
    105 @item
    106 @code{symbol?}
    107 
    108 @item
    109 @code{vector?}
    110 
    111 @end itemize
    112 
    113 and all predicates created by @code{define-record-type}.
    114 
    115 @cindex empty list
    116 
    117 These predicates define the types @define{boolean}, @define{bytevector},
    118 @define{character}, the empty list object, @define{eof-object}, @define{number},
    119 @define{pair}, @define{port}, @define{procedure}, @define{string}, @define{symbol},
    120 @define{vector}, and all record types.
    121 
    122 @cindex true
    123 @cindex false
    124 
    125 Although there is a separate boolean type, any Scheme value can be used
    126 as a boolean value for the purpose of a conditional test. As explained
    127 in @ref{Booleans}, all values count as true in such a test except for
    128 @code{#f}. This report uses the word ``true'' to refer to any Scheme
    129 value except @code{#f}, and the word ``false'' to refer to @code{#f}.
    130 
    131 @node External representations basic
    132 @section External representations (basic)
    133 
    134 An important concept in Scheme (and Lisp) is that of the @define{external
    135 representation} of an object as a sequence of characters. For example,
    136 an external representation of the integer 28 is the sequence of
    137 characters @samp{28}, and an external representation of a list
    138 consisting of the integers 8 and 13 is the sequence of characters
    139 @samp{(8 13)}.
    140 
    141 The external representation of an object is not necessarily unique. The
    142 integer 28 also has representations @samp{#e28.000} and @samp{#x1c},
    143 and the list in the previous paragraph also has the representations
    144 @samp{( 08 13 )} and @samp{(8 . (13 . ()))} (see @ref{Pairs and
    145 lists}).
    146 
    147 Many objects have standard external representations, but some, such as
    148 procedures, do not have standard representations (although particular
    149 implementations may define representations for them).
    150 
    151 An external representation can be written in a program to obtain the
    152 corresponding object (see @code{quote}, @ref{Literal expressions}).
    153 
    154 External representations can also be used for input and output. The
    155 procedure @code{read} (@ref{Input}) parses external representations,
    156 and the procedure @code{write} (@ref{Output}) generates them. Together,
    157 they provide an elegant and powerful input/output facility.
    158 
    159 Note that the sequence of characters @samp{(+ 2 6)} is @emph{not}
    160 an external representation of the integer 8, even though it @emph{is}
    161 an expression evaluating to the integer 8; rather, it is an external
    162 representation of a three-element list, the elements of which are
    163 the symbol @code{+} and the integers 2 and 6. Scheme's syntax has the
    164 property that any sequence of characters that is an expression is also
    165 the external representation of some object. This can lead to confusion,
    166 since it is not always obvious out of context whether a given sequence
    167 of characters is intended to denote data or program, but it is also
    168 a source of power, since it facilitates writing programs such as
    169 interpreters and compilers that treat programs as data (or vice versa).
    170 
    171 The syntax of external representations of various kinds of objects
    172 accompanies the description of the primitives for manipulating the
    173 objects in the appropriate sections of @ref{Standard procedures}.
    174 
    175 @node Storage model
    176 @section Storage model
    177 
    178 @cindex location
    179 
    180 Variables and objects such as pairs, strings, vectors, and bytevectors
    181 implicitly denote locations or sequences of locations. A string,
    182 for example, denotes as many locations as there are characters in the
    183 string. A new value can be stored into one of these locations using
    184 the @code{string-set!} procedure, but the string continues to denote
    185 the same locations as before.
    186 
    187 An object fetched from a location, by a variable reference or by a
    188 procedure such as @code{car}, @code{vector-ref}, or @code{string-ref},
    189 is equivalent in the sense of @code{eqv?} (@ref{Equivalence
    190 predicates}) to the object last stored in the location before the
    191 fetch.
    192 
    193 Every location is marked to show whether it is in use. No variable
    194 or object ever refers to a location that is not in use.
    195 
    196 Whenever this report speaks of storage being newly allocated for
    197 a variable or object, what is meant is that an appropriate number
    198 of locations are chosen from the set of locations that are not in
    199 use, and the chosen locations are marked to indicate that they
    200 are now in use before the variable or object is made to denote
    201 them. Notwithstanding this, it is understood that the empty list
    202 cannot be newly allocated, because it is a unique object. It is also
    203 understood that empty strings, empty vectors, and empty bytevectors,
    204 which contain no locations, may or may not be newly allocated.
    205 
    206 @cindex mutable
    207 @cindex immutable
    208 
    209 Every object that denotes locations is either mutable
    210 or immutable. Literal constants, the strings returned by
    211 @code{symbol->string}, and possibly the environment returned by
    212 @code{scheme-report-environment} are immutable objects. All objects
    213 created by the other procedures listed in this report are mutable. It
    214 is an error to attempt to store a new value into a location that is
    215 denoted by an immutable object.
    216 
    217 These locations are to be understood as conceptual, not
    218 physical. Hence, they do not necessarily correspond to memory
    219 addresses, and even if they do, the memory address might not be
    220 constant.
    221 
    222 @rationale{}
    223 @cindex constant
    224 
    225 In many systems it is desirable for constants (i.e. the values
    226 of literal expressions) to reside in read-only memory. Making it
    227 an error to alter constants permits this implementation strategy,
    228 while not requiring other systems to distinguish between mutable and
    229 immutable objects.
    230 
    231 @node Proper tail recursion
    232 @section Proper tail recursion
    233 
    234 @cindex proper tail recursion
    235 @cindex tail call
    236 
    237 Implementations of Scheme are required to be @define{properly
    238 tail-recursive}.  Procedure calls that occur in certain syntactic
    239 contexts defined below are @define{tail calls}. A Scheme implementation
    240 is properly tail-recursive if it supports an unbounded number of active
    241 tail calls. A call is @define{active} if the called procedure might still
    242 return. Note that this includes calls that might be returned from
    243 either by the current continuation or by continuations captured earlier
    244 by @code{call-with-current-continuation} that are later invoked. In
    245 the absence of captured continuations, calls could return at most
    246 once and the active calls would be those that had not yet returned. A
    247 formal definition of proper tail recursion can be found in [@ref{propertailrecursion}].
    248 
    249 @rationale{}
    250 
    251 Intuitively, no space is needed for an active tail call because the
    252 continuation that is used in the tail call has the same semantics as
    253 the continuation passed to the procedure containing the call. Although
    254 an improper implementation might use a new continuation in the call,
    255 a return to this new continuation would be followed immediately by
    256 a return to the continuation passed to the procedure. A properly
    257 tail-recursive implementation returns to that continuation directly.
    258 
    259 Proper tail recursion was one of the central ideas in Steele and
    260 Sussman's original version of Scheme. Their first Scheme interpreter
    261 implemented both functions and actors. Control flow was expressed
    262 using actors, which differed from functions in that they passed their
    263 results on to another actor instead of returning to a caller. In the
    264 terminology of this section, each actor finished with a tail call to
    265 another actor.
    266 
    267 Steele and Sussman later observed that in their interpreter the code
    268 for dealing with actors was identical to that for functions and thus
    269 there was no need to include both in the language.
    270 
    271 A @define{tail call} is a procedure call that occurs in a @define{tail
    272 context}. Tail contexts are defined inductively. Note that a tail
    273 context is always determined with respect to a particular lambda
    274 expression.
    275 
    276 @itemize
    277 @item
    278 The last expression within the body of a lambda expression, shown as
    279 <tail expression> below, occurs in a tail context. The same is true of
    280 all the bodies of @code{case-lambda} expressions.
    281 
    282 @lisp
    283 (lambda @svar{formals}
    284   @svar{definition}* @svar{expression}* @svar{tail expression})
    285 
    286 (case-lambda (@svar{formals} @svar{tail body})*)
    287 @end lisp
    288 
    289 @item
    290 If one of the following expressions is in a tail context, then the
    291 subexpressions shown as @svar{tail expression} are in a tail context.
    292 These were derived from rules in the grammar given in @ref{Formal
    293 syntax and semantics} by replacing some occurrences of @svar{body} with
    294 @svar{tail body}, some occurrences of @svar{expression} with @svar{tail
    295 expression}, and some occurrences of @svar{sequence} with @svar{tail
    296 sequence}. Only those rules that contain tail contexts are shown here.
    297 
    298 @lisp
    299 (if @rsvar{expression} @rsvar{tail expression} @rsvar{tail expression})
    300 (if @rsvar{expression} @rsvar{tail expression})
    301 
    302 (cond @rsvar{cond clause}@sup{@r{+}})
    303 (cond @rsvar{cond clause}@r{*} (else @rsvar{tail sequence}))
    304 
    305 (case @rsvar{expression}
    306   @rsvar{case clause}@sup{+})
    307 (case @rsvar{expression}
    308   @rsvar{case clause}@r{*}
    309   (else @rsvar{tail sequence}))
    310 
    311 (and @rsvar{expression}@r{*} @rsvar{tail expression})
    312 (or @rsvar{expression}@r{*} @rsvar{tail expression})
    313 
    314 (when @rsvar{test} @rsvar{tail sequence})
    315 (unless @rsvar{test} @rsvar{tail sequence})
    316 
    317 (let (@rsvar{binding spec}@r{*}) @rsvar{tail body})
    318 (let @rsvar{variable} (@rsvar{binding spec}@r{*}) @rsvar{tail body})
    319 (let* (@rsvar{binding spec}@r{*}) @rsvar{tail body})
    320 (letrec (@rsvar{binding spec}@r{*}) @rsvar{tail body})
    321 (letrec* (@rsvar{binding spec}@r{*}) @rsvar{tail body})
    322 (let-values (@rsvar{mv binding spec}@r{*}) @rsvar{tail body})
    323 (let*-values (@rsvar{mv binding spec}@r{*}) @rsvar{tail body})
    324 
    325 (let-syntax (@rsvar{syntax spec}@r{*}) @rsvar{tail body})
    326 (letrec-syntax (@rsvar{syntax spec}@r{*}) @rsvar{tail body})
    327 
    328 (begin @rsvar{tail sequence})
    329 
    330 (do (@rsvar{iteration spec}@r{*})
    331     (@rsvar{test} @rsvar{tail sequence})
    332   @rsvar{expression}@r{*})
    333 @end lisp
    334 
    335 where
    336 
    337 @lisp
    338 @rsvar{cond clause} @expansion{} (@rsvar{test} @rsvar{tail sequence})
    339 @rsvar{case clause} @expansion{} ((@rsvar{datum}@r{*}) @rsvar{tail sequence})
    340 @rsvar{tail body} @expansion{} @rsvar{definition}@r{*} @rsvar{tail sequence}
    341 @rsvar{tail sequence} @expansion{} @rsvar{expression}@r{*} @rsvar{tail expression}
    342 @end lisp
    343 
    344 @item
    345 If a @code{cond} or @code{case} expression is in a tail context, and
    346 has a clause of the form @code{(}@svar{expression@sub{1}} @code{=>}
    347 @svar{expression@sub{2}}@code{)} then the (implied) call to the
    348 procedure that results from the evaluation of @svar{expression} is in a
    349 tail context. @svar{expression} itself is not in a tail context.
    350 
    351 @end itemize
    352 
    353 Certain procedures defined in this report are also required to
    354 perform tail calls. The first argument passed to @code{apply} and to
    355 @code{call-with-current-continuation}, and the second argument passed
    356 to @code{call-with-values}, must be called via a tail call. Similarly,
    357 @code{eval} must evaluate its first argument as if it were in tail
    358 position within the @code{eval} procedure.
    359 
    360 In the following example the only tail call is the call to
    361 @code{f}. None of the calls to @code{g} or @code{h} are tail calls. The
    362 reference to @code{x} is in a tail context, but it is not a call and
    363 thus is not a tail call.
    364 
    365 @lisp
    366 (lambda ()
    367   (if (g)
    368       (let ((x (h)))
    369         x)
    370       (and (g) (f))))
    371 @end lisp
    372 
    373 Note: Implementations may recognize that some non-tail calls, such
    374 as the call to @code{h} above, can be evaluated as though they were
    375 tail calls. In the example above, the @code{let} expression could be
    376 compiled as a tail call to @code{h}. (The possibility of @code{h}
    377 returning an unexpected number of values can be ignored, because
    378 in that case the effect of the @code{let} is explicitly unspecified
    379 and implementation-dependent.)