diff options
Diffstat (limited to 'doc/r5rs/r5rs.texi')
-rw-r--r-- | doc/r5rs/r5rs.texi | 8538 |
1 files changed, 8538 insertions, 0 deletions
diff --git a/doc/r5rs/r5rs.texi b/doc/r5rs/r5rs.texi new file mode 100644 index 000000000..a33771190 --- /dev/null +++ b/doc/r5rs/r5rs.texi @@ -0,0 +1,8538 @@ +\input texinfo @c -*-texinfo-*- +@c %**start of header +@setfilename r5rs.info +@settitle Revised(5) Scheme + +@c This copy of r5rs.texi differs from Aubrey Jaffer's master copy +@c by a set of changes to allow the building of r5rs.dvi from r5rs.texi. +@c Aubrey Jaffer's view - which I agree with - is that, given that +@c people have the option of building r5rs.dvi from the original +@c LaTeX distribution for R5RS, it is not worth fixing his master +@c copy of r5rs.texi and the tool which autogenerates it. On the +@c other hand, it is a marginal convenience for people to be able to +@c build hardcopy from r5rs.texi, even if the results are less good +@c than with the original LaTeX. Hence the following fixes. +@c (lines 714, 725, 728, 1614, 2258): Remove invalid parentheses from +@c @deffn statements. +@c (line 2316): Change @deffnx to @deffn, and insert `@end deffn' to +@c terminate preceding @deffn. +@c (line 7320): Insert `@c ' at beginning of lines that are intended +@c to be @ignore'd. +@c +@c NJ 2001/1/26 + +@c \documentclass[twoside]{algol60} + +@c \pagestyle{headings} +@c \showboxdepth=0 + + + +@c \def\headertitle{Revised$^{5}$ Scheme} +@c \def\integerversion{5} + +@c Sizes and dimensions + +@c \topmargin -.375in % Nominal distance from top of page to top of + +@c box containing running head. +@c \headsep 15pt % Space between running head and text. + +@c \textheight 663pt % Height of text (including footnotes and figures, + +@c excluding running head and foot). + +@c \textwidth 523pt % Width of text line. +@c \columnsep 15pt % Space between columns +@c \columnseprule 0pt % Width of rule between columns. + +@c \parskip 5pt plus 2pt minus 2pt % Extra vertical space between paragraphs. +@c \parindent 0pt % Width of paragraph indentation. +@c \topsep 0pt plus 2pt % Extra vertical space, in addition to + +@c \parskip, added above and below list and + +@c paragraphing environments. + +@c \oddsidemargin -.5in % Left margin on odd-numbered pages. +@c \evensidemargin -.5in % Left margin on even-numbered pages. + +@c % End of sizes and dimensions + +@paragraphindent 0 +@c %**end of header +@c syncodeindex fn cp + +@ifinfo +@dircategory The Algorithmic Language Scheme +@direntry +* R5RS: (r5rs). The Revised(5) Report on Scheme. +@end direntry +@end ifinfo + + +@c \parindent 0pt %!! 15pt % Width of paragraph indentation. + + @b{20 February 1998} +@c \hfil \today{} + +@c @include{first} +@titlepage + +@c HTML first page +@title Scheme +@subtitle Revised(5) Report on the Algorithmic Language Scheme +@c First page + +@c \thispagestyle{empty} + +@c \todo{"another" report?} + + +@author R@sc{ICHARD} K@sc{ELSEY}, W@sc{ILLIAM} C@sc{LINGER, AND} J@sc{ONATHAN} R@sc{EES} (@i{Editors}) +@author H. A@sc{BELSON} +@author R. K. D@sc{YBVIG} +@author C. T. H@sc{AYNES} +@author G. J. R@sc{OZAS} +@author N. I. A@sc{DAMS IV} +@author D. P. F@sc{RIEDMAN} +@author E. K@sc{OHLBECKER} +@author G. L. S@sc{TEELE} J@sc{R}. +@author D. H. B@sc{ARTLEY} +@author R. H@sc{ALSTEAD} +@author D. O@sc{XLEY} +@author G. J. S@sc{USSMAN} +@author G. B@sc{ROOKS} +@author C. H@sc{ANSON} +@author K. M. P@sc{ITMAN} +@author M. W@sc{AND} +@author + + +@c {\it Dedicated to the Memory of ALGOL 60} +@i{Dedicated to the Memory of Robert Hieb} +@c [For the macros in R5RS -RK] + + + + +@unnumbered Summary + + +The report gives a defining description of the programming language +Scheme. Scheme is a statically scoped and properly tail-recursive +dialect of the Lisp programming language invented by Guy Lewis +Steele Jr.@: and Gerald Jay Sussman. It was designed to have an +exceptionally clear and simple semantics and few different ways to +form expressions. A wide variety of programming paradigms, including +imperative, functional, and message passing styles, find convenient +expression in Scheme. + +The introduction offers a brief history of the language and of +the report. + +The first three chapters present the fundamental ideas of the +language and describe the notational conventions used for describing the +language and for writing programs in the language. + +Chapters @ref{Expressions} and @ref{Program structure} describe +the syntax and semantics of expressions, programs, and definitions. + +Chapter @ref{Standard procedures} describes Scheme's built-in +procedures, which include all of the language's data manipulation and +input/output primitives. + +Chapter @ref{Formal syntax and semantics} provides a formal syntax for Scheme +written in extended BNF, along with a formal denotational semantics. +An example of the use of the language follows the formal syntax and +semantics. + +The report concludes with a list of references and an +alphabetic index. + +@ignore todo +expand the summary so that it fills up the column. +@end ignore + + +@c \vfill +@c \begin{center} +@c {\large \bf +@c *** DRAFT*** \\ +@c %August 31, 1989 +@c \today +@c }\end{center} + + + + + +@c \addvspace{3.5pt} % don't shrink this gap +@c \renewcommand{\tocshrink}{-3.5pt} % value determined experimentally + + + + + + +@page + +@end titlepage + +@c INFO first page +@ifinfo + +@c First page + +@c \thispagestyle{empty} + +@c \todo{"another" report?} + + +@node top, Introduction, (dir), (dir) +@top Revised(5) Report on the Algorithmic Language Scheme + +@sp 1 + + +@center @c begin-tabular +@quotation +@multitable @columnfractions 0.25 0.25 0.25 0.25 +@item +@center R@sc{ICHARD} K@sc{ELSEY}, W@sc{ILLIAM} C@sc{LINGER, AND} J@sc{ONATHAN} R@sc{EES} (@i{Editors}) +@item H. A@sc{BELSON} @tab R. K. D@sc{YBVIG} @tab C. T. H@sc{AYNES} @tab G. J. R@sc{OZAS} +@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}. +@item D. H. B@sc{ARTLEY} @tab R. H@sc{ALSTEAD} @tab D. O@sc{XLEY} @tab G. J. S@sc{USSMAN} +@item G. B@sc{ROOKS} @tab C. H@sc{ANSON} @tab K. M. P@sc{ITMAN} @tab M. W@sc{AND} +@item +@end multitable +@end quotation + + +@sp 2 + +@c {\it Dedicated to the Memory of ALGOL 60} +@i{Dedicated to the Memory of Robert Hieb} +@c [For the macros in R5RS -RK] + +@sp 3 + + + + +@majorheading Summary + + +The report gives a defining description of the programming language +Scheme. Scheme is a statically scoped and properly tail-recursive +dialect of the Lisp programming language invented by Guy Lewis +Steele Jr.@: and Gerald Jay Sussman. It was designed to have an +exceptionally clear and simple semantics and few different ways to +form expressions. A wide variety of programming paradigms, including +imperative, functional, and message passing styles, find convenient +expression in Scheme. + +The introduction offers a brief history of the language and of +the report. + +The first three chapters present the fundamental ideas of the +language and describe the notational conventions used for describing the +language and for writing programs in the language. + +Chapters @ref{Expressions} and @ref{Program structure} describe +the syntax and semantics of expressions, programs, and definitions. + +Chapter @ref{Standard procedures} describes Scheme's built-in +procedures, which include all of the language's data manipulation and +input/output primitives. + +Chapter @ref{Formal syntax and semantics} provides a formal syntax for Scheme +written in extended BNF, along with a formal denotational semantics. +An example of the use of the language follows the formal syntax and +semantics. + +The report concludes with a list of references and an +alphabetic index. + +@ignore todo +expand the summary so that it fills up the column. +@end ignore + + +@c \vfill +@c \begin{center} +@c {\large \bf +@c *** DRAFT*** \\ +@c %August 31, 1989 +@c \today +@c }\end{center} + + + + + +@c \addvspace{3.5pt} % don't shrink this gap +@c \renewcommand{\tocshrink}{-3.5pt} % value determined experimentally + +@unnumbered Contents + +@menu +* Introduction:: +* Overview of Scheme:: +* Lexical conventions:: +* Basic concepts:: +* Expressions:: +* Program structure:: +* Standard procedures:: +* Formal syntax and semantics:: +* Notes:: +* Additional material:: +* Example:: +* Bibliography:: +* Index:: +@end menu + + + + + +@page + +@end ifinfo + + +@c @include{intro} +@node Introduction, Overview of Scheme, top, top +@unnumbered Introduction + +@menu +* Background:: +* Acknowledgements:: +@end menu + + + + +Programming languages should be designed not by piling feature on top of +feature, but by removing the weaknesses and restrictions that make additional +features appear necessary. Scheme demonstrates that a very small number +of rules for forming expressions, with no restrictions on how they are +composed, suffice to form a practical and efficient programming language +that is flexible enough to support most of the major programming +paradigms in use today. + +@c Scheme has influenced the evolution of Lisp. +Scheme +was one of the first programming languages to incorporate first class +procedures as in the lambda calculus, thereby proving the usefulness of +static scope rules and block structure in a dynamically typed language. +Scheme was the first major dialect of Lisp to distinguish procedures +from lambda expressions and symbols, to use a single lexical +environment for all variables, and to evaluate the operator position +of a procedure call in the same way as an operand position. By relying +entirely on procedure calls to express iteration, Scheme emphasized the +fact that tail-recursive procedure calls are essentially goto's that +pass arguments. Scheme was the first widely used programming language to +embrace first class escape procedures, from which all previously known +sequential control structures can be synthesized. A subsequent +version of Scheme introduced the concept of exact and inexact numbers, +an extension of Common Lisp's generic arithmetic. +More recently, Scheme became the first programming language to support +hygienic macros, which permit the syntax of a block-structured language +to be extended in a consistent and reliable manner. +@c A few +@c of these innovations have recently been incorporated into Common Lisp, while +@c others remain to be adopted. + +@ignore todo +Ramsdell: +I would like to make a few comments on presentation. The most +important comment is about section organization. Newspaper writers +spend most of their time writing the first three paragraphs of any +article. This part of the article is often the only part read by +readers, and is important in enticing readers to continue. In the +same way, The first page is most likely to be the only page read by +many SIGPLAN readers. If I had my choice of what I would ask them to +read, it would be the material in section 1.1, the Semantics section +that notes that scheme is lexically scoped, tail recursive, weakly +typed, ... etc. I would expand on the discussion on continuations, +as they represent one important difference between Scheme and other +languages. The introduction, with its history of scheme, its history +of scheme reports and meetings, and acknowledgements giving names of +people that the reader will not likely know, is not that one page I +would like all to read. I suggest moving the history to the back of +the report, and use the first couple of pages to convince the reader +that the language documented in this report is worth studying. + +@end ignore + + +@node Background, Acknowledgements, Introduction, Introduction +@unnumberedsec Background + + +The first description of Scheme was written in +1975 [Scheme75]. A revised report [Scheme78] +@ignore todo +italicize or not? +@end ignore + appeared in 1978, which described the evolution +of the language as its MIT implementation was upgraded to support an +innovative compiler [Rabbit]. Three distinct projects began in +1981 and 1982 to use variants of Scheme for courses at MIT, Yale, and +Indiana University [Rees82], [MITScheme], [Scheme311]. An introductory +computer science textbook using Scheme was published in +1984 [SICP]. + +@c \vest As might be expected of a language used primarily for education and +@c research, Scheme has always evolved rapidly. This was no problem when +@c Scheme was used only within MIT, but +As Scheme became more widespread, +local dialects began to diverge until students and researchers +occasionally found it difficult to understand code written at other +sites. +Fifteen representatives of the major implementations of Scheme therefore +met in October 1984 to work toward a better and more widely accepted +standard for Scheme. +@c Participating in this workshop were Hal Abelson, Norman Adams, David +@c Bartley, Gary Brooks, William Clinger, Daniel Friedman, Robert Halstead, +@c Chris Hanson, Christopher Haynes, Eugene Kohlbecker, Don Oxley, Jonathan Rees, +@c Guillermo Rozas, Gerald Jay Sussman, and Mitchell Wand. Kent Pitman +@c made valuable contributions to the agenda for the workshop but was +@c unable to attend the sessions. + +@c Subsequent electronic mail discussions and committee work completed the +@c definition of the language. +@c Gerry Sussman drafted the section on numbers, Chris Hanson drafted the +@c sections on characters and strings, and Gary Brooks and William Clinger +@c drafted the sections on input and output. +@c William Clinger recorded the decisions of the workshop and +@c compiled the pieces into a coherent document. +@c The ``Revised revised report on Scheme''~\cite{RRRS} +Their report [RRRS] +was published at MIT and Indiana University in the summer of 1985. +Further revision took place in the spring of 1986 [R3RS], +@c , again accomplished +@c almost entirely by electronic mail, resulted in the present report. +and in the spring of 1988 [R4RS]. +The present report reflects further revisions agreed upon in a meeting +at Xerox PARC in June 1992. + +@c \vest The number 3 in the title is part of the title, not a reference to +@c a footnote. The word ``revised'' is raised to the third power because +@c the report is a revision of a report that was already twice revised. + +@ignore todo +Write an editors' note? +@end ignore + + + +@sp 3 + +We intend this report to belong to the entire Scheme community, and so +we grant permission to copy it in whole or in part without fee. In +particular, we encourage implementors of Scheme to use this report as +a starting point for manuals and other documentation, modifying it as +necessary. + + + + +@node Acknowledgements, , Background, Introduction +@unnumberedsec Acknowledgements + + +We would like to thank the following people for their help: Alan Bawden, Michael +Blair, George Carrette, Andy Cromarty, Pavel Curtis, Jeff Dalton, Olivier Danvy, +Ken Dickey, Bruce Duba, Marc Feeley, +Andy Freeman, Richard Gabriel, Yekta G"ursel, Ken Haase, Robert +Hieb, Paul Hudak, Morry Katz, Chris Lindblad, Mark Meyer, Jim Miller, Jim Philbin, +John Ramsdell, Mike Shaff, Jonathan Shapiro, Julie Sussman, +Perry Wagle, Daniel Weise, Henry Wu, and Ozan Yigit. +We thank Carol Fessenden, Daniel +Friedman, and Christopher Haynes for permission to use text from the Scheme 311 +version 4 reference manual. We thank Texas Instruments, Inc. for permission to +use text from the @emph{TI Scheme Language Reference Manual}[TImanual85]. +We gladly acknowledge the influence of manuals for MIT Scheme[MITScheme], +T[Rees84], Scheme 84[Scheme84],Common Lisp[CLtL], +and Algol 60[Naur63]. + +We also thank Betty Dexter for the extreme effort she put into +setting this report in @TeX{}, and Donald Knuth for designing the program +that caused her troubles. + +The Artificial Intelligence Laboratory of the +Massachusetts Institute of Technology, the Computer Science +Department of Indiana University, the Computer and Information +Sciences Department of the University of Oregon, and the NEC Research +Institute supported the preparation of this report. Support for the MIT +work was provided in part by +the Advanced Research Projects Agency of the Department of Defense under Office +of Naval Research contract N00014-80-C-0505. Support for the Indiana +University work was provided by NSF grants NCS 83-04567 and NCS +83-03325. + + + + +@sp 2 + +@c \clearchapterstar{Description of the language} %\unskip\vskip -2ex +@c @include{struct} + +@c 1. Structure of the language + +@node Overview of Scheme, Lexical conventions, Introduction, top +@chapter Overview of Scheme + +@menu +* Semantics:: +* Syntax:: +* Notation and terminology:: +@end menu + + +@node Semantics, Syntax, Overview of Scheme, Overview of Scheme +@section Semantics + + + +This section gives an overview of Scheme's semantics. A +detailed informal semantics is the subject of +chapters @ref{Basic concepts} through @ref{Standard procedures}. For reference +purposes, section @ref{Formal semantics} provides a formal +semantics of Scheme. + +Following Algol, Scheme is a statically scoped programming +language. Each use of a variable is associated with a lexically +apparent binding of that variable. + +Scheme has latent as opposed to manifest types. Types +are associated with values (also called objects) rather than +@cindex @w{object} +with variables. (Some authors refer to languages with latent types as +weakly typed or dynamically typed languages.) Other languages with +latent types are APL, Snobol, and other dialects of Lisp. Languages +with manifest types (sometimes referred to as strongly typed or +statically typed languages) include Algol 60, Pascal, and C. + +All objects created in the course of a Scheme computation, including +procedures and continuations, have unlimited extent. +No Scheme object is ever destroyed. The reason that +implementations of Scheme do not (usually!) run out of storage is that +they are permitted to reclaim the storage occupied by an object if +they can prove that the object cannot possibly matter to any future +computation. Other languages in which most objects have unlimited +extent include APL and other Lisp dialects. + +Implementations of Scheme are required to be properly tail-recursive. +This allows the execution of an iterative computation in constant space, +even if the iterative computation is described by a syntactically +recursive procedure. Thus with a properly tail-recursive implementation, +iteration can be expressed using the ordinary procedure-call +mechanics, so that special iteration constructs are useful only as +syntactic sugar. See section @ref{Proper tail recursion}. + +Scheme procedures are objects in their own right. Procedures can be +created dynamically, stored in data structures, returned as results of +procedures, and so on. Other languages with these properties include +Common Lisp and ML. +@ignore todo +Rozas: Scheme had them first. +@end ignore + + +One distinguishing feature of Scheme is that continuations, which +in most other languages only operate behind the scenes, also have +``first-class'' status. Continuations are useful for implementing a +wide variety of advanced control constructs, including non-local exits, +backtracking, and coroutines. See section @ref{Control features}. + +Arguments to Scheme procedures are always passed by value, which +means that the actual argument expressions are evaluated before the +procedure gains control, whether the procedure needs the result of the +evaluation or not. ML, C, and APL are three other languages that always +pass arguments by value. +This is distinct from the lazy-evaluation semantics of Haskell, +or the call-by-name semantics of Algol 60, where an argument +expression is not evaluated unless its value is needed by the +procedure. + +@ignore todo +Lisp's call by value should be explained more +accurately. What's funny is that all values are references. +@end ignore + + +Scheme's model of arithmetic is designed to remain as independent as +possible of the particular ways in which numbers are represented within a +computer. In Scheme, every integer is a rational number, every rational is a +real, and every real is a complex number. Thus the distinction between integer +and real arithmetic, so important to many programming languages, does not +appear in Scheme. In its place is a distinction between exact arithmetic, +which corresponds to the mathematical ideal, and inexact arithmetic on +approximations. As in Common Lisp, exact arithmetic is not limited to +integers. + +@node Syntax, Notation and terminology, Semantics, Overview of Scheme +@section Syntax + + +Scheme, like most dialects of Lisp, employs a fully parenthesized prefix +notation for programs and (other) data; the grammar of Scheme generates a +sublanguage of the language used for data. An important +consequence of this simple, uniform representation is the susceptibility of +Scheme programs and data to uniform treatment by other Scheme programs. +For example, the @samp{eval} procedure evaluates a Scheme program expressed +as data. + +The @samp{read} procedure performs syntactic as well as lexical decomposition of +the data it reads. The @samp{read} procedure parses its input as data +(section @pxref{External representation}), not as program. + +The formal syntax of Scheme is described in section @ref{Formal syntax}. + + +@node Notation and terminology, , Syntax, Overview of Scheme +@section Notation and terminology + +@menu +* Primitive; library; and optional features:: +* Error situations and unspecified behavior:: +* Entry format:: +* Evaluation examples:: +* Naming conventions:: +@end menu + + + +@node Primitive; library; and optional features, Error situations and unspecified behavior, Notation and terminology, Notation and terminology +@subsection Primitive; library; and optional features + + + +It is required that every implementation of Scheme support all +features that are not marked as being @dfn{optional}. Implementations are +@cindex @w{optional} +free to omit optional features of Scheme or to add extensions, +provided the extensions are not in conflict with the language reported +here. In particular, implementations must support portable code by +providing a syntactic mode that preempts no lexical conventions of this +report. + +To aid in understanding and implementing Scheme, some features are marked +as @dfn{library}. These can be easily implemented in terms of the other, +@cindex @w{library} +primitive, features. They are redundant in the strict sense of +the word, but they capture common patterns of usage, and are therefore +provided as convenient abbreviations. + +@node Error situations and unspecified behavior, Entry format, Primitive; library; and optional features, Notation and terminology +@subsection Error situations and unspecified behavior + + + +@cindex @w{error} +When speaking of an error situation, this report uses the phrase ``an +error is signalled'' to indicate that implementations must detect and +report the error. If such wording does not appear in the discussion of +an error, then implementations are not required to detect or report the +error, though they are encouraged to do so. An error situation that +implementations are not required to detect is usually referred to simply +as ``an error.'' + +For example, it is an error for a procedure to be passed an argument that +the procedure is not explicitly specified to handle, even though such +domain errors are seldom mentioned in this report. Implementations may +extend a procedure's domain of definition to include such arguments. + +This report uses the phrase ``may report a violation of an +implementation restriction'' to indicate circumstances under which an +implementation is permitted to report that it is unable to continue +execution of a correct program because of some restriction imposed by the +implementation. Implementation restrictions are of course discouraged, +but implementations are encouraged to report violations of implementation +restrictions. +@cindex @w{implementation restriction} + +For example, an implementation may report a violation of an +implementation restriction if it does not have enough storage to run a +program. + +If the value of an expression is said to be ``unspecified,'' then +the expression must evaluate to some object without signalling an error, +but the value depends on the implementation; this report explicitly does +not say what value should be returned. +@cindex @w{unspecified} + +@ignore todo +Talk about unspecified behavior vs. unspecified values. +@end ignore + + +@ignore todo +Look at KMP's situations paper. +@end ignore + + + +@node Entry format, Evaluation examples, Error situations and unspecified behavior, Notation and terminology +@subsection Entry format + + +Chapters @ref{Expressions} and @ref{Standard procedures} are organized +into entries. Each entry describes one language feature or a group of +related features, where a feature is either a syntactic construct or a +built-in procedure. An entry begins with one or more header lines of the form + + +@noindent +@deffn {@var{category}} @var{template} + +@end deffn + +for required, primitive features, or + + +@noindent +@deffn {@var{qualifier} @var{category}} @var{template} + +@end deffn + +where @var{qualifier} is either ``library'' or ``optional'' as defined + in section @ref{Primitive; library; and optional features}. + +If @var{category} is ``syntax'', the entry describes an expression +type, and the template gives the syntax of the expression type. +Components of expressions are designated by syntactic variables, which +are written using angle brackets, for example, @r{<expression>}, +@r{<variable>}. Syntactic variables should be understood to denote segments of +program text; for example, @r{<expression>} stands for any string of +characters which is a syntactically valid expression. The notation + +@format + @r{<thing1>} @dots{} +@end format + +indicates zero or more occurrences of a @r{<thing>}, and + +@format + @r{<thing1>} @r{<thing2>} @dots{} +@end format + +indicates one or more occurrences of a @r{<thing>}. + +If @var{category} is ``procedure'', then the entry describes a procedure, and +the header line gives a template for a call to the procedure. Argument +names in the template are @var{italicized}. Thus the header line + + +@noindent +@deffn {procedure} vector-ref @var{vector} @var{k} + +@end deffn + +indicates that the built-in procedure @t{vector-ref} takes +two arguments, a vector @var{vector} and an exact non-negative integer +@var{k} (see below). The header lines + + +@noindent + +@deffn {procedure} make-vector @var{k} + + +@deffnx {procedure} make-vector @var{k} @var{fill} + +@end deffn + +indicate that the @t{make-vector} procedure must be defined to take +either one or two arguments. + + +It is an error for an operation to be presented with an argument that it +is not specified to handle. For succinctness, we follow the convention +that if an argument name is also the name of a type listed in +section @ref{Disjointness of types}, then that argument must be of the named type. +For example, the header line for @t{vector-ref} given above dictates that the +first argument to @t{vector-ref} must be a vector. The following naming +conventions also imply type restrictions: +@c \newcommand{\foo}[1]{\vr{#1}, \vri{#1}, $\ldots$ \vrj{#1}, $\ldots$} + + +@center @c begin-tabular +@quotation +@table @asis +@item @var{obj} +any object +@item @var{list}, @var{list1}, @dots{} @var{listj}, @dots{} +list (see section @pxref{Pairs and lists}) +@item @var{z}, @var{z1}, @dots{} @var{zj}, @dots{} +complex number +@item @var{x}, @var{x1}, @dots{} @var{xj}, @dots{} +real number +@item @var{y}, @var{y1}, @dots{} @var{yj}, @dots{} +real number +@item @var{q}, @var{q1}, @dots{} @var{qj}, @dots{} +rational number +@item @var{n}, @var{n1}, @dots{} @var{nj}, @dots{} +integer +@item @var{k}, @var{k1}, @dots{} @var{kj}, @dots{} +exact non-negative integer +@item +@end table +@end quotation + + + + +@ignore todo +Provide an example entry?? +@end ignore + + + +@node Evaluation examples, Naming conventions, Entry format, Notation and terminology +@subsection Evaluation examples + + +The symbol ``@result{}'' used in program examples should be read +``evaluates to.'' For example, + + +@example + +(* 5 8) ==> 40 + +@end example + + +means that the expression @t{(* 5 8)} evaluates to the object @t{40}. +Or, more precisely: the expression given by the sequence of characters +``@t{(* 5 8)}'' evaluates, in the initial environment, to an object +that may be represented externally by the sequence of characters ``@t{40}''. See section @ref{External representations} for a discussion of external +representations of objects. + +@node Naming conventions, , Evaluation examples, Notation and terminology +@subsection Naming conventions + + +By convention, the names of procedures that always return a boolean +value usually end +in ``@code{?}''. Such procedures are called predicates. +@vindex @w{?} + +By convention, the names of procedures that store values into previously +allocated locations (see section @pxref{Storage model}) usually end in +``@code{!}''. +@vindex @w{!} +Such procedures are called mutation procedures. +By convention, the value returned by a mutation procedure is unspecified. + +By convention, ``@code{->}'' appears within the names of procedures that +@vindex @w{->} +take an object of one type and return an analogous object of another type. +For example, @samp{list->vector} takes a list and returns a vector whose +elements are the same as those of the list. + + + +@ignore todo +Terms that need defining: thunk, command (what else?). +@end ignore + + +@c @include{lex} + +@c Lexical structure + +@c %\vfill\eject +@node Lexical conventions, Basic concepts, Overview of Scheme, top +@chapter Lexical conventions + +@menu +* Identifiers:: +* Whitespace and comments:: +* Other notations:: +@end menu + + +This section gives an informal account of some of the lexical +conventions used in writing Scheme programs. For a formal syntax of +Scheme, see section @ref{Formal syntax}. + +Upper and lower case forms of a letter are never distinguished +except within character and string constants. For example, @samp{Foo} is +the same identifier as @samp{FOO}, and @t{#x1AB} is the same number as +@t{#X1ab}. + +@node Identifiers, Whitespace and comments, Lexical conventions, Lexical conventions +@section Identifiers + + + +Most identifiers allowed by other programming +@cindex @w{identifier} +languages are also acceptable to Scheme. The precise rules for forming +identifiers vary among implementations of Scheme, but in all +implementations a sequence of letters, digits, and ``extended alphabetic +characters'' that begins with a character that cannot begin a number is +an identifier. In addition, @code{+}, @code{-}, and @code{...} are identifiers. +@vindex @w{...} +@vindex @w{-} +@vindex @w{+} +Here are some examples of identifiers: + + +@example + +lambda q +list->vector soup ++ V17a +<=? a34kTMNs +the-word-recursion-has-many-meanings + +@end example + + +Extended alphabetic characters may be used within identifiers as if +they were letters. The following are extended alphabetic characters: + + +@example + +! $ % & * + - . / : < = > ? @@ ^ _ ~ +@end example + + +See section @ref{Lexical structure} for a formal syntax of identifiers. + +Identifiers have two uses within Scheme programs: + + +@itemize @bullet + +@item +Any identifier may be used as a variable +or as a syntactic keyword +(see sections @pxref{Variables; syntactic keywords; and regions} and @pxref{Macros}). + +@item +When an identifier appears as a literal or within a literal +(see section @pxref{Literal expressions}), it is being used to denote a @emph{symbol} +(see section @pxref{Symbols}). + + +@end itemize + +@cindex @w{syntactic keyword} +@cindex @w{variable} + +@c \label{keywordsection} +@c The following identifiers are syntactic keywords, and should not be used +@c as variables: + +@c \begin{scheme} +@c => do or +@c and else quasiquote +@c begin if quote +@c case lambda set! +@c cond let unquote +@c define let* unquote-splicing +@c delay letrec% +@c \end{scheme} + +@c Some implementations allow all identifiers, including syntactic +@c keywords, to be used as variables. This is a compatible extension to +@c the language, but ambiguities in the language result when the +@c restriction is relaxed, and the ways in which these ambiguities are +@c resolved vary between implementations. + + +@node Whitespace and comments, Other notations, Identifiers, Lexical conventions +@section Whitespace and comments + + +@dfn{Whitespace} characters are spaces and newlines. +@cindex @w{Whitespace} +(Implementations typically provide additional whitespace characters such +as tab or page break.) Whitespace is used for improved readability and +as necessary to separate tokens from each other, a token being an +indivisible lexical unit such as an identifier or number, but is +otherwise insignificant. Whitespace may occur between any two tokens, +but not within a token. Whitespace may also occur inside a string, +where it is significant. + +A semicolon (@t{;}) indicates the start of a +comment. The comment continues to the +@cindex @w{;} +@cindex @w{comment} +end of the line on which the semicolon appears. Comments are invisible +to Scheme, but the end of the line is visible as whitespace. This +prevents a comment from appearing in the middle of an identifier or +number. + + +@example + +;;; The FACT procedure computes the factorial +;;; of a non-negative integer. +(define fact + (lambda (n) + (if (= n 0) + 1 ;Base case: return 1 + (* n (fact (- n 1)))))) + +@end example + + + +@node Other notations, , Whitespace and comments, Lexical conventions +@section Other notations + + +@ignore todo +Rewrite? +@end ignore + + +For a description of the notations used for numbers, see +section @ref{Numbers}. + + +@table @t + + +@item @t{.@: + -} +These are used in numbers, and may also occur anywhere in an identifier +except as the first character. A delimited plus or minus sign by itself +is also an identifier. +A delimited period (not occurring within a number or identifier) is used +in the notation for pairs (section @pxref{Pairs and lists}), and to indicate a +rest-parameter in a formal parameter list (section @pxref{Procedures}). +A delimited sequence of three successive periods is also an identifier. + +@item @t{( )} +Parentheses are used for grouping and to notate lists +(section @pxref{Pairs and lists}). + +@item @t{'} +The single quote character is used to indicate literal data (section @pxref{Literal expressions}). + +@item @t{`} +The backquote character is used to indicate almost-constant +data (section @pxref{Quasiquotation}). + +@item @t{, ,@@} +The character comma and the sequence comma at-sign are used in conjunction +with backquote (section @pxref{Quasiquotation}). + +@item @t{"} +The double quote character is used to delimit strings (section @pxref{Strings}). + +@item \ +Backslash is used in the syntax for character constants +(section @pxref{Characters}) and as an escape character within string +constants (section @pxref{Strings}). + +@c A box used because \verb is not allowed in command arguments. + +@item @w{@t{[ ] @{ @} |}} +Left and right square brackets and curly braces and vertical bar +are reserved for possible future extensions to the language. + +@item # + Sharp sign is used for a variety of purposes depending on +the character that immediately follows it: + +@item @t{#t} @t{#f} +These are the boolean constants (section @pxref{Booleans}). + +@item #\ +This introduces a character constant (section @pxref{Characters}). + +@item #@t{(} +This introduces a vector constant (section @pxref{Vectors}). Vector constants +are terminated by @t{)} . + +@item @t{#e #i #b #o #d #x} +These are used in the notation for numbers (section @pxref{Syntax of numerical constants}). + +@end table + + +@c @include{basic} + +@c \vfill\eject +@node Basic concepts, Expressions, Lexical conventions, top +@chapter Basic concepts + +@menu +* Variables; syntactic keywords; and regions:: +* Disjointness of types:: +* External representations:: +* Storage model:: +* Proper tail recursion:: +@end menu + + + +@node Variables; syntactic keywords; and regions, Disjointness of types, Basic concepts, Basic concepts +@section Variables; syntactic keywords; and regions + + + + +An identifier may name a type of syntax, or it may name +@cindex @w{identifier} +a location where a value can be stored. An identifier that names a type +of syntax is called a @emph{syntactic keyword} +@cindex @w{syntactic keyword} +and is said to be @emph{bound} to that syntax. An identifier that names a +location is called a @emph{variable} and is said to be +@cindex @w{variable} +@emph{bound} to that location. The set of all visible +bindings in effect at some point in a program is +@cindex @w{binding} +known as the @emph{environment} in effect at that point. The value +stored in the location to which a variable is bound is called the +variable's value. By abuse of terminology, the variable is sometimes +said to name the value or to be bound to the value. This is not quite +accurate, but confusion rarely results from this practice. + +@ignore todo +Define ``assigned'' and ``unassigned'' perhaps? +@end ignore + + +@ignore todo +In programs without side effects, one can safely pretend that the +variables are bound directly to the arguments. Or: +In programs without @code{set!}, one can safely pretend that the +@vindex @w{set!} +variable is bound directly to the value. +@end ignore + + +Certain expression types are used to create new kinds of syntax +and bind syntactic keywords to those new syntaxes, while other +expression types create new locations and bind variables to those +locations. These expression types are called @emph{binding constructs}. + +@cindex @w{binding construct} +Those that bind syntactic keywords are listed in section @ref{Macros}. +The most fundamental of the variable binding constructs is the +@samp{lambda} expression, because all other variable binding constructs +can be explained in terms of @samp{lambda} expressions. The other +variable binding constructs are @samp{let}, @samp{let*}, @samp{letrec}, +and @samp{do} expressions (see sections @pxref{Procedures}, @pxref{Binding constructs}, and +@pxref{Iteration}). + +@c Note: internal definitions not mentioned here. + +Like Algol and Pascal, and unlike most other dialects of Lisp +except for Common Lisp, Scheme is a statically scoped language with +block structure. To each place where an identifier is bound in a program +there corresponds a @dfn{region} of the program text within which +@cindex @w{region} +the binding is visible. The region is determined by the particular +binding construct that establishes the binding; if the binding is +established by a @samp{lambda} expression, for example, then its region +is the entire @samp{lambda} expression. Every mention of an identifier +refers to the binding of the identifier that established the +innermost of the regions containing the use. If there is no binding of +the identifier whose region contains the use, then the use refers to the +binding for the variable in the top level environment, if any +(chapters @pxref{Expressions} and @pxref{Standard procedures}); if there is no +binding for the identifier, +it is said to be @dfn{unbound}. +@cindex @w{top level environment} +@cindex @w{bound} +@cindex @w{unbound} + +@ignore todo +Mention that some implementations have multiple top level environments? +@end ignore + + +@ignore todo +Pitman sez: needs elaboration in case of @t{(let ...)} +@end ignore + + +@ignore todo +Pitman asks: say something about vars created after scheme starts? +@t{(define x 3) (define (f) x) (define (g) y) (define y 4)} +Clinger replies: The language was explicitly +designed to permit a view in which no variables are created after +Scheme starts. In files, you can scan out the definitions beforehand. +I think we're agreed on the principle that interactive use should +approximate that behavior as closely as possible, though we don't yet +agree on which programming environment provides the best approximation. +@end ignore + + +@node Disjointness of types, External representations, Variables; syntactic keywords; and regions, Basic concepts +@section Disjointness of types + + + +No object satisfies more than one of the following predicates: + + +@example + +boolean? pair? +symbol? number? +char? string? +vector? port? +procedure? + +@end example + + +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 +object of its own type; it satisfies none of the above predicates. + +@vindex symbol? +@vindex pair? +@vindex boolean? +@cindex @w{type} + +@vindex vector? +@vindex string? +@vindex char? +@vindex number? + +@cindex @w{empty list} +@vindex procedure? +@vindex port? + +Although there is a separate boolean type, +any Scheme value can be used as a boolean value for the purpose of a +conditional test. As explained in section @ref{Booleans}, all +values count as true in such a test except for @t{#f}. +@c and possibly the empty list. +@c The only value that is guaranteed to count as +@c false is \schfalse{}. It is explicitly unspecified whether the empty list +@c counts as true or as false. +This report uses the word ``true'' to refer to any +Scheme value except @t{#f}, and the word ``false'' to refer to +@t{#f}. +@cindex @w{false} +@cindex @w{true} + +@node External representations, Storage model, Disjointness of types, Basic concepts +@section External representations + + + +An important concept in Scheme (and Lisp) is that of the @emph{external +representation} of an object as a sequence of characters. For example, +an external representation of the integer 28 is the sequence of +characters ``@t{28}'', and an external representation of a list consisting +of the integers 8 and 13 is the sequence of characters ``@t{(8 13)}''. + +The external representation of an object is not necessarily unique. The +integer 28 also has representations ``@t{#e28.000}'' and ``@t{#x1c}'', and the +list in the previous paragraph also has the representations ``@t{( 08 13 +)}'' and ``@t{(8 .@: (13 .@: ()))}'' (see section @pxref{Pairs and lists}). + +Many objects have standard external representations, but some, such as +procedures, do not have standard representations (although particular +implementations may define representations for them). + +An external representation may be written in a program to obtain the +corresponding object (see @samp{quote}, section @pxref{Literal expressions}). + +External representations can also be used for input and output. The +procedure @samp{read} (section @pxref{Input}) parses external +representations, and the procedure @samp{write} (section @pxref{Output}) +generates them. Together, they provide an elegant and powerful +input/output facility. + +Note that the sequence of characters ``@t{(+ 2 6)}'' is @emph{not} an +external representation of the integer 8, even though it @emph{is} an +expression evaluating to the integer 8; rather, it is an external +representation of a three-element list, the elements of which are the symbol +@t{+} and the integers 2 and 6. Scheme's syntax has the property that +any sequence of characters that is an expression is also the external +representation of some object. This can lead to confusion, since it may +not be obvious out of context whether a given sequence of characters is +intended to denote data or program, but it is also a source of power, +since it facilitates writing programs such as interpreters and +compilers that treat programs as data (or vice versa). + +The syntax of external representations of various kinds of objects +accompanies the description of the primitives for manipulating the +objects in the appropriate sections of chapter @ref{Standard procedures}. + +@node Storage model, Proper tail recursion, External representations, Basic concepts +@section Storage model + + + +Variables and objects such as pairs, vectors, and strings implicitly +denote locations or sequences of locations. A string, for +@cindex @w{location} +example, denotes as many locations as there are characters in the string. +(These locations need not correspond to a full machine word.) A new value may be +stored into one of these locations using the @t{string-set!} procedure, but +the string continues to denote the same locations as before. + +An object fetched from a location, by a variable reference or by +a procedure such as @samp{car}, @samp{vector-ref}, or @samp{string-ref}, is +equivalent in the sense of @code{eqv?} +@c and \ide{eq?} ?? +(section @pxref{Equivalence predicates}) +@vindex @w{eqv?} +to the object last stored in the location before the fetch. + +Every location is marked to show whether it is in use. +No variable or object ever refers to a location that is not in use. +Whenever this report speaks of storage being allocated for a variable +or object, what is meant is that an appropriate number of locations are +chosen from the set of locations that are not in use, and the chosen +locations are marked to indicate that they are now in use before the variable +or object is made to denote them. + +In many systems it is desirable for constants (i.e. the values of +@cindex @w{constant} +literal expressions) to reside in read-only-memory. To express this, it is +convenient to imagine that every object that denotes locations is associated +with a flag telling whether that object is mutable or +@cindex @w{mutable} +immutable. In such systems literal constants and the strings +@cindex @w{immutable} +returned by @code{symbol->string} are immutable objects, while all objects +@vindex @w{symbol->string} +created by the other procedures listed in this report are mutable. It is an +error to attempt to store a new value into a location that is denoted by an +immutable object. + +@node Proper tail recursion, , Storage model, Basic concepts +@section Proper tail recursion + + + +Implementations of Scheme are required to be +@emph{properly tail-recursive}. +@cindex @w{proper tail recursion} +Procedure calls that occur in certain syntactic +contexts defined below are `tail calls'. A Scheme implementation is +properly tail-recursive if it supports an unbounded number of active +tail calls. A call is @emph{active} if the called procedure may still +return. Note that this includes calls that may be returned from either +by the current continuation or by continuations captured earlier by +@samp{call-with-current-continuation} that are later invoked. +In the absence of captured continuations, calls could +return at most once and the active calls would be those that had not +yet returned. +A formal definition of proper tail recursion can be found +in [propertailrecursion]. + + +@quotation +@emph{Rationale:} + +Intuitively, no space is needed for an active tail call because the +continuation that is used in the tail call has the same semantics as the +continuation passed to the procedure containing the call. Although an improper +implementation might use a new continuation in the call, a return +to this new continuation would be followed immediately by a return +to the continuation passed to the procedure. A properly tail-recursive +implementation returns to that continuation directly. + +Proper tail recursion was one of the central ideas in Steele and +Sussman's original version of Scheme. Their first Scheme interpreter +implemented both functions and actors. Control flow was expressed using +actors, which differed from functions in that they passed their results +on to another actor instead of returning to a caller. In the terminology +of this section, each actor finished with a tail call to another actor. + +Steele and Sussman later observed that in their interpreter the code +for dealing with actors was identical to that for functions and thus +there was no need to include both in the language. + +@end quotation + + +A @emph{tail call} is a procedure call that occurs +@cindex @w{tail call} +in a @emph{tail context}. Tail contexts are defined inductively. Note +that a tail context is always determined with respect to a particular lambda +expression. + + + +@itemize @bullet + +@item +The last expression within the body of a lambda expression, +shown as @r{<tail expression>} below, occurs in a tail context. + +@format +@t{(lambda <formals> + <definition>* <expression>* <tail expression>) +} + +@end format + + + +@item +If one of the following expressions is in a tail context, +then the subexpressions shown as <tail expression> are in a tail context. +These were derived from rules in the grammar given in +chapter @ref{Formal syntax and semantics} by replacing some occurrences of <expression> +with <tail expression>. Only those rules that contain tail contexts +are shown here. + + +@format +@t{(if <expression> <tail expression> <tail expression>) +(if <expression> <tail expression>) + +(cond <cond clause>+) +(cond <cond clause>* (else <tail sequence>)) + +(case <expression> + <case clause>+) +(case <expression> + <case clause>* + (else <tail sequence>)) + +(and <expression>* <tail expression>) +(or <expression>* <tail expression>) + +(let (<binding spec>*) <tail body>) +(let <variable> (<binding spec>*) <tail body>) +(let* (<binding spec>*) <tail body>) +(letrec (<binding spec>*) <tail body>) + +(let-syntax (<syntax spec>*) <tail body>) +(letrec-syntax (<syntax spec>*) <tail body>) + +(begin <tail sequence>) + +(do (<iteration spec>*) + (<test> <tail sequence>) + <expression>*) + +@r{where} + +<cond clause> --> (<test> <tail sequence>) +<case clause> --> ((<datum>*) <tail sequence>) + +<tail body> --> <definition>* <tail sequence> +<tail sequence> --> <expression>* <tail expression> +} + +@end format + + + +@item +If a @samp{cond} expression is in a tail context, and has a clause of +the form @samp{(@r{<expression1>} => @r{<expression2>})} +then the (implied) call to +the procedure that results from the evaluation of @r{<expression2>} is in a +tail context. @r{<expression2>} itself is not in a tail context. + + +@end itemize + + +Certain built-in procedures are also required to perform tail calls. +The first argument passed to @code{apply} and to +@vindex @w{apply} +@code{call-with-current-continuation}, and the second argument passed to +@vindex @w{call-with-current-continuation} +@code{call-with-values}, must be called via a tail call. +@vindex @w{call-with-values} +Similarly, @code{eval} must evaluate its argument as if it +@vindex @w{eval} +were in tail position within the @code{eval} procedure. +@vindex @w{eval} + +In the following example the only tail call is the call to @samp{f}. +None of the calls to @samp{g} or @samp{h} are tail calls. The reference to +@samp{x} is in a tail context, but it is not a call and thus is not a +tail call. + +@example + +(lambda () + (if (g) + (let ((x (h))) + x) + (and (g) (f)))) + +@end example + + + +@quotation +@emph{Note:} +Implementations are allowed, but not required, to +recognize that some non-tail calls, such as the call to @samp{h} +above, can be evaluated as though they were tail calls. +In the example above, the @samp{let} expression could be compiled +as a tail call to @samp{h}. (The possibility of @samp{h} returning +an unexpected number of values can be ignored, because in that +case the effect of the @samp{let} is explicitly unspecified and +implementation-dependent.) +@end quotation + + + +@c @include{expr} + +@c \vfill\eject +@node Expressions, Program structure, Basic concepts, top +@chapter Expressions + +@menu +* Primitive expression types:: +* Derived expression types:: +* Macros:: +@end menu + + + +@c \newcommand{\syntax}{{\em Syntax: }} +@c \newcommand{\semantics}{{\em Semantics: }} + +@c [Deleted for R5RS because of multiple-value returns. -RK] +@c A Scheme expression is a construct that returns a value, such as a +@c variable reference, literal, procedure call, or conditional. + +Expression types are categorized as @emph{primitive} or @emph{derived}. +Primitive expression types include variables and procedure calls. +Derived expression types are not semantically primitive, but can instead +be defined as macros. +With the exception of @samp{quasiquote}, whose macro definition is complex, +the derived expressions are classified as library features. +Suitable definitions are given in section @ref{Derived expression type}. + +@node Primitive expression types, Derived expression types, Expressions, Expressions +@section Primitive expression types + +@menu +* Variable references:: +* Literal expressions:: +* Procedure calls:: +* Procedures:: +* Conditionals:: +* Assignments:: +@end menu + + + +@node Variable references, Literal expressions, Primitive expression types, Primitive expression types +@subsection Variable references + + + +@deffn {syntax} @r{<variable>} + + +An expression consisting of a variable +@cindex @w{variable} +(section @pxref{Variables; syntactic keywords; and regions}) is a variable reference. The value of +the variable reference is the value stored in the location to which the +variable is bound. It is an error to reference an +unbound variable. +@cindex @w{unbound} + + +@format +@t{(define x 28) +x ==> 28 +} +@end format + +@end deffn + +@node Literal expressions, Procedure calls, Variable references, Primitive expression types +@subsection Literal expressions + + + + +@deffn {syntax} quote @r{<datum>} + +@deffnx {syntax} @t{'}@r{<datum>} + + +@deffnx {syntax} @r{<constant>} + + +@samp{(quote @r{<datum>})} evaluates to @r{<datum>}. +@cindex @w{'} +@r{<Datum>} +may be any external representation of a Scheme object (see +section @pxref{External representations}). This notation is used to include literal +constants in Scheme code. + + +@format +@t{ +(quote a) ==> a +(quote #(a b c)) ==> #(a b c) +(quote (+ 1 2)) ==> (+ 1 2) +} +@end format + + +@samp{(quote @r{<datum>})} may be abbreviated as +@t{'}@r{<datum>}. The two notations are equivalent in all +respects. + + +@format +@t{'a ==> a +'#(a b c) ==> #(a b c) +'() ==> () +'(+ 1 2) ==> (+ 1 2) +'(quote a) ==> (quote a) +''a ==> (quote a) +} +@end format + + +Numerical constants, string constants, character constants, and boolean +constants evaluate ``to themselves''; they need not be quoted. + + +@format +@t{'"abc" ==> "abc" +"abc" ==> "abc" +'145932 ==> 145932 +145932 ==> 145932 +'#t ==> #t +#t ==> #t +} +@end format + + +As noted in section @ref{Storage model}, it is an error to alter a constant +(i.e. the value of a literal expression) using a mutation procedure like +@samp{set-car!} or @samp{string-set!}. + +@end deffn + + +@node Procedure calls, Procedures, Literal expressions, Primitive expression types +@subsection Procedure calls + + + +@deffn {syntax} @r{<operator>} @r{<operand1>} @dots{}, + + +A procedure call is written by simply enclosing in parentheses +expressions for the procedure to be called and the arguments to be +passed to it. The operator and operand expressions are evaluated (in an +unspecified order) and the resulting procedure is passed the resulting +arguments. +@cindex @w{procedure call} +@cindex @w{call} + +@format +@t{ +(+ 3 4) ==> 7 +((if #f + *) 3 4) ==> 12 +} +@end format + + +A number of procedures are available as the values of variables in the +initial environment; for example, the addition and multiplication +procedures in the above examples are the values of the variables @samp{+} +and @samp{*}. New procedures are created by evaluating lambda expressions +(see section @pxref{Procedures}). +@ignore todo +At Friedman's request, flushed mention of other ways. +@end ignore + +@c or definitions (see section~\ref{define}). + +Procedure calls may return any number of values (see @code{values} in +@vindex @w{values} +section @pxref{Control features}). With the exception of @samp{values} +the procedures available in the initial environment return one +value or, for procedures such as @samp{apply}, pass on the values returned +by a call to one of their arguments. + +Procedure calls are also called @emph{combinations}. + +@cindex @w{combination} + + +@quotation +@emph{Note:} In contrast to other dialects of Lisp, the order of +evaluation is unspecified, and the operator expression and the operand +expressions are always evaluated with the same evaluation rules. +@end quotation + + + +@quotation +@emph{Note:} +Although the order of evaluation is otherwise unspecified, the effect of +any concurrent evaluation of the operator and operand expressions is +constrained to be consistent with some sequential order of evaluation. +The order of evaluation may be chosen differently for each procedure call. +@end quotation + + + +@quotation +@emph{Note:} In many dialects of Lisp, the empty combination, @t{()}, is a legitimate expression. In Scheme, combinations must have at +least one subexpression, so @t{()} is not a syntactically valid +expression. +@ignore todo +Dybvig: ``it should be obvious from the syntax.'' +@end ignore + +@end quotation + + +@ignore todo +Freeman: +I think an explanation as to why evaluation order is not specified +should be included. It should not include any reference to parallel +evaluation. Does any existing compiler generate better code because +the evaluation order is unspecified? Clinger: yes: T3, MacScheme v2, +probably MIT Scheme and Chez Scheme. But that's not the main reason +for leaving the order unspecified. +@end ignore + + +@end deffn + + +@node Procedures, Conditionals, Procedure calls, Primitive expression types +@subsection Procedures + + + + +@deffn {syntax} lambda @r{<formals>} @r{<body>} + +@emph{Syntax:} +@r{<Formals>} should be a formal arguments list as described below, +and @r{<body>} should be a sequence of one or more expressions. + +@emph{Semantics:} +A lambda expression evaluates to a procedure. The environment in +effect when the lambda expression was evaluated is remembered as part of the +procedure. When the procedure is later called with some actual +arguments, the environment in which the lambda expression was evaluated will +be extended by binding the variables in the formal argument list to +fresh locations, the corresponding actual argument values will be stored +in those locations, and the expressions in the body of the lambda expression +will be evaluated sequentially in the extended environment. +The result(s) of the last expression in the body will be returned as +the result(s) of the procedure call. + + +@format +@t{(lambda (x) (+ x x)) ==> @emph{}a procedure +((lambda (x) (+ x x)) 4) ==> 8 + +(define reverse-subtract + (lambda (x y) (- y x))) +(reverse-subtract 7 10) ==> 3 + +(define add4 + (let ((x 4)) + (lambda (y) (+ x y)))) +(add4 6) ==> 10 +} +@end format + + +@r{<Formals>} should have one of the following forms: + + + +@itemize @bullet + +@item +@t{(@r{<variable1>} @dots{},)}: +The procedure takes a fixed number of arguments; when the procedure is +called, the arguments will be stored in the bindings of the +corresponding variables. + +@item +@r{<variable>}: +The procedure takes any number of arguments; when the procedure is +called, the sequence of actual arguments is converted into a newly +allocated list, and the list is stored in the binding of the +@r{<variable>}. + +@item +@t{(@r{<variable1>} @dots{}, @r{<variable_n>} @b{.} +@r{<variable_n+1>})}: +If a space-delimited period precedes the last variable, then +the procedure takes n or more arguments, where n is the +number of formal arguments before the period (there must +be at least one). +The value stored in the binding of the last variable will be a +newly allocated +list of the actual arguments left over after all the other actual +arguments have been matched up against the other formal arguments. + +@end itemize + + +It is an error for a @r{<variable>} to appear more than once in +@r{<formals>}. + + +@format +@t{((lambda x x) 3 4 5 6) ==> (3 4 5 6) +((lambda (x y . z) z) + 3 4 5 6) ==> (5 6) +} +@end format + + +Each procedure created as the result of evaluating a lambda expression is +(conceptually) tagged +with a storage location, in order to make @code{eqv?} and +@vindex @w{eqv?} +@code{eq?} work on procedures (see section @pxref{Equivalence predicates}). +@vindex @w{eq?} + +@end deffn + + +@node Conditionals, Assignments, Procedures, Primitive expression types +@subsection Conditionals + + + +@deffn {syntax} if @r{<test>} @r{<consequent>} @r{<alternate>} +@deffnx {syntax} if @r{<test>} @r{<consequent>} +@c \/ if hyper = italic + +@emph{Syntax:} +@r{<Test>}, @r{<consequent>}, and @r{<alternate>} may be arbitrary +expressions. + +@emph{Semantics:} +An @samp{if} expression is evaluated as follows: first, +@r{<test>} is evaluated. If it yields a true value (see +@cindex @w{true} +section @pxref{Booleans}), then @r{<consequent>} is evaluated and +its value(s) is(are) returned. Otherwise @r{<alternate>} is evaluated and its +value(s) is(are) returned. If @r{<test>} yields a false value and no +@r{<alternate>} is specified, then the result of the expression is +unspecified. + + +@format +@t{(if (> 3 2) 'yes 'no) ==> yes +(if (> 2 3) 'yes 'no) ==> no +(if (> 3 2) + (- 3 2) + (+ 3 2)) ==> 1 +} +@end format + + +@end deffn + + +@node Assignments, , Conditionals, Primitive expression types +@subsection Assignments + + + + +@deffn {syntax} set! @r{<variable>} @r{<expression>} + +@r{<Expression>} is evaluated, and the resulting value is stored in +the location to which @r{<variable>} is bound. @r{<Variable>} must +be bound either in some region enclosing the @samp{set!} expression +@cindex @w{region} +or at top level. The result of the @samp{set!} expression is +unspecified. + + +@format +@t{(define x 2) +(+ x 1) ==> 3 +(set! x 4) ==> @emph{unspecified} +(+ x 1) ==> 5 +} +@end format + + +@end deffn + + +@node Derived expression types, Macros, Primitive expression types, Expressions +@section Derived expression types + +@menu +* Conditional:: +* Binding constructs:: +* Sequencing:: +* Iteration:: +* Delayed evaluation:: +* Quasiquotation:: +@end menu + + + +The constructs in this section are hygienic, as discussed in +section @ref{Macros}. +For reference purposes, section @ref{Derived expression type} gives macro definitions +that will convert most of the constructs described in this section +into the primitive constructs described in the previous section. + +@ignore todo +Mention that no definition of backquote is provided? +@end ignore + + +@node Conditional, Binding constructs, Derived expression types, Derived expression types +@subsection Conditionals + + + +@deffn {library syntax} cond <clause1> <clause2> @dots{}, + +@emph{Syntax:} +Each @r{<clause>} should be of the form + +@format +@t{(@r{<test>} @r{<expression1>} @dots{},) +} +@end format + +where @r{<test>} is any expression. Alternatively, a @r{<clause>} may be +of the form + +@format +@t{(@r{<test>} => @r{<expression>}) +} +@end format + +The last @r{<clause>} may be +an ``else clause,'' which has the form + +@format +@t{(else @r{<expression1>} @r{<expression2>} @dots{},)@r{.} +} +@end format + + +@cindex @w{else} + +@cindex @w{=>} + +@emph{Semantics:} +A @samp{cond} expression is evaluated by evaluating the @r{<test>} +expressions of successive @r{<clause>}s in order until one of them +evaluates to a true value (see +@cindex @w{true} +section @pxref{Booleans}). When a @r{<test>} evaluates to a true +value, then the remaining @r{<expression>}s in its @r{<clause>} are +evaluated in order, and the result(s) of the last @r{<expression>} in the +@r{<clause>} is(are) returned as the result(s) of the entire @samp{cond} +expression. If the selected @r{<clause>} contains only the +@r{<test>} and no @r{<expression>}s, then the value of the +@r{<test>} is returned as the result. If the selected @r{<clause>} uses the +@code{=>} alternate form, then the @r{<expression>} is evaluated. +@vindex @w{=>} +Its value must be a procedure that accepts one argument; this procedure is then +called on the value of the @r{<test>} and the value(s) returned by this +procedure is(are) returned by the @samp{cond} expression. +If all @r{<test>}s evaluate +to false values, and there is no else clause, then the result of +the conditional expression is unspecified; if there is an else +clause, then its @r{<expression>}s are evaluated, and the value(s) of +the last one is(are) returned. + + +@format +@t{(cond ((> 3 2) 'greater) + ((< 3 2) 'less)) ==> greater + +(cond ((> 3 3) 'greater) + ((< 3 3) 'less) + (else 'equal)) ==> equal + +(cond ((assv 'b '((a 1) (b 2))) => cadr) + (else #f)) ==> 2 +} +@end format + + + +@end deffn + + + +@deffn {library syntax} case @r{<key>} <clause1> <clause2> @dots{}, + +@emph{Syntax:} +@r{<Key>} may be any expression. Each @r{<clause>} should have +the form + +@format +@t{((@r{<datum1>} @dots{},) @r{<expression1>} @r{<expression2>} @dots{},)@r{,} +} +@end format + +where each @r{<datum>} is an external representation of some object. +All the @r{<datum>}s must be distinct. +The last @r{<clause>} may be an ``else clause,'' which has the form + +@format +@t{(else @r{<expression1>} @r{<expression2>} @dots{},)@r{.} +} +@end format + + +@vindex else + +@emph{Semantics:} +A @samp{case} expression is evaluated as follows. @r{<Key>} is +evaluated and its result is compared against each @r{<datum>}. If the +result of evaluating @r{<key>} is equivalent (in the sense of +@samp{eqv?}; see section @pxref{Equivalence predicates}) to a @r{<datum>}, then the +expressions in the corresponding @r{<clause>} are evaluated from left +to right and the result(s) of the last expression in the @r{<clause>} is(are) +returned as the result(s) of the @samp{case} expression. If the result of +evaluating @r{<key>} is different from every @r{<datum>}, then if +there is an else clause its expressions are evaluated and the +result(s) of the last is(are) the result(s) of the @samp{case} expression; +otherwise the result of the @samp{case} expression is unspecified. + + +@format +@t{(case (* 2 3) + ((2 3 5 7) 'prime) + ((1 4 6 8 9) 'composite)) ==> composite +(case (car '(c d)) + ((a) 'a) + ((b) 'b)) ==> @emph{unspecified} +(case (car '(c d)) + ((a e i o u) 'vowel) + ((w y) 'semivowel) + (else 'consonant)) ==> consonant +} +@end format + + +@end deffn + + + +@deffn {library syntax} and <test1> @dots{}, + +The @r{<test>} expressions are evaluated from left to right, and the +value of the first expression that evaluates to a false value (see +section @pxref{Booleans}) is returned. Any remaining expressions +are not evaluated. If all the expressions evaluate to true values, the +value of the last expression is returned. If there are no expressions +then @t{#t} is returned. + + +@format +@t{(and (= 2 2) (> 2 1)) ==> #t +(and (= 2 2) (< 2 1)) ==> #f +(and 1 2 'c '(f g)) ==> (f g) +(and) ==> #t +} +@end format + + +@end deffn + + + +@deffn {library syntax} or <test1> @dots{}, + +The @r{<test>} expressions are evaluated from left to right, and the value of the +first expression that evaluates to a true value (see +section @pxref{Booleans}) is returned. Any remaining expressions +are not evaluated. If all expressions evaluate to false values, the +value of the last expression is returned. If there are no +expressions then @t{#f} is returned. + + +@format +@t{(or (= 2 2) (> 2 1)) ==> #t +(or (= 2 2) (< 2 1)) ==> #t +(or #f #f #f) ==> #f +(or (memq 'b '(a b c)) + (/ 3 0)) ==> (b c) +} +@end format + + +@end deffn + + +@node Binding constructs, Sequencing, Conditional, Derived expression types +@subsection Binding constructs + + +The three binding constructs @samp{let}, @samp{let*}, and @samp{letrec} +give Scheme a block structure, like Algol 60. The syntax of the three +constructs is identical, but they differ in the regions they establish +@cindex @w{region} +for their variable bindings. In a @samp{let} expression, the initial +values are computed before any of the variables become bound; in a +@samp{let*} expression, the bindings and evaluations are performed +sequentially; while in a @samp{letrec} expression, all the bindings are in +effect while their initial values are being computed, thus allowing +mutually recursive definitions. + + +@deffn {library syntax} let @r{<bindings>} @r{<body>} + +@emph{Syntax:} +@r{<Bindings>} should have the form + +@format +@t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,} +} +@end format + +where each @r{<init>} is an expression, and @r{<body>} should be a +sequence of one or more expressions. It is +an error for a @r{<variable>} to appear more than once in the list of variables +being bound. + +@emph{Semantics:} +The @r{<init>}s are evaluated in the current environment (in some +unspecified order), the @r{<variable>}s are bound to fresh locations +holding the results, the @r{<body>} is evaluated in the extended +environment, and the value(s) of the last expression of @r{<body>} +is(are) returned. Each binding of a @r{<variable>} has @r{<body>} as its +region. +@cindex @w{region} + + +@format +@t{(let ((x 2) (y 3)) + (* x y)) ==> 6 + +(let ((x 2) (y 3)) + (let ((x 7) + (z (+ x y))) + (* z x))) ==> 35 +} +@end format + + +See also named @samp{let}, section @ref{Iteration}. + +@end deffn + + + +@deffn {library syntax} let* @r{<bindings>} @r{<body>} + + +@emph{Syntax:} +@r{<Bindings>} should have the form + +@format +@t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,} +} +@end format + +and @r{<body>} should be a sequence of +one or more expressions. + +@emph{Semantics:} +@samp{Let*} is similar to @samp{let}, but the bindings are performed +sequentially from left to right, and the region of a binding indicated +@cindex @w{region} +by @samp{(@r{<variable>} @r{<init>})} is that part of the @samp{let*} +expression to the right of the binding. Thus the second binding is done +in an environment in which the first binding is visible, and so on. + + +@format +@t{(let ((x 2) (y 3)) + (let* ((x 7) + (z (+ x y))) + (* z x))) ==> 70 +} +@end format + + +@end deffn + + + +@deffn {library syntax} letrec @r{<bindings>} @r{<body>} + +@emph{Syntax:} +@r{<Bindings>} should have the form + +@format +@t{((@r{<variable1>} @r{<init1>}) @dots{},)@r{,} +} +@end format + +and @r{<body>} should be a sequence of +one or more expressions. It is an error for a @r{<variable>} to appear more +than once in the list of variables being bound. + +@emph{Semantics:} +The @r{<variable>}s are bound to fresh locations holding undefined +values, the @r{<init>}s are evaluated in the resulting environment (in +some unspecified order), each @r{<variable>} is assigned to the result +of the corresponding @r{<init>}, the @r{<body>} is evaluated in the +resulting environment, and the value(s) of the last expression in +@r{<body>} is(are) returned. Each binding of a @r{<variable>} has the +entire @samp{letrec} expression as its region, making it possible to +@cindex @w{region} +define mutually recursive procedures. + + +@format +@t{(letrec ((even? + (lambda (n) + (if (zero? n) + #t + (odd? (- n 1))))) + (odd? + (lambda (n) + (if (zero? n) + #f + (even? (- n 1)))))) + (even? 88)) + ==> #t +} +@end format + + +One restriction on @samp{letrec} is very important: it must be possible +to evaluate each @r{<init>} without assigning or referring to the value of any +@r{<variable>}. If this restriction is violated, then it is an error. The +restriction is necessary because Scheme passes arguments by value rather than by +name. In the most common uses of @samp{letrec}, all the @r{<init>}s are +lambda expressions and the restriction is satisfied automatically. + +@c \todo{use or uses? --- Jinx.} + +@end deffn + + +@node Sequencing, Iteration, Binding constructs, Derived expression types +@subsection Sequencing + + + +@deffn {library syntax} begin <expression1> <expression2> @dots{}, + +The @r{<expression>}s are evaluated sequentially from left to right, +and the value(s) of the last @r{<expression>} is(are) returned. This +expression type is used to sequence side effects such as input and +output. + + +@format +@t{(define x 0) + +(begin (set! x 5) + (+ x 1)) ==> 6 + +(begin (display "4 plus 1 equals ") + (display (+ 4 1))) ==> @emph{unspecified} + @emph{and prints} 4 plus 1 equals 5 +} +@end format + + +@end deffn + + +@node Iteration, Delayed evaluation, Sequencing, Derived expression types +@subsection Iteration + +@c \unsection + + +@noindent + +@deffn {library syntax} do ((@r{<variable1>} @r{<init1>} @r{<step1>}) @dots{}) (@r{<test>} @r{<expression>} @dots{}) @r{<command>} @dots{} +@cindex @w{do} + +@samp{Do} is an iteration construct. It specifies a set of variables to +be bound, how they are to be initialized at the start, and how they are +to be updated on each iteration. When a termination condition is met, +the loop exits after evaluating the @r{<expression>}s. + +@samp{Do} expressions are evaluated as follows: +The @r{<init>} expressions are evaluated (in some unspecified order), +the @r{<variable>}s are bound to fresh locations, the results of the +@r{<init>} expressions are stored in the bindings of the +@r{<variable>}s, and then the iteration phase begins. + +Each iteration begins by evaluating @r{<test>}; if the result is +false (see section @pxref{Booleans}), then the @r{<command>} +expressions are evaluated in order for effect, the @r{<step>} +expressions are evaluated in some unspecified order, the +@r{<variable>}s are bound to fresh locations, the results of the +@r{<step>}s are stored in the bindings of the +@r{<variable>}s, and the next iteration begins. + +If @r{<test>} evaluates to a true value, then the +@r{<expression>}s are evaluated from left to right and the value(s) of +the last @r{<expression>} is(are) returned. If no @r{<expression>}s +are present, then the value of the @samp{do} expression is unspecified. + +The region of the binding of a @r{<variable>} +@cindex @w{region} +consists of the entire @samp{do} expression except for the @r{<init>}s. +It is an error for a @r{<variable>} to appear more than once in the +list of @samp{do} variables. + +A @r{<step>} may be omitted, in which case the effect is the +same as if @samp{(@r{<variable>} @r{<init>} @r{<variable>})} had +been written instead of @samp{(@r{<variable>} @r{<init>})}. + + +@format +@t{(do ((vec (make-vector 5)) + (i 0 (+ i 1))) + ((= i 5) vec) + (vector-set! vec i i)) ==> #(0 1 2 3 4) + +(let ((x '(1 3 5 7 9))) + (do ((x x (cdr x)) + (sum 0 (+ sum (car x)))) + ((null? x) sum))) ==> 25 +} +@end format + + +@c \end{entry} +@end deffn + + +@deffn {library syntax} let @r{<variable>} @r{<bindings>} @r{<body>} + + +``Named @samp{let}'' is a variant on the syntax of @code{let} which provides +@vindex @w{let} +a more general looping construct than @samp{do} and may also be used to express +recursions. +It has the same syntax and semantics as ordinary @samp{let} +except that @r{<variable>} is bound within @r{<body>} to a procedure +whose formal arguments are the bound variables and whose body is +@r{<body>}. Thus the execution of @r{<body>} may be repeated by +invoking the procedure named by @r{<variable>}. + +@c | <-- right margin + +@format +@t{(let loop ((numbers '(3 -2 1 6 -5)) + (nonneg '()) + (neg '())) + (cond ((null? numbers) (list nonneg neg)) + ((>= (car numbers) 0) + (loop (cdr numbers) + (cons (car numbers) nonneg) + neg)) + ((< (car numbers) 0) + (loop (cdr numbers) + nonneg + (cons (car numbers) neg))))) + ==> ((6 1 3) (-5 -2)) +} +@end format + + +@end deffn + + +@node Delayed evaluation, Quasiquotation, Iteration, Derived expression types +@subsection Delayed evaluation + + + +@deffn {library syntax} delay @r{<expression>} + +@ignore todo +Fix. +@end ignore + + +The @samp{delay} construct is used together with the procedure @code{force} to +@vindex @w{force} +implement @dfn{lazy evaluation} or @dfn{call by need}. +@cindex @w{call by need} +@cindex @w{lazy evaluation} +@t{(delay @r{<expression>})} returns an object called a +@dfn{promise} which at some point in the future may be asked (by +@cindex @w{promise} +the @samp{force} procedure) +@ignore todo +Bartley's white lie; OK? +@end ignore + to evaluate +@r{<expression>}, and deliver the resulting value. +The effect of @r{<expression>} returning multiple values +is unspecified. + +See the description of @samp{force} (section @pxref{Control features}) for a +more complete description of @samp{delay}. + +@end deffn + + +@node Quasiquotation, , Delayed evaluation, Derived expression types +@subsection Quasiquotation + + + + +@deffn {syntax} quasiquote @r{<qq template>} + +@deffnx {syntax} @t{`}@r{<qq template>} + + +``Backquote'' or ``quasiquote'' expressions are useful +@cindex @w{backquote} +for constructing a list or vector structure when most but not all of the +desired structure is known in advance. If no +commas appear within the @r{<qq template>}, the result of +@cindex @w{comma} +evaluating +@t{`}@r{<qq template>} is equivalent to the result of evaluating +@t{'}@r{<qq template>}. If a comma appears within the +@cindex @w{,} +@r{<qq template>}, however, the expression following the comma is +evaluated (``unquoted'') and its result is inserted into the structure +instead of the comma and the expression. If a comma appears followed +immediately by an at-sign (@@), then the following +@cindex @w{,@@} +expression must evaluate to a list; the opening and closing parentheses +of the list are then ``stripped away'' and the elements of the list are +inserted in place of the comma at-sign expression sequence. A comma +at-sign should only appear within a list or vector @r{<qq template>}. + +@c struck: "(in the sense of {\cf equal?})" after "equivalent" + + +@format +@t{`(list ,(+ 1 2) 4) ==> (list 3 4) +(let ((name 'a)) `(list ,name ',name)) + ==> (list a (quote a)) +`(a ,(+ 1 2) ,@@(map abs '(4 -5 6)) b) + ==> (a 3 4 5 6 b) +`((@samp{foo} ,(- 10 3)) ,@@(cdr '(c)) . ,(car '(cons))) + ==> ((foo 7) . cons) +`#(10 5 ,(sqrt 4) ,@@(map sqrt '(16 9)) 8) + ==> #(10 5 2 4 3 8) +} +@end format + + +Quasiquote forms may be nested. Substitutions are made only for +unquoted components appearing at the same nesting level +as the outermost backquote. The nesting level increases by one inside +each successive quasiquotation, and decreases by one inside each +unquotation. + + +@format +@t{`(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f) + ==> (a `(b ,(+ 1 2) ,(foo 4 d) e) f) +(let ((name1 'x) + (name2 'y)) + `(a `(b ,,name1 ,',name2 d) e)) + ==> (a `(b ,x ,'y d) e) +} +@end format + + +The two notations + @t{`}@r{<qq template>} and @t{(quasiquote @r{<qq template>})} + are identical in all respects. + @samp{,@r{<expression>}} is identical to @samp{(unquote @r{<expression>})}, + and + @samp{,@@@r{<expression>}} is identical to @samp{(unquote-splicing @r{<expression>})}. +The external syntax generated by @code{write} for two-element lists whose +@vindex @w{write} +car is one of these symbols may vary between implementations. + +@cindex @w{`} + + +@format +@t{(quasiquote (list (unquote (+ 1 2)) 4)) + ==> (list 3 4) +'(quasiquote (list (unquote (+ 1 2)) 4)) + ==> `(list ,(+ 1 2) 4) + @emph{}i.e., (quasiquote (list (unquote (+ 1 2)) 4)) +} +@end format + + +Unpredictable behavior can result if any of the symbols +@code{quasiquote}, @code{unquote}, or @code{unquote-splicing} appear in +@vindex @w{unquote-splicing} +@vindex @w{unquote} +@vindex @w{quasiquote} +positions within a @r{<qq template>} otherwise than as described above. + +@end deffn + +@node Macros, , Derived expression types, Expressions +@section Macros + +@menu +* Binding constructs for syntactic keywords:: +* Pattern language:: +@end menu + + + +Scheme programs can define and use new derived expression types, + called @emph{macros}. +@cindex @w{macro} +Program-defined expression types have the syntax + +@example + +(@r{<keyword>} @r{<datum>} ...) + +@end example + +where @r{<keyword>} is an identifier that uniquely determines the +expression type. This identifier is called the @emph{syntactic +keyword}, or simply @emph{keyword}, of the macro. The +@cindex @w{macro keyword} +@cindex @w{keyword} +@cindex @w{syntactic keyword} +number of the @r{<datum>}s, and their syntax, depends on the +expression type. + +Each instance of a macro is called a @emph{use} +@cindex @w{macro use} +of the macro. +The set of rules that specifies +how a use of a macro is transcribed into a more primitive expression +is called the @emph{transformer} +@cindex @w{macro transformer} +of the macro. + +The macro definition facility consists of two parts: + + + +@itemize @bullet + +@item +A set of expressions used to establish that certain identifiers +are macro keywords, associate them with macro transformers, and control +the scope within which a macro is defined, and + +@item +a pattern language for specifying macro transformers. + +@end itemize + + +The syntactic keyword of a macro may shadow variable bindings, and local +variable bindings may shadow keyword bindings. All macros +@cindex @w{keyword} +defined using the pattern language are ``hygienic'' and ``referentially +transparent'' and thus preserve Scheme's lexical scoping [Kohlbecker86], [ +hygienic], [Bawden88], [macrosthatwork], [syntacticabstraction]: + +@cindex @w{hygienic} + +@cindex @w{referentially transparent} + + + + +@itemize @bullet + + +@item +If a macro transformer inserts a binding for an identifier +(variable or keyword), the identifier will in effect be renamed +throughout its scope to avoid conflicts with other identifiers. +Note that a @code{define} at top level may or may not introduce a binding; +see section @ref{Definitions}. + +@item +If a macro transformer inserts a free reference to an +identifier, the reference refers to the binding that was visible +where the transformer was specified, regardless of any local +bindings that may surround the use of the macro. + + +@end itemize + +@vindex @w{define} + +@c The low-level facility permits non-hygienic macros to be written, +@c and may be used to implement the high-level pattern language. + +@c The fourth section describes some features that would make the +@c low-level macro facility easier to use directly. + +@node Binding constructs for syntactic keywords, Pattern language, Macros, Macros +@subsection Binding constructs for syntactic keywords + + + +@samp{Let-syntax} and @samp{letrec-syntax} are +analogous to @samp{let} and @samp{letrec}, but they bind +syntactic keywords to macro transformers instead of binding variables +to locations that contain values. Syntactic keywords may also be +bound at top level; see section @ref{Syntax definitions}. + + +@deffn {syntax} let-syntax @r{<bindings>} @r{<body>} + +@emph{Syntax:} +@r{<Bindings>} should have the form + +@format +@t{((@r{<keyword>} @r{<transformer spec>}) @dots{},) +} +@end format + +Each @r{<keyword>} is an identifier, +each @r{<transformer spec>} is an instance of @samp{syntax-rules}, and +@r{<body>} should be a sequence of one or more expressions. It is an error +for a @r{<keyword>} to appear more than once in the list of keywords +being bound. + +@emph{Semantics:} +The @r{<body>} is expanded in the syntactic environment +obtained by extending the syntactic environment of the +@samp{let-syntax} expression with macros whose keywords are +the @r{<keyword>}s, bound to the specified transformers. +Each binding of a @r{<keyword>} has @r{<body>} as its region. + + +@format +@t{(let-syntax ((when (syntax-rules () + ((when test stmt1 stmt2 ...) + (if test + (begin stmt1 + stmt2 ...)))))) + (let ((if #t)) + (when if (set! if 'now)) + if)) ==> now + +(let ((x 'outer)) + (let-syntax ((m (syntax-rules () ((m) x)))) + (let ((x 'inner)) + (m)))) ==> outer +} +@end format + + +@end deffn + + +@deffn {syntax} letrec-syntax @r{<bindings>} @r{<body>} + +@emph{Syntax:} +Same as for @samp{let-syntax}. + +@emph{Semantics:} + The @r{<body>} is expanded in the syntactic environment obtained by +extending the syntactic environment of the @samp{letrec-syntax} +expression with macros whose keywords are the +@r{<keyword>}s, bound to the specified transformers. +Each binding of a @r{<keyword>} has the @r{<bindings>} +as well as the @r{<body>} within its region, +so the transformers can +transcribe expressions into uses of the macros +introduced by the @samp{letrec-syntax} expression. + + +@format +@t{(letrec-syntax + ((my-or (syntax-rules () + ((my-or) #f) + ((my-or e) e) + ((my-or e1 e2 ...) + (let ((temp e1)) + (if temp + temp + (my-or e2 ...))))))) + (let ((x #f) + (y 7) + (temp 8) + (let odd?) + (if even?)) + (my-or x + (let temp) + (if y) + y))) ==> 7 +} +@end format + + +@end deffn + +@node Pattern language, , Binding constructs for syntactic keywords, Macros +@subsection Pattern language + + + +A @r{<transformer spec>} has the following form: + + +@deffn {} syntax-rules @r{<literals>} @r{<syntax rule>} @dots{}, + +@emph{Syntax:} +@r{<Literals>} is a list of identifiers and each @r{<syntax rule>} +should be of the form + +@format +@t{(@r{<pattern>} @r{<template>}) +} +@end format + +The @r{<pattern>} in a @r{<syntax rule>} is a list @r{<pattern>} +that begins with the keyword for the macro. + +A @r{<pattern>} is either an identifier, a constant, or one of the +following + +@format +@t{(@r{<pattern>} @dots{}) +(@r{<pattern>} @r{<pattern>} @dots{} . @r{<pattern>}) +(@r{<pattern>} @dots{} @r{<pattern>} @r{<ellipsis>}) +#(@r{<pattern>} @dots{}) +#(@r{<pattern>} @dots{} @r{<pattern>} @r{<ellipsis>}) +} +@end format + +and a template is either an identifier, a constant, or one of the following + +@format +@t{(@r{<element>} @dots{}) +(@r{<element>} @r{<element>} @dots{} . @r{<template>}) +#(@r{<element>} @dots{}) +} +@end format + +where an @r{<element>} is a @r{<template>} optionally +followed by an @r{<ellipsis>} and +an @r{<ellipsis>} is the identifier ``@samp{...}'' (which cannot be used as +an identifier in either a template or a pattern). +@vindex ... + +@emph{Semantics:} An instance of @samp{syntax-rules} produces a new macro +transformer by specifying a sequence of hygienic rewrite rules. A use +of a macro whose keyword is associated with a transformer specified by +@samp{syntax-rules} is matched against the patterns contained in the +@r{<syntax rule>}s, beginning with the leftmost @r{<syntax rule>}. +When a match is found, the macro use is transcribed hygienically +according to the template. + +An identifier that appears in the pattern of a @r{<syntax rule>} is +a @emph{pattern variable}, unless it is the keyword that begins the pattern, +is listed in @r{<literals>}, or is the identifier ``@samp{...}''. +Pattern variables match arbitrary input elements and +are used to refer to elements of the input in the template. It is an +error for the same pattern variable to appear more than once in a +@r{<pattern>}. + +The keyword at the beginning of the pattern in a +@r{<syntax rule>} is not involved in the matching and +is not considered a pattern variable or literal identifier. + + +@quotation +@emph{Rationale:} +The scope of the keyword is determined by the expression or syntax +definition that binds it to the associated macro transformer. +If the keyword were a pattern variable or literal +identifier, then +the template that follows the pattern would be within its scope +regardless of whether the keyword were bound by @samp{let-syntax} +or by @samp{letrec-syntax}. +@end quotation + + +Identifiers that appear in @r{<literals>} are interpreted as literal +identifiers to be matched against corresponding subforms of the input. +A subform +in the input matches a literal identifier if and only if it is an +identifier +and either both its occurrence in the macro expression and its +occurrence in the macro definition have the same lexical binding, or +the two identifiers are equal and both have no lexical binding. + +@c [Bill Rozas suggested the term "noise word" for these literal +@c identifiers, but in their most interesting uses, such as a setf +@c macro, they aren't noise words at all. -- Will] + +A subpattern followed by @samp{...} can match zero or more elements of the +input. It is an error for @samp{...} to appear in @r{<literals>}. +Within a pattern the identifier @samp{...} must follow the last element of +a nonempty sequence of subpatterns. + +More formally, an input form F matches a pattern P if and only if: + + + +@itemize @bullet + +@item +P is a non-literal identifier; or + +@item +P is a literal identifier and F is an identifier with the same +binding; or + +@item +P is a list @samp{(P_1 @dots{} P_n)} and F is a +list of n +forms that match P_1 through P_n, respectively; or + +@item +P is an improper list +@samp{(P_1 P_2 @dots{} P_n . P_n+1)} +and F is a list or +improper list of n or more forms that match P_1 through P_n, +respectively, and whose nth ``cdr'' matches P_n+1; or + +@item +P is of the form +@samp{(P_1 @dots{} P_n P_n+1 <ellipsis>)} +where <ellipsis> is the identifier @samp{...} +and F is +a proper list of at least n forms, the first n of which match +P_1 through P_n, respectively, and each remaining element of F +matches P_n+1; or + +@item +P is a vector of the form @samp{#(P_1 @dots{} P_n)} +and F is a vector +of n forms that match P_1 through P_n; or + +@item +P is of the form +@samp{#(P_1 @dots{} P_n P_n+1 <ellipsis>)} +where <ellipsis> is the identifier @samp{...} +and F is a vector of n +or more forms the first n of which match +P_1 through P_n, respectively, and each remaining element of F +matches P_n+1; or + +@item +P is a datum and F is equal to P in the sense of +the @samp{equal?} procedure. + +@end itemize + + +It is an error to use a macro keyword, within the scope of its +binding, in an expression that does not match any of the patterns. + +When a macro use is transcribed according to the template of the +matching @r{<syntax rule>}, pattern variables that occur in the +template are replaced by the subforms they match in the input. +Pattern variables that occur in subpatterns followed by one or more +instances of the identifier +@samp{...} are allowed only in subtemplates that are +followed by as many instances of @samp{...}. +They are replaced in the +output by all of the subforms they match in the input, distributed as +indicated. It is an error if the output cannot be built up as +specified. + +@c %% This description of output construction is very vague. It should +@c %% probably be formalized, but that is not easy... + +Identifiers that appear in the template but are not pattern variables +or the identifier +@samp{...} are inserted into the output as literal identifiers. If a +literal identifier is inserted as a free identifier then it refers to the +binding of that identifier within whose scope the instance of +@samp{syntax-rules} appears. +If a literal identifier is inserted as a bound identifier then it is +in effect renamed to prevent inadvertent captures of free identifiers. + +As an example, if @code{let} and @code{cond} are defined as in +@vindex @w{cond} +@vindex @w{let} +section @ref{Derived expression type} then they are hygienic (as required) and +the following is not an error. + + +@format +@t{(let ((=> #f)) + (cond (#t => 'ok))) ==> ok +} +@end format + + +The macro transformer for @samp{cond} recognizes @samp{=>} +as a local variable, and hence an expression, and not as the +top-level identifier @samp{=>}, which the macro transformer treats +as a syntactic keyword. Thus the example expands into + + +@format +@t{(let ((=> #f)) + (if #t (begin => 'ok))) +} +@end format + + +instead of + + +@format +@t{(let ((=> #f)) + (let ((temp #t)) + (if temp ('ok temp)))) +} +@end format + + +which would result in an invalid procedure call. + +@end deffn + + +@page + +@c @include{prog} +@node Program structure, Standard procedures, Expressions, top +@chapter Program structure + +@menu +* Programs:: +* Definitions:: +* Syntax definitions:: +@end menu + + + +@node Programs, Definitions, Program structure, Program structure +@section Programs + + +A Scheme program consists of a sequence of expressions, definitions, +and syntax definitions. +Expressions are described in chapter @ref{Expressions}; +definitions and syntax definitions are the subject of the rest of the +present chapter. + +Programs are typically stored in files or entered interactively to a +running Scheme system, although other paradigms are possible; +questions of user interface lie outside the scope of this report. +(Indeed, Scheme would still be useful as a notation for expressing +computational methods even in the absence of a mechanical +implementation.) + +Definitions and syntax definitions occurring at the top level of a program +can be interpreted +declaratively. +They cause bindings to be created in the top level +environment or modify the value of existing top-level bindings. +Expressions occurring at the top level of a program are +interpreted imperatively; they are executed in order when the program is +invoked or loaded, and typically perform some kind of initialization. + +At the top level of a program @t{(begin @r{<form1>} @dots{},)} is +equivalent to the sequence of expressions, definitions, and syntax definitions +that form the body of the @code{begin}. +@vindex @w{begin} + +@ignore todo +Cromarty, etc.: disclaimer about top level? +@end ignore + + +@node Definitions, Syntax definitions, Programs, Program structure +@section Definitions + +@menu +* Top level definitions:: +* Internal definitions:: +@end menu + + + +Definitions are valid in some, but not all, contexts where expressions +are allowed. They are valid only at the top level of a @r{<program>} +and at the beginning of a @r{<body>}. + +@cindex @w{definition} + +A definition should have one of the following forms: +@cindex @w{define} + + + +@itemize @bullet + + +@item @t{(define @r{<variable>} @r{<expression>})} + +@item @t{(define (@r{<variable>} @r{<formals>}) @r{<body>})} + +@r{<Formals>} should be either a +sequence of zero or more variables, or a sequence of one or more +variables followed by a space-delimited period and another variable (as +in a lambda expression). This form is equivalent to + +@example + +(define @r{<variable>} + (lambda (@r{<formals>}) @r{<body>}))@r{.} + +@end example + + +@item @t{(define (@r{<variable>} .@: @r{<formal>}) @r{<body>})} + +@r{<Formal>} should be a single +variable. This form is equivalent to + +@example + +(define @r{<variable>} + (lambda @r{<formal>} @r{<body>}))@r{.} + +@end example + + + +@end itemize + + +@node Top level definitions, Internal definitions, Definitions, Definitions +@subsection Top level definitions + + +At the top level of a program, a definition + +@example + +(define @r{<variable>} @r{<expression>}) + +@end example + +has essentially the same effect as the assignment expression + +@example + +(set! @r{<variable>} @r{<expression>}) + +@end example + +if @r{<variable>} is bound. If @r{<variable>} is not bound, +however, then the definition will bind @r{<variable>} to a new +location before performing the assignment, whereas it would be an error +to perform a @samp{set!} on an unbound variable. +@cindex @w{unbound} + + +@example + +(define add3 + (lambda (x) (+ x 3))) +(add3 3) ==> 6 +(define first car) +(first '(1 2)) ==> 1 + +@end example + + +Some implementations of Scheme use an initial environment in +which all possible variables are bound to locations, most of +which contain undefined values. Top level definitions in +such an implementation are truly equivalent to assignments. + +@ignore todo +Rozas: equal time for opposition semantics? +@end ignore + + + +@node Internal definitions, , Top level definitions, Definitions +@subsection Internal definitions + + + +Definitions may occur at the +beginning of a @r{<body>} (that is, the body of a @code{lambda}, +@vindex @w{lambda} +@code{let}, @code{let*}, @code{letrec}, @code{let-syntax}, or @code{letrec-syntax} +@vindex @w{letrec-syntax} +@vindex @w{let-syntax} +@vindex @w{letrec} +@vindex @w{let*} +@vindex @w{let} +expression or that of a definition of an appropriate form). +Such definitions are known as @emph{internal definitions} as opposed to the top level definitions described above. +@cindex @w{internal definition} +The variable defined by an internal definition is local to the +@r{<body>}. That is, @r{<variable>} is bound rather than assigned, +and the region of the binding is the entire @r{<body>}. For example, + + +@example + +(let ((x 5)) + (define foo (lambda (y) (bar x y))) + (define bar (lambda (a b) (+ (* a b) a))) + (foo (+ x 3))) ==> 45 + +@end example + + +A @r{<body>} containing internal definitions can always be converted +into a completely equivalent @samp{letrec} expression. For example, the +@samp{let} expression in the above example is equivalent to + + +@example + +(let ((x 5)) + (letrec ((foo (lambda (y) (bar x y))) + (bar (lambda (a b) (+ (* a b) a)))) + (foo (+ x 3)))) + +@end example + + +Just as for the equivalent @samp{letrec} expression, it must be +possible to evaluate each @r{<expression>} of every internal +definition in a @r{<body>} without assigning or referring to +the value of any @r{<variable>} being defined. + +Wherever an internal definition may occur +@t{(begin @r{<definition1>} @dots{},)} +is equivalent to the sequence of definitions +that form the body of the @code{begin}. +@vindex @w{begin} + +@node Syntax definitions, , Definitions, Program structure +@section Syntax definitions + + +Syntax definitions are valid only at the top level of a @r{<program>}. + +@cindex @w{syntax definition} +They have the following form: +@cindex @w{define-syntax} + +@t{(define-syntax @r{<keyword>} @r{<transformer spec>})} + +@r{<Keyword>} is an identifier, and +the @r{<transformer spec>} should be an instance of @code{syntax-rules}. +@vindex @w{syntax-rules} +The top-level syntactic environment is extended by binding the +@r{<keyword>} to the specified transformer. + +There is no @samp{define-syntax} analogue of internal definitions. + +@c [Rationale flushed because it may or may not be true and isn't the +@c real rationale anyway. -RK] +@c \begin{rationale} +@c As discussed below, the syntax and scope rules for syntax definitions +@c can give rise to syntactic ambiguities when syntactic keywords are +@c shadowed. +@c Further ambiguities would arise if {\cf define-syntax} +@c were permitted at the beginning of a \meta{body}, with scope +@c rules analogous to those for internal definitions. +@c \end{rationale} + +@c It is an error for a program to contain more than one top-level +@c \meta{definition} or \meta{syntax definition} of any identifier. + +@c [I flushed this because it isn't an error for a program to +@c contain more than one top-level definition of an identifier, +@c and I didn't want to introduce any gratuitous incompatibilities +@c with the existing Scheme language. -- Will] + +Although macros may expand into definitions and syntax definitions in +any context that permits them, it is an error for a definition or syntax +definition to shadow a syntactic keyword whose meaning is needed to +determine whether some form in the group of forms that contains the +shadowing definition is in fact a definition, or, for internal definitions, +is needed to determine the boundary between the group and the expressions +that follow the group. For example, the following are errors: + + +@example + +(define define 3) + +(begin (define begin list)) + +(let-syntax + ((foo (syntax-rules () + ((foo (proc args ...) body ...) + (define proc + (lambda (args ...) + body ...)))))) + (let ((x 3)) + (foo (plus x y) (+ x y)) + (define foo x) + (plus foo x))) + +@end example + + + + +@c @include{procs} + +@c Initial environment + +@c \vfill\eject +@node Standard procedures, Formal syntax and semantics, Program structure, top +@chapter Standard procedures + +@menu +* Equivalence predicates:: +* Numbers:: +* Other data types:: +* Control features:: +* Eval:: +* Input and output:: +@end menu + + + + + +@cindex @w{initial environment} + +@cindex @w{top level environment} + +@cindex @w{library procedure} + +This chapter describes Scheme's built-in procedures. The initial (or +``top level'') Scheme environment starts out with a number of variables +bound to locations containing useful values, most of which are primitive +procedures that manipulate data. For example, the variable @samp{abs} is +bound to (a location initially containing) a procedure of one argument +that computes the absolute value of a number, and the variable @samp{+} +is bound to a procedure that computes sums. Built-in procedures that +can easily be written in terms of other built-in procedures are identified as +``library procedures''. + +A program may use a top-level definition to bind any variable. It may +subsequently alter any such binding by an assignment (see @pxref{Assignments}). +These operations do not modify the behavior of Scheme's built-in +procedures. Altering any top-level binding that has not been introduced by a +definition has an unspecified effect on the behavior of the built-in procedures. + +@node Equivalence predicates, Numbers, Standard procedures, Standard procedures +@section Equivalence predicates + + + +A @dfn{predicate} is a procedure that always returns a boolean +@cindex @w{predicate} +value (@t{#t} or @t{#f}). An @dfn{equivalence predicate} is +@cindex @w{equivalence predicate} +the computational analogue of a mathematical equivalence relation (it is +symmetric, reflexive, and transitive). Of the equivalence predicates +described in this section, @samp{eq?} is the finest or most +discriminating, and @samp{equal?} is the coarsest. @samp{Eqv?} is +slightly less discriminating than @samp{eq?}. +@ignore todo +Pitman doesn't like +this paragraph. Lift the discussion from the Maclisp manual. Explain +why there's more than one predicate. +@end ignore + + + + +@deffn {procedure} eqv? obj1 obj2 + +The @samp{eqv?} procedure defines a useful equivalence relation on objects. +Briefly, it returns @t{#t} if @var{obj1} and @var{obj2} should +normally be regarded as the same object. This relation is left slightly +open to interpretation, but the following partial specification of +@samp{eqv?} holds for all implementations of Scheme. + +The @samp{eqv?} procedure returns @t{#t} if: + + + +@itemize @bullet + +@item +@var{obj1} and @var{obj2} are both @t{#t} or both @t{#f}. + +@item +@var{obj1} and @var{obj2} are both symbols and + + +@format +@t{(string=? (symbol->string obj1) + (symbol->string obj2)) + ==> #t +} +@end format + + + +@quotation +@emph{Note:} +This assumes that neither @var{obj1} nor @var{obj2} is an ``uninterned +symbol'' as alluded to in section @ref{Symbols}. This report does +not presume to specify the behavior of @samp{eqv?} on implementation-dependent +extensions. +@end quotation + + +@item +@var{obj1} and @var{obj2} are both numbers, are numerically +equal (see @samp{=}, section @pxref{Numbers}), and are either both +exact or both inexact. + +@item +@var{obj1} and @var{obj2} are both characters and are the same +character according to the @samp{char=?} procedure +(section @pxref{Characters}). + +@item +both @var{obj1} and @var{obj2} are the empty list. + +@item +@var{obj1} and @var{obj2} are pairs, vectors, or strings that denote the +same locations in the store (section @pxref{Storage model}). + +@item +@var{obj1} and @var{obj2} are procedures whose location tags are +equal (section @pxref{Procedures}). + +@end itemize + +@cindex @w{inexact} +@cindex @w{exact} + +The @samp{eqv?} procedure returns @t{#f} if: + + + +@itemize @bullet + +@item +@var{obj1} and @var{obj2} are of different types +(section @pxref{Disjointness of types}). + +@item +one of @var{obj1} and @var{obj2} is @t{#t} but the other is +@t{#f}. + +@item +@var{obj1} and @var{obj2} are symbols but + + +@format +@t{(string=? (symbol->string @var{obj1}) + (symbol->string @var{obj2})) + ==> #f +} +@end format + + +@item +one of @var{obj1} and @var{obj2} is an exact number but the other +is an inexact number. + +@item +@var{obj1} and @var{obj2} are numbers for which the @samp{=} +procedure returns @t{#f}. + +@item +@var{obj1} and @var{obj2} are characters for which the @samp{char=?} +procedure returns @t{#f}. + +@item +one of @var{obj1} and @var{obj2} is the empty list but the other +is not. + +@item +@var{obj1} and @var{obj2} are pairs, vectors, or strings that denote +distinct locations. + +@item +@var{obj1} and @var{obj2} are procedures that would behave differently +(return different value(s) or have different side effects) for some arguments. + + +@end itemize + + + +@format +@t{(eqv? 'a 'a) ==> #t +(eqv? 'a 'b) ==> #f +(eqv? 2 2) ==> #t +(eqv? '() '()) ==> #t +(eqv? 100000000 100000000) ==> #t +(eqv? (cons 1 2) (cons 1 2)) ==> #f +(eqv? (lambda () 1) + (lambda () 2)) ==> #f +(eqv? #f 'nil) ==> #f +(let ((p (lambda (x) x))) + (eqv? p p)) ==> #t +} +@end format + + +The following examples illustrate cases in which the above rules do +not fully specify the behavior of @samp{eqv?}. All that can be said +about such cases is that the value returned by @samp{eqv?} must be a +boolean. + + +@format +@t{(eqv? "" "") ==> @emph{unspecified} +(eqv? '#() '#()) ==> @emph{unspecified} +(eqv? (lambda (x) x) + (lambda (x) x)) ==> @emph{unspecified} +(eqv? (lambda (x) x) + (lambda (y) y)) ==> @emph{unspecified} +} +@end format + + +The next set of examples shows the use of @samp{eqv?} with procedures +that have local state. @samp{Gen-counter} must return a distinct +procedure every time, since each procedure has its own internal counter. +@samp{Gen-loser}, however, returns equivalent procedures each time, since +the local state does not affect the value or side effects of the +procedures. + + +@format +@t{(define gen-counter + (lambda () + (let ((n 0)) + (lambda () (set! n (+ n 1)) n)))) +(let ((g (gen-counter))) + (eqv? g g)) ==> #t +(eqv? (gen-counter) (gen-counter)) + ==> #f +(define gen-loser + (lambda () + (let ((n 0)) + (lambda () (set! n (+ n 1)) 27)))) +(let ((g (gen-loser))) + (eqv? g g)) ==> #t +(eqv? (gen-loser) (gen-loser)) + ==> @emph{unspecified} + +(letrec ((f (lambda () (if (eqv? f g) 'both 'f))) + (g (lambda () (if (eqv? f g) 'both 'g)))) + (eqv? f g)) + ==> @emph{unspecified} + +(letrec ((f (lambda () (if (eqv? f g) 'f 'both))) + (g (lambda () (if (eqv? f g) 'g 'both)))) + (eqv? f g)) + ==> #f +} +@end format + + +@c Objects of distinct types must never be regarded as the same object, +@c except that \schfalse{} and the empty list\index{empty list} are permitted to +@c be identical. + +@c \begin{scheme} +@c (eqv? '() \schfalse) \ev \unspecified% +@c \end{scheme} + +Since it is an error to modify constant objects (those returned by +literal expressions), implementations are permitted, though not +required, to share structure between constants where appropriate. Thus +the value of @samp{eqv?} on constants is sometimes +implementation-dependent. + + +@format +@t{(eqv? '(a) '(a)) ==> @emph{unspecified} +(eqv? "a" "a") ==> @emph{unspecified} +(eqv? '(b) (cdr '(a b))) ==> @emph{unspecified} +(let ((x '(a))) + (eqv? x x)) ==> #t +} +@end format + + + +@quotation +@emph{Rationale:} +The above definition of @samp{eqv?} allows implementations latitude in +their treatment of procedures and literals: implementations are free +either to detect or to fail to detect that two procedures or two literals +are equivalent to each other, and can decide whether or not to +merge representations of equivalent objects by using the same pointer or +bit pattern to represent both. +@end quotation + + +@end deffn + + + +@deffn {procedure} eq? obj1 obj2 + +@samp{Eq?} is similar to @samp{eqv?} except that in some cases it is +capable of discerning distinctions finer than those detectable by +@samp{eqv?}. + +@samp{Eq?} and @samp{eqv?} are guaranteed to have the same +behavior on symbols, booleans, the empty list, pairs, procedures, +and non-empty +strings and vectors. @samp{Eq?}'s behavior on numbers and characters is +implementation-dependent, but it will always return either true or +false, and will return true only when @samp{eqv?} would also return +true. @samp{Eq?} may also behave differently from @samp{eqv?} on empty +vectors and empty strings. + + +@format +@t{(eq? 'a 'a) ==> #t +(eq? '(a) '(a)) ==> @emph{unspecified} +(eq? (list 'a) (list 'a)) ==> #f +(eq? "a" "a") ==> @emph{unspecified} +(eq? "" "") ==> @emph{unspecified} +(eq? '() '()) ==> #t +(eq? 2 2) ==> @emph{unspecified} +(eq? #\A #\A) ==> @emph{unspecified} +(eq? car car) ==> #t +(let ((n (+ 2 3))) + (eq? n n)) ==> @emph{unspecified} +(let ((x '(a))) + (eq? x x)) ==> #t +(let ((x '#())) + (eq? x x)) ==> #t +(let ((p (lambda (x) x))) + (eq? p p)) ==> #t +} +@end format + + +@ignore todo +Needs to be explained better above. How can this be made to be +not confusing? A table maybe? +@end ignore + + + +@quotation +@emph{Rationale:} It will usually be possible to implement @samp{eq?} much +more efficiently than @samp{eqv?}, for example, as a simple pointer +comparison instead of as some more complicated operation. One reason is +that it may not be possible to compute @samp{eqv?} of two numbers in +constant time, whereas @samp{eq?} implemented as pointer comparison will +always finish in constant time. @samp{Eq?} may be used like @samp{eqv?} +in applications using procedures to implement objects with state since +it obeys the same constraints as @samp{eqv?}. +@end quotation + + +@end deffn + + + +@deffn {library procedure} equal? obj1 obj2 + +@samp{Equal?} recursively compares the contents of pairs, vectors, and +strings, applying @samp{eqv?} on other objects such as numbers and symbols. +A rule of thumb is that objects are generally @samp{equal?} if they print +the same. @samp{Equal?} may fail to terminate if its arguments are +circular data structures. + + +@format +@t{(equal? 'a 'a) ==> #t +(equal? '(a) '(a)) ==> #t +(equal? '(a (b) c) + '(a (b) c)) ==> #t +(equal? "abc" "abc") ==> #t +(equal? 2 2) ==> #t +(equal? (make-vector 5 'a) + (make-vector 5 'a)) ==> #t +(equal? (lambda (x) x) + (lambda (y) y)) ==> @emph{unspecified} +} +@end format + + +@end deffn + + +@node Numbers, Other data types, Equivalence predicates, Standard procedures +@section Numbers + +@menu +* Numerical types:: +* Exactness:: +* Implementation restrictions:: +* Syntax of numerical constants:: +* Numerical operations:: +* Numerical input and output:: +@end menu + + + +@cindex @w{number} + +@c %R4%% The excessive use of the code font in this section was +@c confusing, somewhat obnoxious, and inconsistent with the rest +@c of the report and with parts of the section itself. I added +@c a \tupe no-op, and changed most old uses of \type to \tupe, +@c to make it easier to change the fonts back if people object +@c to the change. + +@c \newcommand{\type}[1]{{\it#1}} +@c \newcommand{\tupe}[1]{{#1}} + +Numerical computation has traditionally been neglected by the Lisp +community. Until Common Lisp there was no carefully thought out +strategy for organizing numerical computation, and with the exception of +the MacLisp system [Pitman83] little effort was made to +execute numerical code efficiently. This report recognizes the excellent work +of the Common Lisp committee and accepts many of their recommendations. +In some ways this report simplifies and generalizes their proposals in a manner +consistent with the purposes of Scheme. + +It is important to distinguish between the mathematical numbers, the +Scheme numbers that attempt to model them, the machine representations +used to implement the Scheme numbers, and notations used to write numbers. +This report uses the types @i{number}, @i{complex}, @i{real}, +@i{rational}, and @i{integer} to refer to both mathematical numbers +and Scheme numbers. Machine representations such as fixed point and +floating point are referred to by names such as @i{fixnum} and +@i{flonum}. + +@c %R4%% I did some reorganizing here to move the discussion of mathematical +@c numbers before the discussion of the Scheme numbers, hoping that this +@c would help to motivate the discussion of representation independence. + +@node Numerical types, Exactness, Numbers, Numbers +@subsection Numerical types + + + +@cindex @w{numerical types} + +@c %R4%% A Scheme system provides data of type \type{number}, which is the most +@c general numerical type supported by that system. +@c \type{Number} is +@c likely to be a complicated union type implemented in terms of +@c \type{fixnum}s, \type{bignum}s, \type{flonum}s, and so forth, but this +@c should not be apparent to a naive user. What the user should see is +@c that the usual operations on numbers produce the mathematically +@c expected results, within the limits of the implementation. + +@c %R4%% I rewrote the following paragraph to make the various levels of +@c the tower into subsets of each other, instead of relating them by +@c injections. I think the injections tended to put people in the frame +@c of mind of thinking about coercions between non-overlapping numeric +@c types in mainstream programming languages. + +Mathematically, numbers may be arranged into a tower of subtypes +@c %R4%% with injections relating adjacent levels of the tower: +in which each level is a subset of the level above it: + +@format + @r{number} + @r{complex} + @r{real} + @r{rational} + @r{integer} +@end format + + +For example, 3 is an integer. Therefore 3 is also a rational, +a real, and a complex. The same is true of the Scheme numbers +that model 3. For Scheme numbers, these types are defined by the +predicates @code{number?}, @code{complex?}, @code{real?}, @code{rational?}, +@vindex @w{rational?} +@vindex @w{real?} +@vindex @w{complex?} +@vindex @w{number?} +and @code{integer?}. +@vindex @w{integer?} + +There is no simple relationship between a number's type and its +representation inside a computer. Although most implementations of +Scheme will offer at least two different representations of 3, these +different representations denote the same integer. + +@c %R4%% I moved "Implementations of Scheme are not required to implement +@c the whole tower..." to the subsection on implementation restrictions. + +Scheme's numerical operations treat numbers as abstract data, as +independent of their representation as possible. Although an implementation +of Scheme may use fixnum, flonum, and perhaps other representations for +numbers, this should not be apparent to a casual programmer writing +simple programs. + +It is necessary, however, to distinguish between numbers that are +represented exactly and those that may not be. For example, indexes +into data structures must be known exactly, as must some polynomial +coefficients in a symbolic algebra system. On the other hand, the +results of measurements are inherently inexact, and irrational numbers +may be approximated by rational and therefore inexact approximations. +In order to catch uses of inexact numbers where exact numbers are +required, Scheme explicitly distinguishes exact from inexact numbers. +This distinction is orthogonal to the dimension of type. + +@node Exactness, Implementation restrictions, Numerical types, Numbers +@subsection Exactness + + +@c %R4%% I tried to direct the following paragraph away from philosophizing +@c about the exactness of mathematical numbers, and toward philosophizing +@c about the exactness of Scheme numbers. + + +@cindex @w{exactness} +Scheme numbers are either @i{exact} or @i{inexact}. A number is +@r{exact} if it was written as an exact constant or was derived from +@r{exact} numbers using only @r{exact} operations. A number is +@r{inexact} if it was written as an inexact constant, +@c %R4%% models a quantity (e.g., a measurement) known only approximately, +if it was +derived using @r{inexact} ingredients, or if it was derived using +@r{inexact} operations. Thus @r{inexact}ness is a contagious +property of a number. +@c %R4%% The rest of this paragraph (from R3RS) has been dropped. + +If two implementations produce @r{exact} results for a +computation that did not involve @r{inexact} intermediate results, +the two ultimate results will be mathematically equivalent. This is +generally not true of computations involving @r{inexact} numbers +since approximate methods such as floating point arithmetic may be used, +but it is the duty of each implementation to make the result as close as +practical to the mathematically ideal result. + +Rational operations such as @samp{+} should always produce +@r{exact} results when given @r{exact} arguments. +@c %R4%%If an implementation is +@c unable to represent an \tupe{exact} result (for example, if it does not +@c support infinite precision integers and rationals) +If the operation is unable to produce an @r{exact} result, +then it may either report the violation of an implementation restriction +or it may silently coerce its +result to an @r{inexact} value. +@c %R4%%Such a coercion may cause an error later. +See section @ref{Implementation restrictions}. + +With the exception of @code{inexact->exact}, the operations described in +@vindex @w{inexact->exact} +this section must generally return inexact results when given any inexact +arguments. An operation may, however, return an @r{exact} result if it can +prove that the value of the result is unaffected by the inexactness of its +arguments. For example, multiplication of any number by an @r{exact} zero +may produce an @r{exact} zero result, even if the other argument is +@r{inexact}. + +@node Implementation restrictions, Syntax of numerical constants, Exactness, Numbers +@subsection Implementation restrictions + + + +@cindex @w{implementation restriction} + +Implementations of Scheme are not required to implement the whole +tower of subtypes given in section @ref{Numerical types}, +but they must implement a coherent subset consistent with both the +purposes of the implementation and the spirit of the Scheme language. +For example, an implementation in which all numbers are @r{real} +may still be quite useful. + +Implementations may also support only a limited range of numbers of +any type, subject to the requirements of this section. The supported +range for @r{exact} numbers of any type may be different from the +supported range for @r{inexact} numbers of that type. For example, +an implementation that uses flonums to represent all its +@r{inexact} @r{real} numbers may +support a practically unbounded range of @r{exact} @r{integer}s +and @r{rational}s +while limiting the range of @r{inexact} @r{real}s (and therefore +the range of @r{inexact} @r{integer}s and @r{rational}s) +to the dynamic range of the flonum format. +Furthermore +the gaps between the representable @r{inexact} @r{integer}s and +@r{rational}s are +likely to be very large in such an implementation as the limits of this +range are approached. + +An implementation of Scheme must support exact integers +throughout the range of numbers that may be used for indexes of +lists, vectors, and strings or that may result from computing the length of a +list, vector, or string. The @code{length}, @code{vector-length}, +@vindex @w{vector-length} +@vindex @w{length} +and @code{string-length} procedures must return an exact +@vindex @w{string-length} +integer, and it is an error to use anything but an exact integer as an +index. Furthermore any integer constant within the index range, if +expressed by an exact integer syntax, will indeed be read as an exact +integer, regardless of any implementation restrictions that may apply +outside this range. Finally, the procedures listed below will always +return an exact integer result provided all their arguments are exact integers +and the mathematically expected result is representable as an exact integer +within the implementation: + + +@example + ++ - * +quotient remainder modulo +max min abs +numerator denominator gcd +lcm floor ceiling +truncate round rationalize +expt + +@end example + + +Implementations are encouraged, but not required, to support +@r{exact} @r{integer}s and @r{exact} @r{rational}s of +practically unlimited size and precision, and to implement the +above procedures and the @samp{/} procedure in +such a way that they always return @r{exact} results when given @r{exact} +arguments. If one of these procedures is unable to deliver an @r{exact} +result when given @r{exact} arguments, then it may either report a +violation of an +implementation restriction or it may silently coerce its result to an +@r{inexact} number. Such a coercion may cause an error later. + +@c %R4%% I moved this stuff here. +@c It seems to me that the only thing that this requires is that +@c implementations that support inexact numbers have to have both +@c exact and inexact representations for the integers 0 through 15. +@c If that's what it's saying, I'd rather say it that way. +@c On the other hand, letting the limit be as small as 15 sounds a +@c tad silly, though I think I understand how that number was arrived at. +@c (Or is 35 the number?) + +@c Implementations are encouraged, but not required, to support \tupe{inexact} +@c numbers. For any implementation that supports \tupe{inexact} numbers, +@c there is a subset of the integers for which there are both \tupe{exact} and +@c \tupe{inexact} representations. This subset must include all non-negative +@c integers up to some limit specified by the implementation. This limit +@c must be 16 or greater. The +@c \ide{exact\coerce{}inexact} and \ide{inexact\coerce{}exact} +@c procedures implement the natural one-to-one correspondence between +@c the \tupe{inexact} and \tupe{exact} integers within this range. + +An implementation may use floating point and other approximate +representation strategies for @r{inexact} numbers. +@c %R4%% The following sentence seemed a bit condescending as well as +@c awkward. It didn't seem to be very enforceable, so I flushed it. + +@c This is not to +@c say that implementors need not use the best known algorithms for +@c \tupe{inexact} computations---only that approximate methods of high +@c quality are allowed. + +This report recommends, but does not require, that the IEEE 32-bit +and 64-bit floating point standards be followed by implementations that use +flonum representations, and that implementations using +other representations should match or exceed the precision achievable +using these floating point standards [IEEE]. + +In particular, implementations that use flonum representations +must follow these rules: A @r{flonum} result +must be represented with at least as much precision as is used to express any of +the inexact arguments to that operation. It is desirable (but not required) for +potentially inexact operations such as @samp{sqrt}, when applied to @r{exact} +arguments, to produce @r{exact} answers whenever possible (for example the +square root of an @r{exact} 4 ought to be an @r{exact} 2). +If, however, an +@r{exact} number is operated upon so as to produce an @r{inexact} result +(as by @samp{sqrt}), and if the result is represented as a @r{flonum}, then +the most precise @r{flonum} format available must be used; but if the result +is represented in some other way then the representation must have at least as +much precision as the most precise @r{flonum} format available. + +Although Scheme allows a variety of written +@c %R4%% representations of +notations for +numbers, any particular implementation may support only some of them. +@c %R4%% +For example, an implementation in which all numbers are @r{real} +need not support the rectangular and polar notations for complex +numbers. If an implementation encounters an @r{exact} numerical constant that +it cannot represent as an @r{exact} number, then it may either report a +violation of an implementation restriction or it may silently represent the +constant by an @r{inexact} number. + + +@node Syntax of numerical constants, Numerical operations, Implementation restrictions, Numbers +@subsection Syntax of numerical constants + + + +@c @@@@LOSE@@@@ + +@c %R4%% I removed the following paragraph in an attempt to tighten up +@c this subsection. Except for its first sentence, which I moved to +@c the subsection on implementation restrictions, I think its content +@c is implied by the rest of the section. + +@c Although Scheme allows a variety of written representations of numbers, +@c any particular implementation may support only some of them. +@c These syntaxes are intended to be purely notational; any kind of number +@c may be written in any form that the user deems convenient. Of course, +@c writing 1/7 as a limited-precision decimal fraction will not express the +@c number exactly, but this approximate form of expression may be just what +@c the user wants to see. + +The syntax of the written representations for numbers is described formally in +section @ref{Lexical structure}. Note that case is not significant in numerical +constants. + +@c %R4%% See section~\ref{numberformats} for many examples. + +A number may be written in binary, octal, decimal, or +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 +@vindex #x +@vindex #d +@vindex #o +@vindex #b +no radix prefix, a number is assumed to be expressed in decimal. + +A +@c %R4%% +@c simple +numerical constant may be specified to be either @r{exact} or +@r{inexact} by a prefix. The prefixes are @samp{#e} +@vindex #e +for @r{exact}, and @samp{#i} for @r{inexact}. An exactness +@vindex #i +prefix may appear before or after any radix prefix that is used. If +the written representation of a number has no exactness prefix, the +constant may be either @r{inexact} or @r{exact}. It is +@r{inexact} if it contains a decimal point, an +exponent, or a ``#'' character in the place of a digit, +otherwise it is @r{exact}. +@c %R4%% With our new syntax, the following sentence is redundant: + +@c The written representation of a +@c compound number, such as a ratio or a complex, is exact if and only if +@c all of its constituents are exact. + +In systems with @r{inexact} numbers +of varying precisions it may be useful to specify +the precision of a constant. For this purpose, numerical constants +may be written with an exponent marker that indicates the +desired precision of the @r{inexact} +representation. The letters @samp{s}, @samp{f}, +@samp{d}, and @samp{l} specify the use of @var{short}, @var{single}, +@var{double}, and @var{long} precision, respectively. (When fewer +than four internal +@c %R4%%\tupe{flonum} +@r{inexact} +representations exist, the four size +specifications are mapped onto those available. For example, an +implementation with two internal representations may map short and +single together and long and double together.) In addition, the +exponent marker @samp{e} specifies the default precision for the +implementation. The default precision has at least as much precision +as @var{double}, but +implementations may wish to allow this default to be set by the user. + + +@example + +3.14159265358979F0 + @r{Round to single ---} 3.141593 +0.6L0 + @r{Extend to long ---} .600000000000000 + +@end example + + + +@node Numerical operations, Numerical input and output, Syntax of numerical constants, Numbers +@subsection Numerical operations + + +The reader is referred to section @ref{Entry format} for a summary +of the naming conventions used to specify restrictions on the types of +arguments to numerical routines. +@c %R4%% The following sentence has already been said twice, and the +@c term "exactness-preserving" is no longer defined by the Report. + +@c Remember that +@c an exactness-preserving operation may coerce its result to inexact if the +@c implementation is unable to represent it exactly. +The examples used in this section assume that any numerical constant written +using an @r{exact} notation is indeed represented as an @r{exact} +number. Some examples also assume that certain numerical constants written +using an @r{inexact} notation can be represented without loss of +accuracy; the @r{inexact} constants were chosen so that this is +likely to be true in implementations that use flonums to represent +inexact numbers. + +@ignore todo +Scheme provides the usual set of operations for manipulating +numbers, etc. +@end ignore + + + +@deffn {procedure} number? obj +@deffnx {procedure} complex? obj +@deffnx {procedure} real? obj +@deffnx {procedure} rational? obj +@deffnx {procedure} integer? obj + +These numerical type predicates can be applied to any kind of +argument, including non-numbers. They return @t{#t} if the object is +of the named type, and otherwise they return @t{#f}. +In general, if a type predicate is true of a number then all higher +type predicates are also true of that number. Consequently, if a type +predicate is false of a number, then all lower type predicates are +also false of that number. +@c %R4%% The new section on implementation restrictions subsumes: +@c Not every system +@c supports all of these types; for example, it is entirely possible to have a +@c Scheme system that has only \tupe{integer}s. Nonetheless every implementation +@c of Scheme must have all of these predicates. + +If @var{z} is an inexact complex number, then @samp{(real? @var{z})} is true if +and only if @samp{(zero? (imag-part @var{z}))} is true. If @var{x} is an inexact +real number, then @samp{(integer? @var{x})} is true if and only if +@samp{(= @var{x} (round @var{x}))}. + + +@format +@t{(complex? 3+4i) ==> #t +(complex? 3) ==> #t +(real? 3) ==> #t +(real? -2.5+0.0i) ==> #t +(real? #e1e10) ==> #t +(rational? 6/10) ==> #t +(rational? 6/3) ==> #t +(integer? 3+0i) ==> #t +(integer? 3.0) ==> #t +(integer? 8/4) ==> #t +} +@end format + + + +@quotation +@emph{Note:} +The behavior of these type predicates on @r{inexact} numbers +is unreliable, since any inaccuracy may affect the result. +@end quotation + + + +@quotation +@emph{Note:} +In many implementations the @code{rational?} procedure will be the same +@vindex @w{rational?} +as @code{real?}, and the @code{complex?} procedure will be the same as +@vindex @w{complex?} +@vindex @w{real?} +@code{number?}, but unusual implementations may be able to represent +@vindex @w{number?} +some irrational numbers exactly or may extend the number system to +support some kind of non-complex numbers. +@end quotation + + +@end deffn + + +@deffn {procedure} exact? @var{z} +@deffnx {procedure} inexact? @var{z} + +These numerical predicates provide tests for the exactness of a +quantity. For any Scheme number, precisely one of these predicates +is true. + +@end deffn + + + +@deffn {procedure} = z1 z2 z3 @dots{}, +@deffnx {procedure} < x1 x2 x3 @dots{}, +@deffnx {procedure} > x1 x2 x3 @dots{}, +@deffnx {procedure} <= x1 x2 x3 @dots{}, +@deffnx {procedure} >= x1 x2 x3 @dots{}, + +@c - Some implementations allow these procedures to take many arguments, to +@c - facilitate range checks. +These procedures return @t{#t} if their arguments are (respectively): +equal, monotonically increasing, monotonically decreasing, +monotonically nondecreasing, or monotonically nonincreasing. + +These predicates are required to be transitive. + + +@quotation +@emph{Note:} +The traditional implementations of these predicates in Lisp-like +languages are not transitive. +@end quotation + + + +@quotation +@emph{Note:} +While it is not an error to compare @r{inexact} numbers using these +predicates, the results may be unreliable because a small inaccuracy +may affect the result; this is especially true of @code{=} and @code{zero?}. +@vindex @w{zero?} +@vindex @w{=} +When in doubt, consult a numerical analyst. +@end quotation + + +@end deffn + + +@deffn {library procedure} zero? @var{z} +@deffnx {library procedure} positive? @var{x} +@deffnx {library procedure} negative? @var{x} +@deffnx {library procedure} odd? @var{n} +@deffnx {library procedure} even? @var{n} + +These numerical predicates test a number for a particular property, +returning @t{#t} or @t{#f}. See note above. + +@end deffn + + +@deffn {library procedure} max x1 x2 @dots{}, +@deffnx {library procedure} min x1 x2 @dots{}, + +These procedures return the maximum or minimum of their arguments. + + +@format +@t{(max 3 4) ==> 4 ; exact +(max 3.9 4) ==> 4.0 ; inexact +} +@end format + + + +@quotation +@emph{Note:} +If any argument is inexact, then the result will also be inexact (unless +the procedure can prove that the inaccuracy is not large enough to affect the +result, which is possible only in unusual implementations). If @samp{min} or +@samp{max} is used to compare numbers of mixed exactness, and the numerical +value of the result cannot be represented as an inexact number without loss of +accuracy, then the procedure may report a violation of an implementation +restriction. +@end quotation + + +@end deffn + + + +@deffn {procedure} + z1 @dots{}, +@deffnx {procedure} * z1 @dots{}, + +These procedures return the sum or product of their arguments. +@c - These procedures are exactness preserving. + + +@format +@t{(+ 3 4) ==> 7 +(+ 3) ==> 3 +(+) ==> 0 +(* 4) ==> 4 +(*) ==> 1 +} +@end format + + +@end deffn + + + +@deffn {procedure} - z1 z2 +@deffnx {procedure} - @var{z} +@deffnx {optional procedure} - z1 z2 @dots{}, +@deffnx {procedure} / z1 z2 +@deffnx {procedure} / @var{z} +@deffnx {optional procedure} / z1 z2 @dots{}, + +With two or more arguments, these procedures return the difference or +quotient of their arguments, associating to the left. With one argument, +however, they return the additive or multiplicative inverse of their argument. +@c - These procedures are exactness preserving, except that division may +@c - coerce its result to inexact in implementations that do not support +@c - \tupe{ratnum}s. + + +@format +@t{(- 3 4) ==> -1 +(- 3 4 5) ==> -6 +(- 3) ==> -3 +(/ 3 4 5) ==> 3/20 +(/ 3) ==> 1/3 +} +@end format + + +@end deffn + + + +@deffn {library procedure} abs x + +@samp{Abs} returns the absolute value of its argument. +@c - {\cf Abs} is exactness preserving when its argument is real. + +@format +@t{(abs -7) ==> 7 +} +@end format + +@end deffn + + + +@deffn {procedure} quotient n1 n2 +@deffnx {procedure} remainder n1 n2 +@deffnx {procedure} modulo n1 n2 + +These procedures implement number-theoretic (integer) +division. @var{n2} should be non-zero. All three procedures +return integers. If @var{n1}/@var{n2} is an integer: + +@format +@t{ (quotient @var{n1} @var{n2}) ==> @var{n1}/@var{n2} + (remainder @var{n1} @var{n2}) ==> 0 + (modulo @var{n1} @var{n2}) ==> 0 +} +@end format + +If @var{n1}/@var{n2} is not an integer: + +@format +@t{ (quotient @var{n1} @var{n2}) ==> @var{n_q} + (remainder @var{n1} @var{n2}) ==> @var{n_r} + (modulo @var{n1} @var{n2}) ==> @var{n_m} +} +@end format + +where @var{n_q} is @var{n1}/@var{n2} rounded towards zero, +0 < |@var{n_r}| < |@var{n2}|, 0 < |@var{n_m}| < |@var{n2}|, +@var{n_r} and @var{n_m} differ from @var{n1} by a multiple of @var{n2}, +@var{n_r} has the same sign as @var{n1}, and +@var{n_m} has the same sign as @var{n2}. + +From this we can conclude that for integers @var{n1} and @var{n2} with +@var{n2} not equal to 0, + +@format +@t{ (= @var{n1} (+ (* @var{n2} (quotient @var{n1} @var{n2})) + (remainder @var{n1} @var{n2}))) + ==> #t +} +@end format + +provided all numbers involved in that computation are exact. + + +@format +@t{(modulo 13 4) ==> 1 +(remainder 13 4) ==> 1 + +(modulo -13 4) ==> 3 +(remainder -13 4) ==> -1 + +(modulo 13 -4) ==> -3 +(remainder 13 -4) ==> 1 + +(modulo -13 -4) ==> -1 +(remainder -13 -4) ==> -1 + +(remainder -13 -4.0) ==> -1.0 ; inexact +} +@end format + +@end deffn + + +@deffn {library procedure} gcd n1 @dots{}, +@deffnx {library procedure} lcm n1 @dots{}, + +These procedures return the greatest common divisor or least common +multiple of their arguments. The result is always non-negative. +@c - These procedures are exactness preserving. + +@c %R4%% I added the inexact example. + +@format +@t{(gcd 32 -36) ==> 4 +(gcd) ==> 0 +(lcm 32 -36) ==> 288 +(lcm 32.0 -36) ==> 288.0 ; inexact +(lcm) ==> 1 +} +@end format + + +@end deffn + + + +@deffn {procedure} numerator @var{q} +@deffnx {procedure} denominator @var{q} + +These procedures return the numerator or denominator of their +argument; the result is computed as if the argument was represented as +a fraction in lowest terms. The denominator is always positive. The +denominator of 0 is defined to be 1. +@c - The remarks about denominators are new. +@c - Clearly, they are exactness-preserving procedures. + +@ignore todo +More description and examples needed. +@end ignore + + +@format +@t{(numerator (/ 6 4)) ==> 3 +(denominator (/ 6 4)) ==> 2 +(denominator + (exact->inexact (/ 6 4))) ==> 2.0 +} +@end format + + +@end deffn + + + +@deffn {procedure} floor x +@deffnx {procedure} ceiling x +@deffnx {procedure} truncate x +@deffnx {procedure} round x + + +These procedures return integers. +@samp{Floor} returns the largest integer not larger than @var{x}. +@samp{Ceiling} returns the smallest integer not smaller than @var{x}. +@samp{Truncate} returns the integer closest to @var{x} whose absolute +value is not larger than the absolute value of @var{x}. @samp{Round} returns the +closest integer to @var{x}, rounding to even when @var{x} is halfway between two +integers. + + +@quotation +@emph{Rationale:} +@samp{Round} rounds to even for consistency with the default rounding +mode specified by the IEEE floating point standard. +@end quotation + + + +@quotation +@emph{Note:} +If the argument to one of these procedures is inexact, then the result +will also be inexact. If an exact value is needed, the +result should be passed to the @samp{inexact->exact} procedure. +@end quotation + + + +@format +@t{(floor -4.3) ==> -5.0 +(ceiling -4.3) ==> -4.0 +(truncate -4.3) ==> -4.0 +(round -4.3) ==> -4.0 + +(floor 3.5) ==> 3.0 +(ceiling 3.5) ==> 4.0 +(truncate 3.5) ==> 3.0 +(round 3.5) ==> 4.0 ; inexact + +(round 7/2) ==> 4 ; exact +(round 7) ==> 7 +} +@end format + + +@end deffn + + +@deffn {library procedure} rationalize x y +@c - \proto{rationalize}{ x}{procedure} + + +@samp{Rationalize} returns the @emph{simplest} rational number +differing from @var{x} by no more than @var{y}. A rational number r_1 is +@emph{simpler} than another rational number +@cindex @w{simplest rational} +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. +Although not all rationals are comparable in this ordering (consider 2/7 +and 3/5) any interval contains a rational number that is simpler than +every other rational number in that interval (the simpler 2/5 lies +between 2/7 and 3/5). Note that 0 = 0/1 is the simplest rational of +all. + + +@format +@t{(rationalize + (inexact->exact .3) 1/10) ==> 1/3 ; exact +(rationalize .3 1/10) ==> #i1/3 ; inexact +} +@end format + + +@end deffn + + +@deffn {procedure} exp @var{z} +@deffnx {procedure} log @var{z} +@deffnx {procedure} sin @var{z} +@deffnx {procedure} cos @var{z} +@deffnx {procedure} tan @var{z} +@deffnx {procedure} asin @var{z} +@deffnx {procedure} acos @var{z} +@deffnx {procedure} atan @var{z} +@deffnx {procedure} atan @var{y} @var{x} + +These procedures are part of every implementation that supports +@c %R4%% +general +real numbers; they compute the usual transcendental functions. @samp{Log} +computes the natural logarithm of @var{z} (not the base ten logarithm). +@samp{Asin}, @samp{acos}, and @samp{atan} compute arcsine (sin^-1), +arccosine (cos^-1), and arctangent (tan^-1), respectively. +The two-argument variant of @samp{atan} computes @t{(angle +(make-rectangular @var{x} @var{y}))} (see below), even in implementations +that don't support general complex numbers. + +In general, the mathematical functions log, arcsine, arccosine, and +arctangent are multiply defined. +The value of log z is defined to be the one whose imaginary +part lies in the range from -pi (exclusive) to pi (inclusive). +log 0 is undefined. +With log defined this way, the values of sin^-1 z, cos^-1 z, +and tan^-1 z are according to the following formulae: + + +@center sin^-1 z = -i log (i z + sqrt1 - z^2) + + + +@center cos^-1 z = pi / 2 - sin^-1 z + + + +@center tan^-1 z = (log (1 + i z) - log (1 - i z)) / (2 i) + + +The above specification follows [CLtL], which in turn +cites [Penfield81]; refer to these sources for more detailed +discussion of branch cuts, boundary conditions, and implementation of +these functions. When it is possible these procedures produce a real +result from a real argument. + +@c %R4%% + +@ignore todo +The cited references are likely to change their branch cuts +soon to allow for the possibility of distinct positive and negative +zeroes, as in IEEE floating point. We may not want to follow those +changes, since we may want a complex number with zero imaginary part +(whether positive or negative zero) to be treated as a real. I don't +think there are any better standards for complex arithmetic than the +ones cited, so we're really on our own here. +@end ignore + + +@end deffn + + + +@deffn {procedure} sqrt @var{z} + +Returns the principal square root of @var{z}. The result will have +either positive real part, or zero real part and non-negative imaginary +part. +@end deffn + + + +@deffn {procedure} expt z1 z2 + +Returns @var{z1} raised to the power @var{z2}. For z_1 ~= 0 + + +@center z_1^z_2 = e^z_2 log z_1 + +0^z is 1 if z = 0 and 0 otherwise. +@end deffn + +@c - \begin{entry}{%- +@c - \proto{approximate}{ z x}{procedure}} +@c - +@c - Returns an approximation to \vr{z} in a representation whose precision is +@c - the same as that +@c - of the representation of \vr{x}, which must be an inexact number. The +@c - result is always inexact. +@c - +@c - \begin{scheme} +@c - (approximate 3.1415926535 1F10) +@c - \ev 3.14159F0 +@c - (approximate 3.1415926535 \#I65535) +@c - \ev \#I3 +@c - (approximate 3.14F0 1L8) +@c - \ev 3.14L0 +@c - (approximate 3.1415926535F0 1L8) +@c - \ev 3.14159L0 +@c - \end{scheme} +@c - \end{entry} + + + + +@deffn {procedure} make-rectangular x1 x2 +@deffnx {procedure} make-polar x3 x4 +@deffnx {procedure} real-part @var{z} +@deffnx {procedure} imag-part @var{z} +@deffnx {procedure} magnitude @var{z} +@deffnx {procedure} angle @var{z} + +These procedures are part of every implementation that supports +@c %R4%% +general +complex numbers. Suppose @var{x1}, @var{x2}, @var{x3}, and @var{x4} are +real numbers and @var{z} is a complex number such that + + +@center @var{z} = @var{x1} + @var{x2}@w{i} = @var{x3} . e^@w{i} @var{x4} + +Then + +@format +@t{(make-rectangular @var{x1} @var{x2}) ==> @var{z} +(make-polar @var{x3} @var{x4}) ==> @var{z} +(real-part @var{z}) ==> @var{x1} +(imag-part @var{z}) ==> @var{x2} +(magnitude @var{z}) ==> |@var{x3}| +(angle @var{z}) ==> x_angle +} +@end format + +where -pi < x_angle <= pi with x_angle = @var{x4} + 2pi n +for some integer n. + + +@quotation +@emph{Rationale:} +@samp{Magnitude} is the same as @code{abs} for a real argument, +@vindex @w{abs} +but @samp{abs} must be present in all implementations, whereas +@samp{magnitude} need only be present in implementations that support +general complex numbers. +@end quotation + + +@end deffn + + + +@deffn {procedure} exact->inexact @var{z} +@deffnx {procedure} inexact->exact @var{z} + +@samp{Exact->inexact} returns an @r{inexact} representation of @var{z}. +The value returned is the +@r{inexact} number that is numerically closest to the argument. +@c %R4%%For +@c \tupe{exact} arguments which have no reasonably close \tupe{inexact} equivalent, +@c it is permissible to signal an error. +If an @r{exact} argument has no reasonably close @r{inexact} equivalent, +then a violation of an implementation restriction may be reported. + +@samp{Inexact->exact} returns an @r{exact} representation of +@var{z}. The value returned is the @r{exact} number that is numerically +closest to the argument. +@c %R4%% For \tupe{inexact} arguments which have no +@c reasonably close \tupe{exact} equivalent, it is permissible to signal +@c an error. +If an @r{inexact} argument has no reasonably close @r{exact} equivalent, +then a violation of an implementation restriction may be reported. + +@c %R%% I moved this to the section on implementation restrictions. +@c For any implementation that supports \tupe{inexact} quantities, +@c there is a subset of the integers for which there are both \tupe{exact} and +@c \tupe{inexact} representations. This subset must include the non-negative +@c integers up to a limit specified by the implementation. The limit +@c must be big enough to represent all digits in reasonable radices, and +@c may correspond to some natural word size for the implementation. For +@c such integers, these procedures implement the natural one-to-one +@c correspondence between the representations. + +These procedures implement the natural one-to-one correspondence between +@r{exact} and @r{inexact} integers throughout an +implementation-dependent range. See section @ref{Implementation restrictions}. + +@end deffn + +@sp 3 + +@node Numerical input and output, , Numerical operations, Numbers +@subsection Numerical input and output + + + +@deffn {procedure} number->string z +@deffnx {procedure} number->string z radix + +@var{Radix} must be an exact integer, either 2, 8, 10, or 16. If omitted, +@var{radix} defaults to 10. +The procedure @samp{number->string} takes a +number and a radix and returns as a string an external representation of +the given number in the given radix such that + +@format +@t{(let ((number @var{number}) + (radix @var{radix})) + (eqv? number + (string->number (number->string number + radix) + radix))) +} +@end format + +is true. It is an error if no possible result makes this expression true. + +If @var{z} is inexact, the radix is 10, and the above expression +can be satisfied by a result that contains a decimal point, +then the result contains a decimal point and is expressed using the +minimum number of digits (exclusive of exponent and trailing +zeroes) needed to make the above expression +true [howtoprint], [howtoread]; +otherwise the format of the result is unspecified. + +The result returned by @samp{number->string} +never contains an explicit radix prefix. + + +@quotation +@emph{Note:} +The error case can occur only when @var{z} is not a complex number +or is a complex number with a non-rational real or imaginary part. +@end quotation + + + +@quotation +@emph{Rationale:} +If @var{z} is an inexact number represented using flonums, and +the radix is 10, then the above expression is normally satisfied by +a result containing a decimal point. The unspecified case +allows for infinities, NaNs, and non-flonum representations. +@end quotation + + +@end deffn + + + +@deffn {procedure} string->number string +@deffnx {procedure} string->number string radix + +@c %R4%% I didn't include the (string->number string radix exactness) +@c case, since I haven't heard any resolution of the coding to be used +@c for the third argument. + +Returns a number of the maximally precise representation expressed by the +given @var{string}. @var{Radix} must be an exact integer, either 2, 8, 10, +or 16. If supplied, @var{radix} is a default radix that may be overridden +by an explicit radix prefix in @var{string} (e.g. @t{"#o177"}). If @var{radix} +is not supplied, then the default radix is 10. If @var{string} is not +a syntactically valid notation for a number, then @samp{string->number} +returns @t{#f}. + + +@format +@t{(string->number "100") ==> 100 +(string->number "100" 16) ==> 256 +(string->number "1e2") ==> 100.0 +(string->number "15##") ==> 1500.0 +} +@end format + + + +@quotation +@emph{Note:} +The domain of @samp{string->number} may be restricted by implementations +in the following ways. @samp{String->number} is permitted to return +@t{#f} whenever @var{string} contains an explicit radix prefix. +If all numbers supported by an implementation are real, then +@samp{string->number} is permitted to return @t{#f} whenever +@var{string} uses the polar or rectangular notations for complex +numbers. If all numbers are integers, then +@samp{string->number} may return @t{#f} whenever +the fractional notation is used. If all numbers are exact, then +@samp{string->number} may return @t{#f} whenever +an exponent marker or explicit exactness prefix is used, or if +a @t{#} appears in place of a digit. If all inexact +numbers are integers, then +@samp{string->number} may return @t{#f} whenever +a decimal point is used. +@end quotation + + +@end deffn + +@node Other data types, Control features, Numbers, Standard procedures +@section Other data types + +@menu +* Booleans:: +* Pairs and lists:: +* Symbols:: +* Characters:: +* Strings:: +* Vectors:: +@end menu + + +This section describes operations on some of Scheme's non-numeric data types: +booleans, pairs, lists, symbols, characters, strings and vectors. + +@node Booleans, Pairs and lists, Other data types, Other data types +@subsection Booleans + + + +The standard boolean objects for true and false are written as +@t{#t} and @t{#f}. What really +@vindex #f +@vindex #t +matters, though, are the objects that the Scheme conditional expressions +(@samp{if}, @samp{cond}, @samp{and}, @samp{or}, @samp{do}) treat as +true or false. The phrase ``a true value'' +@cindex @w{false} +@cindex @w{true} +(or sometimes just ``true'') means any object treated as true by the +conditional expressions, and the phrase ``a false value'' (or +@cindex @w{false} +``false'') means any object treated as false by the conditional expressions. + +Of all the standard Scheme values, only @t{#f} +@c is guaranteed to count +counts as false in conditional expressions. +@c It is not +@c specified whether the empty list\index{empty list} counts as false +@c or as true in conditional expressions. +Except for @t{#f}, +@c and possibly the empty list, +all standard Scheme values, including @t{#t}, +pairs, the empty list, symbols, numbers, strings, vectors, and procedures, +count as true. + +@c \begin{note} +@c In some implementations the empty list counts as false, contrary +@c to the above. +@c Nonetheless a few examples in this report assume that the +@c empty list counts as true, as in \cite{IEEEScheme}. +@c \end{note} + +@c \begin{rationale} +@c For historical reasons some implementations regard \schfalse{} and the +@c empty list as the same object. These implementations therefore cannot +@c make the empty list count as true in conditional expressions. +@c \end{rationale} + + +@quotation +@emph{Note:} +Programmers accustomed to other dialects of Lisp should be aware that +Scheme distinguishes both @t{#f} and the empty list +@cindex @w{empty list} +from the symbol @code{nil}. +@vindex @w{nil} +@end quotation + + +Boolean constants evaluate to themselves, so they do not need to be quoted +in programs. + + +@example + +#t ==> #t +#f ==> #f +'#f ==> #f + +@end example + + + + +@deffn {library procedure} not obj + +@samp{Not} returns @t{#t} if @var{obj} is false, and returns +@t{#f} otherwise. + + +@format +@t{(not #t) ==> #f +(not 3) ==> #f +(not (list 3)) ==> #f +(not #f) ==> #t +(not '()) ==> #f +(not (list)) ==> #f +(not 'nil) ==> #f +} +@end format + + +@end deffn + + + +@deffn {library procedure} boolean? obj + +@samp{Boolean?} returns @t{#t} if @var{obj} is either @t{#t} or +@t{#f} and returns @t{#f} otherwise. + + +@format +@t{(boolean? #f) ==> #t +(boolean? 0) ==> #f +(boolean? '()) ==> #f +} +@end format + + +@end deffn + + +@node Pairs and lists, Symbols, Booleans, Other data types +@subsection Pairs and lists + + + +A @dfn{pair} (sometimes called a @dfn{dotted pair}) is a +@cindex @w{dotted pair} +@cindex @w{pair} +record structure with two fields called the car and cdr fields (for +historical reasons). Pairs are created by the procedure @samp{cons}. +The car and cdr fields are accessed by the procedures @samp{car} and +@samp{cdr}. The car and cdr fields are assigned by the procedures +@samp{set-car!} and @samp{set-cdr!}. + +Pairs are used primarily to represent lists. A list can +be defined recursively as either the empty list or a pair whose +@cindex @w{empty list} +cdr is a list. More precisely, the set of lists is defined as the smallest +set @var{X} such that + + + +@itemize @bullet + +@item +The empty list is in @var{X}. +@item +If @var{list} is in @var{X}, then any pair whose cdr field contains +@var{list} is also in @var{X}. + +@end itemize + + +The objects in the car fields of successive pairs of a list are the +elements of the list. For example, a two-element list is a pair whose car +is the first element and whose cdr is a pair whose car is the second element +and whose cdr is the empty list. The length of a list is the number of +elements, which is the same as the number of pairs. + +The empty list is a special object of its own type +@cindex @w{empty list} +(it is not a pair); it has no elements and its length is zero. + + +@quotation +@emph{Note:} +The above definitions imply that all lists have finite length and are +terminated by the empty list. +@end quotation + + +The most general notation (external representation) for Scheme pairs is +the ``dotted'' notation @w{@samp{(@var{c1} .@: @var{c2})}} where +@var{c1} is the value of the car field and @var{c2} is the value of the +cdr field. For example @samp{(4 .@: 5)} is a pair whose car is 4 and whose +cdr is 5. Note that @samp{(4 .@: 5)} is the external representation of a +pair, not an expression that evaluates to a pair. + +A more streamlined notation can be used for lists: the elements of the +list are simply enclosed in parentheses and separated by spaces. The +empty list is written @t{()} . For example, +@cindex @w{empty list} + + +@example + +(a b c d e) + +@end example + + +and + + +@example + +(a . (b . (c . (d . (e . ()))))) + +@end example + + +are equivalent notations for a list of symbols. + +A chain of pairs not ending in the empty list is called an +@dfn{improper list}. Note that an improper list is not a list. +@cindex @w{improper list} +The list and dotted notations can be combined to represent +improper lists: + + +@example + +(a b c . d) + +@end example + + +is equivalent to + + +@example + +(a . (b . (c . d))) + +@end example + + +Whether a given pair is a list depends upon what is stored in the cdr +field. When the @code{set-cdr!} procedure is used, an object can be a +@vindex @w{set-cdr!} +list one moment and not the next: + + +@example + +(define x (list 'a 'b 'c)) +(define y x) +y ==> (a b c) +(list? y) ==> #t +(set-cdr! x 4) ==> @emph{unspecified} +x ==> (a . 4) +(eqv? x y) ==> #t +y ==> (a . 4) +(list? y) ==> #f +(set-cdr! x x) ==> @emph{unspecified} +(list? x) ==> #f + +@end example + + +@c It is often convenient to speak of a homogeneous list of objects +@c of some particular data type, as for example \hbox{\cf (1 2 3)} is a list of +@c integers. To be more precise, suppose \var{D} is some data type. (Any +@c predicate defines a data type consisting of those objects of which the +@c predicate is true.) Then + +@c \begin{itemize} +@c \item The empty list is a list of \var{D}. +@c \item If \var{list} is a list of \var{D}, then any pair whose cdr is +@c \var{list} and whose car is an element of the data type \var{D} is also a +@c list of \var{D}. +@c \item There are no other lists of \var{D}. +@c \end{itemize} + +Within literal expressions and representations of objects read by the +@code{read} procedure, the forms @t{'}@r{<datum>}, +@vindex ' +@vindex @w{read} +@t{`}@r{<datum>}, @t{,}@r{<datum>}, and +@vindex , +@t{,@@}@r{<datum>} denote two-ele@-ment lists whose first elements are +the symbols @code{quote}, @code{quasiquote}, @w{@code{unquote}}, and +@vindex @w{unquote} +@vindex @w{quasiquote} +@vindex @w{quote} +@code{unquote-splicing}, respectively. The second element in each case +@vindex @w{unquote-splicing} +is @r{<datum>}. This convention is supported so that arbitrary Scheme +programs may be represented as lists. +@ignore todo +Can or need this be stated +more carefully? +@end ignore + That is, according to Scheme's grammar, every +<expression> is also a <datum> (see section @pxref{External representation}). +Among other things, this permits the use of the @samp{read} procedure to +parse Scheme programs. See section @ref{External representations}. + + + +@deffn {procedure} pair? obj + +@samp{Pair?} returns @t{#t} if @var{obj} is a pair, and otherwise +returns @t{#f}. + + +@format +@t{(pair? '(a . b)) ==> #t +(pair? '(a b c)) ==> #t +(pair? '()) ==> #f +(pair? '#(a b)) ==> #f +} +@end format + +@end deffn + + + +@deffn {procedure} cons obj1 obj2 + +Returns a newly allocated pair whose car is @var{obj1} and whose cdr is +@var{obj2}. The pair is guaranteed to be different (in the sense of +@samp{eqv?}) from every existing object. + + +@format +@t{(cons 'a '()) ==> (a) +(cons '(a) '(b c d)) ==> ((a) b c d) +(cons "a" '(b c)) ==> ("a" b c) +(cons 'a 3) ==> (a . 3) +(cons '(a b) 'c) ==> ((a b) . c) +} +@end format + +@end deffn + + + +@deffn {procedure} car pair + +@ignore nodomain +@var{Pair} must be a pair. +@end ignore + +Returns the contents of the car field of @var{pair}. Note that it is an +error to take the car of the empty list. +@cindex @w{empty list} + + +@format +@t{(car '(a b c)) ==> a +(car '((a) b c d)) ==> (a) +(car '(1 . 2)) ==> 1 +(car '()) ==> @emph{error} +} +@end format + + +@end deffn + + + +@deffn {procedure} cdr pair + +@ignore nodomain +@var{Pair} must be a pair. +@end ignore + +Returns the contents of the cdr field of @var{pair}. +Note that it is an error to take the cdr of the empty list. + + +@format +@t{(cdr '((a) b c d)) ==> (b c d) +(cdr '(1 . 2)) ==> 2 +(cdr '()) ==> @emph{error} +} +@end format + + +@end deffn + + + +@deffn {procedure} set-car! pair obj + +@ignore nodomain +@var{Pair} must be a pair. +@end ignore + +Stores @var{obj} in the car field of @var{pair}. +The value returned by @samp{set-car!} is unspecified. +@c <!> +@c This procedure can be very confusing if used indiscriminately. + + +@format +@t{(define (f) (list 'not-a-constant-list)) +(define (g) '(constant-list)) +(set-car! (f) 3) ==> @emph{unspecified} +(set-car! (g) 3) ==> @emph{error} +} +@end format + + +@end deffn + + + +@deffn {procedure} set-cdr! pair obj + +@ignore nodomain +@var{Pair} must be a pair. +@end ignore + +Stores @var{obj} in the cdr field of @var{pair}. +The value returned by @samp{set-cdr!} is unspecified. +@c <!> +@c This procedure can be very confusing if used indiscriminately. + +@end deffn + + + + + + +@deffn {library procedure} caar pair +@deffnx {library procedure} cadr pair + +@deffnx { @w{ @dots{}}} @w{ @dots{}} + +@deffnx {library procedure} cdddar pair +@deffnx {library procedure} cddddr pair + +These procedures are compositions of @samp{car} and @samp{cdr}, where +for example @samp{caddr} could be defined by + + +@format +@t{(define caddr (lambda (x) (car (cdr (cdr x)))))@r{.} +} +@end format + + +Arbitrary compositions, up to four deep, are provided. There are +twenty-eight of these procedures in all. + +@end deffn + + + +@deffn {library procedure} null? obj + +Returns @t{#t} if @var{obj} is the empty list, +@cindex @w{empty list} +otherwise returns @t{#f}. + +@c \begin{note} +@c In implementations in which the empty +@c list is the same as \schfalse{}, {\cf null?} will return \schtrue{} +@c if \var{obj} is \schfalse{}. +@c \end{note} + +@end deffn + + +@deffn {library procedure} list? obj + +Returns @t{#t} if @var{obj} is a list, otherwise returns @t{#f}. +By definition, all lists have finite length and are terminated by +the empty list. + + +@format +@t{ (list? '(a b c)) ==> #t + (list? '()) ==> #t + (list? '(a . b)) ==> #f + (let ((x (list 'a))) + (set-cdr! x x) + (list? x)) ==> #f +} +@end format + +@end deffn + + + +@deffn {library procedure} list @var{obj} @dots{}, + +Returns a newly allocated list of its arguments. + + +@format +@t{(list 'a (+ 3 4) 'c) ==> (a 7 c) +(list) ==> () +} +@end format + +@end deffn + + + +@deffn {library procedure} length list + +@ignore nodomain +@var{List} must be a list. +@end ignore + +Returns the length of @var{list}. + + +@format +@t{(length '(a b c)) ==> 3 +(length '(a (b) (c d e))) ==> 3 +(length '()) ==> 0 +} +@end format + +@end deffn + + + +@deffn {library procedure} append list @dots{}, + +@ignore nodomain +All @var{list}s should be lists. +@end ignore + +Returns a list consisting of the elements of the first @var{list} +followed by the elements of the other @var{list}s. + + +@format +@t{(append '(x) '(y)) ==> (x y) +(append '(a) '(b c d)) ==> (a b c d) +(append '(a (b)) '((c))) ==> (a (b) (c)) +} +@end format + + +The resulting list is always newly allocated, except that it shares +structure with the last @var{list} argument. The last argument may +actually be any object; an improper list results if the last argument is not a +proper list. +@ignore todo +This is pretty awkward. I should get Bartley to fix this. +@end ignore + + + +@format +@t{(append '(a b) '(c . d)) ==> (a b c . d) +(append '() 'a) ==> a +} +@end format + +@end deffn + + + +@deffn {library procedure} reverse list + +@ignore nodomain +@var{List} must be a list. +@end ignore + +Returns a newly allocated list consisting of the elements of @var{list} +in reverse order. + + +@format +@t{(reverse '(a b c)) ==> (c b a) +(reverse '(a (b c) d (e (f)))) + ==> ((e (f)) d (b c) a) +} +@end format + +@end deffn + + + +@deffn {library procedure} list-tail list @var{k} + +Returns the sublist of @var{list} obtained by omitting the first @var{k} +elements. It is an error if @var{list} has fewer than @var{k} elements. +@samp{List-tail} could be defined by + + +@format +@t{(define list-tail + (lambda (x k) + (if (zero? k) + x + (list-tail (cdr x) (- k 1))))) +} +@end format + +@end deffn + + + +@deffn {library procedure} list-ref list @var{k} + +Returns the @var{k}th element of @var{list}. (This is the same +as the car of @t{(list-tail @var{list} @var{k})}.) +It is an error if @var{list} has fewer than @var{k} elements. + + +@format +@t{(list-ref '(a b c d) 2) ==> c +(list-ref '(a b c d) + (inexact->exact (round 1.8))) + ==> c +} +@end format + +@end deffn + + +@c \begin{entry}{% +@c \proto{last-pair}{ list}{library procedure}} + +@c Returns the last pair in the nonempty, possibly improper, list \var{list}. +@c {\cf Last-pair} could be defined by + +@c \begin{scheme} +@c (define last-pair +@c (lambda (x) +@c (if (pair? (cdr x)) +@c (last-pair (cdr x)) +@c x)))% +@c \end{scheme} + +@c \end{entry} + + + +@deffn {library procedure} memq obj list +@deffnx {library procedure} memv obj list +@deffnx {library procedure} member obj list + +These procedures return the first sublist of @var{list} whose car is +@var{obj}, where the sublists of @var{list} are the non-empty lists +returned by @t{(list-tail @var{list} @var{k})} for @var{k} less +than the length of @var{list}. If +@var{obj} does not occur in @var{list}, then @t{#f} (not the empty list) is +returned. @samp{Memq} uses @samp{eq?} to compare @var{obj} with the elements of +@var{list}, while @samp{memv} uses @samp{eqv?} and @samp{member} uses @samp{equal?}. + + +@format +@t{(memq 'a '(a b c)) ==> (a b c) +(memq 'b '(a b c)) ==> (b c) +(memq 'a '(b c d)) ==> #f +(memq (list 'a) '(b (a) c)) ==> #f +(member (list 'a) + '(b (a) c)) ==> ((a) c) +(memq 101 '(100 101 102)) ==> @emph{unspecified} +(memv 101 '(100 101 102)) ==> (101 102) +} +@end format + + +@end deffn + + + +@deffn {library procedure} assq obj alist +@deffnx {library procedure} assv obj alist +@deffnx {library procedure} assoc obj alist + +@var{Alist} (for ``association list'') must be a list of +pairs. These procedures find the first pair in @var{alist} whose car field is @var{obj}, +and returns that pair. If no pair in @var{alist} has @var{obj} as its +car, then @t{#f} (not the empty list) is returned. @samp{Assq} uses +@samp{eq?} to compare @var{obj} with the car fields of the pairs in @var{alist}, +while @samp{assv} uses @samp{eqv?} and @samp{assoc} uses @samp{equal?}. + + +@format +@t{(define e '((a 1) (b 2) (c 3))) +(assq 'a e) ==> (a 1) +(assq 'b e) ==> (b 2) +(assq 'd e) ==> #f +(assq (list 'a) '(((a)) ((b)) ((c)))) + ==> #f +(assoc (list 'a) '(((a)) ((b)) ((c)))) + ==> ((a)) +(assq 5 '((2 3) (5 7) (11 13))) + ==> @emph{unspecified} +(assv 5 '((2 3) (5 7) (11 13))) + ==> (5 7) +} +@end format + + + + +@quotation +@emph{Rationale:} +Although they are ordinarily used as predicates, +@samp{memq}, @samp{memv}, @samp{member}, @samp{assq}, @samp{assv}, and @samp{assoc} do not +have question marks in their names because they return useful values rather +than just @t{#t} or @t{#f}. +@end quotation + +@end deffn + + +@node Symbols, Characters, Pairs and lists, Other data types +@subsection Symbols + + + +Symbols are objects whose usefulness rests on the fact that two +symbols are identical (in the sense of @samp{eqv?}) if and only if their +names are spelled the same way. This is exactly the property needed to +represent identifiers in programs, and so most +@cindex @w{identifier} +implementations of Scheme use them internally for that purpose. Symbols +are useful for many other applications; for instance, they may be used +the way enumerated values are used in Pascal. + +The rules for writing a symbol are exactly the same as the rules for +writing an identifier; see sections @ref{Identifiers} +and @ref{Lexical structure}. + +It is guaranteed that any symbol that has been returned as part of +a literal expression, or read using the @samp{read} procedure, and +subsequently written out using the @samp{write} procedure, will read back +in as the identical symbol (in the sense of @samp{eqv?}). The +@samp{string->symbol} procedure, however, can create symbols for +which this write/read invariance may not hold because their names +contain special characters or letters in the non-standard case. + + +@quotation +@emph{Note:} +Some implementations of Scheme have a feature known as ``slashification'' +in order to guarantee write/read invariance for all symbols, but +historically the most important use of this feature has been to +compensate for the lack of a string data type. + +Some implementations also have ``uninterned symbols'', which +defeat write/read invariance even in implementations with slashification, +and also generate exceptions to the rule that two symbols are the same +if and only if their names are spelled the same. +@end quotation + + + + +@deffn {procedure} symbol? obj + +Returns @t{#t} if @var{obj} is a symbol, otherwise returns @t{#f}. + + +@format +@t{(symbol? 'foo) ==> #t +(symbol? (car '(a b))) ==> #t +(symbol? "bar") ==> #f +(symbol? 'nil) ==> #t +(symbol? '()) ==> #f +(symbol? #f) ==> #f +} +@end format + +@end deffn + + + +@deffn {procedure} symbol->string symbol + +Returns the name of @var{symbol} as a string. If the symbol was part of +an object returned as the value of a literal expression +(section @pxref{Literal expressions}) or by a call to the @samp{read} procedure, +and its name contains alphabetic characters, then the string returned +will contain characters in the implementation's preferred standard +case---some implementations will prefer upper case, others lower case. +If the symbol was returned by @samp{string->symbol}, the case of +characters in the string returned will be the same as the case in the +string that was passed to @samp{string->symbol}. It is an error +to apply mutation procedures like @code{string-set!} to strings returned +@vindex @w{string-set!} +by this procedure. + +The following examples assume that the implementation's standard case is +lower case: + + +@format +@t{(symbol->string 'flying-fish) + ==> "flying-fish" +(symbol->string 'Martin) ==> "martin" +(symbol->string + (string->symbol "Malvina")) + ==> "Malvina" +} +@end format + +@end deffn + + + +@deffn {procedure} string->symbol string + +Returns the symbol whose name is @var{string}. This procedure can +create symbols with names containing special characters or letters in +the non-standard case, but it is usually a bad idea to create such +symbols because in some implementations of Scheme they cannot be read as +themselves. See @samp{symbol->string}. + +The following examples assume that the implementation's standard case is +lower case: + + +@format +@t{(eq? 'mISSISSIppi 'mississippi) + ==> #t +(string->symbol "mISSISSIppi") + ==> + @r{}the symbol with name "mISSISSIppi" +(eq? 'bitBlt (string->symbol "bitBlt")) + ==> #f +(eq? 'JollyWog + (string->symbol + (symbol->string 'JollyWog))) + ==> #t +(string=? "K. Harper, M.D." + (symbol->string + (string->symbol "K. Harper, M.D."))) + ==> #t +} +@end format + + +@end deffn + + +@node Characters, Strings, Symbols, Other data types +@subsection Characters + + + +Characters are objects that represent printed characters such as +letters and digits. +@c There is no requirement that the data type of +@c characters be disjoint from other data types; implementations are +@c encouraged to have a separate character data type, but may choose to +@c represent characters as integers, strings, or some other type. +Characters are written using the notation #\@r{<character>} +or #\@r{<character name>}. +For example: + + + +@center @c begin-tabular +@quotation +@table @asis +@item @t{#\a} +; lower case letter +@item @t{#\A} +; upper case letter +@item @t{#\(} +; left parenthesis +@item @t{#\ } +; the space character +@item @t{#\space} +; the preferred way to write a space +@item @t{#\newline} +; the newline character +@item +@end table +@end quotation + + + + +Case is significant in #\@r{<character>}, but not in +#\@r{<character name>}. +@c \hyper doesn't + +@c allow a linebreak +If @r{<character>} in +#\@r{<character>} is alphabetic, then the character +following @r{<character>} must be a delimiter character such as a +space or parenthesis. This rule resolves the ambiguous case where, for +example, the sequence of characters ``@t{#\ space}'' +could be taken to be either a representation of the space character or a +representation of the character ``@t{#\ s}'' followed +by a representation of the symbol ``@t{pace}.'' + +@ignore todo +Fix +@end ignore + +Characters written in the #\ notation are self-evaluating. +That is, they do not have to be quoted in programs. +@c The \sharpsign\backwhack{} +@c notation is not an essential part of Scheme, however. Even implementations +@c that support the \sharpsign\backwhack{} notation for input do not have to +@c support it for output. + +Some of the procedures that operate on characters ignore the +difference between upper case and lower case. The procedures that +ignore case have @w{``@t{-ci}''} (for ``case +insensitive'') embedded in their names. + + + +@deffn {procedure} char? obj + +Returns @t{#t} if @var{obj} is a character, otherwise returns @t{#f}. + +@end deffn + + + +@deffn {procedure} char=? char1 char2 +@deffnx {procedure} char<? char1 char2 +@deffnx {procedure} char>? char1 char2 +@deffnx {procedure} char<=? char1 char2 +@deffnx {procedure} char>=? char1 char2 + + +@ignore nodomain +Both @var{char1} and @var{char2} must be characters. +@end ignore + +These procedures impose a total ordering on the set of characters. It +is guaranteed that under this ordering: + + + +@itemize @bullet + +@item +The upper case characters are in order. For example, @samp{(char<? #\A #\B)} returns @t{#t}. +@item +The lower case characters are in order. For example, @samp{(char<? #\a #\b)} returns @t{#t}. +@item +The digits are in order. For example, @samp{(char<? #\0 #\9)} returns @t{#t}. +@item +Either all the digits precede all the upper case letters, or vice versa. +@item +Either all the digits precede all the lower case letters, or vice versa. + +@end itemize + + +Some implementations may generalize these procedures to take more than +two arguments, as with the corresponding numerical predicates. + +@end deffn + + + +@deffn {library procedure} char-ci=? char1 char2 +@deffnx {library procedure} char-ci<? char1 char2 +@deffnx {library procedure} char-ci>? char1 char2 +@deffnx {library procedure} char-ci<=? char1 char2 +@deffnx {library procedure} char-ci>=? char1 char2 + +@ignore nodomain +Both @var{char1} and @var{char2} must be characters. +@end ignore + +These procedures are similar to @samp{char=?} et cetera, but they treat +upper case and lower case letters as the same. For example, @samp{(char-ci=? #\A #\a)} returns @t{#t}. Some +implementations may generalize these procedures to take more than two +arguments, as with the corresponding numerical predicates. + +@end deffn + + + +@deffn {library procedure} char-alphabetic? char +@deffnx {library procedure} char-numeric? char +@deffnx {library procedure} char-whitespace? char +@deffnx {library procedure} char-upper-case? letter +@deffnx {library procedure} char-lower-case? letter + +These procedures return @t{#t} if their arguments are alphabetic, +numeric, whitespace, upper case, or lower case characters, respectively, +otherwise they return @t{#f}. The following remarks, which are specific to +the ASCII character set, are intended only as a guide: The alphabetic characters +are the 52 upper and lower case letters. The numeric characters are the +ten decimal digits. The whitespace characters are space, tab, line +feed, form feed, and carriage return. +@end deffn + + +@c %R4%%\begin{entry}{% +@c \proto{char-upper-case?}{ letter}{procedure} +@c \proto{char-lower-case?}{ letter}{procedure}} + +@c \domain{\var{Letter} must be an alphabetic character.} +@c These procedures return \schtrue{} if their arguments are upper case or +@c lower case characters, respectively, otherwise they return \schfalse. +@c \end{entry} + + + +@deffn {procedure} char->integer char +@deffnx {procedure} integer->char @var{n} + +Given a character, @samp{char->integer} returns an exact integer +representation of the character. Given an exact integer that is the image of +a character under @samp{char->integer}, @samp{integer->char} +returns that character. These procedures implement order-preserving isomorphisms +between the set of characters under the @code{char<=?} ordering and some +@vindex @w{char<=?} +subset of the integers under the @samp{<=} ordering. That is, if + + +@format +@t{(char<=? @var{a} @var{b}) @result{} #t @r{}and (<= @var{x} @var{y}) @result{} #t +} +@end format + + + +@noindent + and @var{x} and @var{y} are in the domain of +@samp{integer->char}, then + + +@format +@t{(<= (char->integer @var{a}) + (char->integer @var{b})) ==> #t + +(char<=? (integer->char @var{x}) + (integer->char @var{y})) ==> #t +} +@end format + + +@end deffn + + + +@deffn {library procedure} char-upcase char +@deffnx {library procedure} char-downcase char + +@ignore nodomain +@var{Char} must be a character. +@end ignore + +These procedures return a character @var{char2} such that @samp{(char-ci=? @var{char} @var{char2})}. In addition, if @var{char} is +alphabetic, then the result of @samp{char-upcase} is upper case and the +result of @samp{char-downcase} is lower case. + +@end deffn + + +@node Strings, Vectors, Characters, Other data types +@subsection Strings + + + +Strings are sequences of characters. +@c In some implementations of Scheme +@c they are immutable; other implementations provide destructive procedures +@c such as {\cf string-set!}\ that alter string objects. +Strings are written as sequences of characters enclosed within doublequotes +(@samp{"}). A doublequote can be written inside a string only by escaping +it with a backslash (\), as in + + +@example + +"The word \"recursion\" has many meanings." + +@end example + + +A backslash can be written inside a string only by escaping it with another +backslash. Scheme does not specify the effect of a backslash within a +string that is not followed by a doublequote or backslash. + +A string constant may continue from one line to the next, but +the exact contents of such a string are unspecified. +@c this is +@c usually a bad idea because +@c the exact effect may vary from one computer +@c system to another. + +The @emph{length} of a string is the number of characters that it +contains. This number is an exact, non-negative integer that is fixed when the +string is created. The @dfn{valid indexes} of a string are the +@cindex @w{valid indexes} +exact non-negative integers less than the length of the string. The first +character of a string has index 0, the second has index 1, and so on. + +In phrases such as ``the characters of @var{string} beginning with +index @var{start} and ending with index @var{end},'' it is understood +that the index @var{start} is inclusive and the index @var{end} is +exclusive. Thus if @var{start} and @var{end} are the same index, a null +substring is referred to, and if @var{start} is zero and @var{end} is +the length of @var{string}, then the entire string is referred to. + +Some of the procedures that operate on strings ignore the +difference between upper and lower case. The versions that ignore case +have @w{``@samp{-ci}''} (for ``case insensitive'') embedded in their +names. + + + +@deffn {procedure} string? obj + +Returns @t{#t} if @var{obj} is a string, otherwise returns @t{#f}. +@end deffn + + + +@deffn {procedure} make-string @var{k} +@deffnx {procedure} make-string @var{k} char + +@c \domain{\vr{k} must be a non-negative integer, and \var{char} must be +@c a character.} +@samp{Make-string} returns a newly allocated string of +length @var{k}. If @var{char} is given, then all elements of the string +are initialized to @var{char}, otherwise the contents of the +@var{string} are unspecified. + +@end deffn + + +@deffn {library procedure} string char @dots{}, + +Returns a newly allocated string composed of the arguments. + +@end deffn + + +@deffn {procedure} string-length string + +Returns the number of characters in the given @var{string}. +@end deffn + + + +@deffn {procedure} string-ref string @var{k} + +@var{k} must be a valid index of @var{string}. +@samp{String-ref} returns character @var{k} of @var{string} using zero-origin indexing. +@end deffn + + + +@deffn {procedure} string-set! string k char + + +@c \var{String} must be a string, +@var{k} must be a valid index of @var{string} +@c , and \var{char} must be a character +. +@samp{String-set!} stores @var{char} in element @var{k} of @var{string} +and returns an unspecified value. +@c <!> + + +@format +@t{(define (f) (make-string 3 #\*)) +(define (g) "***") +(string-set! (f) 0 #\?) ==> @emph{unspecified} +(string-set! (g) 0 #\?) ==> @emph{error} +(string-set! (symbol->string 'immutable) + 0 + #\?) ==> @emph{error} +} +@end format + + +@end deffn + + + +@deffn {library procedure} string=? string1 string2 +@deffnx {library procedure} string-ci=? string1 string2 + +Returns @t{#t} if the two strings are the same length and contain the same +characters in the same positions, otherwise returns @t{#f}. +@samp{String-ci=?} treats +upper and lower case letters as though they were the same character, but +@samp{string=?} treats upper and lower case as distinct characters. + +@end deffn + + + +@deffn {library procedure} string<? string1 string2 +@deffnx {library procedure} string>? string1 string2 +@deffnx {library procedure} string<=? string1 string2 +@deffnx {library procedure} string>=? string1 string2 +@deffnx {library procedure} string-ci<? string1 string2 +@deffnx {library procedure} string-ci>? string1 string2 +@deffnx {library procedure} string-ci<=? string1 string2 +@deffnx {library procedure} string-ci>=? string1 string2 + +These procedures are the lexicographic extensions to strings of the +corresponding orderings on characters. For example, @samp{string<?} is +the lexicographic ordering on strings induced by the ordering +@samp{char<?} on characters. If two strings differ in length but +are the same up to the length of the shorter string, the shorter string +is considered to be lexicographically less than the longer string. + +Implementations may generalize these and the @samp{string=?} and +@samp{string-ci=?} procedures to take more than two arguments, as with +the corresponding numerical predicates. + +@end deffn + + + +@deffn {library procedure} substring string start end + +@var{String} must be a string, and @var{start} and @var{end} +must be exact integers satisfying + + +@center 0 <= @var{start} <= @var{end} <= @w{@t{(string-length @var{string})@r{.}}} + +@samp{Substring} returns a newly allocated string formed from the characters of +@var{string} beginning with index @var{start} (inclusive) and ending with index +@var{end} (exclusive). +@end deffn + + + +@deffn {library procedure} string-append @var{string} @dots{}, + +Returns a newly allocated string whose characters form the concatenation of the +given strings. + +@end deffn + + + +@deffn {library procedure} string->list string +@deffnx {library procedure} list->string list + +@samp{String->list} returns a newly allocated list of the +characters that make up the given string. @samp{List->string} +returns a newly allocated string formed from the characters in the list +@var{list}, which must be a list of characters. @samp{String->list} +and @samp{list->string} are +inverses so far as @samp{equal?} is concerned. +@c Implementations that provide +@c destructive operations on strings should ensure that the result of +@c {\cf list\coerce{}string} is newly allocated. + +@end deffn + + + +@deffn {library procedure} string-copy string + +Returns a newly allocated copy of the given @var{string}. + +@end deffn + + + +@deffn {library procedure} string-fill! string char + +Stores @var{char} in every element of the given @var{string} and returns an +unspecified value. +@c <!> + +@end deffn + + +@node Vectors, , Strings, Other data types +@subsection Vectors + + + +Vectors are heterogenous structures whose elements are indexed +by integers. A vector typically occupies less space than a list +of the same length, and the average time required to access a randomly +chosen element is typically less for the vector than for the list. + +The @emph{length} of a vector is the number of elements that it +contains. This number is a non-negative integer that is fixed when the +vector is created. The @emph{valid indexes} of a +@cindex @w{valid indexes} +vector are the exact non-negative integers less than the length of the +vector. The first element in a vector is indexed by zero, and the last +element is indexed by one less than the length of the vector. + +Vectors are written using the notation @t{#(@var{obj} @dots{},)}. +For example, a vector of length 3 containing the number zero in element +0, the list @samp{(2 2 2 2)} in element 1, and the string @samp{"Anna"} in +element 2 can be written as following: + + +@example + +#(0 (2 2 2 2) "Anna") + +@end example + + +Note that this is the external representation of a vector, not an +expression evaluating to a vector. Like list constants, vector +constants must be quoted: + + +@example + +'#(0 (2 2 2 2) "Anna") + ==> #(0 (2 2 2 2) "Anna") + +@end example + + +@ignore todo +Pitman sez: The visual similarity to lists is bound to be confusing +to some. Elaborate on the distinction. +@end ignore + + + + +@deffn {procedure} vector? obj + +Returns @t{#t} if @var{obj} is a vector, otherwise returns @t{#f}. +@end deffn + + + +@deffn {procedure} make-vector k +@deffnx {procedure} make-vector k fill + +Returns a newly allocated vector of @var{k} elements. If a second +argument is given, then each element is initialized to @var{fill}. +Otherwise the initial contents of each element is unspecified. + +@end deffn + + + +@deffn {library procedure} vector obj @dots{}, + +Returns a newly allocated vector whose elements contain the given +arguments. Analogous to @samp{list}. + + +@format +@t{(vector 'a 'b 'c) ==> #(a b c) +} +@end format + +@end deffn + + + +@deffn {procedure} vector-length vector + +Returns the number of elements in @var{vector} as an exact integer. +@end deffn + + + +@deffn {procedure} vector-ref vector k + +@var{k} must be a valid index of @var{vector}. +@samp{Vector-ref} returns the contents of element @var{k} of +@var{vector}. + + +@format +@t{(vector-ref '#(1 1 2 3 5 8 13 21) + 5) + ==> 8 +(vector-ref '#(1 1 2 3 5 8 13 21) + (let ((i (round (* 2 (acos -1))))) + (if (inexact? i) + (inexact->exact i) + i))) + ==> 13 +} +@end format + +@end deffn + + + +@deffn {procedure} vector-set! vector k obj + +@var{k} must be a valid index of @var{vector}. +@samp{Vector-set!} stores @var{obj} in element @var{k} of @var{vector}. +The value returned by @samp{vector-set!} is unspecified. +@c <!> + + +@format +@t{(let ((vec (vector 0 '(2 2 2 2) "Anna"))) + (vector-set! vec 1 '("Sue" "Sue")) + vec) + ==> #(0 ("Sue" "Sue") "Anna") + +(vector-set! '#(0 1 2) 1 "doe") + ==> @emph{error} ; constant vector +} +@end format + +@end deffn + + + +@deffn {library procedure} vector->list vector +@deffnx {library procedure} list->vector list + +@samp{Vector->list} returns a newly allocated list of the objects contained +in the elements of @var{vector}. @samp{List->vector} returns a newly +created vector initialized to the elements of the list @var{list}. + + +@format +@t{(vector->list '#(dah dah didah)) + ==> (dah dah didah) +(list->vector '(dididit dah)) + ==> #(dididit dah) +} +@end format + +@end deffn + + + +@deffn {library procedure} vector-fill! vector fill + +Stores @var{fill} in every element of @var{vector}. +The value returned by @samp{vector-fill!} is unspecified. +@c <!> + +@end deffn + + +@node Control features, Eval, Other data types, Standard procedures +@section Control features + + + +@c Intro flushed; not very a propos any more. +@c Procedures should be discussed somewhere, however. + +This chapter describes various primitive procedures which control the +flow of program execution in special ways. +The @samp{procedure?} predicate is also described here. + +@ignore todo +@t{Procedure?} doesn't belong in a section with the name +``control features.'' What to do? +@end ignore + + + +@deffn {procedure} procedure? obj + +Returns @t{#t} if @var{obj} is a procedure, otherwise returns @t{#f}. + + +@format +@t{(procedure? car) ==> #t +(procedure? 'car) ==> #f +(procedure? (lambda (x) (* x x))) + ==> #t +(procedure? '(lambda (x) (* x x))) + ==> #f +(call-with-current-continuation procedure?) + ==> #t +} +@end format + + +@end deffn + + + +@deffn {procedure} apply proc arg1 @dots{} args + +@var{Proc} must be a procedure and @var{args} must be a list. +Calls @var{proc} with the elements of the list +@samp{(append (list @var{arg1} @dots{},) @var{args})} as the actual +arguments. + + +@format +@t{(apply + (list 3 4)) ==> 7 + +(define compose + (lambda (f g) + (lambda args + (f (apply g args))))) + +((compose sqrt *) 12 75) ==> 30 +} +@end format + +@end deffn + + + +@deffn {library procedure} map proc list1 list2 @dots{}, + +The @var{list}s must be lists, and @var{proc} must be a +procedure taking as many arguments as there are @i{list}s +and returning a single value. If more +than one @var{list} is given, then they must all be the same length. +@samp{Map} applies @var{proc} element-wise to the elements of the +@var{list}s and returns a list of the results, in order. +The dynamic order in which @var{proc} is applied to the elements of the +@var{list}s is unspecified. + + +@format +@t{(map cadr '((a b) (d e) (g h))) + ==> (b e h) + +(map (lambda (n) (expt n n)) + '(1 2 3 4 5)) + ==> (1 4 27 256 3125) + +(map + '(1 2 3) '(4 5 6)) ==> (5 7 9) + +(let ((count 0)) + (map (lambda (ignored) + (set! count (+ count 1)) + count) + '(a b))) ==> (1 2) @var{or} (2 1) +} +@end format + + +@end deffn + + + +@deffn {library procedure} for-each proc list1 list2 @dots{}, + +The arguments to @samp{for-each} are like the arguments to @samp{map}, but +@samp{for-each} calls @var{proc} for its side effects rather than for its +values. Unlike @samp{map}, @samp{for-each} is guaranteed to call @var{proc} on +the elements of the @var{list}s in order from the first element(s) to the +last, and the value returned by @samp{for-each} is unspecified. + + +@format +@t{(let ((v (make-vector 5))) + (for-each (lambda (i) + (vector-set! v i (* i i))) + '(0 1 2 3 4)) + v) ==> #(0 1 4 9 16) +} +@end format + + +@end deffn + + + +@deffn {library procedure} force promise + +Forces the value of @var{promise} (see @code{delay}, +@vindex @w{delay} +section @pxref{Delayed evaluation}). If no value has been computed for +@cindex @w{promise} +the promise, then a value is computed and returned. The value of the +promise is cached (or ``memoized'') so that if it is forced a second +time, the previously computed value is returned. +@c without any recomputation. +@c [As pointed out by Marc Feeley, the "without any recomputation" +@c isn't necessarily true. --Will] + + +@format +@t{(force (delay (+ 1 2))) ==> 3 +(let ((p (delay (+ 1 2)))) + (list (force p) (force p))) + ==> (3 3) + +(define a-stream + (letrec ((next + (lambda (n) + (cons n (delay (next (+ n 1))))))) + (next 0))) +(define head car) +(define tail + (lambda (stream) (force (cdr stream)))) + +(head (tail (tail a-stream))) + ==> 2 +} +@end format + + +@samp{Force} and @samp{delay} are mainly intended for programs written in +functional style. The following examples should not be considered to +illustrate good programming style, but they illustrate the property that +only one value is computed for a promise, no matter how many times it is +forced. +@c the value of a promise is computed at most once. +@c [As pointed out by Marc Feeley, it may be computed more than once, +@c but as I observed we can at least insist that only one value be +@c used! -- Will] + + +@format +@t{(define count 0) +(define p + (delay (begin (set! count (+ count 1)) + (if (> count x) + count + (force p))))) +(define x 5) +p ==> @i{}a promise +(force p) ==> 6 +p ==> @i{}a promise, still +(begin (set! x 10) + (force p)) ==> 6 +} +@end format + + +Here is a possible implementation of @samp{delay} and @samp{force}. +Promises are implemented here as procedures of no arguments, +and @samp{force} simply calls its argument: + + +@format +@t{(define force + (lambda (object) + (object))) +} +@end format + + +We define the expression + + +@format +@t{(delay @r{<expression>}) +} +@end format + + +to have the same meaning as the procedure call + + +@format +@t{(make-promise (lambda () @r{<expression>}))@r{} +} +@end format + + +as follows + + +@format +@t{(define-syntax delay + (syntax-rules () + ((delay expression) + (make-promise (lambda () expression))))), +} +@end format + + +where @samp{make-promise} is defined as follows: + +@c \begin{scheme} +@c (define make-promise +@c (lambda (proc) +@c (let ((already-run? \schfalse) (result \schfalse)) +@c (lambda () +@c (cond ((not already-run?) +@c (set! result (proc)) +@c (set! already-run? \schtrue))) +@c result))))% +@c \end{scheme} + + +@format +@t{(define make-promise + (lambda (proc) + (let ((result-ready? #f) + (result #f)) + (lambda () + (if result-ready? + result + (let ((x (proc))) + (if result-ready? + result + (begin (set! result-ready? #t) + (set! result x) + result)))))))) +} +@end format + + + +@quotation +@emph{Rationale:} +A promise may refer to its own value, as in the last example above. +Forcing such a promise may cause the promise to be forced a second time +before the value of the first force has been computed. +This complicates the definition of @samp{make-promise}. +@end quotation + + +Various extensions to this semantics of @samp{delay} and @samp{force} +are supported in some implementations: + + + +@itemize @bullet + +@item +Calling @samp{force} on an object that is not a promise may simply +return the object. + +@item +It may be the case that there is no means by which a promise can be +operationally distinguished from its forced value. That is, expressions +like the following may evaluate to either @t{#t} or to @t{#f}, +depending on the implementation: + + +@format +@t{(eqv? (delay 1) 1) ==> @emph{unspecified} +(pair? (delay (cons 1 2))) ==> @emph{unspecified} +} +@end format + + +@item +Some implementations may implement ``implicit forcing,'' where +the value of a promise is forced by primitive procedures like @samp{cdr} +and @samp{+}: + + +@format +@t{(+ (delay (* 3 7)) 13) ==> 34 +} +@end format + + +@end itemize + +@end deffn + + +@deffn {procedure} call-with-current-continuation proc + + @var{Proc} must be a procedure of one +argument. The procedure @samp{call-with-current-continuation} packages +up the current continuation (see the rationale below) as an ``escape +procedure'' and passes it as an argument to +@cindex @w{escape procedure} +@var{proc}. The escape procedure is a Scheme procedure that, if it is +later called, will abandon whatever continuation is in effect at that later +time and will instead use the continuation that was in effect +when the escape procedure was created. Calling the escape procedure +may cause the invocation of @var{before} and @var{after} thunks installed using +@code{dynamic-wind}. +@vindex @w{dynamic-wind} + +The escape procedure accepts the same number of arguments as the continuation to +the original call to @t{call-with-current-continuation}. +Except for continuations created by the @samp{call-with-values} +procedure, all continuations take exactly one value. The +effect of passing no value or more than one value to continuations +that were not created by @t{call-with-values} is unspecified. + +The escape procedure that is passed to @var{proc} has +unlimited extent just like any other procedure in Scheme. It may be stored +in variables or data structures and may be called as many times as desired. + +The following examples show only the most common ways in which +@samp{call-with-current-continuation} is used. If all real uses were as +simple as these examples, there would be no need for a procedure with +the power of @samp{call-with-current-continuation}. + + +@format +@t{(call-with-current-continuation + (lambda (exit) + (for-each (lambda (x) + (if (negative? x) + (exit x))) + '(54 0 37 -3 245 19)) + #t)) ==> -3 + +(define list-length + (lambda (obj) + (call-with-current-continuation + (lambda (return) + (letrec ((r + (lambda (obj) + (cond ((null? obj) 0) + ((pair? obj) + (+ (r (cdr obj)) 1)) + (else (return #f)))))) + (r obj)))))) + +(list-length '(1 2 3 4)) ==> 4 + +(list-length '(a b . c)) ==> #f +} +@end format + + + +@quotation +@emph{Rationale:} + +A common use of @samp{call-with-current-continuation} is for +structured, non-local exits from loops or procedure bodies, but in fact +@samp{call-with-current-continuation} is extremely useful for implementing a +wide variety of advanced control structures. + +Whenever a Scheme expression is evaluated there is a +@dfn{continuation} wanting the result of the expression. The continuation +@cindex @w{continuation} +represents an entire (default) future for the computation. If the expression is +evaluated at top level, for example, then the continuation might take the +result, print it on the screen, prompt for the next input, evaluate it, and +so on forever. Most of the time the continuation includes actions +specified by user code, as in a continuation that will take the result, +multiply it by the value stored in a local variable, add seven, and give +the answer to the top level continuation to be printed. Normally these +ubiquitous continuations are hidden behind the scenes and programmers do not +think much about them. On rare occasions, however, a programmer may +need to deal with continuations explicitly. +@samp{Call-with-current-continuation} allows Scheme programmers to do +that by creating a procedure that acts just like the current +continuation. + +Most programming languages incorporate one or more special-purpose +escape constructs with names like @t{exit}, @w{@samp{return}}, or +even @t{goto}. In 1965, however, Peter Landin [Landin65] +invented a general purpose escape operator called the J-operator. John +Reynolds [Reynolds72] described a simpler but equally powerful +construct in 1972. The @samp{catch} special form described by Sussman +and Steele in the 1975 report on Scheme is exactly the same as +Reynolds's construct, though its name came from a less general construct +in MacLisp. Several Scheme implementors noticed that the full power of the +@code{catch} construct could be provided by a procedure instead of by a +@vindex @w{catch} +special syntactic construct, and the name +@samp{call-with-current-continuation} was coined in 1982. This name is +descriptive, but opinions differ on the merits of such a long name, and +some people use the name @code{call/cc} instead. +@vindex @w{call/cc} +@end quotation + + +@end deffn + + +@deffn {procedure} values obj @dots{} + +Delivers all of its arguments to its continuation. +Except for continuations created by the @code{call-with-values} +@vindex @w{call-with-values} +procedure, all continuations take exactly one value. +@t{Values} might be defined as follows: + +@format +@t{(define (values . things) + (call-with-current-continuation + (lambda (cont) (apply cont things)))) +} +@end format + + +@end deffn + + +@deffn {procedure} call-with-values producer consumer + +Calls its @var{producer} argument with no values and +a continuation that, when passed some values, calls the +@var{consumer} procedure with those values as arguments. +The continuation for the call to @var{consumer} is the +continuation of the call to @t{call-with-values}. + + +@format +@t{(call-with-values (lambda () (values 4 5)) + (lambda (a b) b)) + ==> 5 + +(call-with-values * -) ==> -1 +} +@end format + + +@end deffn + + +@deffn {procedure} dynamic-wind before thunk after + +Calls @var{thunk} without arguments, returning the result(s) of this call. +@var{Before} and @var{after} are called, also without arguments, as required +by the following rules (note that in the absence of calls to continuations +captured using @code{call-with-current-continuation} the three arguments are +@vindex @w{call-with-current-continuation} +called once each, in order). @var{Before} is called whenever execution +enters the dynamic extent of the call to @var{thunk} and @var{after} is called +whenever it exits that dynamic extent. The dynamic extent of a procedure +call is the period between when the call is initiated and when it +returns. In Scheme, because of @samp{call-with-current-continuation}, the +dynamic extent of a call may not be a single, connected time period. +It is defined as follows: + + +@itemize @bullet + +@item +The dynamic extent is entered when execution of the body of the +called procedure begins. + +@item +The dynamic extent is also entered when execution is not within +the dynamic extent and a continuation is invoked that was captured +(using @samp{call-with-current-continuation}) during the dynamic extent. + +@item +It is exited when the called procedure returns. + +@item +It is also exited when execution is within the dynamic extent and +a continuation is invoked that was captured while not within the +dynamic extent. + +@end itemize + + +If a second call to @samp{dynamic-wind} occurs within the dynamic extent of the +call to @var{thunk} and then a continuation is invoked in such a way that the +@var{after}s from these two invocations of @samp{dynamic-wind} are both to be +called, then the @var{after} associated with the second (inner) call to +@samp{dynamic-wind} is called first. + +If a second call to @samp{dynamic-wind} occurs within the dynamic extent of the +call to @var{thunk} and then a continuation is invoked in such a way that the +@var{before}s from these two invocations of @samp{dynamic-wind} are both to be +called, then the @var{before} associated with the first (outer) call to +@samp{dynamic-wind} is called first. + +If invoking a continuation requires calling the @var{before} from one call +to @samp{dynamic-wind} and the @var{after} from another, then the @var{after} +is called first. + +The effect of using a captured continuation to enter or exit the dynamic +extent of a call to @var{before} or @var{after} is undefined. + + +@format +@t{(let ((path '()) + (c #f)) + (let ((add (lambda (s) + (set! path (cons s path))))) + (dynamic-wind + (lambda () (add 'connect)) + (lambda () + (add (call-with-current-continuation + (lambda (c0) + (set! c c0) + 'talk1)))) + (lambda () (add 'disconnect))) + (if (< (length path) 4) + (c 'talk2) + (reverse path)))) + + ==> (connect talk1 disconnect + connect talk2 disconnect) +} +@end format + +@end deffn + +@node Eval, Input and output, Control features, Standard procedures +@section Eval + + + +@deffn {procedure} eval expression environment-specifier + +Evaluates @var{expression} in the specified environment and returns its value. +@var{Expression} must be a valid Scheme expression represented as data, +and @var{environment-specifier} must be a value returned by one of the +three procedures described below. +Implementations may extend @samp{eval} to allow non-expression programs +(definitions) as the first argument and to allow other +values as environments, with the restriction that @samp{eval} is not +allowed to create new bindings in the environments associated with +@samp{null-environment} or @samp{scheme-report-environment}. + + +@format +@t{(eval '(* 7 3) (scheme-report-environment 5)) + ==> 21 + +(let ((f (eval '(lambda (f x) (f x x)) + (null-environment 5)))) + (f + 10)) + ==> 20 +} +@end format + + +@end deffn + + +@deffn {procedure} scheme-report-environment version +@deffnx {procedure} null-environment version + +@var{Version} must be the exact integer @samp{5}, +corresponding to this revision of the Scheme report (the +Revised^5 Report on Scheme). +@samp{Scheme-report-environment} returns a specifier for an +environment that is empty except for all bindings defined in +this report that are either required or both optional and +supported by the implementation. @samp{Null-environment} returns +a specifier for an environment that is empty except for the +(syntactic) bindings for all syntactic keywords defined in +this report that are either required or both optional and +supported by the implementation. + +Other values of @var{version} can be used to specify environments +matching past revisions of this report, but their support is not +required. An implementation will signal an error if @var{version} +is neither @samp{5} nor another value supported by +the implementation. + +The effect of assigning (through the use of @samp{eval}) a variable +bound in a @samp{scheme-report-environment} +(for example @samp{car}) is unspecified. Thus the environments specified +by @samp{scheme-report-environment} may be immutable. + +@end deffn + + +@deffn {optional procedure} interaction-environment + +This procedure returns a specifier for the environment that +contains imple@-men@-ta@-tion-defined bindings, typically a superset of +those listed in the report. The intent is that this procedure +will return the environment in which the implementation would evaluate +expressions dynamically typed by the user. + +@end deffn + +@node Input and output, , Eval, Standard procedures +@section Input and output + +@menu +* Ports:: +* Input:: +* Output:: +* System interface:: +@end menu + + +@node Ports, Input, Input and output, Input and output +@subsection Ports + + + +Ports represent input and output devices. To Scheme, an input port is a +Scheme object that can deliver characters upon command, while an output port +is a Scheme object that can accept characters. +@cindex @w{port} + +@ignore todo +Haase: Mention that there are alternatives to files? +@end ignore + + + +@deffn {library procedure} call-with-input-file string proc +@deffnx {library procedure} call-with-output-file string proc + +@var{String} should be a string naming a file, and +@var{proc} should be a procedure that accepts one argument. +For @samp{call-with-input-file}, +the file should already exist; for +@samp{call-with-output-file}, +the effect is unspecified if the file +already exists. These procedures call @var{proc} with one argument: the +port obtained by opening the named file for input or output. If the +file cannot be opened, an error is signalled. If @var{proc} returns, +then the port is closed automatically and the value(s) yielded by the +@var{proc} is(are) returned. If @var{proc} does not return, then +the port will not be closed automatically unless it is possible to +prove that the port will never again be used for a read or write +operation. +@c Scheme +@c will not close the port unless it can prove that the port will never +@c again be used for a read or write operation. + + +@quotation +@emph{Rationale:} +Because Scheme's escape procedures have unlimited extent, it is +possible to escape from the current continuation but later to escape back in. +If implementations were permitted to close the port on any escape from the +current continuation, then it would be impossible to write portable code using +both @samp{call-with-current-continuation} and @samp{call-with-input-file} or +@samp{call-with-output-file}. +@ignore todo +Pitman wants more said here; maybe encourage users to call +@var{close-foo-port}; maybe talk about process switches (?). +@end ignore + +@end quotation + +@end deffn + + + +@deffn {procedure} input-port? obj +@deffnx {procedure} output-port? obj + +Returns @t{#t} if @var{obj} is an input port or output port +respectively, otherwise returns @t{#f}. + +@ignore todo +Won't necessarily return true after port is closed. +@end ignore + + +@end deffn + + + +@deffn {procedure} current-input-port +@deffnx {procedure} current-output-port + +Returns the current default input or output port. + +@end deffn + + + +@deffn {optional procedure} with-input-from-file string thunk +@deffnx {optional procedure} with-output-to-file string thunk + +@var{String} should be a string naming a file, and +@var{proc} should be a procedure of no arguments. +For @samp{with-input-from-file}, +the file should already exist; for +@samp{with-output-to-file}, +the effect is unspecified if the file +already exists. +The file is opened for input or output, an input or output port +connected to it is made the default value returned by +@samp{current-input-port} or @samp{current-output-port} +(and is used by @t{(read)}, @t{(write @var{obj})}, and so forth), +and the +@var{thunk} is called with no arguments. When the @var{thunk} returns, +the port is closed and the previous default is restored. +@samp{With-input-from-file} and @samp{with-output-to-file} return(s) the +value(s) yielded by @var{thunk}. +If an escape procedure +is used to escape from the continuation of these procedures, their +behavior is implementation dependent. + +@ignore todo +OK this with authors?? +@end ignore + +@c current continuation changes in such a way +@c as to make it doubtful that the \var{thunk} will ever return. + +@ignore todo +Freeman: +Throughout this section I wanted to see ``the value of @t{(current-input-port)}'' +instead of ``the value returned by @var{current-input-port}''. (Same for +@var{current-output-port}.) +@end ignore + + + +@end deffn + + + +@deffn {procedure} open-input-file filename + +Takes a string naming an existing file and returns an input port capable of +delivering characters from the file. If the file cannot be opened, an error is +signalled. + +@end deffn + + + +@deffn {procedure} open-output-file filename + +Takes a string naming an output file to be created and returns an output +port capable of writing characters to a new file by that name. If the file +cannot be opened, an error is signalled. If a file with the given name +already exists, the effect is unspecified. + +@end deffn + + + +@deffn {procedure} close-input-port port +@deffnx {procedure} close-output-port port + +Closes the file associated with @var{port}, rendering the @var{port} +incapable of delivering or accepting characters. +@ignore todo +But maybe a no-op +on some ports, e.g. terminals or editor buffers. +@end ignore + +These routines have no effect if the file has already been closed. +The value returned is unspecified. + +@ignore todo +Ramsdell: Some note is needed explaining why there are two +different close procedures. +@end ignore + + +@ignore todo +A port isn't necessarily still a port after it has been closed? +@end ignore + + +@end deffn + + +@node Input, Output, Ports, Input and output +@subsection Input + + + + +@noindent + @w{ } +@c ??? +@sp 5 +@ignore todo +The input routines have some things in common, maybe explain here. +@end ignore + + + +@deffn {library procedure} read +@deffnx {library procedure} read port + +@samp{Read} converts external representations of Scheme objects into the +objects themselves. That is, it is a parser for the nonterminal +<datum> (see sections @pxref{External representation} and +@pxref{Pairs and lists}). @samp{Read} returns the next +object parsable from the given input @var{port}, updating @var{port} to point to +the first character past the end of the external representation of the object. + +If an end of file is encountered in the input before any +characters are found that can begin an object, then an end of file +object is returned. +@ignore todo + +@end ignore + The port remains open, and further attempts +to read will also return an end of file object. If an end of file is +encountered after the beginning of an object's external representation, +but the external representation is incomplete and therefore not parsable, +an error is signalled. + +The @var{port} argument may be omitted, in which case it defaults to the +value returned by @samp{current-input-port}. It is an error to read from +a closed port. +@end deffn + + +@deffn {procedure} read-char +@deffnx {procedure} read-char port + +Returns the next character available from the input @var{port}, updating +the @var{port} to point to the following character. If no more characters +are available, an end of file object is returned. @var{Port} may be +omitted, in which case it defaults to the value returned by @samp{current-input-port}. + +@end deffn + + + +@deffn {procedure} peek-char +@deffnx {procedure} peek-char port + +Returns the next character available from the input @var{port}, +@emph{without} updating +the @var{port} to point to the following character. If no more characters +are available, an end of file object is returned. @var{Port} may be +omitted, in which case it defaults to the value returned by @samp{current-input-port}. + + +@quotation +@emph{Note:} +The value returned by a call to @samp{peek-char} is the same as the +value that would have been returned by a call to @samp{read-char} with the +same @var{port}. The only difference is that the very next call to +@samp{read-char} or @samp{peek-char} on that @var{port} will return the +value returned by the preceding call to @samp{peek-char}. In particular, a call +to @samp{peek-char} on an interactive port will hang waiting for input +whenever a call to @samp{read-char} would have hung. +@end quotation + + +@end deffn + + + +@deffn {procedure} eof-object? obj + +Returns @t{#t} if @var{obj} is an end of file object, otherwise returns +@t{#f}. The precise set of end of file objects will vary among +implementations, but in any case no end of file object will ever be an object +that can be read in using @samp{read}. + +@end deffn + + + +@deffn {procedure} char-ready? +@deffnx {procedure} char-ready? port + +Returns @t{#t} if a character is ready on the input @var{port} and +returns @t{#f} otherwise. If @samp{char-ready} returns @t{#t} then +the next @samp{read-char} operation on the given @var{port} is guaranteed +not to hang. If the @var{port} is at end of file then @samp{char-ready?} +returns @t{#t}. @var{Port} may be omitted, in which case it defaults to +the value returned by @samp{current-input-port}. + + +@quotation +@emph{Rationale:} +@samp{Char-ready?} exists to make it possible for a program to +accept characters from interactive ports without getting stuck waiting for +input. Any input editors associated with such ports must ensure that +characters whose existence has been asserted by @samp{char-ready?} cannot +be rubbed out. If @samp{char-ready?} were to return @t{#f} at end of +file, a port at end of file would be indistinguishable from an interactive +port that has no ready characters. +@end quotation + +@end deffn + + +@node Output, System interface, Input, Input and output +@subsection Output + + + +@c We've got to put something here to fix the indentation!! + +@noindent + @w{} +@sp 5 + + +@deffn {library procedure} write obj +@deffnx {library procedure} write obj port + +Writes a written representation of @var{obj} to the given @var{port}. Strings +that appear in the written representation are enclosed in doublequotes, and +within those strings backslash and doublequote characters are +escaped by backslashes. +Character objects are written using the @samp{#\} notation. +@samp{Write} returns an unspecified value. The +@var{port} argument may be omitted, in which case it defaults to the value +returned by @samp{current-output-port}. + +@end deffn + + + +@deffn {library procedure} display obj +@deffnx {library procedure} display obj port + +Writes a representation of @var{obj} to the given @var{port}. Strings +that appear in the written representation are not enclosed in +doublequotes, and no characters are escaped within those strings. Character +objects appear in the representation as if written by @samp{write-char} +instead of by @samp{write}. @samp{Display} returns an unspecified value. +The @var{port} argument may be omitted, in which case it defaults to the +value returned by @samp{current-output-port}. + + +@quotation +@emph{Rationale:} +@samp{Write} is intended +for producing mach@-ine-readable output and @samp{display} is for producing +human-readable output. Implementations that allow ``slashification'' +within symbols will probably want @samp{write} but not @samp{display} to +slashify funny characters in symbols. +@end quotation + +@end deffn + + + +@deffn {library procedure} newline +@deffnx {library procedure} newline port + +Writes an end of line to @var{port}. Exactly how this is done differs +from one operating system to another. Returns an unspecified value. +The @var{port} argument may be omitted, in which case it defaults to the +value returned by @samp{current-output-port}. + +@end deffn + + + +@deffn {procedure} write-char char +@deffnx {procedure} write-char char port + +Writes the character @var{char} (not an external representation of the +character) to the given @var{port} and returns an unspecified value. The +@var{port} argument may be omitted, in which case it defaults to the value +returned by @samp{current-output-port}. + +@end deffn + + +@node System interface, , Output, Input and output +@subsection System interface + + +Questions of system interface generally fall outside of the domain of this +report. However, the following operations are important enough to +deserve description here. + + + +@deffn {optional procedure} load filename + +@ignore todo +Fix +@end ignore + + +@c \domain{\var{Filename} should be a string naming an existing file +@c containing Scheme source code.} The {\cf load} procedure reads +@var{Filename} should be a string naming an existing file +containing Scheme source code. The @samp{load} procedure reads +expressions and definitions from the file and evaluates them +sequentially. It is unspecified whether the results of the expressions +are printed. The @samp{load} procedure does not affect the values +returned by @samp{current-input-port} and @samp{current-output-port}. +@samp{Load} returns an unspecified value. + + +@quotation +@emph{Rationale:} +For portability, @samp{load} must operate on source files. +Its operation on other kinds of files necessarily varies among +implementations. +@end quotation + +@end deffn + + + +@deffn {optional procedure} transcript-on filename +@deffnx {optional procedure} transcript-off + +@var{Filename} must be a string naming an output file to be +created. The effect of @samp{transcript-on} is to open the named file +for output, and to cause a transcript of subsequent interaction between +the user and the Scheme system to be written to the file. The +transcript is ended by a call to @samp{transcript-off}, which closes the +transcript file. Only one transcript may be in progress at any time, +though some implementations may relax this restriction. The values +returned by these procedures are unspecified. + +@c \begin{note} +@c These procedures are redundant in some systems, but +@c systems that need them should provide them. +@c \end{note} +@end deffn + +@page + +@c @include{syn} +@node Formal syntax and semantics, Notes, Standard procedures, top +@chapter Formal syntax and semantics + +@menu +* Formal syntax:: +* Formal semantics:: +* Derived expression type:: +@end menu + + + +This chapter provides formal descriptions of what has already been +described informally in previous chapters of this report. + +@ignore todo +Allow grammar to say that else clause needn't be last? +@end ignore + + + +@node Formal syntax, Formal semantics, Formal syntax and semantics, Formal syntax and semantics +@section Formal syntax + +@menu +* Lexical structure:: +* External representation:: +* Expression:: +* Quasiquotations:: +* Transformers:: +* Programs and definitions:: +@end menu + + + +This section provides a formal syntax for Scheme written in an extended +BNF. + +All spaces in the grammar are for legibility. Case is insignificant; +for example, @samp{#x1A} and @samp{#X1a} are equivalent. <empty> +stands for the empty string. + +The following extensions to BNF are used to make the description more +concise: <thing>* means zero or more occurrences of +<thing>; and <thing>+ means at least one +<thing>. + + +@node Lexical structure, External representation, Formal syntax, Formal syntax +@subsection Lexical structure + + +This section describes how individual tokens (identifiers, +@cindex @w{token} +numbers, etc.) are formed from sequences of characters. The following +sections describe how expressions and programs are formed from sequences +of tokens. + +<Intertoken space> may occur on either side of any token, but not +within a token. + +Tokens which require implicit termination (identifiers, numbers, +characters, and dot) may be terminated by any <delimiter>, but not +necessarily by anything else. + +The following five characters are reserved for future extensions to the +language: @t{[ ] @{ @} |} + + +@format +@t{<token> --> <identifier> | <boolean> | <number> +@cindex @w{identifier} + | <character> | <string> + | ( | ) | #( | @t{'} | @t{`} | , | ,@@ | @b{.} +<delimiter> --> <whitespace> | ( | ) | " | ; +<whitespace> --> <space or newline> +<comment> --> ; <@r{all subsequent characters up to a} + @r{line break>} +@cindex @w{comment} +<atmosphere> --> <whitespace> | <comment> +<intertoken space> --> <atmosphere>*} + +@end format + + + + + + +@c This is a kludge, but \multicolumn doesn't work in tabbing environments. + + + +@format +@t{<identifier> --> <initial> <subsequent>* + | <peculiar identifier> +<initial> --> <letter> | <special initial> +<letter> --> a | b | c | ... | z + +<special initial> --> ! | $ | % | & | * | / | : | < | = + | > | ? | ^ | _ | ~ +<subsequent> --> <initial> | <digit> + | <special subsequent> +<digit> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 +<special subsequent> --> + | - | .@: | @@ +<peculiar identifier> --> + | - | ... +<syntactic keyword> --> <expression keyword> +@cindex @w{syntactic keyword} +@cindex @w{keyword} + | else | => | define + | unquote | unquote-splicing +<expression keyword> --> quote | lambda | if + | set! | begin | cond | and | or | case + | let | let* | letrec | do | delay + | quasiquote + +@w{@samp{<variable> @result{} <}}@r{any <identifier> that isn't} +@cindex @w{variable} + @w{ @r{also a <syntactic keyword>>}} + +<boolean> --> #t | #f +<character> --> #\ <any character> + | #\ <character name> +<character name> --> space | newline + +<string> --> " <string element>* " +<string element> --> <any character other than " or \> + | \" | \\ } + +@end format + + + + + + + +@format +@t{<number> --> <num 2>| <num 8> + | <num 10>| <num 16> +} + +@end format + + + +The following rules for <num R>, <complex R>, <real +R>, <ureal R>, <uinteger R>, and <prefix R> +should be replicated for @w{R = 2, 8, 10,} +and 16. There are no rules for <decimal 2>, <decimal +8>, and <decimal 16>, which means that numbers containing +decimal points or exponents must be in decimal radix. +@ignore todo +Mark Meyer and David Bartley want to fix this. (What? -- Will) +@end ignore + + + +@format +@t{<num R> --> <prefix R> <complex R> +<complex R> --> <real R> | <real R> @@ <real R> + | <real R> + <ureal R> i | <real R> - <ureal R> i + | <real R> + i | <real R> - i + | + <ureal R> i | - <ureal R> i | + i | - i +<real R> --> <sign> <ureal R> +<ureal R> --> <uinteger R> + | <uinteger R> / <uinteger R> + | <decimal R> +<decimal 10> --> <uinteger 10> <suffix> + | . <digit 10>+ #* <suffix> + | <digit 10>+ . <digit 10>* #* <suffix> + | <digit 10>+ #+ . #* <suffix> +<uinteger R> --> <digit R>+ #* +<prefix R> --> <radix R> <exactness> + | <exactness> <radix R> +} + +@end format + + + + +@format +@t{<suffix> --> <empty> + | <exponent marker> <sign> <digit 10>+ +<exponent marker> --> e | s | f | d | l +<sign> --> <empty> | + | - +<exactness> --> <empty> | #i | #e +@vindex #e +@vindex #i +<radix 2> --> #b +@vindex #b +<radix 8> --> #o +@vindex #o +<radix 10> --> <empty> | #d +<radix 16> --> #x +@vindex #x +<digit 2> --> 0 | 1 +<digit 8> --> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 +<digit 10> --> <digit> +<digit 16> --> <digit 10> | a | b | c | d | e | f } + +@end format + + + +@ignore todo +Mark Meyer of TI sez, shouldn't we allow @t{1e3/2}? +@end ignore + + + +@node External representation, Expression, Lexical structure, Formal syntax +@subsection External representations + + + +<Datum> is what the @code{read} procedure (section @pxref{Input}) +@vindex @w{read} +successfully parses. Note that any string that parses as an +<ex@-pres@-sion> will also parse as a <datum>. + + +@format +@t{<datum> --> <simple datum> | <compound datum> +<simple datum> --> <boolean> | <number> + | <character> | <string> | <symbol> +<symbol> --> <identifier> +<compound datum> --> <list> | <vector> +<list> --> (<datum>*) | (<datum>+ .@: <datum>) + | <abbreviation> +<abbreviation> --> <abbrev prefix> <datum> +<abbrev prefix> --> ' | ` | , | ,@@ +<vector> --> #(<datum>*) } + +@end format + + + + +@node Expression, Quasiquotations, External representation, Formal syntax +@subsection Expressions + + + +@format +@t{<expression> --> <variable> + | <literal> + | <procedure call> + | <lambda expression> + | <conditional> + | <assignment> + | <derived expression> + | <macro use> + | <macro block> + +<literal> --> <quotation> | <self-evaluating> +<self-evaluating> --> <boolean> | <number> + | <character> | <string> +<quotation> --> '<datum> | (quote <datum>) +<procedure call> --> (<operator> <operand>*) +<operator> --> <expression> +<operand> --> <expression> + +<lambda expression> --> (lambda <formals> <body>) +<formals> --> (<variable>*) | <variable> + | (<variable>+ .@: <variable>) +<body> --> <definition>* <sequence> +<sequence> --> <command>* <expression> +<command> --> <expression> + +<conditional> --> (if <test> <consequent> <alternate>) +<test> --> <expression> +<consequent> --> <expression> +<alternate> --> <expression> | <empty> + +<assignment> --> (set! <variable> <expression>) + +<derived expression> --> + (cond <cond clause>+) + | (cond <cond clause>* (else <sequence>)) + | (case <expression> + <case clause>+) + | (case <expression> + <case clause>* + (else <sequence>)) + | (and <test>*) + | (or <test>*) + | (let (<binding spec>*) <body>) + | (let <variable> (<binding spec>*) <body>) + | (let* (<binding spec>*) <body>) + | (letrec (<binding spec>*) <body>) + | (begin <sequence>) + | (do (<iteration spec>*) + (<test> <do result>) + <command>*) + | (delay <expression>) + | <quasiquotation> + +<cond clause> --> (<test> <sequence>) + | (<test>) + | (<test> => <recipient>) +<recipient> --> <expression> +<case clause> --> ((<datum>*) <sequence>) +<binding spec> --> (<variable> <expression>) +<iteration spec> --> (<variable> <init> <step>) + | (<variable> <init>) +<init> --> <expression> +<step> --> <expression> +<do result> --> <sequence> | <empty> + +<macro use> --> (<keyword> <datum>*) +<keyword> --> <identifier> + +<macro block> --> + (let-syntax (<syntax spec>*) <body>) + | (letrec-syntax (<syntax spec>*) <body>) +<syntax spec> --> (<keyword> <transformer spec>) + +} + +@end format + + + +@node Quasiquotations, Transformers, Expression, Formal syntax +@subsection Quasiquotations + + +The following grammar for quasiquote expressions is not context-free. +It is presented as a recipe for generating an infinite number of +production rules. Imagine a copy of the following rules for D = 1, 2,3, @dots{}. D keeps track of the nesting depth. + + +@format +@t{<quasiquotation> --> <quasiquotation 1> +<qq template 0> --> <expression> +<quasiquotation D> --> `<qq template D> + | (quasiquote <qq template D>) +<qq template D> --> <simple datum> + | <list qq template D> + | <vector qq template D> + | <unquotation D> +<list qq template D> --> (<qq template or splice D>*) + | (<qq template or splice D>+ .@: <qq template D>) + | '<qq template D> + | <quasiquotation D+1> +<vector qq template D> --> #(<qq template or splice D>*) +<unquotation D> --> ,<qq template D-1> + | (unquote <qq template D-1>) +<qq template or splice D> --> <qq template D> + | <splicing unquotation D> +<splicing unquotation D> --> ,@@<qq template D-1> + | (unquote-splicing <qq template D-1>) } + +@end format + + + +In <quasiquotation>s, a <list qq template D> can sometimes +be confused with either an <un@-quota@-tion D> or a <splicing +un@-quo@-ta@-tion D>. The interpretation as an +<un@-quo@-ta@-tion> or <splicing +un@-quo@-ta@-tion D> takes precedence. + +@node Transformers, Programs and definitions, Quasiquotations, Formal syntax +@subsection Transformers + + + +@format +@t{<transformer spec> --> + (syntax-rules (<identifier>*) <syntax rule>*) +<syntax rule> --> (<pattern> <template>) +<pattern> --> <pattern identifier> + | (<pattern>*) + | (<pattern>+ . <pattern>) + | (<pattern>* <pattern> <ellipsis>) + | #(<pattern>*) + | #(<pattern>* <pattern> <ellipsis>) + | <pattern datum> +<pattern datum> --> <string> + | <character> + | <boolean> + | <number> +<template> --> <pattern identifier> + | (<template element>*) + | (<template element>+ . <template>) + | #(<template element>*) + | <template datum> +<template element> --> <template> + | <template> <ellipsis> +<template datum> --> <pattern datum> +<pattern identifier> --> <any identifier except @samp{...}> +<ellipsis> --> <the identifier @samp{...}> +} + +@end format + + + +@node Programs and definitions, , Transformers, Formal syntax +@subsection Programs and definitions + + + +@format +@t{<program> --> <command or definition>* +<command or definition> --> <command> + | <definition> + | <syntax definition> + | (begin <command or definition>+) +<definition> --> (define <variable> <expression>) + | (define (<variable> <def formals>) <body>) + | (begin <definition>*) +<def formals> --> <variable>* + | <variable>* .@: <variable> +<syntax definition> --> + (define-syntax <keyword> <transformer spec>) +} + +@end format + + + +@node Formal semantics, Derived expression type, Formal syntax, Formal syntax and semantics +@section Formal semantics + + +This section provides a formal denotational semantics for the primitive +expressions of Scheme and selected built-in procedures. The concepts +and notation used here are described in @sc{[Stoy77]}. + +@quotation +@emph{Note:} The formal semantics section was written in La@TeX{} which +is incompatible with @TeX{}info. See the Formal semantics section of +the original document from which this was derived. +@end quotation + + +@c @include{derive} +@node Derived expression type, , Formal semantics, Formal syntax and semantics +@section Derived expression types + + + +This section gives macro definitions for the derived expression types in +terms of the primitive expression types (literal, variable, call, @samp{lambda}, +@samp{if}, @samp{set!}). See section @ref{Control features} for a possible +definition of @samp{delay}. + + +@example + +(define-syntax cond + (syntax-rules (else =>) + ((cond (else result1 result2 ...)) + (begin result1 result2 ...)) + ((cond (test => result)) + (let ((temp test)) + (if temp (result temp)))) + ((cond (test => result) clause1 clause2 ...) + (let ((temp test)) + (if temp + (result temp) + (cond clause1 clause2 ...)))) + ((cond (test)) test) + ((cond (test) clause1 clause2 ...) + (let ((temp test)) + (if temp + temp + (cond clause1 clause2 ...)))) + ((cond (test result1 result2 ...)) + (if test (begin result1 result2 ...))) + ((cond (test result1 result2 ...) + clause1 clause2 ...) + (if test + (begin result1 result2 ...) + (cond clause1 clause2 ...))))) + +@end example + + + +@example + +(define-syntax case + (syntax-rules (else) + ((case (key ...) + clauses ...) + (let ((atom-key (key ...))) + (case atom-key clauses ...))) + ((case key + (else result1 result2 ...)) + (begin result1 result2 ...)) + ((case key + ((atoms ...) result1 result2 ...)) + (if (memv key '(atoms ...)) + (begin result1 result2 ...))) + ((case key + ((atoms ...) result1 result2 ...) + clause clauses ...) + (if (memv key '(atoms ...)) + (begin result1 result2 ...) + (case key clause clauses ...))))) + +@end example + + + +@example + +(define-syntax and + (syntax-rules () + ((and) #t) + ((and test) test) + ((and test1 test2 ...) + (if test1 (and test2 ...) #f)))) + +@end example + + + +@example + +(define-syntax or + (syntax-rules () + ((or) #f) + ((or test) test) + ((or test1 test2 ...) + (let ((x test1)) + (if x x (or test2 ...)))))) + +@end example + + + +@example + +(define-syntax let + (syntax-rules () + ((let ((name val) ...) body1 body2 ...) + ((lambda (name ...) body1 body2 ...) + val ...)) + ((let tag ((name val) ...) body1 body2 ...) + ((letrec ((tag (lambda (name ...) + body1 body2 ...))) + tag) + val ...)))) + +@end example + + + +@example + +(define-syntax let* + (syntax-rules () + ((let* () body1 body2 ...) + (let () body1 body2 ...)) + ((let* ((name1 val1) (name2 val2) ...) + body1 body2 ...) + (let ((name1 val1)) + (let* ((name2 val2) ...) + body1 body2 ...))))) + +@end example + + +The following @samp{letrec} macro uses the symbol @samp{<undefined>} +in place of an expression which returns something that when stored in +a location makes it an error to try to obtain the value stored in the +location (no such expression is defined in Scheme). +A trick is used to generate the temporary names needed to avoid +specifying the order in which the values are evaluated. +This could also be accomplished by using an auxiliary macro. + + +@example + +(define-syntax letrec + (syntax-rules () + ((letrec ((var1 init1) ...) body ...) + (letrec "generate temp names" + (var1 ...) + () + ((var1 init1) ...) + body ...)) + ((letrec "generate temp names" + () + (temp1 ...) + ((var1 init1) ...) + body ...) + (let ((var1 <undefined>) ...) + (let ((temp1 init1) ...) + (set! var1 temp1) + ... + body ...))) + ((letrec "generate temp names" + (x y ...) + (temp ...) + ((var1 init1) ...) + body ...) + (letrec "generate temp names" + (y ...) + (newtemp temp ...) + ((var1 init1) ...) + body ...)))) + +@end example + + + +@example + +(define-syntax begin + (syntax-rules () + ((begin exp ...) + ((lambda () exp ...))))) + +@end example + + +The following alternative expansion for @samp{begin} does not make use of +the ability to write more than one expression in the body of a lambda +expression. In any case, note that these rules apply only if the body +of the @samp{begin} contains no definitions. + + +@example + +(define-syntax begin + (syntax-rules () + ((begin exp) + exp) + ((begin exp1 exp2 ...) + (let ((x exp1)) + (begin exp2 ...))))) + +@end example + + +The following definition +of @samp{do} uses a trick to expand the variable clauses. +As with @samp{letrec} above, an auxiliary macro would also work. +The expression @samp{(if #f #f)} is used to obtain an unspecific +value. + + +@example + +(define-syntax do + (syntax-rules () + ((do ((var init step ...) ...) + (test expr ...) + command ...) + (letrec + ((loop + (lambda (var ...) + (if test + (begin + (if #f #f) + expr ...) + (begin + command + ... + (loop (do "step" var step ...) + ...)))))) + (loop init ...))) + ((do "step" x) + x) + ((do "step" x y) + y))) + +@end example + + +@c `a = Q_1[a] +@c `(a b c ... . z) = `(a . (b c ...)) +@c `(a . b) = (append Q*_0[a] `b) +@c `(a) = Q*_0[a] +@c Q*_0[a] = (list 'a) +@c Q*_0[,a] = (list a) +@c Q*_0[,@a] = a +@c Q*_0[`a] = (list 'quasiquote Q*_1[a]) +@c `#(a b ...) = (list->vector `(a b ...)) +@c ugh. + +@page + +@c @include{notes} +@node Notes, Additional material, Formal syntax and semantics, top +@unnumbered Notes + +@menu +* Language changes:: +@end menu + + + +@ignore todo +Perhaps this section should be made to disappear. +Can these remarks be moved somewhere else? +@end ignore + + +@node Language changes, , Notes, Notes +@unnumberedsec Language changes + + + +This section enumerates the changes that have been made to Scheme since +the ``Revised^4 report'' [R4RS] was published. + + + +@itemize @bullet + + +@item +The report is now a superset of the IEEE standard for Scheme +[IEEEScheme]: implementations that conform to the report will +also conform to the standard. This required the following changes: + + +@itemize @bullet + + +@item +The empty list is now required to count as true. + +@item +The classification of features as essential or inessential has been +removed. There are now three classes of built-in procedures: primitive, +library, and optional. The optional procedures are @samp{load}, +@samp{with-input-from-file}, @samp{with-output-to-file}, +@samp{transcript-on}, @samp{transcript-off}, and +@samp{interaction-environment}, +and @samp{-} and @samp{/} with more than two arguments. +None of these are in the IEEE standard. + +@item +Programs are allowed to redefine built-in procedures. Doing so +will not change the behavior of other built-in procedures. + +@end itemize + + +@item +@emph{Port} has been added to the list of disjoint types. + +@item +The macro appendix has been removed. High-level macros are now part +of the main body of the report. The rewrite rules for derived expressions +have been replaced with macro definitions. There are no reserved identifiers. + +@item +@samp{Syntax-rules} now allows vector patterns. + +@item +Multiple-value returns, @samp{eval}, and @samp{dynamic-wind} have +been added. + +@item +The calls that are required to be implemented in a properly tail-recursive +fashion are defined explicitly. + +@item +`@samp{@@}' can be used within identifiers. `@samp{|}' is reserved +for possible future extensions. + + +@end itemize + + +@c %R4%% +@c \subsection*{Keywords as variable names} + +@c Some implementations allow arbitrary syntactic +@c keywords \index{keyword}\index{syntactic keyword}to be used as variable +@c names, instead of reserving them, as this report would have +@c it.\index{variable} But this creates ambiguities in the interpretation +@c of expressions: for example, in the following, it's not clear whether +@c the expression {\tt (if 1 2 3)} should be treated as a procedure call or +@c as a conditional. + +@c \begin{scheme} +@c (define if list) +@c (if 1 2 3) \ev 2 {\em{}or} (1 2 3)% +@c \end{scheme} + +@c These ambiguities are usually resolved in some consistent way within any +@c given implementation, but no particular treatment stands out as being +@c clearly superior to any other, so these situations were excluded for the +@c purposes of this report. + +@c %R4%% +@c \subsection*{Macros} + +@c Scheme does not have any standard facility for defining new kinds of +@c expressions.\index{macros} + +@c \vest The ability to alter the syntax of the language creates +@c numerous problems. All current implementations of Scheme have macro +@c facilities that solve those problems to one degree or another, but the +@c solutions are quite different and it isn't clear at this time which +@c solution is best, or indeed whether any of the solutions are truly +@c adequate. Rather than standardize, we are encouraging implementations +@c to continue to experiment with different solutions. + +@c \vest The main problems with traditional macros are: They must be +@c defined to the system before any code using them is loaded; this is a +@c common source of obscure bugs. They are usually global; macros can be +@c made to follow lexical scope rules \todo{flushed: ``as in Common +@c Lisp's {\tt macrolet}''; OK?}, but many people find the resulting scope rules +@c confusing. Unless they are written very carefully, macros are +@c vulnerable to inadvertent capture of free variables; to get around this, +@c for example, macros may have to generate code in which procedure values +@c appear as quoted constants. There is a similar problem with syntactic +@c keywords if the keywords of special forms are not reserved. If keywords +@c are reserved, then either macros introduce new reserved words, +@c invalidating old code, or else special forms defined by the programmer +@c do not have the same status as special forms defined by the system. + +@c \todo{Refer to Pitman's special forms paper.} +@c \todo{Pitman sez: Discuss importance of having a small number of special forms +@c so that programs can inspect each other.} + +@ignore todo +Move cwcc history back here? --- Andy Cromarty is concerned about +confusion over who the audience is. +@end ignore + + +@ignore todo +Cromarty: +23. NOTES, p.35ff.: This material should stay somehow. We need to + make it clear that R^3 Scheme is not being touted as Yet Another + Ultimate Solution To The Programming Language Problem, but rather + as a snapshot of a *process* of good design, for which not all + answers have yet been found. We also ought to use the opportunity + for publicity afforded us by SIGPLAN to advertise some of the thorny + unsolved problems that need further research, and encourage + language designers to work on them. +@end ignore + + +@c @include{repository} +@node Additional material, Example, Notes, top +@unnumbered Additional material + + +The Internet Scheme Repository at + +@center +@center @url{http://www.cs.indiana.edu/scheme-repository/} +@center + +contains an extensive Scheme bibliography, as well as papers, +programs, implementations, and other material related to Scheme. + +@page + +@c @include{example} + +@node Example, Bibliography, Additional material, top +@unnumbered Example + +@c -*- Mode: Lisp; Package: SCHEME; Syntax: Common-lisp -*- + + +@samp{Integrate-system} integrates the system + + +@center y_k^^ = f_k(y_1, y_2, @dots{}, y_n), k = 1, @dots{}, n + +of differential equations with the method of Runge-Kutta. + +The parameter @t{system-derivative} is a function that takes a system +state (a vector of values for the state variables y_1, @dots{}, y_n) +and produces a system derivative (the values y_1^^, @dots{},y_n^^). The parameter @t{initial-state} provides an initial +system state, and @t{h} is an initial guess for the length of the +integration step. + +The value returned by @samp{integrate-system} is an infinite stream of +system states. + + +@example + +(define integrate-system + (lambda (system-derivative initial-state h) + (let ((next (runge-kutta-4 system-derivative h))) + (letrec ((states + (cons initial-state + (delay (map-streams next + states))))) + states)))) + +@end example + + +@samp{Runge-Kutta-4} takes a function, @t{f}, that produces a +system derivative from a system state. @samp{Runge-Kutta-4} +produces a function that takes a system state and +produces a new system state. + + +@example + +(define runge-kutta-4 + (lambda (f h) + (let ((*h (scale-vector h)) + (*2 (scale-vector 2)) + (*1/2 (scale-vector (/ 1 2))) + (*1/6 (scale-vector (/ 1 6)))) + (lambda (y) + ;; y @r{}is a system state + (let* ((k0 (*h (f y))) + (k1 (*h (f (add-vectors y (*1/2 k0))))) + (k2 (*h (f (add-vectors y (*1/2 k1))))) + (k3 (*h (f (add-vectors y k2))))) + (add-vectors y + (*1/6 (add-vectors k0 + (*2 k1) + (*2 k2) + k3)))))))) +@c |--------------------------------------------------| + +(define elementwise + (lambda (f) + (lambda vectors + (generate-vector + (vector-length (car vectors)) + (lambda (i) + (apply f + (map (lambda (v) (vector-ref v i)) + vectors))))))) + +@c |--------------------------------------------------| +(define generate-vector + (lambda (size proc) + (let ((ans (make-vector size))) + (letrec ((loop + (lambda (i) + (cond ((= i size) ans) + (else + (vector-set! ans i (proc i)) + (loop (+ i 1))))))) + (loop 0))))) + +(define add-vectors (elementwise +)) + +(define scale-vector + (lambda (s) + (elementwise (lambda (x) (* x s))))) + +@end example + + +@samp{Map-streams} is analogous to @samp{map}: it applies its first +argument (a procedure) to all the elements of its second argument (a +stream). + + +@example + +(define map-streams + (lambda (f s) + (cons (f (head s)) + (delay (map-streams f (tail s)))))) + +@end example + + +Infinite streams are implemented as pairs whose car holds the first +element of the stream and whose cdr holds a promise to deliver the rest +of the stream. + + +@example + +(define head car) +(define tail + (lambda (stream) (force (cdr stream)))) + +@end example + + +@sp 6 +The following illustrates the use of @samp{integrate-system} in +integrating the system + + +@center C dv_C / dt = -i_L - v_C / R + + + +@center L di_L / dt = v_C + +which models a damped oscillator. + + +@example + +(define damped-oscillator + (lambda (R L C) + (lambda (state) + (let ((Vc (vector-ref state 0)) + (Il (vector-ref state 1))) + (vector (- 0 (+ (/ Vc (* R C)) (/ Il C))) + (/ Vc L)))))) + +(define the-states + (integrate-system + (damped-oscillator 10000 1000 .001) + '#(1 0) + .01)) + +@end example + + +@ignore todo +Show some output? +@end ignore + + +@c (letrec ((loop (lambda (s) +@c (newline) +@c (write (head s)) +@c (loop (tail s))))) +@c (loop the-states)) + +@c #(1 0) +@c #(0.99895054 9.994835e-6) +@c #(0.99780226 1.9978681e-5) +@c #(0.9965554 2.9950552e-5) +@c #(0.9952102 3.990946e-5) +@c #(0.99376684 4.985443e-5) +@c #(0.99222565 5.9784474e-5) +@c #(0.9905868 6.969862e-5) +@c #(0.9888506 7.9595884e-5) +@c #(0.9870173 8.94753e-5) + +@page + +@c \newpage % Put bib on it's own page (it's just one) +@c \twocolumn[\vspace{-.18in}]% Last bib item was on a page by itself. +@c \renewcommand{\bibname}{References} +@c @include{bib} + +@c My reference for proper reference format is: +@c Mary-Claire van Leunen. +@c {\em A Handbook for Scholars.} +@c Knopf, 1978. +@c I think the references list would look better in ``open'' format, +@c i.e. with the three blocks for each entry appearing on separate +@c lines. I used the compressed format for SIGPLAN in the interest of +@c space. In open format, when a block runs over one line, +@c continuation lines should be indented; this could probably be done +@c using some flavor of latex list environment. Maybe the right thing +@c to do in the long run would be to convert to Bibtex, which probably +@c does the right thing, since it was implemented by one of van +@c Leunen's colleagues at DEC SRC. +@c -- Jonathan + +@c I tried to follow Jonathan's format, insofar as I understood it. +@c I tried to order entries lexicographically by authors (with singly +@c authored papers first), then by date. +@c In some cases I replaced a technical report or conference paper +@c by a subsequent journal article, but I think there are several +@c more such replacements that ought to be made. +@c -- Will, 1991. + +@c This is just a personal remark on your question on the RRRS: +@c The language CUCH (Curry-Church) was implemented by 1964 and +@c is a practical version of the lambda-calculus (call-by-name). +@c One reference you may find in Formal Language Description Languages +@c for Computer Programming T.~B.~Steele, 1965 (or so). +@c -- Matthias Felleisen + +@c Rather than try to keep the bibliography up-to-date, which is hopeless +@c given the time between updates, I replaced the bulk of the references +@c with a pointer to the Scheme Repository. Ozan Yigit's bibliography in +@c the repository is a superset of the R4RS one. +@c The bibliography now contains only items referenced within the report. +@c -- Richard, 1996. + +@node Bibliography, Index, Example, top +@unnumbered Bibliography + + +@itemize @bullet +@c 999 + + +@item [SICP] +@pindex SICP +Harold Abelson and Gerald Jay Sussman with Julie Sussman. +@emph{Structure and Interpretation of Computer Programs, second edition.} +MIT Press, Cambridge, 1996. + +@item [Bawden88] +@c new +Alan Bawden and Jonathan Rees. +@pindex Bawden88 +Syntactic closures. +In @emph{Proceedings of the 1988 ACM Symposium on Lisp and + Functional Programming}, pages 86--95. + +@item [howtoprint] +@pindex howtoprint +Robert G. Burger and R. Kent Dybvig. +Printing floating-point numbers quickly and accurately. +In @emph{Proceedings of the ACM SIGPLAN '96 Conference + on Programming Language Design and Implementation}, pages 108--116. + +@item [RRRS] +@pindex RRRS +William Clinger, editor. +The revised revised report on Scheme, or an uncommon Lisp. +MIT Artificial Intelligence Memo 848, August 1985. +Also published as Computer Science Department Technical Report 174, + Indiana University, June 1985. + +@item [howtoread] +@c new +William Clinger. +@pindex howtoread +How to read floating point numbers accurately. +In @emph{Proceedings of the ACM SIGPLAN '90 Conference + on Programming Language Design and Implementation}, pages 92--101. +Proceedings published as @emph{SIGPLAN Notices} 25(6), June 1990. + +@item [R4RS] +@pindex R4RS +William Clinger and Jonathan Rees, editors. +The revised^4 report on the algorithmic language Scheme. +In @emph{ACM Lisp Pointers} 4(3), pages 1--55, 1991. + +@item [macrosthatwork] +@c new +William Clinger and Jonathan Rees. +@pindex macrosthatwork +Macros that work. +In @emph{Proceedings of the 1991 ACM Conference on Principles of + Programming Languages}, pages 155--162. + +@item [propertailrecursion] +@c new +William Clinger. +@pindex propertailrecursion +Proper Tail Recursion and Space Efficiency. +To appear in @emph{Proceedings of the 1998 ACM Conference on Programming + Language Design and Implementation}, June 1998. + +@item [syntacticabstraction] +@pindex syntacticabstraction +R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. +Syntactic abstraction in Scheme. +@emph{Lisp and Symbolic Computation} 5(4):295--326, 1993. + +@item [Scheme311] +@pindex Scheme311 +Carol Fessenden, William Clinger, Daniel P. Friedman, and Christopher Haynes. +Scheme 311 version 4 reference manual. +Indiana University Computer Science Technical Report 137, February 1983. +Superseded by [Scheme84]. + +@item [Scheme84] +@pindex Scheme84 +D. Friedman, C. Haynes, E. Kohlbecker, and M. Wand. +Scheme 84 interim reference manual. +Indiana University Computer Science Technical Report 153, January 1985. + +@item [IEEE] +@pindex IEEE +@emph{IEEE Standard 754-1985. IEEE Standard for Binary Floating-Point +Arithmetic.} IEEE, New York, 1985. + +@item [IEEEScheme] +@pindex IEEEScheme +@emph{IEEE Standard 1178-1990. IEEE Standard for the Scheme + Programming Language.} IEEE, New York, 1991. + +@item [Kohlbecker86] +@pindex Kohlbecker86 +Eugene E. Kohlbecker Jr. +@emph{Syntactic Extensions in the Programming Language Lisp.} +PhD thesis, Indiana University, August 1986. + +@item [hygienic] +@pindex hygienic +Eugene E. Kohlbecker Jr., Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. +Hygienic macro expansion. +In @emph{Proceedings of the 1986 ACM Conference on Lisp + and Functional Programming}, pages 151--161. + +@item [Landin65] +@pindex Landin65 +Peter Landin. +A correspondence between Algol 60 and Church's lambda notation: Part I. +@emph{Communications of the ACM} 8(2):89--101, February 1965. + +@item [MITScheme] +@pindex MITScheme +MIT Department of Electrical Engineering and Computer Science. +Scheme manual, seventh edition. +September 1984. + +@item [Naur63] +@pindex Naur63 +Peter Naur et al. +Revised report on the algorithmic language Algol 60. +@emph{Communications of the ACM} 6(1):1--17, January 1963. + +@item [Penfield81] +@pindex Penfield81 +Paul Penfield, Jr. +Principal values and branch cuts in complex APL. +In @emph{APL '81 Conference Proceedings,} pages 248--256. +ACM SIGAPL, San Francisco, September 1981. +Proceedings published as @emph{APL Quote Quad} 12(1), ACM, September 1981. + +@item [Pitman83] +@pindex Pitman83 +Kent M. Pitman. +The revised MacLisp manual (Saturday evening edition). +MIT Laboratory for Computer Science Technical Report 295, May 1983. + +@item [Rees82] +@pindex Rees82 +Jonathan A. Rees and Norman I. Adams IV. +T: A dialect of Lisp or, lambda: The ultimate software tool. +In @emph{Conference Record of the 1982 ACM Symposium on Lisp and + Functional Programming}, pages 114--122. + +@item [Rees84] +@pindex Rees84 +Jonathan A. Rees, Norman I. Adams IV, and James R. Meehan. +The T manual, fourth edition. +Yale University Computer Science Department, January 1984. + +@item [R3RS] +@pindex R3RS +Jonathan Rees and William Clinger, editors. +The revised^3 report on the algorithmic language Scheme. +In @emph{ACM SIGPLAN Notices} 21(12), pages 37--79, December 1986. + +@item [Reynolds72] +@pindex Reynolds72 +John Reynolds. +Definitional interpreters for higher order programming languages. +In @emph{ACM Conference Proceedings}, pages 717--740. +ACM, +@ignore todo +month? +@end ignore + 1972. + +@item [Scheme78] +@pindex Scheme78 +Guy Lewis Steele Jr. and Gerald Jay Sussman. +The revised report on Scheme, a dialect of Lisp. +MIT Artificial Intelligence Memo 452, January 1978. + +@item [Rabbit] +@pindex Rabbit +Guy Lewis Steele Jr. +Rabbit: a compiler for Scheme. +MIT Artificial Intelligence Laboratory Technical Report 474, May 1978. + +@item [CLtL] +@pindex CLtL +Guy Lewis Steele Jr. +@emph{Common Lisp: The Language, second edition.} +Digital Press, Burlington MA, 1990. + +@item [Scheme75] +@pindex Scheme75 +Gerald Jay Sussman and Guy Lewis Steele Jr. +Scheme: an interpreter for extended lambda calculus. +MIT Artificial Intelligence Memo 349, December 1975. + +@item [Stoy77] +@pindex Stoy77 +Joseph E. Stoy. +@emph{Denotational Semantics: The Scott-Strachey Approach to + Programming Language Theory.} +MIT Press, Cambridge, 1977. + +@item [TImanual85] +@pindex TImanual85 +Texas Instruments, Inc. +TI Scheme Language Reference Manual. +Preliminary version 1.0, November 1985. + +@end itemize + + + + +@page + + +@c Adjustment to avoid having the last index entry on a page by itself. +@c \addtolength{\baselineskip}{-0.1pt} + +@node Index, , Bibliography, top +@unnumbered Alphabetic index of definitions of concepts, keywords, and procedures + + + +The principal entry for each term, procedure, or keyword is listed +first, separated from the other entries by a semicolon. + +@sp 6 + +@unnumberedsec Concepts +@printindex cp +@page +@unnumberedsec Procedures +@printindex fn + +@ifinfo +@unnumberedsec References +@printindex pg +@end ifinfo + + +@contents +@bye |