diff options
Diffstat (limited to 'doc/r5rs/r5rs.texi')
-rw-r--r-- | doc/r5rs/r5rs.texi | 8538 |
1 files changed, 0 insertions, 8538 deletions
diff --git a/doc/r5rs/r5rs.texi b/doc/r5rs/r5rs.texi deleted file mode 100644 index a33771190..000000000 --- a/doc/r5rs/r5rs.texi +++ /dev/null @@ -1,8538 +0,0 @@ -\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 |