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.)