r7rs-small.texinfo (15513B)
1 \input texinfo @c -*-texinfo-*- 2 @c %**start of header 3 @documentencoding UTF-8 4 @setfilename r7rs-small.info 5 @settitle Revised(7) Report on the Algorithmic Language Scheme 6 7 @ifinfo 8 @dircategory The Algorithmic Language Scheme 9 @direntry 10 * R7RS Small: (r7rs-small). Revised(7) Report on the Algorithmic Language Scheme. 11 @end direntry 12 @end ifinfo 13 14 @include r7rs-texinfo-macros.texinfo 15 16 @titlepage 17 @title Revised@sup{7} Report on the Algorithmic Language Scheme 18 19 @author ALEX SHINN, JOHN COWAN, AND ARTHUR A. GLECKLER (Editors) 20 21 @author STEVEN GANZ 22 @author ALEXEY RADUL 23 @author OLIN SHIVERS 24 @author AARON W. HSU 25 @author JEFFREY T. READ 26 @author ALARIC SNELL-PYM 27 @author BRADLEY LUCIER 28 @author DAVID RUSH 29 @author GERALD J. SUSSMAN 30 @author EMMANUEL MEDERNACH 31 @author BENJAMIN L. RUSSEL 32 33 @author RICHARD KELSEY, WILLIAM CLINGER, AND JONATHAN REES 34 @author (Editors, Revised@sup{5} Report on the Algorithmic Language Scheme) 35 36 @author MICHAEL SPERBER, R. KENT DYBVIG, MATTHEW FLATT, AND ANTON VAN STRAATEN 37 @author (Editors, Revised@sup{6} Report on the Algorithmic Language Scheme) 38 39 Dedicated to the memory of John McCarthy and Daniel Weinreb 40 41 Texinfo version 0.1 42 43 @end titlepage 44 45 @node top, Introduction, (dir), (dir) 46 @top Revised(7) Report on the Algorithmic Language Scheme 47 48 @majorheading Summary 49 50 The report gives a defining description of the programming language 51 Scheme. Scheme is a statically scoped and properly tail recursive 52 dialect of the Lisp programming language [@ref{McCarthy}] invented by 53 Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have 54 exceptionally clear and simple semantics and few different ways to 55 form expressions. A wide variety of programming paradigms, including 56 imperative, functional, and object-oriented styles, find convenient 57 expression in Scheme. 58 59 The introduction offers a brief history of the language and of 60 the report. 61 62 The first three chapters present the fundamental ideas of the language 63 and describe the notational conventions used for describing the 64 language and for writing programs in the language. 65 66 @ref{Expressions} and @ref{Program structure} describe the syntax 67 and semantics of expressions, definitions, programs, and libraries. 68 69 @ref{Standard procedures} describes Scheme's built-in procedures, 70 which include all of the language's data manipulation and input/output 71 primitives. 72 73 @ref{Formal syntax and semantics} provides a formal syntax for 74 Scheme written in extended BNF, along with a formal denotational 75 semantics. An example of the use of the language follows the formal 76 syntax and semantics. 77 78 @ref{Appendix A,, Appendix A} provides a list of the standard libraries 79 and the identifiers that they export. 80 81 @ref{Appendix B,, Appendix B} provides a list of optional but 82 standardized implementation feature names. 83 84 The report concludes with a list of references and an alphabetic index. 85 86 Note: The editors of the @rfivers{} and @rsixrs{} reports are 87 listed as authors of this report in recognition of the substantial 88 portions of this report that are copied directly from @rfivers{} 89 and @rsixrs{}. There is no intended implication that those editors, 90 individually or collectively, support or do not support this report. 91 92 @menu 93 * Introduction:: 94 * Overview of Scheme:: 95 * Lexical conventions:: 96 * Basic concepts:: 97 * Expressions:: 98 * Program structure:: 99 * Standard procedures:: 100 * Formal syntax and semantics:: 101 * Appendices:: 102 * Language changes:: 103 * Additional material:: 104 * Example:: 105 * References:: 106 * Alphabetic index of definitions of concepts, keywords, and 107 procedures: Alphabetic index. 108 @end menu 109 110 @node Introduction 111 @unnumbered Introduction 112 113 Programming languages should be designed not by piling feature on top 114 of feature, but by removing the weaknesses and restrictions that make 115 additional features appear necessary. Scheme demonstrates that a very 116 small number of rules for forming expressions, with no restrictions 117 on how they are composed, suffice to form a practical and efficient 118 programming language that is flexible enough to support most of the 119 major programming paradigms in use today. 120 121 Scheme was one of the first programming languages to incorporate 122 first-class procedures as in the lambda calculus, thereby proving the 123 usefulness of static scope rules and block structure in a dynamically 124 typed language. Scheme was the first major dialect of Lisp to 125 distinguish procedures from lambda expressions and symbols, to use 126 a single lexical environment for all variables, and to evaluate the 127 operator position of a procedure call in the same way as an operand 128 position. By relying entirely on procedure calls to express iteration, 129 Scheme emphasized the fact that tail-recursive procedure calls are 130 essentially GOTOs that pass arguments, thus allowing a programming 131 style that is both coherent and efficient. Scheme was the first widely 132 used programming language to embrace first-class escape procedures, 133 from which all previously known sequential control structures can be 134 synthesized. A subsequent version of Scheme introduced the concept 135 of exact and inexact numbers, an extension of Common Lisp's generic 136 arithmetic. More recently, Scheme became the first programming 137 language to support hygienic macros, which permit the syntax of a 138 block-structured language to be extended in a consistent and reliable 139 manner. 140 141 @heading Background 142 143 The first description of Scheme was written in 1975 [@ref{Scheme75}]. A 144 revised report [@ref{Scheme78}] appeared in 1978, which described 145 the evolution of the language as its MIT implementation was upgraded 146 to support an innovative compiler [@ref{Rabbit}]. Three distinct 147 projects began in 1981 and 1982 to use variants of Scheme for courses 148 at MIT, Yale, and Indiana University [@ref{Rees82}, @ref{MITScheme}, 149 @ref{Scheme311}] An introductory computer science textbook using 150 Scheme was published in 1984 [@ref{SICP}]. 151 152 As Scheme became more widespread, local dialects began to diverge 153 until students and researchers occasionally found it difficult to 154 understand code written at other sites. Fifteen representatives of 155 the major implementations of Scheme therefore met in October 1984 to 156 work toward a better and more widely accepted standard for Scheme. 157 Their report, the RRRS [@ref{RRRS}], was published at MIT and Indiana 158 University in the summer of 1985. Further revision took place in 159 the spring of 1986, resulting in the R3RS [@ref{R3RS}]. Work in the 160 spring of 1988 resulted in R4RS [@ref{R4RS}], which became the basis 161 for the IEEE Standard for the Scheme Programming Language in 1991 162 [@ref{IEEEScheme}]. In 1998, several additions to the IEEE standard, 163 including high-level hygienic macros, multiple return values, and eval, 164 were finalized as the @rfivers{} [@ref{R5RS}]. 165 166 In the fall of 2006, work began on a more ambitious standard, including 167 many new improvements and stricter requirements made in the interest 168 of improved portability. The resulting standard, the @rsixrs{}, was 169 completed in August 2007 [@ref{R6RS}], and was organized as a 170 core language and set of mandatory standard libraries. Several new 171 implementations of Scheme conforming to it were created. However, 172 most existing @rfivers{} implementations (even excluding those which 173 are essentially unmaintained) did not adopt @rsixrs{}, or adopted 174 only selected parts of it. 175 176 In consequence, the Scheme Steering Committee decided in August 2009 177 to divide the standard into two separate but compatible languages---a 178 ``small'' language, suitable for educators, researchers, and users 179 of embedded languages, focused on @rfivers{} compatibility, and a 180 ``large'' language focused on the practical needs of mainstream 181 software development, intended to become a replacement for 182 @rsixrs{}. The present report describes the ``small'' language of 183 that effort: therefore it cannot be considered in isolation as the 184 successor to @rsixrs{}. 185 186 We intend this report to belong to the entire Scheme community, and 187 so we grant permission to copy it in whole or in part without fee. In 188 particular, we encourage implementers of Scheme to use this report 189 as a starting point for manuals and other documentation, modifying 190 it as necessary. 191 192 @heading Acknowledgments 193 194 We would like to thank the members of the Steering Committee, William 195 Clinger, Marc Feeley, Chris Hanson, Jonathan Rees, and Olin Shivers, 196 for their support and guidance. 197 198 This report is very much a community effort, and we'd like to 199 thank everyone who provided comments and feedback, including 200 the following people: David Adler, Eli Barzilay, Taylan Ulrich 201 Bay@nodoti{}rl@nodoti{}/Kammer, Marco Benelli, Pierpaolo Bernardi, 202 Peter Bex, Per Bothner, John Boyle, Taylor Campbell, Raffael Cavallaro, 203 Ray Dillinger, Biep Durieux, Sztefan Edwards, Helmut Eller, Justin 204 Ethier, Jay Reynolds Freeman, Tony Garnock-Jones, Alan Manuel 205 Gloria, Steve Hafner, Sven Hartrumpf, Brian Harvey, Moritz Heidkamp, 206 Jean-Michel Hufflen, Aubrey Jaffer, Takashi Kato, Shiro Kawai, 207 Richard Kelsey, Oleg Kiselyov, Pjotr Kourzanov, Jonathan Kraut, 208 Daniel Krueger, Christian Stigen Larsen, Noah Lavine, Stephen Leach, 209 Larry D. Lee, Kun Liang, Thomas Lord, Vincent Stewart Manis, Perry 210 Metzger, Michael Montague, Mikael More, Vitaly Magerya, Vincent Manis, 211 Vassil Nikolov, Joseph Wayne Norton, Yuki Okumura, Daichi Oohashi, 212 Jeronimo Pellegrini, Jussi Piitulainen, Alex Queiroz, Jim Rees, Grant 213 Rettke, Andrew Robbins, Devon Schudy, Bakul Shah, Robert Smith, Arthur 214 Smyles, Michael Sperber, John David Stone, Jay Sulzberger, Malcolm 215 Tredinnick, Sam Tobin-Hochstadt, Andre van Tonder, Daniel Villeneuve, 216 Denis Washington, Alan Watson, Mark H. Weaver, G@"oran Weinholt, 217 David A. Wheeler, Andy Wingo, James Wise, J@"org F. Wittenberger, 218 Kevin A. Wortman, Sascha Ziemann. 219 220 In addition we would like to thank all the past editors, and the people 221 who helped them in turn: Hal Abelson, Norman Adams, David Bartley, Alan 222 Bawden, Michael Blair, Gary Brooks, George Carrette, Andy Cromarty, 223 Pavel Curtis, Jeff Dalton, Olivier Danvy, Ken Dickey, Betty Dexter, Bruce Duba, 224 Robert Findler, Andy Freeman, Richard Gabriel, Yekta G@"ursel, Ken 225 Haase, Robert Halstead, Robert Hieb, Paul Hudak, Morry Katz, Eugene 226 Kohlbecker, Chris Lindblad, Jacob Matthews, Mark Meyer, Jim Miller, 227 Don Oxley, Jim Philbin, Kent Pitman, John Ramsdell, Guillermo Rozas, 228 Mike Shaff, Jonathan Shapiro, Guy Steele, Julie Sussman, Perry Wagle, 229 Mitchel Wand, Daniel Weise, Henry Wu, and Ozan Yigit. We thank Carol 230 Fessenden, Daniel Friedman, and Christopher Haynes for permission 231 to use text from the Scheme 311 version 4 reference manual. We 232 thank Texas Instruments, Inc. for permission to use text from the 233 TI Scheme Language Reference Manual [@ref{TImanual85}]. We gladly 234 acknowledge the influence of manuals for MIT Scheme [@ref{MITScheme}], 235 T [@ref{Rees84}], Scheme 84 [@ref{Scheme84}], Common Lisp [@ref{CLtL}], 236 and Algol 60 [@ref{Naur63}], as well as the following SRFIs: 0, 1, 237 4, 6, 9, 11, 13, 16, 30, 34, 39, 43, 46, 62, and 87, all of which 238 are available at @url{http://srfi.schemers.org}. 239 240 @include overview.texinfo 241 242 @include lexical-conventions.texinfo 243 244 @include basic-concepts.texinfo 245 246 @node Expressions 247 @chapter Expressions 248 249 Expression types are categorized as @define{primitive} or @define{derived}. 250 Primitive expression types include variables and procedure 251 calls. Derived expression types are not semantically primitive, 252 but can instead be defined as macros. Suitable syntax definitions of 253 some of the derived expressions are given in @ref{Derived expression 254 types formal}. 255 256 The procedures @code{force}, @code{promise?}, @code{make-promise}, and 257 @code{make-parameter} are also described in this chapter because they 258 are intimately associated with the @code{delay}, @code{delay-force}, 259 and @code{parameterize} expression types. 260 261 @menu 262 * Primitive expression types:: 263 * Derived expression types:: 264 * Macros:: 265 @end menu 266 267 @include primitive-expressions.texinfo 268 269 @node Derived expression types 270 @section Derived expression types 271 272 The constructs in this section are hygienic, as discussed in 273 @ref{Macros}. For reference purposes, @ref{Derived expression types 274 formal} gives syntax definitions that will convert most of the 275 constructs described in this section into the primitive constructs 276 described in the previous section. 277 278 @menu 279 * Conditionals derived:: 280 * Binding constructs:: 281 * Sequencing:: 282 * Iteration:: 283 * Delayed evaluation:: 284 * Dynamic bindings:: 285 * Exception handling:: 286 * Quasiquotation:: 287 * Case-lambda:: 288 @end menu 289 290 @include derived/conditionals.texinfo 291 @include derived/binding-constructs.texinfo 292 @include derived/sequencing.texinfo 293 @include derived/iteration.texinfo 294 @include derived/delayed-evaluation.texinfo 295 @include derived/dynamic-bindings.texinfo 296 @include derived/exception-handling.texinfo 297 @include derived/quasiquotation.texinfo 298 @include derived/case-lambda.texinfo 299 300 @include macros.texinfo 301 302 @include program-structure.texinfo 303 304 @node Standard procedures 305 @chapter Standard procedures 306 307 @cindex initial environment 308 @cindex global environment 309 @cindex procedure 310 311 This chapter describes Scheme's built-in procedures. 312 313 The procedures @code{force}, @code{promise?}, and @code{make-promise} 314 are intimately associated with the expression types @code{delay} 315 and @code{delay-force}, and are described with them in @ref{Delayed 316 evaluation}. In the same way, the procedure @code{make-parameter} is 317 intimately associated with the expression type @code{parameterize}, 318 and is described with it in @ref{Dynamic bindings}. 319 320 A program can use a global variable definition to bind any 321 variable. It may subsequently alter any such binding by an assignment 322 (@xref{Assignments}). These operations do not modify the behavior 323 of any procedure defined in this report or imported from a library 324 (@xref{Libraries}). Altering any global binding that has not been 325 introduced by a definition has an unspecified effect on the behavior 326 of the procedures defined in this chapter. 327 328 When a procedure is said to return a @define{newly allocated} object, 329 it means that the locations in the object are fresh. 330 331 @menu 332 * Equivalence predicates:: 333 * Numbers:: 334 * Booleans:: 335 * Pairs and lists:: 336 * Symbols:: 337 * Characters:: 338 * Strings:: 339 * Vectors:: 340 * Bytevectors:: 341 * Control features:: 342 * Exceptions:: 343 * Environments and evaluation:: 344 * Input and output:: 345 * System interface:: 346 @end menu 347 348 @include procedures/equivalence-predicates.texinfo 349 @include procedures/numbers.texinfo 350 @include procedures/booleans.texinfo 351 @include procedures/pairs-and-lists.texinfo 352 @include procedures/symbols.texinfo 353 @include procedures/characters.texinfo 354 @include procedures/strings.texinfo 355 @include procedures/vectors.texinfo 356 @include procedures/bytevectors.texinfo 357 @include procedures/control-features.texinfo 358 @include procedures/exceptions.texinfo 359 @include procedures/environments-and-evaluation.texinfo 360 @include procedures/input-and-output.texinfo 361 @include procedures/system-interface.texinfo 362 363 @node Formal syntax and semantics 364 @chapter Formal syntax and semantics 365 366 This chapter provides formal descriptions of what has already been 367 described informally in previous chapters of this report. 368 369 @menu 370 * Formal syntax:: 371 * Formal semantics:: 372 * Derived expression types formal:: 373 @end menu 374 375 @include formal-syntax.texinfo 376 377 @include formal-semantics.texinfo 378 379 @include derived-expressions-implementation.texinfo 380 381 @node Appendices 382 @chapter Appendices 383 384 @menu 385 * Appendix A:: 386 * Appendix B:: 387 @end menu 388 389 @include appendix-a.texinfo 390 391 @include appendix-b.texinfo 392 393 @include language-changes.texinfo 394 395 @include additional-material.texinfo 396 397 @include scheme-example.texinfo 398 399 @include references.texinfo 400 401 @include index.texinfo 402 403 @bye