overview.texinfo (14966B)
1 @node Overview of Scheme 2 @chapter Overview of Scheme 3 4 @menu 5 * Semantics:: 6 * Syntax:: 7 * Notation and terminology:: 8 @end menu 9 10 @node Semantics 11 @section Semantics 12 13 This section gives an overview of Scheme's semantics. A detailed 14 informal semantics is the subject of chapters @ref{Basic concepts} 15 through @ref{Standard procedures}. For reference purposes, 16 @ref{Formal semantics} provides a formal semantics of Scheme. 17 18 Scheme is a statically scoped programming language. After macros are 19 expanded, each use of a 20 variable is associated with a lexically apparent binding of that 21 variable. 22 23 Scheme is a dynamically typed language. Types are associated with 24 values (also called objects) rather than with variables. Statically 25 typed languages, by contrast, associate types with variables and 26 expressions as well as with values. 27 28 All objects created in the course of a Scheme computation, including 29 procedures and continuations, have unlimited extent. No Scheme object 30 is ever destroyed. The reason that implementations of Scheme do not 31 (usually!) run out of storage is that they are permitted to reclaim 32 the storage occupied by an object if they can prove that the object 33 cannot possibly matter to any future computation. Implementations 34 of Scheme are required to be properly tail-recursive. This allows 35 the execution of an iterative computation in constant space, even if 36 the iterative computation is described by a syntactically recursive 37 procedure. Thus with a properly tail-recursive implementation, 38 iteration can be expressed using the ordinary procedure-call mechanics, 39 so that special iteration constructs are useful only as syntactic 40 sugar. @xref{Proper tail recursion}. 41 42 Scheme procedures are objects in their own right. Procedures can be 43 created dynamically, stored in data structures, returned as results of 44 procedures, and so on. One distinguishing feature of Scheme is that 45 continuations, which in most other languages only operate behind the 46 scenes, also have ``first-class'' status. Continuations are useful for 47 implementing a wide variety of advanced control constructs, including 48 non-local exits, backtracking, and coroutines. @xref{Control features}. 49 50 Arguments to Scheme procedures are always passed by value, which 51 means that the actual argument expressions are evaluated before 52 the procedure gains control, regardless of whether the procedure 53 needs the result of the evaluation. Scheme's model of arithmetic is 54 designed to remain as independent as possible of the particular ways 55 in which numbers are represented within a computer. In Scheme, every 56 integer is a rational number, every rational is a real, and every real 57 is a complex number. Thus the distinction between integer and real 58 arithmetic, so important to many programming languages, does not appear 59 in Scheme. In its place is a distinction between exact arithmetic, 60 which corresponds to the mathematical ideal, and inexact arithmetic 61 on approximations. Exact arithmetic is not limited to integers. 62 63 @node Syntax 64 @section Syntax 65 66 Scheme, like most dialects of Lisp, employs a fully parenthesized 67 prefix notation for programs and other data; the grammar of Scheme 68 generates a sublanguage of the language used for data. An important 69 consequence of this simple, uniform representation is that Scheme 70 programs and data can easily be treated uniformly by other Scheme 71 programs. For example, the @code{eval} procedure evaluates a Scheme 72 program expressed as data. 73 74 The @code{read} procedure performs syntactic as well as lexical 75 decomposition of the data it reads. The @code{read} procedure parses 76 its input as data 77 (@ref{External representations formal,, External representations}), 78 not as program. 79 80 The formal syntax of Scheme is described in @ref{Formal syntax}. 81 82 @node Notation and terminology 83 @section Notation and terminology 84 85 @menu 86 * Base and optional features:: 87 * Error situations and unspecified behavior:: 88 * Entry format:: 89 * Evaluation examples:: 90 * Naming conventions:: 91 @end menu 92 93 @node Base and optional features 94 @subsection Base and optional features 95 96 Every identifier defined in this report appears in one or more of 97 several @define{libraries}. Identifiers defined in the @define{base library} 98 are not marked specially in the body of the report. This library 99 includes the core syntax of Scheme and generally useful procedures that 100 manipulate data. For example, the variable @code{abs} is bound to a 101 procedure of one argument that computes the absolute value of a number, 102 and the variable @code{+} is bound to a procedure that computes sums. 103 The full list all the standard libraries and the identifiers they 104 export is given in @ref{Appendix A}. 105 106 All implementations of Scheme: 107 108 @itemize 109 110 @item 111 Must provide the base library and all the identifiers exported from it. 112 113 @item 114 May provide or omit the other libraries given in this report, but each 115 library must either be provided in its entirety, exporting no 116 additional identifiers, or else omitted altogether. 117 118 @item 119 May provide other libraries not described in this report. 120 121 @item 122 May also extend the function of any identifier in this report, provided 123 the extensions are not in conflict with the language reported here. 124 125 @item 126 Must support portable code by providing a mode of operation in which 127 the lexical syntax does not conflict with the lexical syntax described 128 in this report. 129 130 @end itemize 131 132 @node Error situations and unspecified behavior 133 @subsection Error situations and unspecified behavior 134 135 When speaking of an error situation, this report uses the phrase ``an 136 error is signaled'' to indicate that implementations must detect and 137 report the error. An error is signaled by raising a non-continuable 138 exception, as if by the procedure @code{raise} as described in 139 @ref{Exceptions}. The object raised is implementation-dependent 140 and need not be distinct from objects previously used for the same 141 purpose. In addition to errors signaled in situations described 142 in this report, programmers can signal their own errors and handle 143 signaled errors. 144 145 The phrase ``an error that satisfies @var{predicate} is signaled'' 146 means that an error is signaled as above. Furthermore, if the 147 object that is signaled is passed to the specified predicate (such 148 as @code{file-error?} or @code{read-error?}), the predicate returns 149 @code{#t}. 150 151 If such wording does not appear in the discussion of an error, 152 then implementations are not required to detect or report the error, 153 though they are encouraged to do so. Such a situation is sometimes, 154 but not always, referred to with the phrase ``an error.'' In such a 155 situation, an implementation may or may not signal an error; if it 156 does signal an error, the object that is signaled may or may not 157 satisfy the predicates @code{error-object?}, @code{file-error?}, 158 or @code{read-error?}. Alternatively, implementations may provide 159 non-portable extensions. 160 161 For example, it is an error for a procedure to be passed an 162 argument of a type that the procedure is not explicitly specified 163 to handle, even though such domain errors are seldom mentioned 164 in this report. Implementations may signal an error, extend a 165 procedure's domain of definition to include such arguments, or fail 166 catastrophically. 167 168 This report uses the phrase ``may report a violation of an 169 implementation restriction'' to indicate circumstances under which an 170 implementation is permitted to report that it is unable to continue 171 execution of a correct program because of some restriction imposed by 172 the implementation. Implementation restrictions are discouraged, but 173 implementations are encouraged to report violations of implementation 174 restrictions. 175 176 For example, an implementation may report a violation of an 177 implementation restriction if it does not have enough storage to run 178 a program, or if an arithmetic operation would produce an exact number 179 that is too large for the implementation to represent. 180 181 If the value of an expression is said to be ``unspecified,'' then the 182 expression must evaluate to some object without signaling an error, 183 but the value depends on the implementation; this report explicitly 184 does not say what value is returned. 185 186 Finally, the words and phrases ``must,'' ``must not,'' ``shall,'' 187 ``shall not,'' ``should,'' ``should not,'' ``may,'' ``required,'' 188 ``recommended,'' and ``optional,'' although not capitalized in this 189 report, are to be interpreted as described in RFC 2119 [@ref{rfc2119}]. They are 190 used only with reference to implementer or implementation behavior, 191 not with reference to programmer or program behavior. 192 193 @node Entry format 194 @subsection Entry format 195 196 Chapters @ref{Expressions} and @ref{Standard procedures} are organized 197 into entries. Each entry describes one language feature or a group of 198 related features, where a feature is either a syntactic construct or a 199 procedure. An entry begins with one or more header lines of the form 200 201 @c Use a table to simulate deffn without the indexing. 202 @multitable {category:} {template} 203 @item 204 @var{category}: @tab @var{template} 205 @end multitable 206 207 for identifiers in the base library, or 208 209 @multitable {name library category} {template} 210 @item 211 @var{name} library @var{category}: @tab @var{template} 212 @end multitable 213 214 where @var{name} is the short name of a library as defined in 215 @ref{Appendix A}. 216 217 If @var{category} is ``syntax,'' the entry describes an expression 218 type, and the template gives the syntax of the expression type. 219 Components of expressions are designated by syntactic variables, which 220 are written using angle brackets, for example @svar{expression} and 221 @svar{variable}. Syntactic variables are intended to denote segments of 222 program text; for example, @svar{expression} stands for any string of 223 characters which is a syntactically valid expression. The notation 224 225 @display 226 @svar{thing@sub{1}} @dots{} 227 @end display 228 229 indicates zero or more occurrences of a @svar{thing}, and 230 231 @display 232 @svar{thing@sub{1}} @svar{thing@sub{2}} @dots{} 233 @end display 234 235 indicates one or more occurrences of a @svar{thing}. 236 237 If @var{category} is ``auxiliary syntax,'' then the entry describes a 238 syntax binding that occurs only as part of specific surrounding 239 expressions. Any use as an independent syntactic construct or 240 variable is an error. 241 242 If @var{category} is ``procedure,'' then the entry describes a procedure, and 243 the header line gives a template for a call to the procedure. 244 Thus the header line 245 246 @multitable {procedure:} {vector-ref vector k} 247 @item 248 procedure: @tab @b{vector-ref} @var{vector} @var{k} 249 @end multitable 250 251 indicates that the procedure bound to the @code{vector-ref} variable takes 252 two arguments, a vector @var{vector} and an exact non-negative integer 253 @var{k} (see below). The header lines 254 255 @multitable {procedure:} {make-vector k fill} 256 @item 257 procedure: @tab @b{make-vector} @var{k} 258 @item 259 procedure: @tab @b{make-vector} @var{k} @var{fill} 260 @end multitable 261 262 indicate that the @code{make-vector} procedure must be defined to take 263 either one or two arguments. 264 265 It is an error for a procedure to be presented with an argument 266 that it is not specified to handle. For succinctness, we follow 267 the convention that if an argument name is also the name of a type 268 listed in @ref{Disjointness of types}, then it is an error if that 269 argument is not of the named type. For example, the header line for 270 @code{vector-ref} given above dictates that the first argument to 271 @code{vector-ref} is a vector. The following naming conventions also 272 imply type restrictions: 273 274 @table @asis 275 @item @var{alist} 276 association list (list of pairs) 277 278 @item @var{boolean} 279 boolean value (@code{#t} or @code{#f}) 280 281 @item @var{byte} 282 exact integer 0 @leq{} @var{byte} < 256 283 284 @item @var{bytevector} 285 bytevector 286 287 @item @var{char} 288 character 289 290 @item @var{end} 291 exact non-negative integer 292 293 @item @var{k}, @vari{k}, @dots{} @var{k@sub{j}}, @dots{} 294 exact non-negative integer 295 296 @item @var{letter} 297 alphabetic character 298 299 @item @var{list}, @vari{list}, @dots{} @var{list@sub{j}}, @dots{} 300 list (see @ref{Pairs and lists}) 301 302 @item @var{n}, @vari{n}, @dots{} @var{n@sub{j}}, @dots{} 303 integer 304 305 @item @var{obj} 306 any object 307 308 @item @var{pair} 309 pair 310 311 @item @var{port} 312 port 313 314 @item @var{proc} 315 procedure 316 317 @item @var{q}, @vari{q}, @dots{} @var{q@sub{j}}, @dots{} 318 rational number 319 320 @item @var{start} 321 exact non-negative integer 322 323 @item @var{string} 324 string 325 326 @item @var{symbol} 327 symbol 328 329 @item @var{thunk} 330 zero-argument procedure 331 332 @item @var{vector} 333 vector 334 335 @item @var{x}, @vari{x}, @dots{} @var{x@sub{j}}, @dots{} 336 real number 337 338 @item @var{y}, @vari{y}, @dots{} @var{y@sub{j}}, @dots{} 339 real number 340 341 @item @var{z}, @vari{z}, @dots{} @var{z@sub{j}}, @dots{} 342 complex number 343 @end table 344 345 The names @var{start} and @var{end} are used as indexes into strings, 346 vectors, and bytevectors. Their use implies the following: 347 348 @itemize 349 @item 350 It is an error if @var{start} is greater than @var{end}. 351 352 @item 353 It is an error if @var{end} is greater than the length of the string, 354 vector, or bytevector. 355 356 @item 357 If @var{start} is omitted, it is assumed to be zero. 358 359 @item 360 If @var{end} is omitted, it assumed to be the length of the string, 361 vector, or bytevector. 362 363 @item 364 The index @var{start} is always inclusive and the index @var{end} is 365 always exclusive. As an example, consider a string. If @var{start} and 366 @var{end} are the same, an empty substring is referred to, and if 367 @var{start} is zero and @var{end} is the length of string, then the 368 entire string is referred to. 369 370 @end itemize 371 372 @node Evaluation examples 373 @subsection Evaluation examples 374 375 The symbol @samp{@result{}} used in program examples is read ``evaluates 376 to.'' For example, 377 378 @lisp 379 (* 5 8) @result{} 40 380 @end lisp 381 382 means that the expression @code{(* 5 8)} evaluates to the object 383 @code{40}. Or, more precisely: the expression given by the sequence of 384 characters ``@code{(* 5 8)}'' evaluates, in an environment containing 385 the base library, to an object that can be represented externally by 386 the sequence of characters ``@code{40}.'' 387 @xref{External representations basic,, External representations} for 388 a discussion of external representations of objects. 389 390 @node Naming conventions 391 @subsection Naming conventions 392 393 By convention, @samp{?} is the final character of the names of 394 procedures that always return a boolean value. Such procedures are 395 called @define{predicates}. Predicates are generally understood to be 396 side-effect free, except that they may raise an exception when passed 397 the wrong type of argument. 398 399 Similarly, @samp{!} is the final character of the names of procedures 400 that store values into previously allocated locations (@ref{Storage 401 model}). Such procedures are called @define{mutation procedures}. The 402 value returned by a mutation procedure is unspecified. 403 404 By convention, @samp{->} appears within the names of procedures that 405 take an object of one type and return an analogous object of another 406 type. For example, @code{list->vector} takes a list and returns a 407 vector whose elements are the same as those of the list. 408 409 A @define{command} is a procedure that does not return useful values to 410 its continuation. 411 412 A @define{thunk} is a procedure that does not accept arguments.