1 \input texinfo @c -*-texinfo-*-
4 @settitle Revised(5) Scheme
6 @c This copy of r5rs.texi differs from Aubrey Jaffer's master copy
7 @c by a set of changes to allow the building of r5rs.dvi from r5rs.texi.
8 @c Aubrey Jaffer's view - which I agree with - is that, given that
9 @c people have the option of building r5rs.dvi from the original
10 @c LaTeX distribution for R5RS, it is not worth fixing his master
11 @c copy of r5rs.texi and the tool which autogenerates it. On the
12 @c other hand, it is a marginal convenience for people to be able to
13 @c build hardcopy from r5rs.texi, even if the results are less good
14 @c than with the original LaTeX. Hence the following fixes.
15 @c (lines 714, 725, 728, 1614, 2258): Remove invalid parentheses from
17 @c (line 2316): Change @deffnx to @deffn, and insert `@end deffn' to
18 @c terminate preceding @deffn.
19 @c (line 7320): Insert `@c ' at beginning of lines that are intended
24 @c \documentclass[twoside]{algol60}
26 @c \pagestyle{headings}
31 @c \def\headertitle{Revised$^{5}$ Scheme}
32 @c \def\integerversion{5}
34 @c Sizes and dimensions
36 @c \topmargin -.375in % Nominal distance from top of page to top of
38 @c box containing running head.
39 @c \headsep 15pt % Space between running head and text.
41 @c \textheight 663pt % Height of text (including footnotes and figures,
43 @c excluding running head and foot).
45 @c \textwidth 523pt % Width of text line.
46 @c \columnsep 15pt % Space between columns
47 @c \columnseprule 0pt % Width of rule between columns.
49 @c \parskip 5pt plus 2pt minus 2pt % Extra vertical space between paragraphs.
50 @c \parindent 0pt % Width of paragraph indentation.
51 @c \topsep 0pt plus 2pt % Extra vertical space, in addition to
53 @c \parskip, added above and below list and
55 @c paragraphing environments.
57 @c \oddsidemargin -.5in % Left margin on odd-numbered pages.
58 @c \evensidemargin -.5in % Left margin on even-numbered pages.
60 @c % End of sizes and dimensions
67 @dircategory The Algorithmic Language Scheme
69 * R5RS: (r5rs). The Revised(5) Report on Scheme.
74 @c \parindent 0pt %!! 15pt % Width of paragraph indentation.
84 @subtitle Revised(5) Report on the Algorithmic Language Scheme
87 @c \thispagestyle{empty}
89 @c \todo{"another" report?}
92 @author R@sc{ICHARD} K@sc{ELSEY}, W@sc{ILLIAM} C@sc{LINGER, AND} J@sc{ONATHAN} R@sc{EES} (@i{Editors})
93 @author H. A@sc{BELSON}
94 @author R. K. D@sc{YBVIG}
95 @author C. T. H@sc{AYNES}
96 @author G. J. R@sc{OZAS}
97 @author N. I. A@sc{DAMS IV}
98 @author D. P. F@sc{RIEDMAN}
99 @author E. K@sc{OHLBECKER}
100 @author G. L. S@sc{TEELE} J@sc{R}.
101 @author D. H. B@sc{ARTLEY}
102 @author R. H@sc{ALSTEAD}
103 @author D. O@sc{XLEY}
104 @author G. J. S@sc{USSMAN}
105 @author G. B@sc{ROOKS}
106 @author C. H@sc{ANSON}
107 @author K. M. P@sc{ITMAN}
112 @c {\it Dedicated to the Memory of ALGOL 60}
113 @i{Dedicated to the Memory of Robert Hieb}
114 @c [For the macros in R5RS -RK]
122 The report gives a defining description of the programming language
123 Scheme. Scheme is a statically scoped and properly tail-recursive
124 dialect of the Lisp programming language invented by Guy Lewis
125 Steele Jr.@: and Gerald Jay Sussman. It was designed to have an
126 exceptionally clear and simple semantics and few different ways to
127 form expressions. A wide variety of programming paradigms, including
128 imperative, functional, and message passing styles, find convenient
129 expression in Scheme.
131 The introduction offers a brief history of the language and of
134 The first three chapters present the fundamental ideas of the
135 language and describe the notational conventions used for describing the
136 language and for writing programs in the language.
138 Chapters @ref{Expressions} and @ref{Program structure} describe
139 the syntax and semantics of expressions, programs, and definitions.
141 Chapter @ref{Standard procedures} describes Scheme's built-in
142 procedures, which include all of the language's data manipulation and
143 input/output primitives.
145 Chapter @ref{Formal syntax and semantics} provides a formal syntax for Scheme
146 written in extended BNF, along with a formal denotational semantics.
147 An example of the use of the language follows the formal syntax and
150 The report concludes with a list of references and an
154 expand the summary so that it fills up the column.
170 @c \addvspace{3.5pt} % don't shrink this gap
171 @c \renewcommand{\tocshrink}{-3.5pt} % value determined experimentally
187 @c \thispagestyle{empty}
189 @c \todo{"another" report?}
192 @node top, Introduction, (dir), (dir)
193 @top Revised(5) Report on the Algorithmic Language Scheme
199 R@sc{ichard} K@sc{elsey}, W@sc{illiam} C@sc{linger, and} J@sc{onathan} R@sc{ees} (@i{Editors})
201 @multitable @columnfractions 0.25 0.25 0.25 0.25
202 @item H. A@sc{belson} @tab R. K. D@sc{ybvig} @tab C. T. H@sc{aynes} @tab G. J. R@sc{ozas}
203 @item N. I. A@sc{dams IV} @tab D. P. F@sc{riedman} @tab E. K@sc{ohlbecker} @tab G. L. S@sc{teele} J@sc{r}.
204 @item D. H. B@sc{artley} @tab R. H@sc{alstead} @tab D. O@sc{xley} @tab G. J. S@sc{ussman}
205 @item G. B@sc{rooks} @tab C. H@sc{anson} @tab K. M. P@sc{itman} @tab M. W@sc{and}
213 @c {\it Dedicated to the Memory of ALGOL 60}
214 @i{Dedicated to the Memory of Robert Hieb}
215 @c [For the macros in R5RS -RK]
222 @majorheading Summary
225 The report gives a defining description of the programming language
226 Scheme. Scheme is a statically scoped and properly tail-recursive
227 dialect of the Lisp programming language invented by Guy Lewis
228 Steele Jr.@: and Gerald Jay Sussman. It was designed to have an
229 exceptionally clear and simple semantics and few different ways to
230 form expressions. A wide variety of programming paradigms, including
231 imperative, functional, and message passing styles, find convenient
232 expression in Scheme.
234 The introduction offers a brief history of the language and of
237 The first three chapters present the fundamental ideas of the
238 language and describe the notational conventions used for describing the
239 language and for writing programs in the language.
241 Chapters @ref{Expressions} and @ref{Program structure} describe
242 the syntax and semantics of expressions, programs, and definitions.
244 Chapter @ref{Standard procedures} describes Scheme's built-in
245 procedures, which include all of the language's data manipulation and
246 input/output primitives.
248 Chapter @ref{Formal syntax and semantics} provides a formal syntax for Scheme
249 written in extended BNF, along with a formal denotational semantics.
250 An example of the use of the language follows the formal syntax and
253 The report concludes with a list of references and an
257 expand the summary so that it fills up the column.
273 @c \addvspace{3.5pt} % don't shrink this gap
274 @c \renewcommand{\tocshrink}{-3.5pt} % value determined experimentally
280 * Overview of Scheme::
281 * Lexical conventions::
284 * Program structure::
285 * Standard procedures::
286 * Formal syntax and semantics::
288 * Additional material::
304 @node Introduction, Overview of Scheme, top, top
305 @unnumbered Introduction
315 Programming languages should be designed not by piling feature on top of
316 feature, but by removing the weaknesses and restrictions that make additional
317 features appear necessary. Scheme demonstrates that a very small number
318 of rules for forming expressions, with no restrictions on how they are
319 composed, suffice to form a practical and efficient programming language
320 that is flexible enough to support most of the major programming
321 paradigms in use today.
323 @c Scheme has influenced the evolution of Lisp.
325 was one of the first programming languages to incorporate first class
326 procedures as in the lambda calculus, thereby proving the usefulness of
327 static scope rules and block structure in a dynamically typed language.
328 Scheme was the first major dialect of Lisp to distinguish procedures
329 from lambda expressions and symbols, to use a single lexical
330 environment for all variables, and to evaluate the operator position
331 of a procedure call in the same way as an operand position. By relying
332 entirely on procedure calls to express iteration, Scheme emphasized the
333 fact that tail-recursive procedure calls are essentially goto's that
334 pass arguments. Scheme was the first widely used programming language to
335 embrace first class escape procedures, from which all previously known
336 sequential control structures can be synthesized. A subsequent
337 version of Scheme introduced the concept of exact and inexact numbers,
338 an extension of Common Lisp's generic arithmetic.
339 More recently, Scheme became the first programming language to support
340 hygienic macros, which permit the syntax of a block-structured language
341 to be extended in a consistent and reliable manner.
343 @c of these innovations have recently been incorporated into Common Lisp, while
344 @c others remain to be adopted.
348 I would like to make a few comments on presentation. The most
349 important comment is about section organization. Newspaper writers
350 spend most of their time writing the first three paragraphs of any
351 article. This part of the article is often the only part read by
352 readers, and is important in enticing readers to continue. In the
353 same way, The first page is most likely to be the only page read by
354 many SIGPLAN readers. If I had my choice of what I would ask them to
355 read, it would be the material in section 1.1, the Semantics section
356 that notes that scheme is lexically scoped, tail recursive, weakly
357 typed, ... etc. I would expand on the discussion on continuations,
358 as they represent one important difference between Scheme and other
359 languages. The introduction, with its history of scheme, its history
360 of scheme reports and meetings, and acknowledgements giving names of
361 people that the reader will not likely know, is not that one page I
362 would like all to read. I suggest moving the history to the back of
363 the report, and use the first couple of pages to convince the reader
364 that the language documented in this report is worth studying.
369 @node Background, Acknowledgements, Introduction, Introduction
370 @unnumberedsec Background
373 The first description of Scheme was written in
374 1975 [Scheme75]. A revised report [Scheme78]
378 appeared in 1978, which described the evolution
379 of the language as its MIT implementation was upgraded to support an
380 innovative compiler [Rabbit]. Three distinct projects began in
381 1981 and 1982 to use variants of Scheme for courses at MIT, Yale, and
382 Indiana University [Rees82], [MITScheme], [Scheme311]. An introductory
383 computer science textbook using Scheme was published in
386 @c \vest As might be expected of a language used primarily for education and
387 @c research, Scheme has always evolved rapidly. This was no problem when
388 @c Scheme was used only within MIT, but
389 As Scheme became more widespread,
390 local dialects began to diverge until students and researchers
391 occasionally found it difficult to understand code written at other
393 Fifteen representatives of the major implementations of Scheme therefore
394 met in October 1984 to work toward a better and more widely accepted
396 @c Participating in this workshop were Hal Abelson, Norman Adams, David
397 @c Bartley, Gary Brooks, William Clinger, Daniel Friedman, Robert Halstead,
398 @c Chris Hanson, Christopher Haynes, Eugene Kohlbecker, Don Oxley, Jonathan Rees,
399 @c Guillermo Rozas, Gerald Jay Sussman, and Mitchell Wand. Kent Pitman
400 @c made valuable contributions to the agenda for the workshop but was
401 @c unable to attend the sessions.
403 @c Subsequent electronic mail discussions and committee work completed the
404 @c definition of the language.
405 @c Gerry Sussman drafted the section on numbers, Chris Hanson drafted the
406 @c sections on characters and strings, and Gary Brooks and William Clinger
407 @c drafted the sections on input and output.
408 @c William Clinger recorded the decisions of the workshop and
409 @c compiled the pieces into a coherent document.
410 @c The ``Revised revised report on Scheme''~\cite{RRRS}
412 was published at MIT and Indiana University in the summer of 1985.
413 Further revision took place in the spring of 1986 [R3RS],
414 @c , again accomplished
415 @c almost entirely by electronic mail, resulted in the present report.
416 and in the spring of 1988 [R4RS].
417 The present report reflects further revisions agreed upon in a meeting
418 at Xerox PARC in June 1992.
420 @c \vest The number 3 in the title is part of the title, not a reference to
421 @c a footnote. The word ``revised'' is raised to the third power because
422 @c the report is a revision of a report that was already twice revised.
425 Write an editors' note?
432 We intend this report to belong to the entire Scheme community, and so
433 we grant permission to copy it in whole or in part without fee. In
434 particular, we encourage implementors of Scheme to use this report as
435 a starting point for manuals and other documentation, modifying it as
441 @node Acknowledgements, , Background, Introduction
442 @unnumberedsec Acknowledgements
445 We would like to thank the following people for their help: Alan Bawden, Michael
446 Blair, George Carrette, Andy Cromarty, Pavel Curtis, Jeff Dalton, Olivier Danvy,
447 Ken Dickey, Bruce Duba, Marc Feeley,
448 Andy Freeman, Richard Gabriel, Yekta G"ursel, Ken Haase, Robert
449 Hieb, Paul Hudak, Morry Katz, Chris Lindblad, Mark Meyer, Jim Miller, Jim Philbin,
450 John Ramsdell, Mike Shaff, Jonathan Shapiro, Julie Sussman,
451 Perry Wagle, Daniel Weise, Henry Wu, and Ozan Yigit.
452 We thank Carol Fessenden, Daniel
453 Friedman, and Christopher Haynes for permission to use text from the Scheme 311
454 version 4 reference manual. We thank Texas Instruments, Inc. for permission to
455 use text from the @emph{TI Scheme Language Reference Manual}[TImanual85].
456 We gladly acknowledge the influence of manuals for MIT Scheme[MITScheme],
457 T[Rees84], Scheme 84[Scheme84],Common Lisp[CLtL],
458 and Algol 60[Naur63].
460 We also thank Betty Dexter for the extreme effort she put into
461 setting this report in @TeX{}, and Donald Knuth for designing the program
462 that caused her troubles.
464 The Artificial Intelligence Laboratory of the
465 Massachusetts Institute of Technology, the Computer Science
466 Department of Indiana University, the Computer and Information
467 Sciences Department of the University of Oregon, and the NEC Research
468 Institute supported the preparation of this report. Support for the MIT
469 work was provided in part by
470 the Advanced Research Projects Agency of the Department of Defense under Office
471 of Naval Research contract N00014-80-C-0505. Support for the Indiana
472 University work was provided by NSF grants NCS 83-04567 and NCS
480 @c \clearchapterstar{Description of the language} %\unskip\vskip -2ex
483 @c 1. Structure of the language
485 @node Overview of Scheme, Lexical conventions, Introduction, top
486 @chapter Overview of Scheme
491 * Notation and terminology::
495 @node Semantics, Syntax, Overview of Scheme, Overview of Scheme
500 This section gives an overview of Scheme's semantics. A
501 detailed informal semantics is the subject of
502 chapters @ref{Basic concepts} through @ref{Standard procedures}. For reference
503 purposes, section @ref{Formal semantics} provides a formal
506 Following Algol, Scheme is a statically scoped programming
507 language. Each use of a variable is associated with a lexically
508 apparent binding of that variable.
510 Scheme has latent as opposed to manifest types. Types
511 are associated with values (also called objects) rather than
513 with variables. (Some authors refer to languages with latent types as
514 weakly typed or dynamically typed languages.) Other languages with
515 latent types are APL, Snobol, and other dialects of Lisp. Languages
516 with manifest types (sometimes referred to as strongly typed or
517 statically typed languages) include Algol 60, Pascal, and C.
519 All objects created in the course of a Scheme computation, including
520 procedures and continuations, have unlimited extent.
521 No Scheme object is ever destroyed. The reason that
522 implementations of Scheme do not (usually!) run out of storage is that
523 they are permitted to reclaim the storage occupied by an object if
524 they can prove that the object cannot possibly matter to any future
525 computation. Other languages in which most objects have unlimited
526 extent include APL and other Lisp dialects.
528 Implementations of Scheme are required to be properly tail-recursive.
529 This allows the execution of an iterative computation in constant space,
530 even if the iterative computation is described by a syntactically
531 recursive procedure. Thus with a properly tail-recursive implementation,
532 iteration can be expressed using the ordinary procedure-call
533 mechanics, so that special iteration constructs are useful only as
534 syntactic sugar. See section @ref{Proper tail recursion}.
536 Scheme procedures are objects in their own right. Procedures can be
537 created dynamically, stored in data structures, returned as results of
538 procedures, and so on. Other languages with these properties include
541 Rozas: Scheme had them first.
545 One distinguishing feature of Scheme is that continuations, which
546 in most other languages only operate behind the scenes, also have
547 ``first-class'' status. Continuations are useful for implementing a
548 wide variety of advanced control constructs, including non-local exits,
549 backtracking, and coroutines. See section @ref{Control features}.
551 Arguments to Scheme procedures are always passed by value, which
552 means that the actual argument expressions are evaluated before the
553 procedure gains control, whether the procedure needs the result of the
554 evaluation or not. ML, C, and APL are three other languages that always
555 pass arguments by value.
556 This is distinct from the lazy-evaluation semantics of Haskell,
557 or the call-by-name semantics of Algol 60, where an argument
558 expression is not evaluated unless its value is needed by the
562 Lisp's call by value should be explained more
563 accurately. What's funny is that all values are references.
567 Scheme's model of arithmetic is designed to remain as independent as
568 possible of the particular ways in which numbers are represented within a
569 computer. In Scheme, every integer is a rational number, every rational is a
570 real, and every real is a complex number. Thus the distinction between integer
571 and real arithmetic, so important to many programming languages, does not
572 appear in Scheme. In its place is a distinction between exact arithmetic,
573 which corresponds to the mathematical ideal, and inexact arithmetic on
574 approximations. As in Common Lisp, exact arithmetic is not limited to
577 @node Syntax, Notation and terminology, Semantics, Overview of Scheme
581 Scheme, like most dialects of Lisp, employs a fully parenthesized prefix
582 notation for programs and (other) data; the grammar of Scheme generates a
583 sublanguage of the language used for data. An important
584 consequence of this simple, uniform representation is the susceptibility of
585 Scheme programs and data to uniform treatment by other Scheme programs.
586 For example, the @samp{eval} procedure evaluates a Scheme program expressed
589 The @samp{read} procedure performs syntactic as well as lexical decomposition of
590 the data it reads. The @samp{read} procedure parses its input as data
591 (section @pxref{External representation}), not as program.
593 The formal syntax of Scheme is described in section @ref{Formal syntax}.
596 @node Notation and terminology, , Syntax, Overview of Scheme
597 @section Notation and terminology
600 * Primitive; library; and optional features::
601 * Error situations and unspecified behavior::
603 * Evaluation examples::
604 * Naming conventions::
609 @node Primitive; library; and optional features, Error situations and unspecified behavior, Notation and terminology, Notation and terminology
610 @subsection Primitive; library; and optional features
614 It is required that every implementation of Scheme support all
615 features that are not marked as being @dfn{optional}. Implementations are
617 free to omit optional features of Scheme or to add extensions,
618 provided the extensions are not in conflict with the language reported
619 here. In particular, implementations must support portable code by
620 providing a syntactic mode that preempts no lexical conventions of this
623 To aid in understanding and implementing Scheme, some features are marked
624 as @dfn{library}. These can be easily implemented in terms of the other,
626 primitive, features. They are redundant in the strict sense of
627 the word, but they capture common patterns of usage, and are therefore
628 provided as convenient abbreviations.
630 @node Error situations and unspecified behavior, Entry format, Primitive; library; and optional features, Notation and terminology
631 @subsection Error situations and unspecified behavior
636 When speaking of an error situation, this report uses the phrase ``an
637 error is signalled'' to indicate that implementations must detect and
638 report the error. If such wording does not appear in the discussion of
639 an error, then implementations are not required to detect or report the
640 error, though they are encouraged to do so. An error situation that
641 implementations are not required to detect is usually referred to simply
644 For example, it is an error for a procedure to be passed an argument that
645 the procedure is not explicitly specified to handle, even though such
646 domain errors are seldom mentioned in this report. Implementations may
647 extend a procedure's domain of definition to include such arguments.
649 This report uses the phrase ``may report a violation of an
650 implementation restriction'' to indicate circumstances under which an
651 implementation is permitted to report that it is unable to continue
652 execution of a correct program because of some restriction imposed by the
653 implementation. Implementation restrictions are of course discouraged,
654 but implementations are encouraged to report violations of implementation
656 @cindex @w{implementation restriction}
658 For example, an implementation may report a violation of an
659 implementation restriction if it does not have enough storage to run a
662 If the value of an expression is said to be ``unspecified,'' then
663 the expression must evaluate to some object without signalling an error,
664 but the value depends on the implementation; this report explicitly does
665 not say what value should be returned.
666 @cindex @w{unspecified}
669 Talk about unspecified behavior vs. unspecified values.
674 Look at KMP's situations paper.
679 @node Entry format, Evaluation examples, Error situations and unspecified behavior, Notation and terminology
680 @subsection Entry format
683 Chapters @ref{Expressions} and @ref{Standard procedures} are organized
684 into entries. Each entry describes one language feature or a group of
685 related features, where a feature is either a syntactic construct or a
686 built-in procedure. An entry begins with one or more header lines of the form
690 @deffn {@var{category}} @var{template}
694 for required, primitive features, or
698 @deffn {@var{qualifier} @var{category}} @var{template}
702 where @var{qualifier} is either ``library'' or ``optional'' as defined
703 in section @ref{Primitive; library; and optional features}.
705 If @var{category} is ``syntax'', the entry describes an expression
706 type, and the template gives the syntax of the expression type.
707 Components of expressions are designated by syntactic variables, which
708 are written using angle brackets, for example, @r{<expression>},
709 @r{<variable>}. Syntactic variables should be understood to denote segments of
710 program text; for example, @r{<expression>} stands for any string of
711 characters which is a syntactically valid expression. The notation
717 indicates zero or more occurrences of a @r{<thing>}, and
720 @r{<thing1>} @r{<thing2>} @dots{}
723 indicates one or more occurrences of a @r{<thing>}.
725 If @var{category} is ``procedure'', then the entry describes a procedure, and
726 the header line gives a template for a call to the procedure. Argument
727 names in the template are @var{italicized}. Thus the header line
731 @deffn {procedure} vector-ref @var{vector} @var{k}
735 indicates that the built-in procedure @t{vector-ref} takes
736 two arguments, a vector @var{vector} and an exact non-negative integer
737 @var{k} (see below). The header lines
742 @deffn {procedure} make-vector @var{k}
745 @deffnx {procedure} make-vector @var{k} @var{fill}
749 indicate that the @t{make-vector} procedure must be defined to take
750 either one or two arguments.
753 It is an error for an operation to be presented with an argument that it
754 is not specified to handle. For succinctness, we follow the convention
755 that if an argument name is also the name of a type listed in
756 section @ref{Disjointness of types}, then that argument must be of the named type.
757 For example, the header line for @t{vector-ref} given above dictates that the
758 first argument to @t{vector-ref} must be a vector. The following naming
759 conventions also imply type restrictions:
760 @c \newcommand{\foo}[1]{\vr{#1}, \vri{#1}, $\ldots$ \vrj{#1}, $\ldots$}
763 @center @c begin-tabular
768 @item @var{list}, @var{list1}, @dots{} @var{listj}, @dots{}
769 list (see section @pxref{Pairs and lists})
770 @item @var{z}, @var{z1}, @dots{} @var{zj}, @dots{}
772 @item @var{x}, @var{x1}, @dots{} @var{xj}, @dots{}
774 @item @var{y}, @var{y1}, @dots{} @var{yj}, @dots{}
776 @item @var{q}, @var{q1}, @dots{} @var{qj}, @dots{}
778 @item @var{n}, @var{n1}, @dots{} @var{nj}, @dots{}
780 @item @var{k}, @var{k1}, @dots{} @var{kj}, @dots{}
781 exact non-negative integer
790 Provide an example entry??
795 @node Evaluation examples, Naming conventions, Entry format, Notation and terminology
796 @subsection Evaluation examples
799 The symbol ``@result{}'' used in program examples should be read
800 ``evaluates to.'' For example,
810 means that the expression @t{(* 5 8)} evaluates to the object @t{40}.
811 Or, more precisely: the expression given by the sequence of characters
812 ``@t{(* 5 8)}'' evaluates, in the initial environment, to an object
813 that may be represented externally by the sequence of characters ``@t{40}''. See section @ref{External representations} for a discussion of external
814 representations of objects.
816 @node Naming conventions, , Evaluation examples, Notation and terminology
817 @subsection Naming conventions
820 By convention, the names of procedures that always return a boolean
822 in ``@code{?}''. Such procedures are called predicates.
825 By convention, the names of procedures that store values into previously
826 allocated locations (see section @pxref{Storage model}) usually end in
829 Such procedures are called mutation procedures.
830 By convention, the value returned by a mutation procedure is unspecified.
832 By convention, ``@code{->}'' appears within the names of procedures that
834 take an object of one type and return an analogous object of another type.
835 For example, @samp{list->vector} takes a list and returns a vector whose
836 elements are the same as those of the list.
841 Terms that need defining: thunk, command (what else?).
850 @node Lexical conventions, Basic concepts, Overview of Scheme, top
851 @chapter Lexical conventions
855 * Whitespace and comments::
860 This section gives an informal account of some of the lexical
861 conventions used in writing Scheme programs. For a formal syntax of
862 Scheme, see section @ref{Formal syntax}.
864 Upper and lower case forms of a letter are never distinguished
865 except within character and string constants. For example, @samp{Foo} is
866 the same identifier as @samp{FOO}, and @t{#x1AB} is the same number as
869 @node Identifiers, Whitespace and comments, Lexical conventions, Lexical conventions
874 Most identifiers allowed by other programming
875 @cindex @w{identifier}
876 languages are also acceptable to Scheme. The precise rules for forming
877 identifiers vary among implementations of Scheme, but in all
878 implementations a sequence of letters, digits, and ``extended alphabetic
879 characters'' that begins with a character that cannot begin a number is
880 an identifier. In addition, @code{+}, @code{-}, and @code{...} are identifiers.
884 Here are some examples of identifiers:
893 the-word-recursion-has-many-meanings
898 Extended alphabetic characters may be used within identifiers as if
899 they were letters. The following are extended alphabetic characters:
904 ! $ % & * + - . / : < = > ? @@ ^ _ ~
908 See section @ref{Lexical structure} for a formal syntax of identifiers.
910 Identifiers have two uses within Scheme programs:
916 Any identifier may be used as a variable
917 or as a syntactic keyword
918 (see sections @pxref{Variables; syntactic keywords; and regions} and @pxref{Macros}).
921 When an identifier appears as a literal or within a literal
922 (see section @pxref{Literal expressions}), it is being used to denote a @emph{symbol}
923 (see section @pxref{Symbols}).
928 @cindex @w{syntactic keyword}
931 @c \label{keywordsection}
932 @c The following identifiers are syntactic keywords, and should not be used
937 @c and else quasiquote
941 @c define let* unquote-splicing
945 @c Some implementations allow all identifiers, including syntactic
946 @c keywords, to be used as variables. This is a compatible extension to
947 @c the language, but ambiguities in the language result when the
948 @c restriction is relaxed, and the ways in which these ambiguities are
949 @c resolved vary between implementations.
952 @node Whitespace and comments, Other notations, Identifiers, Lexical conventions
953 @section Whitespace and comments
956 @dfn{Whitespace} characters are spaces and newlines.
957 @cindex @w{Whitespace}
958 (Implementations typically provide additional whitespace characters such
959 as tab or page break.) Whitespace is used for improved readability and
960 as necessary to separate tokens from each other, a token being an
961 indivisible lexical unit such as an identifier or number, but is
962 otherwise insignificant. Whitespace may occur between any two tokens,
963 but not within a token. Whitespace may also occur inside a string,
964 where it is significant.
966 A semicolon (@t{;}) indicates the start of a
967 comment. The comment continues to the
970 end of the line on which the semicolon appears. Comments are invisible
971 to Scheme, but the end of the line is visible as whitespace. This
972 prevents a comment from appearing in the middle of an identifier or
978 ;;; The FACT procedure computes the factorial
979 ;;; of a non-negative integer.
983 1 ;Base case: return 1
984 (* n (fact (- n 1))))))
990 @node Other notations, , Whitespace and comments, Lexical conventions
991 @section Other notations
999 For a description of the notations used for numbers, see
1000 section @ref{Numbers}.
1007 These are used in numbers, and may also occur anywhere in an identifier
1008 except as the first character. A delimited plus or minus sign by itself
1009 is also an identifier.
1010 A delimited period (not occurring within a number or identifier) is used
1011 in the notation for pairs (section @pxref{Pairs and lists}), and to indicate a
1012 rest-parameter in a formal parameter list (section @pxref{Procedures}).
1013 A delimited sequence of three successive periods is also an identifier.
1016 Parentheses are used for grouping and to notate lists
1017 (section @pxref{Pairs and lists}).
1020 The single quote character is used to indicate literal data (section @pxref{Literal expressions}).
1023 The backquote character is used to indicate almost-constant
1024 data (section @pxref{Quasiquotation}).
1027 The character comma and the sequence comma at-sign are used in conjunction
1028 with backquote (section @pxref{Quasiquotation}).
1031 The double quote character is used to delimit strings (section @pxref{Strings}).
1034 Backslash is used in the syntax for character constants
1035 (section @pxref{Characters}) and as an escape character within string
1036 constants (section @pxref{Strings}).
1038 @c A box used because \verb is not allowed in command arguments.
1040 @item @w{@t{[ ] @{ @} |}}
1041 Left and right square brackets and curly braces and vertical bar
1042 are reserved for possible future extensions to the language.
1045 Sharp sign is used for a variety of purposes depending on
1046 the character that immediately follows it:
1049 These are the boolean constants (section @pxref{Booleans}).
1052 This introduces a character constant (section @pxref{Characters}).
1055 This introduces a vector constant (section @pxref{Vectors}). Vector constants
1056 are terminated by @t{)} .
1058 @item @t{#e #i #b #o #d #x}
1059 These are used in the notation for numbers (section @pxref{Syntax of numerical constants}).
1067 @node Basic concepts, Expressions, Lexical conventions, top
1068 @chapter Basic concepts
1071 * Variables; syntactic keywords; and regions::
1072 * Disjointness of types::
1073 * External representations::
1075 * Proper tail recursion::
1080 @node Variables; syntactic keywords; and regions, Disjointness of types, Basic concepts, Basic concepts
1081 @section Variables; syntactic keywords; and regions
1086 An identifier may name a type of syntax, or it may name
1087 @cindex @w{identifier}
1088 a location where a value can be stored. An identifier that names a type
1089 of syntax is called a @emph{syntactic keyword}
1090 @cindex @w{syntactic keyword}
1091 and is said to be @emph{bound} to that syntax. An identifier that names a
1092 location is called a @emph{variable} and is said to be
1093 @cindex @w{variable}
1094 @emph{bound} to that location. The set of all visible
1095 bindings in effect at some point in a program is
1097 known as the @emph{environment} in effect at that point. The value
1098 stored in the location to which a variable is bound is called the
1099 variable's value. By abuse of terminology, the variable is sometimes
1100 said to name the value or to be bound to the value. This is not quite
1101 accurate, but confusion rarely results from this practice.
1104 Define ``assigned'' and ``unassigned'' perhaps?
1109 In programs without side effects, one can safely pretend that the
1110 variables are bound directly to the arguments. Or:
1111 In programs without @code{set!}, one can safely pretend that the
1113 variable is bound directly to the value.
1117 Certain expression types are used to create new kinds of syntax
1118 and bind syntactic keywords to those new syntaxes, while other
1119 expression types create new locations and bind variables to those
1120 locations. These expression types are called @emph{binding constructs}.
1122 @cindex @w{binding construct}
1123 Those that bind syntactic keywords are listed in section @ref{Macros}.
1124 The most fundamental of the variable binding constructs is the
1125 @samp{lambda} expression, because all other variable binding constructs
1126 can be explained in terms of @samp{lambda} expressions. The other
1127 variable binding constructs are @samp{let}, @samp{let*}, @samp{letrec},
1128 and @samp{do} expressions (see sections @pxref{Procedures}, @pxref{Binding constructs}, and
1131 @c Note: internal definitions not mentioned here.
1133 Like Algol and Pascal, and unlike most other dialects of Lisp
1134 except for Common Lisp, Scheme is a statically scoped language with
1135 block structure. To each place where an identifier is bound in a program
1136 there corresponds a @dfn{region} of the program text within which
1138 the binding is visible. The region is determined by the particular
1139 binding construct that establishes the binding; if the binding is
1140 established by a @samp{lambda} expression, for example, then its region
1141 is the entire @samp{lambda} expression. Every mention of an identifier
1142 refers to the binding of the identifier that established the
1143 innermost of the regions containing the use. If there is no binding of
1144 the identifier whose region contains the use, then the use refers to the
1145 binding for the variable in the top level environment, if any
1146 (chapters @pxref{Expressions} and @pxref{Standard procedures}); if there is no
1147 binding for the identifier,
1148 it is said to be @dfn{unbound}.
1149 @cindex @w{top level environment}
1154 Mention that some implementations have multiple top level environments?
1159 Pitman sez: needs elaboration in case of @t{(let ...)}
1164 Pitman asks: say something about vars created after scheme starts?
1165 @t{(define x 3) (define (f) x) (define (g) y) (define y 4)}
1166 Clinger replies: The language was explicitly
1167 designed to permit a view in which no variables are created after
1168 Scheme starts. In files, you can scan out the definitions beforehand.
1169 I think we're agreed on the principle that interactive use should
1170 approximate that behavior as closely as possible, though we don't yet
1171 agree on which programming environment provides the best approximation.
1175 @node Disjointness of types, External representations, Variables; syntactic keywords; and regions, Basic concepts
1176 @section Disjointness of types
1180 No object satisfies more than one of the following predicates:
1194 These predicates define the types @emph{boolean}, @emph{pair}, @emph{symbol}, @emph{number}, @emph{char} (or @emph{character}), @emph{string}, @emph{vector}, @emph{port}, and @emph{procedure}. The empty list is a special
1195 object of its own type; it satisfies none of the above predicates.
1207 @cindex @w{empty list}
1211 Although there is a separate boolean type,
1212 any Scheme value can be used as a boolean value for the purpose of a
1213 conditional test. As explained in section @ref{Booleans}, all
1214 values count as true in such a test except for @t{#f}.
1215 @c and possibly the empty list.
1216 @c The only value that is guaranteed to count as
1217 @c false is \schfalse{}. It is explicitly unspecified whether the empty list
1218 @c counts as true or as false.
1219 This report uses the word ``true'' to refer to any
1220 Scheme value except @t{#f}, and the word ``false'' to refer to
1225 @node External representations, Storage model, Disjointness of types, Basic concepts
1226 @section External representations
1230 An important concept in Scheme (and Lisp) is that of the @emph{external
1231 representation} of an object as a sequence of characters. For example,
1232 an external representation of the integer 28 is the sequence of
1233 characters ``@t{28}'', and an external representation of a list consisting
1234 of the integers 8 and 13 is the sequence of characters ``@t{(8 13)}''.
1236 The external representation of an object is not necessarily unique. The
1237 integer 28 also has representations ``@t{#e28.000}'' and ``@t{#x1c}'', and the
1238 list in the previous paragraph also has the representations ``@t{( 08 13
1239 )}'' and ``@t{(8 .@: (13 .@: ()))}'' (see section @pxref{Pairs and lists}).
1241 Many objects have standard external representations, but some, such as
1242 procedures, do not have standard representations (although particular
1243 implementations may define representations for them).
1245 An external representation may be written in a program to obtain the
1246 corresponding object (see @samp{quote}, section @pxref{Literal expressions}).
1248 External representations can also be used for input and output. The
1249 procedure @samp{read} (section @pxref{Input}) parses external
1250 representations, and the procedure @samp{write} (section @pxref{Output})
1251 generates them. Together, they provide an elegant and powerful
1252 input/output facility.
1254 Note that the sequence of characters ``@t{(+ 2 6)}'' is @emph{not} an
1255 external representation of the integer 8, even though it @emph{is} an
1256 expression evaluating to the integer 8; rather, it is an external
1257 representation of a three-element list, the elements of which are the symbol
1258 @t{+} and the integers 2 and 6. Scheme's syntax has the property that
1259 any sequence of characters that is an expression is also the external
1260 representation of some object. This can lead to confusion, since it may
1261 not be obvious out of context whether a given sequence of characters is
1262 intended to denote data or program, but it is also a source of power,
1263 since it facilitates writing programs such as interpreters and
1264 compilers that treat programs as data (or vice versa).
1266 The syntax of external representations of various kinds of objects
1267 accompanies the description of the primitives for manipulating the
1268 objects in the appropriate sections of chapter @ref{Standard procedures}.
1270 @node Storage model, Proper tail recursion, External representations, Basic concepts
1271 @section Storage model
1275 Variables and objects such as pairs, vectors, and strings implicitly
1276 denote locations or sequences of locations. A string, for
1277 @cindex @w{location}
1278 example, denotes as many locations as there are characters in the string.
1279 (These locations need not correspond to a full machine word.) A new value may be
1280 stored into one of these locations using the @t{string-set!} procedure, but
1281 the string continues to denote the same locations as before.
1283 An object fetched from a location, by a variable reference or by
1284 a procedure such as @samp{car}, @samp{vector-ref}, or @samp{string-ref}, is
1285 equivalent in the sense of @code{eqv?}
1287 (section @pxref{Equivalence predicates})
1289 to the object last stored in the location before the fetch.
1291 Every location is marked to show whether it is in use.
1292 No variable or object ever refers to a location that is not in use.
1293 Whenever this report speaks of storage being allocated for a variable
1294 or object, what is meant is that an appropriate number of locations are
1295 chosen from the set of locations that are not in use, and the chosen
1296 locations are marked to indicate that they are now in use before the variable
1297 or object is made to denote them.
1299 In many systems it is desirable for constants (i.e. the values of
1300 @cindex @w{constant}
1301 literal expressions) to reside in read-only-memory. To express this, it is
1302 convenient to imagine that every object that denotes locations is associated
1303 with a flag telling whether that object is mutable or
1305 immutable. In such systems literal constants and the strings
1306 @cindex @w{immutable}
1307 returned by @code{symbol->string} are immutable objects, while all objects
1308 @vindex @w{symbol->string}
1309 created by the other procedures listed in this report are mutable. It is an
1310 error to attempt to store a new value into a location that is denoted by an
1313 @node Proper tail recursion, , Storage model, Basic concepts
1314 @section Proper tail recursion
1318 Implementations of Scheme are required to be
1319 @emph{properly tail-recursive}.
1320 @cindex @w{proper tail recursion}
1321 Procedure calls that occur in certain syntactic
1322 contexts defined below are `tail calls'. A Scheme implementation is
1323 properly tail-recursive if it supports an unbounded number of active
1324 tail calls. A call is @emph{active} if the called procedure may still
1325 return. Note that this includes calls that may be returned from either
1326 by the current continuation or by continuations captured earlier by
1327 @samp{call-with-current-continuation} that are later invoked.
1328 In the absence of captured continuations, calls could
1329 return at most once and the active calls would be those that had not
1331 A formal definition of proper tail recursion can be found
1332 in [propertailrecursion].
1338 Intuitively, no space is needed for an active tail call because the
1339 continuation that is used in the tail call has the same semantics as the
1340 continuation passed to the procedure containing the call. Although an improper
1341 implementation might use a new continuation in the call, a return
1342 to this new continuation would be followed immediately by a return
1343 to the continuation passed to the procedure. A properly tail-recursive
1344 implementation returns to that continuation directly.
1346 Proper tail recursion was one of the central ideas in Steele and
1347 Sussman's original version of Scheme. Their first Scheme interpreter
1348 implemented both functions and actors. Control flow was expressed using
1349 actors, which differed from functions in that they passed their results
1350 on to another actor instead of returning to a caller. In the terminology
1351 of this section, each actor finished with a tail call to another actor.
1353 Steele and Sussman later observed that in their interpreter the code
1354 for dealing with actors was identical to that for functions and thus
1355 there was no need to include both in the language.
1360 A @emph{tail call} is a procedure call that occurs
1361 @cindex @w{tail call}
1362 in a @emph{tail context}. Tail contexts are defined inductively. Note
1363 that a tail context is always determined with respect to a particular lambda
1371 The last expression within the body of a lambda expression,
1372 shown as @r{<tail expression>} below, occurs in a tail context.
1375 @t{(lambda <formals>
1376 <definition>* <expression>* <tail expression>)
1384 If one of the following expressions is in a tail context,
1385 then the subexpressions shown as <tail expression> are in a tail context.
1386 These were derived from rules in the grammar given in
1387 chapter @ref{Formal syntax and semantics} by replacing some occurrences of <expression>
1388 with <tail expression>. Only those rules that contain tail contexts
1393 @t{(if <expression> <tail expression> <tail expression>)
1394 (if <expression> <tail expression>)
1396 (cond <cond clause>+)
1397 (cond <cond clause>* (else <tail sequence>))
1403 (else <tail sequence>))
1405 (and <expression>* <tail expression>)
1406 (or <expression>* <tail expression>)
1408 (let (<binding spec>*) <tail body>)
1409 (let <variable> (<binding spec>*) <tail body>)
1410 (let* (<binding spec>*) <tail body>)
1411 (letrec (<binding spec>*) <tail body>)
1413 (let-syntax (<syntax spec>*) <tail body>)
1414 (letrec-syntax (<syntax spec>*) <tail body>)
1416 (begin <tail sequence>)
1418 (do (<iteration spec>*)
1419 (<test> <tail sequence>)
1424 <cond clause> --> (<test> <tail sequence>)
1425 <case clause> --> ((<datum>*) <tail sequence>)
1427 <tail body> --> <definition>* <tail sequence>
1428 <tail sequence> --> <expression>* <tail expression>
1436 If a @samp{cond} expression is in a tail context, and has a clause of
1437 the form @samp{(@r{<expression1>} => @r{<expression2>})}
1438 then the (implied) call to
1439 the procedure that results from the evaluation of @r{<expression2>} is in a
1440 tail context. @r{<expression2>} itself is not in a tail context.
1446 Certain built-in procedures are also required to perform tail calls.
1447 The first argument passed to @code{apply} and to
1449 @code{call-with-current-continuation}, and the second argument passed to
1450 @vindex @w{call-with-current-continuation}
1451 @code{call-with-values}, must be called via a tail call.
1452 @vindex @w{call-with-values}
1453 Similarly, @code{eval} must evaluate its argument as if it
1455 were in tail position within the @code{eval} procedure.
1458 In the following example the only tail call is the call to @samp{f}.
1459 None of the calls to @samp{g} or @samp{h} are tail calls. The reference to
1460 @samp{x} is in a tail context, but it is not a call and thus is not a
1477 Implementations are allowed, but not required, to
1478 recognize that some non-tail calls, such as the call to @samp{h}
1479 above, can be evaluated as though they were tail calls.
1480 In the example above, the @samp{let} expression could be compiled
1481 as a tail call to @samp{h}. (The possibility of @samp{h} returning
1482 an unexpected number of values can be ignored, because in that
1483 case the effect of the @samp{let} is explicitly unspecified and
1484 implementation-dependent.)
1492 @node Expressions, Program structure, Basic concepts, top
1493 @chapter Expressions
1496 * Primitive expression types::
1497 * Derived expression types::
1503 @c \newcommand{\syntax}{{\em Syntax: }}
1504 @c \newcommand{\semantics}{{\em Semantics: }}
1506 @c [Deleted for R5RS because of multiple-value returns. -RK]
1507 @c A Scheme expression is a construct that returns a value, such as a
1508 @c variable reference, literal, procedure call, or conditional.
1510 Expression types are categorized as @emph{primitive} or @emph{derived}.
1511 Primitive expression types include variables and procedure calls.
1512 Derived expression types are not semantically primitive, but can instead
1513 be defined as macros.
1514 With the exception of @samp{quasiquote}, whose macro definition is complex,
1515 the derived expressions are classified as library features.
1516 Suitable definitions are given in section @ref{Derived expression type}.
1518 @node Primitive expression types, Derived expression types, Expressions, Expressions
1519 @section Primitive expression types
1522 * Variable references::
1523 * Literal expressions::
1532 @node Variable references, Literal expressions, Primitive expression types, Primitive expression types
1533 @subsection Variable references
1537 @deffn {syntax} @r{<variable>}
1540 An expression consisting of a variable
1541 @cindex @w{variable}
1542 (section @pxref{Variables; syntactic keywords; and regions}) is a variable reference. The value of
1543 the variable reference is the value stored in the location to which the
1544 variable is bound. It is an error to reference an
1557 @node Literal expressions, Procedure calls, Variable references, Primitive expression types
1558 @subsection Literal expressions
1563 @deffn {syntax} quote @r{<datum>}
1565 @deffnx {syntax} @t{'}@r{<datum>}
1568 @deffnx {syntax} @r{<constant>}
1571 @samp{(quote @r{<datum>})} evaluates to @r{<datum>}.
1574 may be any external representation of a Scheme object (see
1575 section @pxref{External representations}). This notation is used to include literal
1576 constants in Scheme code.
1582 (quote #(a b c)) ==> #(a b c)
1583 (quote (+ 1 2)) ==> (+ 1 2)
1588 @samp{(quote @r{<datum>})} may be abbreviated as
1589 @t{'}@r{<datum>}. The two notations are equivalent in all
1595 '#(a b c) ==> #(a b c)
1597 '(+ 1 2) ==> (+ 1 2)
1598 '(quote a) ==> (quote a)
1604 Numerical constants, string constants, character constants, and boolean
1605 constants evaluate ``to themselves''; they need not be quoted.
1619 As noted in section @ref{Storage model}, it is an error to alter a constant
1620 (i.e. the value of a literal expression) using a mutation procedure like
1621 @samp{set-car!} or @samp{string-set!}.
1626 @node Procedure calls, Procedures, Literal expressions, Primitive expression types
1627 @subsection Procedure calls
1631 @deffn {syntax} @r{<operator>} @r{<operand1>} @dots{},
1634 A procedure call is written by simply enclosing in parentheses
1635 expressions for the procedure to be called and the arguments to be
1636 passed to it. The operator and operand expressions are evaluated (in an
1637 unspecified order) and the resulting procedure is passed the resulting
1639 @cindex @w{procedure call}
1645 ((if #f + *) 3 4) ==> 12
1650 A number of procedures are available as the values of variables in the
1651 initial environment; for example, the addition and multiplication
1652 procedures in the above examples are the values of the variables @samp{+}
1653 and @samp{*}. New procedures are created by evaluating lambda expressions
1654 (see section @pxref{Procedures}).
1656 At Friedman's request, flushed mention of other ways.
1659 @c or definitions (see section~\ref{define}).
1661 Procedure calls may return any number of values (see @code{values} in
1663 section @pxref{Control features}). With the exception of @samp{values}
1664 the procedures available in the initial environment return one
1665 value or, for procedures such as @samp{apply}, pass on the values returned
1666 by a call to one of their arguments.
1668 Procedure calls are also called @emph{combinations}.
1670 @cindex @w{combination}
1674 @emph{Note:} In contrast to other dialects of Lisp, the order of
1675 evaluation is unspecified, and the operator expression and the operand
1676 expressions are always evaluated with the same evaluation rules.
1683 Although the order of evaluation is otherwise unspecified, the effect of
1684 any concurrent evaluation of the operator and operand expressions is
1685 constrained to be consistent with some sequential order of evaluation.
1686 The order of evaluation may be chosen differently for each procedure call.
1692 @emph{Note:} In many dialects of Lisp, the empty combination, @t{()}, is a legitimate expression. In Scheme, combinations must have at
1693 least one subexpression, so @t{()} is not a syntactically valid
1696 Dybvig: ``it should be obvious from the syntax.''
1704 I think an explanation as to why evaluation order is not specified
1705 should be included. It should not include any reference to parallel
1706 evaluation. Does any existing compiler generate better code because
1707 the evaluation order is unspecified? Clinger: yes: T3, MacScheme v2,
1708 probably MIT Scheme and Chez Scheme. But that's not the main reason
1709 for leaving the order unspecified.
1716 @node Procedures, Conditionals, Procedure calls, Primitive expression types
1717 @subsection Procedures
1722 @deffn {syntax} lambda @r{<formals>} @r{<body>}
1725 @r{<Formals>} should be a formal arguments list as described below,
1726 and @r{<body>} should be a sequence of one or more expressions.
1729 A lambda expression evaluates to a procedure. The environment in
1730 effect when the lambda expression was evaluated is remembered as part of the
1731 procedure. When the procedure is later called with some actual
1732 arguments, the environment in which the lambda expression was evaluated will
1733 be extended by binding the variables in the formal argument list to
1734 fresh locations, the corresponding actual argument values will be stored
1735 in those locations, and the expressions in the body of the lambda expression
1736 will be evaluated sequentially in the extended environment.
1737 The result(s) of the last expression in the body will be returned as
1738 the result(s) of the procedure call.
1742 @t{(lambda (x) (+ x x)) ==> @emph{}a procedure
1743 ((lambda (x) (+ x x)) 4) ==> 8
1745 (define reverse-subtract
1746 (lambda (x y) (- y x)))
1747 (reverse-subtract 7 10) ==> 3
1751 (lambda (y) (+ x y))))
1757 @r{<Formals>} should have one of the following forms:
1764 @t{(@r{<variable1>} @dots{},)}:
1765 The procedure takes a fixed number of arguments; when the procedure is
1766 called, the arguments will be stored in the bindings of the
1767 corresponding variables.
1771 The procedure takes any number of arguments; when the procedure is
1772 called, the sequence of actual arguments is converted into a newly
1773 allocated list, and the list is stored in the binding of the
1777 @t{(@r{<variable1>} @dots{}, @r{<variable_n>} @b{.}
1778 @r{<variable_n+1>})}:
1779 If a space-delimited period precedes the last variable, then
1780 the procedure takes n or more arguments, where n is the
1781 number of formal arguments before the period (there must
1783 The value stored in the binding of the last variable will be a
1785 list of the actual arguments left over after all the other actual
1786 arguments have been matched up against the other formal arguments.
1791 It is an error for a @r{<variable>} to appear more than once in
1796 @t{((lambda x x) 3 4 5 6) ==> (3 4 5 6)
1797 ((lambda (x y . z) z)
1803 Each procedure created as the result of evaluating a lambda expression is
1804 (conceptually) tagged
1805 with a storage location, in order to make @code{eqv?} and
1807 @code{eq?} work on procedures (see section @pxref{Equivalence predicates}).
1813 @node Conditionals, Assignments, Procedures, Primitive expression types
1814 @subsection Conditionals
1818 @deffn {syntax} if @r{<test>} @r{<consequent>} @r{<alternate>}
1819 @deffnx {syntax} if @r{<test>} @r{<consequent>}
1820 @c \/ if hyper = italic
1823 @r{<Test>}, @r{<consequent>}, and @r{<alternate>} may be arbitrary
1827 An @samp{if} expression is evaluated as follows: first,
1828 @r{<test>} is evaluated. If it yields a true value (see
1830 section @pxref{Booleans}), then @r{<consequent>} is evaluated and
1831 its value(s) is(are) returned. Otherwise @r{<alternate>} is evaluated and its
1832 value(s) is(are) returned. If @r{<test>} yields a false value and no
1833 @r{<alternate>} is specified, then the result of the expression is
1838 @t{(if (> 3 2) 'yes 'no) ==> yes
1839 (if (> 2 3) 'yes 'no) ==> no
1850 @node Assignments, , Conditionals, Primitive expression types
1851 @subsection Assignments
1856 @deffn {syntax} set! @r{<variable>} @r{<expression>}
1858 @r{<Expression>} is evaluated, and the resulting value is stored in
1859 the location to which @r{<variable>} is bound. @r{<Variable>} must
1860 be bound either in some region enclosing the @samp{set!} expression
1862 or at top level. The result of the @samp{set!} expression is
1869 (set! x 4) ==> @emph{unspecified}
1878 @node Derived expression types, Macros, Primitive expression types, Expressions
1879 @section Derived expression types
1883 * Binding constructs::
1886 * Delayed evaluation::
1892 The constructs in this section are hygienic, as discussed in
1893 section @ref{Macros}.
1894 For reference purposes, section @ref{Derived expression type} gives macro definitions
1895 that will convert most of the constructs described in this section
1896 into the primitive constructs described in the previous section.
1899 Mention that no definition of backquote is provided?
1903 @node Conditional, Binding constructs, Derived expression types, Derived expression types
1904 @subsection Conditionals
1908 @deffn {library syntax} cond <clause1> <clause2> @dots{},
1911 Each @r{<clause>} should be of the form
1914 @t{(@r{<test>} @r{<expression1>} @dots{},)
1918 where @r{<test>} is any expression. Alternatively, a @r{<clause>} may be
1922 @t{(@r{<test>} => @r{<expression>})
1926 The last @r{<clause>} may be
1927 an ``else clause,'' which has the form
1930 @t{(else @r{<expression1>} @r{<expression2>} @dots{},)@r{.}
1940 A @samp{cond} expression is evaluated by evaluating the @r{<test>}
1941 expressions of successive @r{<clause>}s in order until one of them
1942 evaluates to a true value (see
1944 section @pxref{Booleans}). When a @r{<test>} evaluates to a true
1945 value, then the remaining @r{<expression>}s in its @r{<clause>} are
1946 evaluated in order, and the result(s) of the last @r{<expression>} in the
1947 @r{<clause>} is(are) returned as the result(s) of the entire @samp{cond}
1948 expression. If the selected @r{<clause>} contains only the
1949 @r{<test>} and no @r{<expression>}s, then the value of the
1950 @r{<test>} is returned as the result. If the selected @r{<clause>} uses the
1951 @code{=>} alternate form, then the @r{<expression>} is evaluated.
1953 Its value must be a procedure that accepts one argument; this procedure is then
1954 called on the value of the @r{<test>} and the value(s) returned by this
1955 procedure is(are) returned by the @samp{cond} expression.
1956 If all @r{<test>}s evaluate
1957 to false values, and there is no else clause, then the result of
1958 the conditional expression is unspecified; if there is an else
1959 clause, then its @r{<expression>}s are evaluated, and the value(s) of
1960 the last one is(are) returned.
1964 @t{(cond ((> 3 2) 'greater)
1965 ((< 3 2) 'less)) ==> greater
1967 (cond ((> 3 3) 'greater)
1969 (else 'equal)) ==> equal
1971 (cond ((assv 'b '((a 1) (b 2))) => cadr)
1982 @deffn {library syntax} case @r{<key>} <clause1> <clause2> @dots{},
1985 @r{<Key>} may be any expression. Each @r{<clause>} should have
1989 @t{((@r{<datum1>} @dots{},) @r{<expression1>} @r{<expression2>} @dots{},)@r{,}
1993 where each @r{<datum>} is an external representation of some object.
1994 All the @r{<datum>}s must be distinct.
1995 The last @r{<clause>} may be an ``else clause,'' which has the form
1998 @t{(else @r{<expression1>} @r{<expression2>} @dots{},)@r{.}
2006 A @samp{case} expression is evaluated as follows. @r{<Key>} is
2007 evaluated and its result is compared against each @r{<datum>}. If the
2008 result of evaluating @r{<key>} is equivalent (in the sense of
2009 @samp{eqv?}; see section @pxref{Equivalence predicates}) to a @r{<datum>}, then the
2010 expressions in the corresponding @r{<clause>} are evaluated from left
2011 to right and the result(s) of the last expression in the @r{<clause>} is(are)
2012 returned as the result(s) of the @samp{case} expression. If the result of
2013 evaluating @r{<key>} is different from every @r{<datum>}, then if
2014 there is an else clause its expressions are evaluated and the
2015 result(s) of the last is(are) the result(s) of the @samp{case} expression;
2016 otherwise the result of the @samp{case} expression is unspecified.
2022 ((1 4 6 8 9) 'composite)) ==> composite
2025 ((b) 'b)) ==> @emph{unspecified}
2027 ((a e i o u) 'vowel)
2029 (else 'consonant)) ==> consonant
2038 @deffn {library syntax} and <test1> @dots{},
2040 The @r{<test>} expressions are evaluated from left to right, and the
2041 value of the first expression that evaluates to a false value (see
2042 section @pxref{Booleans}) is returned. Any remaining expressions
2043 are not evaluated. If all the expressions evaluate to true values, the
2044 value of the last expression is returned. If there are no expressions
2045 then @t{#t} is returned.
2049 @t{(and (= 2 2) (> 2 1)) ==> #t
2050 (and (= 2 2) (< 2 1)) ==> #f
2051 (and 1 2 'c '(f g)) ==> (f g)
2061 @deffn {library syntax} or <test1> @dots{},
2063 The @r{<test>} expressions are evaluated from left to right, and the value of the
2064 first expression that evaluates to a true value (see
2065 section @pxref{Booleans}) is returned. Any remaining expressions
2066 are not evaluated. If all expressions evaluate to false values, the
2067 value of the last expression is returned. If there are no
2068 expressions then @t{#f} is returned.
2072 @t{(or (= 2 2) (> 2 1)) ==> #t
2073 (or (= 2 2) (< 2 1)) ==> #t
2074 (or #f #f #f) ==> #f
2075 (or (memq 'b '(a b c))
2084 @node Binding constructs, Sequencing, Conditional, Derived expression types
2085 @subsection Binding constructs
2088 The three binding constructs @samp{let}, @samp{let*}, and @samp{letrec}
2089 give Scheme a block structure, like Algol 60. The syntax of the three
2090 constructs is identical, but they differ in the regions they establish
2092 for their variable bindings. In a @samp{let} expression, the initial
2093 values are computed before any of the variables become bound; in a
2094 @samp{let*} expression, the bindings and evaluations are performed
2095 sequentially; while in a @samp{letrec} expression, all the bindings are in
2096 effect while their initial values are being computed, thus allowing
2097 mutually recursive definitions.
2100 @deffn {library syntax} let @r{<bindings>} @r{<body>}
2103 @r{<Bindings>} should have the form
2106 @t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,}
2110 where each @r{<init>} is an expression, and @r{<body>} should be a
2111 sequence of one or more expressions. It is
2112 an error for a @r{<variable>} to appear more than once in the list of variables
2116 The @r{<init>}s are evaluated in the current environment (in some
2117 unspecified order), the @r{<variable>}s are bound to fresh locations
2118 holding the results, the @r{<body>} is evaluated in the extended
2119 environment, and the value(s) of the last expression of @r{<body>}
2120 is(are) returned. Each binding of a @r{<variable>} has @r{<body>} as its
2126 @t{(let ((x 2) (y 3))
2137 See also named @samp{let}, section @ref{Iteration}.
2143 @deffn {library syntax} let* @r{<bindings>} @r{<body>}
2147 @r{<Bindings>} should have the form
2150 @t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,}
2154 and @r{<body>} should be a sequence of
2155 one or more expressions.
2158 @samp{Let*} is similar to @samp{let}, but the bindings are performed
2159 sequentially from left to right, and the region of a binding indicated
2161 by @samp{(@r{<variable>} @r{<init>})} is that part of the @samp{let*}
2162 expression to the right of the binding. Thus the second binding is done
2163 in an environment in which the first binding is visible, and so on.
2167 @t{(let ((x 2) (y 3))
2179 @deffn {library syntax} letrec @r{<bindings>} @r{<body>}
2182 @r{<Bindings>} should have the form
2185 @t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,}
2189 and @r{<body>} should be a sequence of
2190 one or more expressions. It is an error for a @r{<variable>} to appear more
2191 than once in the list of variables being bound.
2194 The @r{<variable>}s are bound to fresh locations holding undefined
2195 values, the @r{<init>}s are evaluated in the resulting environment (in
2196 some unspecified order), each @r{<variable>} is assigned to the result
2197 of the corresponding @r{<init>}, the @r{<body>} is evaluated in the
2198 resulting environment, and the value(s) of the last expression in
2199 @r{<body>} is(are) returned. Each binding of a @r{<variable>} has the
2200 entire @samp{letrec} expression as its region, making it possible to
2202 define mutually recursive procedures.
2222 One restriction on @samp{letrec} is very important: it must be possible
2223 to evaluate each @r{<init>} without assigning or referring to the value of any
2224 @r{<variable>}. If this restriction is violated, then it is an error. The
2225 restriction is necessary because Scheme passes arguments by value rather than by
2226 name. In the most common uses of @samp{letrec}, all the @r{<init>}s are
2227 lambda expressions and the restriction is satisfied automatically.
2229 @c \todo{use or uses? --- Jinx.}
2234 @node Sequencing, Iteration, Binding constructs, Derived expression types
2235 @subsection Sequencing
2239 @deffn {library syntax} begin <expression1> <expression2> @dots{},
2241 The @r{<expression>}s are evaluated sequentially from left to right,
2242 and the value(s) of the last @r{<expression>} is(are) returned. This
2243 expression type is used to sequence side effects such as input and
2253 (begin (display "4 plus 1 equals ")
2254 (display (+ 4 1))) ==> @emph{unspecified}
2255 @emph{and prints} 4 plus 1 equals 5
2263 @node Iteration, Delayed evaluation, Sequencing, Derived expression types
2264 @subsection Iteration
2271 @deffn {library syntax} do ((@r{<variable1>} @r{<init1>} @r{<step1>}) @dots{}) (@r{<test>} @r{<expression>} @dots{}) @r{<command>} @dots{}
2274 @samp{Do} is an iteration construct. It specifies a set of variables to
2275 be bound, how they are to be initialized at the start, and how they are
2276 to be updated on each iteration. When a termination condition is met,
2277 the loop exits after evaluating the @r{<expression>}s.
2279 @samp{Do} expressions are evaluated as follows:
2280 The @r{<init>} expressions are evaluated (in some unspecified order),
2281 the @r{<variable>}s are bound to fresh locations, the results of the
2282 @r{<init>} expressions are stored in the bindings of the
2283 @r{<variable>}s, and then the iteration phase begins.
2285 Each iteration begins by evaluating @r{<test>}; if the result is
2286 false (see section @pxref{Booleans}), then the @r{<command>}
2287 expressions are evaluated in order for effect, the @r{<step>}
2288 expressions are evaluated in some unspecified order, the
2289 @r{<variable>}s are bound to fresh locations, the results of the
2290 @r{<step>}s are stored in the bindings of the
2291 @r{<variable>}s, and the next iteration begins.
2293 If @r{<test>} evaluates to a true value, then the
2294 @r{<expression>}s are evaluated from left to right and the value(s) of
2295 the last @r{<expression>} is(are) returned. If no @r{<expression>}s
2296 are present, then the value of the @samp{do} expression is unspecified.
2298 The region of the binding of a @r{<variable>}
2300 consists of the entire @samp{do} expression except for the @r{<init>}s.
2301 It is an error for a @r{<variable>} to appear more than once in the
2302 list of @samp{do} variables.
2304 A @r{<step>} may be omitted, in which case the effect is the
2305 same as if @samp{(@r{<variable>} @r{<init>} @r{<variable>})} had
2306 been written instead of @samp{(@r{<variable>} @r{<init>})}.
2310 @t{(do ((vec (make-vector 5))
2313 (vector-set! vec i i)) ==> #(0 1 2 3 4)
2315 (let ((x '(1 3 5 7 9)))
2317 (sum 0 (+ sum (car x))))
2318 ((null? x) sum))) ==> 25
2327 @deffn {library syntax} let @r{<variable>} @r{<bindings>} @r{<body>}
2330 ``Named @samp{let}'' is a variant on the syntax of @code{let} which provides
2332 a more general looping construct than @samp{do} and may also be used to express
2334 It has the same syntax and semantics as ordinary @samp{let}
2335 except that @r{<variable>} is bound within @r{<body>} to a procedure
2336 whose formal arguments are the bound variables and whose body is
2337 @r{<body>}. Thus the execution of @r{<body>} may be repeated by
2338 invoking the procedure named by @r{<variable>}.
2340 @c | <-- right margin
2343 @t{(let loop ((numbers '(3 -2 1 6 -5))
2346 (cond ((null? numbers) (list nonneg neg))
2347 ((>= (car numbers) 0)
2349 (cons (car numbers) nonneg)
2351 ((< (car numbers) 0)
2354 (cons (car numbers) neg)))))
2355 ==> ((6 1 3) (-5 -2))
2363 @node Delayed evaluation, Quasiquotation, Iteration, Derived expression types
2364 @subsection Delayed evaluation
2368 @deffn {library syntax} delay @r{<expression>}
2375 The @samp{delay} construct is used together with the procedure @code{force} to
2377 implement @dfn{lazy evaluation} or @dfn{call by need}.
2378 @cindex @w{call by need}
2379 @cindex @w{lazy evaluation}
2380 @t{(delay @r{<expression>})} returns an object called a
2381 @dfn{promise} which at some point in the future may be asked (by
2383 the @samp{force} procedure)
2385 Bartley's white lie; OK?
2388 @r{<expression>}, and deliver the resulting value.
2389 The effect of @r{<expression>} returning multiple values
2392 See the description of @samp{force} (section @pxref{Control features}) for a
2393 more complete description of @samp{delay}.
2398 @node Quasiquotation, , Delayed evaluation, Derived expression types
2399 @subsection Quasiquotation
2404 @deffn {syntax} quasiquote @r{<qq template>}
2406 @deffnx {syntax} @t{`}@r{<qq template>}
2409 ``Backquote'' or ``quasiquote'' expressions are useful
2410 @cindex @w{backquote}
2411 for constructing a list or vector structure when most but not all of the
2412 desired structure is known in advance. If no
2413 commas appear within the @r{<qq template>}, the result of
2416 @t{`}@r{<qq template>} is equivalent to the result of evaluating
2417 @t{'}@r{<qq template>}. If a comma appears within the
2419 @r{<qq template>}, however, the expression following the comma is
2420 evaluated (``unquoted'') and its result is inserted into the structure
2421 instead of the comma and the expression. If a comma appears followed
2422 immediately by an at-sign (@@), then the following
2424 expression must evaluate to a list; the opening and closing parentheses
2425 of the list are then ``stripped away'' and the elements of the list are
2426 inserted in place of the comma at-sign expression sequence. A comma
2427 at-sign should only appear within a list or vector @r{<qq template>}.
2429 @c struck: "(in the sense of {\cf equal?})" after "equivalent"
2433 @t{`(list ,(+ 1 2) 4) ==> (list 3 4)
2434 (let ((name 'a)) `(list ,name ',name))
2435 ==> (list a (quote a))
2436 `(a ,(+ 1 2) ,@@(map abs '(4 -5 6)) b)
2438 `((@samp{foo} ,(- 10 3)) ,@@(cdr '(c)) . ,(car '(cons)))
2439 ==> ((foo 7) . cons)
2440 `#(10 5 ,(sqrt 4) ,@@(map sqrt '(16 9)) 8)
2446 Quasiquote forms may be nested. Substitutions are made only for
2447 unquoted components appearing at the same nesting level
2448 as the outermost backquote. The nesting level increases by one inside
2449 each successive quasiquotation, and decreases by one inside each
2454 @t{`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f)
2455 ==> (a `(b ,(+ 1 2) ,(foo 4 d) e) f)
2458 `(a `(b ,,name1 ,',name2 d) e))
2459 ==> (a `(b ,x ,'y d) e)
2465 @t{`}@r{<qq template>} and @t{(quasiquote @r{<qq template>})}
2466 are identical in all respects.
2467 @samp{,@r{<expression>}} is identical to @samp{(unquote @r{<expression>})},
2469 @samp{,@@@r{<expression>}} is identical to @samp{(unquote-splicing @r{<expression>})}.
2470 The external syntax generated by @code{write} for two-element lists whose
2472 car is one of these symbols may vary between implementations.
2478 @t{(quasiquote (list (unquote (+ 1 2)) 4))
2480 '(quasiquote (list (unquote (+ 1 2)) 4))
2481 ==> `(list ,(+ 1 2) 4)
2482 @emph{}i.e., (quasiquote (list (unquote (+ 1 2)) 4))
2487 Unpredictable behavior can result if any of the symbols
2488 @code{quasiquote}, @code{unquote}, or @code{unquote-splicing} appear in
2489 @vindex @w{unquote-splicing}
2491 @vindex @w{quasiquote}
2492 positions within a @r{<qq template>} otherwise than as described above.
2496 @node Macros, , Derived expression types, Expressions
2500 * Binding constructs for syntactic keywords::
2501 * Pattern language::
2506 Scheme programs can define and use new derived expression types,
2507 called @emph{macros}.
2509 Program-defined expression types have the syntax
2513 (@r{<keyword>} @r{<datum>} ...)
2517 where @r{<keyword>} is an identifier that uniquely determines the
2518 expression type. This identifier is called the @emph{syntactic
2519 keyword}, or simply @emph{keyword}, of the macro. The
2520 @cindex @w{macro keyword}
2522 @cindex @w{syntactic keyword}
2523 number of the @r{<datum>}s, and their syntax, depends on the
2526 Each instance of a macro is called a @emph{use}
2527 @cindex @w{macro use}
2529 The set of rules that specifies
2530 how a use of a macro is transcribed into a more primitive expression
2531 is called the @emph{transformer}
2532 @cindex @w{macro transformer}
2535 The macro definition facility consists of two parts:
2542 A set of expressions used to establish that certain identifiers
2543 are macro keywords, associate them with macro transformers, and control
2544 the scope within which a macro is defined, and
2547 a pattern language for specifying macro transformers.
2552 The syntactic keyword of a macro may shadow variable bindings, and local
2553 variable bindings may shadow keyword bindings. All macros
2555 defined using the pattern language are ``hygienic'' and ``referentially
2556 transparent'' and thus preserve Scheme's lexical scoping [Kohlbecker86], [
2557 hygienic], [Bawden88], [macrosthatwork], [syntacticabstraction]:
2559 @cindex @w{hygienic}
2561 @cindex @w{referentially transparent}
2570 If a macro transformer inserts a binding for an identifier
2571 (variable or keyword), the identifier will in effect be renamed
2572 throughout its scope to avoid conflicts with other identifiers.
2573 Note that a @code{define} at top level may or may not introduce a binding;
2574 see section @ref{Definitions}.
2577 If a macro transformer inserts a free reference to an
2578 identifier, the reference refers to the binding that was visible
2579 where the transformer was specified, regardless of any local
2580 bindings that may surround the use of the macro.
2587 @c The low-level facility permits non-hygienic macros to be written,
2588 @c and may be used to implement the high-level pattern language.
2590 @c The fourth section describes some features that would make the
2591 @c low-level macro facility easier to use directly.
2593 @node Binding constructs for syntactic keywords, Pattern language, Macros, Macros
2594 @subsection Binding constructs for syntactic keywords
2598 @samp{Let-syntax} and @samp{letrec-syntax} are
2599 analogous to @samp{let} and @samp{letrec}, but they bind
2600 syntactic keywords to macro transformers instead of binding variables
2601 to locations that contain values. Syntactic keywords may also be
2602 bound at top level; see section @ref{Syntax definitions}.
2605 @deffn {syntax} let-syntax @r{<bindings>} @r{<body>}
2608 @r{<Bindings>} should have the form
2611 @t{((@r{<keyword>} @r{<transformer spec>}) @dots{},)
2615 Each @r{<keyword>} is an identifier,
2616 each @r{<transformer spec>} is an instance of @samp{syntax-rules}, and
2617 @r{<body>} should be a sequence of one or more expressions. It is an error
2618 for a @r{<keyword>} to appear more than once in the list of keywords
2622 The @r{<body>} is expanded in the syntactic environment
2623 obtained by extending the syntactic environment of the
2624 @samp{let-syntax} expression with macros whose keywords are
2625 the @r{<keyword>}s, bound to the specified transformers.
2626 Each binding of a @r{<keyword>} has @r{<body>} as its region.
2630 @t{(let-syntax ((when (syntax-rules ()
2631 ((when test stmt1 stmt2 ...)
2636 (when if (set! if 'now))
2640 (let-syntax ((m (syntax-rules () ((m) x))))
2650 @deffn {syntax} letrec-syntax @r{<bindings>} @r{<body>}
2653 Same as for @samp{let-syntax}.
2656 The @r{<body>} is expanded in the syntactic environment obtained by
2657 extending the syntactic environment of the @samp{letrec-syntax}
2658 expression with macros whose keywords are the
2659 @r{<keyword>}s, bound to the specified transformers.
2660 Each binding of a @r{<keyword>} has the @r{<bindings>}
2661 as well as the @r{<body>} within its region,
2662 so the transformers can
2663 transcribe expressions into uses of the macros
2664 introduced by the @samp{letrec-syntax} expression.
2669 ((my-or (syntax-rules ()
2676 (my-or e2 ...)))))))
2692 @node Pattern language, , Binding constructs for syntactic keywords, Macros
2693 @subsection Pattern language
2697 A @r{<transformer spec>} has the following form:
2700 @deffn {} syntax-rules @r{<literals>} @r{<syntax rule>} @dots{},
2703 @r{<Literals>} is a list of identifiers and each @r{<syntax rule>}
2704 should be of the form
2707 @t{(@r{<pattern>} @r{<template>})
2711 The @r{<pattern>} in a @r{<syntax rule>} is a list @r{<pattern>}
2712 that begins with the keyword for the macro.
2714 A @r{<pattern>} is either an identifier, a constant, or one of the
2718 @t{(@r{<pattern>} @dots{})
2719 (@r{<pattern>} @r{<pattern>} @dots{} . @r{<pattern>})
2720 (@r{<pattern>} @dots{} @r{<pattern>} @r{<ellipsis>})
2721 #(@r{<pattern>} @dots{})
2722 #(@r{<pattern>} @dots{} @r{<pattern>} @r{<ellipsis>})
2726 and a template is either an identifier, a constant, or one of the following
2729 @t{(@r{<element>} @dots{})
2730 (@r{<element>} @r{<element>} @dots{} . @r{<template>})
2731 #(@r{<element>} @dots{})
2735 where an @r{<element>} is a @r{<template>} optionally
2736 followed by an @r{<ellipsis>} and
2737 an @r{<ellipsis>} is the identifier ``@samp{...}'' (which cannot be used as
2738 an identifier in either a template or a pattern).
2741 @emph{Semantics:} An instance of @samp{syntax-rules} produces a new macro
2742 transformer by specifying a sequence of hygienic rewrite rules. A use
2743 of a macro whose keyword is associated with a transformer specified by
2744 @samp{syntax-rules} is matched against the patterns contained in the
2745 @r{<syntax rule>}s, beginning with the leftmost @r{<syntax rule>}.
2746 When a match is found, the macro use is transcribed hygienically
2747 according to the template.
2749 An identifier that appears in the pattern of a @r{<syntax rule>} is
2750 a @emph{pattern variable}, unless it is the keyword that begins the pattern,
2751 is listed in @r{<literals>}, or is the identifier ``@samp{...}''.
2752 Pattern variables match arbitrary input elements and
2753 are used to refer to elements of the input in the template. It is an
2754 error for the same pattern variable to appear more than once in a
2757 The keyword at the beginning of the pattern in a
2758 @r{<syntax rule>} is not involved in the matching and
2759 is not considered a pattern variable or literal identifier.
2764 The scope of the keyword is determined by the expression or syntax
2765 definition that binds it to the associated macro transformer.
2766 If the keyword were a pattern variable or literal
2768 the template that follows the pattern would be within its scope
2769 regardless of whether the keyword were bound by @samp{let-syntax}
2770 or by @samp{letrec-syntax}.
2774 Identifiers that appear in @r{<literals>} are interpreted as literal
2775 identifiers to be matched against corresponding subforms of the input.
2777 in the input matches a literal identifier if and only if it is an
2779 and either both its occurrence in the macro expression and its
2780 occurrence in the macro definition have the same lexical binding, or
2781 the two identifiers are equal and both have no lexical binding.
2783 @c [Bill Rozas suggested the term "noise word" for these literal
2784 @c identifiers, but in their most interesting uses, such as a setf
2785 @c macro, they aren't noise words at all. -- Will]
2787 A subpattern followed by @samp{...} can match zero or more elements of the
2788 input. It is an error for @samp{...} to appear in @r{<literals>}.
2789 Within a pattern the identifier @samp{...} must follow the last element of
2790 a nonempty sequence of subpatterns.
2792 More formally, an input form F matches a pattern P if and only if:
2799 P is a non-literal identifier; or
2802 P is a literal identifier and F is an identifier with the same
2806 P is a list @samp{(P_1 @dots{} P_n)} and F is a
2808 forms that match P_1 through P_n, respectively; or
2811 P is an improper list
2812 @samp{(P_1 P_2 @dots{} P_n . P_n+1)}
2814 improper list of n or more forms that match P_1 through P_n,
2815 respectively, and whose nth ``cdr'' matches P_n+1; or
2819 @samp{(P_1 @dots{} P_n P_n+1 <ellipsis>)}
2820 where <ellipsis> is the identifier @samp{...}
2822 a proper list of at least n forms, the first n of which match
2823 P_1 through P_n, respectively, and each remaining element of F
2827 P is a vector of the form @samp{#(P_1 @dots{} P_n)}
2829 of n forms that match P_1 through P_n; or
2833 @samp{#(P_1 @dots{} P_n P_n+1 <ellipsis>)}
2834 where <ellipsis> is the identifier @samp{...}
2835 and F is a vector of n
2836 or more forms the first n of which match
2837 P_1 through P_n, respectively, and each remaining element of F
2841 P is a datum and F is equal to P in the sense of
2842 the @samp{equal?} procedure.
2847 It is an error to use a macro keyword, within the scope of its
2848 binding, in an expression that does not match any of the patterns.
2850 When a macro use is transcribed according to the template of the
2851 matching @r{<syntax rule>}, pattern variables that occur in the
2852 template are replaced by the subforms they match in the input.
2853 Pattern variables that occur in subpatterns followed by one or more
2854 instances of the identifier
2855 @samp{...} are allowed only in subtemplates that are
2856 followed by as many instances of @samp{...}.
2857 They are replaced in the
2858 output by all of the subforms they match in the input, distributed as
2859 indicated. It is an error if the output cannot be built up as
2862 @c %% This description of output construction is very vague. It should
2863 @c %% probably be formalized, but that is not easy...
2865 Identifiers that appear in the template but are not pattern variables
2867 @samp{...} are inserted into the output as literal identifiers. If a
2868 literal identifier is inserted as a free identifier then it refers to the
2869 binding of that identifier within whose scope the instance of
2870 @samp{syntax-rules} appears.
2871 If a literal identifier is inserted as a bound identifier then it is
2872 in effect renamed to prevent inadvertent captures of free identifiers.
2874 As an example, if @code{let} and @code{cond} are defined as in
2877 section @ref{Derived expression type} then they are hygienic (as required) and
2878 the following is not an error.
2883 (cond (#t => 'ok))) ==> ok
2888 The macro transformer for @samp{cond} recognizes @samp{=>}
2889 as a local variable, and hence an expression, and not as the
2890 top-level identifier @samp{=>}, which the macro transformer treats
2891 as a syntactic keyword. Thus the example expands into
2896 (if #t (begin => 'ok)))
2907 (if temp ('ok temp))))
2912 which would result in an invalid procedure call.
2920 @node Program structure, Standard procedures, Expressions, top
2921 @chapter Program structure
2926 * Syntax definitions::
2931 @node Programs, Definitions, Program structure, Program structure
2935 A Scheme program consists of a sequence of expressions, definitions,
2936 and syntax definitions.
2937 Expressions are described in chapter @ref{Expressions};
2938 definitions and syntax definitions are the subject of the rest of the
2941 Programs are typically stored in files or entered interactively to a
2942 running Scheme system, although other paradigms are possible;
2943 questions of user interface lie outside the scope of this report.
2944 (Indeed, Scheme would still be useful as a notation for expressing
2945 computational methods even in the absence of a mechanical
2948 Definitions and syntax definitions occurring at the top level of a program
2951 They cause bindings to be created in the top level
2952 environment or modify the value of existing top-level bindings.
2953 Expressions occurring at the top level of a program are
2954 interpreted imperatively; they are executed in order when the program is
2955 invoked or loaded, and typically perform some kind of initialization.
2957 At the top level of a program @t{(begin @r{<form1>} @dots{},)} is
2958 equivalent to the sequence of expressions, definitions, and syntax definitions
2959 that form the body of the @code{begin}.
2963 Cromarty, etc.: disclaimer about top level?
2967 @node Definitions, Syntax definitions, Programs, Program structure
2968 @section Definitions
2971 * Top level definitions::
2972 * Internal definitions::
2977 Definitions are valid in some, but not all, contexts where expressions
2978 are allowed. They are valid only at the top level of a @r{<program>}
2979 and at the beginning of a @r{<body>}.
2981 @cindex @w{definition}
2983 A definition should have one of the following forms:
2991 @item @t{(define @r{<variable>} @r{<expression>})}
2993 @item @t{(define (@r{<variable>} @r{<formals>}) @r{<body>})}
2995 @r{<Formals>} should be either a
2996 sequence of zero or more variables, or a sequence of one or more
2997 variables followed by a space-delimited period and another variable (as
2998 in a lambda expression). This form is equivalent to
3002 (define @r{<variable>}
3003 (lambda (@r{<formals>}) @r{<body>}))@r{.}
3008 @item @t{(define (@r{<variable>} .@: @r{<formal>}) @r{<body>})}
3010 @r{<Formal>} should be a single
3011 variable. This form is equivalent to
3015 (define @r{<variable>}
3016 (lambda @r{<formal>} @r{<body>}))@r{.}
3025 @node Top level definitions, Internal definitions, Definitions, Definitions
3026 @subsection Top level definitions
3029 At the top level of a program, a definition
3033 (define @r{<variable>} @r{<expression>})
3037 has essentially the same effect as the assignment expression
3041 (set! @r{<variable>} @r{<expression>})
3045 if @r{<variable>} is bound. If @r{<variable>} is not bound,
3046 however, then the definition will bind @r{<variable>} to a new
3047 location before performing the assignment, whereas it would be an error
3048 to perform a @samp{set!} on an unbound variable.
3055 (lambda (x) (+ x 3)))
3058 (first '(1 2)) ==> 1
3063 Some implementations of Scheme use an initial environment in
3064 which all possible variables are bound to locations, most of
3065 which contain undefined values. Top level definitions in
3066 such an implementation are truly equivalent to assignments.
3069 Rozas: equal time for opposition semantics?
3074 @node Internal definitions, , Top level definitions, Definitions
3075 @subsection Internal definitions
3079 Definitions may occur at the
3080 beginning of a @r{<body>} (that is, the body of a @code{lambda},
3082 @code{let}, @code{let*}, @code{letrec}, @code{let-syntax}, or @code{letrec-syntax}
3083 @vindex @w{letrec-syntax}
3084 @vindex @w{let-syntax}
3088 expression or that of a definition of an appropriate form).
3089 Such definitions are known as @emph{internal definitions} as opposed to the top level definitions described above.
3090 @cindex @w{internal definition}
3091 The variable defined by an internal definition is local to the
3092 @r{<body>}. That is, @r{<variable>} is bound rather than assigned,
3093 and the region of the binding is the entire @r{<body>}. For example,
3099 (define foo (lambda (y) (bar x y)))
3100 (define bar (lambda (a b) (+ (* a b) a)))
3101 (foo (+ x 3))) ==> 45
3106 A @r{<body>} containing internal definitions can always be converted
3107 into a completely equivalent @samp{letrec} expression. For example, the
3108 @samp{let} expression in the above example is equivalent to
3114 (letrec ((foo (lambda (y) (bar x y)))
3115 (bar (lambda (a b) (+ (* a b) a))))
3121 Just as for the equivalent @samp{letrec} expression, it must be
3122 possible to evaluate each @r{<expression>} of every internal
3123 definition in a @r{<body>} without assigning or referring to
3124 the value of any @r{<variable>} being defined.
3126 Wherever an internal definition may occur
3127 @t{(begin @r{<definition1>} @dots{},)}
3128 is equivalent to the sequence of definitions
3129 that form the body of the @code{begin}.
3132 @node Syntax definitions, , Definitions, Program structure
3133 @section Syntax definitions
3136 Syntax definitions are valid only at the top level of a @r{<program>}.
3138 @cindex @w{syntax definition}
3139 They have the following form:
3140 @cindex @w{define-syntax}
3142 @t{(define-syntax @r{<keyword>} @r{<transformer spec>})}
3144 @r{<Keyword>} is an identifier, and
3145 the @r{<transformer spec>} should be an instance of @code{syntax-rules}.
3146 @vindex @w{syntax-rules}
3147 The top-level syntactic environment is extended by binding the
3148 @r{<keyword>} to the specified transformer.
3150 There is no @samp{define-syntax} analogue of internal definitions.
3152 @c [Rationale flushed because it may or may not be true and isn't the
3153 @c real rationale anyway. -RK]
3154 @c \begin{rationale}
3155 @c As discussed below, the syntax and scope rules for syntax definitions
3156 @c can give rise to syntactic ambiguities when syntactic keywords are
3158 @c Further ambiguities would arise if {\cf define-syntax}
3159 @c were permitted at the beginning of a \meta{body}, with scope
3160 @c rules analogous to those for internal definitions.
3163 @c It is an error for a program to contain more than one top-level
3164 @c \meta{definition} or \meta{syntax definition} of any identifier.
3166 @c [I flushed this because it isn't an error for a program to
3167 @c contain more than one top-level definition of an identifier,
3168 @c and I didn't want to introduce any gratuitous incompatibilities
3169 @c with the existing Scheme language. -- Will]
3171 Although macros may expand into definitions and syntax definitions in
3172 any context that permits them, it is an error for a definition or syntax
3173 definition to shadow a syntactic keyword whose meaning is needed to
3174 determine whether some form in the group of forms that contains the
3175 shadowing definition is in fact a definition, or, for internal definitions,
3176 is needed to determine the boundary between the group and the expressions
3177 that follow the group. For example, the following are errors:
3184 (begin (define begin list))
3187 ((foo (syntax-rules ()
3188 ((foo (proc args ...) body ...)
3193 (foo (plus x y) (+ x y))
3204 @c Initial environment
3207 @node Standard procedures, Formal syntax and semantics, Program structure, top
3208 @chapter Standard procedures
3211 * Equivalence predicates::
3213 * Other data types::
3214 * Control features::
3216 * Input and output::
3223 @cindex @w{initial environment}
3225 @cindex @w{top level environment}
3227 @cindex @w{library procedure}
3229 This chapter describes Scheme's built-in procedures. The initial (or
3230 ``top level'') Scheme environment starts out with a number of variables
3231 bound to locations containing useful values, most of which are primitive
3232 procedures that manipulate data. For example, the variable @samp{abs} is
3233 bound to (a location initially containing) a procedure of one argument
3234 that computes the absolute value of a number, and the variable @samp{+}
3235 is bound to a procedure that computes sums. Built-in procedures that
3236 can easily be written in terms of other built-in procedures are identified as
3237 ``library procedures''.
3239 A program may use a top-level definition to bind any variable. It may
3240 subsequently alter any such binding by an assignment (see @pxref{Assignments}).
3241 These operations do not modify the behavior of Scheme's built-in
3242 procedures. Altering any top-level binding that has not been introduced by a
3243 definition has an unspecified effect on the behavior of the built-in procedures.
3245 @node Equivalence predicates, Numbers, Standard procedures, Standard procedures
3246 @section Equivalence predicates
3250 A @dfn{predicate} is a procedure that always returns a boolean
3251 @cindex @w{predicate}
3252 value (@t{#t} or @t{#f}). An @dfn{equivalence predicate} is
3253 @cindex @w{equivalence predicate}
3254 the computational analogue of a mathematical equivalence relation (it is
3255 symmetric, reflexive, and transitive). Of the equivalence predicates
3256 described in this section, @samp{eq?} is the finest or most
3257 discriminating, and @samp{equal?} is the coarsest. @samp{Eqv?} is
3258 slightly less discriminating than @samp{eq?}.
3261 this paragraph. Lift the discussion from the Maclisp manual. Explain
3262 why there's more than one predicate.
3268 @deffn {procedure} eqv? obj1 obj2
3270 The @samp{eqv?} procedure defines a useful equivalence relation on objects.
3271 Briefly, it returns @t{#t} if @var{obj1} and @var{obj2} should
3272 normally be regarded as the same object. This relation is left slightly
3273 open to interpretation, but the following partial specification of
3274 @samp{eqv?} holds for all implementations of Scheme.
3276 The @samp{eqv?} procedure returns @t{#t} if:
3283 @var{obj1} and @var{obj2} are both @t{#t} or both @t{#f}.
3286 @var{obj1} and @var{obj2} are both symbols and
3290 @t{(string=? (symbol->string obj1)
3291 (symbol->string obj2))
3300 This assumes that neither @var{obj1} nor @var{obj2} is an ``uninterned
3301 symbol'' as alluded to in section @ref{Symbols}. This report does
3302 not presume to specify the behavior of @samp{eqv?} on implementation-dependent
3308 @var{obj1} and @var{obj2} are both numbers, are numerically
3309 equal (see @samp{=}, section @pxref{Numbers}), and are either both
3310 exact or both inexact.
3313 @var{obj1} and @var{obj2} are both characters and are the same
3314 character according to the @samp{char=?} procedure
3315 (section @pxref{Characters}).
3318 both @var{obj1} and @var{obj2} are the empty list.
3321 @var{obj1} and @var{obj2} are pairs, vectors, or strings that denote the
3322 same locations in the store (section @pxref{Storage model}).
3325 @var{obj1} and @var{obj2} are procedures whose location tags are
3326 equal (section @pxref{Procedures}).
3333 The @samp{eqv?} procedure returns @t{#f} if:
3340 @var{obj1} and @var{obj2} are of different types
3341 (section @pxref{Disjointness of types}).
3344 one of @var{obj1} and @var{obj2} is @t{#t} but the other is
3348 @var{obj1} and @var{obj2} are symbols but
3352 @t{(string=? (symbol->string @var{obj1})
3353 (symbol->string @var{obj2}))
3360 one of @var{obj1} and @var{obj2} is an exact number but the other
3361 is an inexact number.
3364 @var{obj1} and @var{obj2} are numbers for which the @samp{=}
3365 procedure returns @t{#f}.
3368 @var{obj1} and @var{obj2} are characters for which the @samp{char=?}
3369 procedure returns @t{#f}.
3372 one of @var{obj1} and @var{obj2} is the empty list but the other
3376 @var{obj1} and @var{obj2} are pairs, vectors, or strings that denote
3380 @var{obj1} and @var{obj2} are procedures that would behave differently
3381 (return different value(s) or have different side effects) for some arguments.
3389 @t{(eqv? 'a 'a) ==> #t
3392 (eqv? '() '()) ==> #t
3393 (eqv? 100000000 100000000) ==> #t
3394 (eqv? (cons 1 2) (cons 1 2)) ==> #f
3396 (lambda () 2)) ==> #f
3397 (eqv? #f 'nil) ==> #f
3398 (let ((p (lambda (x) x)))
3404 The following examples illustrate cases in which the above rules do
3405 not fully specify the behavior of @samp{eqv?}. All that can be said
3406 about such cases is that the value returned by @samp{eqv?} must be a
3411 @t{(eqv? "" "") ==> @emph{unspecified}
3412 (eqv? '#() '#()) ==> @emph{unspecified}
3413 (eqv? (lambda (x) x)
3414 (lambda (x) x)) ==> @emph{unspecified}
3415 (eqv? (lambda (x) x)
3416 (lambda (y) y)) ==> @emph{unspecified}
3421 The next set of examples shows the use of @samp{eqv?} with procedures
3422 that have local state. @samp{Gen-counter} must return a distinct
3423 procedure every time, since each procedure has its own internal counter.
3424 @samp{Gen-loser}, however, returns equivalent procedures each time, since
3425 the local state does not affect the value or side effects of the
3430 @t{(define gen-counter
3433 (lambda () (set! n (+ n 1)) n))))
3434 (let ((g (gen-counter)))
3436 (eqv? (gen-counter) (gen-counter))
3441 (lambda () (set! n (+ n 1)) 27))))
3442 (let ((g (gen-loser)))
3444 (eqv? (gen-loser) (gen-loser))
3445 ==> @emph{unspecified}
3447 (letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
3448 (g (lambda () (if (eqv? f g) 'both 'g))))
3450 ==> @emph{unspecified}
3452 (letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
3453 (g (lambda () (if (eqv? f g) 'g 'both))))
3460 @c Objects of distinct types must never be regarded as the same object,
3461 @c except that \schfalse{} and the empty list\index{empty list} are permitted to
3465 @c (eqv? '() \schfalse) \ev \unspecified%
3468 Since it is an error to modify constant objects (those returned by
3469 literal expressions), implementations are permitted, though not
3470 required, to share structure between constants where appropriate. Thus
3471 the value of @samp{eqv?} on constants is sometimes
3472 implementation-dependent.
3476 @t{(eqv? '(a) '(a)) ==> @emph{unspecified}
3477 (eqv? "a" "a") ==> @emph{unspecified}
3478 (eqv? '(b) (cdr '(a b))) ==> @emph{unspecified}
3488 The above definition of @samp{eqv?} allows implementations latitude in
3489 their treatment of procedures and literals: implementations are free
3490 either to detect or to fail to detect that two procedures or two literals
3491 are equivalent to each other, and can decide whether or not to
3492 merge representations of equivalent objects by using the same pointer or
3493 bit pattern to represent both.
3501 @deffn {procedure} eq? obj1 obj2
3503 @samp{Eq?} is similar to @samp{eqv?} except that in some cases it is
3504 capable of discerning distinctions finer than those detectable by
3507 @samp{Eq?} and @samp{eqv?} are guaranteed to have the same
3508 behavior on symbols, booleans, the empty list, pairs, procedures,
3510 strings and vectors. @samp{Eq?}'s behavior on numbers and characters is
3511 implementation-dependent, but it will always return either true or
3512 false, and will return true only when @samp{eqv?} would also return
3513 true. @samp{Eq?} may also behave differently from @samp{eqv?} on empty
3514 vectors and empty strings.
3518 @t{(eq? 'a 'a) ==> #t
3519 (eq? '(a) '(a)) ==> @emph{unspecified}
3520 (eq? (list 'a) (list 'a)) ==> #f
3521 (eq? "a" "a") ==> @emph{unspecified}
3522 (eq? "" "") ==> @emph{unspecified}
3523 (eq? '() '()) ==> #t
3524 (eq? 2 2) ==> @emph{unspecified}
3525 (eq? #\A #\A) ==> @emph{unspecified}
3526 (eq? car car) ==> #t
3528 (eq? n n)) ==> @emph{unspecified}
3533 (let ((p (lambda (x) x)))
3540 Needs to be explained better above. How can this be made to be
3541 not confusing? A table maybe?
3547 @emph{Rationale:} It will usually be possible to implement @samp{eq?} much
3548 more efficiently than @samp{eqv?}, for example, as a simple pointer
3549 comparison instead of as some more complicated operation. One reason is
3550 that it may not be possible to compute @samp{eqv?} of two numbers in
3551 constant time, whereas @samp{eq?} implemented as pointer comparison will
3552 always finish in constant time. @samp{Eq?} may be used like @samp{eqv?}
3553 in applications using procedures to implement objects with state since
3554 it obeys the same constraints as @samp{eqv?}.
3562 @deffn {library procedure} equal? obj1 obj2
3564 @samp{Equal?} recursively compares the contents of pairs, vectors, and
3565 strings, applying @samp{eqv?} on other objects such as numbers and symbols.
3566 A rule of thumb is that objects are generally @samp{equal?} if they print
3567 the same. @samp{Equal?} may fail to terminate if its arguments are
3568 circular data structures.
3572 @t{(equal? 'a 'a) ==> #t
3573 (equal? '(a) '(a)) ==> #t
3576 (equal? "abc" "abc") ==> #t
3578 (equal? (make-vector 5 'a)
3579 (make-vector 5 'a)) ==> #t
3580 (equal? (lambda (x) x)
3581 (lambda (y) y)) ==> @emph{unspecified}
3589 @node Numbers, Other data types, Equivalence predicates, Standard procedures
3595 * Implementation restrictions::
3596 * Syntax of numerical constants::
3597 * Numerical operations::
3598 * Numerical input and output::
3605 @c %R4%% The excessive use of the code font in this section was
3606 @c confusing, somewhat obnoxious, and inconsistent with the rest
3607 @c of the report and with parts of the section itself. I added
3608 @c a \tupe no-op, and changed most old uses of \type to \tupe,
3609 @c to make it easier to change the fonts back if people object
3612 @c \newcommand{\type}[1]{{\it#1}}
3613 @c \newcommand{\tupe}[1]{{#1}}
3615 Numerical computation has traditionally been neglected by the Lisp
3616 community. Until Common Lisp there was no carefully thought out
3617 strategy for organizing numerical computation, and with the exception of
3618 the MacLisp system [Pitman83] little effort was made to
3619 execute numerical code efficiently. This report recognizes the excellent work
3620 of the Common Lisp committee and accepts many of their recommendations.
3621 In some ways this report simplifies and generalizes their proposals in a manner
3622 consistent with the purposes of Scheme.
3624 It is important to distinguish between the mathematical numbers, the
3625 Scheme numbers that attempt to model them, the machine representations
3626 used to implement the Scheme numbers, and notations used to write numbers.
3627 This report uses the types @i{number}, @i{complex}, @i{real},
3628 @i{rational}, and @i{integer} to refer to both mathematical numbers
3629 and Scheme numbers. Machine representations such as fixed point and
3630 floating point are referred to by names such as @i{fixnum} and
3633 @c %R4%% I did some reorganizing here to move the discussion of mathematical
3634 @c numbers before the discussion of the Scheme numbers, hoping that this
3635 @c would help to motivate the discussion of representation independence.
3637 @node Numerical types, Exactness, Numbers, Numbers
3638 @subsection Numerical types
3642 @cindex @w{numerical types}
3644 @c %R4%% A Scheme system provides data of type \type{number}, which is the most
3645 @c general numerical type supported by that system.
3647 @c likely to be a complicated union type implemented in terms of
3648 @c \type{fixnum}s, \type{bignum}s, \type{flonum}s, and so forth, but this
3649 @c should not be apparent to a naive user. What the user should see is
3650 @c that the usual operations on numbers produce the mathematically
3651 @c expected results, within the limits of the implementation.
3653 @c %R4%% I rewrote the following paragraph to make the various levels of
3654 @c the tower into subsets of each other, instead of relating them by
3655 @c injections. I think the injections tended to put people in the frame
3656 @c of mind of thinking about coercions between non-overlapping numeric
3657 @c types in mainstream programming languages.
3659 Mathematically, numbers may be arranged into a tower of subtypes
3660 @c %R4%% with injections relating adjacent levels of the tower:
3661 in which each level is a subset of the level above it:
3672 For example, 3 is an integer. Therefore 3 is also a rational,
3673 a real, and a complex. The same is true of the Scheme numbers
3674 that model 3. For Scheme numbers, these types are defined by the
3675 predicates @code{number?}, @code{complex?}, @code{real?}, @code{rational?},
3676 @vindex @w{rational?}
3678 @vindex @w{complex?}
3680 and @code{integer?}.
3681 @vindex @w{integer?}
3683 There is no simple relationship between a number's type and its
3684 representation inside a computer. Although most implementations of
3685 Scheme will offer at least two different representations of 3, these
3686 different representations denote the same integer.
3688 @c %R4%% I moved "Implementations of Scheme are not required to implement
3689 @c the whole tower..." to the subsection on implementation restrictions.
3691 Scheme's numerical operations treat numbers as abstract data, as
3692 independent of their representation as possible. Although an implementation
3693 of Scheme may use fixnum, flonum, and perhaps other representations for
3694 numbers, this should not be apparent to a casual programmer writing
3697 It is necessary, however, to distinguish between numbers that are
3698 represented exactly and those that may not be. For example, indexes
3699 into data structures must be known exactly, as must some polynomial
3700 coefficients in a symbolic algebra system. On the other hand, the
3701 results of measurements are inherently inexact, and irrational numbers
3702 may be approximated by rational and therefore inexact approximations.
3703 In order to catch uses of inexact numbers where exact numbers are
3704 required, Scheme explicitly distinguishes exact from inexact numbers.
3705 This distinction is orthogonal to the dimension of type.
3707 @node Exactness, Implementation restrictions, Numerical types, Numbers
3708 @subsection Exactness
3711 @c %R4%% I tried to direct the following paragraph away from philosophizing
3712 @c about the exactness of mathematical numbers, and toward philosophizing
3713 @c about the exactness of Scheme numbers.
3716 @cindex @w{exactness}
3717 Scheme numbers are either @i{exact} or @i{inexact}. A number is
3718 @r{exact} if it was written as an exact constant or was derived from
3719 @r{exact} numbers using only @r{exact} operations. A number is
3720 @r{inexact} if it was written as an inexact constant,
3721 @c %R4%% models a quantity (e.g., a measurement) known only approximately,
3723 derived using @r{inexact} ingredients, or if it was derived using
3724 @r{inexact} operations. Thus @r{inexact}ness is a contagious
3725 property of a number.
3726 @c %R4%% The rest of this paragraph (from R3RS) has been dropped.
3728 If two implementations produce @r{exact} results for a
3729 computation that did not involve @r{inexact} intermediate results,
3730 the two ultimate results will be mathematically equivalent. This is
3731 generally not true of computations involving @r{inexact} numbers
3732 since approximate methods such as floating point arithmetic may be used,
3733 but it is the duty of each implementation to make the result as close as
3734 practical to the mathematically ideal result.
3736 Rational operations such as @samp{+} should always produce
3737 @r{exact} results when given @r{exact} arguments.
3738 @c %R4%%If an implementation is
3739 @c unable to represent an \tupe{exact} result (for example, if it does not
3740 @c support infinite precision integers and rationals)
3741 If the operation is unable to produce an @r{exact} result,
3742 then it may either report the violation of an implementation restriction
3743 or it may silently coerce its
3744 result to an @r{inexact} value.
3745 @c %R4%%Such a coercion may cause an error later.
3746 See section @ref{Implementation restrictions}.
3748 With the exception of @code{inexact->exact}, the operations described in
3749 @vindex @w{inexact->exact}
3750 this section must generally return inexact results when given any inexact
3751 arguments. An operation may, however, return an @r{exact} result if it can
3752 prove that the value of the result is unaffected by the inexactness of its
3753 arguments. For example, multiplication of any number by an @r{exact} zero
3754 may produce an @r{exact} zero result, even if the other argument is
3757 @node Implementation restrictions, Syntax of numerical constants, Exactness, Numbers
3758 @subsection Implementation restrictions
3762 @cindex @w{implementation restriction}
3764 Implementations of Scheme are not required to implement the whole
3765 tower of subtypes given in section @ref{Numerical types},
3766 but they must implement a coherent subset consistent with both the
3767 purposes of the implementation and the spirit of the Scheme language.
3768 For example, an implementation in which all numbers are @r{real}
3769 may still be quite useful.
3771 Implementations may also support only a limited range of numbers of
3772 any type, subject to the requirements of this section. The supported
3773 range for @r{exact} numbers of any type may be different from the
3774 supported range for @r{inexact} numbers of that type. For example,
3775 an implementation that uses flonums to represent all its
3776 @r{inexact} @r{real} numbers may
3777 support a practically unbounded range of @r{exact} @r{integer}s
3779 while limiting the range of @r{inexact} @r{real}s (and therefore
3780 the range of @r{inexact} @r{integer}s and @r{rational}s)
3781 to the dynamic range of the flonum format.
3783 the gaps between the representable @r{inexact} @r{integer}s and
3785 likely to be very large in such an implementation as the limits of this
3786 range are approached.
3788 An implementation of Scheme must support exact integers
3789 throughout the range of numbers that may be used for indexes of
3790 lists, vectors, and strings or that may result from computing the length of a
3791 list, vector, or string. The @code{length}, @code{vector-length},
3792 @vindex @w{vector-length}
3794 and @code{string-length} procedures must return an exact
3795 @vindex @w{string-length}
3796 integer, and it is an error to use anything but an exact integer as an
3797 index. Furthermore any integer constant within the index range, if
3798 expressed by an exact integer syntax, will indeed be read as an exact
3799 integer, regardless of any implementation restrictions that may apply
3800 outside this range. Finally, the procedures listed below will always
3801 return an exact integer result provided all their arguments are exact integers
3802 and the mathematically expected result is representable as an exact integer
3803 within the implementation:
3809 quotient remainder modulo
3811 numerator denominator gcd
3813 truncate round rationalize
3819 Implementations are encouraged, but not required, to support
3820 @r{exact} @r{integer}s and @r{exact} @r{rational}s of
3821 practically unlimited size and precision, and to implement the
3822 above procedures and the @samp{/} procedure in
3823 such a way that they always return @r{exact} results when given @r{exact}
3824 arguments. If one of these procedures is unable to deliver an @r{exact}
3825 result when given @r{exact} arguments, then it may either report a
3827 implementation restriction or it may silently coerce its result to an
3828 @r{inexact} number. Such a coercion may cause an error later.
3830 @c %R4%% I moved this stuff here.
3831 @c It seems to me that the only thing that this requires is that
3832 @c implementations that support inexact numbers have to have both
3833 @c exact and inexact representations for the integers 0 through 15.
3834 @c If that's what it's saying, I'd rather say it that way.
3835 @c On the other hand, letting the limit be as small as 15 sounds a
3836 @c tad silly, though I think I understand how that number was arrived at.
3837 @c (Or is 35 the number?)
3839 @c Implementations are encouraged, but not required, to support \tupe{inexact}
3840 @c numbers. For any implementation that supports \tupe{inexact} numbers,
3841 @c there is a subset of the integers for which there are both \tupe{exact} and
3842 @c \tupe{inexact} representations. This subset must include all non-negative
3843 @c integers up to some limit specified by the implementation. This limit
3844 @c must be 16 or greater. The
3845 @c \ide{exact\coerce{}inexact} and \ide{inexact\coerce{}exact}
3846 @c procedures implement the natural one-to-one correspondence between
3847 @c the \tupe{inexact} and \tupe{exact} integers within this range.
3849 An implementation may use floating point and other approximate
3850 representation strategies for @r{inexact} numbers.
3851 @c %R4%% The following sentence seemed a bit condescending as well as
3852 @c awkward. It didn't seem to be very enforceable, so I flushed it.
3855 @c say that implementors need not use the best known algorithms for
3856 @c \tupe{inexact} computations---only that approximate methods of high
3857 @c quality are allowed.
3859 This report recommends, but does not require, that the IEEE 32-bit
3860 and 64-bit floating point standards be followed by implementations that use
3861 flonum representations, and that implementations using
3862 other representations should match or exceed the precision achievable
3863 using these floating point standards [IEEE].
3865 In particular, implementations that use flonum representations
3866 must follow these rules: A @r{flonum} result
3867 must be represented with at least as much precision as is used to express any of
3868 the inexact arguments to that operation. It is desirable (but not required) for
3869 potentially inexact operations such as @samp{sqrt}, when applied to @r{exact}
3870 arguments, to produce @r{exact} answers whenever possible (for example the
3871 square root of an @r{exact} 4 ought to be an @r{exact} 2).
3873 @r{exact} number is operated upon so as to produce an @r{inexact} result
3874 (as by @samp{sqrt}), and if the result is represented as a @r{flonum}, then
3875 the most precise @r{flonum} format available must be used; but if the result
3876 is represented in some other way then the representation must have at least as
3877 much precision as the most precise @r{flonum} format available.
3879 Although Scheme allows a variety of written
3880 @c %R4%% representations of
3882 numbers, any particular implementation may support only some of them.
3884 For example, an implementation in which all numbers are @r{real}
3885 need not support the rectangular and polar notations for complex
3886 numbers. If an implementation encounters an @r{exact} numerical constant that
3887 it cannot represent as an @r{exact} number, then it may either report a
3888 violation of an implementation restriction or it may silently represent the
3889 constant by an @r{inexact} number.
3892 @node Syntax of numerical constants, Numerical operations, Implementation restrictions, Numbers
3893 @subsection Syntax of numerical constants
3899 @c %R4%% I removed the following paragraph in an attempt to tighten up
3900 @c this subsection. Except for its first sentence, which I moved to
3901 @c the subsection on implementation restrictions, I think its content
3902 @c is implied by the rest of the section.
3904 @c Although Scheme allows a variety of written representations of numbers,
3905 @c any particular implementation may support only some of them.
3906 @c These syntaxes are intended to be purely notational; any kind of number
3907 @c may be written in any form that the user deems convenient. Of course,
3908 @c writing 1/7 as a limited-precision decimal fraction will not express the
3909 @c number exactly, but this approximate form of expression may be just what
3910 @c the user wants to see.
3912 The syntax of the written representations for numbers is described formally in
3913 section @ref{Lexical structure}. Note that case is not significant in numerical
3916 @c %R4%% See section~\ref{numberformats} for many examples.
3918 A number may be written in binary, octal, decimal, or
3919 hexadecimal by the use of a radix prefix. The radix prefixes are @samp{#b} (binary), @samp{#o} (octal), @samp{#d} (decimal), and @samp{#x} (hexadecimal). With
3924 no radix prefix, a number is assumed to be expressed in decimal.
3929 numerical constant may be specified to be either @r{exact} or
3930 @r{inexact} by a prefix. The prefixes are @samp{#e}
3932 for @r{exact}, and @samp{#i} for @r{inexact}. An exactness
3934 prefix may appear before or after any radix prefix that is used. If
3935 the written representation of a number has no exactness prefix, the
3936 constant may be either @r{inexact} or @r{exact}. It is
3937 @r{inexact} if it contains a decimal point, an
3938 exponent, or a ``#'' character in the place of a digit,
3939 otherwise it is @r{exact}.
3940 @c %R4%% With our new syntax, the following sentence is redundant:
3942 @c The written representation of a
3943 @c compound number, such as a ratio or a complex, is exact if and only if
3944 @c all of its constituents are exact.
3946 In systems with @r{inexact} numbers
3947 of varying precisions it may be useful to specify
3948 the precision of a constant. For this purpose, numerical constants
3949 may be written with an exponent marker that indicates the
3950 desired precision of the @r{inexact}
3951 representation. The letters @samp{s}, @samp{f},
3952 @samp{d}, and @samp{l} specify the use of @var{short}, @var{single},
3953 @var{double}, and @var{long} precision, respectively. (When fewer
3955 @c %R4%%\tupe{flonum}
3957 representations exist, the four size
3958 specifications are mapped onto those available. For example, an
3959 implementation with two internal representations may map short and
3960 single together and long and double together.) In addition, the
3961 exponent marker @samp{e} specifies the default precision for the
3962 implementation. The default precision has at least as much precision
3963 as @var{double}, but
3964 implementations may wish to allow this default to be set by the user.
3970 @r{Round to single ---} 3.141593
3972 @r{Extend to long ---} .600000000000000
3978 @node Numerical operations, Numerical input and output, Syntax of numerical constants, Numbers
3979 @subsection Numerical operations
3982 The reader is referred to section @ref{Entry format} for a summary
3983 of the naming conventions used to specify restrictions on the types of
3984 arguments to numerical routines.
3985 @c %R4%% The following sentence has already been said twice, and the
3986 @c term "exactness-preserving" is no longer defined by the Report.
3989 @c an exactness-preserving operation may coerce its result to inexact if the
3990 @c implementation is unable to represent it exactly.
3991 The examples used in this section assume that any numerical constant written
3992 using an @r{exact} notation is indeed represented as an @r{exact}
3993 number. Some examples also assume that certain numerical constants written
3994 using an @r{inexact} notation can be represented without loss of
3995 accuracy; the @r{inexact} constants were chosen so that this is
3996 likely to be true in implementations that use flonums to represent
4000 Scheme provides the usual set of operations for manipulating
4006 @deffn {procedure} number? obj
4007 @deffnx {procedure} complex? obj
4008 @deffnx {procedure} real? obj
4009 @deffnx {procedure} rational? obj
4010 @deffnx {procedure} integer? obj
4012 These numerical type predicates can be applied to any kind of
4013 argument, including non-numbers. They return @t{#t} if the object is
4014 of the named type, and otherwise they return @t{#f}.
4015 In general, if a type predicate is true of a number then all higher
4016 type predicates are also true of that number. Consequently, if a type
4017 predicate is false of a number, then all lower type predicates are
4018 also false of that number.
4019 @c %R4%% The new section on implementation restrictions subsumes:
4021 @c supports all of these types; for example, it is entirely possible to have a
4022 @c Scheme system that has only \tupe{integer}s. Nonetheless every implementation
4023 @c of Scheme must have all of these predicates.
4025 If @var{z} is an inexact complex number, then @samp{(real? @var{z})} is true if
4026 and only if @samp{(zero? (imag-part @var{z}))} is true. If @var{x} is an inexact
4027 real number, then @samp{(integer? @var{x})} is true if and only if
4028 @samp{(= @var{x} (round @var{x}))}.
4032 @t{(complex? 3+4i) ==> #t
4035 (real? -2.5+0.0i) ==> #t
4036 (real? #e1e10) ==> #t
4037 (rational? 6/10) ==> #t
4038 (rational? 6/3) ==> #t
4039 (integer? 3+0i) ==> #t
4040 (integer? 3.0) ==> #t
4041 (integer? 8/4) ==> #t
4049 The behavior of these type predicates on @r{inexact} numbers
4050 is unreliable, since any inaccuracy may affect the result.
4057 In many implementations the @code{rational?} procedure will be the same
4058 @vindex @w{rational?}
4059 as @code{real?}, and the @code{complex?} procedure will be the same as
4060 @vindex @w{complex?}
4062 @code{number?}, but unusual implementations may be able to represent
4064 some irrational numbers exactly or may extend the number system to
4065 support some kind of non-complex numbers.
4072 @deffn {procedure} exact? @var{z}
4073 @deffnx {procedure} inexact? @var{z}
4075 These numerical predicates provide tests for the exactness of a
4076 quantity. For any Scheme number, precisely one of these predicates
4083 @deffn {procedure} = z1 z2 z3 @dots{},
4084 @deffnx {procedure} < x1 x2 x3 @dots{},
4085 @deffnx {procedure} > x1 x2 x3 @dots{},
4086 @deffnx {procedure} <= x1 x2 x3 @dots{},
4087 @deffnx {procedure} >= x1 x2 x3 @dots{},
4089 @c - Some implementations allow these procedures to take many arguments, to
4090 @c - facilitate range checks.
4091 These procedures return @t{#t} if their arguments are (respectively):
4092 equal, monotonically increasing, monotonically decreasing,
4093 monotonically nondecreasing, or monotonically nonincreasing.
4095 These predicates are required to be transitive.
4100 The traditional implementations of these predicates in Lisp-like
4101 languages are not transitive.
4108 While it is not an error to compare @r{inexact} numbers using these
4109 predicates, the results may be unreliable because a small inaccuracy
4110 may affect the result; this is especially true of @code{=} and @code{zero?}.
4113 When in doubt, consult a numerical analyst.
4120 @deffn {library procedure} zero? @var{z}
4121 @deffnx {library procedure} positive? @var{x}
4122 @deffnx {library procedure} negative? @var{x}
4123 @deffnx {library procedure} odd? @var{n}
4124 @deffnx {library procedure} even? @var{n}
4126 These numerical predicates test a number for a particular property,
4127 returning @t{#t} or @t{#f}. See note above.
4132 @deffn {library procedure} max x1 x2 @dots{},
4133 @deffnx {library procedure} min x1 x2 @dots{},
4135 These procedures return the maximum or minimum of their arguments.
4139 @t{(max 3 4) ==> 4 ; exact
4140 (max 3.9 4) ==> 4.0 ; inexact
4148 If any argument is inexact, then the result will also be inexact (unless
4149 the procedure can prove that the inaccuracy is not large enough to affect the
4150 result, which is possible only in unusual implementations). If @samp{min} or
4151 @samp{max} is used to compare numbers of mixed exactness, and the numerical
4152 value of the result cannot be represented as an inexact number without loss of
4153 accuracy, then the procedure may report a violation of an implementation
4162 @deffn {procedure} + z1 @dots{},
4163 @deffnx {procedure} * z1 @dots{},
4165 These procedures return the sum or product of their arguments.
4166 @c - These procedures are exactness preserving.
4183 @deffn {procedure} - z1 z2
4184 @deffnx {procedure} - @var{z}
4185 @deffnx {optional procedure} - z1 z2 @dots{},
4186 @deffnx {procedure} / z1 z2
4187 @deffnx {procedure} / @var{z}
4188 @deffnx {optional procedure} / z1 z2 @dots{},
4190 With two or more arguments, these procedures return the difference or
4191 quotient of their arguments, associating to the left. With one argument,
4192 however, they return the additive or multiplicative inverse of their argument.
4193 @c - These procedures are exactness preserving, except that division may
4194 @c - coerce its result to inexact in implementations that do not support
4195 @c - \tupe{ratnum}s.
4212 @deffn {library procedure} abs x
4214 @samp{Abs} returns the absolute value of its argument.
4215 @c - {\cf Abs} is exactness preserving when its argument is real.
4226 @deffn {procedure} quotient n1 n2
4227 @deffnx {procedure} remainder n1 n2
4228 @deffnx {procedure} modulo n1 n2
4230 These procedures implement number-theoretic (integer)
4231 division. @var{n2} should be non-zero. All three procedures
4232 return integers. If @var{n1}/@var{n2} is an integer:
4235 @t{ (quotient @var{n1} @var{n2}) ==> @var{n1}/@var{n2}
4236 (remainder @var{n1} @var{n2}) ==> 0
4237 (modulo @var{n1} @var{n2}) ==> 0
4241 If @var{n1}/@var{n2} is not an integer:
4244 @t{ (quotient @var{n1} @var{n2}) ==> @var{n_q}
4245 (remainder @var{n1} @var{n2}) ==> @var{n_r}
4246 (modulo @var{n1} @var{n2}) ==> @var{n_m}
4250 where @var{n_q} is @var{n1}/@var{n2} rounded towards zero,
4251 0 < |@var{n_r}| < |@var{n2}|, 0 < |@var{n_m}| < |@var{n2}|,
4252 @var{n_r} and @var{n_m} differ from @var{n1} by a multiple of @var{n2},
4253 @var{n_r} has the same sign as @var{n1}, and
4254 @var{n_m} has the same sign as @var{n2}.
4256 From this we can conclude that for integers @var{n1} and @var{n2} with
4257 @var{n2} not equal to 0,
4260 @t{ (= @var{n1} (+ (* @var{n2} (quotient @var{n1} @var{n2}))
4261 (remainder @var{n1} @var{n2})))
4266 provided all numbers involved in that computation are exact.
4270 @t{(modulo 13 4) ==> 1
4271 (remainder 13 4) ==> 1
4273 (modulo -13 4) ==> 3
4274 (remainder -13 4) ==> -1
4276 (modulo 13 -4) ==> -3
4277 (remainder 13 -4) ==> 1
4279 (modulo -13 -4) ==> -1
4280 (remainder -13 -4) ==> -1
4282 (remainder -13 -4.0) ==> -1.0 ; inexact
4289 @deffn {library procedure} gcd n1 @dots{},
4290 @deffnx {library procedure} lcm n1 @dots{},
4292 These procedures return the greatest common divisor or least common
4293 multiple of their arguments. The result is always non-negative.
4294 @c - These procedures are exactness preserving.
4296 @c %R4%% I added the inexact example.
4299 @t{(gcd 32 -36) ==> 4
4301 (lcm 32 -36) ==> 288
4302 (lcm 32.0 -36) ==> 288.0 ; inexact
4312 @deffn {procedure} numerator @var{q}
4313 @deffnx {procedure} denominator @var{q}
4315 These procedures return the numerator or denominator of their
4316 argument; the result is computed as if the argument was represented as
4317 a fraction in lowest terms. The denominator is always positive. The
4318 denominator of 0 is defined to be 1.
4319 @c - The remarks about denominators are new.
4320 @c - Clearly, they are exactness-preserving procedures.
4323 More description and examples needed.
4328 @t{(numerator (/ 6 4)) ==> 3
4329 (denominator (/ 6 4)) ==> 2
4331 (exact->inexact (/ 6 4))) ==> 2.0
4340 @deffn {procedure} floor x
4341 @deffnx {procedure} ceiling x
4342 @deffnx {procedure} truncate x
4343 @deffnx {procedure} round x
4346 These procedures return integers.
4347 @samp{Floor} returns the largest integer not larger than @var{x}.
4348 @samp{Ceiling} returns the smallest integer not smaller than @var{x}.
4349 @samp{Truncate} returns the integer closest to @var{x} whose absolute
4350 value is not larger than the absolute value of @var{x}. @samp{Round} returns the
4351 closest integer to @var{x}, rounding to even when @var{x} is halfway between two
4357 @samp{Round} rounds to even for consistency with the default rounding
4358 mode specified by the IEEE floating point standard.
4365 If the argument to one of these procedures is inexact, then the result
4366 will also be inexact. If an exact value is needed, the
4367 result should be passed to the @samp{inexact->exact} procedure.
4373 @t{(floor -4.3) ==> -5.0
4374 (ceiling -4.3) ==> -4.0
4375 (truncate -4.3) ==> -4.0
4376 (round -4.3) ==> -4.0
4379 (ceiling 3.5) ==> 4.0
4380 (truncate 3.5) ==> 3.0
4381 (round 3.5) ==> 4.0 ; inexact
4383 (round 7/2) ==> 4 ; exact
4392 @deffn {library procedure} rationalize x y
4393 @c - \proto{rationalize}{ x}{procedure}
4396 @samp{Rationalize} returns the @emph{simplest} rational number
4397 differing from @var{x} by no more than @var{y}. A rational number r_1 is
4398 @emph{simpler} than another rational number
4399 @cindex @w{simplest rational}
4400 r_2 if r_1 = p_1/q_1 and r_2 = p_2/q_2 (in lowest terms) and |p_1|<= |p_2| and |q_1| <= |q_2|. Thus 3/5 is simpler than 4/7.
4401 Although not all rationals are comparable in this ordering (consider 2/7
4402 and 3/5) any interval contains a rational number that is simpler than
4403 every other rational number in that interval (the simpler 2/5 lies
4404 between 2/7 and 3/5). Note that 0 = 0/1 is the simplest rational of
4410 (inexact->exact .3) 1/10) ==> 1/3 ; exact
4411 (rationalize .3 1/10) ==> #i1/3 ; inexact
4419 @deffn {procedure} exp @var{z}
4420 @deffnx {procedure} log @var{z}
4421 @deffnx {procedure} sin @var{z}
4422 @deffnx {procedure} cos @var{z}
4423 @deffnx {procedure} tan @var{z}
4424 @deffnx {procedure} asin @var{z}
4425 @deffnx {procedure} acos @var{z}
4426 @deffnx {procedure} atan @var{z}
4427 @deffnx {procedure} atan @var{y} @var{x}
4429 These procedures are part of every implementation that supports
4432 real numbers; they compute the usual transcendental functions. @samp{Log}
4433 computes the natural logarithm of @var{z} (not the base ten logarithm).
4434 @samp{Asin}, @samp{acos}, and @samp{atan} compute arcsine (sin^-1),
4435 arccosine (cos^-1), and arctangent (tan^-1), respectively.
4436 The two-argument variant of @samp{atan} computes @t{(angle
4437 (make-rectangular @var{x} @var{y}))} (see below), even in implementations
4438 that don't support general complex numbers.
4440 In general, the mathematical functions log, arcsine, arccosine, and
4441 arctangent are multiply defined.
4442 The value of log z is defined to be the one whose imaginary
4443 part lies in the range from -pi (exclusive) to pi (inclusive).
4445 With log defined this way, the values of sin^-1 z, cos^-1 z,
4446 and tan^-1 z are according to the following formulae:
4449 @center sin^-1 z = -i log (i z + sqrt1 - z^2)
4453 @center cos^-1 z = pi / 2 - sin^-1 z
4457 @center tan^-1 z = (log (1 + i z) - log (1 - i z)) / (2 i)
4460 The above specification follows [CLtL], which in turn
4461 cites [Penfield81]; refer to these sources for more detailed
4462 discussion of branch cuts, boundary conditions, and implementation of
4463 these functions. When it is possible these procedures produce a real
4464 result from a real argument.
4469 The cited references are likely to change their branch cuts
4470 soon to allow for the possibility of distinct positive and negative
4471 zeroes, as in IEEE floating point. We may not want to follow those
4472 changes, since we may want a complex number with zero imaginary part
4473 (whether positive or negative zero) to be treated as a real. I don't
4474 think there are any better standards for complex arithmetic than the
4475 ones cited, so we're really on our own here.
4483 @deffn {procedure} sqrt @var{z}
4485 Returns the principal square root of @var{z}. The result will have
4486 either positive real part, or zero real part and non-negative imaginary
4492 @deffn {procedure} expt z1 z2
4494 Returns @var{z1} raised to the power @var{z2}. For z_1 ~= 0
4497 @center z_1^z_2 = e^z_2 log z_1
4499 0^z is 1 if z = 0 and 0 otherwise.
4502 @c - \begin{entry}{%-
4503 @c - \proto{approximate}{ z x}{procedure}}
4505 @c - Returns an approximation to \vr{z} in a representation whose precision is
4506 @c - the same as that
4507 @c - of the representation of \vr{x}, which must be an inexact number. The
4508 @c - result is always inexact.
4511 @c - (approximate 3.1415926535 1F10)
4513 @c - (approximate 3.1415926535 \#I65535)
4515 @c - (approximate 3.14F0 1L8)
4517 @c - (approximate 3.1415926535F0 1L8)
4525 @deffn {procedure} make-rectangular x1 x2
4526 @deffnx {procedure} make-polar x3 x4
4527 @deffnx {procedure} real-part @var{z}
4528 @deffnx {procedure} imag-part @var{z}
4529 @deffnx {procedure} magnitude @var{z}
4530 @deffnx {procedure} angle @var{z}
4532 These procedures are part of every implementation that supports
4535 complex numbers. Suppose @var{x1}, @var{x2}, @var{x3}, and @var{x4} are
4536 real numbers and @var{z} is a complex number such that
4539 @center @var{z} = @var{x1} + @var{x2}@w{i} = @var{x3} . e^@w{i} @var{x4}
4544 @t{(make-rectangular @var{x1} @var{x2}) ==> @var{z}
4545 (make-polar @var{x3} @var{x4}) ==> @var{z}
4546 (real-part @var{z}) ==> @var{x1}
4547 (imag-part @var{z}) ==> @var{x2}
4548 (magnitude @var{z}) ==> |@var{x3}|
4549 (angle @var{z}) ==> x_angle
4553 where -pi < x_angle <= pi with x_angle = @var{x4} + 2pi n
4559 @samp{Magnitude} is the same as @code{abs} for a real argument,
4561 but @samp{abs} must be present in all implementations, whereas
4562 @samp{magnitude} need only be present in implementations that support
4563 general complex numbers.
4571 @deffn {procedure} exact->inexact @var{z}
4572 @deffnx {procedure} inexact->exact @var{z}
4574 @samp{Exact->inexact} returns an @r{inexact} representation of @var{z}.
4575 The value returned is the
4576 @r{inexact} number that is numerically closest to the argument.
4578 @c \tupe{exact} arguments which have no reasonably close \tupe{inexact} equivalent,
4579 @c it is permissible to signal an error.
4580 If an @r{exact} argument has no reasonably close @r{inexact} equivalent,
4581 then a violation of an implementation restriction may be reported.
4583 @samp{Inexact->exact} returns an @r{exact} representation of
4584 @var{z}. The value returned is the @r{exact} number that is numerically
4585 closest to the argument.
4586 @c %R4%% For \tupe{inexact} arguments which have no
4587 @c reasonably close \tupe{exact} equivalent, it is permissible to signal
4589 If an @r{inexact} argument has no reasonably close @r{exact} equivalent,
4590 then a violation of an implementation restriction may be reported.
4592 @c %R%% I moved this to the section on implementation restrictions.
4593 @c For any implementation that supports \tupe{inexact} quantities,
4594 @c there is a subset of the integers for which there are both \tupe{exact} and
4595 @c \tupe{inexact} representations. This subset must include the non-negative
4596 @c integers up to a limit specified by the implementation. The limit
4597 @c must be big enough to represent all digits in reasonable radices, and
4598 @c may correspond to some natural word size for the implementation. For
4599 @c such integers, these procedures implement the natural one-to-one
4600 @c correspondence between the representations.
4602 These procedures implement the natural one-to-one correspondence between
4603 @r{exact} and @r{inexact} integers throughout an
4604 implementation-dependent range. See section @ref{Implementation restrictions}.
4610 @node Numerical input and output, , Numerical operations, Numbers
4611 @subsection Numerical input and output
4615 @deffn {procedure} number->string z
4616 @deffnx {procedure} number->string z radix
4618 @var{Radix} must be an exact integer, either 2, 8, 10, or 16. If omitted,
4619 @var{radix} defaults to 10.
4620 The procedure @samp{number->string} takes a
4621 number and a radix and returns as a string an external representation of
4622 the given number in the given radix such that
4625 @t{(let ((number @var{number})
4626 (radix @var{radix}))
4628 (string->number (number->string number
4634 is true. It is an error if no possible result makes this expression true.
4636 If @var{z} is inexact, the radix is 10, and the above expression
4637 can be satisfied by a result that contains a decimal point,
4638 then the result contains a decimal point and is expressed using the
4639 minimum number of digits (exclusive of exponent and trailing
4640 zeroes) needed to make the above expression
4641 true [howtoprint], [howtoread];
4642 otherwise the format of the result is unspecified.
4644 The result returned by @samp{number->string}
4645 never contains an explicit radix prefix.
4650 The error case can occur only when @var{z} is not a complex number
4651 or is a complex number with a non-rational real or imaginary part.
4658 If @var{z} is an inexact number represented using flonums, and
4659 the radix is 10, then the above expression is normally satisfied by
4660 a result containing a decimal point. The unspecified case
4661 allows for infinities, NaNs, and non-flonum representations.
4669 @deffn {procedure} string->number string
4670 @deffnx {procedure} string->number string radix
4672 @c %R4%% I didn't include the (string->number string radix exactness)
4673 @c case, since I haven't heard any resolution of the coding to be used
4674 @c for the third argument.
4676 Returns a number of the maximally precise representation expressed by the
4677 given @var{string}. @var{Radix} must be an exact integer, either 2, 8, 10,
4678 or 16. If supplied, @var{radix} is a default radix that may be overridden
4679 by an explicit radix prefix in @var{string} (e.g. @t{"#o177"}). If @var{radix}
4680 is not supplied, then the default radix is 10. If @var{string} is not
4681 a syntactically valid notation for a number, then @samp{string->number}
4686 @t{(string->number "100") ==> 100
4687 (string->number "100" 16) ==> 256
4688 (string->number "1e2") ==> 100.0
4689 (string->number "15##") ==> 1500.0
4697 The domain of @samp{string->number} may be restricted by implementations
4698 in the following ways. @samp{String->number} is permitted to return
4699 @t{#f} whenever @var{string} contains an explicit radix prefix.
4700 If all numbers supported by an implementation are real, then
4701 @samp{string->number} is permitted to return @t{#f} whenever
4702 @var{string} uses the polar or rectangular notations for complex
4703 numbers. If all numbers are integers, then
4704 @samp{string->number} may return @t{#f} whenever
4705 the fractional notation is used. If all numbers are exact, then
4706 @samp{string->number} may return @t{#f} whenever
4707 an exponent marker or explicit exactness prefix is used, or if
4708 a @t{#} appears in place of a digit. If all inexact
4709 numbers are integers, then
4710 @samp{string->number} may return @t{#f} whenever
4711 a decimal point is used.
4717 @node Other data types, Control features, Numbers, Standard procedures
4718 @section Other data types
4730 This section describes operations on some of Scheme's non-numeric data types:
4731 booleans, pairs, lists, symbols, characters, strings and vectors.
4733 @node Booleans, Pairs and lists, Other data types, Other data types
4734 @subsection Booleans
4738 The standard boolean objects for true and false are written as
4739 @t{#t} and @t{#f}. What really
4742 matters, though, are the objects that the Scheme conditional expressions
4743 (@samp{if}, @samp{cond}, @samp{and}, @samp{or}, @samp{do}) treat as
4744 true or false. The phrase ``a true value''
4747 (or sometimes just ``true'') means any object treated as true by the
4748 conditional expressions, and the phrase ``a false value'' (or
4750 ``false'') means any object treated as false by the conditional expressions.
4752 Of all the standard Scheme values, only @t{#f}
4753 @c is guaranteed to count
4754 counts as false in conditional expressions.
4756 @c specified whether the empty list\index{empty list} counts as false
4757 @c or as true in conditional expressions.
4759 @c and possibly the empty list,
4760 all standard Scheme values, including @t{#t},
4761 pairs, the empty list, symbols, numbers, strings, vectors, and procedures,
4765 @c In some implementations the empty list counts as false, contrary
4767 @c Nonetheless a few examples in this report assume that the
4768 @c empty list counts as true, as in \cite{IEEEScheme}.
4771 @c \begin{rationale}
4772 @c For historical reasons some implementations regard \schfalse{} and the
4773 @c empty list as the same object. These implementations therefore cannot
4774 @c make the empty list count as true in conditional expressions.
4780 Programmers accustomed to other dialects of Lisp should be aware that
4781 Scheme distinguishes both @t{#f} and the empty list
4782 @cindex @w{empty list}
4783 from the symbol @code{nil}.
4788 Boolean constants evaluate to themselves, so they do not need to be quoted
4803 @deffn {library procedure} not obj
4805 @samp{Not} returns @t{#t} if @var{obj} is false, and returns
4812 (not (list 3)) ==> #f
4825 @deffn {library procedure} boolean? obj
4827 @samp{Boolean?} returns @t{#t} if @var{obj} is either @t{#t} or
4828 @t{#f} and returns @t{#f} otherwise.
4832 @t{(boolean? #f) ==> #t
4834 (boolean? '()) ==> #f
4842 @node Pairs and lists, Symbols, Booleans, Other data types
4843 @subsection Pairs and lists
4847 A @dfn{pair} (sometimes called a @dfn{dotted pair}) is a
4848 @cindex @w{dotted pair}
4850 record structure with two fields called the car and cdr fields (for
4851 historical reasons). Pairs are created by the procedure @samp{cons}.
4852 The car and cdr fields are accessed by the procedures @samp{car} and
4853 @samp{cdr}. The car and cdr fields are assigned by the procedures
4854 @samp{set-car!} and @samp{set-cdr!}.
4856 Pairs are used primarily to represent lists. A list can
4857 be defined recursively as either the empty list or a pair whose
4858 @cindex @w{empty list}
4859 cdr is a list. More precisely, the set of lists is defined as the smallest
4860 set @var{X} such that
4867 The empty list is in @var{X}.
4869 If @var{list} is in @var{X}, then any pair whose cdr field contains
4870 @var{list} is also in @var{X}.
4875 The objects in the car fields of successive pairs of a list are the
4876 elements of the list. For example, a two-element list is a pair whose car
4877 is the first element and whose cdr is a pair whose car is the second element
4878 and whose cdr is the empty list. The length of a list is the number of
4879 elements, which is the same as the number of pairs.
4881 The empty list is a special object of its own type
4882 @cindex @w{empty list}
4883 (it is not a pair); it has no elements and its length is zero.
4888 The above definitions imply that all lists have finite length and are
4889 terminated by the empty list.
4893 The most general notation (external representation) for Scheme pairs is
4894 the ``dotted'' notation @w{@samp{(@var{c1} .@: @var{c2})}} where
4895 @var{c1} is the value of the car field and @var{c2} is the value of the
4896 cdr field. For example @samp{(4 .@: 5)} is a pair whose car is 4 and whose
4897 cdr is 5. Note that @samp{(4 .@: 5)} is the external representation of a
4898 pair, not an expression that evaluates to a pair.
4900 A more streamlined notation can be used for lists: the elements of the
4901 list are simply enclosed in parentheses and separated by spaces. The
4902 empty list is written @t{()} . For example,
4903 @cindex @w{empty list}
4918 (a . (b . (c . (d . (e . ())))))
4923 are equivalent notations for a list of symbols.
4925 A chain of pairs not ending in the empty list is called an
4926 @dfn{improper list}. Note that an improper list is not a list.
4927 @cindex @w{improper list}
4928 The list and dotted notations can be combined to represent
4949 Whether a given pair is a list depends upon what is stored in the cdr
4950 field. When the @code{set-cdr!} procedure is used, an object can be a
4951 @vindex @w{set-cdr!}
4952 list one moment and not the next:
4957 (define x (list 'a 'b 'c))
4961 (set-cdr! x 4) ==> @emph{unspecified}
4966 (set-cdr! x x) ==> @emph{unspecified}
4972 @c It is often convenient to speak of a homogeneous list of objects
4973 @c of some particular data type, as for example \hbox{\cf (1 2 3)} is a list of
4974 @c integers. To be more precise, suppose \var{D} is some data type. (Any
4975 @c predicate defines a data type consisting of those objects of which the
4976 @c predicate is true.) Then
4979 @c \item The empty list is a list of \var{D}.
4980 @c \item If \var{list} is a list of \var{D}, then any pair whose cdr is
4981 @c \var{list} and whose car is an element of the data type \var{D} is also a
4983 @c \item There are no other lists of \var{D}.
4986 Within literal expressions and representations of objects read by the
4987 @code{read} procedure, the forms @t{'}@r{<datum>},
4990 @t{`}@r{<datum>}, @t{,}@r{<datum>}, and
4992 @t{,@@}@r{<datum>} denote two-ele@-ment lists whose first elements are
4993 the symbols @code{quote}, @code{quasiquote}, @w{@code{unquote}}, and
4995 @vindex @w{quasiquote}
4997 @code{unquote-splicing}, respectively. The second element in each case
4998 @vindex @w{unquote-splicing}
4999 is @r{<datum>}. This convention is supported so that arbitrary Scheme
5000 programs may be represented as lists.
5002 Can or need this be stated
5005 That is, according to Scheme's grammar, every
5006 <expression> is also a <datum> (see section @pxref{External representation}).
5007 Among other things, this permits the use of the @samp{read} procedure to
5008 parse Scheme programs. See section @ref{External representations}.
5012 @deffn {procedure} pair? obj
5014 @samp{Pair?} returns @t{#t} if @var{obj} is a pair, and otherwise
5019 @t{(pair? '(a . b)) ==> #t
5020 (pair? '(a b c)) ==> #t
5022 (pair? '#(a b)) ==> #f
5030 @deffn {procedure} cons obj1 obj2
5032 Returns a newly allocated pair whose car is @var{obj1} and whose cdr is
5033 @var{obj2}. The pair is guaranteed to be different (in the sense of
5034 @samp{eqv?}) from every existing object.
5038 @t{(cons 'a '()) ==> (a)
5039 (cons '(a) '(b c d)) ==> ((a) b c d)
5040 (cons "a" '(b c)) ==> ("a" b c)
5041 (cons 'a 3) ==> (a . 3)
5042 (cons '(a b) 'c) ==> ((a b) . c)
5050 @deffn {procedure} car pair
5053 @var{Pair} must be a pair.
5056 Returns the contents of the car field of @var{pair}. Note that it is an
5057 error to take the car of the empty list.
5058 @cindex @w{empty list}
5062 @t{(car '(a b c)) ==> a
5063 (car '((a) b c d)) ==> (a)
5064 (car '(1 . 2)) ==> 1
5065 (car '()) ==> @emph{error}
5074 @deffn {procedure} cdr pair
5077 @var{Pair} must be a pair.
5080 Returns the contents of the cdr field of @var{pair}.
5081 Note that it is an error to take the cdr of the empty list.
5085 @t{(cdr '((a) b c d)) ==> (b c d)
5086 (cdr '(1 . 2)) ==> 2
5087 (cdr '()) ==> @emph{error}
5096 @deffn {procedure} set-car! pair obj
5099 @var{Pair} must be a pair.
5102 Stores @var{obj} in the car field of @var{pair}.
5103 The value returned by @samp{set-car!} is unspecified.
5105 @c This procedure can be very confusing if used indiscriminately.
5109 @t{(define (f) (list 'not-a-constant-list))
5110 (define (g) '(constant-list))
5111 (set-car! (f) 3) ==> @emph{unspecified}
5112 (set-car! (g) 3) ==> @emph{error}
5121 @deffn {procedure} set-cdr! pair obj
5124 @var{Pair} must be a pair.
5127 Stores @var{obj} in the cdr field of @var{pair}.
5128 The value returned by @samp{set-cdr!} is unspecified.
5130 @c This procedure can be very confusing if used indiscriminately.
5139 @deffn {library procedure} caar pair
5140 @deffnx {library procedure} cadr pair
5142 @deffnx { @w{ @dots{}}} @w{ @dots{}}
5144 @deffnx {library procedure} cdddar pair
5145 @deffnx {library procedure} cddddr pair
5147 These procedures are compositions of @samp{car} and @samp{cdr}, where
5148 for example @samp{caddr} could be defined by
5152 @t{(define caddr (lambda (x) (car (cdr (cdr x)))))@r{.}
5157 Arbitrary compositions, up to four deep, are provided. There are
5158 twenty-eight of these procedures in all.
5164 @deffn {library procedure} null? obj
5166 Returns @t{#t} if @var{obj} is the empty list,
5167 @cindex @w{empty list}
5168 otherwise returns @t{#f}.
5171 @c In implementations in which the empty
5172 @c list is the same as \schfalse{}, {\cf null?} will return \schtrue{}
5173 @c if \var{obj} is \schfalse{}.
5179 @deffn {library procedure} list? obj
5181 Returns @t{#t} if @var{obj} is a list, otherwise returns @t{#f}.
5182 By definition, all lists have finite length and are terminated by
5187 @t{ (list? '(a b c)) ==> #t
5189 (list? '(a . b)) ==> #f
5190 (let ((x (list 'a)))
5200 @deffn {library procedure} list @var{obj} @dots{},
5202 Returns a newly allocated list of its arguments.
5206 @t{(list 'a (+ 3 4) 'c) ==> (a 7 c)
5215 @deffn {library procedure} length list
5218 @var{List} must be a list.
5221 Returns the length of @var{list}.
5225 @t{(length '(a b c)) ==> 3
5226 (length '(a (b) (c d e))) ==> 3
5235 @deffn {library procedure} append list @dots{},
5238 All @var{list}s should be lists.
5241 Returns a list consisting of the elements of the first @var{list}
5242 followed by the elements of the other @var{list}s.
5246 @t{(append '(x) '(y)) ==> (x y)
5247 (append '(a) '(b c d)) ==> (a b c d)
5248 (append '(a (b)) '((c))) ==> (a (b) (c))
5253 The resulting list is always newly allocated, except that it shares
5254 structure with the last @var{list} argument. The last argument may
5255 actually be any object; an improper list results if the last argument is not a
5258 This is pretty awkward. I should get Bartley to fix this.
5264 @t{(append '(a b) '(c . d)) ==> (a b c . d)
5265 (append '() 'a) ==> a
5273 @deffn {library procedure} reverse list
5276 @var{List} must be a list.
5279 Returns a newly allocated list consisting of the elements of @var{list}
5284 @t{(reverse '(a b c)) ==> (c b a)
5285 (reverse '(a (b c) d (e (f))))
5286 ==> ((e (f)) d (b c) a)
5294 @deffn {library procedure} list-tail list @var{k}
5296 Returns the sublist of @var{list} obtained by omitting the first @var{k}
5297 elements. It is an error if @var{list} has fewer than @var{k} elements.
5298 @samp{List-tail} could be defined by
5302 @t{(define list-tail
5306 (list-tail (cdr x) (- k 1)))))
5314 @deffn {library procedure} list-ref list @var{k}
5316 Returns the @var{k}th element of @var{list}. (This is the same
5317 as the car of @t{(list-tail @var{list} @var{k})}.)
5318 It is an error if @var{list} has fewer than @var{k} elements.
5322 @t{(list-ref '(a b c d) 2) ==> c
5323 (list-ref '(a b c d)
5324 (inexact->exact (round 1.8)))
5333 @c \proto{last-pair}{ list}{library procedure}}
5335 @c Returns the last pair in the nonempty, possibly improper, list \var{list}.
5336 @c {\cf Last-pair} could be defined by
5339 @c (define last-pair
5341 @c (if (pair? (cdr x))
5342 @c (last-pair (cdr x))
5350 @deffn {library procedure} memq obj list
5351 @deffnx {library procedure} memv obj list
5352 @deffnx {library procedure} member obj list
5354 These procedures return the first sublist of @var{list} whose car is
5355 @var{obj}, where the sublists of @var{list} are the non-empty lists
5356 returned by @t{(list-tail @var{list} @var{k})} for @var{k} less
5357 than the length of @var{list}. If
5358 @var{obj} does not occur in @var{list}, then @t{#f} (not the empty list) is
5359 returned. @samp{Memq} uses @samp{eq?} to compare @var{obj} with the elements of
5360 @var{list}, while @samp{memv} uses @samp{eqv?} and @samp{member} uses @samp{equal?}.
5364 @t{(memq 'a '(a b c)) ==> (a b c)
5365 (memq 'b '(a b c)) ==> (b c)
5366 (memq 'a '(b c d)) ==> #f
5367 (memq (list 'a) '(b (a) c)) ==> #f
5369 '(b (a) c)) ==> ((a) c)
5370 (memq 101 '(100 101 102)) ==> @emph{unspecified}
5371 (memv 101 '(100 101 102)) ==> (101 102)
5380 @deffn {library procedure} assq obj alist
5381 @deffnx {library procedure} assv obj alist
5382 @deffnx {library procedure} assoc obj alist
5384 @var{Alist} (for ``association list'') must be a list of
5385 pairs. These procedures find the first pair in @var{alist} whose car field is @var{obj},
5386 and returns that pair. If no pair in @var{alist} has @var{obj} as its
5387 car, then @t{#f} (not the empty list) is returned. @samp{Assq} uses
5388 @samp{eq?} to compare @var{obj} with the car fields of the pairs in @var{alist},
5389 while @samp{assv} uses @samp{eqv?} and @samp{assoc} uses @samp{equal?}.
5393 @t{(define e '((a 1) (b 2) (c 3)))
5394 (assq 'a e) ==> (a 1)
5395 (assq 'b e) ==> (b 2)
5397 (assq (list 'a) '(((a)) ((b)) ((c))))
5399 (assoc (list 'a) '(((a)) ((b)) ((c))))
5401 (assq 5 '((2 3) (5 7) (11 13)))
5402 ==> @emph{unspecified}
5403 (assv 5 '((2 3) (5 7) (11 13)))
5413 Although they are ordinarily used as predicates,
5414 @samp{memq}, @samp{memv}, @samp{member}, @samp{assq}, @samp{assv}, and @samp{assoc} do not
5415 have question marks in their names because they return useful values rather
5416 than just @t{#t} or @t{#f}.
5422 @node Symbols, Characters, Pairs and lists, Other data types
5427 Symbols are objects whose usefulness rests on the fact that two
5428 symbols are identical (in the sense of @samp{eqv?}) if and only if their
5429 names are spelled the same way. This is exactly the property needed to
5430 represent identifiers in programs, and so most
5431 @cindex @w{identifier}
5432 implementations of Scheme use them internally for that purpose. Symbols
5433 are useful for many other applications; for instance, they may be used
5434 the way enumerated values are used in Pascal.
5436 The rules for writing a symbol are exactly the same as the rules for
5437 writing an identifier; see sections @ref{Identifiers}
5438 and @ref{Lexical structure}.
5440 It is guaranteed that any symbol that has been returned as part of
5441 a literal expression, or read using the @samp{read} procedure, and
5442 subsequently written out using the @samp{write} procedure, will read back
5443 in as the identical symbol (in the sense of @samp{eqv?}). The
5444 @samp{string->symbol} procedure, however, can create symbols for
5445 which this write/read invariance may not hold because their names
5446 contain special characters or letters in the non-standard case.
5451 Some implementations of Scheme have a feature known as ``slashification''
5452 in order to guarantee write/read invariance for all symbols, but
5453 historically the most important use of this feature has been to
5454 compensate for the lack of a string data type.
5456 Some implementations also have ``uninterned symbols'', which
5457 defeat write/read invariance even in implementations with slashification,
5458 and also generate exceptions to the rule that two symbols are the same
5459 if and only if their names are spelled the same.
5465 @deffn {procedure} symbol? obj
5467 Returns @t{#t} if @var{obj} is a symbol, otherwise returns @t{#f}.
5471 @t{(symbol? 'foo) ==> #t
5472 (symbol? (car '(a b))) ==> #t
5473 (symbol? "bar") ==> #f
5474 (symbol? 'nil) ==> #t
5475 (symbol? '()) ==> #f
5484 @deffn {procedure} symbol->string symbol
5486 Returns the name of @var{symbol} as a string. If the symbol was part of
5487 an object returned as the value of a literal expression
5488 (section @pxref{Literal expressions}) or by a call to the @samp{read} procedure,
5489 and its name contains alphabetic characters, then the string returned
5490 will contain characters in the implementation's preferred standard
5491 case---some implementations will prefer upper case, others lower case.
5492 If the symbol was returned by @samp{string->symbol}, the case of
5493 characters in the string returned will be the same as the case in the
5494 string that was passed to @samp{string->symbol}. It is an error
5495 to apply mutation procedures like @code{string-set!} to strings returned
5496 @vindex @w{string-set!}
5499 The following examples assume that the implementation's standard case is
5504 @t{(symbol->string 'flying-fish)
5506 (symbol->string 'Martin) ==> "martin"
5508 (string->symbol "Malvina"))
5517 @deffn {procedure} string->symbol string
5519 Returns the symbol whose name is @var{string}. This procedure can
5520 create symbols with names containing special characters or letters in
5521 the non-standard case, but it is usually a bad idea to create such
5522 symbols because in some implementations of Scheme they cannot be read as
5523 themselves. See @samp{symbol->string}.
5525 The following examples assume that the implementation's standard case is
5530 @t{(eq? 'mISSISSIppi 'mississippi)
5532 (string->symbol "mISSISSIppi")
5534 @r{}the symbol with name "mISSISSIppi"
5535 (eq? 'bitBlt (string->symbol "bitBlt"))
5539 (symbol->string 'JollyWog)))
5541 (string=? "K. Harper, M.D."
5543 (string->symbol "K. Harper, M.D.")))
5552 @node Characters, Strings, Symbols, Other data types
5553 @subsection Characters
5557 Characters are objects that represent printed characters such as
5559 @c There is no requirement that the data type of
5560 @c characters be disjoint from other data types; implementations are
5561 @c encouraged to have a separate character data type, but may choose to
5562 @c represent characters as integers, strings, or some other type.
5563 Characters are written using the notation #\@r{<character>}
5564 or #\@r{<character name>}.
5569 @center @c begin-tabular
5579 ; the space character
5581 ; the preferred way to write a space
5583 ; the newline character
5591 Case is significant in #\@r{<character>}, but not in
5592 #\@r{<character name>}.
5595 @c allow a linebreak
5596 If @r{<character>} in
5597 #\@r{<character>} is alphabetic, then the character
5598 following @r{<character>} must be a delimiter character such as a
5599 space or parenthesis. This rule resolves the ambiguous case where, for
5600 example, the sequence of characters ``@t{#\ space}''
5601 could be taken to be either a representation of the space character or a
5602 representation of the character ``@t{#\ s}'' followed
5603 by a representation of the symbol ``@t{pace}.''
5609 Characters written in the #\ notation are self-evaluating.
5610 That is, they do not have to be quoted in programs.
5611 @c The \sharpsign\backwhack{}
5612 @c notation is not an essential part of Scheme, however. Even implementations
5613 @c that support the \sharpsign\backwhack{} notation for input do not have to
5614 @c support it for output.
5616 Some of the procedures that operate on characters ignore the
5617 difference between upper case and lower case. The procedures that
5618 ignore case have @w{``@t{-ci}''} (for ``case
5619 insensitive'') embedded in their names.
5623 @deffn {procedure} char? obj
5625 Returns @t{#t} if @var{obj} is a character, otherwise returns @t{#f}.
5631 @deffn {procedure} char=? char1 char2
5632 @deffnx {procedure} char<? char1 char2
5633 @deffnx {procedure} char>? char1 char2
5634 @deffnx {procedure} char<=? char1 char2
5635 @deffnx {procedure} char>=? char1 char2
5639 Both @var{char1} and @var{char2} must be characters.
5642 These procedures impose a total ordering on the set of characters. It
5643 is guaranteed that under this ordering:
5650 The upper case characters are in order. For example, @samp{(char<? #\A #\B)} returns @t{#t}.
5652 The lower case characters are in order. For example, @samp{(char<? #\a #\b)} returns @t{#t}.
5654 The digits are in order. For example, @samp{(char<? #\0 #\9)} returns @t{#t}.
5656 Either all the digits precede all the upper case letters, or vice versa.
5658 Either all the digits precede all the lower case letters, or vice versa.
5663 Some implementations may generalize these procedures to take more than
5664 two arguments, as with the corresponding numerical predicates.
5670 @deffn {library procedure} char-ci=? char1 char2
5671 @deffnx {library procedure} char-ci<? char1 char2
5672 @deffnx {library procedure} char-ci>? char1 char2
5673 @deffnx {library procedure} char-ci<=? char1 char2
5674 @deffnx {library procedure} char-ci>=? char1 char2
5677 Both @var{char1} and @var{char2} must be characters.
5680 These procedures are similar to @samp{char=?} et cetera, but they treat
5681 upper case and lower case letters as the same. For example, @samp{(char-ci=? #\A #\a)} returns @t{#t}. Some
5682 implementations may generalize these procedures to take more than two
5683 arguments, as with the corresponding numerical predicates.
5689 @deffn {library procedure} char-alphabetic? char
5690 @deffnx {library procedure} char-numeric? char
5691 @deffnx {library procedure} char-whitespace? char
5692 @deffnx {library procedure} char-upper-case? letter
5693 @deffnx {library procedure} char-lower-case? letter
5695 These procedures return @t{#t} if their arguments are alphabetic,
5696 numeric, whitespace, upper case, or lower case characters, respectively,
5697 otherwise they return @t{#f}. The following remarks, which are specific to
5698 the ASCII character set, are intended only as a guide: The alphabetic characters
5699 are the 52 upper and lower case letters. The numeric characters are the
5700 ten decimal digits. The whitespace characters are space, tab, line
5701 feed, form feed, and carriage return.
5705 @c %R4%%\begin{entry}{%
5706 @c \proto{char-upper-case?}{ letter}{procedure}
5707 @c \proto{char-lower-case?}{ letter}{procedure}}
5709 @c \domain{\var{Letter} must be an alphabetic character.}
5710 @c These procedures return \schtrue{} if their arguments are upper case or
5711 @c lower case characters, respectively, otherwise they return \schfalse.
5716 @deffn {procedure} char->integer char
5717 @deffnx {procedure} integer->char @var{n}
5719 Given a character, @samp{char->integer} returns an exact integer
5720 representation of the character. Given an exact integer that is the image of
5721 a character under @samp{char->integer}, @samp{integer->char}
5722 returns that character. These procedures implement order-preserving isomorphisms
5723 between the set of characters under the @code{char<=?} ordering and some
5725 subset of the integers under the @samp{<=} ordering. That is, if
5729 @t{(char<=? @var{a} @var{b}) @result{} #t @r{}and (<= @var{x} @var{y}) @result{} #t
5736 and @var{x} and @var{y} are in the domain of
5737 @samp{integer->char}, then
5741 @t{(<= (char->integer @var{a})
5742 (char->integer @var{b})) ==> #t
5744 (char<=? (integer->char @var{x})
5745 (integer->char @var{y})) ==> #t
5754 @deffn {library procedure} char-upcase char
5755 @deffnx {library procedure} char-downcase char
5758 @var{Char} must be a character.
5761 These procedures return a character @var{char2} such that @samp{(char-ci=? @var{char} @var{char2})}. In addition, if @var{char} is
5762 alphabetic, then the result of @samp{char-upcase} is upper case and the
5763 result of @samp{char-downcase} is lower case.
5768 @node Strings, Vectors, Characters, Other data types
5773 Strings are sequences of characters.
5774 @c In some implementations of Scheme
5775 @c they are immutable; other implementations provide destructive procedures
5776 @c such as {\cf string-set!}\ that alter string objects.
5777 Strings are written as sequences of characters enclosed within doublequotes
5778 (@samp{"}). A doublequote can be written inside a string only by escaping
5779 it with a backslash (\), as in
5784 "The word \"recursion\" has many meanings."
5789 A backslash can be written inside a string only by escaping it with another
5790 backslash. Scheme does not specify the effect of a backslash within a
5791 string that is not followed by a doublequote or backslash.
5793 A string constant may continue from one line to the next, but
5794 the exact contents of such a string are unspecified.
5796 @c usually a bad idea because
5797 @c the exact effect may vary from one computer
5798 @c system to another.
5800 The @emph{length} of a string is the number of characters that it
5801 contains. This number is an exact, non-negative integer that is fixed when the
5802 string is created. The @dfn{valid indexes} of a string are the
5803 @cindex @w{valid indexes}
5804 exact non-negative integers less than the length of the string. The first
5805 character of a string has index 0, the second has index 1, and so on.
5807 In phrases such as ``the characters of @var{string} beginning with
5808 index @var{start} and ending with index @var{end},'' it is understood
5809 that the index @var{start} is inclusive and the index @var{end} is
5810 exclusive. Thus if @var{start} and @var{end} are the same index, a null
5811 substring is referred to, and if @var{start} is zero and @var{end} is
5812 the length of @var{string}, then the entire string is referred to.
5814 Some of the procedures that operate on strings ignore the
5815 difference between upper and lower case. The versions that ignore case
5816 have @w{``@samp{-ci}''} (for ``case insensitive'') embedded in their
5821 @deffn {procedure} string? obj
5823 Returns @t{#t} if @var{obj} is a string, otherwise returns @t{#f}.
5828 @deffn {procedure} make-string @var{k}
5829 @deffnx {procedure} make-string @var{k} char
5831 @c \domain{\vr{k} must be a non-negative integer, and \var{char} must be
5833 @samp{Make-string} returns a newly allocated string of
5834 length @var{k}. If @var{char} is given, then all elements of the string
5835 are initialized to @var{char}, otherwise the contents of the
5836 @var{string} are unspecified.
5841 @deffn {library procedure} string char @dots{},
5843 Returns a newly allocated string composed of the arguments.
5848 @deffn {procedure} string-length string
5850 Returns the number of characters in the given @var{string}.
5855 @deffn {procedure} string-ref string @var{k}
5857 @var{k} must be a valid index of @var{string}.
5858 @samp{String-ref} returns character @var{k} of @var{string} using zero-origin indexing.
5863 @deffn {procedure} string-set! string k char
5866 @c \var{String} must be a string,
5867 @var{k} must be a valid index of @var{string}
5868 @c , and \var{char} must be a character
5870 @samp{String-set!} stores @var{char} in element @var{k} of @var{string}
5871 and returns an unspecified value.
5876 @t{(define (f) (make-string 3 #\*))
5878 (string-set! (f) 0 #\?) ==> @emph{unspecified}
5879 (string-set! (g) 0 #\?) ==> @emph{error}
5880 (string-set! (symbol->string 'immutable)
5882 #\?) ==> @emph{error}
5891 @deffn {library procedure} string=? string1 string2
5892 @deffnx {library procedure} string-ci=? string1 string2
5894 Returns @t{#t} if the two strings are the same length and contain the same
5895 characters in the same positions, otherwise returns @t{#f}.
5896 @samp{String-ci=?} treats
5897 upper and lower case letters as though they were the same character, but
5898 @samp{string=?} treats upper and lower case as distinct characters.
5904 @deffn {library procedure} string<? string1 string2
5905 @deffnx {library procedure} string>? string1 string2
5906 @deffnx {library procedure} string<=? string1 string2
5907 @deffnx {library procedure} string>=? string1 string2
5908 @deffnx {library procedure} string-ci<? string1 string2
5909 @deffnx {library procedure} string-ci>? string1 string2
5910 @deffnx {library procedure} string-ci<=? string1 string2
5911 @deffnx {library procedure} string-ci>=? string1 string2
5913 These procedures are the lexicographic extensions to strings of the
5914 corresponding orderings on characters. For example, @samp{string<?} is
5915 the lexicographic ordering on strings induced by the ordering
5916 @samp{char<?} on characters. If two strings differ in length but
5917 are the same up to the length of the shorter string, the shorter string
5918 is considered to be lexicographically less than the longer string.
5920 Implementations may generalize these and the @samp{string=?} and
5921 @samp{string-ci=?} procedures to take more than two arguments, as with
5922 the corresponding numerical predicates.
5928 @deffn {library procedure} substring string start end
5930 @var{String} must be a string, and @var{start} and @var{end}
5931 must be exact integers satisfying
5934 @center 0 <= @var{start} <= @var{end} <= @w{@t{(string-length @var{string})@r{.}}}
5936 @samp{Substring} returns a newly allocated string formed from the characters of
5937 @var{string} beginning with index @var{start} (inclusive) and ending with index
5938 @var{end} (exclusive).
5943 @deffn {library procedure} string-append @var{string} @dots{},
5945 Returns a newly allocated string whose characters form the concatenation of the
5952 @deffn {library procedure} string->list string
5953 @deffnx {library procedure} list->string list
5955 @samp{String->list} returns a newly allocated list of the
5956 characters that make up the given string. @samp{List->string}
5957 returns a newly allocated string formed from the characters in the list
5958 @var{list}, which must be a list of characters. @samp{String->list}
5959 and @samp{list->string} are
5960 inverses so far as @samp{equal?} is concerned.
5961 @c Implementations that provide
5962 @c destructive operations on strings should ensure that the result of
5963 @c {\cf list\coerce{}string} is newly allocated.
5969 @deffn {library procedure} string-copy string
5971 Returns a newly allocated copy of the given @var{string}.
5977 @deffn {library procedure} string-fill! string char
5979 Stores @var{char} in every element of the given @var{string} and returns an
5986 @node Vectors, , Strings, Other data types
5991 Vectors are heterogenous structures whose elements are indexed
5992 by integers. A vector typically occupies less space than a list
5993 of the same length, and the average time required to access a randomly
5994 chosen element is typically less for the vector than for the list.
5996 The @emph{length} of a vector is the number of elements that it
5997 contains. This number is a non-negative integer that is fixed when the
5998 vector is created. The @emph{valid indexes} of a
5999 @cindex @w{valid indexes}
6000 vector are the exact non-negative integers less than the length of the
6001 vector. The first element in a vector is indexed by zero, and the last
6002 element is indexed by one less than the length of the vector.
6004 Vectors are written using the notation @t{#(@var{obj} @dots{},)}.
6005 For example, a vector of length 3 containing the number zero in element
6006 0, the list @samp{(2 2 2 2)} in element 1, and the string @samp{"Anna"} in
6007 element 2 can be written as following:
6012 #(0 (2 2 2 2) "Anna")
6017 Note that this is the external representation of a vector, not an
6018 expression evaluating to a vector. Like list constants, vector
6019 constants must be quoted:
6024 '#(0 (2 2 2 2) "Anna")
6025 ==> #(0 (2 2 2 2) "Anna")
6031 Pitman sez: The visual similarity to lists is bound to be confusing
6032 to some. Elaborate on the distinction.
6038 @deffn {procedure} vector? obj
6040 Returns @t{#t} if @var{obj} is a vector, otherwise returns @t{#f}.
6045 @deffn {procedure} make-vector k
6046 @deffnx {procedure} make-vector k fill
6048 Returns a newly allocated vector of @var{k} elements. If a second
6049 argument is given, then each element is initialized to @var{fill}.
6050 Otherwise the initial contents of each element is unspecified.
6056 @deffn {library procedure} vector obj @dots{},
6058 Returns a newly allocated vector whose elements contain the given
6059 arguments. Analogous to @samp{list}.
6063 @t{(vector 'a 'b 'c) ==> #(a b c)
6071 @deffn {procedure} vector-length vector
6073 Returns the number of elements in @var{vector} as an exact integer.
6078 @deffn {procedure} vector-ref vector k
6080 @var{k} must be a valid index of @var{vector}.
6081 @samp{Vector-ref} returns the contents of element @var{k} of
6086 @t{(vector-ref '#(1 1 2 3 5 8 13 21)
6089 (vector-ref '#(1 1 2 3 5 8 13 21)
6090 (let ((i (round (* 2 (acos -1)))))
6102 @deffn {procedure} vector-set! vector k obj
6104 @var{k} must be a valid index of @var{vector}.
6105 @samp{Vector-set!} stores @var{obj} in element @var{k} of @var{vector}.
6106 The value returned by @samp{vector-set!} is unspecified.
6111 @t{(let ((vec (vector 0 '(2 2 2 2) "Anna")))
6112 (vector-set! vec 1 '("Sue" "Sue"))
6114 ==> #(0 ("Sue" "Sue") "Anna")
6116 (vector-set! '#(0 1 2) 1 "doe")
6117 ==> @emph{error} ; constant vector
6125 @deffn {library procedure} vector->list vector
6126 @deffnx {library procedure} list->vector list
6128 @samp{Vector->list} returns a newly allocated list of the objects contained
6129 in the elements of @var{vector}. @samp{List->vector} returns a newly
6130 created vector initialized to the elements of the list @var{list}.
6134 @t{(vector->list '#(dah dah didah))
6136 (list->vector '(dididit dah))
6145 @deffn {library procedure} vector-fill! vector fill
6147 Stores @var{fill} in every element of @var{vector}.
6148 The value returned by @samp{vector-fill!} is unspecified.
6154 @node Control features, Eval, Other data types, Standard procedures
6155 @section Control features
6159 @c Intro flushed; not very a propos any more.
6160 @c Procedures should be discussed somewhere, however.
6162 This chapter describes various primitive procedures which control the
6163 flow of program execution in special ways.
6164 The @samp{procedure?} predicate is also described here.
6167 @t{Procedure?} doesn't belong in a section with the name
6168 ``control features.'' What to do?
6173 @deffn {procedure} procedure? obj
6175 Returns @t{#t} if @var{obj} is a procedure, otherwise returns @t{#f}.
6179 @t{(procedure? car) ==> #t
6180 (procedure? 'car) ==> #f
6181 (procedure? (lambda (x) (* x x)))
6183 (procedure? '(lambda (x) (* x x)))
6185 (call-with-current-continuation procedure?)
6195 @deffn {procedure} apply proc arg1 @dots{} args
6197 @var{Proc} must be a procedure and @var{args} must be a list.
6198 Calls @var{proc} with the elements of the list
6199 @samp{(append (list @var{arg1} @dots{},) @var{args})} as the actual
6204 @t{(apply + (list 3 4)) ==> 7
6209 (f (apply g args)))))
6211 ((compose sqrt *) 12 75) ==> 30
6219 @deffn {library procedure} map proc list1 list2 @dots{},
6221 The @var{list}s must be lists, and @var{proc} must be a
6222 procedure taking as many arguments as there are @i{list}s
6223 and returning a single value. If more
6224 than one @var{list} is given, then they must all be the same length.
6225 @samp{Map} applies @var{proc} element-wise to the elements of the
6226 @var{list}s and returns a list of the results, in order.
6227 The dynamic order in which @var{proc} is applied to the elements of the
6228 @var{list}s is unspecified.
6232 @t{(map cadr '((a b) (d e) (g h)))
6235 (map (lambda (n) (expt n n))
6237 ==> (1 4 27 256 3125)
6239 (map + '(1 2 3) '(4 5 6)) ==> (5 7 9)
6242 (map (lambda (ignored)
6243 (set! count (+ count 1))
6245 '(a b))) ==> (1 2) @var{or} (2 1)
6254 @deffn {library procedure} for-each proc list1 list2 @dots{},
6256 The arguments to @samp{for-each} are like the arguments to @samp{map}, but
6257 @samp{for-each} calls @var{proc} for its side effects rather than for its
6258 values. Unlike @samp{map}, @samp{for-each} is guaranteed to call @var{proc} on
6259 the elements of the @var{list}s in order from the first element(s) to the
6260 last, and the value returned by @samp{for-each} is unspecified.
6264 @t{(let ((v (make-vector 5)))
6265 (for-each (lambda (i)
6266 (vector-set! v i (* i i)))
6268 v) ==> #(0 1 4 9 16)
6277 @deffn {library procedure} force promise
6279 Forces the value of @var{promise} (see @code{delay},
6281 section @pxref{Delayed evaluation}). If no value has been computed for
6283 the promise, then a value is computed and returned. The value of the
6284 promise is cached (or ``memoized'') so that if it is forced a second
6285 time, the previously computed value is returned.
6286 @c without any recomputation.
6287 @c [As pointed out by Marc Feeley, the "without any recomputation"
6288 @c isn't necessarily true. --Will]
6292 @t{(force (delay (+ 1 2))) ==> 3
6293 (let ((p (delay (+ 1 2))))
6294 (list (force p) (force p)))
6300 (cons n (delay (next (+ n 1)))))))
6304 (lambda (stream) (force (cdr stream))))
6306 (head (tail (tail a-stream)))
6312 @samp{Force} and @samp{delay} are mainly intended for programs written in
6313 functional style. The following examples should not be considered to
6314 illustrate good programming style, but they illustrate the property that
6315 only one value is computed for a promise, no matter how many times it is
6317 @c the value of a promise is computed at most once.
6318 @c [As pointed out by Marc Feeley, it may be computed more than once,
6319 @c but as I observed we can at least insist that only one value be
6326 (delay (begin (set! count (+ count 1))
6333 p ==> @i{}a promise, still
6340 Here is a possible implementation of @samp{delay} and @samp{force}.
6341 Promises are implemented here as procedures of no arguments,
6342 and @samp{force} simply calls its argument:
6353 We define the expression
6357 @t{(delay @r{<expression>})
6362 to have the same meaning as the procedure call
6366 @t{(make-promise (lambda () @r{<expression>}))@r{}
6375 @t{(define-syntax delay
6378 (make-promise (lambda () expression))))),
6383 where @samp{make-promise} is defined as follows:
6386 @c (define make-promise
6388 @c (let ((already-run? \schfalse) (result \schfalse))
6390 @c (cond ((not already-run?)
6391 @c (set! result (proc))
6392 @c (set! already-run? \schtrue)))
6398 @t{(define make-promise
6400 (let ((result-ready? #f)
6408 (begin (set! result-ready? #t)
6418 A promise may refer to its own value, as in the last example above.
6419 Forcing such a promise may cause the promise to be forced a second time
6420 before the value of the first force has been computed.
6421 This complicates the definition of @samp{make-promise}.
6425 Various extensions to this semantics of @samp{delay} and @samp{force}
6426 are supported in some implementations:
6433 Calling @samp{force} on an object that is not a promise may simply
6437 It may be the case that there is no means by which a promise can be
6438 operationally distinguished from its forced value. That is, expressions
6439 like the following may evaluate to either @t{#t} or to @t{#f},
6440 depending on the implementation:
6444 @t{(eqv? (delay 1) 1) ==> @emph{unspecified}
6445 (pair? (delay (cons 1 2))) ==> @emph{unspecified}
6451 Some implementations may implement ``implicit forcing,'' where
6452 the value of a promise is forced by primitive procedures like @samp{cdr}
6457 @t{(+ (delay (* 3 7)) 13) ==> 34
6467 @deffn {procedure} call-with-current-continuation proc
6469 @var{Proc} must be a procedure of one
6470 argument. The procedure @samp{call-with-current-continuation} packages
6471 up the current continuation (see the rationale below) as an ``escape
6472 procedure'' and passes it as an argument to
6473 @cindex @w{escape procedure}
6474 @var{proc}. The escape procedure is a Scheme procedure that, if it is
6475 later called, will abandon whatever continuation is in effect at that later
6476 time and will instead use the continuation that was in effect
6477 when the escape procedure was created. Calling the escape procedure
6478 may cause the invocation of @var{before} and @var{after} thunks installed using
6479 @code{dynamic-wind}.
6480 @vindex @w{dynamic-wind}
6482 The escape procedure accepts the same number of arguments as the continuation to
6483 the original call to @t{call-with-current-continuation}.
6484 Except for continuations created by the @samp{call-with-values}
6485 procedure, all continuations take exactly one value. The
6486 effect of passing no value or more than one value to continuations
6487 that were not created by @t{call-with-values} is unspecified.
6489 The escape procedure that is passed to @var{proc} has
6490 unlimited extent just like any other procedure in Scheme. It may be stored
6491 in variables or data structures and may be called as many times as desired.
6493 The following examples show only the most common ways in which
6494 @samp{call-with-current-continuation} is used. If all real uses were as
6495 simple as these examples, there would be no need for a procedure with
6496 the power of @samp{call-with-current-continuation}.
6500 @t{(call-with-current-continuation
6502 (for-each (lambda (x)
6505 '(54 0 37 -3 245 19))
6510 (call-with-current-continuation
6514 (cond ((null? obj) 0)
6516 (+ (r (cdr obj)) 1))
6517 (else (return #f))))))
6520 (list-length '(1 2 3 4)) ==> 4
6522 (list-length '(a b . c)) ==> #f
6531 A common use of @samp{call-with-current-continuation} is for
6532 structured, non-local exits from loops or procedure bodies, but in fact
6533 @samp{call-with-current-continuation} is extremely useful for implementing a
6534 wide variety of advanced control structures.
6536 Whenever a Scheme expression is evaluated there is a
6537 @dfn{continuation} wanting the result of the expression. The continuation
6538 @cindex @w{continuation}
6539 represents an entire (default) future for the computation. If the expression is
6540 evaluated at top level, for example, then the continuation might take the
6541 result, print it on the screen, prompt for the next input, evaluate it, and
6542 so on forever. Most of the time the continuation includes actions
6543 specified by user code, as in a continuation that will take the result,
6544 multiply it by the value stored in a local variable, add seven, and give
6545 the answer to the top level continuation to be printed. Normally these
6546 ubiquitous continuations are hidden behind the scenes and programmers do not
6547 think much about them. On rare occasions, however, a programmer may
6548 need to deal with continuations explicitly.
6549 @samp{Call-with-current-continuation} allows Scheme programmers to do
6550 that by creating a procedure that acts just like the current
6553 Most programming languages incorporate one or more special-purpose
6554 escape constructs with names like @t{exit}, @w{@samp{return}}, or
6555 even @t{goto}. In 1965, however, Peter Landin [Landin65]
6556 invented a general purpose escape operator called the J-operator. John
6557 Reynolds [Reynolds72] described a simpler but equally powerful
6558 construct in 1972. The @samp{catch} special form described by Sussman
6559 and Steele in the 1975 report on Scheme is exactly the same as
6560 Reynolds's construct, though its name came from a less general construct
6561 in MacLisp. Several Scheme implementors noticed that the full power of the
6562 @code{catch} construct could be provided by a procedure instead of by a
6564 special syntactic construct, and the name
6565 @samp{call-with-current-continuation} was coined in 1982. This name is
6566 descriptive, but opinions differ on the merits of such a long name, and
6567 some people use the name @code{call/cc} instead.
6575 @deffn {procedure} values obj @dots{}
6577 Delivers all of its arguments to its continuation.
6578 Except for continuations created by the @code{call-with-values}
6579 @vindex @w{call-with-values}
6580 procedure, all continuations take exactly one value.
6581 @t{Values} might be defined as follows:
6584 @t{(define (values . things)
6585 (call-with-current-continuation
6586 (lambda (cont) (apply cont things))))
6594 @deffn {procedure} call-with-values producer consumer
6596 Calls its @var{producer} argument with no values and
6597 a continuation that, when passed some values, calls the
6598 @var{consumer} procedure with those values as arguments.
6599 The continuation for the call to @var{consumer} is the
6600 continuation of the call to @t{call-with-values}.
6604 @t{(call-with-values (lambda () (values 4 5))
6608 (call-with-values * -) ==> -1
6616 @deffn {procedure} dynamic-wind before thunk after
6618 Calls @var{thunk} without arguments, returning the result(s) of this call.
6619 @var{Before} and @var{after} are called, also without arguments, as required
6620 by the following rules (note that in the absence of calls to continuations
6621 captured using @code{call-with-current-continuation} the three arguments are
6622 @vindex @w{call-with-current-continuation}
6623 called once each, in order). @var{Before} is called whenever execution
6624 enters the dynamic extent of the call to @var{thunk} and @var{after} is called
6625 whenever it exits that dynamic extent. The dynamic extent of a procedure
6626 call is the period between when the call is initiated and when it
6627 returns. In Scheme, because of @samp{call-with-current-continuation}, the
6628 dynamic extent of a call may not be a single, connected time period.
6629 It is defined as follows:
6635 The dynamic extent is entered when execution of the body of the
6636 called procedure begins.
6639 The dynamic extent is also entered when execution is not within
6640 the dynamic extent and a continuation is invoked that was captured
6641 (using @samp{call-with-current-continuation}) during the dynamic extent.
6644 It is exited when the called procedure returns.
6647 It is also exited when execution is within the dynamic extent and
6648 a continuation is invoked that was captured while not within the
6654 If a second call to @samp{dynamic-wind} occurs within the dynamic extent of the
6655 call to @var{thunk} and then a continuation is invoked in such a way that the
6656 @var{after}s from these two invocations of @samp{dynamic-wind} are both to be
6657 called, then the @var{after} associated with the second (inner) call to
6658 @samp{dynamic-wind} is called first.
6660 If a second call to @samp{dynamic-wind} occurs within the dynamic extent of the
6661 call to @var{thunk} and then a continuation is invoked in such a way that the
6662 @var{before}s from these two invocations of @samp{dynamic-wind} are both to be
6663 called, then the @var{before} associated with the first (outer) call to
6664 @samp{dynamic-wind} is called first.
6666 If invoking a continuation requires calling the @var{before} from one call
6667 to @samp{dynamic-wind} and the @var{after} from another, then the @var{after}
6670 The effect of using a captured continuation to enter or exit the dynamic
6671 extent of a call to @var{before} or @var{after} is undefined.
6677 (let ((add (lambda (s)
6678 (set! path (cons s path)))))
6680 (lambda () (add 'connect))
6682 (add (call-with-current-continuation
6686 (lambda () (add 'disconnect)))
6687 (if (< (length path) 4)
6691 ==> (connect talk1 disconnect
6692 connect talk2 disconnect)
6698 @node Eval, Input and output, Control features, Standard procedures
6703 @deffn {procedure} eval expression environment-specifier
6705 Evaluates @var{expression} in the specified environment and returns its value.
6706 @var{Expression} must be a valid Scheme expression represented as data,
6707 and @var{environment-specifier} must be a value returned by one of the
6708 three procedures described below.
6709 Implementations may extend @samp{eval} to allow non-expression programs
6710 (definitions) as the first argument and to allow other
6711 values as environments, with the restriction that @samp{eval} is not
6712 allowed to create new bindings in the environments associated with
6713 @samp{null-environment} or @samp{scheme-report-environment}.
6717 @t{(eval '(* 7 3) (scheme-report-environment 5))
6720 (let ((f (eval '(lambda (f x) (f x x))
6721 (null-environment 5))))
6731 @deffn {procedure} scheme-report-environment version
6732 @deffnx {procedure} null-environment version
6734 @var{Version} must be the exact integer @samp{5},
6735 corresponding to this revision of the Scheme report (the
6736 Revised^5 Report on Scheme).
6737 @samp{Scheme-report-environment} returns a specifier for an
6738 environment that is empty except for all bindings defined in
6739 this report that are either required or both optional and
6740 supported by the implementation. @samp{Null-environment} returns
6741 a specifier for an environment that is empty except for the
6742 (syntactic) bindings for all syntactic keywords defined in
6743 this report that are either required or both optional and
6744 supported by the implementation.
6746 Other values of @var{version} can be used to specify environments
6747 matching past revisions of this report, but their support is not
6748 required. An implementation will signal an error if @var{version}
6749 is neither @samp{5} nor another value supported by
6752 The effect of assigning (through the use of @samp{eval}) a variable
6753 bound in a @samp{scheme-report-environment}
6754 (for example @samp{car}) is unspecified. Thus the environments specified
6755 by @samp{scheme-report-environment} may be immutable.
6760 @deffn {optional procedure} interaction-environment
6762 This procedure returns a specifier for the environment that
6763 contains imple@-men@-ta@-tion-defined bindings, typically a superset of
6764 those listed in the report. The intent is that this procedure
6765 will return the environment in which the implementation would evaluate
6766 expressions dynamically typed by the user.
6770 @node Input and output, , Eval, Standard procedures
6771 @section Input and output
6777 * System interface::
6781 @node Ports, Input, Input and output, Input and output
6786 Ports represent input and output devices. To Scheme, an input port is a
6787 Scheme object that can deliver characters upon command, while an output port
6788 is a Scheme object that can accept characters.
6792 Haase: Mention that there are alternatives to files?
6797 @deffn {library procedure} call-with-input-file string proc
6798 @deffnx {library procedure} call-with-output-file string proc
6800 @var{String} should be a string naming a file, and
6801 @var{proc} should be a procedure that accepts one argument.
6802 For @samp{call-with-input-file},
6803 the file should already exist; for
6804 @samp{call-with-output-file},
6805 the effect is unspecified if the file
6806 already exists. These procedures call @var{proc} with one argument: the
6807 port obtained by opening the named file for input or output. If the
6808 file cannot be opened, an error is signalled. If @var{proc} returns,
6809 then the port is closed automatically and the value(s) yielded by the
6810 @var{proc} is(are) returned. If @var{proc} does not return, then
6811 the port will not be closed automatically unless it is possible to
6812 prove that the port will never again be used for a read or write
6815 @c will not close the port unless it can prove that the port will never
6816 @c again be used for a read or write operation.
6821 Because Scheme's escape procedures have unlimited extent, it is
6822 possible to escape from the current continuation but later to escape back in.
6823 If implementations were permitted to close the port on any escape from the
6824 current continuation, then it would be impossible to write portable code using
6825 both @samp{call-with-current-continuation} and @samp{call-with-input-file} or
6826 @samp{call-with-output-file}.
6828 Pitman wants more said here; maybe encourage users to call
6829 @var{close-foo-port}; maybe talk about process switches (?).
6838 @deffn {procedure} input-port? obj
6839 @deffnx {procedure} output-port? obj
6841 Returns @t{#t} if @var{obj} is an input port or output port
6842 respectively, otherwise returns @t{#f}.
6845 Won't necessarily return true after port is closed.
6853 @deffn {procedure} current-input-port
6854 @deffnx {procedure} current-output-port
6856 Returns the current default input or output port.
6862 @deffn {optional procedure} with-input-from-file string thunk
6863 @deffnx {optional procedure} with-output-to-file string thunk
6865 @var{String} should be a string naming a file, and
6866 @var{proc} should be a procedure of no arguments.
6867 For @samp{with-input-from-file},
6868 the file should already exist; for
6869 @samp{with-output-to-file},
6870 the effect is unspecified if the file
6872 The file is opened for input or output, an input or output port
6873 connected to it is made the default value returned by
6874 @samp{current-input-port} or @samp{current-output-port}
6875 (and is used by @t{(read)}, @t{(write @var{obj})}, and so forth),
6877 @var{thunk} is called with no arguments. When the @var{thunk} returns,
6878 the port is closed and the previous default is restored.
6879 @samp{With-input-from-file} and @samp{with-output-to-file} return(s) the
6880 value(s) yielded by @var{thunk}.
6881 If an escape procedure
6882 is used to escape from the continuation of these procedures, their
6883 behavior is implementation dependent.
6886 OK this with authors??
6889 @c current continuation changes in such a way
6890 @c as to make it doubtful that the \var{thunk} will ever return.
6894 Throughout this section I wanted to see ``the value of @t{(current-input-port)}''
6895 instead of ``the value returned by @var{current-input-port}''. (Same for
6896 @var{current-output-port}.)
6905 @deffn {procedure} open-input-file filename
6907 Takes a string naming an existing file and returns an input port capable of
6908 delivering characters from the file. If the file cannot be opened, an error is
6915 @deffn {procedure} open-output-file filename
6917 Takes a string naming an output file to be created and returns an output
6918 port capable of writing characters to a new file by that name. If the file
6919 cannot be opened, an error is signalled. If a file with the given name
6920 already exists, the effect is unspecified.
6926 @deffn {procedure} close-input-port port
6927 @deffnx {procedure} close-output-port port
6929 Closes the file associated with @var{port}, rendering the @var{port}
6930 incapable of delivering or accepting characters.
6933 on some ports, e.g. terminals or editor buffers.
6936 These routines have no effect if the file has already been closed.
6937 The value returned is unspecified.
6940 Ramsdell: Some note is needed explaining why there are two
6941 different close procedures.
6946 A port isn't necessarily still a port after it has been closed?
6953 @node Input, Output, Ports, Input and output
6964 The input routines have some things in common, maybe explain here.
6969 @deffn {library procedure} read
6970 @deffnx {library procedure} read port
6972 @samp{Read} converts external representations of Scheme objects into the
6973 objects themselves. That is, it is a parser for the nonterminal
6974 <datum> (see sections @pxref{External representation} and
6975 @pxref{Pairs and lists}). @samp{Read} returns the next
6976 object parsable from the given input @var{port}, updating @var{port} to point to
6977 the first character past the end of the external representation of the object.
6979 If an end of file is encountered in the input before any
6980 characters are found that can begin an object, then an end of file
6985 The port remains open, and further attempts
6986 to read will also return an end of file object. If an end of file is
6987 encountered after the beginning of an object's external representation,
6988 but the external representation is incomplete and therefore not parsable,
6989 an error is signalled.
6991 The @var{port} argument may be omitted, in which case it defaults to the
6992 value returned by @samp{current-input-port}. It is an error to read from
6997 @deffn {procedure} read-char
6998 @deffnx {procedure} read-char port
7000 Returns the next character available from the input @var{port}, updating
7001 the @var{port} to point to the following character. If no more characters
7002 are available, an end of file object is returned. @var{Port} may be
7003 omitted, in which case it defaults to the value returned by @samp{current-input-port}.
7009 @deffn {procedure} peek-char
7010 @deffnx {procedure} peek-char port
7012 Returns the next character available from the input @var{port},
7013 @emph{without} updating
7014 the @var{port} to point to the following character. If no more characters
7015 are available, an end of file object is returned. @var{Port} may be
7016 omitted, in which case it defaults to the value returned by @samp{current-input-port}.
7021 The value returned by a call to @samp{peek-char} is the same as the
7022 value that would have been returned by a call to @samp{read-char} with the
7023 same @var{port}. The only difference is that the very next call to
7024 @samp{read-char} or @samp{peek-char} on that @var{port} will return the
7025 value returned by the preceding call to @samp{peek-char}. In particular, a call
7026 to @samp{peek-char} on an interactive port will hang waiting for input
7027 whenever a call to @samp{read-char} would have hung.
7035 @deffn {procedure} eof-object? obj
7037 Returns @t{#t} if @var{obj} is an end of file object, otherwise returns
7038 @t{#f}. The precise set of end of file objects will vary among
7039 implementations, but in any case no end of file object will ever be an object
7040 that can be read in using @samp{read}.
7046 @deffn {procedure} char-ready?
7047 @deffnx {procedure} char-ready? port
7049 Returns @t{#t} if a character is ready on the input @var{port} and
7050 returns @t{#f} otherwise. If @samp{char-ready} returns @t{#t} then
7051 the next @samp{read-char} operation on the given @var{port} is guaranteed
7052 not to hang. If the @var{port} is at end of file then @samp{char-ready?}
7053 returns @t{#t}. @var{Port} may be omitted, in which case it defaults to
7054 the value returned by @samp{current-input-port}.
7059 @samp{Char-ready?} exists to make it possible for a program to
7060 accept characters from interactive ports without getting stuck waiting for
7061 input. Any input editors associated with such ports must ensure that
7062 characters whose existence has been asserted by @samp{char-ready?} cannot
7063 be rubbed out. If @samp{char-ready?} were to return @t{#f} at end of
7064 file, a port at end of file would be indistinguishable from an interactive
7065 port that has no ready characters.
7071 @node Output, System interface, Input, Input and output
7076 @c We've got to put something here to fix the indentation!!
7083 @deffn {library procedure} write obj
7084 @deffnx {library procedure} write obj port
7086 Writes a written representation of @var{obj} to the given @var{port}. Strings
7087 that appear in the written representation are enclosed in doublequotes, and
7088 within those strings backslash and doublequote characters are
7089 escaped by backslashes.
7090 Character objects are written using the @samp{#\} notation.
7091 @samp{Write} returns an unspecified value. The
7092 @var{port} argument may be omitted, in which case it defaults to the value
7093 returned by @samp{current-output-port}.
7099 @deffn {library procedure} display obj
7100 @deffnx {library procedure} display obj port
7102 Writes a representation of @var{obj} to the given @var{port}. Strings
7103 that appear in the written representation are not enclosed in
7104 doublequotes, and no characters are escaped within those strings. Character
7105 objects appear in the representation as if written by @samp{write-char}
7106 instead of by @samp{write}. @samp{Display} returns an unspecified value.
7107 The @var{port} argument may be omitted, in which case it defaults to the
7108 value returned by @samp{current-output-port}.
7113 @samp{Write} is intended
7114 for producing mach@-ine-readable output and @samp{display} is for producing
7115 human-readable output. Implementations that allow ``slashification''
7116 within symbols will probably want @samp{write} but not @samp{display} to
7117 slashify funny characters in symbols.
7124 @deffn {library procedure} newline
7125 @deffnx {library procedure} newline port
7127 Writes an end of line to @var{port}. Exactly how this is done differs
7128 from one operating system to another. Returns an unspecified value.
7129 The @var{port} argument may be omitted, in which case it defaults to the
7130 value returned by @samp{current-output-port}.
7136 @deffn {procedure} write-char char
7137 @deffnx {procedure} write-char char port
7139 Writes the character @var{char} (not an external representation of the
7140 character) to the given @var{port} and returns an unspecified value. The
7141 @var{port} argument may be omitted, in which case it defaults to the value
7142 returned by @samp{current-output-port}.
7147 @node System interface, , Output, Input and output
7148 @subsection System interface
7151 Questions of system interface generally fall outside of the domain of this
7152 report. However, the following operations are important enough to
7153 deserve description here.
7157 @deffn {optional procedure} load filename
7164 @c \domain{\var{Filename} should be a string naming an existing file
7165 @c containing Scheme source code.} The {\cf load} procedure reads
7166 @var{Filename} should be a string naming an existing file
7167 containing Scheme source code. The @samp{load} procedure reads
7168 expressions and definitions from the file and evaluates them
7169 sequentially. It is unspecified whether the results of the expressions
7170 are printed. The @samp{load} procedure does not affect the values
7171 returned by @samp{current-input-port} and @samp{current-output-port}.
7172 @samp{Load} returns an unspecified value.
7177 For portability, @samp{load} must operate on source files.
7178 Its operation on other kinds of files necessarily varies among
7186 @deffn {optional procedure} transcript-on filename
7187 @deffnx {optional procedure} transcript-off
7189 @var{Filename} must be a string naming an output file to be
7190 created. The effect of @samp{transcript-on} is to open the named file
7191 for output, and to cause a transcript of subsequent interaction between
7192 the user and the Scheme system to be written to the file. The
7193 transcript is ended by a call to @samp{transcript-off}, which closes the
7194 transcript file. Only one transcript may be in progress at any time,
7195 though some implementations may relax this restriction. The values
7196 returned by these procedures are unspecified.
7199 @c These procedures are redundant in some systems, but
7200 @c systems that need them should provide them.
7207 @node Formal syntax and semantics, Notes, Standard procedures, top
7208 @chapter Formal syntax and semantics
7212 * Formal semantics::
7213 * Derived expression type::
7218 This chapter provides formal descriptions of what has already been
7219 described informally in previous chapters of this report.
7222 Allow grammar to say that else clause needn't be last?
7227 @node Formal syntax, Formal semantics, Formal syntax and semantics, Formal syntax and semantics
7228 @section Formal syntax
7231 * Lexical structure::
7232 * External representation::
7236 * Programs and definitions::
7241 This section provides a formal syntax for Scheme written in an extended
7244 All spaces in the grammar are for legibility. Case is insignificant;
7245 for example, @samp{#x1A} and @samp{#X1a} are equivalent. <empty>
7246 stands for the empty string.
7248 The following extensions to BNF are used to make the description more
7249 concise: <thing>* means zero or more occurrences of
7250 <thing>; and <thing>+ means at least one
7254 @node Lexical structure, External representation, Formal syntax, Formal syntax
7255 @subsection Lexical structure
7258 This section describes how individual tokens (identifiers,
7260 numbers, etc.) are formed from sequences of characters. The following
7261 sections describe how expressions and programs are formed from sequences
7264 <Intertoken space> may occur on either side of any token, but not
7267 Tokens which require implicit termination (identifiers, numbers,
7268 characters, and dot) may be terminated by any <delimiter>, but not
7269 necessarily by anything else.
7271 The following five characters are reserved for future extensions to the
7272 language: @t{[ ] @{ @} |}
7276 @t{<token> --> <identifier> | <boolean> | <number>
7277 @cindex @w{identifier}
7278 | <character> | <string>
7279 | ( | ) | #( | @t{'} | @t{`} | , | ,@@ | @b{.}
7280 <delimiter> --> <whitespace> | ( | ) | " | ;
7281 <whitespace> --> <space or newline>
7282 <comment> --> ; <@r{all subsequent characters up to a}
7285 <atmosphere> --> <whitespace> | <comment>
7286 <intertoken space> --> <atmosphere>*}
7295 @c This is a kludge, but \multicolumn doesn't work in tabbing environments.
7300 @t{<identifier> --> <initial> <subsequent>*
7301 | <peculiar identifier>
7302 <initial> --> <letter> | <special initial>
7303 <letter> --> a | b | c | ... | z
7305 <special initial> --> ! | $ | % | & | * | / | : | < | =
7307 <subsequent> --> <initial> | <digit>
7308 | <special subsequent>
7309 <digit> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
7310 <special subsequent> --> + | - | .@: | @@
7311 <peculiar identifier> --> + | - | ...
7312 <syntactic keyword> --> <expression keyword>
7313 @cindex @w{syntactic keyword}
7315 | else | => | define
7316 | unquote | unquote-splicing
7317 <expression keyword> --> quote | lambda | if
7318 | set! | begin | cond | and | or | case
7319 | let | let* | letrec | do | delay
7322 @w{@samp{<variable> @result{} <}}@r{any <identifier> that isn't}
7323 @cindex @w{variable}
7324 @w{ @r{also a <syntactic keyword>>}}
7326 <boolean> --> #t | #f
7327 <character> --> #\ <any character>
7328 | #\ <character name>
7329 <character name> --> space | newline
7331 <string> --> " <string element>* "
7332 <string element> --> <any character other than " or \>
7344 @t{<number> --> <num 2>| <num 8>
7345 | <num 10>| <num 16>
7352 The following rules for <num R>, <complex R>, <real
7353 R>, <ureal R>, <uinteger R>, and <prefix R>
7354 should be replicated for @w{R = 2, 8, 10,}
7355 and 16. There are no rules for <decimal 2>, <decimal
7356 8>, and <decimal 16>, which means that numbers containing
7357 decimal points or exponents must be in decimal radix.
7359 Mark Meyer and David Bartley want to fix this. (What? -- Will)
7365 @t{<num R> --> <prefix R> <complex R>
7366 <complex R> --> <real R> | <real R> @@ <real R>
7367 | <real R> + <ureal R> i | <real R> - <ureal R> i
7368 | <real R> + i | <real R> - i
7369 | + <ureal R> i | - <ureal R> i | + i | - i
7370 <real R> --> <sign> <ureal R>
7371 <ureal R> --> <uinteger R>
7372 | <uinteger R> / <uinteger R>
7374 <decimal 10> --> <uinteger 10> <suffix>
7375 | . <digit 10>+ #* <suffix>
7376 | <digit 10>+ . <digit 10>* #* <suffix>
7377 | <digit 10>+ #+ . #* <suffix>
7378 <uinteger R> --> <digit R>+ #*
7379 <prefix R> --> <radix R> <exactness>
7380 | <exactness> <radix R>
7389 @t{<suffix> --> <empty>
7390 | <exponent marker> <sign> <digit 10>+
7391 <exponent marker> --> e | s | f | d | l
7392 <sign> --> <empty> | + | -
7393 <exactness> --> <empty> | #i | #e
7400 <radix 10> --> <empty> | #d
7404 <digit 8> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
7405 <digit 10> --> <digit>
7406 <digit 16> --> <digit 10> | a | b | c | d | e | f }
7413 Mark Meyer of TI sez, shouldn't we allow @t{1e3/2}?
7418 @node External representation, Expression, Lexical structure, Formal syntax
7419 @subsection External representations
7423 <Datum> is what the @code{read} procedure (section @pxref{Input})
7425 successfully parses. Note that any string that parses as an
7426 <ex@-pres@-sion> will also parse as a <datum>.
7430 @t{<datum> --> <simple datum> | <compound datum>
7431 <simple datum> --> <boolean> | <number>
7432 | <character> | <string> | <symbol>
7433 <symbol> --> <identifier>
7434 <compound datum> --> <list> | <vector>
7435 <list> --> (<datum>*) | (<datum>+ .@: <datum>)
7437 <abbreviation> --> <abbrev prefix> <datum>
7438 <abbrev prefix> --> ' | ` | , | ,@@
7439 <vector> --> #(<datum>*) }
7446 @node Expression, Quasiquotations, External representation, Formal syntax
7447 @subsection Expressions
7452 @t{<expression> --> <variable>
7455 | <lambda expression>
7458 | <derived expression>
7462 <literal> --> <quotation> | <self-evaluating>
7463 <self-evaluating> --> <boolean> | <number>
7464 | <character> | <string>
7465 <quotation> --> '<datum> | (quote <datum>)
7466 <procedure call> --> (<operator> <operand>*)
7467 <operator> --> <expression>
7468 <operand> --> <expression>
7470 <lambda expression> --> (lambda <formals> <body>)
7471 <formals> --> (<variable>*) | <variable>
7472 | (<variable>+ .@: <variable>)
7473 <body> --> <definition>* <sequence>
7474 <sequence> --> <command>* <expression>
7475 <command> --> <expression>
7477 <conditional> --> (if <test> <consequent> <alternate>)
7478 <test> --> <expression>
7479 <consequent> --> <expression>
7480 <alternate> --> <expression> | <empty>
7482 <assignment> --> (set! <variable> <expression>)
7484 <derived expression> -->
7485 (cond <cond clause>+)
7486 | (cond <cond clause>* (else <sequence>))
7487 | (case <expression>
7489 | (case <expression>
7494 | (let (<binding spec>*) <body>)
7495 | (let <variable> (<binding spec>*) <body>)
7496 | (let* (<binding spec>*) <body>)
7497 | (letrec (<binding spec>*) <body>)
7498 | (begin <sequence>)
7499 | (do (<iteration spec>*)
7500 (<test> <do result>)
7502 | (delay <expression>)
7505 <cond clause> --> (<test> <sequence>)
7507 | (<test> => <recipient>)
7508 <recipient> --> <expression>
7509 <case clause> --> ((<datum>*) <sequence>)
7510 <binding spec> --> (<variable> <expression>)
7511 <iteration spec> --> (<variable> <init> <step>)
7512 | (<variable> <init>)
7513 <init> --> <expression>
7514 <step> --> <expression>
7515 <do result> --> <sequence> | <empty>
7517 <macro use> --> (<keyword> <datum>*)
7518 <keyword> --> <identifier>
7521 (let-syntax (<syntax spec>*) <body>)
7522 | (letrec-syntax (<syntax spec>*) <body>)
7523 <syntax spec> --> (<keyword> <transformer spec>)
7531 @node Quasiquotations, Transformers, Expression, Formal syntax
7532 @subsection Quasiquotations
7535 The following grammar for quasiquote expressions is not context-free.
7536 It is presented as a recipe for generating an infinite number of
7537 production rules. Imagine a copy of the following rules for D = 1, 2,3, @dots{}. D keeps track of the nesting depth.
7541 @t{<quasiquotation> --> <quasiquotation 1>
7542 <qq template 0> --> <expression>
7543 <quasiquotation D> --> `<qq template D>
7544 | (quasiquote <qq template D>)
7545 <qq template D> --> <simple datum>
7546 | <list qq template D>
7547 | <vector qq template D>
7549 <list qq template D> --> (<qq template or splice D>*)
7550 | (<qq template or splice D>+ .@: <qq template D>)
7552 | <quasiquotation D+1>
7553 <vector qq template D> --> #(<qq template or splice D>*)
7554 <unquotation D> --> ,<qq template D-1>
7555 | (unquote <qq template D-1>)
7556 <qq template or splice D> --> <qq template D>
7557 | <splicing unquotation D>
7558 <splicing unquotation D> --> ,@@<qq template D-1>
7559 | (unquote-splicing <qq template D-1>) }
7565 In <quasiquotation>s, a <list qq template D> can sometimes
7566 be confused with either an <un@-quota@-tion D> or a <splicing
7567 un@-quo@-ta@-tion D>. The interpretation as an
7568 <un@-quo@-ta@-tion> or <splicing
7569 un@-quo@-ta@-tion D> takes precedence.
7571 @node Transformers, Programs and definitions, Quasiquotations, Formal syntax
7572 @subsection Transformers
7577 @t{<transformer spec> -->
7578 (syntax-rules (<identifier>*) <syntax rule>*)
7579 <syntax rule> --> (<pattern> <template>)
7580 <pattern> --> <pattern identifier>
7582 | (<pattern>+ . <pattern>)
7583 | (<pattern>* <pattern> <ellipsis>)
7585 | #(<pattern>* <pattern> <ellipsis>)
7587 <pattern datum> --> <string>
7591 <template> --> <pattern identifier>
7592 | (<template element>*)
7593 | (<template element>+ . <template>)
7594 | #(<template element>*)
7596 <template element> --> <template>
7597 | <template> <ellipsis>
7598 <template datum> --> <pattern datum>
7599 <pattern identifier> --> <any identifier except @samp{...}>
7600 <ellipsis> --> <the identifier @samp{...}>
7607 @node Programs and definitions, , Transformers, Formal syntax
7608 @subsection Programs and definitions
7613 @t{<program> --> <command or definition>*
7614 <command or definition> --> <command>
7616 | <syntax definition>
7617 | (begin <command or definition>+)
7618 <definition> --> (define <variable> <expression>)
7619 | (define (<variable> <def formals>) <body>)
7620 | (begin <definition>*)
7621 <def formals> --> <variable>*
7622 | <variable>* .@: <variable>
7623 <syntax definition> -->
7624 (define-syntax <keyword> <transformer spec>)
7631 @node Formal semantics, Derived expression type, Formal syntax, Formal syntax and semantics
7632 @section Formal semantics
7635 This section provides a formal denotational semantics for the primitive
7636 expressions of Scheme and selected built-in procedures. The concepts
7637 and notation used here are described in @sc{[Stoy77]}.
7640 @emph{Note:} The formal semantics section was written in La@TeX{} which
7641 is incompatible with @TeX{}info. See the Formal semantics section of
7642 the original document from which this was derived.
7647 @node Derived expression type, , Formal semantics, Formal syntax and semantics
7648 @section Derived expression types
7652 This section gives macro definitions for the derived expression types in
7653 terms of the primitive expression types (literal, variable, call, @samp{lambda},
7654 @samp{if}, @samp{set!}). See section @ref{Control features} for a possible
7655 definition of @samp{delay}.
7661 (syntax-rules (else =>)
7662 ((cond (else result1 result2 ...))
7663 (begin result1 result2 ...))
7664 ((cond (test => result))
7666 (if temp (result temp))))
7667 ((cond (test => result) clause1 clause2 ...)
7671 (cond clause1 clause2 ...))))
7672 ((cond (test)) test)
7673 ((cond (test) clause1 clause2 ...)
7677 (cond clause1 clause2 ...))))
7678 ((cond (test result1 result2 ...))
7679 (if test (begin result1 result2 ...)))
7680 ((cond (test result1 result2 ...)
7681 clause1 clause2 ...)
7683 (begin result1 result2 ...)
7684 (cond clause1 clause2 ...)))))
7693 (syntax-rules (else)
7696 (let ((atom-key (key ...)))
7697 (case atom-key clauses ...)))
7699 (else result1 result2 ...))
7700 (begin result1 result2 ...))
7702 ((atoms ...) result1 result2 ...))
7703 (if (memv key '(atoms ...))
7704 (begin result1 result2 ...)))
7706 ((atoms ...) result1 result2 ...)
7708 (if (memv key '(atoms ...))
7709 (begin result1 result2 ...)
7710 (case key clause clauses ...)))))
7722 ((and test1 test2 ...)
7723 (if test1 (and test2 ...) #f))))
7735 ((or test1 test2 ...)
7737 (if x x (or test2 ...))))))
7747 ((let ((name val) ...) body1 body2 ...)
7748 ((lambda (name ...) body1 body2 ...)
7750 ((let tag ((name val) ...) body1 body2 ...)
7751 ((letrec ((tag (lambda (name ...)
7764 ((let* () body1 body2 ...)
7765 (let () body1 body2 ...))
7766 ((let* ((name1 val1) (name2 val2) ...)
7769 (let* ((name2 val2) ...)
7770 body1 body2 ...)))))
7775 The following @samp{letrec} macro uses the symbol @samp{<undefined>}
7776 in place of an expression which returns something that when stored in
7777 a location makes it an error to try to obtain the value stored in the
7778 location (no such expression is defined in Scheme).
7779 A trick is used to generate the temporary names needed to avoid
7780 specifying the order in which the values are evaluated.
7781 This could also be accomplished by using an auxiliary macro.
7786 (define-syntax letrec
7788 ((letrec ((var1 init1) ...) body ...)
7789 (letrec "generate temp names"
7794 ((letrec "generate temp names"
7799 (let ((var1 <undefined>) ...)
7800 (let ((temp1 init1) ...)
7804 ((letrec "generate temp names"
7809 (letrec "generate temp names"
7821 (define-syntax begin
7824 ((lambda () exp ...)))))
7829 The following alternative expansion for @samp{begin} does not make use of
7830 the ability to write more than one expression in the body of a lambda
7831 expression. In any case, note that these rules apply only if the body
7832 of the @samp{begin} contains no definitions.
7837 (define-syntax begin
7841 ((begin exp1 exp2 ...)
7843 (begin exp2 ...)))))
7848 The following definition
7849 of @samp{do} uses a trick to expand the variable clauses.
7850 As with @samp{letrec} above, an auxiliary macro would also work.
7851 The expression @samp{(if #f #f)} is used to obtain an unspecific
7859 ((do ((var init step ...) ...)
7872 (loop (do "step" var step ...)
7884 @c `(a b c ... . z) = `(a . (b c ...))
7885 @c `(a . b) = (append Q*_0[a] `b)
7887 @c Q*_0[a] = (list 'a)
7888 @c Q*_0[,a] = (list a)
7890 @c Q*_0[`a] = (list 'quasiquote Q*_1[a])
7891 @c `#(a b ...) = (list->vector `(a b ...))
7897 @node Notes, Additional material, Formal syntax and semantics, top
7901 * Language changes::
7907 Perhaps this section should be made to disappear.
7908 Can these remarks be moved somewhere else?
7912 @node Language changes, , Notes, Notes
7913 @unnumberedsec Language changes
7917 This section enumerates the changes that have been made to Scheme since
7918 the ``Revised^4 report'' [R4RS] was published.
7926 The report is now a superset of the IEEE standard for Scheme
7927 [IEEEScheme]: implementations that conform to the report will
7928 also conform to the standard. This required the following changes:
7935 The empty list is now required to count as true.
7938 The classification of features as essential or inessential has been
7939 removed. There are now three classes of built-in procedures: primitive,
7940 library, and optional. The optional procedures are @samp{load},
7941 @samp{with-input-from-file}, @samp{with-output-to-file},
7942 @samp{transcript-on}, @samp{transcript-off}, and
7943 @samp{interaction-environment},
7944 and @samp{-} and @samp{/} with more than two arguments.
7945 None of these are in the IEEE standard.
7948 Programs are allowed to redefine built-in procedures. Doing so
7949 will not change the behavior of other built-in procedures.
7955 @emph{Port} has been added to the list of disjoint types.
7958 The macro appendix has been removed. High-level macros are now part
7959 of the main body of the report. The rewrite rules for derived expressions
7960 have been replaced with macro definitions. There are no reserved identifiers.
7963 @samp{Syntax-rules} now allows vector patterns.
7966 Multiple-value returns, @samp{eval}, and @samp{dynamic-wind} have
7970 The calls that are required to be implemented in a properly tail-recursive
7971 fashion are defined explicitly.
7974 `@samp{@@}' can be used within identifiers. `@samp{|}' is reserved
7975 for possible future extensions.
7982 @c \subsection*{Keywords as variable names}
7984 @c Some implementations allow arbitrary syntactic
7985 @c keywords \index{keyword}\index{syntactic keyword}to be used as variable
7986 @c names, instead of reserving them, as this report would have
7987 @c it.\index{variable} But this creates ambiguities in the interpretation
7988 @c of expressions: for example, in the following, it's not clear whether
7989 @c the expression {\tt (if 1 2 3)} should be treated as a procedure call or
7990 @c as a conditional.
7994 @c (if 1 2 3) \ev 2 {\em{}or} (1 2 3)%
7997 @c These ambiguities are usually resolved in some consistent way within any
7998 @c given implementation, but no particular treatment stands out as being
7999 @c clearly superior to any other, so these situations were excluded for the
8000 @c purposes of this report.
8003 @c \subsection*{Macros}
8005 @c Scheme does not have any standard facility for defining new kinds of
8006 @c expressions.\index{macros}
8008 @c \vest The ability to alter the syntax of the language creates
8009 @c numerous problems. All current implementations of Scheme have macro
8010 @c facilities that solve those problems to one degree or another, but the
8011 @c solutions are quite different and it isn't clear at this time which
8012 @c solution is best, or indeed whether any of the solutions are truly
8013 @c adequate. Rather than standardize, we are encouraging implementations
8014 @c to continue to experiment with different solutions.
8016 @c \vest The main problems with traditional macros are: They must be
8017 @c defined to the system before any code using them is loaded; this is a
8018 @c common source of obscure bugs. They are usually global; macros can be
8019 @c made to follow lexical scope rules \todo{flushed: ``as in Common
8020 @c Lisp's {\tt macrolet}''; OK?}, but many people find the resulting scope rules
8021 @c confusing. Unless they are written very carefully, macros are
8022 @c vulnerable to inadvertent capture of free variables; to get around this,
8023 @c for example, macros may have to generate code in which procedure values
8024 @c appear as quoted constants. There is a similar problem with syntactic
8025 @c keywords if the keywords of special forms are not reserved. If keywords
8026 @c are reserved, then either macros introduce new reserved words,
8027 @c invalidating old code, or else special forms defined by the programmer
8028 @c do not have the same status as special forms defined by the system.
8030 @c \todo{Refer to Pitman's special forms paper.}
8031 @c \todo{Pitman sez: Discuss importance of having a small number of special forms
8032 @c so that programs can inspect each other.}
8035 Move cwcc history back here? --- Andy Cromarty is concerned about
8036 confusion over who the audience is.
8042 23. NOTES, p.35ff.: This material should stay somehow. We need to
8043 make it clear that R^3 Scheme is not being touted as Yet Another
8044 Ultimate Solution To The Programming Language Problem, but rather
8045 as a snapshot of a *process* of good design, for which not all
8046 answers have yet been found. We also ought to use the opportunity
8047 for publicity afforded us by SIGPLAN to advertise some of the thorny
8048 unsolved problems that need further research, and encourage
8049 language designers to work on them.
8053 @c @include{repository}
8054 @node Additional material, Example, Notes, top
8055 @unnumbered Additional material
8058 The Internet Scheme Repository at
8061 @center @url{http://www.cs.indiana.edu/scheme-repository/}
8064 contains an extensive Scheme bibliography, as well as papers,
8065 programs, implementations, and other material related to Scheme.
8069 @c @include{example}
8071 @node Example, Bibliography, Additional material, top
8074 @c -*- Mode: Lisp; Package: SCHEME; Syntax: Common-lisp -*-
8077 @samp{Integrate-system} integrates the system
8080 @center y_k^^ = f_k(y_1, y_2, @dots{}, y_n), k = 1, @dots{}, n
8082 of differential equations with the method of Runge-Kutta.
8084 The parameter @t{system-derivative} is a function that takes a system
8085 state (a vector of values for the state variables y_1, @dots{}, y_n)
8086 and produces a system derivative (the values y_1^^, @dots{},y_n^^). The parameter @t{initial-state} provides an initial
8087 system state, and @t{h} is an initial guess for the length of the
8090 The value returned by @samp{integrate-system} is an infinite stream of
8096 (define integrate-system
8097 (lambda (system-derivative initial-state h)
8098 (let ((next (runge-kutta-4 system-derivative h)))
8101 (delay (map-streams next
8108 @samp{Runge-Kutta-4} takes a function, @t{f}, that produces a
8109 system derivative from a system state. @samp{Runge-Kutta-4}
8110 produces a function that takes a system state and
8111 produces a new system state.
8116 (define runge-kutta-4
8118 (let ((*h (scale-vector h))
8119 (*2 (scale-vector 2))
8120 (*1/2 (scale-vector (/ 1 2)))
8121 (*1/6 (scale-vector (/ 1 6))))
8123 ;; y @r{}is a system state
8124 (let* ((k0 (*h (f y)))
8125 (k1 (*h (f (add-vectors y (*1/2 k0)))))
8126 (k2 (*h (f (add-vectors y (*1/2 k1)))))
8127 (k3 (*h (f (add-vectors y k2)))))
8129 (*1/6 (add-vectors k0
8133 @c |--------------------------------------------------|
8139 (vector-length (car vectors))
8142 (map (lambda (v) (vector-ref v i))
8145 @c |--------------------------------------------------|
8146 (define generate-vector
8148 (let ((ans (make-vector size)))
8151 (cond ((= i size) ans)
8153 (vector-set! ans i (proc i))
8157 (define add-vectors (elementwise +))
8159 (define scale-vector
8161 (elementwise (lambda (x) (* x s)))))
8166 @samp{Map-streams} is analogous to @samp{map}: it applies its first
8167 argument (a procedure) to all the elements of its second argument (a
8176 (delay (map-streams f (tail s))))))
8181 Infinite streams are implemented as pairs whose car holds the first
8182 element of the stream and whose cdr holds a promise to deliver the rest
8190 (lambda (stream) (force (cdr stream))))
8196 The following illustrates the use of @samp{integrate-system} in
8197 integrating the system
8200 @center C dv_C / dt = -i_L - v_C / R
8204 @center L di_L / dt = v_C
8206 which models a damped oscillator.
8211 (define damped-oscillator
8214 (let ((Vc (vector-ref state 0))
8215 (Il (vector-ref state 1)))
8216 (vector (- 0 (+ (/ Vc (* R C)) (/ Il C)))
8221 (damped-oscillator 10000 1000 .001)
8233 @c (letrec ((loop (lambda (s)
8236 @c (loop (tail s)))))
8237 @c (loop the-states))
8240 @c #(0.99895054 9.994835e-6)
8241 @c #(0.99780226 1.9978681e-5)
8242 @c #(0.9965554 2.9950552e-5)
8243 @c #(0.9952102 3.990946e-5)
8244 @c #(0.99376684 4.985443e-5)
8245 @c #(0.99222565 5.9784474e-5)
8246 @c #(0.9905868 6.969862e-5)
8247 @c #(0.9888506 7.9595884e-5)
8248 @c #(0.9870173 8.94753e-5)
8252 @c \newpage % Put bib on it's own page (it's just one)
8253 @c \twocolumn[\vspace{-.18in}]% Last bib item was on a page by itself.
8254 @c \renewcommand{\bibname}{References}
8257 @c My reference for proper reference format is:
8258 @c Mary-Claire van Leunen.
8259 @c {\em A Handbook for Scholars.}
8261 @c I think the references list would look better in ``open'' format,
8262 @c i.e. with the three blocks for each entry appearing on separate
8263 @c lines. I used the compressed format for SIGPLAN in the interest of
8264 @c space. In open format, when a block runs over one line,
8265 @c continuation lines should be indented; this could probably be done
8266 @c using some flavor of latex list environment. Maybe the right thing
8267 @c to do in the long run would be to convert to Bibtex, which probably
8268 @c does the right thing, since it was implemented by one of van
8269 @c Leunen's colleagues at DEC SRC.
8272 @c I tried to follow Jonathan's format, insofar as I understood it.
8273 @c I tried to order entries lexicographically by authors (with singly
8274 @c authored papers first), then by date.
8275 @c In some cases I replaced a technical report or conference paper
8276 @c by a subsequent journal article, but I think there are several
8277 @c more such replacements that ought to be made.
8280 @c This is just a personal remark on your question on the RRRS:
8281 @c The language CUCH (Curry-Church) was implemented by 1964 and
8282 @c is a practical version of the lambda-calculus (call-by-name).
8283 @c One reference you may find in Formal Language Description Languages
8284 @c for Computer Programming T.~B.~Steele, 1965 (or so).
8285 @c -- Matthias Felleisen
8287 @c Rather than try to keep the bibliography up-to-date, which is hopeless
8288 @c given the time between updates, I replaced the bulk of the references
8289 @c with a pointer to the Scheme Repository. Ozan Yigit's bibliography in
8290 @c the repository is a superset of the R4RS one.
8291 @c The bibliography now contains only items referenced within the report.
8292 @c -- Richard, 1996.
8294 @node Bibliography, Index, Example, top
8295 @unnumbered Bibliography
8304 Harold Abelson and Gerald Jay Sussman with Julie Sussman.
8305 @emph{Structure and Interpretation of Computer Programs, second edition.}
8306 MIT Press, Cambridge, 1996.
8310 Alan Bawden and Jonathan Rees.
8313 In @emph{Proceedings of the 1988 ACM Symposium on Lisp and
8314 Functional Programming}, pages 86--95.
8318 Robert G. Burger and R. Kent Dybvig.
8319 Printing floating-point numbers quickly and accurately.
8320 In @emph{Proceedings of the ACM SIGPLAN '96 Conference
8321 on Programming Language Design and Implementation}, pages 108--116.
8325 William Clinger, editor.
8326 The revised revised report on Scheme, or an uncommon Lisp.
8327 MIT Artificial Intelligence Memo 848, August 1985.
8328 Also published as Computer Science Department Technical Report 174,
8329 Indiana University, June 1985.
8335 How to read floating point numbers accurately.
8336 In @emph{Proceedings of the ACM SIGPLAN '90 Conference
8337 on Programming Language Design and Implementation}, pages 92--101.
8338 Proceedings published as @emph{SIGPLAN Notices} 25(6), June 1990.
8342 William Clinger and Jonathan Rees, editors.
8343 The revised^4 report on the algorithmic language Scheme.
8344 In @emph{ACM Lisp Pointers} 4(3), pages 1--55, 1991.
8346 @item [macrosthatwork]
8348 William Clinger and Jonathan Rees.
8349 @pindex macrosthatwork
8351 In @emph{Proceedings of the 1991 ACM Conference on Principles of
8352 Programming Languages}, pages 155--162.
8354 @item [propertailrecursion]
8357 @pindex propertailrecursion
8358 Proper Tail Recursion and Space Efficiency.
8359 To appear in @emph{Proceedings of the 1998 ACM Conference on Programming
8360 Language Design and Implementation}, June 1998.
8362 @item [syntacticabstraction]
8363 @pindex syntacticabstraction
8364 R. Kent Dybvig, Robert Hieb, and Carl Bruggeman.
8365 Syntactic abstraction in Scheme.
8366 @emph{Lisp and Symbolic Computation} 5(4):295--326, 1993.
8370 Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes.
8371 Scheme 311 version 4 reference manual.
8372 Indiana University Computer Science Technical Report 137, February 1983.
8373 Superseded by [Scheme84].
8377 D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand.
8378 Scheme 84 interim reference manual.
8379 Indiana University Computer Science Technical Report 153, January 1985.
8383 @emph{IEEE Standard 754-1985. IEEE Standard for Binary Floating-Point
8384 Arithmetic.} IEEE, New York, 1985.
8388 @emph{IEEE Standard 1178-1990. IEEE Standard for the Scheme
8389 Programming Language.} IEEE, New York, 1991.
8391 @item [Kohlbecker86]
8392 @pindex Kohlbecker86
8393 Eugene E. Kohlbecker Jr.
8394 @emph{Syntactic Extensions in the Programming Language Lisp.}
8395 PhD thesis, Indiana University, August 1986.
8399 Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias Felleisen, and Bruce Duba.
8400 Hygienic macro expansion.
8401 In @emph{Proceedings of the 1986 ACM Conference on Lisp
8402 and Functional Programming}, pages 151--161.
8407 A correspondence between Algol 60 and Church's lambda notation: Part I.
8408 @emph{Communications of the ACM} 8(2):89--101, February 1965.
8412 MIT Department of Electrical Engineering and Computer Science.
8413 Scheme manual, seventh edition.
8419 Revised report on the algorithmic language Algol 60.
8420 @emph{Communications of the ACM} 6(1):1--17, January 1963.
8425 Principal values and branch cuts in complex APL.
8426 In @emph{APL '81 Conference Proceedings,} pages 248--256.
8427 ACM SIGAPL, San Francisco, September 1981.
8428 Proceedings published as @emph{APL Quote Quad} 12(1), ACM, September 1981.
8433 The revised MacLisp manual (Saturday evening edition).
8434 MIT Laboratory for Computer Science Technical Report 295, May 1983.
8438 Jonathan A. Rees and Norman I. Adams IV.
8439 T: A dialect of Lisp or, lambda: The ultimate software tool.
8440 In @emph{Conference Record of the 1982 ACM Symposium on Lisp and
8441 Functional Programming}, pages 114--122.
8445 Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan.
8446 The T manual, fourth edition.
8447 Yale University Computer Science Department, January 1984.
8451 Jonathan Rees and William Clinger, editors.
8452 The revised^3 report on the algorithmic language Scheme.
8453 In @emph{ACM SIGPLAN Notices} 21(12), pages 37--79, December 1986.
8458 Definitional interpreters for higher order programming languages.
8459 In @emph{ACM Conference Proceedings}, pages 717--740.
8468 Guy Lewis Steele Jr. and Gerald Jay Sussman.
8469 The revised report on Scheme, a dialect of Lisp.
8470 MIT Artificial Intelligence Memo 452, January 1978.
8474 Guy Lewis Steele Jr.
8475 Rabbit: a compiler for Scheme.
8476 MIT Artificial Intelligence Laboratory Technical Report 474, May 1978.
8480 Guy Lewis Steele Jr.
8481 @emph{Common Lisp: The Language, second edition.}
8482 Digital Press, Burlington MA, 1990.
8486 Gerald Jay Sussman and Guy Lewis Steele Jr.
8487 Scheme: an interpreter for extended lambda calculus.
8488 MIT Artificial Intelligence Memo 349, December 1975.
8493 @emph{Denotational Semantics: The Scott-Strachey Approach to
8494 Programming Language Theory.}
8495 MIT Press, Cambridge, 1977.
8499 Texas Instruments, Inc.
8500 TI Scheme Language Reference Manual.
8501 Preliminary version 1.0, November 1985.
8511 @c Adjustment to avoid having the last index entry on a page by itself.
8512 @c \addtolength{\baselineskip}{-0.1pt}
8514 @node Index, , Bibliography, top
8515 @unnumbered Alphabetic index of definitions of concepts, keywords, and procedures
8519 The principal entry for each term, procedure, or keyword is listed
8520 first, separated from the other entries by a semicolon.
8524 @unnumberedsec Concepts
8527 @unnumberedsec Procedures
8531 @unnumberedsec References