commit bb2830195ddad6a7330cc3e3984d84c2087d23bc
parent b2e1edd23fbfb3acb454e9c4310676c602a1fee0
Author: Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
Date: Mon, 5 Feb 2024 15:49:51 -0500
Basic concepts: Reflow paragraphs.
Diffstat:
1 file changed, 176 insertions(+), 162 deletions(-)
diff --git a/doc/r7rs-small/basic-concepts.texinfo b/doc/r7rs-small/basic-concepts.texinfo
@@ -13,41 +13,44 @@
@node Variables syntactic keywords and regions
@section Variables, syntactic keywords, and regions
-An identifier can name either a type of syntax or a location where a value
-can be stored. An identifier that names a type of syntax is called a
-@dfn{syntactic keyword} and is said to be @dfn{bound} to a transformer for
-that syntax. An identifier that names a location is called a @dfn{variable}
-and is said to be @dfn{bound} to that location. The set of all visible
-bindings in effect at some point in a program is known as the
-@dfn{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.
-
-Certain expression types are used to create new kinds of syntax and to 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 @dfn{binding constructs}. Those that bind syntactic
-keywords are listed in @ref{Macros}. The most fundamental of the variable
-binding constructs is the @code{lambda} expression, because all other
-variable binding constructs (except top-level bindings) can be explained in
-terms of @code{lambda} expressions. The other variable binding constructs
-are @code{let}, @code{let*}, @code{letrec}, @code{letrec*},
-@code{let-values}, @code{let*-values}, and @code{do} expressions (see
-@ref{Procedures}, @ref{Binding constructs}, and @ref{Iteration}).
-
-Scheme is a 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 the binding is visible. The region is determined by the
-particular binding construct that establishes the binding; if the binding is
-established by a @code{lambda} expression, for example, then its region is
-the entire @code{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 global environment, if any (@ref{Expressions} and @ref{Standard procedures}); if there is no binding
-for the identifier, it is said to be @dfn{unbound}.
+An identifier can name either a type of syntax or a location where
+a value can be stored. An identifier that names a type of syntax is
+called a @dfn{syntactic keyword} and is said to be @dfn{bound} to
+a transformer for that syntax. An identifier that names a location
+is called a @dfn{variable} and is said to be @dfn{bound} to that
+location. The set of all visible bindings in effect at some point
+in a program is known as the @dfn{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.
+
+Certain expression types are used to create new kinds of syntax and to
+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 @dfn{binding constructs}. Those
+that bind syntactic keywords are listed in @ref{Macros}. The most
+fundamental of the variable binding constructs is the @code{lambda}
+expression, because all other variable binding constructs (except
+top-level bindings) can be explained in terms of @code{lambda}
+expressions. The other variable binding constructs are @code{let},
+@code{let*}, @code{letrec}, @code{letrec*}, @code{let-values},
+@code{let*-values}, and @code{do} expressions (see @ref{Procedures},
+@ref{Binding constructs}, and @ref{Iteration}).
+
+Scheme is a 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 the binding is visible. The region
+is determined by the particular binding construct that establishes
+the binding; if the binding is established by a @code{lambda}
+expression, for example, then its region is the entire @code{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 global environment, if any (@ref{Expressions} and
+@ref{Standard procedures}); if there is no binding for the identifier,
+it is said to be @dfn{unbound}.
@node Disjointness of types
@section Disjointness of types
@@ -102,25 +105,27 @@ These predicates define the types @dfn{boolean}, @dfn{bytevector},
@dfn{pair}, @dfn{port}, @dfn{procedure}, @dfn{string}, @dfn{symbol},
@dfn{vector}, and all record types.
-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 @ref{Booleans},
-all values count as true in such a test except for @code{#f}. This
-report uses the word ``true'' to refer to any Scheme value except @code{#f},
-and the word ``false'' to refer to @code{#f}.
+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 @ref{Booleans}, all values count as true in such a test except for
+@code{#f}. This report uses the word ``true'' to refer to any Scheme
+value except @code{#f}, and the word ``false'' to refer to @code{#f}.
@node External representations basic
@section External representations (basic)
An important concept in Scheme (and Lisp) is that of the @dfn{external
-representation} of an object as a sequence of characters. For example, an
-external representation of the integer 28 is the sequence of characters
-@samp{28}, and an external representation of a list consisting of the
-integers 8 and 13 is the sequence of characters @samp{(8 13)}.
+representation} of an object as a sequence of characters. For example,
+an external representation of the integer 28 is the sequence of
+characters @samp{28}, and an external representation of a list
+consisting of the integers 8 and 13 is the sequence of characters
+@samp{(8 13)}.
The external representation of an object is not necessarily unique. The
-integer 28 also has representations @samp{#e28.000} and @samp{#x1c}, and the
-list in the previous paragraph also has the representations @samp{( 08 13 )}
-and @samp{(8 . (13 . ()))} (see @ref{Pairs and lists}).
+integer 28 also has representations @samp{#e28.000} and @samp{#x1c},
+and the list in the previous paragraph also has the representations
+@samp{( 08 13 )} and @samp{(8 . (13 . ()))} (see @ref{Pairs and
+lists}).
Many objects have standard external representations, but some, such as
procedures, do not have standard representations (although particular
@@ -130,116 +135,123 @@ An external representation can be written in a program to obtain the
corresponding object (see @code{quote}, @ref{Literal expressions}).
External representations can also be used for input and output. The
-procedure @code{read} (@ref{Input}) parses external representations, and
-the procedure @code{write} (@ref{Output}) generates them. Together, they
-provide an elegant and powerful input/output facility.
-
-Note that the sequence of characters @samp{(+ 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
-@code{+} 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 is not
-always 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).
+procedure @code{read} (@ref{Input}) parses external representations,
+and the procedure @code{write} (@ref{Output}) generates them. Together,
+they provide an elegant and powerful input/output facility.
+
+Note that the sequence of characters @samp{(+ 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 @code{+} 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 is not always 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 @ref{Standard procedures}.
+accompanies the description of the primitives for manipulating the
+objects in the appropriate sections of @ref{Standard procedures}.
@node Storage model
@section Storage model
Variables and objects such as pairs, strings, vectors, and bytevectors
-implicitly denote locations or sequences of locations. A string, for
-example, denotes as many locations as there are characters in the string. A
-new value can be stored into one of these locations using the
-@code{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 @code{car}, @code{vector-ref}, or @code{string-ref}, is equivalent
-in the sense of @code{eqv?} (@ref{Equivalence predicates}) 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 newly 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. Notwithstanding this, it is
-understood that the empty list cannot be newly allocated, because it is a
-unique object. It is also understood that empty strings, empty vectors, and
-empty bytevectors, which contain no locations, may or may not be newly
-allocated.
-
-Every object that denotes locations is either mutable or immutable. Literal
-constants, the strings returned by @code{symbol->string}, and possibly the
-environment returned by @code{scheme-report-environment} are immutable
-objects. All objects 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.
-
-These locations are to be understood as conceptual, not physical. Hence,
-they do not necessarily correspond to memory addresses, and even if they do,
-the memory address might not be constant.
+implicitly denote locations or sequences of locations. A string,
+for example, denotes as many locations as there are characters in the
+string. A new value can be stored into one of these locations using
+the @code{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 @code{car}, @code{vector-ref}, or @code{string-ref},
+is equivalent in the sense of @code{eqv?} (@ref{Equivalence
+predicates}) 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 newly 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. Notwithstanding this, it is understood that the empty list
+cannot be newly allocated, because it is a unique object. It is also
+understood that empty strings, empty vectors, and empty bytevectors,
+which contain no locations, may or may not be newly allocated.
+
+Every object that denotes locations is either mutable
+or immutable. Literal constants, the strings returned by
+@code{symbol->string}, and possibly the environment returned by
+@code{scheme-report-environment} are immutable objects. All objects
+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.
+
+These locations are to be understood as conceptual, not
+physical. Hence, they do not necessarily correspond to memory
+addresses, and even if they do, the memory address might not be
+constant.
@rationale{}
-In many systems it is desirable for constants (i.e. the values of
-literal expressions) to reside in read-only memory. Making it an error to
-alter constants permits this implementation strategy, while not requiring
-other systems to distinguish between mutable and immutable objects.
+In many systems it is desirable for constants (i.e. the values
+of literal expressions) to reside in read-only memory. Making it
+an error to alter constants permits this implementation strategy,
+while not requiring other systems to distinguish between mutable and
+immutable objects.
@node Proper tail recursion
@section Proper tail recursion
-Implementations of Scheme are required to be @dfn{properly tail-recursive}.
-Procedure calls that occur in certain syntactic contexts defined below are
-@dfn{tail calls}. A Scheme implementation is properly tail-recursive if it
-supports an unbounded number of active tail calls. A call is @dfn{active} if
-the called procedure might still return. Note that this includes calls that
-might be returned from either by the current continuation or by
-continuations captured earlier by @code{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 [6].
+Implementations of Scheme are required to be @dfn{properly
+tail-recursive}. Procedure calls that occur in certain syntactic
+contexts defined below are @dfn{tail calls}. A Scheme implementation
+is properly tail-recursive if it supports an unbounded number of active
+tail calls. A call is @dfn{active} if the called procedure might still
+return. Note that this includes calls that might be returned from
+either by the current continuation or by continuations captured earlier
+by @code{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 [6].
@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.
-
-A @dfn{tail call} is a procedure call that occurs in a @dfn{tail context}. Tail
-contexts are defined inductively. Note that a tail context is always
-determined with respect to a particular lambda expression.
+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.
+
+A @dfn{tail call} is a procedure call that occurs in a @dfn{tail
+context}. Tail contexts are defined inductively. Note that a tail
+context is always determined with respect to a particular lambda
+expression.
@itemize
@item
-The last expression within the body of a lambda expression, shown as <tail
-expression> below, occurs in a tail context. The same is true of all the
-bodies of @code{case-lambda} expressions.
+The last expression within the body of a lambda expression, shown as
+<tail expression> below, occurs in a tail context. The same is true of
+all the bodies of @code{case-lambda} expressions.
@lisp
(lambda @svar{formals}
@@ -250,12 +262,12 @@ bodies of @code{case-lambda} expressions.
@item
If one of the following expressions is in a tail context, then the
-subexpressions shown as @svar{tail expression} are in a tail context. These
-were derived from rules in the grammar given in @ref{Formal syntax and
-semantics} by replacing some occurrences of @svar{body} with @svar{tail
-body}, some occurrences of @svar{expression} with @svar{tail expression},
-and some occurrences of @svar{sequence} with @svar{tail sequence}. Only
-those rules that contain tail contexts are shown here.
+subexpressions shown as @svar{tail expression} are in a tail context.
+These were derived from rules in the grammar given in @ref{Formal
+syntax and semantics} by replacing some occurrences of @svar{body} with
+@svar{tail body}, some occurrences of @svar{expression} with @svar{tail
+expression}, and some occurrences of @svar{sequence} with @svar{tail
+sequence}. Only those rules that contain tail contexts are shown here.
@c Maybe @format would be better here. FIXME: We still need markup
@c for metavariables.
@@ -307,24 +319,25 @@ where
@end display
@item
-If a @code{cond} or @code{case} expression is in a tail context, and has a
-clause of the form @code{(}@svar{expression@sub{1}} @code{=>}
-@svar{expression@sub{2}}@code{)} then the (implied) call to the procedure
-that results from the evaluation of @svar{expression} is in a tail context.
-@svar{expression} itself is not in a tail context.
+If a @code{cond} or @code{case} expression is in a tail context, and
+has a clause of the form @code{(}@svar{expression@sub{1}} @code{=>}
+@svar{expression@sub{2}}@code{)} then the (implied) call to the
+procedure that results from the evaluation of @svar{expression} is in a
+tail context. @svar{expression} itself is not in a tail context.
@end itemize
-Certain procedures defined in this report are also required to perform tail
-calls. The first argument passed to @code{apply} and to
-@code{call-with-current-continuation}, and the second argument passed to
-@code{call-with-values}, must be called via a tail call. Similarly,
-@code{eval} must evaluate its first argument as if it were in tail position
-within the @code{eval} procedure.
+Certain procedures defined in this report are also required to
+perform tail calls. The first argument passed to @code{apply} and to
+@code{call-with-current-continuation}, and the second argument passed
+to @code{call-with-values}, must be called via a tail call. Similarly,
+@code{eval} must evaluate its first argument as if it were in tail
+position within the @code{eval} procedure.
-In the following example the only tail call is the call to @code{f}. None of
-the calls to @code{g} or @code{h} are tail calls. The reference to @code{x}
-is in a tail context, but it is not a call and thus is not a tail call.
+In the following example the only tail call is the call to
+@code{f}. None of the calls to @code{g} or @code{h} are tail calls. The
+reference to @code{x} is in a tail context, but it is not a call and
+thus is not a tail call.
@lisp
(lambda ()
@@ -334,9 +347,10 @@ is in a tail context, but it is not a call and thus is not a tail call.
(and (g) (f))))
@end lisp
-Note: Implementations may recognize that some non-tail calls, such as the call to
-@code{h} above, can be evaluated as though they were tail calls. In the
-example above, the @code{let} expression could be compiled as a tail call to
-@code{h}. (The possibility of @code{h} returning an unexpected number of
-values can be ignored, because in that case the effect of the @code{let} is
-explicitly unspecified and implementation-dependent.)
+Note: Implementations may recognize that some non-tail calls, such
+as the call to @code{h} above, can be evaluated as though they were
+tail calls. In the example above, the @code{let} expression could be
+compiled as a tail call to @code{h}. (The possibility of @code{h}
+returning an unexpected number of values can be ignored, because
+in that case the effect of the @code{let} is explicitly unspecified
+and implementation-dependent.)
