While "a cast of thousands" may be an overstatement, it is certainly the case that this document represents the work of many people. First and foremost, thanks go to the authors of the Revised^4 Report on the Algorithmic Language Scheme, from which much of this document is derived. Thanks also to BBN Advanced Computers Inc. for the use of parts of their Butterfly Scheme Reference, and to Margaret O'Connell for translating it from BBN's text-formatting language to ours.
Special thanks to Richard Stallman, Bob Chassell, and Brian Fox, all of the Free Software Foundation, for creating and maintaining the Texinfo formatting language in which this document is written.
This report describes research done at the Artificial Intelligence Laboratory and the Laboratory for Computer Science, both of the Massachusetts Institute of Technology. Support for this research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-92-J-4097 and by the National Science Foundation under grant number MIP-9001651.
This manual is a detailed description of the MIT Scheme runtime system. It is intended to be a reference document for programmers. It does not describe how to run Scheme or how to interact with it -- that is the subject of the MIT Scheme User's Manual.
This chapter summarizes the semantics of Scheme, briefly describes the MIT Scheme programming environment, and explains the syntactic and lexical conventions of the language. Subsequent chapters describe special forms, numerous data abstractions, and facilities for input and output.
Throughout this manual, we will make frequent references to standard Scheme, which is the language defined by the document Revised^4 Report on the Algorithmic Language Scheme, by William Clinger, Jonathan Rees, et al., or by IEEE Std. 1178-1990, IEEE Standard for the Scheme Programming Language (in fact, several parts of this document are copied from the Revised Report). MIT Scheme is an extension of standard Scheme.
These are the significant semantic characteristics of the Scheme language:
Scheme uses a parenthesized-list Polish notation to describe programs
and (other) data. The syntax of Scheme, like that of most Lisp
dialects, provides for great expressive power, largely due to its
simplicity. An important consequence of this simplicity is the
susceptibility of Scheme programs and data to uniform treatment by other
Scheme programs. As with other Lisp dialects, the read primitive
parses its input; that is, it performs syntactic as well as lexical
decomposition of what it reads.
This section details the notational conventions used throughout the rest of this document.
When this manual uses the phrase "an error will be signalled," it
means that Scheme will call error, which normally halts execution
of the program and prints an error message.
When this manual uses the phrase "it is an error," it means that the specified action is not valid in Scheme, but the system may or may not signal the error. When this manual says that something "must be," it means that violating the requirement is an error.
This manual gives many examples showing the evaluation of expressions. The examples have a common format that shows the expression being evaluated on the left hand side, an "arrow" in the middle, and the value of the expression written on the right. For example:
(+ 1 2) => 3
Sometimes the arrow and value will be moved under the expression, due to lack of space. Occasionally we will not care what the value is, in which case both the arrow and the value are omitted.
If an example shows an evaluation that results in an error, an error message is shown, prefaced by `error-->':
(+ 1 'foo) error--> Illegal datum
An example that shows printed output marks it with `-|':
(begin (write 'foo) 'bar)
-| foo
=> bar
When this manual indicates that the value returned by some expression is unspecified, it means that the expression will evaluate to some object without signalling an error, but that programs should not depend on the value in any way.
Each description of an MIT Scheme variable, special form, or procedure begins with one or more header lines in this format:
@deffnexample category template
where category specifies the kind of item ("variable", "special form", or "procedure"), and how the item conforms to standard Scheme, as follows:
The form of template is interpreted depending on category.
else keyword in
the cond special form, are set in a fixed width font in the
printed manual; in the Info file they are not distinguished.
Parentheses indicate themselves.
A horizontal ellipsis (...) is describes repeated components.
Specifically,
thing ...indicates zero or more occurrences of thing, while
thing thing ...indicates one or more occurrences of thing. Brackets,
[ ], enclose optional components.
Several special forms (e.g. lambda) have an internal component
consisting of a series of expressions; usually these expressions are
evaluated sequentially under conditions that are specified in the
description of the special form. This sequence of expressions is commonly
referred to as the body of the special form.
cdr takes one argument,
which must be a pair.
Many procedures signal an error when an argument is of the wrong type;
usually this error is a condition of type
condition-type:wrong-type-argument.
In addition to the standard data-type names (pair, list,
boolean, string, etc.), the following names as arguments
also imply type restrictions:
Some examples:
@deffnexample procedure list object ...
indicates that the standard Scheme procedure list takes zero or
more arguments, each of which may be any Scheme object.
@deffnexample procedure write-char char [output-port]
indicates that the standard Scheme procedure write-char must be
called with a character, char, and may also be called with a
character and an output port.
Any identifier that is not a syntactic keyword may be used as a variable (see section Identifiers). A variable may name a location where a value can be stored. A variable that does so is said to be bound to the location. The value stored in the location to which a variable is bound is called the variable's value. (The variable is sometimes said to name the value or to be bound to the value.)
A variable may be bound but still not have a value; such a variable is
said to be unassigned. Referencing an unassigned variable is an
error. When this error is signalled, it is a condition of type
condition-type:unassigned-variable; sometimes the compiler does
not generate code to signal the error. Unassigned variables are useful
only in combination with side effects (see section Assignments).
An environment is a set of variable bindings. If an environment
has no binding for a variable, that variable is said to be unbound
in that environment. Referencing an unbound variable signals a
condition of type condition-type:unbound-variable.
A new environment can be created by extending an existing
environment with a set of new bindings. Note that "extending an
environment" does not modify the environment; rather, it
creates a new environment that contains the new bindings and the old
ones. The new bindings shadow the old ones; that is, if an
environment that contains a binding for x is extended with a new
binding for x, then only the new binding is seen when x is
looked up in the extended environment. Sometimes we say that the
original environment is the parent of the new one, or that the new
environment is a child of the old one, or that the new environment
inherits the bindings in the old one.
Procedure calls extend an environment, as do let, let*,
letrec, and do expressions. Internal definitions
(see section Internal Definitions) also extend an environment. (Actually,
all the constructs that extend environments can be expressed in terms of
procedure calls, so there is really just one fundamental mechanism for
environment extension.)
A top-level definition (see section Top-Level Definitions) may add a binding to an existing environment.
MIT Scheme provides an initial environment that contains all of the variable bindings described in this manual. Most environments are ultimately extensions of this initial environment. In Scheme, the environment in which your programs execute is actually a child (extension) of the environment containing the system's bindings. Thus, system names are visible to your programs, but your names do not interfere with system programs.
The environment in effect at some point in a program is called the
current environment at that point. In particular, every REP
loop has a current environment. (REP stands for
"read-eval-print"; the REP loop is the Scheme program that reads
your input, evaluates it, and prints the result.) The environment of
the top-level REP loop (the one you are in when Scheme starts up)
starts as user-initial-environment, although it can be changed by
the ge procedure. When a new REP loop is created, its
environment is determined by the program that creates it.
Scheme is a statically scoped language with block structure. In this respect, it is like Algol and Pascal, and unlike most other dialects of Lisp except for Common Lisp.
The fact that Scheme is statically scoped (rather than dynamically bound) means that the environment that is extended (and becomes current) when a procedure is called is the environment in which the procedure was created (i.e. in which the procedure's defining lambda expression was evaluated), not the environment in which the procedure is called. Because all the other Scheme binding expressions can be expressed in terms of procedures, this determines how all bindings behave.
Consider the following definitions, made at the top-level REP loop (in the initial environment):
(define x 1) (define (f x) (g 2)) (define (g y) (+ x y)) (f 5) => 3 ; not 7
Here f and g are bound to procedures created in the
initial environment. Because Scheme is statically scoped, the call to
g from f extends the initial environment (the one in which
g was created) with a binding of y to 2. In this
extended environment, y is 2 and x is 1.
(In a dynamically bound Lisp, the call to g would extend the
environment in effect during the call to f, in which x is
bound to 5 by the call to f, and the answer would be
7.)
Note that with static scoping, you can tell what binding a variable
reference refers to just from looking at the text of the program; the
referenced binding cannot depend on how the program is used. That is,
the nesting of environments (their parent-child relationship)
corresponds to the nesting of binding expressions in program text.
(Because of this connection to the text of the program, static scoping
is also called lexical scoping.) For each place where a variable
is bound in a program there is a corresponding region of the
program text within which the binding is effective. For example, the
region of a binding established by a lambda expression is the
entire body of the lambda expression. The documentation of each
binding expression explains what the region of the bindings it makes is.
A use of a variable (that is, a reference to or assignment of a
variable) refers to the innermost binding of that variable whose region
contains the variable use. If there is no such region, the use refers
to the binding of the variable in the global environment (which is an
ancestor of all other environments, and can be thought of as a region in
which all your programs are contained).
In Scheme, the boolean values true and false are denoted by #t
and #f. However, any Scheme value can be treated as a boolean
for the purpose of a conditional test. This manual uses the word
true to refer to any Scheme value that counts as true, and the
word false to refer to any Scheme value that counts as false. In
conditional tests, all values count as true except for #f, which
counts as false (see section Conditionals).
Implementation note: In MIT Scheme, #f and the empty list
are the same object, and the printed representation of #f is
always `()'. As this contradicts the Scheme standard, MIT
Scheme will soon be changed to make #f and the empty list
different objects.
An important concept in Scheme is that of the external representation of an object as a sequence of characters. For example, an external representation of the integer 28 is the sequence of characters `28', and an external representation of a list consisting of the integers 8 and 13 is the sequence of characters `(8 13)'.
The external representation of an object is not necessarily unique. The integer 28 also has representations `#e28.000' and `#x1c', and the list in the previous paragraph also has the representations `( 08 13 )' and `(8 . (13 . ( )))'.
Many objects have standard external representations, but some, such as procedures and circular data structures, 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 section Quoting).
External representations can also be used for input and output. The
procedure read parses external representations, and the procedure
write generates them. Together, they provide an elegant and
powerful input/output facility.
Note that the sequence of characters `(+ 2 6)' is not an
external representation of the integer 8, even though it is an
expression that evaluates to the integer 8; rather, it is an external
representation of a three-element list, the elements of which are the
symbol + 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 data as
programs.
Every object satisfies at most one of the following predicates (but see section True and False, for an exception):
bit-string? environment? port? symbol? boolean? null? procedure? vector? cell? number? promise? weak-pair? char? pair? string? condition?
This section describes a model that can be used to understand Scheme's use of storage.
Variables and objects such as pairs, vectors, and strings implicitly
denote locations or sequences of locations. A string, for 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 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 car, vector-ref, or string-ref,
is equivalent in the sense of 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 document 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
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
immutable. The constants and the strings returned by
symbol->string are then the immutable objects, while all objects
created by other procedures are mutable. It is an error to attempt to
store a new value into a location that is denoted by an immutable
object. Note that the MIT Scheme compiler takes advantage of this
property to share constants, but that these constants are not immutable.
Instead, two constants that are equal? may be eq? in
compiled code.
This section describes Scheme's lexical conventions.
Whitespace characters are spaces, newlines, tabs, and page breaks. Whitespace is used to improve the readability of your programs and to separate tokens from each other, when necessary. (A token is an indivisible lexical unit such as an identifier or number.) Whitespace 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.
All whitespace characters are delimiters. In addition, the following characters act as delimiters:
( ) ; " ' ` |
Finally, these next characters act as delimiters, despite the fact that Scheme does not define any special meaning for them:
[ ] { }
For example, if the value of the variable name is
"max":
(list"Hi"name(+ 1 2)) => ("Hi" "max" 3)
An identifier is a sequence of one or more non-delimiter characters. Identifiers are used in several ways in Scheme programs:
Scheme accepts most of the identifiers that other programming languages allow. MIT Scheme allows all of the identifiers that standard Scheme does, plus many more.
MIT Scheme defines a potential identifier to be a sequence of non-delimiter characters that does not begin with either of the characters `#' or `,'. Any such sequence of characters that is not a syntactically valid number (see section Numbers) is considered to be a valid identifier. Note that, although it is legal for `#' and `,' to appear in an identifier (other than in the first character position), it is poor programming practice.
Here are some examples of identifiers:
lambda q list->vector soup + V17a <=? a34kTMNs the-word-recursion-has-many-meanings
Scheme doesn't distinguish uppercase and lowercase forms of a letter except within character and string constants; in other words, Scheme is case-insensitive. For example, `Foo' is the same identifier as `FOO', and `#x1AB' is the same number as `#X1ab'. But `#\a' and `#\A' are different characters.
A predicate is a procedure that always returns a boolean value
(#t or #f). By convention, predicates usually have names
that end in `?'.
A mutation procedure is a procedure that alters a data structure. By convention, mutation procedures usually have names that end in `!'.
The beginning of a comment is indicated with a semicolon (;).
Scheme ignores everything on a line in which a semicolon appears, from
the semicolon until the end of the line. The entire comment, including
the newline character that terminates it, is treated as
whitespace.
An alternative form of comment (sometimes called an extended comment) begins with the characters `#|' and ends with the characters `|#'. This alternative form is an MIT Scheme extension. As with ordinary comments, all of the characters in an extended comment, including the leading `#|' and trailing `|#', are treated as whitespace. Comments of this form may extend over multiple lines, and additionally may be nested (unlike the comments of the programming language C, which have a similar syntax).
;;; This is a comment about the FACT procedure. Scheme
;;; ignores all of this comment. The FACT procedure computes
;;; the factorial of a non-negative integer.
#|
This is an extended comment.
Such comments are useful for commenting out code fragments.
|#
(define fact
(lambda (n)
(if (= n 0) ;This is another comment:
1 ;Base case: return 1
(* n (fact (- n 1))))))
The following list describes additional notations used in Scheme. See section Numbers, for a description of the notations used for numbers.
+ - .
( )
"
\
;
'
`
,
,@
#
#t #f
#\
#(
#e #i #b #o #d #l #s #x
#|
#!
#!optional and
#!rest, both of which are used in the lambda special form
to mark certain parameters as being "optional" or "rest" parameters.
This notation is an MIT Scheme extension.
#*
#[
#@
#=
##
A Scheme expression is a construct that returns a value. An expression may be a literal, a variable reference, a special form, or a procedure call.
Literal constants may be written by using an external representation of the data. In general, the external representation must be quoted (see section Quoting); but some external representations can be used without quotation.
"abc" => "abc" 145932 => 145932 #t => #t #\a => #\a
The external representation of numeric constants, string constants, character constants, and boolean constants evaluate to the constants themselves. Symbols, pairs, lists, and vectors require quoting.
An expression consisting of an identifier (see section Identifiers) is a variable reference; the identifier is the name of the variable being referenced. The value of the variable reference is the value stored in the location to which the variable is bound. An error is signalled if the referenced variable is unbound or unassigned.
(define x 28) x => 28
(keyword component ...)
A parenthesized expression that starts with a syntactic keyword is a special form. Each special form has its own syntax, which is described later in the manual. The following list contains all of the syntactic keywords that are defined when MIT Scheme is initialized:
access define-syntax macro and delay make-environment begin do named-lambda bkpt fluid-let or case if quasiquote cond in-package quote cons-stream lambda scode-quote declare let sequence default-object? let* set! define let-syntax the-environment define-integrable letrec unassigned? define-macro local-declare using-syntax define-structure
(operator operand ...)
A procedure call is written by simply enclosing in parentheses expressions for the procedure to be called (the operator) and the arguments to be passed to it (the operands). The operator and operand expressions are evaluated and the resulting procedure is passed the resulting arguments. See section Lambda Expressions, for a more complete description of this.
Another name for the procedure call expression is combination. This word is more specific in that it always refers to the expression; "procedure call" sometimes refers to the process of calling a procedure.
Unlike some other dialects of Lisp, Scheme always evaluates the operator expression and the operand expressions with the same evaluation rules, and the order of evaluation is unspecified.
(+ 3 4) => 7 ((if #f = *) 3 4) => 12
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
+ and *. New procedures are created by evaluating
lambda expressions.
If the operator is a syntactic keyword, then the expression is not
treated as a procedure call: it is a special form. Thus you should not
use syntactic keywords as procedure names. If you were to bind one of
these keywords to a procedure, you would have to use apply to
call the procedure. MIT Scheme signals an error when such a
binding is attempted.
A special form is an expression that follows special evaluation rules. This chapter describes the basic Scheme special forms.
lambda expression evaluates to a procedure. The environment in
effect when the lambda expression is evaluated is remembered as
part of the procedure; it is called the closing environment. When
the procedure is later called with some arguments, the closing
environment is extended by binding the variables in the formal parameter
list to fresh locations, and the locations are filled with the arguments
according to rules about to be given. The new environment created by
this process is referred to as the invocation environment.
Once the invocation environment has been constructed, the
expressions in the body of the lambda expression are
evaluated sequentially in it. This means that the region of the
variables bound by the lambda expression is all of the
expressions in the body. The result of evaluating the last
expression in the body is returned as the result of the procedure
call.
Formals, the formal parameter list, is often referred to as a lambda list.
The process of matching up formal parameters with arguments is somewhat involved. There are three types of parameters, and the matching treats each in sequence:
condition-type:wrong-number-of-arguments is signalled;
this error is also signalled if there are more arguments than required
parameters and there are no further parameters.
condition-type:wrong-number-of-arguments is signalled.
The predicate default-object?, which is true only of default
objects, can be used to determine which optional parameters were
supplied, and which were defaulted.
Specially recognized keywords divide the formals parameters into these three classes. The keywords used here are `#!optional', `.', and `#!rest'. Note that only `.' is defined by standard Scheme -- the other keywords are MIT Scheme extensions. `#!rest' has the same meaning as `.' in formals.
The use of these keywords is best explained by means of examples. The following are typical lambda lists, followed by descriptions of which parameters are required, optional, and rest. We will use `#!rest' in these examples, but anywhere it appears `.' could be used instead.
(a b c)
a, b, and c are all required. The procedure must
be passed exactly three arguments.
(a b #!optional c)
a and b are required, c is optional. The procedure
may be passed either two or three arguments.
(#!optional a b c)
a, b, and c are all optional. The procedure may be
passed any number of arguments between zero and three, inclusive.
a
(#!rest a)
a is a rest parameter. The
procedure may be passed any number of arguments. Note: this is the only
case in which `.' cannot be used in place of `#!rest'.
(a b #!optional c d #!rest e)
a and b are required, c and d are optional,
and e is rest. The procedure may be passed two or more
arguments.
Some examples of lambda expressions:
(lambda (x) (+ x x)) => #[compound-procedure 53]
((lambda (x) (+ x x)) 4) => 8
(define reverse-subtract
(lambda (x y)
(- y x)))
(reverse-subtract 7 10) => 3
(define foo
(let ((x 4))
(lambda (y) (+ x y))))
(foo 6) => 10
named-lambda special form is similar to lambda, except
that the first "required parameter" in formals is not a
parameter but the name of the resulting procedure; thus
formals must have at least one required parameter. This name has
no semantic meaning, but is included in the external representation of
the procedure, making it useful for debugging. In MIT Scheme,
lambda is implemented as named-lambda, with a special name
that means "unnamed".
(named-lambda (f x) (+ x x)) => #[compound-procedure 53 f] ((named-lambda (f x) (+ x x)) 4) => 8
The three binding constructs let, let*, and letrec,
give Scheme block structure. The syntax of the three constructs is
identical, but they differ in the regions they establish for their
variable bindings. In a let expression, the initial values are
computed before any of the variables become bound. In a let*
expression, the evaluations and bindings are sequentially interleaved.
And in a letrec expression, all the bindings are in effect while
the initial values are being computed (thus allowing mutually recursive
definitions).
MIT Scheme allows any of the inits to be omitted, in which case the corresponding variables are unassigned.
Note that the following are equivalent:
(let ((variable init) ...) expression expression ...) ((lambda (variable ...) expression expression ...) init ...)
Some examples:
(let ((x 2) (y 3))
(* x y)) => 6
(let ((x 2) (y 3))
(let ((foo (lambda (z) (+ x y z)))
(x 7))
(foo 4))) => 9
See section Iteration, for information on "named let".
let* is similar to let, but the bindings are performed
sequentially from left to right, and the region of a binding is that
part of the 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.
Note that the following are equivalent:
(let* ((variable1 init1)
(variable2 init2)
...
(variableN initN))
expression
expression ...)
(let ((variable1 init1))
(let ((variable2 init2))
...
(let ((variableN initN))
expression
expression ...)
...))
An example:
(let ((x 2) (y 3))
(let* ((x 7)
(z (+ x y)))
(* z x))) => 70
letrec expression as its region, making it possible to
define mutually recursive procedures.
MIT Scheme allows any of the inits to be omitted, in which case the corresponding variables are unassigned.
(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? 88)) => #t
One restriction on letrec is very important: it shall be possible
to evaluated each init without assigning or referring to the value
of any 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 letrec,
all the inits are lambda or delay expressions and
the restriction is satisfied automatically.
The syntax of this special form is similar to that of let, but
fluid-let temporarily rebinds existing variables. Unlike
let, fluid-let creates no new bindings; instead it
assigns the value of each init to the binding (determined
by the rules of lexical scoping) of its corresponding variable.
MIT Scheme allows any of the inits to be omitted, in which case the corresponding variables are temporarily unassigned.
An error of type condition-type:unbound-variable is signalled if
any of the variables are unbound. However, because
fluid-let operates by means of side effects, it is valid for any
variable to be unassigned when the form is entered.
Here is an example showing the difference between fluid-let and
let. First see how let affects the binding of a variable:
(define variable #t) (define (access-variable) variable) variable => #t (let ((variable #f)) (access-variable)) => #t variable => #t
access-variable returns #t in this case because it
is defined in an environment with variable bound to
#t. fluid-let, on the other hand, temporarily reuses an
existing variable:
variable => #t (fluid-let ((variable #f)) ;reuses old binding (access-variable)) => #f variable => #t
The extent of a dynamic binding is defined to be the time period during which the variable contains the new value. Normally this time period begins when the body is entered and ends when it is exited; on a sequential machine it is normally a contiguous time period. However, because Scheme has first-class continuations, it is possible to leave the body and then reenter it, as many times as desired. In this situation, the extent becomes non-contiguous.
When the body is exited by invoking a continuation, the new value is saved, and the variable is set to the old value. Then, if the body is reentered by invoking a continuation, the old value is saved, and the variable is set to the new value. In addition, side effects to the variable that occur both inside and outside of body are preserved, even if continuations are used to jump in and out of body repeatedly.
Here is a complicated example that shows the interaction between dynamic binding and continuations:
(define (complicated-dynamic-binding)
(let ((variable 1)
(inside-continuation))
(write-line variable)
(call-with-current-continuation
(lambda (outside-continuation)
(fluid-let ((variable 2))
(write-line variable)
(set! variable 3)
(call-with-current-continuation
(lambda (k)
(set! inside-continuation k)
(outside-continuation #t)))
(write-line variable)
(set! inside-continuation #f))))
(write-line variable)
(if inside-continuation
(begin
(set! variable 4)
(inside-continuation #f)))))
Evaluating `(complicated-dynamic-binding)' writes the following on the console:
1 2 1 3 4
Commentary: the first two values written are the initial binding of
variable and its new binding after the fluid-let's body is
entered. Immediately after they are written, variable is set to
`3', and then outside-continuation is invoked, causing us to
exit the body. At this point, `1' is written, demonstrating that
the original value of variable has been restored, because we have
left the body. Then we set variable to `4' and reenter the
body by invoking inside-continuation. At this point, `3' is
written, indicating that the side effect that previously occurred within
the body has been preserved. Finally, we exit body normally, and write
`4', demonstrating that the side effect that occurred outside of
the body was also preserved.
lambda,
let, let*, letrec, fluid-let, or "procedure
define" expression). A definition that occurs at the top level
of a program is called a top-level definition, and a definition
that occurs at the beginning of a body is called an internal
definition.
In the second form of define (called "procedure
define"), the component formals is identical to the
component of the same name in a named-lambda expression. In
fact, these two expressions are equivalent:
(define (name1 name2 ...)
expression
expression ...)
(define name1
(named-lambda (name1 name2 ...)
expression
expression ...))
(define variable expression)
has essentially the same effect as this assignment expression, if variable is bound:
(set! variable expression)
If variable is not bound, however, define binds
variable to a new location in the current environment before
performing the assignment (it is an error to perform a set! on an
unbound variable). If you omit expression, the variable becomes
unassigned; an attempt to reference such a variable is an error.
(define add3 (lambda (x) (+ x 3))) => unspecified (add3 3) => 6 (define first car) => unspecified (first '(1 2)) => 1 (define bar) => unspecified bar error--> Unassigned variable
An internal definition is a definition that occurs at the
beginning of a body (that is, the body of a lambda,
let, let*, letrec, fluid-let, or "procedure
define" expression), rather than at the top level of a program.
The variable defined by an internal definition is local to the
body. That is, variable is bound rather than assigned, and
the region of the binding is the entire body. For example,
(let ((x 5)) (define foo (lambda (y) (bar x y))) (define bar (lambda (a b) (+ (* a b) a))) (foo (+ x 3))) => 45
A body containing internal definitions can always be converted
into a completely equivalent letrec expression. For example, the
let expression in the above example is equivalent to
(let ((x 5))
(letrec ((foo (lambda (y) (bar x y)))
(bar (lambda (a b) (+ (* a b) a))))
(foo (+ x 3))))
set! expression is unspecified.
Variable must be bound either in some region enclosing the
set! expression, or at the top level. However, variable is
permitted to be unassigned when the set! form is entered.
(define x 2) => unspecified (+ x 1) => 3 (set! x 4) => unspecified (+ x 1) => 5
Variable may be an access expression
(see section Environments). This allows you to assign variables in an
arbitrary environment. For example,
(define x (let ((y 0)) (the-environment))) (define y 'a) y => a (access y x) => 0 (set! (access y x) 1) => unspecified y => a (access y x) => 1
This section describes the expressions that are used to modify or prevent the evaluation of objects.
(quote datum) evaluates to datum. Datum may be
any external representation of a Scheme object
(see section External Representations).
Use quote to include literal constants in
Scheme code.
(quote a) => a (quote #(a b c)) => #(a b c) (quote (+ 1 2)) => (+ 1 2)
(quote datum) may be abbreviated as 'datum.
The two notations are equivalent in all respects.
'a => a '#(a b c) => #(a b c) '(+ 1 2) => (+ 1 2) '(quote a) => 'a "a => 'a
Numeric constants, string constants, character constants, and boolean constants evaluate to themselves, so they don't need to be quoted.
'"abc" => "abc" "abc" => "abc" '145932 => 145932 145932 => 145932 '#t => #t #t => #t '#\a => #\a #\a => #\a
`template is
equivalent (in the sense of equal?) to the result of evaluating
'template. If a comma appears within the 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 expression shall 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.
`(list ,(+ 1 2) 4) => (list 3 4)
(let ((name 'a)) `(list ,name ',name)) => (list a 'a)
`(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b) => (a 3 4 5 6 b)
`((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)
`,(+ 2 3) => 5
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.
`(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)
The notations `template and (quasiquote
template) are identical in all respects.
,expression is identical to (unquote
expression) and ,@expression is identical to
(unquote-splicing expression).
(quasiquote (list (unquote (+ 1 2)) 4))
=> (list 3 4)
'(quasiquote (list (unquote (+ 1 2)) 4))
=> `(list ,(+ 1 2) 4)
i.e., (quasiquote (list (unquote (+ 1 2)) 4))
Unpredictable behavior can result if any of the symbols
quasiquote, unquote, or unquote-splicing appear in
a template in ways otherwise than as described above.
The behavior of the conditional expressions is determined by
whether objects are true or false. The conditional expressions count
only #f as false. They count everything else, including
#t, pairs, symbols, numbers, strings, vectors, and procedures as
true (but see section True and False).
In the descriptions that follow, we say that an object has "a true value" or "is true" when the conditional expressions treat it as true, and we say that an object has "a false value" or "is false" when the conditional expressions treat it as false.
if expression is evaluated as follows: first,
predicate is evaluated. If it yields a true value, then
consequent is evaluated and its value is returned. Otherwise
alternative is evaluated and its value is returned. If
predicate yields a false value and no alternative is
specified, then the result of the expression is unspecified.
An if expression evaluates either consequent or
alternative, never both. Programs should not depend on the value
of an if expression that has no alternative.
(if (> 3 2) 'yes 'no) => yes
(if (> 2 3) 'yes 'no) => no
(if (> 3 2)
(- 3 2)
(+ 3 2)) => 1
(predicate expression ...)
where predicate is any expression. The last clause may be
an else clause, which has the form:
(else expression expression ...)
A cond expression does the following:
cond evaluates
the expressions in the associated clause in left to right
order, and returns the result of evaluating the last expression in
the clause as the result of the entire cond expression.
If the selected clause contains only the predicate and no
expressions, cond returns the value of the predicate
as the result.
else clause, the result of the conditional expression is
unspecified; if there is an else clause, cond evaluates
its expressions (left to right) and returns the value of the last
one.
(cond ((> 3 2) 'greater)
((< 3 2) 'less)) => greater
(cond ((> 3 3) 'greater)
((< 3 3) 'less)
(else 'equal)) => equal
Normally, programs should not depend on the value of a cond
expression that has no else clause. However, some Scheme
programmers prefer to write cond expressions in which at least
one of the predicates is always true. In this style, the final
clause is equivalent to an else clause.
Scheme supports an alternative clause syntax:
(predicate => recipient)
where recipient is an expression. If predicate evaluates to a true value, then recipient is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the predicate.
(cond ((assv 'b '((a 1) (b 2))) => cadr)
(else #f)) => 2
((object ...) expression expression ...)
No object is evaluated, and all the objects must be
distinct. The last clause may be an else clause,
which has the form:
(else expression expression ...)
A case expression does the following:
eqv?; see section Equivalence Predicates) to an object,
case evaluates the expressions in the corresponding
clause from left to right and returns the result of evaluating the
last expression in the clause as the result of the
case expression.
else clause, case
evaluates its expressions and returns the result of the last one
as the result of the case expression. If there's no else
clause, case returns an unspecified result. Programs should not
depend on the value of a case expression that has no else
clause.
For example,
(case (* 2 3) ((2 3 5 7) 'prime) ((1 4 6 8 9) 'composite)) => composite (case (car '(c d)) ((a) 'a) ((b) 'b)) => unspecified (case (car '(c d)) ((a e i o u) 'vowel) ((w y) 'semivowel) (else 'consonant)) => consonant
#t is returned.
(and (= 2 2) (> 2 1)) => #t (and (= 2 2) (< 2 1)) => #f (and 1 2 'c '(f g)) => (f g) (and) => #t
#f is returned.
(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)
(define x 0)
(begin (set! x 5)
(+ x 1)) => 6
(begin (display "4 plus 1 equals ")
(display (+ 4 1)))
-| 4 plus 1 equals 5
=> unspecified
Often the use of begin is unnecessary, because many special forms
already support sequences of expressions (that is, they have an implicit
begin). Some of these special forms are:
case
cond
define ;"procedure define" only
do
fluid-let
lambda
let
let*
letrec
named-lambda
The obsolete special form sequence is identical to begin.
It should not be used in new code.
The iteration expressions are: "named let" and do.
They are also binding expressions, but are more commonly referred to as
iteration expressions. Because Scheme is properly tail-recursive, you
don't need to use these special forms to express iteration; you can
simply use appropriately written "recursive" procedure calls.
let called
"named let" which provides a more general looping construct
than do, and may also be used to express recursions.
Named let has the same syntax and semantics as ordinary
let except that name is bound within the expressions
to a procedure whose formal arguments are the variables and whose
body is the expressions. Thus the execution of the
expressions may be repeated by invoking the procedure named by
name.
MIT Scheme allows any of the inits to be omitted, in which case the corresponding variables are unassigned.
Note: the following expressions are equivalent:
(let name ((variable init) ...)
expression
expression ...)
((letrec ((name
(named-lambda (name variable ...)
expression
expression ...)))
name)
init ...)
Here is an example:
(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))
(else
(loop (cdr numbers)
nonneg
(cons (car numbers) neg)))))
=> ((6 1 3) (-5 -2))
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 with a specified result value.
do expressions are evaluated as follows: The init
expressions are evaluated (in some unspecified order), the
variables are bound to fresh locations, the results of the
init expressions are stored in the bindings of the
variables, and then the iteration phase begins.
Each iteration begins by evaluating test; if the result is false, then the command expressions are evaluated in order for effect, the step expressions are evaluated in some unspecified order, the variables are bound to fresh locations, the results of the steps are stored in the bindings of the variables, and the next iteration begins.
If test evaluates to a true value, then the expressions are
evaluated from left to right and the value of the last expression
is returned as the value of the do expression. If no
expressions are present, then the value of the do
expression is unspecified in standard Scheme; in MIT Scheme, the
value of test is returned.
The region of the binding of a variable consists of the entire
do expression except for the inits. It is an error for a
variable to appear more than once in the list of do
variables.
A step may be omitted, in which case the effect is the same as if
(variable init variable) had been written
instead of (variable init).
(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
This section provides examples and describes the options and syntax of
define-structure, an MIT Scheme macro that is very similar to
defstruct in Common Lisp. The differences between them are
summarized at the end of this section. For more information, see
Steele's Common Lisp book.
slot-name (slot-name default-init [slot-option value]*)
The fields name and slot-name must both be symbols. The field default-init is an expression for the initial value of the slot. It is evaluated each time a new instance is constructed. If it is not specified, the initial content of the slot is undefined. Default values are only useful with a BOA constructor with argument list or a keyword constructor (see below).
Evaluation of a define-structure expression defines a structure
descriptor and a set of procedures to manipulate instances of the
structure. These instances are represented as records by default
(see section Records) but may alternately be lists or vectors. The
accessors and modifiers are marked with compiler declarations so that
calls to them are automatically transformed into appropriate references.
Often, no options are required, so a simple call to
define-structure looks like:
(define-structure foo a b c)
This defines a type descriptor foo, a constructor
make-foo, a predicate foo?, accessors foo-a,
foo-b, and foo-c, and modifiers set-foo-a!,
set-foo-b!, and set-foo-c!.
In general, if no options are specified, define-structure defines
the following (using the simple call above as an example):
record-type?.
"make-" followed by the name of
the structure, e.g. `make-foo'. The number of arguments accepted
by the constructor is the same as the number of slots; the arguments are
the initial values for the slots, and the order of the arguments matches
the order of the slot definitions.
"?", e.g. `foo?'. The predicate is a procedure of one
argument, which returns #t if its argument is a record of the
type defined by this structure definition, and #f otherwise.
"set-", the name of the accessor, and
"!", e.g. `set-foo-a!'. The modifier is a procedure of
two arguments, the first of which must be a record of the type defined
by this structure definition, and the second of which may be any object.
The modifier modifies the contents of the corresponding slot in that
record to be that object, and returns an unspecified value.
When options are not supplied, (name) may be abbreviated to
name. This convention holds equally for structure-options
and slot-options. Hence, these are equivalent:
(define-structure foo a b c) (define-structure (foo) (a) b (c))
as are
(define-structure (foo keyword-constructor) a b c) (define-structure (foo (keyword-constructor)) a b c)
When specified as option values, false and nil are
equivalent to #f, and true and t are equivalent to
#t.
Possible slot-options are:
#f, this specifies that no
modifier should be created for the slot.
Possible structure-options are:
#f, the predicate
is not defined at all. Otherwise, name must be a symbol, and
the predicate is defined with that symbol as its name.
"copy-" followed by the structure name (e.g.
`copy-foo'). If name is #f, the copier is not
defined. Otherwise, name must be a symbol, and the copier is
defined with that symbol as its name.
set-record-type-unparser-method!.
If name is not given, a constructor is defined with the default
name and arguments (see above). If name is #f, no
constructor is defined; argument-list may not be specified in this
case. Otherwise, name must be a symbol, and a constructor is
defined with that symbol as its name. If name is a symbol,
argument-list is optionally allowed; if it is omitted, the
constructor accepts one argument for each slot in the structure
definition, in the same order in which the slots appear in the
definition. Otherwise, argument-list must be a lambda list
(see section Lambda Expressions), and each of the parameters of the lambda
list must be the name of a slot in the structure. The arguments
accepted by the constructor are defined by this lambda list. Any slot
that is not specified by the lambda list is initialized to the
default-init as specified above; likewise for any slot specified
as an optional parameter when the corresponding argument is not
supplied.
If the constructor option is specified, the default constructor
is not defined. Additionally, the constructor option may be
specified multiple times to define multiple constructors with
different names and argument lists.
(define-structure (foo (constructor make-foo (#!optional a b))) (a 6 read-only #t) (b 9))
"make-" followed by the name of the structure (e.g.
`make-foo'). Otherwise, name must be a symbol, and a keyword
constructor is defined with this symbol as its name.
If the keyword-constructor option is specified, the default
constructor is not defined. Additionally, the
keyword-constructor option may be specified multiple times to
define multiple keyword constructors; this is usually not done since
such constructors would all be equivalent.
(define-structure (foo (keyword-constructor make-bar)) a b) (foo-a (make-bar 'b 20 'a 19)) => 19
conc-name option can be
used to specify an alternative. If name is not given, the prefix
is the name of the structure followed by a hyphen (the default). If
name is #f, the slot names are used directly, without
prefix. Otherwise, name must a symbol, and that symbol is used as
the prefix.
(define-structure (foo (conc-name moby/)) a b)
defines accessors moby/a and moby/b, and modifiers
set-moby/a! and set-moby/b!.
(define-structure (foo (conc-name #f)) a b)
defines accessors a and b, and modifiers set-a! and
set-b!.
type
option overrides this default, allowing the programmer to specify that
the structure be implemented using another data type. The option value
representation-type specifies the alternate data type; it is
allowed to be one of the symbols vector or list, and the
data type used is the one corresponding to the symbol.
If this option is given, and the named option is not specified,
the representation will not be tagged, and neither a predicate nor a
type descriptor will be defined; also, the print-procedure
option may not be given.
(define-structure (foo (type list)) a b) (make-foo 1 2) => (1 2)
type option and
specifies that the structure instances be tagged to make them
identifiable as instances of this structure type. In the usual case,
where expression is not given, the named option causes a
type descriptor and predicate to be defined for the structure (recall
that the type option without named suppresses their
definition), and also defines a default unparser method for the
structure instances (which can be overridden by the
print-procedure option). If the default unparser method is not
wanted then the print-procedure option should be specified as
#F. This cases the structure to be printed in its native
representation, as a list or vector, which includes the type descriptor.
The type descriptor is a unique object, not a record type, that
describes the structure instances and is additionally stored in the
structure instances to identify them: if the representation type is
vector, the type descriptor is stored in the zero-th slot of the
vector, and if the representation type is list, it is stored as
the first element of the list.
(define-structure (foo (type vector) named) a b c) (vector-ref (make-foo 1 2 3) 0) => #[structure-type 52]
If expression is specified, it is an expression that is evaluated to yield a tag object. The expression is evaluated once when the structure definition is evaluated (to specify the unparser method), and again whenever a predicate or constructor is called. Because of this, expression is normally a variable reference or a constant. The value yielded by expression may be any object at all. That object is stored in the structure instances in the same place that the type descriptor is normally stored, as described above. If expression is specified, no type descriptor is defined, only a predicate.
(define-structure (foo (type vector) (named 'foo)) a b c) (vector-ref (make-foo 1 2 3) 0) => foo
type option.
Offset must be an exact non-negative integer and specifies the
number of slots to leave open at the beginning of the structure instance
before the specified slots are allocated. Specifying an offset of
zero is equivalent to omitting the initial-offset option.
If the named option is specified, the structure tag appears in
the first slot, followed by the "offset" slots, and then the regular
slots. Otherwise, the "offset" slots come first, followed by the
regular slots.
(define-structure (foo (type vector) (initial-offset 3)) a b c) (make-foo 1 2 3) => #(() () () 1 2 3)
The essential differences between MIT Scheme's define-structure
and Common Lisp's defstruct are:
keyword-constructor.
&aux in Scheme lambda lists, this
functionality is not implemented.
copier procedure is defined.
foo is
given the name set-foo!.
foo instead of :foo.
false, nil, true, and t
are treated as if the appropriate boolean constant had been specified
instead.
print-function option is named print-procedure. Its
argument is a procedure of two arguments (the unparser state and the
structure instance) rather than three as in Common Lisp.
named option may optionally take an argument, which is
normally the name of a variable (any expression may be used, but it is
evaluated whenever the tag name is needed). If used, structure
instances will be tagged with that variable's value. The variable must
be defined when define-structure is evaluated.
type option is restricted to the values vector and
list.
include option is not implemented.
A predicate is a procedure that always returns a boolean value
(#t or #f). An equivalence predicate is the
computational analogue of a mathematical equivalence relation (it is
symmetric, reflexive, and transitive). Of the equivalence predicates
described in this section, eq? is the finest or most
discriminating, and equal? is the coarsest. eqv? is
slightly less discriminating than eq?.
eqv? procedure defines a useful equivalence relation on
objects. Briefly, it returns #t if obj1 and obj2
should normally be regarded as the same object.
The eqv? procedure returns #t if:
#t or both #f.
(string=? (symbol->string obj1)
(symbol->string obj2))
=> #t
= procedure, and are either both exact or both
inexact (see section Numbers).
char=? procedure (see section Characters).
The eqv? procedure returns #f if:
#t but the other is
#f.
(string=? (symbol->string obj1)
(symbol->string obj2))
=> #f
= procedure
returns #f.
char=?
procedure returns #f.
Some examples:
(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
The following examples illustrate cases in which the above rules do not
fully specify the behavior of eqv?. All that can be said about
such cases is that the value returned by eqv? must be a boolean.
(eqv? "" "") => unspecified
(eqv? '#() '#()) => unspecified
(eqv? (lambda (x) x)
(lambda (x) x)) => unspecified
(eqv? (lambda (x) x)
(lambda (y) y)) => unspecified
The next set of examples shows the use of eqv? with procedures
that have local state. gen-counter must return a distinct
procedure every time, since each procedure has its own internal counter.
gen-loser, however, returns equivalent procedures each time,
since the local state does not affect the value or side effects of the
procedures.
(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))
=> unspecified
(letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
(g (lambda () (if (eqv? f g) 'both 'g)))
(eqv? f g))
=> unspecified
(letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
(g (lambda () (if (eqv? f g) 'g 'both)))
(eqv? f g))
=> #f
Objects of distinct types must never be regarded as the same object.
Since it is an error to modify constant objects (those returned by
literal expressions), the implementation may share structure between
constants where appropriate. Thus the value of eqv? on constants
is sometimes unspecified.
(let ((x '(a))) (eqv? x x)) => #t (eqv? '(a) '(a)) => unspecified (eqv? "a" "a") => unspecified (eqv? '(b) (cdr '(a b))) => unspecified
Rationale: The above definition of 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.
eq? is similar to eqv? except that in some cases it is
capable of discerning distinctions finer than those detectable by
eqv?.
eq? and eqv? are guaranteed to have the same behavior on
symbols, booleans, the empty list, pairs, records, and non-empty strings
and vectors. 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 eqv? would also return
true. eq? may also behave differently from eqv? on empty
vectors and empty strings.
(eq? 'a 'a) => #t (eq? '(a) '(a)) => unspecified (eq? (list 'a) (list 'a)) => #f (eq? "a" "a") => unspecified (eq? "" "") => unspecified (eq? '() '()) => #t (eq? 2 2) => unspecified (eq? #\A #\A) => unspecified (eq? car car) => #t (let ((n (+ 2 3))) (eq? n n)) => unspecified (let ((x '(a))) (eq? x x)) => #t (let ((x '#())) (eq? x x)) => #t (let ((p (lambda (x) x))) (eq? p p)) => #t
Rationale: It will usually be possible to implement eq? much more
efficiently than 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 eqv? of two numbers in
constant time, whereas eq? implemented as pointer comparison will
always finish in constant time. eq? may be used like eqv?
in applications using procedures to implement objects with state since
it obeys the same constraints as eqv?.
equal? recursively compares the contents of pairs, vectors, and
strings, applying eqv? on other objects such as numbers, symbols,
and records. A rule of thumb is that objects are generally
equal? if they print the same. equal? may fail to
terminate if its arguments are circular data structures.
(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)) => unspecified
(This section is largely taken from the Revised^4 Report on the Algorithmic Language Scheme.)
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 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 number, complex, real, rational, and 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 fixnum and flonum.
Mathematically, numbers may be arranged into a tower of subtypes in which each level is a subset of the level above it:
number complex real rational integer
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
number?, complex?, real?, rational?, and
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.
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.
Scheme numbers are either exact or inexact. A number is exact if it was written as an exact constant or was derived from exact numbers using only exact operations. A number is inexact if it was written as an inexact constant, if it was derived using inexact ingredients, or if it was derived using inexact operations. Thus inexactness is a contagious property of a number.
If two implementations produce exact results for a computation that did not involve inexact intermediate results, the two ultimate results will be mathematically equivalent. This is generally not true of computations involving 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 + should always produce exact results
when given exact arguments. If the operation is unable to produce an
exact result, then it may either report the violation of an
implementation restriction or it may silently coerce its result to an
inexact value. See section Implementation restrictions.
With the exception of inexact->exact, the operations described in
this section must generally return inexact results when given any
inexact arguments. An operation may, however, return an 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 exact zero may produce an exact zero result, even if the other
argument is inexact.
Implementations of Scheme are not required to implement the whole tower of subtypes (see section 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 real may still be quite useful.(1)
Implementations may also support only a limited range of numbers of any type, subject to the requirements of this section. The supported range for exact numbers of any type may be different from the supported range for inexact numbers of that type. For example, an implementation that uses flonums to represent all its inexact real numbers may support a practically unbounded range of exact integers and rationals while limiting the range of inexact reals (and therefore the range of inexact integers and rationals) to the dynamic range of the flonum format. Furthermore the gaps between the representable inexact integers and rationals 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 length, vector-length, and
string-length procedures must return an exact 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:
* gcd modulo + imag-part numerator - inexact->exact quotient abs lcm rationalize angle magnitude real-part ceiling make-polar remainder denominator make-rectangular round expt max truncate floor min
Implementations are encouraged, but not required, to support exact
integers and exact rationals of practically unlimited size and
precision, and to implement the above procedures and the /
procedure in such a way that they always return exact results when given
exact arguments. If one of these procedures is unable to deliver an
exact result when given exact arguments, then it may either report a
violation of an implementation restriction or it may silently coerce its
result to an inexact number. Such a coercion may cause an error
later.
An implementation may use floating point and other approximate representation strategies for inexact numbers. 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.
In particular, implementations that use flonum representations must
follow these rules: A 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 sqrt, when applied to exact arguments,
to produce exact answers whenever possible (for example the square root
of an exact 4 ought to be an exact 2). If, however, an exact number is
operated upon so as to produce an inexact result (as by sqrt),
and if the result is represented as a flonum, then the most precise
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 flonum format available.
Although Scheme allows a variety of written notations for numbers, any particular implementation may support only some of them.(2) For example, an implementation in which all numbers are real need not support the rectangular and polar notations for complex numbers. If an implementation encounters an exact numerical constant that it cannot represent as an exact number, then it may either report a violation of an implementation restriction or it may silently represent the constant by an inexact number.
A number may be written in binary, octal, decimal, or hexadecimal by the
use of a radix prefix. The radix prefixes are #b (binary),
#o (octal), #d (decimal), and #x (hexadecimal).
With no radix prefix, a number is assumed to be expressed in
decimal.
A numerical constant may be specified to be either exact or inexact by a
prefix. The prefixes are #e for exact, and #i for
inexact. An exactness 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 inexact or exact. It is
inexact if it contains a decimal point, an exponent, or a #
character in the place of a digit, otherwise it is exact.
In systems with 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 inexact representation. The letters
s, f, d, and l specify the use of
short, single, double, and long precision,
respectively. (When fewer than four internal 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 e specifies the default precision for the
implementation. The default precision has at least as much precision as
double, but implementations may wish to allow this default to be
set by the user.
3.14159265358979F0
Round to single --- 3.141593
0.6L0
Extend to long --- .600000000000000
See section Entry Format, for a summary of the naming conventions used to specify restrictions on the types of arguments to numerical routines. The examples used in this section assume that any numerical constant written using an exact notation is indeed represented as an exact number. Some examples also assume that certain numerical constants written using an inexact notation can be represented without loss of accuracy; the inexact constants were chosen so that this is likely to be true in implementations that use flonums to represent inexact numbers.
#t if the object is of the
named type, and otherwise they return #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.(3)
If z is an inexact complex number, then (real? z) is
true if and only if (zero? (imag-part z)) is true. If
x is an inexact real number, then (integer? x) is
true if and only if (= x (round x)).
(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
Note: The behavior of these type predicates on inexact numbers is unreliable, since any inaccuracy may affect the result.
#t if their arguments are (respectively):
equal, monotonically increasing, monotonically decreasing, monotonically
nondecreasing, or monotonically nonincreasing.
These predicates are transitive. Note that the traditional implementations of these predicates in Lisp-like languages are not transitive.
Note: While it is not an error to compare inexact numbers using these
predicates, the results may be unreliable because a small inaccuracy may
affect the result; this is especially true of = and zero?.
When in doubt, consult a numerical analyst.
#t or #f. See note above regarding inexact
numbers.
(max 3 4) => 4 ; exact (max 3.9 4) => 4.0 ; inexact
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 min or 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.(4)
(+ 3 4) => 7 (+ 3) => 3 (+) => 0 (* 4) => 4 (*) => 1
(- 3 4) => -1 (- 3 4 5) => -6 (- 3) => -3 (/ 3 4 5) => 3/20 (/ 3) => 1/3
(1+ z) is equivalent to (+ z 1); (-1+ z) is
equivalent to (- z 1).
abs returns the magnitude of its argument.
(abs -7) => 7
(quotient n1 n2) => n3 (remainder n1 n2) => n4 (modulo n1 n2) => n4
For integers n1 and n2 with n2 not equal to 0,
(= n1
(+ (* n2 (quotient n1 n2))
(remainder n1 n2)))
=> #t
provided all numbers involved in that computation are exact.
The value returned by quotient always has the sign of the product
of its arguments. remainder and modulo differ on negative
arguments -- the remainder always has the sign of the dividend,
the modulo always has the sign of the divisor:
(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
(integer-floor n1 n2) (floor (/ n1 n2))
However, the former is faster and does not produce an intermediate result.
integer-divide is equivalent to performing both quotient
and remainder at once. The result of integer-divide is an
object with two components; the procedures
integer-divide-quotient and integer-divide-remainder
select those components. These procedures are useful when both the
quotient and remainder are needed; often computing both of these numbers
simultaneously is much faster than computing them separately.
For example, the following are equivalent:
(lambda (n d)
(cons (quotient n d)
(remainder n d)))
(lambda (n d)
(let ((qr (integer-divide n d)))
(cons (integer-divide-quotient qr)
(integer-divide-remainder qr))))
(gcd 32 -36) => 4 (gcd) => 0 (lcm 32 -36) => 288 (lcm 32.0 -36) => 288.0 ; inexact (lcm) => 1
(numerator (/ 6 4)) => 3 (denominator (/ 6 4)) => 2 (denominator (exact->inexact (/ 6 4))) => 2.0
floor returns the largest
integer not larger than x. ceiling returns the smallest
integer not smaller than x. truncate returns the integer
closest to x whose absolute value is not larger than the absolute
value of x. round returns the closest integer to x,
rounding to even when x is halfway between two integers.
Rationale: round rounds to even for consistency with the rounding
modes required by the IEEE floating point standard.
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 inexact->exact procedure (or use one of
the procedures below).
(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
(floor->exact x) (inexact->exact (floor x))
except that the former is faster and has fewer range restrictions.
rationalize returns the simplest rational number differing
from x by no more than y. A rational number r1 is
simpler than another rational number r2 if
r1=p1/q1 and r2=p2/q2 (both
in lowest terms) and |p1|<=|p2| and
|q1|<=|q2|. 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.
(rationalize (inexact->exact .3) 1/10) => 1/3 ; exact (rationalize .3 1/10) => #i1/3 ; inexact
rationalize->exact is similar to rationalize except that
it always returns an exact result.
simplest-rational returns the simplest rational number between
x and y inclusive; simplest-exact-rational is similar
except that it always returns an exact result.
These procedures implement the same functionality as rationalize
and rationalize->exact, except that they specify the input range
by its endpoints; rationalize specifies the range by its center
point and its (half-) width.
log
computes the natural logarithm of z (not the base ten logarithm).
asin, acos, and atan compute arcsine, arccosine,
and arctangent, respectively. The two-argument variant of atan
computes (angle (make-rectangular x y)) (see
below).
In general, the mathematical functions log, arcsine, arccosine, and arctangent are multiply defined. For nonzero real x, the value of log x is defined to be the one whose imaginary part lies in the range minus pi (exclusive) to pi (inclusive). log 0 is undefined. The value of log z when z is complex is defined according to the formula With log defined this way, the values of arcsine, arccosine, and arctangent are according to the following formulae: The above specification follows Common Lisp: the Language, which in turn cites Principal Values and Branch Cuts in Complex APL; 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.
make-rectangular and make-polar return z,
real-part returns x1, imag-part returns x2,
magnitude returns x3, and angle returns x4.
In the case of angle, whose value is not uniquely determined by
the preceding rule, the value returned will be the one in the range
minus pi (exclusive) to pi (inclusive).
conjugate returns the complex conjugate of z.
exact->inexact returns an inexact representation of z. The
value returned is the inexact number that is numerically closest to the
argument. If an exact argument has no reasonably close inexact
equivalent, then a violation of an implementation restriction may be
reported; MIT Scheme signals an error of type
condition-type:bad-range-argument in this case.
inexact->exact returns an exact representation of z. The
value returned is the exact number that is numerically closest to the
argument. If an inexact argument has no reasonably close exact
equivalent, then a violation of an implementation restriction may be
reported; in MIT Scheme this case does not occur because all inexact
numbers are representable as exact numbers.
These procedures implement the natural one-to-one correspondence between exact and inexact integers throughout an implementation-dependent range. See section Implementation restrictions.
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
(let ((number number)
(radix radix))
(eqv? number
(string->number (number->string number radix)
radix)))
is true. It is an error if no possible result makes this expression true.
If number 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; otherwise the format of the result is unspecified.
The result returned by number->string never contains an explicit
radix prefix.
Note: The error case can occur only when number is not a complex number or is a complex number with an non-rational real or imaginary part.
Rationale: If number 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.
number->string when
number is a flonum (and consequently controls all printing of
flonums); it can have the following values:
normal, which is the initial value of this variable,
causes flonums to be printed with full precision. number->string
uses as many digits as are necessary to display all of the information
in the flonum. This value may also be specified as a list (normal
n) where n is an exact integer; n is ignored.
(relative n), where n is an exact positive
integer, constrains number->string to represent the flonum using
at most n significant digits. number->string rounds the
result so that it is as accurate as possible. For example:
(number->string (* 4 (atan 1 1)))
=> "3.141592653589793"
(fluid-let ((flonum-unparser-cutoff '(relative 5)))
(number->string (* 4 (atan 1 1))))
=> "3.1416"
(fluid-let ((flonum-unparser-cutoff '(relative 5)))
(number->string (* 4000 (atan 1 1))))
=> "3141.6"
(absolute n), where n is an exact integer,
constrains number->string to represent the flonum by rounding it
at the nth digit to the right of the decimal point; if n is
negative, the number is rounded (- n) digits to the left of
the decimal point. For example:
(fluid-let ((flonum-unparser-cutoff '(absolute 5)))
(number->string (* 4 (atan 1 1))))
=> "3.14159"
(fluid-let ((flonum-unparser-cutoff '(absolute 5)))
(number->string (* 4000 (atan 1 1))))
=> "3141.59265"
(fluid-let ((flonum-unparser-cutoff '(absolute -4)))
(number->string (* 4e10 (atan 1 1))))
=> "31415930000."
(fluid-let ((flonum-unparser-cutoff '(absolute -5)))
(number->string (* 4e10 (atan 1 1))))
=> "31415900000."
If flonum-unparser-cutoff is bound to a value different from
those described here, number->string issues a warning and acts as
though it had been bound to normal.
"#o177"). If radix is not supplied, then the default radix
is 10. If string is not a syntactically valid notation for a
number, then string->number returns #f.
(string->number "100") => 100 (string->number "100" 16) => 256 (string->number "1e2") => 100.0 (string->number "15##") => 1500.0
Note that a numeric representation using a decimal point or an exponent
marker is not recognized unless radix is 10.
This section describes numerical operations that are restricted forms of the operations described above. These operations are useful because they compile very efficiently. However, care should be exercised: if used improperly, these operations can return incorrect answers, or even malformed objects that confuse the garbage collector.
A fixnum is an exact integer that is small enough to fit in a machine word. In MIT Scheme, fixnums are typically 24 or 26 bits, depending on the machine; it is reasonable to assume that fixnums are at least 24 bits. Fixnums are signed; they are encoded using 2's complement.
All exact integers that are small enough to be encoded as fixnums are
always encoded as fixnums -- in other words, any exact integer that is
not a fixnum is too big to be encoded as such. For this reason, small
constants such as 0 or 1 are guaranteed to be fixnums.
#t if object is a fixnum; otherwise returns
#f.
Here is an expression that determines the largest fixnum:
(let loop ((n 1))
(if (fix:fixnum? n)
(loop (* n 2))
(- n 1)))
A similar expression determines the smallest fixnum.
(fix:zero? fixnum) (fix:= fixnum 0)
Similarly, fix:positive? and fix:negative? produce code
identical to equivalent expressions using fix:> and fix:<.
integer-divide, except that its arguments
and its results must be fixnums. It should be used in conjunction with
integer-divide-quotient and integer-divide-remainder.
The following are bitwise-logical operations on fixnums.
(fix:not 0) => -1 (fix:not -1) => 0 (fix:not 1) => -2 (fix:not -34) => 33
(fix:and #x43 #x0f) => 3 (fix:and #x43 #xf0) => #x40
(fix:andc #x43 #x0f) => #x40 (fix:andc #x43 #xf0) => 3
(fix:or #x40 3) => #x43 (fix:or #x41 3) => #x43
(fix:xor #x40 3) => #x43 (fix:xor #x41 3) => #x42
(fix:lsh 1 10) => #x400 (fix:lsh #x432 -10) => 1 (fix:lsh -1 3) => -8 (fix:lsh -128 -4) => #x3FFFF8
A flonum is an inexact real number that is implemented as a
floating-point number. In MIT Scheme, all inexact real numbers are
flonums. For this reason, constants such as 0. and 2.3
are guaranteed to be flonums.
#t if object is a flonum; otherwise returns #f.
(flo:- 0.
flonum).
atan with two arguments. When
compiled, it does not check the types of its arguments.
MIT Scheme provides a facility for generating pseudo-random numbers. The current implementation is a "subtract-with-carry" random-number generator, based on the algorithm from A New Class of Random Number Generators, George Marsaglia and Arif Zaman, The Annals of Applied Probability, Vol. 1, No. 3, 1991. At the time it was implemented, this was a good algorithm for general purposes, but the state of the art in random-number generation is constantly changing. If necessary, the implementation will be updated to use a new algorithm while retaining the same interface.
The interface described here is very similar to that of Common Lisp.
random returns a
pseudo-random number between zero (inclusive) and modulus
(exclusive). The exactness of the returned number is the same as the
exactness of modulus. Additionally, if modulus is an exact
integer, the returned number will be also. Usually, modulus is
either an exact integer or an inexact real; the current implementation
has been tuned to make these two cases fast.
If state is given and not #f, it must be a random-state
object; otherwise, it defaults to the value of the variable
*random-state*. This object is used to maintain the state of the
pseudo-random-number generator and is altered as a side effect of the
random procedure.
(random 1.0) => .32744744667719056 (random 1.0) => .01668326768172354 (random 10) => 3 (random 10) => 8 (random 100) => 38 (random 100) => 63 (random 100/3) => 130501475769920525/6755399441055744 (random 100/3) => 170571694016427575/13510798882111488
flo:random-unit
returns a pseudo-random number between zero inclusive and one exclusive;
the returned number is always a flonum and therefore an inexact real
number. flo:random-unit is equivalent to random with a
modulus of 1.0, except that it is faster.
The next three definitions concern random-state objects. In addition to
these definitions, it is important to know that random-state objects are
specifically designed so that they can be saved to disk using the
fasdump procedure, and later restored using the fasload
procedure. This allows a particular random-state object to be saved in
order to replay a particular pseudo-random sequence.
random uses by default. A call to random will perform a
side effect on this data structure. This variable may be changed, using
set! or fluid-let, to hold a new random-state object.
*random-state*, or as the state
argument to random. If state is not given or #f,
make-random-state returns a copy of the current
random-number state object (the value of the variable
*random-state*). If state is a random-state object, a copy
of that object is returned. If state is #t, then a new
random-state object is returned that has been "randomly" initialized
by some means (such as by a time-of-day clock).
#t if object is a random-state object, otherwise
returns #f.
Characters are objects that represent printed characters, such as letters and digits.(5)
Characters are written using the notation #\character or
#\character-name. For example:
#\a ; lowercase letter #\A ; uppercase letter #\( ; left parenthesis #\space ; the space character #\newline ; the newline character
Case is significant in #\character, but not in
#\character-name. If character in
#\character is a letter, character must be followed
by a delimiter character such as a space or parenthesis. Characters
written in the #\ notation are self-evaluating; you don't need to
quote them.
A character name may include one or more bucky bit prefixes to indicate that the character includes one or more of the keyboard shift keys Control, Meta, Super, Hyper, or Top (note that the Control bucky bit prefix is not the same as the ASCII control key). The bucky bit prefixes and their meanings are as follows (case is not significant):
Key Bucky bit prefix Bucky bit --- ---------------- --------- Meta M- or Meta- 1 Control C- or Control- 2 Super S- or Super- 4 Hyper H- or Hyper- 8 Top T- or Top- 16
For example,
#\c-a ; Control-a #\meta-b ; Meta-b #\c-s-m-h-a ; Control-Meta-Super-Hyper-A
The following character-names are supported, shown here with their ASCII equivalents:
Character Name ASCII Name -------------- ---------- altmode ESC backnext US backspace BS call SUB linefeed LF page FF return CR rubout DEL space tab HT
In addition, #\newline is either #\linefeed or
#\return, depending on the operating system that Scheme is
running under. All of the standard ASCII names for non-printing
characters are supported:
NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US DEL
(char->name #\a) => "a" (char->name #\space) => "Space" (char->name #\c-a) => "C-a" (char->name #\control-a) => "C-a"
Slashify?, if specified and true, says to insert the necessary
backslash characters in the result so that read will parse it
correctly. In other words, the following generates the external
representation of char:
(string-append "#\\" (char->name char #t))
If slashify? is not specified, it defaults to #f.
name->char signals
an error.
(name->char "a") => #\a (name->char "space") => #\Space (name->char "c-a") => #\C-a (name->char "control-a") => #\C-a
#t if the specified characters are have the appropriate
order relationship to one another; otherwise returns #f. The
-ci procedures don't distinguish uppercase and lowercase letters.
Character ordering follows these rules:
(char<? #\0 #\9) returns
#t.
(char<? #\A
#\B) returns #t.
(char<? #\a
#\b) returns #t.
In addition, MIT Scheme orders those characters that satisfy
char-standard? the same way that ASCII does. Specifically,
all the digits precede all the uppercase letters, and all the upper-case
letters precede all the lowercase letters.
Characters are ordered by first comparing their bucky bits part and then their code part. In particular, characters without bucky bits come before characters with bucky bits.
#t if object is a character; otherwise returns
#f.
(char-ci=? char
char2).
char->digit returns #f.
Note that this procedure is insensitive to the alphabetic case of char.
(char->digit #\8) => 8 (char->digit #\e 16) => 14 (char->digit #\e) => #f
digit->char
returns #f.
(digit->char 8) => #\8 (digit->char 14 16) => #\E
An MIT Scheme character consists of a code part and a bucky bits part. The MIT Scheme set of characters can represent more characters than ASCII can; it includes characters with Super, Hyper, and Top bucky bits, as well as Control and Meta. Every ASCII character corresponds to some MIT Scheme character, but not vice versa.(6)
MIT Scheme uses a 7-bit ASCII character code with 5 bucky bits. The least significant bucky bit, Meta, is stored adjacent to the MSB of the character code, allowing the least significant 8 bits of a character object to be interpreted as ordinary ASCII with a meta bit. This is compatible with standard practice for 8-bit characters when meta bits are employed.
char-code and char-bits to
extract the code and bucky bits from the character. If 0 is
specified for bucky-bits, make-char produces an ordinary
character; otherwise, the appropriate bits are turned on as follows:
1 Meta 2 Control 4 Super 8 Hyper 16 Top
For example,
(make-char 97 0) => #\a (make-char 97 1) => #\M-a (make-char 97 2) => #\C-a (make-char 97 3) => #\C-M-a
(char-bits #\a) => 0 (char-bits #\m-a) => 1 (char-bits #\c-a) => 2 (char-bits #\c-m-a) => 3
(char-code #\a) => 97 (char-code #\c-a) => 97
char->integer returns the character code representation for
char. integer->char returns the character whose character
code representation is k.
In MIT Scheme, if (char-ascii? char) is true, then
(eqv? (char->ascii char) (char->integer char))
However, this behavior is not required by the Scheme standard, and code that depends on it is not portable to other implementations.
These procedures implement order isomorphisms between the set of
characters under the char<=? ordering and some subset of the
integers under the <= ordering. That is, if
(char<=? a b) => #t and (<= x y) => #t
and x and y are in the range of char->integer,
then
(<= (char->integer a)
(char->integer b)) => #t
(char<=? (integer->char x)
(integer->char y)) => #t
Note: if char is a character constant for which
char->integer returns an integer strictly less than 256, then the
compiler will constant-fold the call, replacing it with the
corresponding integer. Likewise, if k is an integer constant
strictly less than 256, the compiler will constant-fold a call to
integer->char, replacing it with the corresponding character.
This is a very useful way to denote unusual character constants or
ASCII codes.
char->integer is defined to be the exact
non-negative integers that are less than the value of this variable
(exclusive).
MIT Scheme internally uses ASCII codes for I/O, and stores character objects in a fashion that makes it convenient to convert between ASCII codes and characters. Also, character strings are implemented as byte vectors whose elements are ASCII codes; these codes are converted to character objects when accessed. For these reasons it is sometimes desirable to be able to convert between ASCII codes and characters.
Not all characters can be represented as ASCII codes. A character that has an equivalent ASCII representation is called an ASCII character.
#f.
In the current implementation, the characters that satisfy this
predicate are those in which the Control, Super, Hyper, and Top bucky
bits are turned off. All characters for which the char-bits
procedure returns 0 or 1 (i.e. no bucky bits, or just
Meta) count as legal ASCII characters.
condition-type:bad-range-argument is signalled if char
doesn't have an ASCII representation.
MIT Scheme's character-set abstraction is used to represent groups of characters, such as the letters or digits. Character sets may contain only ASCII characters; in the future this may be changed to allow the full range of characters.
There is no meaningful external representation for character sets; use
char-set-members to examine their contents. There is (at
present) no specific equivalence predicate for character sets; use
equal? for this purpose.
#t if object is a character set; otherwise returns
#f.(7)
char-set-members.
Alphabetic characters are the 52 upper and lower case letters.
Numeric characters are the 10 decimal digits. Alphanumeric
characters are those in the union of these two sets. Whitespace
characters are #\space, #\tab, #\page,
#\linefeed, and #\return. Graphic characters are
the printing characters and #\space. Standard characters
are the printing characters, #\space, and #\newline.
These are the printing characters:
! " # $ % & ' ( ) * + , - . /
0 1 2 3 4 5 6 7 8 9
: ; < = > ? @
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
[ \ ] ^ _ `
a b c d e f g h i j k l m n o p q r s t u v w x y z
{ | } ~
#t if the char is in char-set; otherwise
returns #f.
char-set returns an empty
character set.
(apply char-set
chars).
predicate->char-set creates and returns a character set
consisting of the ASCII characters for which predicate is
true.
A string is a mutable sequence of characters. In the current
implementation of MIT Scheme, the elements of a string must all
satisfy the predicate char-ascii?; if someone ports MIT
Scheme to a non-ASCII operating system this requirement will
change.
A string is written as a sequence of characters enclosed within double
quotes " ". To include a double quote inside a string, precede
the double quote with a backslash \ (escape it), as in
"The word \"recursion\" has many meanings."
The printed representation of this string is
The word "recursion" has many meanings.
To include a backslash inside a string, precede it with another backslash; for example,
"Use #\\Control-q to quit."
The printed representation of this string is
Use #\Control-q to quit.
The effect of a backslash that doesn't precede a double quote or
backslash is unspecified in standard Scheme, but MIT Scheme
specifies the effect for three other characters: \t, \n,
and \f. These escape sequences are respectively translated into
the following characters: #\tab, #\newline, and
#\page. Finally, a backslash followed by exactly three octal
digits is translated into the character whose ASCII code is those
digits.
If a string literal is continued from one line to another, the string
will contain the newline character (#\newline) at the line break.
Standard Scheme does not specify what appears in a string literal at a
line break.
The length of a string is the number of characters that it contains. This number is an exact non-negative integer that is established when the string is created (but see section Variable-Length Strings). Each character in a string has an index, which is a number that indicates the character's position in the string. The index of the first (leftmost) character in a string is 0, and the index of the last character is one less than the length of the string. The valid indexes of a string are the exact non-negative integers less than the length of the string.
A number of the string procedures operate on substrings. A substring is a segment of a string, which is specified by two integers start and end satisfying these relationships:
0 <= start <= end <= (string-length string)
Start is the index of the first character in the substring, and end is one greater than the index of the last character in the substring. Thus if start and end are equal, they refer to an empty substring, and if start is zero and end is the length of string, they refer to all of string.
Some of the procedures that operate on strings ignore the difference between uppercase and lowercase. The versions that ignore case include `-ci' (for "case insensitive") in their names.
char-ascii?.
(make-string 10 #\x) => "xxxxxxxxxx"
char-ascii?.
(string #\a) => "a" (string #\a #\b #\c) => "abc" (string #\a #\space #\b #\space #\c) => "a b c" (string) => ""
For compatibility with old code, char->string is a synonym for
this procedure.
list->string returns a newly allocated string formed from the
elements of char-list. This is equivalent to (apply string
char-list). The inverse of this operation is
string->list.
(list->string '(#\a #\b)) => "ab" (string->list "Hello") => (#\H #\e #\l #\l #\o)
Note regarding variable-length strings: the maximum length of the result depends only on the length of string, not its maximum length. If you wish to copy a string and preserve its maximum length, do the following:
(define (string-copy-preserving-max-length string)
(let ((length))
(dynamic-wind
(lambda ()
(set! length (string-length string))
(set-string-length! string (string-maximum-length string)))
(lambda ()
(string-copy string))
(lambda ()
(set-string-length! string length)))))
#t if object is a string; otherwise returns
#f.
(string? "Hi") => #t (string? 'Hi) => #f
(string-length "") => 0 (string-length "The length") => 10
#t if string has zero length; otherwise returns
#f.
(string-null? "") => #t (string-null? "Hi") => #f
(string-ref "Hello" 1) => #\e (string-ref "Hello" 5) error--> 5 not in correct range
char-ascii?.
(define str "Dog") => unspecified (string-set! str 0 #\L) => unspecified str => "Log" (string-set! str 3 #\t) error--> 3 not in correct range
#t if the two strings (substrings) are the same length
and contain the same characters in the same (relative) positions;
otherwise returns #f. string-ci=? and
substring-ci=? don't distinguish uppercase and lowercase letters,
but string=? and substring=? do.
(string=? "PIE" "PIE") => #t (string=? "PIE" "pie") => #f (string-ci=? "PIE" "pie") => #t (substring=? "Alamo" 1 3 "cola" 2 4) => #t ; compares "la"
(string<? "cat" "dog") => #t (string<? "cat" "DOG") => #f (string-ci<? "cat" "DOG") => #t (string>? "catkin" "cat") => #t ; shorter is lesser
string-compare distinguishes uppercase and lowercase letters;
string-compare-ci does not.
(define (cheer) (display "Hooray!"))
(define (boo) (display "Boo-hiss!"))
(string-compare "a" "b" cheer (lambda() 'ignore) boo)
-| Hooray!
=> unspecified
string-hash returns an exact non-negative integer that can be used
for storing the specified string in a hash table. Equal strings
(in the sense of string=?) return equal (=) hash codes,
and non-equal but similar strings are usually mapped to distinct hash
codes.
string-hash-mod is like string-hash, except that it limits
the result to a particular range based on the exact non-negative integer
k. The following are equivalent:
(string-hash-mod string k) (modulo (string-hash string) k)
#t if the first word in the string
(substring) is capitalized, and any subsequent words are either lower
case or capitalized. Otherwise, they return #f. A word is
defined as a non-null contiguous sequence of alphabetic characters,
delimited by non-alphabetic characters or the limits of the string
(substring). A word is capitalized if its first letter is upper case
and all its remaining letters are lower case.
(map string-capitalized? '("" "A" "art" "Art" "ART"))
=> (#f #t #f #t #f)
#t if all the letters in the string
(substring) are of the correct case, otherwise they return #f.
The string (substring) must contain at least one letter or the
procedures return #f.
(map string-upper-case? '("" "A" "art" "Art" "ART"))
=> (#f #t #f #f #t)
string-capitalize returns a newly allocated copy of string
in which the first alphabetic character is uppercase and the remaining
alphabetic characters are lowercase. For example, "abcDEF"
becomes "Abcdef". string-capitalize! is the destructive
version of string-capitalize: it alters string and returns
an unspecified value. substring-capitalize! destructively
capitalizes the specified part of string.
string-downcase returns a newly allocated copy of string in
which all uppercase letters are changed to lowercase.
string-downcase! is the destructive version of
string-downcase: it alters string and returns an
unspecified value. substring-downcase! destructively changes the
case of the specified part of string.
(define str "ABCDEFG") => unspecified (substring-downcase! str 3 5) => unspecified str => "ABCdeFG"
string-upcase returns a newly allocated copy of string in
which all lowercase letters are changed to uppercase.
string-upcase! is the destructive version of
string-upcase: it alters string and returns an unspecified
value. substring-upcase! destructively changes the case of the
specified part of string.
string-append returns the empty
string ("").
(string-append) => "" (string-append "*" "ace" "*") => "*ace*" (string-append "" "" "") => "" (eq? str (string-append str)) => #f ; newly allocated
(substring "" 0 0) => "" (substring "arduous" 2 5) => "duo" (substring "arduous" 2 8) error--> 8 not in correct range (define (string-copy s) (substring s 0 (string-length s)))
(define (string-head string end) (substring string 0 end))
(define (string-tail string start) (substring string start (string-length string))) (string-tail "uncommon" 2) => "common"
#\space. If k is less than the
length of string, the resulting string is a truncated form of
string. string-pad-left adds padding characters or
truncates from the beginning of the string (lowest indices), while
string-pad-right does so at the end of the string (highest
indices).
(string-pad-left "hello" 4) => "ello" (string-pad-left "hello" 8) => " hello" (string-pad-left "hello" 8 #\*) => "***hello" (string-pad-right "hello" 4) => "hell" (string-pad-right "hello" 8) => "hello "
string-trim) both ends of
string; (string-trim-left) the beginning of string;
or (string-trim-right) the end of string. Char-set
defaults to char-set:not-whitespace.
(string-trim " in the end ") => "in the end"
(string-trim " ") => ""
(string-trim "100th" char-set:numeric) => "100"
(string-trim-left "-.-+-=-" (char-set #\+))
=> "+-=-"
(string-trim "but (+ x y) is" (char-set #\( #\)))
=> "(+ x y)"
#f if string does not contain pattern.
(substring? "rat" "pirate") => 2
(substring? "rat" "outrage") => #f
(substring? "" any-string) => 0
(if (substring? "moon" text)
(process-lunar text)
'no-moon)
#f if char does not appear in the
string. For the substring procedures, the index returned is relative to
the entire string, not just the substring. The -ci procedures
don't distinguish uppercase and lowercase letters.
(string-find-next-char "Adam" #\A) => 0 (substring-find-next-char "Adam" 1 4 #\A) => #f (substring-find-next-char-ci "Adam" 1 4 #\A) => 2
#f if none of the
characters in char-set occur in string.
For the substring procedure, only the substring is searched, but the
index returned is relative to the entire string, not just the substring.
(string-find-next-char-in-set my-string char-set:alphabetic)
=> start position of the first word in my-string
; Can be used as a predicate:
(if (string-find-next-char-in-set my-string (char-set #\( #\) ))
'contains-parentheses
'no-parentheses)
#f if char doesn't appear in the
string. For the substring procedures, the index returned is relative to
the entire string, not just the substring. The -ci procedures
don't distinguish uppercase and lowercase letters.
-ci procedures
don't distinguish uppercase and lowercase letters.
(string-match-forward "mirror" "micro") => 2 ; matches "mi" (string-match-forward "a" "b") => 0 ; no match
-ci procedures don't distinguish uppercase and lowercase
letters.
(string-match-backward-ci "BULBOUS" "fractious")
=> 3 ; matches "ous"
#t if the first string (substring) forms
the prefix of the second; otherwise returns #f. The -ci
procedures don't distinguish uppercase and lowercase letters.
(string-prefix? "abc" "abcdef") => #t (string-prefix? "" any-string) => #t
#t if the first string (substring) forms
the suffix of the second; otherwise returns #f. The -ci
procedures don't distinguish uppercase and lowercase letters.
(string-suffix? "ous" "bulbous") => #t (string-suffix? "" any-string) => #t
string-replace and
substring-replace return a newly allocated string containing the
result. string-replace! and substring-replace!
destructively modify string and return an unspecified value.
(define str "a few words") => unspecified (string-replace str #\space #\-) => "a-few-words" (substring-replace str 2 9 #\space #\-) => "a few-words" str => "a few words" (string-replace! str #\space #\-) => unspecified str => "a-few-words"
(define s (make-string 10 #\space)) => unspecified (substring-fill! s 2 8 #\*) => unspecified s => " ****** "
eqv?):
substring-move-left!
substring-move-right!
The following example shows how these procedures can be used to build up
a string (it would have been easier to use string-append):
(define answer (make-string 9 #\*)) => unspecified answer => "*********" (substring-move-left! "start" 0 5 answer 0) => unspecified answer => "start****" (substring-move-left! "-end" 0 4 answer 5) => unspecified answer => "start-end"
MIT Scheme allows the length of a string to be dynamically adjusted in a
limited way. This feature works as follows. When a new string is
allocated, by whatever method, it has a specific length. At the time of
allocation, it is also given a maximum length, which is guaranteed
to be at least as large as the string's length. (Sometimes the maximum
length will be slightly larger than the length, but it is a bad idea to
count on this. Programs should assume that the maximum length is the
same as the length at the time of the string's allocation.) After the
string is allocated, the operation set-string-length! can be used
to alter the string's length to any value between 0 and the string's
maximum length, inclusive.
(<= (string-length string)
(string-maximum-length string)) => #t
The maximum length of a string never changes.
set-string-length! does not change the
maximum length of string.
MIT Scheme implements strings as packed vectors of 8-bit ASCII
bytes. Most of the string operations, such as string-ref, coerce
these 8-bit codes into character objects. However, some lower-level
operations are made available for use.
(vector-8b-ref "abcde" 2) => 99 ; ascii for `c'
#f if ascii does not appear. The index
returned is relative to the entire string, not just the substring.
Ascii must be a valid ASCII code.
vector-8b-find-next-char-ci doesn't distinguish uppercase and
lowercase letters.
#f if ascii does not appear. The index
returned is relative to the entire string, not just the substring.
Ascii must be a valid ASCII code.
vector-8b-find-previous-char-ci doesn't distinguish uppercase and
lowercase letters.
A pair (sometimes called a dotted pair) is a data structure
with two fields called the car and cdr fields (for
historical reasons). Pairs are created by the procedure cons.
The car and cdr fields are accessed by the procedures car and
cdr. The car and cdr fields are assigned by the procedures
set-car! and set-cdr!.
Pairs are used primarily to represent lists. A list can be defined recursively as either the empty list or a pair whose cdr is a list. More precisely, the set of lists is defined as the smallest set X such that
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 (it is not a pair); it has no elements and its length is zero.(8)
The most general notation (external representation) for Scheme pairs is
the "dotted" notation (c1 . c2) where c1 is
the value of the car field and c2 is the value of the cdr field.
For example, (4 . 5) is a pair whose car is 4 and whose
cdr is 5. Note that (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 (). For example, the following are
equivalent notations for a list of symbols:
(a b c d e) (a . (b . (c . (d . (e . ())))))
Whether a given pair is a list depends upon what is stored in the cdr
field. When the set-cdr! procedure is used, an object can be a
list one moment and not the next:
(define x (list 'a 'b 'c)) (define y x) y => (a b c) (list? y) => #t (set-cdr! x 4) => unspecified x => (a . 4) (eqv? x y) => #t y => (a . 4) (list? y) => #f (set-cdr! x x) => unspecified (list? y) => #f
A chain of pairs that doesn't end in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations can be combined to represent improper lists, as the following equivalent notations show:
(a b c . d) (a . (b . (c . d)))
Within literal expressions and representations of objects read by the
read procedure, the forms 'datum,
`datum, ,datum, and ,@datum
denote two-element lists whose first elements are the symbols
quote, quasiquote, unquote, and
unquote-splicing, respectively. The second element in each case
is datum. This convention is supported so that arbitrary Scheme
programs may be represented as lists. Among other things, this permits
the use of the read procedure to parse Scheme programs.
This section describes the simple operations that are available for constructing and manipulating arbitrary graphs constructed from pairs.
#t if object is a pair; otherwise returns
#f.
(pair? '(a . b)) => #t (pair? '(a b c)) => #t (pair? '()) => #f (pair? '#(a b)) => #f
eqv?) from every previously existing object.
(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)
car of the empty list.
(car '(a b c)) => a (car '((a) b c d)) => (a) (car '(1 . 2)) => 1 (car '()) error--> Illegal datum
cdr of the empty list.
(cdr '((a) b c d)) => (b c d) (cdr '(1 . 2)) => 2 (cdr '()) error--> Illegal datum
set-car! is unspecified.
(define (f) (list 'not-a-constant-list)) (define (g) '(constant-list)) (set-car! (f) 3) => unspecified (set-car! (g) 3) error--> Illegal datum
set-cdr! is unspecified.
car and cdr; for
example, caddr could be defined by
(define caddr (lambda (x) (car (cdr (cdr x)))))
car and cdr.
Path encodes a particular sequence of car and cdr
operations, which general-car-cdr executes on object.
Path is an exact non-negative integer that encodes the operations
in a bitwise fashion: a zero bit represents a cdr operation, and
a one bit represents a car. The bits are executed LSB to MSB,
and the most significant one bit, rather than being interpreted as an
operation, signals the end of the sequence.(9)
For example, the following are equivalent:
(general-car-cdr object #b1011) (cdr (car (car object)))
Here is a partial table of path/operation equivalents:
#b10 cdr #b11 car #b100 cddr #b101 cdar #b110 cadr #b111 caar #b1000 cdddr
(define (tree-copy tree)
(let loop ((tree tree))
(if (pair? tree)
(cons (loop (car tree)) (loop (cdr tree)))
tree)))
(list 'a (+ 3 4) 'c) => (a 7 c) (list) => ()
These expressions are equivalent:
(list obj1 obj2 ... objN) (cons obj1 (cons obj2 ... (cons objN '()) ...))
cons* is similar to list, except that cons* conses
together the last two arguments rather than consing the last argument
with the empty list. If the last argument is not a list the result is
an improper list. If the last argument is a list, the result is a list
consisting of the initial arguments and all of the items in the final
argument. If there is only one argument, the result is the argument.
(cons* 'a 'b 'c) => (a b . c) (cons* 'a 'b '(c d)) => (a b c d) (cons* 'a) => a
These expressions are equivalent:
(cons* obj1 obj2 ... objN-1 objN) (cons obj1 (cons obj2 ... (cons objN-1 objN) ...))
(define (list-copy list)
(if (null? list)
'()
(cons (car list)
(list-copy (cdr list)))))
vector->list returns a newly allocated list of the elements of
vector. subvector->list returns a newly allocated list of the
elements of the given subvector. The inverse of vector->list is
list->vector.
(vector->list '#(dah dah didah)) => (dah dah didah)
string->list returns a newly allocated list of the character
elements of string.substring->list returns a newly allocated list of the character
elements of the given substring. The inverse of string->list is
list->string.
(string->list "abcd") => (#\a #\b #\c #\d) (substring->list "abcdef" 1 3) => (#\b #\c)
#t if object is a list, otherwise returns
#f. By definition, all lists have finite length and are
terminated by the empty list. This procedure returns an answer even for
circular structures.
Any object satisfying this predicate will also satisfy exactly one
of pair? or null?.
(list? '(a b c)) => #t (list? '()) => #t (list? '(a . b)) => #f (let ((x (list 'a))) (set-cdr! x x) (list? x)) => #f
(length '(a b c)) => 3 (length '(a (b) (c d e))) => 3 (length '()) => 0
#t if object is the empty list; otherwise returns
#f (but see section True and False).
(null? '(a . b)) => #f (null? '(a b c)) => #f (null? '()) => #t
0, the second has index 1, and so on.
(list-ref '(a b c d) 2) => c
(list-ref '(a b c d)
(inexact->exact (round 1.8)))
=> c
(list-ref list k) is equivalent to (car
(list-tail list k)).
seventh is a list that contains only
six elements).
0 <= start <= end <= (length list)
sublist returns a newly allocated list formed from the elements
of list beginning at index start (inclusive) and ending at
end (exclusive).
We could have defined list-head this way:
(define (list-head list k) (sublist list 0 k))
(append '(x) '(y)) => (x y) (append '(a) '(b c d)) => (a b c d) (append '(a (b)) '((c))) => (a (b) (c)) (append) => ()
The resulting list is always newly allocated, except that it shares structure with the last list argument. The last argument may actually be any object; an improper list results if the last argument is not a proper list.
(append '(a b) '(c . d)) => (a b c . d) (append '() 'a) => a
append, which copies arguments rather than destroying them.) For
example:
(define x '(a b c)) (define y '(d e f)) (define z '(g h)) (append! x y z) => (a b c d e f g h) x => (a b c d e f g h) y => (d e f g h) z => (g h)
(list-transform-positive '(1 2 3 4 5) odd?) => (1 3 5) (list-transform-negative '(1 2 3 4 5) odd?) => (2 4)
delq uses eq? to compare
element with the entries in list, delv uses
eqv?, and delete uses equal?.
delq, delv, and delete except that they
destructively modify list. delq! uses eq? to
compare element with the entries in list, delv! uses
eqv?, and delete! uses equal?. Because the result
may not be eq? to list, it is desirable to do something
like (set! x (delete! x)).
(define x '(a b c b)) (delete 'b x) => (a c) x => (a b c b) (define x '(a b c b)) (delete! 'b x) => (a c) x => (a c) ;; Returns correct result: (delete! 'a x) => (c) ;; Didn't modify what x points to: x => (a c)
delv or delete!.
Deletor should be one of the procedures list-deletor or
list-deletor!. Predicate must be an equivalence predicate.
The returned procedure accepts exactly two arguments: first, an object
to be deleted, and second, a list of objects from which it is to be
deleted. If deletor is list-deletor, the procedure
returns a newly allocated copy of the given list in which all entries
equal to the given object have been removed. If deletor is
list-deletor!, the procedure returns a list consisting of the
top-level elements of the given list with all entries equal to the given
object removed; the given list is destructively modified to produce the
result. In either case predicate is used to compare the given
object to the elements of the given list.
Here are some examples that demonstrate how
delete-member-procedure could have been used to implement
delv and delete!:
(define delv (delete-member-procedure list-deletor eqv?)) (define delete! (delete-member-procedure list-deletor! equal?))
The procedure returned by list-deletor deletes elements
non-destructively, by returning a newly allocated copy of the argument
with the appropriate elements removed. The procedure returned by
list-deletor! performs a destructive deletion.
#f if it doesn't find such
an element. (This means that if predicate is true (false) for
#f, it may be impossible to distinguish a successful result from
an unsuccessful one.) Predicate must be a procedure of one
argument.
#f
(n.b.: not the empty list) is returned. memq uses eq? to
compare object with the elements of list, while memv
uses eqv? and member uses equal?.(10)
(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)) => unspecified (memv 101 '(100 101 102)) => (101 102)
memq, except that predicate,
which must be an equivalence predicate, is used instead of eq?.
This could be used to define memv as follows:
(define memv (member-procedure eqv?))
map applies procedure element-wise
to the elements of the lists and returns a list of the results, in
order from left to right. The dynamic order in which procedure is
applied to the elements of the lists is unspecified; use
for-each to sequence side effects.
(map cadr '((a b) (d e) (g h))) => (b e h)
(map (lambda (n) (expt n n)) '(1 2 3 4)) => (1 4 27 256)
(map + '(1 2 3) '(4 5 6)) => (5 7 9)
(let ((count 0))
(map (lambda (ignored)
(set! count (+ count 1))
count)
'(a b c))) => unspecified
map, except that the resulting list is terminated by
initial-value rather than the empty list. The following are
equivalent:
(map procedure list list ...) (map* '() procedure list list ...)
map and map*, respectively, except that the
results of applying procedure to the elements of lists are
concatenated together by append rather than by cons. The
following are equivalent, except that the former is more efficient:
(append-map procedure list list ...) (apply append (map procedure list list ...))
map and map*, respectively, except that the
results of applying procedure to the elements of lists are
concatenated together by append! rather than by cons. The
following are equivalent, except that the former is more efficient:
(append-map! procedure list list ...) (apply append! (map procedure list list ...))
for-each are like the arguments to map,
but for-each calls procedure for its side effects rather
than for its values. Unlike map, for-each is guaranteed
to call procedure on the elements of the lists in order from
the first element to the last, and the value returned by for-each
is unspecified.
(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)
+ one can add up all the
elements:
(reduce + 0 list-of-numbers)
The argument initial is used only if list is empty; in this
case initial is the result of the call to reduce. If
list has a single argument, it is returned. Otherwise, the arguments
are reduced in a left-associative fashion. For example:
(reduce + 0 '(1 2 3 4)) => 10 (reduce + 0 '(1 2)) => 3 (reduce + 0 '(1)) => 1 (reduce + 0 '()) => 0 (reduce + 0 '(foo)) => foo (reduce list '() '(1 2 3 4)) => (((1 2) 3) 4)
reduce except that it is right-associative.
(reduce-right list '() '(1 2 3 4)) => (1 (2 (3 4)))
reduce and reduce-right,
initial is always used:
(fold-right + 0 '(1 2 3 4)) => 10 (fold-right + 0 '(foo)) error--> Illegal datum (fold-right list '() '(1 2 3 4)) => (1 (2 (3 (4 ()))))
Fold-right has interesting properties because it establishes a
homomorphism between (cons, ()) and (procedure,
initial). It can be thought of as replacing the pairs in the
spine of the list with procedure and replacing the () at
the end with initial. Many of the classical list-processing
procedures can be expressed in terms of fold-right, at least for
the simple versions that take a fixed number of arguments:
(define (copy-list list) (fold-right cons '() list)) (define (append list1 list2) (fold-right cons list2 list1)) (define (map p list) (fold-right (lambda (x r) (cons (p x) r)) '() list)) (define (reverse items) (fold-right (lambda (x r) (append r (list x))) '() items))
fold-right is recursive in nature, capturing the essence of
cdr-ing down a list and then computing a result, fold-left
is iterative in nature, combining the elements as the list is traversed.
(fold-left list '() '(1 2 3 4)) => ((((() 1) 2) 3) 4) (define (length list) (fold-left (lambda (sum element) (+ sum 1)) 0 list)) (define (reverse items) (fold-left (lambda (x y) (cons y x)) () items))
there-exists?; predicate will not be applied to the
remaining elements of list. If predicate returns #f
for all of the elements of list, then #f is returned.
#f for any element of
list, #f is immediately returned as the value of
for-all?; predicate will not be applied to the remaining
elements of list. If predicate is true for all of the
elements of list, then #t is returned.
list and make-list,
respectively, except that the returned lists are circular.
circular-list could have been defined like this:
(define (circular-list . objects) (append! objects objects))
(reverse '(a b c)) => (c b a) (reverse '(a (b c) d (e (f)))) => ((e (f)) d (b c) a)
reverse! is like reverse, except that it
destructively modifies list. Because the result may not be
eqv? to list, it is desirable to do something like
(set! x (reverse! x)).
last-pair could have been defined this way:
(define last-pair
(lambda (x)
(if (pair? (cdr x))
(last-pair (cdr x))
x)))
except-last-pair returns a newly allocated copy of list
that omits the last pair. except-last-pair! destructively
removes the last pair from list and returns list. If the
cdr of list is not a pair, the empty list is returned by either
procedure.
(and (procedure x y)
(procedure y x))
=> #f
If sequence is a list (vector), sort returns a newly
allocated list (vector) whose elements are those of sequence,
except that they are rearranged to be sorted in the order defined by
procedure. So, for example, if the elements of sequence are
numbers, and procedure is <, then the resulting elements
are sorted in monotonically nondecreasing order. Likewise, if
procedure is >, the resulting elements are sorted in
monotonically nonincreasing order. To be precise, if x and
y are any two adjacent elements in the result, where x
precedes y, it is the case that
(procedure y x)
=> #f
See also the definition of sort!.
Vectors are heterogenous structures whose elements are indexed by exact non-negative 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 length of a vector is the number of elements that it contains. This number is an exact non-negative integer that is fixed when the vector is created. The valid indexes of a 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 #(object ...).
For example, a vector of length 3 containing the number zero in element
0, the list (2 2 2 2) in element 1, and the string "Anna"
in element 2 can be written as
#(0 (2 2 2 2) "Anna")
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:
'#(0 (2 2 2 2) "Anna") => #(0 (2 2 2 2) "Anna")
A number of the vector procedures operate on subvectors. A subvector is a segment of a vector that is specified by two exact non-negative integers, start and end. Start is the index of the first element that is included in the subvector, and end is one greater than the index of the last element that is included in the subvector. Thus if start and end are the same, they refer to a null subvector, and if start is zero and end is the length of the vector, they refer to the entire vector. The valid indexes of a subvector are the exact integers between start inclusive and end exclusive.
make-vector initializes each element of the vector
to object. Otherwise the initial elements of the result are
unspecified.
vector is analogous to list.
(vector 'a 'b 'c) => #(a b c)
list->vector is vector->list.
(list->vector '(dididit dah)) => #(dididit dah)
make-vector, except that the elements of the result
are determined by calling the procedure initialization on the
indices. For example:
(make-initialized-vector 5 (lambda (x) (* x x)))
=> #(0 1 4 9 16)
(vector-length vector) elements of the result are
initialized from the corresponding elements of vector. The
remaining elements of the result are unspecified.
vector-map
applies procedure element-wise to the elements of vector and
returns a newly allocated vector of the results, in order from left to
right. The dynamic order in which procedure is applied to the
elements of vector is unspecified.
(vector-map '#((a b) (d e) (g h)) cadr) => #(b e h) (vector-map '#(1 2 3 4) (lambda (n) (expt n n))) => #(1 4 27 256) (vector-map '#(5 7 9) +) => #(5 7 9)
#t if object is a vector; otherwise returns
#f.
(vector-ref '#(1 1 2 3 5 8 13 21) 5) => 8
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
(vector-set! vec 1 '("Sue" "Sue"))
vec)
=> #(0 ("Sue" "Sue") "Anna")
#f if none. The
search operation takes time proportional to the logarithm of the length
of vector. Unwrap-key must be a procedure that maps each
element of vector to a key. Key<? must be a procedure that
implements a total ordering on the keys of the elements.
(define (translate number)
(vector-binary-search '#((1 . i) (2 . ii) (3 . iii) (6 . vi))
< car number))
(translate 2) => (2 . ii)
(translate 4) => #F
(subvector vector 0 end)
(subvector vector start (vector-length vector))
The elements are copied as follows (note that this is only important when
vector1 and vector2 are eqv?):
subvector-move-left!
subvector-move-right!
sort! returns vector as its value.
See also the definition of sort.
A bit string is a sequence of bits. Bit strings can be used to represent sets or to manipulate binary data. The elements of a bit string are numbered from zero up to the number of bits in the string less one, in right to left order, (the rightmost bit is numbered zero). When you convert from a bit string to an integer, the zero-th bit is associated with the zero-th power of two, the first bit is associated with the first power, and so on.
Bit strings are encoded very densely in memory. Each bit occupies exactly one bit of storage, and the overhead for the entire bit string is bounded by a small constant. However, accessing a bit in a bit string is slow compared to accessing an element of a vector or character string. If performance is of overriding concern, it is better to use character strings to store sets of boolean values even though they occupy more space.
The length of a bit string is the number of bits that it contains. This number is an exact non-negative integer that is fixed when the bit string is created. The valid indexes of a bit string are the exact non-negative integers less than the length of the bit string.
Bit strings may contain zero or more bits. They are not limited by the length of a machine word. In the printed representation of a bit string, the contents of the bit string are preceded by `#*'. The contents are printed starting with the most significant bit (highest index).
Note that the external representation of bit strings uses a bit ordering that is the reverse of the representation for bit strings in Common Lisp. It is likely that MIT Scheme's representation will be changed in the future, to be compatible with Common Lisp. For the time being this representation should be considered a convenience for viewing bit strings rather than a means of entering them as data.
#*11111 #*1010 #*00000000 #*
All of the bit-string procedures are MIT Scheme extensions.
#f, the bit string is filled with 0 bits;
otherwise, the bit string is filled with 1 bits.
(make-bit-string 7 #f) => #*0000000
#t if object is a bit string; otherwise returns
#f.
#t if the kth bit is 1; otherwise returns
#f. K must be a valid index of bit-string.
#f is
returned. The index returned is relative to the whole bit string, not
substring.
The following procedure uses bit-substring-find-next-set-bit to
find all the set bits and display their indexes:
(define (scan-bitstring bs)
(let ((end (bit-string-length bs)))
(let loop ((start 0))
(let ((next (bit-substring-find-next-set-bit bs start end)))
(if next
(begin
(write-line next)
(if (< next end)
(loop (+ next 1)))))))))
#t if bit-string contains only 0 bits; otherwise
returns #f.
#t if they are the
same length and contain the same bits; otherwise returns #f.
bit-string-not. The arguments
target-bit-string and bit-string must be bit strings of the
same length. The bitwise-logical negation of bit-string is
computed and the result placed in target-bit-string. The value of
this procedure is unspecified.
#f;
otherwise fills bit-string with ones. Returns an unspecified
value.
The bits are copied starting from the MSB and working towards the LSB; the
direction of copying only matters when bit-string-1 and
bit-string-2 are eqv?.
condition-type:bad-range-argument
if integer is too large to be represented in length bits.
condition-type:bad-range-argument if integer is too large
to be represented in length bits.
bit-string->signed-integer regards bit-string as a two's
complement representation of a signed integer, and produces an integer
of like sign and absolute value. bit-string->unsigned-integer
regards bit-string as an unsigned quantity and converts to an
integer accordingly.
The boolean objects are true and false. The boolean constant true is written as `#t', and the boolean constant false is written as `#f'.
The primary use for boolean objects is in the conditional expressions
if, cond, and, and or; the behavior of these
expressions is determined by whether objects are true or false. These
expressions count only #f as false. They count everything else,
including #t, pairs, symbols, numbers, strings, vectors, and
procedures as true (but see section True and False).
Programmers accustomed to other dialects of Lisp should note that Scheme
distinguishes #f and the empty list from the symbol nil.
Similarly, #t is distinguished from the symbol t. In
fact, the boolean objects (and the empty list) are not symbols at all.
Boolean constants evaluate to themselves, so you don't need to quote them.
#t => #t #f => #f '#f => #f t error--> Unbound variable
#f and #t
respectively. The compiler, given the usual-integrations
declaration, replaces references to these variables with their
respective values.
Note that the symbol true is not equivalent to #t, and the
symbol false is not equivalent to #f.
#t if object is either #t or #f;
otherwise returns #f.
(boolean? #f) => #t (boolean? 0) => #f
#t if object is false; otherwise
they return #f. In other words they invert boolean
values. These two procedures have identical semantics; their names are
different to give different connotations to the test.
(not #t) => #f (not 3) => #f (not (list 3)) => #f (not #f) => #t
#t if none of its arguments are #f.
Otherwise it returns #f.
#f if all of its arguments are #f.
Otherwise it returns #t.
MIT Scheme provides two types of symbols: interned and
uninterned. Interned symbols are far more common than uninterned
symbols, and there are more ways to create them. Interned symbols have
an external representation that is recognized by the procedure
read; uninterned symbols do not.(11)
Interned symbols have an extremely useful property: any two interned
symbols whose names are the same, in the sense of string=?, are
the same object (i.e. they are eq? to one another). The term
interned refers to the process of interning by which this is
accomplished. Uninterned symbols do not share this property.
The names of interned symbols are not distinguished by their alphabetic
case. Because of this, MIT Scheme converts all alphabetic
characters in the name of an interned symbol to a specific case (lower
case) when the symbol is created. When the name of an interned symbol
is referenced (using symbol->string) or written (using
write) it appears in this case. It is a bad idea to depend on
the name being lower case. In fact, it is preferable to take this one
step further: don't depend on the name of a symbol being in a uniform
case.
The rules for writing an interned symbol are the same as the rules for
writing an identifier (see section Identifiers). Any interned symbol that
has been returned as part of a literal expression, or read using the
read procedure and subsequently written out using the
write procedure, will read back in as the identical symbol (in
the sense of eq?).
Usually it is also true that reading in an interned symbol that was
previously written out produces the same symbol. An exception are
symbols created by the procedures string->symbol and
intern; they can create symbols for which this write/read
invariance may not hold because the symbols' names contain special
characters or letters in the non-standard case.(12)
The external representation for uninterned symbols is special, to
distinguish them from interned symbols and prevent them from being
recognized by the read procedure:
(string->uninterned-symbol "foo")
=> #[uninterned-symbol 30 foo]
In this section, the procedures that return symbols as values will either always return interned symbols, or always return uninterned symbols. The procedures that accept symbols as arguments will always accept either interned or uninterned symbols, and do not distinguish the two.
#t if object is a symbol, otherwise returns
#f.
(symbol? 'foo) => #t (symbol? (car '(a b))) => #t (symbol? "bar") => #f
string->symbol, the value of this procedure will be
identical (in the sense of string=?) to the string that was
passed to string->symbol. It is an error to apply mutation
procedures such as string-set! to strings returned by this
procedure.
(symbol->string 'flying-fish) => "flying-fish"
(symbol->string 'Martin) => "martin"
(symbol->string (string->symbol "Malvina"))
=> "Malvina"
Note that two distinct uninterned symbols can have the same name.
(eq? 'bitBlt (intern "bitBlt")) => #t
The user should take care that string obeys the rules for identifiers (see section Identifiers), otherwise the resulting symbol cannot be read as itself.
#f.
This is exactly like intern, except that it will not create an
interned symbol, but only returns symbols that already exist.
symbol->string.
(eq? 'mISSISSIppi 'mississippi) => #t
(string->symbol "mISSISSIppi")
=> the symbol with the 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
Note: this is the fastest way to make a symbol.
The optional argument object is used to control how the symbol is generated. It may take one of the following values:
#f, the prefix is "G".
(generate-uninterned-symbol)
=> #[uninterned-symbol 31 G0]
(generate-uninterned-symbol)
=> #[uninterned-symbol 32 G1]
(generate-uninterned-symbol 'this)
=> #[uninterned-symbol 33 this2]
(generate-uninterned-symbol)
=> #[uninterned-symbol 34 G3]
(generate-uninterned-symbol 100)
=> #[uninterned-symbol 35 G100]
(generate-uninterned-symbol)
=> #[uninterned-symbol 36 G101]
(symbol-append 'foo- 'bar) => foo-bar
;; the arguments may be uninterned:
(symbol-append 'foo- (string->uninterned-symbol "baz"))
=> foo-baz
;; the result has the same case as the arguments:
(symbol-append 'foo- (string->symbol "BAZ")) => foo-BAZ
string-hash on symbol's name. The hash number is an exact
non-negative integer.
(modulo (symbol-hash symbol) modulus)
This procedure is provided for convenience in constructing hash tables.
However, it is normally preferable to use make-eq-hash-table to
build hash tables keyed by symbols, because eq? hash tables are
much faster.
(string<? (symbol->string symbol1)
(symbol->string symbol2))
Cells are data structures similar to pairs except that they have only one element. They are useful for managing state.
#t if object is a cell; otherwise returns
#f.
MIT Scheme provides a record abstraction, which is a simple and
flexible mechanism for building structures with named components.
Records can be defined and accessed using the procedures defined in this
section. A less flexible but more concise way to manipulate records is
to use the define-structure special form (see section Structure Definitions).
make-record-type that created the type represented by
record-type; if the field-names argument is provided, it is
an error if it contains any duplicates or any symbols not in the default
list.
#t if the argument is a member of the indicated
record type; it returns #f otherwise.
make-record-type that created the type represented by
record-type.
make-record-type that created the
type represented by record-type.
For compatibility with old code, record-updater is a synonym for
this procedure.
#t if object is a record of any type and #f
otherwise. Note that record? may be true of any Scheme value; of
course, if it returns #t for some particular value, then
record-type-descriptor is applicable to that value and returns an
appropriate descriptor.
record-predicate, the resulting predicate would return
#t when passed record. Note that it is not necessarily the
case that the returned descriptor is the one that was passed to
record-constructor in the call that created the constructor
procedure that created record.
#t if object is a record-type descriptor; otherwise
returns #f.
eqv? to the
type-name argument given in the call to make-record-type
that created the type represented by record-type.
equal?
to the field-names argument given in the call to
make-record-type that created the type represented by
record-type.(13)
delay construct is used together with the procedure
force to implement lazy evaluation or call by need.
(delay expression) returns an object called a promise
which at some point in the future may be asked (by the force
procedure) to evaluate expression and deliver the resulting value.
(force (delay (+ 1 2))) => 3
(let ((p (delay (+ 1 2))))
(list (force p) (force p))) => (3 3)
(define head car)
(define tail
(lambda (stream)
(force (cdr stream))))
(define a-stream
(letrec ((next
(lambda (n)
(cons n (delay (next (+ n 1)))))))
(next 0)))
(head (tail (tail a-stream))) => 2
#t if object is a promise; otherwise returns
#f.
#t if promise has been forced and its value cached;
otherwise returns #f.
force and 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
the value of a promise is computed at most once.
(define count 0)
(define p
(delay
(begin
(set! count (+ count 1))
(* x 3))))
(define x 5)
count => 0
p => #[promise 54]
(force p) => 15
p => #[promise 54]
count => 1
(force p) => 15
count => 1
Here is a possible implementation of delay and force. We
define the expression
(delay expression)
to have the same meaning as the procedure call
(make-promise (lambda () expression))
where make-promise is defined as follows:
(define make-promise
(lambda (proc)
(let ((already-run? #f)
(result #f))
(lambda ()
(cond ((not already-run?)
(set! result (proc))
(set! already-run? #t)))
result))))
Promises are implemented here as procedures of no arguments, and
force simply calls its argument.
(define force
(lambda (promise)
(promise)))
Various extensions to this semantics of delay and force
are supported in some implementations (none of these are currently
supported in MIT Scheme):
force on an object that is not a promise may simply
return the object.
#t or #f,
depending on the implementation:
(eqv? (delay 1) 1) => unspecified (pair? (delay (cons 1 2))) => unspecified
car and
+:
(+ (delay (* 3 7)) 13) => 34
In addition to promises, MIT Scheme supports a higher-level abstraction called streams. Streams are similar to lists, except that the tail of a stream is not computed until it is referred to. This allows streams to be used to represent infinitely long lists.
(stream) returns the empty stream, or
end-of-stream marker.
(apply stream list).
(define (stream->list stream)
(if (stream-null? stream)
'()
(cons (stream-car stream)
(stream->list (stream-cdr stream)))))
(cons
object (delay expression)).
#t if object is a pair whose cdr contains a
promise. Otherwise returns #f. This could have been defined by
(define (stream-pair? object)
(and (pair? object)
(promise? (cdr object))))
stream-car is
equivalent to car. stream-first is a synonym for
stream-car.
(force (cdr
stream)). stream-rest is a synonym for stream-cdr.
#t if stream is the end-of-stream marker; otherwise
returns #f. This is equivalent to null?, but should be
used whenever testing for the end of a stream.
stream-cdr
k times. K must be an exact non-negative integer strictly
less than the length of stream.
The following are supported for compatibility with old code. Please do
not use these for new code. The variable the-empty-stream is
bound to the end-of-stream marker; use (stream) in new code.
head is a synonym for stream-car. tail is a
synonym for stream-cdr. empty-stream? is a synonym for
stream-null?.
Weak pairs are a mechanism for building data structures that point at objects without protecting them from garbage collection. The car of a weak pair holds its pointer weakly, while the cdr holds its pointer in the normal way. If the object in the car of a weak pair is not held normally by any other data structure, it will be garbage-collected.
Note: weak pairs are not pairs; that is, they do not satisfy the
predicate pair?.
#t if object is a weak pair; otherwise returns
#f.
#f if the car of weak-pair has been
garbage-collected; otherwise returns #t. In other words, it is
true if weak-pair has a valid car component.
#f, but it can
also return #f if that is the value that was stored in the car.
Normally, weak-pair/car? is used to determine if weak-car
would return a valid value. An obvious way of doing this would be:
(if (weak-pair/car? x)
(weak-car x)
...)
However, since a garbage collection could occur between the call to
weak-pair/car? and weak-car, this would not always work
correctly. Instead, the following should be used, which always works:
(or (weak-car x)
(and (not (weak-pair/car? x))
...))
The reason that the latter expression works is that weak-car
returns #f in just two instances: when the car component is
#f, and when the car component has been garbage-collected. In
the former case, if a garbage collection happens between the two calls,
it won't matter, because #f will never be garbage-collected. And
in the latter case, it also won't matter, because the car component no
longer exists and cannot be affected by the garbage collector.
MIT Scheme provides several mechanisms for associating objects with one another. Each of these mechanisms creates a link between one or more objects, called keys, and some other object, called a datum. Beyond this common idea, however, each of the mechanisms has various different properties that make it appropriate in different situations:
An association list, or alist, is a data structure used very frequently in Scheme. An alist is a list of pairs, each of which is called an association. The car of an association is called the key.
An advantage of the alist representation is that an alist can be
incrementally augmented simply by adding new entries to the front.
Moreover, because the searching procedures assv et al. search the
alist in order, new entries can "shadow" old entries. If an alist is
viewed as a mapping from keys to data, then the mapping can be not only
augmented but also altered in a non-destructive manner by adding new
entries to the front of the alist.(14)
#t if object is an association list (including the
empty list); otherwise returns #f. Any object satisfying this
predicate also satisfies list?.
#f (n.b.: not the empty list) is returned. assq
uses eq? to compare object with the car fields of the pairs
in alist, while assv uses eqv? and assoc uses
equal?.(15)
(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))) => unspecified (assv 5 '((2 3) (5 7) (11 13))) => (5 7)
assv, except
that selector (a procedure of one argument) is used to select the
key from the association, and predicate (an equivalence predicate)
is used to compare the key to the given item. This can be used to make
association lists whose elements are, say, vectors instead of pairs
(also see section Searching Lists).
For example, here is how assv could be implemented:
(define assv (association-procedure eqv? car))
Another example is a "reverse association" procedure:
(define rassv (association-procedure eqv? cdr))
del-assq uses eq? to compare
object with the keys, while del-assv uses eqv? and
del-assoc uses equal?.
(define a
'((butcher . "231 e22nd St.")
(baker . "515 w23rd St.")
(hardware . "988 Lexington Ave.")))
(del-assq 'baker a)
=>
((butcher . "231 e22nd St.")
(hardware . "988 Lexington Ave."))
del-assq! uses eq? to compare object with the keys,
while del-assv! uses eqv? and del-assoc! uses
equal?. These procedures are like del-assq,
del-assv, and del-assoc, respectively, except that they
destructively modify alist.
del-assv or
del-assq!. The predicate and selector arguments are
the same as those for association-procedure, while the
deletor argument should be either the procedure
list-deletor (for non-destructive deletions), or the procedure
list-deletor! (for destructive deletions).
For example, here is a possible implementation of del-assv:
(define del-assv (delete-association-procedure list-deletor eqv? car))
list-copy except that the "association" pairs, i.e. the
elements of the list alist, are also copied. alist-copy
could have been implemented like this:
(define (alist-copy alist)
(if (null? alist)
'()
(cons (cons (car (car alist)) (cdr (car alist)))
(alist-copy (cdr alist)))))
1D tables ("one-dimensional" tables) are similar to association
lists. In a 1D table, unlike an association list, the keys of the table
are held weakly: if a key is garbage-collected, its associated
value in the table is removed. 1D tables compare their keys for
equality using eq?.
1D tables can often be used as a higher-performance alternative to the two-dimensional association table (see section The Association Table). If one of the keys being associated is a compound object such as a vector, a 1D table can be stored in one of the vector's slots. Under these circumstances, accessing items in a 1D table will be comparable in performance to using a property list in a conventional Lisp.
#t if object is a 1D table, otherwise returns
#f. Any object that satisfies this predicate also satisfies
list?.
1d-table/lookup.
MIT Scheme provides a generalization of the property-list mechanism
found in most other implementations of Lisp: a global two-dimensional
association table. This table is indexed by two keys, called
x-key and y-key in the following procedure descriptions.
These keys and the datum associated with them can be arbitrary objects.
eq? is used to discriminate keys.
Think of the association table as a matrix: a single datum can be accessed using both keys, a column using x-key only, and a row using y-key only.
#f if no such association exists.
(y-key . datum) pairs. Returns the empty list if no
entries for x-key exist.
(2d-put! 'foo 'bar 5) (2d-put! 'foo 'baz 6) (2d-get-alist-x 'foo) => ((baz . 6) (bar . 5))
(x-key . datum) pairs. Returns the empty list if no
entries for y-key exist.
(2d-put! 'bar 'foo 5) (2d-put! 'baz 'foo 6) (2d-get-alist-y 'foo) => ((baz . 6) (bar . 5))
Hash tables are a fast, powerful mechanism for storing large numbers of associations. MIT Scheme's hash tables feature automatic resizing, customizable growth parameters, and customizable hash procedures.
The average times for the insertion, deletion, and lookup operations on a hash table are bounded by a constant. The space required by the table is proportional to the number of associations in the table; the constant of proportionality is described below (see section Resizing of Hash Tables).
The hash-table implementation is a run-time-loadable option. To use hash tables, execute
(load-option 'hash-table)
once before calling any of the procedures defined here.
The next few procedures are hash-table constructors. All hash table
constructors are procedures that accept one optional argument,
initial-size, and return a newly allocated hash table. If
initial-size is given, it must be an exact non-negative integer or
#f. The meaning of initial-size is discussed below
(see section Resizing of Hash Tables).
Hash tables are normally characterized by two things: the equivalence predicate that is used to compare keys, and whether or not the table allows its keys to be reclaimed by the garbage collector. If a table prevents its keys from being reclaimed by the garbage collector, it is said to hold its keys strongly; otherwise it holds its keys weakly (see section Weak Pairs).
eq?. The keys are held
weakly. These are the fastest of the standard hash tables.
For compatibility with old code, make-symbol-hash-table is a
synonym for this procedure.
eqv?. The keys are held
weakly, except that booleans, characters, and numbers are held strongly.
These hash tables are a little slower than those made by
make-eq-hash-table.
For compatibility with old code, make-object-hash-table is a
synonym for this procedure.
equal?. The keys are held
strongly. These hash tables are quite a bit slower than those made by
make-eq-hash-table.
string=?. The keys are held
strongly.
The next two procedures are used to create new hash-table constructors.
All of the above hash table constructors, with the exception of
make-eqv-hash-table, could have been created by calls to these
"constructor-constructors"; see the examples below.
The optional argument rehash-after-gc?, if true, says that the
values returned by key-hash might change after a garbage
collection. If so, the hash-table implementation arranges for the table
to be rehashed when necessary. (See section Address Hashing, for
information about hash procedures that have this property.) Otherwise,
it is assumed that key-hash always returns the same value for the
same arguments. The default value of this argument is #f.
The constructors returned by strong-hash-table/constructor make
hash tables that hold their keys strongly. The constructors returned by
weak-hash-table/constructor make hash tables that hold their keys
weakly.
Some examples showing how some standard hash-table constructors could have been defined:
(define make-eq-hash-table (weak-hash-table/constructor eq-hash-mod eq? #t)) (define make-equal-hash-table (strong-hash-table/constructor equal-hash-mod equal? #t)) (define make-string-hash-table (strong-hash-table/constructor string-hash-mod string=? #f))
The following procedure is sometimes useful in conjunction with weak hash tables. Normally it is not needed, because such hash tables clean themselves automatically as they are used.
The procedures described in this section are the basic operations on hash tables. They provide the functionality most often needed by programmers. Subsequent sections describe other operations that provide additional functionality needed by some applications.
#t if object is a hash table, otherwise returns
#f.
(key . datum)
where key is one of the keys of hash-table, and datum
is its associated datum. The average and worst-case times required by
this operation are linear in the number of associations
in the table.
hash-table/remove! to remove the association being processed.
The following procedure is an alternate form of hash-table/get
that is useful in some situations. Usually, hash-table/get is
preferable because it is faster.
hash-table/lookup (hash-table/lookup reduces into
the invoked procedure, i.e. calls it tail-recursively). The average
time required by this operation is bounded by a constant.
Normally, hash tables automatically resize themselves according to need. Because of this, the programmer need not be concerned with management of the table's size. However, some limited control over the table's size is provided, which will be discussed below. This discussion involves two concepts, usable size and physical size, which we will now define.
The usable size of a hash table is the number of associations that the table can hold at a given time. If the number of associations in the table exceeds the usable size, the table will automatically grow, increasing the usable size to a new value that is sufficient to hold the associations.
The physical size is an abstract measure of a hash table that specifies how much space is allocated to hold the associations of the table. The physical size is always greater than or equal to the usable size. The physical size is not interesting in itself; it is interesting only for its effect on the performance of the hash table. While the average performance of a hash-table lookup is bounded by a constant, the worst-case performance is not. For a table containing a given number of associations, increasing the physical size of the table decreases the probability that worse-than-average performance will occur.
The physical size of a hash table is statistically related to the number of associations. However, it is possible to place bounds on the physical size, and from this to estimate the amount of space used by the table:
(define (hash-table-space-bounds count rehash-size rehash-threshold)
(let ((tf (/ 1 rehash-threshold)))
(values (if (exact-integer? rehash-size)
(- (* count (+ 4 tf))
(* tf (+ rehash-size rehash-size)))
(* count (+ 4 (/ tf (* rehash-size rehash-size)))))
(* count (+ 4 tf)))))
What this formula shows is that, for a "normal" rehash size (that is, not an exact integer), the amount of space used by the hash table is proportional to the number of associations in the table. The constant of proportionality varies statistically, with the low bound being
(+ 4 (/ (/ 1 rehash-threshold) (* rehash-size rehash-size)))
and the high bound being
(+ 4 (/ 1 rehash-threshold))
which, for the default values of these parameters, are 4.25 and
5, respectively. Reducing the rehash size will tighten these
bounds, but increases the amount of time spent resizing, so you can see
that the rehash size gives some control over the time-space tradeoff of
the table.
The programmer can control the size of a hash table by means of three parameters:
If the programmer knows that the table will initially contain a specific
number of items, initial-size can be given when the table is
created. If initial-size is an exact non-negative integer, it
specifies the initial usable size of the hash table; the table will not
change size until the number of items in the table exceeds
initial-size, after which automatic resizing is enabled and
initial-size no longer has any effect. Otherwise, if
initial-size is not given or is #f, the table is
initialized to an unspecified size and automatic resizing is immediately
enabled.
The rehash size specifies how much to increase the usable size of
the hash table when it becomes full. It is either an exact positive
integer, or a real number greater than one. If it is an integer, the
new size is the sum of the old size and the rehash size. Otherwise, it
is a real number, and the new size is the product of the old size and
the rehash size. Increasing the rehash size decreases the average cost
of an insertion, but increases the average amount of space used by the
table. The rehash size of a table may be altered dynamically by the
application in order to optimize the resizing of the table; for example,
if the table will grow quickly for a known period and afterwards will
not change size, performance might be improved by using a large rehash
size during the growth phase and a small one during the static phase.
The default rehash size of a newly constructed hash table is 2.0.
Note well: The use of an exact positive integer for a rehash size is almost always undesirable; this option is provided solely for compatibility with the Common Lisp hash-table mechanism. The reason for this has to do with the time penalty for resizing the hash table. The time needed to resize a hash table is proportional to the number of associations in the table. This resizing cost is amortized across the insertions required to fill the table to the point where it needs to grow again. If the table grows by an amount proportional to the number of associations, then the cost of resizing and the increase in size are both proportional to the number of associations, so the amortized cost of an insertion operation is still bounded by a constant. However, if the table grows by a constant amount, this is not true: the amortized cost of an insertion is not bounded by a constant. Thus, using a constant rehash size means that the average cost of an insertion increases proportionally to the number of associations in the hash table.
The rehash threshold is a real number, between zero exclusive and
one inclusive, that specifies the ratio between a hash table's usable
size and its physical size. Decreasing the rehash threshold decreases
the probability of worse-than-average insertion, deletion, and lookup
times, but increases the physical size of the table for a given usable
size. The default rehash threshold of a newly constructed hash table is
1.
The procedures described in this section may be used to make very efficient key-hashing procedures for arbitrary objects. All of these procedures are based on address hashing, which uses the address of an object as its hash number. The great advantage of address hashing is that converting an arbitrary object to a hash number is extremely fast and takes the same amount of time for any object.
The disadvantage of address hashing is that the garbage collector changes the addresses of most objects. The hash-table implementation compensates for this disadvantage by automatically rehashing tables that use address hashing when garbage collections occur. Thus, in order to use these procedures for key hashing, it is necessary to tell the hash-table implementation (by means of the rehash-after-gc? argument to the "constructor-constructor" procedure) that the hash numbers computed by your key-hashing procedure must be recomputed after a garbage collection.
eq-hash, a
non-negative fixnum. Two objects that are equivalent according to
eq?, eqv?, or equal?, respectively, will produce the
same hash number when passed as arguments to these procedures, provided
that the garbage collector does not run during or between the two calls.
The following procedures are the key-hashing procedures used by the standard address-hash-based hash tables.
make-eq-hash-table.
make-eqv-hash-table.
make-equal-hash-table.
The procedures in this section allow the programmer to control some of the internal structure of a hash table. Normally, hash tables maintain associations between keys and datums using pairs or weak pairs. These procedures allow the programmer to specify the use of some other data structure to maintain the association. In this section, the data structure that represents an association in a hash table is called an entry.
hash-table/constructor define the characteristics of the hash
table as follows:
#f iff the entry's
key has been reclaimed by the garbage collector. Instead of a
procedure, this may be #t, which is equivalent to (lambda
(entry) #t).
#f.
For example, here is how the constructors for ordinary hash tables could be defined:
(define (strong-hash-table/constructor key-hash key=?
#!optional rehash-after-gc?)
(hash-table/constructor key-hash key=? cons #t car cdr set-cdr!
(if (default-object? rehash-after-gc?)
#f
rehash-after-gc?)))
(define (weak-hash-table/constructor key-hash key=?
#!optional rehash-after-gc?)
(hash-table/constructor key-hash key=? weak-cons weak-pair/car?
weak-car weak-cdr weak-set-cdr!
(if (default-object? rehash-after-gc?)
#f
rehash-after-gc?)))
hash-table/constructor. When called, each procedure returns the
value of the corresponding argument that was used to construct
hash-table.
The following procedures return the contents of a hash table as a collection of entries. While the data structure holding the entries is newly allocated, the entries themselves are not copied. Since hash table operations can modify these entries, the entries should be copied if it is desired to keep them while continuing to modify the table.
(list->vector (hash-table/entries-list hash-table))
The MIT Scheme object-hashing facility provides a mechanism for generating a unique hash number for an arbitrary object. This hash number, unlike an object's address, is unchanged by garbage collection. The object-hashing facility is useful in conjunction with hash tables, but it may be used for other things as well. In particular, it is used in the generation of the written representation for some objects (see section Custom Output).
All of these procedures accept an optional argument called table;
this table contains the object-integer associations. If given, this
argument must be an object-hash table as constructed by
hash-table/make (see below). If not given, a default table is
used.
hash associates an exact non-negative integer with object
and returns that integer. If hash was previously called with
object as its argument, the integer returned is the same as was
returned by the previous call. hash guarantees that distinct
objects (in the sense of eq?) are associated with distinct
integers.
unhash takes an exact non-negative integer k and returns
the object associated with that integer. If there is no object
associated with k, or if the object previously associated with
k has been reclaimed by the garbage collector, an error of type
condition-type:bad-range-argument is signalled. In other words,
if hash previously returned k for some object, and that
object has not been reclaimed, it is the value of the call to
unhash.
An object that is passed to hash as an argument is not protected
from being reclaimed by the garbage collector. If all other references
to that object are eliminated, the object will be reclaimed.
Subsequently calling unhash with the hash number of the (now
reclaimed) object will signal an error.
(define x (cons 0 0)) => unspecified (hash x) => 77 (eqv? (hash x) (hash x)) => #t (define x 0) => unspecified (gc-flip) ;force a garbage collection (unhash 77) error-->
The following two procedures provide a lower-level interface to the object-hashing mechanism.
object-hash is like hash, except that it accepts an
additional optional argument, insert?. If insert? is
supplied and is #f, object-hash will return an integer for
object only if there is already an association in the table;
otherwise, it will return #f. If insert? is not supplied,
or is not #f, object-hash always returns an integer,
creating an association in the table if necessary.
object-hash additionally treats #f differently than does
hash. Calling object-hash with #f as its argument
will return an integer that, when passed to unhash, will signal
an error rather than returning #f. Likewise,
valid-hash-number? will return #f for this integer.
object-unhash is like unhash, except that when k is
not associated with any object or was previously associated with an
object that has been reclaimed, object-unhash returns #f.
This means that there is an ambiguity in the value returned by
object-unhash: if #f is returned, there is no way to
tell if k is associated with #f or is not associated with
any object at all.
Finally, this procedure makes new object-hash tables:
Balanced binary trees are a useful data structure for maintaining large sets of associations whose keys are ordered. While most applications involving large association sets should use hash tables, some applications can benefit from the use of binary trees. Binary trees have two advantages over hash tables:
MIT Scheme provides an implementation of red-black trees. The red-black tree-balancing algorithm provides generally good performance because it doesn't try to keep the tree very closely balanced. At any given node in the tree, one side of the node can be twice as high as the other in the worst case. With typical data the tree will remain fairly well balanced anyway.
A red-black tree takes space that is proportional to the number of associations in the tree. For the current implementation, the constant of proportionality is eight words per association.
Red-black trees hold their keys strongly. In other words, if a red-black tree contains an association for a given key, that key cannot be reclaimed by the garbage collector.
The red-black tree implementation is a run-time-loadable option. To use red-black trees, execute
(load-option 'rb-tree)
once before calling any of the procedures defined here.
#t if object is a red-black tree, otherwise
returns #f.
(key . datum) where
key is one of the keys of rb-tree, and datum is its
associated datum. The alist is sorted by key according to the
key<? argument used to construct rb-tree. The
time required by this operation is proportional to the
number of associations in the tree.
This procedure is equivalent to:
(lambda (rb-tree) (map cdr (rb-tree->alist rb-tree)))
#t iff they are equal and #f otherwise. The trees must
have been constructed with the same equality and order predicates (same
in the sense of eq?). The keys of the trees are compared using
the key=? predicate used to build the trees, while the datums of
the trees are compared using the equivalence predicate datum=?.
The worst-case time required by this operation is proportional to the
number of associations in the tree.
#t iff rb-tree contains no associations. Otherwise
returns #f.
The returned value satisfies the following:
(lambda (rb-tree)
(let ((size (rb-tree/size rb-tree))
(lg (lambda (x) (/ (log x) (log 2)))))
(<= (lg size)
(rb-tree/height rb-tree)
(* 2 (lg (+ size 1))))))
(lambda (alist key=? key<?)
(let ((tree (make-rb-tree key=? key<?)))
(for-each (lambda (association)
(rb-tree/insert! tree
(car association)
(cdr association)))
alist)
tree))
Balanced binary trees are a useful data structure for maintaining large sets of ordered objects or sets of associations whose keys are ordered. MIT Scheme has a comprehensive implementation of weight-balanced binary trees which has several advantages over the other data structures for large aggregates:
(+ 1 x)
modifies neither the constant 1 nor the value bound to x. The
trees are referentially transparent thus the programmer need not worry
about copying the trees. Referential transparency allows space
efficiency to be achieved by sharing subtrees.
These features make weight-balanced trees suitable for a wide range of applications, especially those that require large numbers of sets or discrete maps. Applications that have a few global databases and/or concentrate on element-level operations like insertion and lookup are probably better off using hash tables or red-black trees.
The size of a tree is the number of associations that it contains. Weight-balanced binary trees are balanced to keep the sizes of the subtrees of each node within a constant factor of each other. This ensures logarithmic times for single-path operations (like lookup and insertion). A weight-balanced tree takes space that is proportional to the number of associations in the tree. For the current implementation, the constant of proportionality is six words per association.
Weight-balanced trees can be used as an implementation for either
discrete sets or discrete maps (associations). Sets are implemented by
ignoring the datum that is associated with the key. Under this scheme
if an association exists in the tree this indicates that the key of the
association is a member of the set. Typically a value such as
(), #t or #f is associated with the key.
Many operations can be viewed as computing a result that, depending on
whether the tree arguments are thought of as sets or maps, is known by
two different names. An example is wt-tree/member?, which, when
regarding the tree argument as a set, computes the set membership
operation, but, when regarding the tree as a discrete map,
wt-tree/member? is the predicate testing if the map is defined at
an element in its domain. Most names in this package have been chosen
based on interpreting the trees as sets, hence the name
wt-tree/member? rather than wt-tree/defined-at?.
The weight-balanced tree implementation is a run-time-loadable option. To use weight-balanced trees, execute
(load-option 'wt-tree)
once before calling any of the procedures defined here.
Binary trees require there to be a total order on the keys used to arrange the elements in the tree. Weight-balanced trees are organized by types, where the type is an object encapsulating the ordering relation. Creating a tree is a two-stage process. First a tree type must be created from the predicate that gives the ordering. The tree type is then used for making trees, either empty or singleton trees or trees from other aggregate structures like association lists. Once created, a tree `knows' its type and the type is used to test compatibility between trees in operations taking two trees. Usually a small number of tree types are created at the beginning of a program and used many times throughout the program's execution.
a, b and c:
(key<? a a) => #f
(and (key<? a b) (key<? b a)) => #f
(if (and (key<? a b) (key<? b c))
(key<? a c)
#t) => #t
Two key values are assumed to be equal if neither is less than the other by key<?.
Each call to make-wt-tree-type returns a distinct value, and
trees are only compatible if their tree types are eq?. A
consequence is that trees that are intended to be used in binary-tree
operations must all be created with a tree type originating from the
same call to make-wt-tree-type.
Number-wt-type
could have been defined by
(define number-wt-type (make-wt-tree-type <))
String-wt-type
could have been defined by
(define string-wt-type (make-wt-tree-type string<?))
make-wt-tree-type; the returned tree has this type.
make-wt-tree-type; the returned tree has this type.
(lambda (type alist)
(let ((tree (make-wt-tree type)))
(for-each (lambda (association)
(wt-tree/add! tree
(car association)
(cdr association)))
alist)
tree))
This section describes the basic tree operations on weight-balanced trees. These operations are the usual tree operations for insertion, deletion and lookup, some predicates and a procedure for determining the number of associations in a tree.
#t if object is a weight-balanced tree, otherwise
returns #f.
#t if wt-tree contains no associations, otherwise
returns #f.
#t if wt-tree contains an association for
key, otherwise returns #f. The average and worst-case
times required by this operation are proportional to the logarithm of
the number of associations in wt-tree.
In the following the size of a tree is the number of associations that the tree contains, and a smaller tree contains fewer associations.
wt-tree/union computes the map override of wt-tree-1 by
wt-tree-2. If the trees are viewed as sets the result is the set
union of the arguments.
The worst-case time required by this operation
is proportional to the sum of the sizes of both trees.
If the minimum key of one tree is greater than the maximum key of
the other tree then the worst-case time required is proportional to
the logarithm of the size of the larger tree.
wt-tree/intersection computes the domain restriction of
wt-tree-1 to (the domain of) wt-tree-2.
The worst-case time required by this operation is proportional to
the sum of the sizes of the trees.
#t iff the key of each association in wt-tree-1 is
the key of some association in wt-tree-2, otherwise returns #f.
Viewed as a set operation, wt-tree/subset? is the improper subset
predicate.
A proper subset predicate can be constructed:
(define (proper-subset? s1 s2)
(and (wt-tree/subset? s1 s2)
(< (wt-tree/size s1) (wt-tree/size s2))))
As a discrete map operation, wt-tree/subset? is the subset
test on the domain(s) of the map(s). In the worst-case the time
required by this operation is proportional to the size of
wt-tree-1.
#t iff for every association in wt-tree-1 there is
an association in wt-tree-2 that has the same key, and vice
versa.
Viewing the arguments as sets, wt-tree/set-equal? is the set
equality predicate. As a map operation it determines if two maps are
defined on the same domain.
This procedure is equivalent to
(lambda (wt-tree-1 wt-tree-2)
(and (wt-tree/subset? wt-tree-1 wt-tree-2
(wt-tree/subset? wt-tree-2 wt-tree-1)))
In the worst case the time required by this operation is proportional to the size of the smaller tree.
wt-tree/fold takes time
proportional to the size of wt-tree.
A sorted association list can be derived simply:
(wt-tree/fold (lambda (key datum list)
(cons (cons key datum) list))
'()
wt-tree))
The data in the associations can be summed like this:
(wt-tree/fold (lambda (key datum sum) (+ sum datum))
0
wt-tree)
wt-tree/for-each takes time proportional to the size of
wt-tree.
The example prints the tree:
(wt-tree/for-each (lambda (key value)
(display (list key value)))
wt-tree))
(lambda (key datum-1 datum-2) ...)
If some key occurs only in one tree, that association will appear in the result tree without being processed by merge, so for this operation to make sense, either merge must have both a right and left identity that correspond to the association being absent in one of the trees, or some guarantee must be made, for example, all the keys in one tree are known to occur in the other.
These are all reasonable procedures for merge
(lambda (key val1 val2) (+ val1 val2)) (lambda (key val1 val2) (append val1 val2)) (lambda (key val1 val2) (wt-tree/union val1 val2))
However, a procedure like
(lambda (key val1 val2) (- val1 val2))
would result in a subtraction of the data for all associations with keys occuring in both trees but associations with keys occuring in only the second tree would be copied, not negated, as is presumably be intent. The programmer might ensure that this never happens.
This procedure has the same time behavior as wt-tree/union but
with a slightly worse constant factor. Indeed, wt-tree/union
might have been defined like this:
(define (wt-tree/union tree1 tree2) (wt-tree/union-merge tree1 tree2 (lambda (key val1 val2) val2)))
The merge procedure takes the key as a parameter in case the data are not independent of the key.
Weight-balanced trees support operations that view the tree as sorted sequence of associations. Elements of the sequence can be accessed by position, and the position of an element in the sequence can be determined, both in logarthmic time.
wt-tree/index returns the indexth key,
wt-tree/index-datum returns the datum associated with the
indexth key and wt-tree/index-pair returns a new pair
(key . datum) which is the cons of the indexth
key and its datum. The average and worst-case times required by this
operation are proportional to the logarithm of the number of
associations in the tree.
These operations signal a condition of type
condition-type:bad-range-argument if index<0 or if
index is greater than or equal to the number of associations in
the tree. If the tree is empty, they signal an anonymous error.
Indexing can be used to find the median and maximum keys in the tree as follows:
median: (wt-tree/index wt-tree (quotient (wt-tree/size wt-tree) 2)) maximum: (wt-tree/index wt-tree (- (wt-tree/size wt-tree) 1))
#f if the tree
has no association with for key. This procedure returns either an
exact non-negative integer or #f. The average and worst-case
times required by this operation are proportional to the logarithm of
the number of associations in the tree.
wt-tree/min returns the least key,
wt-tree/min-datum returns the datum associated with the
least key and wt-tree/min-pair returns a new pair
(key . datum) which is the cons of the minimum key and its datum.
The average and worst-case times required by this operation are
proportional to the logarithm of the number of associations in the tree.
These operations signal an error if the tree is empty. They could be written
(define (wt-tree/min tree) (wt-tree/index tree 0)) (define (wt-tree/min-datum tree) (wt-tree/index-datum tree 0)) (define (wt-tree/min-pair tree) (wt-tree/index-pair tree 0))
(wt-tree/delete wt-tree (wt-tree/min wt-tree))
(wt-tree/delete! wt-tree (wt-tree/min wt-tree))
Procedures are created by evaluating lambda expressions
(see section Lambda Expressions); the lambda may either be explicit
or may be implicit as in a "procedure define"
(see section Definitions). Also there are special built-in procedures,
called primitive procedures, such as car; these procedures
are not written in Scheme but in the language used to implement the
Scheme system. MIT Scheme also provides application hooks, which
support the construction of data structures that act like procedures.
In MIT Scheme, the written representation of a procedure tells you the type of the procedure (compiled, interpreted, or primitive):
pp
=> #[compiled-procedure 56 ("pp" #x2) #x10 #x307578]
(lambda (x) x)
=> #[compound-procedure 57]
(define (foo x) x)
foo
=> #[compound-procedure 58 foo]
car
=> #[primitive-procedure car]
(call-with-current-continuation (lambda (x) x))
=> #[continuation 59]
Note that interpreted procedures are called "compound" procedures (strictly speaking, compiled procedures are also compound procedures). The written representation makes this distinction for historical reasons, and may eventually change.
(cons* object object ...)
The initial objects may be any objects, but the last object (there must be at least one object) must be a list.
(apply + (list 3 4 5 6)) => 18
(apply + 3 4 '(5 6)) => 18
(define compose
(lambda (f g)
(lambda args
(f (apply g args)))))
((compose sqrt *) 12 75) => 30
#t if object is a procedure; otherwise returns
#f. If #t is returned, exactly one of the following
predicates is satisfied by object: compiled-procedure?,
compound-procedure?, or primitive-procedure?.
#t if object is a compiled procedure; otherwise
returns #f.
#t if object is a compound (i.e. interpreted)
procedure; otherwise returns #f.
#t if object is a primitive procedure; otherwise
returns #f.
The following two procedures test the arity of a procedure, that
is, the number of arguments that the procedure accepts. The results of
the test may be less restrictive than the effect of calling the
procedure. In other words, these procedures may indicate that the
procedure will accept a given number of arguments, but if you call the
procedure it may signal a
condition-type:wrong-number-of-arguments error. This is because
these procedures examine the apparent arity of a procedure. For
example, here is a procedure that appears to accept any number of
arguments, but when called will signal an error if the number of
arguments is not one:
(lambda arguments (apply car arguments))
#t if procedure accepts k arguments;
otherwise returns #f.
#f meaning
that the procedure has no maximum number of arguments.
(procedure-arity (lambda () 3)) => (0 . 0)
(procedure-arity (lambda (x) x)) => (1 . 1)
(procedure-arity car) => (1 . 1)
(procedure-arity (lambda x x)) => (0 . #f)
(procedure-arity (lambda (x . y) x)) => (1 . #f)
(procedure-arity (lambda (x #!optional y) x))
=> (1 . 2)
-1, #f, or #t; if not supplied it defaults
to #f. Returns the primitive procedure called name. May
perform further actions depending on arity:
#f
#t
#f.
-1 means it
accepts any number of arguments.
(primitive-procedure-name car) => car
#t if primitive-procedure is implemented; otherwise
returns #f. Useful because the code that implements a particular
primitive procedure is not necessarily linked into the executable Scheme
program.
call-with-current-continuation 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 uses of this procedure.
If all real programs were as simple as these examples, there would be no
need for a procedure with the power of
call-with-current-continuation.
(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
A common use of call-with-current-continuation is for structured,
non-local exits from loops or procedure bodies, but in fact
call-with-current-continuation is quite useful for implementing a
wide variety of advanced control structures.
Whenever a Scheme expression is evaluated a continuation exists that
wants the result of the expression. The continuation represents an
entire (default) future for the computation. If the expression is
evaluated at top level, for example, the continuation will 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
don't think much about them. On the rare occasions that you may need to
deal explicitly with continuations,
call-with-current-continuation lets you do so by creating a
procedure that acts just like the current continuation.
#t if object is a continuation; otherwise returns
#f.
call-with-current-continuation.
Thunk must be a procedure of no arguments.
Conceptually, within-continuation invokes continuation on
the result of invoking thunk, but thunk is executed in the
dynamic context of continuation. In other words, the "current"
continuation is abandoned before thunk is invoked.
unwind-protect,
designed to take into account the fact that continuations produced by
call-with-current-continuation may be reentered. The arguments
before-thunk, action-thunk, and after-thunk must all
be procedures of no arguments (thunks).
dynamic-wind behaves as follows. First before-thunk is
called. Then action-thunk is called. Finally, after-thunk
is called. The value returned by action-thunk is returned as the
result of dynamic-wind. After-thunk is also called if
action-thunk escapes from its continuation. If action-thunk
captures its continuation as an escape procedure, escapes from it, then
escapes back to it, after-thunk is invoked when escaping away, and
before-thunk is invoked when escaping back.
dynamic-wind is useful, for example, for ensuring the proper
maintenance of locks: locking would occur in the before-thunk,
protected code would appear in the action-thunk, and unlocking
would occur in the after-thunk.
The following two procedures support multiple values. A future revision of the Scheme standard will support a facility similar to, but almost certainly different from, this one.
values procedure. Then procedure is called with the
multiple values as its arguments. The result yielded by procedure
is returned as the result of call-with-values.
call-with-values. Furthermore it must accept as many values as
there are objects.
Application hooks are objects that can be applied like procedures. Each application hook has two parts: a procedure that specifies what to do when the application hook is applied, and an arbitrary object, called extra. Often the procedure uses the extra object to determine what to do.
There are two kinds of application hooks, which differ in what arguments are passed to the procedure. When an apply hook is applied, the procedure is passed exactly the same arguments that were passed to the apply hook. When an entity is applied, the entity itself is passed as the first argument, followed by the other arguments that were passed to the entity.
Both apply hooks and entities satisfy the predicate procedure?.
Each satisfies either compiled-procedure?,
compound-procedure?, or primitive-procedure?, depending on
its procedure component. An apply hook is considered to accept the same
number of arguments as its procedure, while an entity is considered to
accept one less argument than its procedure.
#t if object is an apply hook; otherwise returns
#f.
#t if object is an entity; otherwise returns
#f.
Environments are first-class objects in MIT Scheme. An environment consists of some bindings and possibly a parent environment, from which other bindings are inherited. The operations in this section reveal the frame-like structure of environments by permitting you to examine the bindings of a particular environment separately from those of its parent.
#t if object is an environment; otherwise returns
#f.
#t if environment has a parent environment;
otherwise returns #f.
(name)
indicates that name is bound but unassigned, while
(name object) indicates that name is bound, and
its value is object.
#t if symbol is bound in environment or one
of its ancestor environments; otherwise returns #f.
#t if the binding may be modified by side
effect.
eval in ordinary programs; it
is useful mostly for evaluating expressions that have been created "on
the fly" by a program. eval is relatively expensive because it
must convert expression to an internal form before it is executed.
(define foo (list '+ 1 2)) (eval foo (the-environment)) => 3
The user-initial-environment is where the top-level
read-eval-print (REP) loop evaluates expressions and stores
definitions. It is a child of the system-global-environment,
which is where all of the Scheme system definitions are stored. All of
the bindings in system-global-environment are available when the
current environment is user-initial-environment. However, any
new bindings that you create in the REP loop (with define
forms or by loading files containing define forms) occur in
user-initial-environment.
system-global-environment is bound to the
environment that's the parent of the user-initial-environment.
Primitives and system procedures are bound (and sometimes closed) in
this environment.
user-initial-environment is bound to the default
environment in which typed expressions are evaluated by the top-level
REP loop.
Although all bindings in system-global-environment are visible to
the REP loop, definitions that are typed at, or loaded by, the
REP loop occur in the user-initial-environment. This is
partly a safety measure: if you enter a definition that happens to have
the same name as a critical system procedure, your definition will be
visible only to the procedures you define in the
user-initial-environment; the MIT Scheme system procedures, which
are defined in the system-global-environment, will continue to
see the original definition.
user-initial-environment.
The operations in this section return environments that are constructed
by the interpreter. These operations should only be used at the top
level of a file; they are not supported in any other place. In
particular, they force the current environment to be represented in a
form suitable for use by the interpreter. This prevents the compiler
from performing many useful optimizations on such environments, and
forces the use of the interpreter for variable references in them.
However, because all top-level environments (such as
user-initial-environment) are already interpreter environments,
it does no harm to use such operations on them.
(make-environment expression ...)
is equivalent to:
(let () expression ... (the-environment))
#t if object is an interpreter environment;
otherwise returns #f.
This chapter describes the procedures that are used for input and output (I/O). The chapter first describes ports and how they are manipulated, then describes the I/O operations. Finally, some low-level procedures are described that permit the implementation of custom ports and high-performance I/O.
Scheme uses ports for I/O. A port, which can be treated like
any other Scheme object, serves as a source or sink for data. A port
must be open before it can be read from or written to. The standard
I/O port, console-i/o-port, is opened automatically when you
start Scheme. When you use a file for input or output, you need to
explicitly open and close a port to the file (with procedures described
in this chapter). Additional procedures let you open ports to strings.
Many input procedures, such as read-char and read, read
data from the current input port by default, or from a port that you
specify. The current input port is initially console-i/o-port,
but Scheme provides procedures that let you change the current input
port to be a file or string.
Similarly, many output procedures, such as write-char and
display, write data to the current output port by default, or to
a port that you specify. The current output port is initially
console-i/o-port, but Scheme provides procedures that let you
change the current output port to be a file or string.
All ports read or write only ASCII characters.
Every port is either an input port, an output port, or both. The following predicates distinguish all of the possible cases.
#t if object is a port, otherwise returns
#f.
#t if object is an input port, otherwise returns
#f. Any object satisfying this predicate also satisfies
port?.
#t if object is an output port, otherwise returns
#f. Any object satisfying this predicate also satisfies
port?.
#t if object is both an input port and an output
port, otherwise returns #f. Any object satisfying this predicate
also satisfies port?, input-port?, and
output-port?.
condition-type:wrong-type-argument if it is not an input
port, output port, or I/O port, respectively. Otherwise they
return object.
The next five procedures return the runtime system's standard ports. All of the standard ports are dynamically bound by the REP loop; this means that when a new REP loop is started, for example by an error, each of these ports is dynamically bound to the I/O port of the REP loop. When the REP loop exits, the ports revert to their original values.
current-input-port returns the
value of console-i/o-port.
current-output-port returns the
value of console-i/o-port.
load procedure writes
messages to this port informing the user that a file is being loaded.
Initially, notification-output-port returns the value of
console-i/o-port.
trace
procedure is sent to this port. Initially, trace-output-port
returns the value of console-i/o-port.
interaction-i/o-port returns the
value of console-i/o-port.
with-input-from-port binds the current input port,
with-output-to-port binds the current output port,
with-notification-output-port binds the "notification" output
port, with-trace-output-port binds the "trace" output port, and
with-interaction-i/o-port binds the "interaction" I/O port.
console-i/o-port is an I/O port that communicates with the
"console". Under unix, the console is the controlling terminal of the
Scheme process. Under Windows and OS/2, the console is the window that
is created when Scheme starts up.
This variable is rarely used; instead programs should use one of the standard ports defined above. This variable should not be modified.
For compatibility with old code, console-input-port and
console-output-port are synonyms for this variable.
close-input-port and
close-output-port are synonyms for close-port that are
defined for compatibility with standard Scheme.
Before Scheme can access a file for reading or writing, it is necessary
to open a port to the file. This section describes procedures used to
open ports to files. Such ports are closed (like any other port) by
close-port. File ports are automatically closed if and when they
are reclaimed by the garbage collector.
Before opening a file for input or output, by whatever method, the
filename argument is converted to canonical form by calling the
procedure merge-pathnames with filename as its sole
argument. Thus, filename can be either a string or a pathname,
and it is merged with the current pathname defaults to produce the
pathname that is then opened.
Any file can be opened in one of two modes, normal or
binary. Normal mode is for accessing text files, and binary mode
is for accessing other files. Unix does not distinguish these modes,
but DOS, Windows, and OS/2 do: in normal mode, their
file ports perform newline translation, mapping between the
carriage-return/linefeed sequence that terminates text lines in files,
and the #\newline that terminates lines in Scheme. In binary
mode, MS-DOS ports do not perform newline translation. Unless
otherwise mentioned, the procedures in this section open files in normal
mode.
condition-type:file-operation-error is
signalled.
condition-type:file-operation-error is signalled.
The optional argument append? is an MIT Scheme extension. If
append? is given and not #f, the file is opened in
append mode. In this mode, the contents of the file are not
overwritten; instead any characters written to the file are appended to
the end of the existing contents. If the file does not exist, append
mode creates the file and writes to it in the normal way.
condition-type:file-operation-error
is signalled.
This procedure is often used to open special files. For example, under unix this procedure can be used to open terminal device files, PTY device files, and named pipes.
open-input-file, open-output-file, and
open-i/o-file, respectively.
condition-type:file-operation-error is signalled. If
procedure returns, then the port is closed automatically and the
value yielded by procedure is returned. If procedure does
not return, then the port will not be closed automatically unless it is
reclaimed by the garbage collector.(16)
call-with-input-file and
call-with-output-file, respectively.
current-input-port or current-output-port, and the
thunk is called with no arguments. When the thunk returns,
the port is closed and the previous default is restored.
with-input-from-file and with-output-to-file return the
value yielded by thunk. If an escape procedure is used to escape
from the continuation of these procedures, their behavior is
implementation-dependent; in that situation MIT Scheme leaves the files
open.
with-input-from-file and
with-output-to-file, respectively.
This section describes the simplest kinds of ports: input ports that read their input from given strings, and output ports that accumulate their output and return it as a string. It also describes "truncating" output ports, which can limit the length of the resulting string to a given value.
0 and
end defaults to (string-length string).
with-input-from-string creates a new input port that reads from
string, makes that port the current input port, and calls
thunk. When thunk returns, with-input-from-string
restores the previous current input port and returns the result yielded
by thunk.
(with-input-from-string "(a b c) (d e f)" read) => (a b c)
Note: this procedure is equivalent to:
(with-input-from-port (string->input-port string) thunk)
with-string-output-port returns the accumulated output to the
port as a newly allocated string.
with-output-to-string creates a new output port that accumulates
output, makes that port the default value returned by
current-output-port, and calls thunk with no arguments.
When thunk returns, with-output-to-string restores the
previous default and returns the accumulated output as a newly allocated
string.
(with-output-to-string
(lambda ()
(write 'abc))) => "abc"
Note: this procedure is equivalent to:
(with-string-output-port (lambda (port) (with-output-to-port port thunk)))
with-output-to-string, except that the output is
limited to k characters. If thunk attempts to write more
than k characters, it will be aborted by invoking an escape
procedure that returns from with-output-to-truncated-string.
The value of this procedure is a pair; the car of the pair is #t
if thunk attempted to write more than k characters, and
#f otherwise. The cdr of the pair is a newly allocated string
containing the accumulated output.
This procedure is helpful for displaying circular lists, as shown in this example:
(define inf (list 'inf))
(with-output-to-truncated-string 40
(lambda ()
(write inf))) => (#f . "(inf)")
(set-cdr! inf inf)
(with-output-to-truncated-string 40
(lambda ()
(write inf)))
=> (#t . "(inf inf inf inf inf inf inf inf inf inf")
#f, this
procedure is equivalent to
(with-output-to-truncated-string k
(lambda ()
(write object)))
otherwise it is equivalent to
(with-output-to-string (lambda () (write object)))
This section describes the procedures that read input. Input procedures can read either from the current input port or from a given port. Remember that to read from a file, you must first open a port to the file.
Input ports can be divided into two types, called interactive and non-interactive. Interactive input ports are ports that read input from a source that is time-dependent; for example, a port that reads input from a terminal or from another program. Non-interactive input ports read input from a time-independent source, such as an ordinary file or a character string.
All optional arguments called input-port, if not supplied, default to the current input port.
In MIT Scheme, if input-port is an interactive input port and no
characters are immediately available, read-char will hang waiting
for input.
In MIT Scheme, if input-port is an interactive input port and no
characters are immediately available, peek-char will hang waiting
for input.
#t if a character is ready on input-port and
returns #f otherwise. If char-ready? returns #t
then the next read-char operation on input-port is
guaranteed not to hang. If input-port is a file port at end of
file then char-ready? returns
#t.(18)
read returns the next object parsable from
input-port, updating input-port to point to the first
character past the end of the written representation of the object. If
an end of file is encountered in the input before any characters are
found that can begin an object, read returns an end-of-file
object. The input-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 written representation,
but the written representation is incomplete and therefore not parsable,
an error is signalled.
#t if object is an end-of-file object; otherwise
returns #f.
read-char, immediately returning that
character. Otherwise, #f is returned, unless input-port is
a file port at end of file, in which case an end-of-file object is
returned. In no case will this procedure block waiting for input.
read-string returns the characters, up to but excluding the
terminating character, as a newly allocated string. However, if end of
file was encountered before any characters were read, read-string
returns an end-of-file object.
On many input ports, this operation is significantly faster than the
following equivalent code using peek-char and read-char:
(define (read-string char-set input-port)
(let ((char (peek-char input-port)))
(if (eof-object? char)
char
(list->string
(let loop ((char char))
(if (or (eof-object? char)
(char-set-member? char-set char))
'()
(begin
(read-char input-port)
(cons char (loop (peek-char input-port))))))))))
Output ports may or may not support buffering of output, in which output characters are collected together in a buffer and then sent to the output device all at once. (Most of the output ports implemented by the runtime system support buffering.) Sending all of the characters in the buffer to the output device is called flushing the buffer. In general, output procedures do not flush the buffer of an output port unless the buffer is full.
However, the standard output procedures described in this section
perform what is called discretionary flushing of the buffer.
Discretionary output flushing works as follows. After a procedure
performs its output (writing characters to the output buffer), it checks
to see if the port implements an operation called
discretionary-output-flush. If so, then that operation is
invoked to flush the buffer. At present, only the console port defines
discretionary-output-flush; this is used to guarantee that output
to the console appears immediately after it is written, without
requiring calls to flush-output.
All optional arguments called output-port, if not supplied, default to the current output port.
write-char, except that it is usually much faster.
write shall be parsable by read into an equivalent object.
Thus strings that appear in the written representation are enclosed in
doublequotes, and within those strings backslash and doublequote are
escaped by backslashes. write performs discretionary output
flushing and returns an unspecified value.
write-string instead of by write. Character objects
appear in the representation as if written by write-char instead
of by write. display performs discretionary output
flushing and returns an unspecified value.(19)
(write-char #\newline output-port).
newline. In either case,
fresh-line performs discretionary output flushing and returns an
unspecified value.
write, except that it writes an end-of-line to
output-port before writing object's representation. This
procedure performs discretionary output flushing and returns an
unspecified value.
pp prints object in a visually appealing and structurally
revealing manner on output-port. If object is a procedure,
pp attempts to print the source text. If the optional argument
as-code? is true, pp prints lists as Scheme code, providing
appropriate indentation; by default this argument is false. pp
performs discretionary output flushing and returns an unspecified value.
The following variables may be dynamically bound to change the behavior
of the write and display procedures.
2, 8, 10,
or 16; the default is 10. If *unparser-radix* is
not 10, numbers are prefixed to indicate their radix.
4, only the first four elements of any list are printed, followed
by ellipses to indicate any additional elements. The value of this
variable must be an exact non-negative integer, or #f meaning no
limit; the default is #f.
(fluid-let ((*unparser-list-breadth-limit* 4))
(write-to-string '(a b c d)))
=> "(a b c d)"
(fluid-let ((*unparser-list-breadth-limit* 4))
(write-to-string '(a b c d e)))
=> "(a b c d ...)"
#f meaning no limit; the default
is #f.
(fluid-let ((*unparser-list-depth-limit* 4))
(write-to-string '((((a))) b c d)))
=> "((((a))) b c d)"
(fluid-let ((*unparser-list-depth-limit* 4))
(write-to-string '(((((a)))) b c d)))
=> "((((...))) b c d)"
#f meaning no limit; the default
is #f.
(fluid-let ((*unparser-string-length-limit* 4))
(write-to-string "abcd"))
=> "\"abcd\""
(fluid-let ((*unparser-string-length-limit* 4))
(write-to-string "abcde"))
=> "\"abcd...\""
read. These objects are printed
using the representation #@n, where n is the result
of calling hash on the object to be printed. The reader
recognizes this syntax, calling unhash on n to get back the
original object. Note that this printed representation can only be
recognized by the Scheme program in which it was generated, because
these hash numbers are different for each invocation of Scheme.
The procedure format is very useful for producing nicely
formatted text, producing good-looking messages, and so on. MIT
Scheme's implementation of format is similar to that of Common
Lisp, except that Common Lisp defines many more
directives.(20)
format is a run-time-loadable option. To use it, execute
(load-option 'format)
once before calling it.
~) introduces a format directive. The
character after the tilde, possibly preceded by prefix parameters and
modifiers, specifies what kind of formatting is desired. Most
directives use one or more arguments to create their output; the
typical directive puts the next argument into the output,
formatted in some special way. It is an error if no argument remains
for a directive requiring an argument, but it is not an error if one or
more arguments remain unprocessed by a directive.
The output is sent to destination. If destination is
#f, a string is created that contains the output; this string is
returned as the value of the call to format. In all other cases
format returns an unspecified value. If destination is
#t, the output is sent to the current output port. Otherwise,
destination must be an output port, and the output is sent there.
This procedure performs discretionary output flushing (see section Output Procedures).
A format directive consists of a tilde (~), optional
prefix parameters separated by commas, optional colon (:) and
at-sign (@) modifiers, and a single character indicating what
kind of directive this is. The alphabetic case of the directive
character is ignored. The prefix parameters are generally integers,
notated as optionally signed decimal numbers. If both the colon and
at-sign modifiers are given, they may appear in either order.
In place of a prefix parameter to a directive, you can put the letter `V' (or `v'), which takes an argument for use as a parameter to the directive. Normally this should be an exact integer. This feature allows variable-width fields and the like. You can also use the character `#' in place of a parameter; it represents the number of arguments remaining to be processed.
It is an error to give a format directive more parameters than it is described here as accepting. It is also an error to give colon or at-sign modifiers to a directive in a combination not specifically described here as being meaningful.
~A
display. ~mincolA inserts spaces on the right, if
necessary, to make the width at least mincol columns. The
@ modifier causes the spaces to be inserted on the left rather
than the right.
~S
write. ~mincolS inserts spaces on the right, if
necessary, to make the width at least mincol columns. The
@ modifier causes the spaces to be inserted on the left rather
than the right.
~%
#\newline character. ~n% outputs
n newlines. No argument is used. Simply putting a newline
in control-string would work, but ~% is often used because
it make the control string look nicer in the middle of a program.
~~
~n~ outputs n tildes.
~newline
@, the
newline is left in place, but any following whitespace is ignored. This
directive is typically used when control-string is too long to fit
nicely into one line of the program:
(define (type-clash-error procedure arg spec actual)
(format #t
"~%Procedure ~S~%requires its %A argument ~
to be of type ~S,~%but it was called with ~
an argument of type ~S.~%"
procedure arg spec actual))
(type-clash-error 'vector-ref "first" 'integer 'vector) prints:
Procedure vector-ref requires its first argument to be of type integer, but it was called with an argument of type vector.Note that in this example newlines appear in the output only as specified by the
~% directives; the actual newline characters in
the control string are suppressed because each is preceded by a tilde.
MIT Scheme provides hooks for specifying that certain kinds of objects have special written representations. There are no restrictions on the written representations, but only a few kinds of objects may have custom representation specified for them, specifically: records (see section Records), vectors that have special tags in their zero-th elements (see section Vectors), and pairs that have special tags in their car fields (see section Lists). There is a different procedure for specifying the written representation of each of these types.
An unparser method is a procedure that is invoked with two arguments: an unparser state and an object. An unparser method generates a written representation for the object, writing it to the output port specified by the unparser state. The value yielded by an unparser method is ignored. Note that an unparser state is not an output port, rather it is an object that contains an output port as one of its components. Application programs generally do not construct or examine unparser state objects, but just pass them along.
There are two ways to create an unparser method (which is then
registered by one of the above procedures). The first, and easiest, is
to use standard-unparser-method. The second is to define your
own method using the procedure with-current-unparser-state. We
encourage the use of the first method, as it results in a more uniform
appearance for objects. Many predefined datatypes, for example
procedures and environments, already have this appearance.
#f or a procedure of two arguments.
If procedure is #f, the returned method generates an
external representation of this form:
#[name hash]
Here name is the external representation of the argument
name, as generated by write,(21) and hash is the external
representation of an exact non-negative integer unique to the object
being printed (specifically, it is the result of calling hash on
the object). Subsequently, the expression
#@hash
is notation for the object.
If procedure is supplied, the returned method generates a slightly different external representation:
#[name hash output]
Here name and hash are as above, and output is the output generated by procedure. The representation is constructed in three stages:
"#[",
name, " ", and hash.
The following procedure is useful for writing more general kinds of unparser methods.
with-current-unparser-state.
The port passed to procedure should only be used within the dynamic extent of procedure.
This section describes procedures that prompt the user for input. Why should the programmer use these procedures when it is possible to do prompting using ordinary input and output procedures? One reason is that the prompting procedures are more succinct. However, a second and better reason is that the prompting procedures can be separately customized for each user interface, providing more natural interaction. The interfaces for Edwin and for GNU Emacs have already been customized in this fashion; because Edwin and Emacs are very similar editors, their customizations provide very similar behavior.
Each of these procedure accepts an optional argument called port,
which must be an I/O port if given. If not given, this port
defaults to the value of (interaction-i/o-port); this is
initially the console I/O port.
The required argument prompt must be a string.
If prompt is a string, it is used verbatim as the prompt string.
Otherwise, it must be a pair whose car is standard and whose cdr
is a string; in this case the prompt string is formed by appending a
space to the cdr string, unless it already ends in a space or is an
empty string.
The default behavior of this procedure is to print two newlines, the current REP loop "level number", a space, and the prompt string; flush the output buffer; then read an object and return it.
Under Edwin and Emacs, before the object is read, the interaction buffer is put into a mode that allows expressions to be edited and submitted for input using specific editor commands. The first expression that is submitted is returned as the value of this procedure.
char-graphic?. If at all possible, the character is read from
the user interface using a mode that reads the character as a single
keystroke; in other words, it should not be necessary for the user to
follow the character with a carriage return or similar rubbish.
This is the procedure called by debug and where to read
the user's commands.
If prompt is a string, it is used verbatim as the prompt string.
Otherwise, it must be a pair whose car is standard and whose cdr
is a string; in this case the prompt string is formed by appending a
space to the cdr string, unless it already ends in a space or is an
empty string.
The default behavior of this procedure is to print two newlines, the current REP loop "level number", a space, and the prompt string; flush the output buffer; read a character in raw mode, echo that character, and return it.
Under Edwin and Emacs, instead of reading a character, the interaction buffer is put into a mode in which graphic characters submit themselves as input. After this mode change, the first such character submitted is returned as the value of this procedure.
The prompt string is formed by appending a colon and a space to prompt, unless prompt already ends in a space or is the null string.
The default behavior of this procedure is to print two newlines and the prompt string; flush the output buffer; then read an object and return it.
Under Edwin and Emacs, the expression is read in the minibuffer.
prompt-for-expression to read an expression, then evaluates the
expression using environment; if environment is not given,
the REP loop environment is used.
The prompt string is formed by appending the string " (y or n)? "
to prompt, unless prompt already ends in a space or is the
null string.
The default behavior of this procedure is to print two newlines and the
prompt string; flush the output buffer; then read a character in raw
mode. If the character is #\y, #\Y, or #\space,
the procedure returns #t; If the character is #\n,
#\N, or #\rubout, the procedure returns #f.
Otherwise the prompt is repeated.
Under Edwin or Emacs, the confirmation is read in the minibuffer.
This section describes the low-level operations that can be used to build and manipulate I/O ports.
The purpose of these operations is twofold: to allow programmers to construct new kinds of I/O ports, and to provide faster I/O operations than those supplied by the standard high level procedures. The latter is useful because the standard I/O operations provide defaulting and error checking, and sometimes other features, which are often unnecessary. This interface provides the means to bypass such features, thus improving performance.
The abstract model of an I/O port, as implemented here, is a
combination of a set of named operations and a state. The state is an
arbitrary object, the meaning of which is determined by the operations.
The operations are defined by a mapping from names to procedures.
Typically the names are symbols, but any object that can be
discriminated by eq? may be used.
The operations are divided into two classes:
y-size that returns the height of the terminal in characters.
Because only some ports will implement these operations, programs that
use custom operations must test each port for their existence, and be
prepared to deal with ports that do not implement them.
The procedures in this section provide means for constructing ports with custom operations, accessing their operations, and manipulating their internal state.
Operations need not contain definitions for all of the standard
operations; the procedure will provide defaults for any standard
operations that are not defined. At a minimum, the following operations
must be defined: for input ports, read-char, peek-char,
and char-ready?; for output ports, either write-char or
write-substring; I/O ports must supply the minimum
operations for both input and output.
port/copy is normally used to speed up creation of ports. This
is done by creating a template using one of the port constructors
make-input-port, make-output-port, or
make-i/o-port, as appropriate; a dummy state component is
supplied for the template. Then port/copy is used to make a copy
of the template, supplying the copy with the correct state. This is
useful because the port constructors are somewhat slow, as they must
parse the operations list, provide defaulting for missing
operations, etc.
For compatibility with old code, input-port/copy and
output-port/copy are synonyms for this procedure.
For compatibility with old code, input-port/state and
output-port/state are synonyms for this procedure.
For compatibility with old code, set-input-port/state! and
set-output-port/ are synonyms for this procedure.
state!
#f.
For compatibility with old code, input-port/operation and
output-port/operation are similar to port/operation. They
differ in that they translate certain old operation names to new
equivalents before calling port/operation.
input-port/custom-operation and
output-port/custom-operation are synonyms for
input-port/ and
operationoutput-port/operation,
respectively.
port. The list is not newly allocated and must not be
modified.
For compatibility with old code, input-port/operation-names and
output-port/ are synonyms for this procedure.
operation-names
eof-object?. This
is sometimes useful when building input ports.
An interactive port is always in one of two modes: blocking or non-blocking. This mode is independent of the terminal mode: each can be changed independent of the other. Furthermore, if it is an interactive I/O port, there are separate blocking modes for input and for output.
If an input port is in blocking mode, attempting to read from it when no input is available will cause Scheme to "block", i.e. suspend itself, until input is available. If an input port is in non-blocking mode, attempting to read from it when no input is available will cause the reading procedure to return immediately, indicating the lack of input in some way (exactly how this situation is indicated is separately specified for each procedure or operation).
An output port in blocking mode will block if the output device is not ready to accept output. In non-blocking mode it will return immediately after performing as much output as the device will allow (again, each procedure or operation reports this situation in its own way).
Interactive ports are initially in blocking mode; this can be changed at any time with the procedures defined in this section.
These procedures represent blocking mode by the symbol blocking,
and non-blocking mode by the symbol nonblocking. An argument
called mode must be one of these symbols. A port argument
to any of these procedures may be any port, even if that port does not
support blocking mode; in that case, the port is not modified in any
way.
port/with-input-blocking-mode
binds the input blocking mode of port to be mode, executes
thunk, restores the input blocking mode of port to what it
was when port/with-input-blocking-mode was called, and returns
the value that was yielded by thunk. This binding is performed
by dynamic-wind, which guarantees that the input blocking mode is
restored if thunk escapes from its continuation.
port/with-output-blocking-mode
binds the output blocking mode of port to be mode, executes
thunk, restores the output blocking mode of port to what it
was when port/with-output-blocking-mode was called, and returns
the value that was yielded by thunk. This binding is performed
by dynamic-wind, which guarantees that the output blocking mode
is restored if thunk escapes from its continuation.
A port that reads from or writes to a terminal has a terminal mode; this is either cooked or raw. This mode is independent of the blocking mode: each can be changed independent of the other. Furthermore, a terminal I/O port has independent terminal modes both for input and for output.
A terminal port in cooked mode provides some standard processing to make the terminal easy to communicate with. For example, under unix, cooked mode on input reads from the terminal a line at a time and provides rubout processing within the line, while cooked mode on output might translate linefeeds to carriage-return/linefeed pairs. In general, the precise meaning of cooked mode is operating-system dependent, and furthermore might be customizable by means of operating system utilities. The basic idea is that cooked mode does whatever is necessary to make the terminal handle all of the usual user-interface conventions for the operating system, while keeping the program's interaction with the port as normal as possible.
A terminal port in raw mode disables all of that processing. In raw mode, characters are directly read from and written to the device without any translation or interpretation by the operating system. On input, characters are available as soon as they are typed, and are not echoed on the terminal by the operating system. In general, programs that put ports in raw mode have to know the details of interacting with the terminal. In particular, raw mode is used for writing programs such as text editors.
Terminal ports are initially in cooked mode; this can be changed at any time with the procedures defined in this section.
These procedures represent cooked mode by the symbol cooked, and
raw mode by the symbol raw. Additionally, the value #f
represents "no mode"; it is the terminal mode of a port that is not a
terminal. An argument called mode must be one of these three
values. A port argument to any of these procedures may be any
port, even if that port does not support terminal mode; in that case,
the port is not modified in any way.
port/with-input-terminal-mode
binds the input terminal mode of port to be mode, executes
thunk, restores the input terminal mode of port to what it
was when port/with-input-terminal-mode was called, and returns
the value that was yielded by thunk. This binding is performed
by dynamic-wind, which guarantees that the input terminal mode is
restored if thunk escapes from its continuation.
port/with-output-terminal-mode
binds the output terminal mode of port to be mode, executes
thunk, restores the output terminal mode of port to what it
was when port/with-output-terminal-mode was called, and returns
the value that was yielded by thunk. This binding is performed
by dynamic-wind, which guarantees that the output terminal mode is
restored if thunk escapes from its continuation.
This section describes the standard operations on input ports. Following that, some useful custom operations are described.
#f is returned;
otherwise the operation hangs until input is available.
read-char.
read-char.
char-ready? returns #t if at least one character is
available to be read from input-port. If no characters are
available, the operation waits up to k milliseconds before
returning #f, returning immediately if any characters become
available while it is waiting.
read-char and discard-char,
except that they read or discard multiple characters at once. This can
have a marked performance improvement on buffered input ports. All
characters up to, but excluding, the first character in char-set
(or end of file) are read from input-port. read-string
returns these characters as a newly allocated string, while
discard-chars discards them and returns an unspecified value.
These operations hang until sufficient input is available, even if
input-port is in non-blocking mode. If end of file is encountered
before any input characters, read-string returns an end-of-file
object.
input-port/operation on the respective operation
name:
(input-port/operation/read-char input-port) (input-port/operation input-port 'read-char)
(input-port/read-string input-port char-set) ((input-port/operation/read-string input-port) input-port char-set)
The following custom operations are implemented for input ports to files, and will also work with some other kinds of input ports:
#t if input-port is known to be at end of file,
otherwise it returns #f.
#f.
This section describes the standard operations on output ports. Following that, some useful custom operations are described.
This operation, if defined, is normally identical to
flush-output. However, it is not normally defined, and even when
it is, it is invoked at different times (see section Output Procedures).
output-port/operation on the respective operation
name:
(output-port/operation/write-char output-port) (output-port/operation output-port 'write-char)
(output-port/write-char output-port char) ((output-port/operation/write-char output-port) output-port char)
The following custom operations are generally useful.
#f is returned.
#f is returned.
x-size, if it exists. If the x-size operation is both
defined and returns a value other than #f, that value is returned
as the result of this procedure. Otherwise, output-port/x-size
returns a default value (currently 79).
output-port/x-size is useful for programs that tailor their
output to the width of the display (a fairly common practice). If the
output device is not a display, such programs normally want some
reasonable default width to work with, and this procedure provides
exactly that.
y-size, if it exists. If the y-size operation is defined,
the value it returns is returned as the result of this procedure;
otherwise, #f is returned.
The Scheme standard provides a simple mechanism for reading and writing files: file ports. MIT Scheme provides additional tools for dealing with other aspects of the file system:
MIT Scheme programs need to use names to designate files. The main difficulty in dealing with names of files is that different file systems have different naming formats for files. For example, here is a table of several file systems (actually, operating systems that provide file systems) and what equivalent file names might look like for each one:
System File Name ------ --------- TOPS-20 <LISPIO>FORMAT.FASL.13 TOPS-10 FORMAT.FAS[1,4] ITS LISPIO;FORMAT FASL MULTICS >udd>LispIO>format.fasl TENEX <LISPIO>FORMAT.FASL;13 VAX/VMS [LISPIO]FORMAT.FAS;13 UNIX /usr/lispio/format.fasl DOS C:\USR\LISPIO\FORMAT.FAS
It would be impossible for each program that deals with file names to know about each different file name format that exists; a new operating system to which Scheme was ported might use a format different from any of its predecessors. Therefore, MIT Scheme provides two ways to represent file names: filenames (also called namestrings), which are strings in the implementation-dependent form customary for the file system, and pathnames, which are special abstract data objects that represent file names in an implementation-independent way. Procedures are provided to convert between these two representations, and all manipulations of files can be expressed in machine-independent terms by using pathnames.
In order to allow MIT Scheme programs to operate in a network environment that may have more than one kind of file system, the pathname facility allows a file name to specify which file system is to be used. In this context, each file system is called a host, in keeping with the usual networking terminology.(22)
Note that the examples given in this section are specific to unix pathnames. Pathnames for other operating systems have different external representations.
Pathname objects are usually created by parsing filenames (character strings) into component parts. MIT Scheme provides operations that convert filenames into pathnames and vice versa.
(parse-namestring object #f #f).
(->pathname "foo") => #[pathname 65 "foo"] (->pathname "/usr/morris") => #[pathname 66 "/usr/morris"]
This procedure does not do defaulting of pathname components.
The optional arguments are used to determine what syntax should be used
for parsing the string. In general this is only really useful if your
implementation of MIT Scheme supports more than one file system,
otherwise you would use ->pathname. If given, host must be
a host object or #f, and defaults must be a pathname.
Host specifies the syntax used to parse the string. If host
is not given or #f, the host component from defaults is
used instead; if defaults is not given, the host component from
*default-pathname-defaults* is used.
->namestring returns a newly allocated string that is the
filename corresponding to pathname.
(->namestring (->pathname "/usr/morris/minor.van"))
=> "/usr/morris/minor.van"
pathname-simplify might not always be able to simplify the
pathname, e.g. on unix with symbolic links the directory
`/usr/morris/../' need not be the same as `/usr/'. In cases
of uncertainty the behavior is conservative, returning the original or a
partly simplified pathname.
(pathname-simplify "/usr/morris/../morris/dance")
=> #[pathname "/usr/morris/dance"]
A pathname object always has six components, described below. These components are the common interface that allows programs to work the same way with different file systems; the mapping of the pathname components into the concepts peculiar to each file system is taken care of by the Scheme implementation.
Note that a pathname is not necessarily the name of a specific file.
Rather, it is a specification (possibly only a partial specification) of
how to access a file. A pathname need not correspond to any file that
actually exists, and more than one pathname can refer to the same file.
For example, the pathname with a version of newest may refer to
the same file as a pathname with the same components except a certain
number as the version. Indeed, a pathname with version newest
may refer to different files as time passes, because the meaning of such
a pathname depends on the state of the file system. In file systems
with such facilities as "links", multiple file names, logical devices,
and so on, two pathnames that look quite different may turn out to
address the same file. To access a file given a pathname, one must do a
file-system operation such as open-input-file.
Two important operations involving pathnames are parsing and merging. Parsing is the conversion of a filename (which might be something supplied interactively by the users when asked to supply the name of a file) into a pathname object. This operation is implementation-dependent, because the format of filenames is implementation-dependent. Merging takes a pathname with missing components and supplies values for those components from a source of default values.
Not all of the components of a pathname need to be specified. If a
component of a pathname is missing, its value is #f.
Before the file system interface can do anything interesting with a
file, such as opening the file, all the missing components of a pathname
must be filled in. Pathnames with missing components are used
internally for various purposes; in particular, parsing a namestring
that does not specify certain components will result in a pathname with
missing components.
Any component of a pathname may be the symbol unspecific, meaning
that the component simply does not exist, for file systems in which such
a value makes no sense. For example, unix, DOS, Windows, and OS/2
file systems usually do not support version numbers, so the version
component for such a host might be
unspecific.(23)
Each component in a pathname is typically one of the following (with some exceptions that will be described below):
#f
wild
unspecific
The host, directory, and version pathname components are exceptions to
these rules in that they may never be strings, although the values
#f, wild, and unspecific are allowed with their
usual meanings. Here are the other values allowed for these components:
host? predicate.
absolute or the symbol relative. If the first
element in the list is the symbol absolute, then the directory
component (and subsequently the pathname) is absolute; the first
component in the sequence is to be found at the "root" of the file
system. If the directory is relative then the
first component is to be found in some as yet unspecified directory;
typically this is later specified to be the current working
directory.
Aside from absolute and relative, which may only appear as
the first element of the list, each subsequent element in the list is
either a string or the symbol wild (each with the same meaning as
described above), or up, which means the next directory is the
"parent" of the previous one. up corresponds to the file
`..' in unix file systems.
In file systems that do not have "hierarchical" structure, a specified
directory component will always be a list whose first element is
absolute. If the system does not support directories other than a
single global directory, the list will have no other elements. If the
system supports "flat" directories, i.e. a global set of directories
with no subdirectories, then the list will contain a second element,
which is either a string or wild. In other words, a
non-hierarchical file system is treated as if it were hierarchical, but
the hierarchical features are unused. This representation is somewhat
inconvenient for such file systems, but it discourages programmers from
making code depend on the lack of a file hierarchy. Fortunately few
such file systems are in common use today.
newest, which
means to choose the largest available version number for that file; or
the symbol oldest, which means to choose the smallest version
number. In the future some other possible values may be added, e.g.
installed. Note that in the current implementation there are no
file systems that support version numbers; thus this component is not
used and should be specified as #f.
(make-pathname #f #f '(absolute "usr" "morris") "foo" "scm" #f)
=> #[pathname 67 "/usr/morris/foo.scm"]
(define x (->pathname "/usr/morris/foo.scm")) (pathname-host x) => #[host 1] (pathname-device x) => unspecific (pathname-directory x) => (absolute "usr" "morris") (pathname-name x) => "foo" (pathname-type x) => "scm" (pathname-version x) => unspecific
unspecific because this might not be permitted in some
situations.
(define p (->pathname "/usr/blisp/rel15"))
p
=> #[pathname 71 "/usr/blisp/rel15"]
(pathname-new-name p "rel100")
=> #[pathname 72 "/usr/blisp/rel100"]
(pathname-new-directory p '(relative "test" "morris"))
=> #[pathname 73 "test/morris/rel15"]
p
=> #[pathname 71 "/usr/blisp/rel15"]
pathname-new-component
operations, except that they only change the specified component
if it has the value #f in pathname.
#t if object is a pathname; otherwise returns
#f.
#t if pathname1 is equivalent to pathname2;
otherwise returns #f.
Pathnames are equivalent if all of their components are equivalent,
hence two pathnames that are equivalent must identify the same file or
equivalent partial pathnames.
However, the converse is not true: non-equivalent pathnames may specify
the same file (e.g. via absolute and relative directory components),
and pathnames that specify no file at all (e.g. name and directory
components unspecified) may be equivalent.
#t if pathname is an absolute rather than relative
pathname object; otherwise returns #f. Specifically, this
procedure returns #t when the directory component of
pathname is a list starting with the symbol absolute, and
returns #f in all other cases. All pathnames are either absolute
or relative, so if this procedure returns #f, the argument is a
relative pathname.
#t if pathname contains any wildcard components;
otherwise returns #f.
*default-pathname-defaults* and default-version defaults
to newest.
The pathnames are combined by components: if pathname has a
non-missing component, that is the resulting component, otherwise the
component from defaults is used.
The default version can be #f to preserve the information that
the component was missing from pathname.
The directory component is handled specially: if both pathnames have
directory components that are lists, and the directory component from
pathname is relative (i.e. starts with relative), then the
resulting directory component is formed by appending pathname's
component to defaults's component.
For example:
(define path1 (->pathname "scheme/foo.scm"))
(define path2 (->pathname "/usr/morris"))
path1
=> #[pathname 74 "scheme/foo.scm"]
path2
=> #[pathname 75 "/usr/morris"]
(merge-pathnames path1 path2)
=> #[pathname 76 "/usr/scheme/foo.scm"]
(merge-pathnames path2 path1)
=> #[pathname 77 "/usr/morris.scm"]
The merging rules for the version are more complex and depend on whether pathname specifies a name. If pathname does not specify a name, then the version, if not provided, will come from defaults. However, if pathname does specify a name then the version is not affected by defaults. The reason is that the version "belongs to" some other file name and is unlikely to have anything to do with the new one. Finally, if this process leaves the version missing, then default-version is used.
The net effect is that if the user supplies just a name, then the host, device, directory and type will come from defaults, but the version will come from default-version. If the user supplies nothing, or just a directory, the name, type and version will come over from defaults together.
set-working-directory-pathname! sets this variable to a new
value, computed by merging the new working directory with the variable's
old value.
(define (pathname-default pathname
device directory name type version)
(make-pathname (pathname-host pathname)
(or (pathname-device pathname) device)
(or (pathname-directory pathname) directory)
(or (pathname-name pathname) name)
(or (pathname-type pathname) type)
(or (pathname-version pathname) version)))
file-namestring returns a string
representing just the name, type and version
components of pathname; the result of directory-namestring
represents just the host, device, and directory
components; and host-namestring returns a string for just the
host portion.
enough-namestring takes another argument, defaults.
It returns an abbreviated namestring that is just sufficient to identify
the file named by pathname when considered relative to the
defaults (which defaults to *default-pathname-defaults*).
(file-namestring "/usr/morris/minor.van")
=> "minor.van"
(directory-namestring "/usr/morris/minor.van")
=> "/usr/morris/"
(enough-namestring "/usr/morris/men")
=> "men" ;perhaps
file-pathname returns a pathname with just the
name, type and version components of pathname.
The result of directory-pathname is a pathname containing the
host, device and directory components of pathname.
enough-pathname takes another argument, defaults.
It returns an abbreviated pathname that is just sufficient to identify
the file named by pathname when considered relative to the
defaults (which defaults to *default-pathname-defaults*).
These procedures are similar to file-namestring,
directory-namestring and enough-namestring, but they
return pathnames instead of strings.
pathname-as-directory.
(directory-pathname-as-file (->pathname "/usr/blisp/"))
=> #[pathname "/usr/blisp"]
directory-pathname-as-file.
(pathname-as-directory (->pathname "/usr/blisp/rel5"))
=> #[pathname "/usr/blisp/rel5/"]
This section gives some standard operations on host objects, and some procedures that return some useful pathnames.
#t if object is a pathname host; otherwise returns
#f.
#t if host1 and host2 denote the same
pathname host; otherwise returns #f.
local-host. If
the initialization file does not exist this procedure returns #f.
Under unix, the init file is called `.scheme.init'; under Windows
and OS/2, the init file is called `scheme.ini'. In either case, it
is located in the user's home directory, which is computed by
user-homedir-pathname.
local-host. The
concept of a "home directory" is itself somewhat
implementation-dependent, but it should be the place where the user
keeps personal files, such as initialization files and mail.
Under unix, the user's home directory is specified by the HOME
environment variable. If this variable is undefined, the user name is
computed using the getlogin system call, or if that fails, the
geteuid system call. The resulting user name is passed to the
getpwnam system call to obtain the home directory.
Under OS/2, the user's home directory is specified by the HOME
environment variable. If this variable is undefined, but the
USERDIR and USER environment variables are defined, then
the user's home directory is `%USERDIR%\%USER%'. If only
USERDIR is defined, then the user's home directory is
`%USERDIR%\nouser'. If none of these variables is defined, then
the home directory is the root directory of the current drive.
Under Windows, the user's home directory is computed by examining
several environment variables, in the following order. If
HOMEPATH is defined, the home directory is
`%HOMEDRIVE%%HOMEPATH%'. If HOME is defined, the home
directory is `%HOMEDRIVE%%HOME%'. If USERDIR and
USERNAME are defined, the home directory is
`%USERDIR%\%USERNAME%'. If USERDIR and USER are
defined, the home directory is `%USERDIR%\%USER%'. If
USERDIR is defined, the home directory is
`%USERDIR%\nouser'. If none of these variables is defined, then
the home directory is the root directory of the current drive.
condition-type:file-operation-error is signalled if
pathname cannot be located on the library search path.
(system-library-pathname "compiler.com")
=> #[pathname 45 "/usr/local/lib/mit-scheme/compiler.com"]
condition-type:file-operation-error is signalled if
pathname cannot be located on the library search path.
(system-library-directory-pathname "options")
=> #[pathname 44 "/usr/local/lib/mit-scheme/options/"]
When MIT Scheme is started, the current working
directory (or simply, working directory) is initialized in an
operating-system dependent manner; usually, it is the directory in which
Scheme was invoked. The working directory can be determined from within
Scheme by calling the pwd procedure, and changed by calling the
cd procedure. Each REP loop has its own working directory,
and inferior REP loops initialize their working directory from the
value in effect in their superior at the time they are created.
pwd is an alias for
working-directory-pathname; the long name is intended for
programs and the short name for interactive use.
pathname-as-directory. cd is an alias for
set-working-directory-pathname!; the long name is intended for
programs and the short name for interactive use.
Additionally, set-working-directory-pathname! modifies the value
of *default-pathname-defaults* by merging the new working
directory into it.
When this procedure is executed in the top-level REP loop, it changes the working directory of the running Scheme executable.
(set-working-directory-pathname! "/usr/morris/blisp")
=> #[pathname "/usr/morris/blisp/"]
(set-working-directory-pathname! "~")
=> #[pathname "/usr/morris/"]
This procedure signals an error if filename does not refer to an existing directory.
If filename describes a relative rather than absolute pathname, this procedure interprets it as relative to the current working directory, before changing the working directory.
(working-directory-pathname)
=> #[pathname "/usr/morris/"]
(set-working-directory-pathname! "foo")
=> #[pathname "/usr/morris/foo/"]
pathname-as-directory. In addition to binding the working
directory, with-working-directory-pathname also binds the
variable *default-pathname-defaults*, merging the old value of
that variable with the new working directory pathname. Both bindings
are performed in exactly the same way as dynamic binding of a variable
(see section Dynamic Binding).
This section describes procedures that manipulate files and directories.
Any of these procedures can signal a number of errors for many reasons.
The specifics of these errors are much too operating-system dependent to
document here. However, if such an error is signalled by one of
these procedures, it will be of type
condition-type:file-operation-error.
#t if filename is an existing file or directory;
otherwise returns #f. In operating systems that support symbolic
links, if the file is a symbolic link, this procedure tests the
existence of the file linked to, not the link itself.
delete-file, but returns a boolean value indicating whether
an error occurred during the deletion. If no errors occurred, #t
is returned. If an error of type condition-type:file-error or
condition-type:port-error is signalled, #f is returned.
condition-type:file-operation-error is signalled if the
appropriate file cannot be located within the file system.
call-with-temporary-file-pathname calls
temporary-file-pathname to create a temporary file, then calls
procedure with one argument, the pathname referring to that file.
When procedure returns, if the temporary file still exists, it is
deleted; then, the value yielded by procedure is returned. If
procedure escapes from its continuation, and the file still
exists, it is deleted.
TEMP environment variable, if any.
TMP environment variable, if any.
*default-pathname-defaults*.)
#t if the file named filename exists and is a
directory. Otherwise returns #f. In operating systems that
support symbolic links, if filename names a symbolic link, this
examines the file linked to, not the link itself.
#f.
#t if filename names a file that can be opened for
input; i.e. a readable file. Otherwise returns #f.
#t if filename names a file that can be opened for
output; i.e. a writable file. Otherwise returns #f.
#t if filename names a file that can be executed.
Otherwise returns #f. Under unix, an executable file is
identified by its mode bits. Under OS/2, an executable file has one of
the file extensions `.exe', `.com', `.cmd', or
`.bat'. Under Windows, an executable file has one of the file
extensions `.exe', `.com', or `.bat'.
0 and 7
inclusive; it is a bitwise-encoded predicate selector with 1
meaning "executable", 2 meaning "writable", and 4
meaning "readable". file-access returns #t if
filename exists and satisfies the predicates selected by
mode. For example, if mode is 5, then filename
must be both readable and executable. If filename doesn't exist,
or if it does not satisfy the selected predicates, #f is
returned.
file-modes returns an
exact non-negative integer encoding the file's permissions. The
encoding of this integer is operating-system dependent, but typically it
contains bits that indicate what users and processes are allowed to
read, write, or execute the file. If filename does not name an
existing file, #f is returned.
file-modes. set-file-modes! modifies the file's
permissions to be those encoded by modes.
file-modification-time returns #f.
In operating systems that support symbolic links, if filename
names a symbolic link, file-modification-time returns the
modification time of the file linked to. An alternate procedure,
file-modification-time-direct, returns the modification time of
the link itself; in all other respects it is identical to
file-modification-time. For symmetry,
file-modification-time-indirect is a synonym of
file-modification-time.
file-access-time returns #f.
Some operating systems don't implement access times; in those systems
file-access-time returns an unspecified value.
In operating systems that support symbolic links, if filename
names a symbolic link, file-access-time returns the access time
of the file linked to. An alternate procedure,
file-access-time-direct, returns the access time of the link
itself; in all other respects it is identical to
file-access-time. For symmetry, file-access-time-indirect
is a synonym of file-access-time.
file-access-time and file-modification-time,
respectively. set-file-times! alters the access and modification
times of the file specified by filename to the values given by
access-time and modification-time, respectively. For
convenience, either of the time arguments may be specified as #f;
in this case the corresponding time is not changed.
set-file-times! returns an unspecified value.
#f is returned. Otherwise, the file is created and #t is
returned. This is an atomic test-and-set operation, so it is useful as
a synchronization mechanism.
#f.
In operating systems that support symbolic links, if filename
names a symbolic link, file-attributes returns the attributes of
the link itself. An alternate procedure,
file-attributes-indirect, returns the attributes of the file
linked to; in all other respects it is identical to
file-attributes. For symmetry, file-attributes-direct is
a synonym of file-attributes.
The information returned by file-attributes is decoded by
accessor procedures. The following accessors are defined in all
operating systems:
#t if the file is a directory, a character string
(the name linked to) if a symbolic link, or #f for all other
types of file.
1.
The following additional accessors are defined under unix:
The following additional accessors are defined under OS/2:
->pathname. The directory specified by directory is
read, and the contents of the directory is returned as a newly allocated
list of absolute pathnames. The result is sorted according to the usual
sorting conventions for directories, unless sort? is specified as
#f. If directory has name, type, or version components,
the returned list contains only those pathnames whose name, type, and
version components match those of directory; wild or
#f as one of these components means "match anything".
The MIT Scheme error system provides a uniform mechanism for the signalling of errors and other exceptional conditions. The simplest and most generally useful procedures in the error system are:
error
warn
ignore-errors
ignore-errors.
More demanding applications require more powerful facilities. To give a concrete example, suppose you want floating-point division to return a very large number whenever the denominator is zero. This behavior can be implemented using the error system.
The Scheme arithmetic system can signal many different kinds of errors, including floating-point divide by zero. In our example, we would like to handle this particular condition specially, allowing the system to handle other arithmetic errors in its usual way.
The error system supports this kind of application by providing mechanisms for distinguishing different types of error conditions and for specifying where control should be transferred should a given condition arise. In this example, there is a specific object that represents the "floating-point divide by zero" condition type, and it is possible to dynamically specify an arbitrary Scheme procedure to be executed when a condition of that type is signalled. This procedure then finds the stack frame containing the call to the division operator, and returns the appropriate value from that frame.
Another useful kind of behavior is the ability to specify uniform handling for related classes of conditions. For example, it might be desirable, when opening a file for input, to gracefully handle a variety of different conditions associated with the file system. One such condition might be that the file does not exist, in which case the program will try some other action, perhaps opening a different file instead. Another related condition is that the file exists, but is read protected, so it cannot be opened for input. If these or any other related conditions occur, the program would like to skip this operation and move on to something else.
At the same time, errors unrelated to the file system should be treated in
their usual way. For example, calling car on the argument 3
should signal an error. Or perhaps the name given for the file is
syntactically incorrect, a condition that probably wants to be handled
differently from the case of the file not existing.
To facilitate the handling of classes of conditions, the error system taxonomically organizes all condition types. The types are related to one another by taxonomical links, which specify that one type is a "kind of" another type. If two types are linked this way, one is considered to be a specialization of the other; or vice-versa, the second is a generalization of the first. In our example, all of the errors associated with opening an input file would be specializations of the condition type "cannot open input file".
The taxonomy of condition types permits any condition type to have no
more than one immediate generalization. Thus, the condition types form
a forest (set of trees). While users can create new trees, the standard
taxonomy (see section Condition-Type Taxonomy) is rooted at
condition-type:serious-condition, condition-type:warning,
condition-type:simple-condition, and
condition-type:breakpoint; users are encouraged to add new
subtypes to these condition types rather than create new trees in the
forest.
To summarize, the error system provides facilities for the following tasks. The sections that follow will describe these facilities in more detail.
error. The signal-condition procedure provides the
most general signalling mechanism.
bind-condition-handler procedure. Individual handlers have
complete control over the handling of a condition, and additionally may
decide not to handle a particular condition, passing it on to previously
bound handlers.
with-restart procedure provides a means for
condition-signalling code to communicate to condition-handling code what
must be done to proceed past the condition. Handlers can examine the
restarts in effect when a condition was signalled, allowing a structured
way to continue an interrupted computation.
Once a condition instance has been created using make-condition
(or any condition constructor), it can be signalled. The act of
signalling a condition is separated from the act of creating the
condition to allow more flexibility in how conditions are handled. For
example, a condition instance could be returned as the value of a
procedure, indicating that something unusual has happened, to allow the
caller to clean up some state. The caller could then signal the
condition once it is ready.
A more important reason for having a separate condition-signalling mechanism is that it allows resignalling. When a signalled condition has been caught by a particular handler, and the handler decides that it doesn't want to process that particular condition, it can signal the condition again. This is one way to allow other handlers to get a chance to see the condition.
warn is more appropriate).
error signals a condition (using signal-condition), and if
no handler for that condition alters the flow of control (by invoking a
restart, for example) it calls the procedure
standard-error-handler, which normally prints an error message
and stops the computation, entering an error REPL. Under normal
circumstances error will not return a value (although an
interactive debugger can be used to force this to occur).
Precisely what condition is signalled depends on the first argument to
error. If reason is a condition, then that condition is
signalled and the arguments are ignored. If reason is a
condition type, then a new instance of this type is generated and
signalled; the arguments are used to generate the values of the
fields for this condition type (they are passed as the field-plist
argument to make-condition). In the most common case, however,
reason is neither a condition nor a condition type, but rather a
string or symbol. In this case a condition of type
condition-type:simple-error is created with the message
field containing the reason and the irritants field
containing the arguments.
warn rather than
error. As with error, warn first calls
signal-condition; the condition that is signalled is chosen
exactly as in error except that a condition of type
condition-type:simple-warning is signalled if reason is
neither a condition nor a condition type. If the condition is not
handled, warn calls the procedure
standard-warning-handler, which normally prints a warning message
and continues the computation by returning from warn.
warn establishes a restart named muffle-warning before
calling signal-condition. This allows a signal handler to
prevent the generation of the warning message by calling
muffle-warning. The value of a call to warn is
unspecified.
signal-condition depends on the condition
type of which condition is an instance, the condition types set by
break-on-signals, and the handlers established by
bind-condition-handler and bind-default-condition-handler.
If the condition is an instance of a type that is a specialization
of any of the types specified by break-on-signals, then a
breakpoint REPL is initiated. Otherwise (or when that REPL
returns), the handlers established by bind-condition-handler are
checked, most recent first. Each applicable handler is invoked, and the
search for a handler continues if the handler returns normally. If all
applicable handlers return, then the applicable handlers established by
bind-default-condition-handler are checked, again most recent
first. Finally, if no handlers apply (or all return in a normal
manner), signal-condition returns an unspecified value.
Note: unlike many other systems, the MIT Scheme runtime library
does not establish handlers of any kind. (However, the Edwin
text editor uses condition handlers extensively.) Thus, calls to
signal-condition will return to the caller unless there are user
supplied condition handlers, as the following example shows:
(signal-condition (make-condition condition-type:error (call-with-current-continuation (lambda (x) x)) '() ; no restarts '())) ; no fields => unspecified
By convention, error messages (and in general, the reports generated by
write-condition-report) should consist of one or more complete
sentences. The usual rules for sentences should be followed: the first
word of the sentence should be capitalized, and the sentence should be
terminated by a period. The message should not contain extraneous
whitespace such as line breaks or indentation.
The error system provides a simple formatting language that allows the programmer to have some control over the printing of error messages. This formatting language will probably be redesigned in a future release.
Error messages typically consist of a string describing the error,
followed by some irritant objects. The string is printed using
display, and the irritants are printed using write,
typically with a space between each irritant. To allow simple
formatting, we introduce a noise object, printed using
display. The irritant list may contain ordinary objects
interspersed with noise objects. Each noise object is printed using
display, with no extra whitespace, while each normal object is
printed using write, prefixed by a single space character.
Here is an example:
(define (error-within-procedure message irritant procedure)
(error message
irritant
(error-irritant/noise "within procedure")
procedure
(error-irritant/noise ".")))
This would format as follows:
(error-within-procedure "Bad widget" 'widget-32 'invert-widget) error--> Bad widget widget-32 within procedure invert-widget.
Here are the operations supporting error messages:
The occurrence of a condition is signalled using
signal-condition. signal-condition attempts to locate and
invoke a condition handler that is prepared to deal with the type
of condition that has occurred. A condition handler is a procedure of
one parameter, the condition that is being signalled. A procedure is
installed as a condition handler by calling
bind-condition-handler (to establish a handler that is in effect
only while a particular thunk is executing) or
bind-default-condition-handler (to establish a handler that is in
effect permanently). As implied by the name, handlers created by
bind-default-condition-handler are invoked only after all other
applicable handlers have been invoked.
A handler may process a signal in any way it deems appropriate, but the common patterns are:
signal-condition.
signal-condition with either
the same condition or a newly created one. In order to support this,
signal-condition runs handler in such a way that a
subsequent call to signal-condition sees only the handlers that
were established prior to this one.
As an aid to debugging condition handlers, Scheme maintains a set of
condition types that will cause an interactive breakpoint to occur prior
to normal condition signalling. That is, signal-condition
creates a new REPL prior to its normal operation when its argument
is a condition that is a specialization of any of these types. The
procedure break-on-signals establishes this set of condition
types.
condition-type:error
(including those produced by calls to error) and immediately
terminates the execution of thunk and returns from the call to
ignore-errors with the signalled condition as its value. If
thunk returns normally, its value is returned from
ignore-errors.
Notice that ignore-errors does not "turn off signalling" or
condition handling. Condition handling takes place in the normal manner
but conditions specialized from condition-type:error are trapped
rather than propogated as they would be by default.
signal-condition for
a description of the mechanism used to invoke handlers.
By special extension, if condition-types is the empty list then the handler is called for all conditions.
signal-condition for a description of the
mechanism used to invoke handlers.
By special extension, if condition-types is the empty list then the handler is called for all conditions.
signal-condition to create an interactive REPL
before it signals a condition that is a specialization of any of the
types in the list of condition-types. This can be extremely
helpful when trying to debug code that uses custom condition handlers.
In order to create a REPL when any condition type is
signalled it is best to actually put a breakpoint on entry to
signal-condition.
error after it calls
signal-condition. It normally creates creates a new REPL
with the prompt "error>" (but see standard-error-hook).
In order to simulate the effect of calling error, code may call
signal-condition directly and then call
standard-error-handler if signal-condition returns.
standard-error-handler, and hence error. It is intended
to be bound with fluid-let and is normally #f. It may be
changed to a procedure of one argument and will then be invoked (with
standard-error-hook rebound to #f) by
standard-error-handler just prior to starting the error
REPL. It is passed one argument, the condition being signalled.
warn after it calls
signal-condition. The normal behavior of
standard-warning-handler is to print a message (but see
standard-warning-hook). More precisely, the message is printed
to the port returned by notification-output-port. The message is
formed by first printing the string "Warning: " to this port, and
then calling write-condition-report on condition and the port.
In order to simulate the effect of calling warn, code may call
signal-condition directly and then call
standard-warning-handler if signal-condition returns.
(This is not sufficient to implement the muffle-warning protocol,
however. For that purpose an explicit restart must be provided.)
standard-warning-handler, and hence warn. It is intended
to be bound with fluid-let and is normally #f. It may be
changed to a procedure of one argument and will then be invoked (with
standard-warning-hook rebound to #f) by
standard-warning-handler in lieu of writing the warning message.
It is passed one argument, the condition being signalled.
The Scheme error system provides a mechanism, known as restarts,
that helps coordinate condition-signalling code with condition-handling
code. A module of code that detects and signals conditions can provide
procedures (using with-simple-restart or with-restart) to
be invoked by handlers that wish to continue, abort, or restart the
computation. These procedures, called restart effectors, are
encapsulated in restart objects.
When a condition object is created, it contains a set of restart
objects, each of which contains a restart effector. Condition handlers
can inspect the condition they are handling (using find-restart
to find restarts by name, or condition/restarts to see the entire
set), and they can invoke the associated effectors (using
invoke-restart or invoke-restart-interactively).
Effectors can take arguments, and these may be computed directly by the
condition-handling code or by gathering them interactively from the
user.
The names of restarts can be chosen arbitrarily, but the choice of name is significant. These names are used to coordinate between the signalling code (which supplies names for restarts) and the handling code (which typically chooses a restart effector by the name of its restart). Thus, the names specify the restart protocol implemented by the signalling code and invoked by the handling code. The protocol indicates the number of arguments required by the effector code as well as the semantics of the arguments.
Scheme provides a conventional set of names (hence, protocols) for
common use. By choosing the names of restarts from this set, signalling
code can indicate that it is able to perform a small set of fairly
common actions (abort, continue, muffle-warning,
retry, store-value, use-value). In turn, simple
condition-handling code can look for the kind of action it wishes to
perform and simply invoke it by name. All of Scheme's conventional
names are symbols, although in general restart names are not restricted
to any particular data type. In addition, the object #f is
reserved to indicate the "not for automated use" protocol: these
restarts should be activated only under human control.
Restarts themselves are first-class objects. They encapsulate their
name, a procedure (known as the effector) to be executed if they
are invoked, and a thunk (known as the reporter) that can be
invoked to display a description of the restart (used, for example, by
the interactive debugger). Invoking a restart is an indication that a
handler has chosen to accept control for a condition; as a consequence,
the effector of the restart should not return, since this would
indicate that the handler declined to handle the condition. Thus, the
effector should call a continuation captured before the
condition-signalling process began. The most common pattern of usage by
signalling code is encapsulated in with-simple-restart.
Within this chapter, a parameter named restarts will accept any of the following values:
condition/restarts is called on the
condition, and the resulting list of restarts is used in place of the
condition.
bound-restarts. The procedure bound-restarts
is called (with no arguments), and the resulting list of restarts is
used in place of the symbol.
bound-restarts.
If the restart created by with-simple-restart is invoked it
simply aborts the computation in progress by returning an unspecified
value from the call to with-simple-restart. Otherwise
with-simple-restart returns the value computed by thunk.
(with-simple-restart 'george "This restart is named george."
(lambda () 3)) => 3
(with-simple-restart 'george "This restart is named george."
(lambda ()
(invoke-restart (find-restart 'george)))) => unspecific
(with-simple-restart 'george "This restart is named george."
(lambda () (car 3)))
;The object 3, passed as the first argument to car,
; is not the correct type.
;To continue, call RESTART with an option number:
; (RESTART 3) => Specify an argument to use in its place.
; (RESTART 2) => This restart is named george.
; (RESTART 1) => Return to read-eval-print level 1.
invoke-restart. Interactor
specifies the arguments that are to be passed to effector when it
is invoked interactively; it may be either a procedure of no arguments,
or #f. If interactor is #f, this restart is not
meant to be invoked interactively.
The value returned by with-restart is the value returned by
thunk. Should the restart be invoked by a condition handler,
however, the effector will not return back to the handler that
invoked it. Instead, the effector should call a continuation
created before the condition-signalling process began, and
with-restart will therefore not return in the normal manner.
(define (by-george! thunk)
; This code handles conditions that arise while executing thunk
; by invoking the GEORGE restart, passing 1 and 2 to the restart's
; effector code.
(bind-condition-handler '() ; All conditions
(lambda (condition)
(invoke-restart (find-restart 'george) 1 2))
thunk))
(define (can-george! thunk)
; This code provides a way of handling errors: the GEORGE restart.
; In order to GEORGE you must supply two values.
(lambda ()
(call-with-current-continuation
(lambda (kappa)
(with-restart
'george ; Name
"This restart is named george." ; Reporter
(lambda (a b) ; Effector
(kappa (list 'george a b)))
values ; Interactor
thunk))))) ; Thunk
(by-george! (can-george! (lambda () -3)) => -3
(by-george! (can-george! (lambda () (car 'x)))) => (george 1 2)
Scheme supports six standard protocols for restarting from a condition, each encapsulated using a named restart (for use by condition-signalling code) and a simple procedure (for use by condition-handling code). Unless otherwise specified, if one of these procedures is unable to find its corresponding restart, it returns immediately with an unspecified value.
Each of these procedures accepts an optional argument restarts, which is described above in section Restarts.
abort. The
corresponding effector takes no arguments and abandons the current line
of computation. This is the restart provided by Scheme's REPL.
If there is no restart named abort, this procedure signals an
error of type condition-type:no-such-restart.
continue. The corresponding effector takes no arguments and
continues the computation beyond the point at which the condition was
signalled.
muffle-warning. The corresponding effector takes no arguments
and continues the computation beyond the point at which any warning
message resulting from the condition would be presented to the user.
The procedure warn establishes a muffle-warning restart
for this purpose.
If there is no restart named muffle-warning, this procedure
signals an error of type condition-type:no-such-restart.
retry.
The corresponding effector takes no arguments and simply retries the
same computation that triggered the condition. The condition may
reoccur, of course, if the root cause has not been eliminated. The code
that signals a "file does not exist" error can be expected to supply a
retry restart. The restart would be invoked after first creating
the missing file, since the computation is then likely to succeed if it
is simply retried.
store-value, after first storing new-value. The
corresponding effector takes one argument, new-value, and stores
it away in a restart-dependent location, then retries the same
computation that triggered the condition. The condition may reoccur, of
course, if the root cause has not been eliminated. The code that
signals an "unassigned variable" error can be expected to supply a
store-value restart; this would store the value in the variable
and continue the computation.
use-value,
but substituting new-value for a value that previously caused a
failure. The corresponding effector takes one argument,
new-value, and retries the same computation that triggered the
condition with the new value substituted for the failing value. The
condition may reoccur, of course, if the new value also induces the
condition.
The code that signals an "unassigned variable" error can be expected
to supply a use-value restart; this would simply continue the
computation with new-value instead of the value of the variable.
Contrast this with the retry and store-value restarts. If
the retry restart is used it will fail because the variable still
has no value. The store-value restart could be used, but it
would alter the value of the variable, so that future references to the
variable would not be detected.
Restarts are a general mechanism for establishing a protocol between
condition-signalling and condition-handling code. The Scheme error
system provides "packaging" for a number of common protocols. It also
provides lower-level hooks that are intended for implementing customized
protocols. The mechanism used by signalling code (with-restart
and with-simple-restart) is used for both purposes.
Four additional operations are provided for the use of
condition-handling code. Two operations (bound-restarts and
find-restart) allow condition-handling code to locate active
restarts. The other two operations (invoke-restart and
invoke-restart-interactively) allow restart effectors to be
invoked once the restart object has been located.
In addition, there is a data abstraction that provides access to the information encapsulated in restart objects.
bound-restarts should be used with caution by
condition-handling code, since it reveals all restarts that are active
at the time it is called, rather than at the time the condition was
signalled. It is useful, however, for collecting the list of restarts
for inclusion in newly generated condition objects or for inspecting the
current state of the system.
find-restart is usually passed the name of a particular restart
and the condition object that has been signalled. In this way
the handler finds only restarts that were available when the condition
was created (usually the same as when it was signalled). If
restarts is omitted, the currently active restarts would be used,
and these often include restarts added after the condition ocurred.
invoke-restart is intended for
use by condition-handling code that understands the protocol implemented
by restart, and can therefore calculate and pass an appropriate
set of arguments.
If a condition handler needs to interact with a user to gather the
arguments for an effector (e.g. if it does not understand the protocol
implemented by restart) invoke-restart-interactively should
be used instead of invoke-restart.
invoke-restart-interactively is intended for calling interactive
restarts (those for which restart/interactor is not #f).
For convenience, invoke-restart-interactively will call the
restart's effector with no arguments if the restart has no interactor;
this behavior may change in the future.
A restart object is very simple, since it encapsulates only a name, effector, interactor, and description.
#f if and only if object is not a restart.
#f for its predefined names, programs
may use arbitrary objects (name equivalence is tested using eq?).
invoke-restart and
invoke-restart-interactively capture the most common invocation
patterns.
#f. Normally this
procedure is not used since invoke-restart-interactively captures
the most common usage. Thus restart/interactor is most useful as
a predicate to determine if restart is intended to be invoked
interactively.
A condition, in addition to the information associated with its type, usually contains other information that is not shared with other conditions of the same type. For example, the condition type associated with "unbound variable" errors does not specify the name of the variable that was unbound. The additional information is captured in a condition object, also called a condition instance.
In addition to information that is specific to a given type of condition (such as the variable name for "unbound variable" conditions), every condition instance also contains a continuation that encapsulates the state of the computation in which the condition occurred. This continuation is used for analyzing the computation to learn more about the context in which the condition occurred. It is not intended to provide a mechanism for continuing the computation; that mechanism is provided by restarts.
Scheme provides four procedures that take a condition type as input and
produce operations on the corresponding condition object. These are
reminiscent of the operations on record types that produce record
operators (see section Records). Given a condition type it is possible to
generate: a constructor for instances of the type (using
condition-constructor); an accessor to extract the contents of a
field in instances of the type (using condition-accessor); a
predicate to test for instances of the type (using
condition-predicate); and a procedure to create and signal an
instance of the type (using condition-signaller).
Notice that the creation of a condition object is distinct from signalling an occurrence of the condition. Condition objects are first-class; they may be created and never signalled, or they may be signalled more than once. Further notice that there are no procedures for modifying conditions; once created, a condition cannot be altered.
condition-constructor has
signature
(lambda (continuation restarts . field-values) ...)
where the field-names correspond to the field-values. The
constructor argument restarts is described in section Restarts.
Conditions created by the constructor procedure have #f for the
values of all fields other than those specified by field-names.
For example, the following procedure make-simple-warning
constructs a condition of type condition-type:simple-warning
given a continuation (where the condition occurred), a description of
the restarts to be made available, a warning message, and a list of
irritants that caused the warning:
(define make-simple-warning
(condition-constructor condition-type:simple-warning
'(message irritants)))
condition-accessor signals
error:bad-range-argument if the field-name isn't one of the
named fields of condition-type; the returned procedure will signal
error:wrong-type-argument if passed an object other than a
condition of type condition-type or one of its specializations.
If it is known in advance that a particular field of a condition will be
accessed repeatedly it is worth constructing an accessor for the field
using condition-accessor rather than using the (possibly more
convenient, but slower) access-condition procedure.
There are several standard procedures that are conventionally used for
default-handler. If condition-type is a specialization of
condition-type:error, default-handler should be the
procedure standard-error-handler. If condition-type is a
specialization of condition-type:warning, default-handler
should be the procedure standard-warning-handler. If
condition-type is a specialization of
condition-type:breakpoint, default-handler should be the
procedure standard-breakpoint-handler.
The condition data type is abstracted through a predicate
condition? and a set of accessor procedures.
#f if and only if object is not a condition.
#t if the condition is an instance of condition
type condition-type:error or a specialization of it, #f
otherwise.
condition/report-string.
The simple procedures described in this section are built on top of the more detailed abstraction of condition objects described above. While these procedures are sometimes easier to use, they are often less efficient.
(condition-type/field-names condition-type). It is used to
provide values for fields in the condition object; fields with no value
specified are set to #f. Once a condition object has been
created there is no way to alter the values of these fields.
(condition-type/field-names (condition/type condition)).
access-condition looks up the field-name at runtime, so it
is more efficient to use condition-accessor to create an access
function if the same field is to be extracted from several instances of
the same condition type.
write-condition-report on condition
and a string output port, and returning the output collected by the port
as a string.
Each condition has a condition type object associated with it. These objects are used as a means of focusing on related classes of conditions, first by concentrating all of the information about a specific class of condition in a single place, and second by specifying an inheritance relationship between types. This inheritance relationship forms the taxonomic structure of the condition hierarchy (see section Condition-Type Taxonomy).
The following procedures consititute the abstraction for condition types.
#f). For
debugging purposes, the condition type has a name, and instances
of this type contain storage for the fields specified by
field-names (a list of symbols) in addition to the fields common
to all conditions (type, continuation and restarts).
Reporter is used to produce a description of a particular
condition of this type. It may be a string describing the condition, a
procedure of arity two (the first argument will be a condition of this
type and the second a port) that will write the message to the
given port, or #f to specify that the reporter should be taken
from the condition type generalization (or produce an
"undocumented condition of type ..." message if generalization
is #f). The conventions used to form descriptions are spelled
out in section Error Messages.
#t if the condition-type is
condition-type:error or a specialization of it, #f
otherwise.
condition-type/field-names of the generalization of this
condition-type.
#f if and only if object is not a condition type.
The MIT Scheme error system provides a rich set of predefined condition
types. These are organized into a forest through taxonomic links
providing the relationships for "specializes" and "generalizes".
The chart appearing below shows these relationships by indenting all the
specializations of a given type relative to the type. Note that the
variables that are bound to these condition types are prefixed by
`condition-type:'; for example, the type appearing in the following
table as `simple-error' is stored in the variable
condition-type:simple-error. Users are encouraged to add new
condition types by creating specializations of existing ones.
Following the chart are detailed descriptions of the predefined condition types. Some of these types are marked as abstract types. Abstract types are not intended to be used directly as the type of a condition; they are to be used as generalizations of other types, and for binding condition handlers. Types that are not marked as abstract are concrete; they are intended to be explicitly used as a condition's type.
serious-condition
error
simple-error
illegal-datum
wrong-type-datum
wrong-type-argument
wrong-number-of-arguments
datum-out-of-range
bad-range-argument
inapplicable-object
file-error
file-operation-error
derived-file-error
port-error
derived-port-error
variable-error
unbound-variable
unassigned-variable
arithmetic-error
divide-by-zero
floating-point-overflow
floating-point-underflow
control-error
no-such-restart
not-loading
primitive-procedure-error
system-call-error
warning
simple-warning
simple-condition
breakpoint
error procedure when its
first argument is not a condition or condition type. The fields
message and irritants are taken directly from the arguments
to error; message contains an object (usually a string) and
irritants contains a list of objects. The reporter for this type
uses format-error-message to generate its output from
message and irritants.
(error:wrong-type-datum 3.4 "integer") error--> ;The object 3.4 is not an integer. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:wrong-type-datum. The datum and type
fields of the condition are filled in from the corresponding arguments
to the procedure.
#f), the type field contains a
string describing the type that was expected, and the datum field
contains the offending argument.
(+ 'a 3) error--> ;The object a, passed as the first argument to integer-add, ; is not the correct type. ;To continue, call RESTART with an option number: ; (RESTART 2) => Specify an argument to use in its place. ; (RESTART 1) => Return to read-eval-print level 1. (list-copy 3) ;The object 3, passed as an argument to list-copy, is not a list. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:wrong-type-argument. The datum, type
and operator fields of the condition are filled in from the
corresponding arguments to the procedure; the operand field of the
condition is set to #f.
(car 3 4) error--> ;The procedure car has been called with 2 arguments; ; it requires exactly 1 argument. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:wrong-number-of-arguments. The datum,
type and operands fields of the condition are filled in from
the corresponding arguments to the procedure.
(error:datum-out-of-range 3) error--> ;The object 3 is not in the correct range. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:datum-out-of-range. The datum field of the
condition is filled in from the corresponding argument to the procedure.
#f), and the
datum field is the offending argument.
(string-ref "abc" 3) error--> ;The object 3, passed as the second argument to string-ref, ; is not in the correct range. ;To continue, call RESTART with an option number: ; (RESTART 2) => Specify an argument to use in its place. ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:bad-range-argument. The datum and
operator fields of the condition are filled in from the
corresponding arguments to the procedure; the operand field of the
condition is set to #f.
(3 4) error--> ;The object 3 is not applicable. ;To continue, call RESTART with an option number: ; (RESTART 2) => Specify a procedure to use in its place. ; (RESTART 1) => Return to read-eval-print level 1.
filename "/zu/cph/tmp/no-such-file"
verb "delete"
noun "file"
reason "no such file or directory"
operator file-remove
operands ("/zu/cph/tmp/no-such-file")
and would generate a message like this:
(delete-file "/zu/cph/tmp/no-such-file") error--> ;Unable to delete file "/zu/cph/tmp/no-such-file" because: ; No such file or directory. ;To continue, call RESTART with an option number: ; (RESTART 3) => Try to delete the same file again. ; (RESTART 2) => Try to delete a different file. ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:file-operation-error. The fields of the condition
are filled in from the corresponding arguments to the procedure.
condition-type:system-call-error.
condition-type:derived-file-error. The filename and
condition fields of the condition are filled in from the
corresponding arguments to the procedure.
condition-type:system-call-error.
condition-type:derived-port-error. The port and
condition fields of the condition are filled in from the
corresponding arguments to the procedure.
foo error--> ;Unbound variable: foo ;To continue, call RESTART with an option number: ; (RESTART 3) => Specify a value to use instead of foo. ; (RESTART 2) => Define foo to a given value. ; (RESTART 1) => Return to read-eval-print level 1.
foo error--> ;Unassigned variable: foo ;To continue, call RESTART with an option number: ; (RESTART 3) => Specify a value to use instead of foo. ; (RESTART 2) => Set foo to a given value. ; (RESTART 1) => Return to read-eval-print level 1.
(/ 1 0) ;Division by zero signalled by /. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:divide-by-zero. The operator and
operands fields of the condition are filled in from the
corresponding arguments to the procedure.
condition-type:file-operation-error. The operator field
contains the procedure that implements the operation (or a symbol naming
the procedure), and the operands field contains a list of the
arguments that were passed to the procedure. The system-call and
error-type fields contain symbols that describe the specific
system call that was being made and the error that occurred,
respectively; these symbols are completely operating-system dependent.
muffle-warning. The name field contains the name that was
being searched for.
(muffle-warning) error--> ;The restart named muffle-warning is not bound. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
condition-type:no-such-restart. The name field of the
condition is filled in from the corresponding argument to the procedure.
current-load-pathname is called from somewhere other than inside
a file being loaded.
(current-load-pathname) error--> ;No file being loaded. ;To continue, call RESTART with an option number: ; (RESTART 1) => Return to read-eval-print level 1.
warn procedure. The
fields message and irritants are taken directly from the
arguments to warn; message contains an object (usually a
string) and irritants contains a list of objects. The reporter
for this type uses format-error-message to generate its output
from message and irritants.
format-error-message to generate its
output from message and irritants.
MIT Scheme has a simple two-dimensional line-graphics interface that is suitable for many graphics applications. In particular it is often used for plotting data points from experiments. The interface is generic in that it can support different types of graphics devices in a uniform manner. At the present time only two types of graphics device are implemented.
Procedures are available for drawing points, lines, and text; defining the coordinate system; clipping graphics output; controlling some of the drawing characteristics; and controlling the output buffer (for devices that perform buffering). Additionally, devices may support custom operations, such as control of colors.
There are some constraints on the arguments to the procedures described
in this chapter. Any argument named graphics-device must be a
graphics device object that was returned from a call to
make-graphics-device. Any argument that is a coordinate must be
either an exact integer or an inexact real.
#t if the graphics system named by the
symbol graphics-device-type is implemented by the Scheme system.
Otherwise it returns #f, in which case it is an error to attempt
to make a graphics device using graphics-device-type.
make-graphics-device, as each device type typically has a unique
way of specifying the initial size, shape and other attributes.
graphics-type-available?. Graphics-device-type may also be
#f, in which case the graphics device type is chosen by the
system from what is available. This allows completely portable graphics
programs to be written provided no custom graphics operations are used.
When graphics-device-type is #f no further arguments may be
given; each graphics device type will use some "sensible" defaults.
If more control is required then the program should use one of the two
procedures above to dispatch on the available types.
This procedure opens and initializes the device, which remains valid
until explicitly closed by the procedure graphics-close.
Depending on the implementation of the graphics device, if this object
is reclaimed by the garbage collector, the graphics device may remain
open or it may be automatically closed. While a graphics device remains
open the resources associated with it are not released.
Each graphics device has two different coordinate systems associated with it: device coordinates and virtual coordinates. Device coordinates are generally defined by low-level characteristics of the device itself, and often cannot be changed. Most device coordinate systems are defined in terms of pixels, and usually the upper-left-hand corner is the origin of the coordinate system, with x coordinates increasing to the right and y coordinates increasing downwards.
In contrast, virtual coordinates are more flexible in the units employed, the position of the origin, and even the direction in which the coordinates increase. A virtual coordinate system is defined by assigning coordinates to the edges of a device. Because these edge coordinates are arbitrary real numbers, any Cartesian coordinate system can be defined.
All graphics procedures that use coordinates are defined on virtual coordinates. For example, to draw a line at a particular place on a device, the virtual coordinates for the endpoints of that line are given.
When a graphics device is initialized, its virtual coordinate system is
reset so that the left edge corresponds to an x-coordinate of -1,
the right edge to x-coordinate 1, the bottom edge to y-coordinate
-1, and the top edge to y-coordinate 1.
graphics-coordinate-limits will return the new limits. This
operation has no effect on the device's displayed contents.
Note: This operation usually resets the clip rectangle, although it is not guaranteed to do so. If a clip rectangle is in effect when this procedure is called, it is necessary to redefine the clip rectangle afterwards.
The procedures in this section provide the basic drawing capabilities of Scheme's graphics system.
This is equivalent to
(lambda (device x y)
(graphics-bind-drawing-mode device 0
(lambda ()
(graphics-draw-point device x y))))
The following two procedures provide an alternate mechanism for drawing lines, which is more akin to using a plotter. They maintain a cursor, which can be positioned to a particular point and then dragged to another point, producing a line. Sequences of connected line segments can be drawn by dragging the cursor from point to point.
Many graphics operations have an unspecified effect on the cursor. The following exceptions are guaranteed to leave the cursor unaffected:
graphics-device-coordinate-limits graphics-coordinate-limits graphics-enable-buffering graphics-disable-buffering graphics-flush graphics-bind-drawing-mode graphics-set-drawing-mode graphics-bind-line-style graphics-set-line-style
The initial state of the cursor is unspecified.
Two characteristics of graphics output are so useful that they are supported uniformly by all graphics devices: drawing mode and line style. A third characteristic, color, is equally useful (if not more so), but implementation restrictions prohibit a uniform interface.
The drawing mode, an exact integer in the range 0 to
15 inclusive, determines how the figure being drawn is combined
with the background over which it is drawn to generate the final result.
Initially the drawing mode is set to "source", so that the new output
overwrites whatever appears in that place. Useful alternative drawing
modes can, for example, erase what was already there, or invert it.
Altogether 16 boolean operations are available for combining the source (what is being drawn) and the destination (what is being drawn over). The source and destination are combined by the device on a pixel-by-pixel basis as follows:
Mode Meaning ---- ------- 0 ZERO [erase; use background color] 1 source AND destination 2 source AND (NOT destination) 3 source 4 (NOT source) AND destination 5 destination 6 source XOR destination 7 source OR destination 8 NOT (source OR destination) 9 NOT (source XOR destination) 10 NOT destination 11 source OR (NOT destination) 12 NOT source 13 (NOT source) OR destination 14 (NOT source) OR (NOT destination) 15 ONE [use foreground color]
The line style, an exact integer in the range 0 to 7
inclusive, determines which parts of a line are drawn in the foreground
color, and which in the background color. The default line style,
"solid", draws the entire line in the foreground color.
Alternatively, the "dash" style alternates between foreground and
background colors to generate a dashed line. This capability is useful
for plotting several things on the same graph.
Here is a table showing the name and approximate pattern of the different styles. A `1' in the pattern represents a foreground pixel, while a `-' represents a background pixel. Note that the precise output for each style will vary from device to device. The only style that is guaranteed to be the same for every device is "solid".
Style Name Pattern ----- ------- ------- 0 solid 1111111111111111 1 dash 11111111-------- 2 dot 1-1-1-1-1-1-1-1- 3 dash dot 1111111111111-1- 4 dash dot dot 11111111111-1-1- 5 long dash 11111111111----- 6 center dash 111111111111-11- 7 center dash dash 111111111-11-11-
To improve performance of graphics output, most graphics devices provide some form of buffering. By default, Scheme's graphics procedures flush this buffer after every drawing operation. The procedures in this section allow the user to control the flushing of the output buffer.
Note: graphics-disable-buffering flushes the output buffer if
necessary.
Scheme provides a rudimentary mechanism for restricting graphics output to a given rectangular subsection of a graphics device. By default, graphics output that is drawn anywhere within the device's virtual coordinate limits will appear on the device. When a clip rectangle is specified, however, output that would have appeared outside the clip rectangle is not drawn.
Note that changing the virtual coordinate limits for a device will usually reset the clip rectangle for that device, as will any operation that affects the size of the device (such as a window resizing operation). However, programs should not depend on this.
In addition to the standard operations, a graphics device may support
custom operations. For example, most devices have custom
operations to control color. graphics-operation is used to
invoke custom operations.
graphics- prefix from the corresponding procedure.
For example, the following are equivalent:
(graphics-draw-point device x y) (graphics-operation device 'draw-point x y)
For information on the custom operations for a particular device, see the documentation for its type.
Some graphics device types support images, which are rectangular pieces of picture that may be drawn into a graphics device. Images are often called something else in the host graphics system, such as bitmaps or pixmaps. The operations supported vary between devices, so look under the different device types to see what operations are available. All devices that support images support the following operations.
create-image graphics operation,
specifying the width and height of the image in device
coordinates (pixels).
(graphics-operation device 'create-image 200 100)
The initial contents of an image are unspecified.
create-image is a graphics operation rather than a procedure
because the kind of image returned depends on the kind of graphics
device used and the options specified in its creation. The image may be
used freely with other graphics devices created with the same
attributes, but the effects of using an image with a graphics device
with different attributes (for example, different colors) is undefined.
Under X, the image is display dependent.
#t if object is an image, otherwise returns
#f.
create-image to fail because it is
unable to allocate enough memory.
(* (image/height
image) (image/width image)) bytes in bytes.
MIT Scheme supports graphics on Microsoft Windows 3.1, Windows 95, and Windows NT. In addition to the usual operations, there are operations to control the size, position and colors of a graphics window. Win32 devices support images, which are implemented as device independent bitmaps (DIBs).
The Win32 graphics device type is implemented as a top level window.
graphics-enable-buffering is implemented and gives a 2x to 4x
speedup on many graphics operations. As a convenience, when buffering
is enabled clicking on the graphics window's title bar effects a
graphics-flush operation. The user has the benefit of the
increased performance and the ability to view the progress in drawing at
the click of a mouse button.
Win32 graphics devices are created by specifying the symbol win32
as the graphics-device-type argument to
make-graphics-device. The Win32 graphics device type is
implemented as a top-level window and supports color drawing in addition
to the standard Scheme graphics operations.
Graphics devices are opened as follows:
(make-graphics-device 'win32 #!optional width height palette)
where width and height specify the size, in pixels, of the drawing area in the graphics window (i.e. excluding the frame). Palette determines the colors available for drawing in the window.
When a color is specified for drawing, the nearest color available in the palette is used. Permitted values for palette are
'grayscale
'grayscale-128
'standard
#f or 'system
If palette is not specified then the standard palette is
used.
Custom operations are invoked using the procedure
graphics-operation. For example,
(graphics-operation device 'set-foreground-color "blue")
set-background-color and
set-foreground-color change the colors to be used when drawing,
but have no effect on anything drawn prior to their invocation. Because
changing the background color affects the entire window, we recommend
calling graphics-clear on the window's device afterwards.
The foreground color affects the drawing of text, points, lines, ellipses and filled polygons.
Colors are specified in one of three ways:
"red", "blue", "black".
More names can be registered with the define-color operation.
#(0 0 0) is black, (0 0
128) is dark blue and #(255 255 255) is white.
If the color is not available in the graphics device then the nearest available color is used instead.
Color names defined by this interface may also be used when setting the colors of the Scheme console window, or the colors of Edwin editor windows.
define-color. This returns
the color in its most efficient form for operations
set-foreground-color or set-background-color.
(graphics-operation device 'fill-polygon #(0 0 0 1 1 0))
draws a solid triangular region between the points (0, 0), (0, 1) and (1, 0).
".BMP" extension is added. If a clip rectangle is in
effect when this procedure is called, it is necessary to redefine the
clip rectangle afterwards.
".BMP"
extension is added. The saved bitmap may be incorporated into documents
or printed.
"Scheme Graphics" at creation.
MIT Scheme supports graphics under the OS/2 Presentation Manager in OS/2 version 2.1 and later. The OS/2 graphics device type is implemented as a top level window. In addition to the usual operations, there are operations to control the size, position, and colors of a graphics window. OS/2 graphics devices support images, which are implemented as memory presentation spaces.
The custom graphics operations defined in this section are invoked using
the procedure graphics-operation. For example,
(graphics-operation device 'set-foreground-color "blue")
OS/2 graphics devices are created by specifying the symbol os/2
as the graphics-device-type argument to
make-graphics-device. The OS/2 graphics device type is
implemented as a top-level window and supports color drawing in addition
to the standard Scheme graphics operations.
Graphics devices are opened as follows:
(make-graphics-device 'os/2 #!optional width height)
where width and height specify the size, in pixels, of the drawing area in the graphics window (i.e. excluding the frame).
These operations control the colors used when drawing on an OS/2 graphics device.
#t if the display supports color.
set-background-color and
set-foreground-color change the colors to be used when drawing,
but have no effect on anything drawn prior to their invocation. Because
changing the background color affects the entire window, we recommend
calling graphics-clear on the window's device afterwards.
The foreground color affects the drawing of text, points, and lines. Colors are specified in one of these ways:
0 and #xffffff inclusive
"red", "blue", "black". More names
can be registered with the define-color operation.
0 and #xff
inclusive which specify the intensity of the red, green and blue
components of the color. Thus (0 0 0) is black, (0 0 128)
is dark blue and (255 255 255) is white.
If the color is not available in the graphics device then the nearest available color is used instead.
Color names defined by this interface may also be used when setting the colors of the Scheme console window, or the colors of Edwin editor windows.
define-color. This
returns the color in its most efficient form for operations
set-foreground-color or set-background-color.
These operations control the window that contains the OS/2 graphics device. They provide facilities to change the window's size and position; to raise and lower the window relative to other windows on the desktop; to hide or minimize the window, and to restore it from the hidden or minimized state; to activate or deactivate the window (that is, control the keyboard focus); and to control the text that appears in the window's title bar.
The frame size is useful in conjunction with the window position and the desktop size to determine relative placement of the window or to guarantee that the entire window is visible on the desktop.
These operations allow you to read some of the events that are generated by the Presentation Manager and put in the message queue of a graphics-device window.
Note that this operation only works when button events are selected (which is the default).
read-user-event
operation. The mask is specified by setting the bits corresponding to
the event types that you are interested in, as follows:
Number Mask Description ------ ----- ----------- 0 #x001 Button press/release 1 #x002 Close (close the window) [WM_CLOSE] 2 #x004 Focus change [WM_SETFOCUS] 3 #x008 Key press/release [WM_CHAR] 4 #x010 Paint [WM_PAINT] 5 #x020 Size change [WM_SIZE] 6 #x040 Visibility change [WM_SHOW] 7 #x080 Command [WM_COMMAND] 8 #x100 Help [WM_HELP] 9 #x200 Mouse-move [WM_MOUSEMOVE]
Note that this operation does not affect any events that are already in the user-event queue. Changing the mask only affects what events will be added to the queue in the future.
An event is a vector whose first element is the event-type number, whose second element is the graphics device that the event refers to, and whose remaining elements provide information about the event. Here is a table of the possible event types and their vector layout:
#(0 device number type x y flags)
0 is usually the left mouse button, 1 is usually
the right button, etc. Type specifies what occurred: 0
means the button was pressed, 1 means the button was released,
2 means the button was clicked, and 3 means the button was
double clicked. X and y are the position of the mouse
pointer at the time of the event, in units of pels (pixels) measured
from the lower left corner of the client area of the associated window.
Finally, flags specifies what shift keys were pressed at the time
of the button event; it is a mask word created by combining zero or more
of the following flags: #x08 means the shift key was pressed,
#x10 means the control key was pressed, and #x20 means the
alt key was pressed.
#(1 device)
#(2 device gained?)
#t, the keyboard focus is
being gained, and if gained? is #f, it is being lost.
#(3 device code flags repeat)
#(4 device xl xh yl yh)
#(5 device width height)
#(6 device shown?)
#f, the window is hidden,
and if it is #t, the window is shown.
#(7 device source mouse?)
#(8 device source mouse?)
7 indicates a command from a `WM_COMMAND' message, while
8 is a command from a `WM_HELP' message.
#(9 device x y hit-test flags)
These operations allow you to: change the font used for drawing text in a graphics-device window; take a snapshot of a graphics-device window and return it as an image object; and draw multiple lines efficiently.
"10.Courier". You may specify any fixed-pitch font
family, in any point size that is supported for that font family. This
includes both image fonts and outline fonts.
graphics-draw-line but much faster. The arguments xv
and yv are vectors of coordinates; these vectors must be the same
length, and the length must be a multiple of two. The contents of the
vectors are alternating start/end pairs. For example, the following are
equivalent:
(graphics-draw-line device xs ys xe ye)
(graphics-operation device 'draw-lines
(vector xs xe)
(vector ys ye))
MIT Scheme supports graphics in the X window system (version 11).
Arbitrary numbers of displays may be opened, and arbitrary numbers of
graphics windows may be created for each display. A variety of
operations is available to manipulate various aspects of the windows, to
control their size, position, colors, and mapping. The X graphics
device type supports images, which are implemented as Xlib XImage
objects. X display, window, and image objects are automatically closed
if they are reclaimed by the garbage collector.
A graphics device for X windows is created by passing the symbol
x as the graphics device type name to
make-graphics-device:
(make-graphics-device 'x #!optional display geometry suppress-map?)
where display is either a display object, #f, or a string;
geometry is either #f or a string; and suppress-map?
is a boolean or a vector (see below). A new window is created on the
appropriate display, and a graphics device representing that window is
returned.
Display specifies which X display the window is to be opened on;
if it is #f or a string, it is passed as an argument to
x-open-display, and the value returned by that procedure is used
in place of the original argument. Geometry is an X geometry
string, or #f which means to use the default geometry (which is
specified as a resource).
Suppress-map?, if given, may take two forms. First, it may be a
boolean: if #f (the default), the window is automatically mapped
after it is created; otherwise, #t means to suppress this
automatic mapping. The second form is a vector of three elements. The
first element is a boolean with the same meaning as the boolean form of
suppress-map?. The second element is a string, which specifies an
alternative resource name to be used for looking up the window's
resources. The third element is also a string, which specifies a class
name for looking up the window's resources. The default value for
suppress-map? is #f.
The default resource and class names are "schemeGraphics" and
"SchemeGraphics" respectively.
The window is initialized using the resource and class names specified by suppress-map?, and is sensitive to the following resource properties:
Property Class Default -------- ----- ------- geometry Geometry 512x384+0+0 font Font fixed borderWidth BorderWidth 2 internalBorder BorderWidth [border width] background Background white foreground Foreground black borderColor BorderColor [foreground color] cursorColor Foreground [foreground color] pointerColor Foreground [foreground color]
The window is created with a backing_store attribute of
Always. The window's name and icon name are initialized to
"scheme-graphics".
#f
is returned. Display-name is normally a string, which is an X
display name in the usual form; however, #f is also allowed,
meaning to use the value of the unix environment variable
DISPLAY.
x-close-display on all open displays.
#f, while width and height must be either exact
non-negative integers or #f. Usually either x and y
are both specified or both #f; similarly for width and
height. If only one of the elements of such a pair is specified,
it is ignored.
Examples:
(x-geometry-string #f #f 100 200) => "100x200" (x-geometry-string 2 -3 100 200) => "100x200+2-3" (x-geometry-string 2 -3 #f #f) => "+2-3"
Note that the x and y arguments cannot distinguish between
+0 and -0, even though these have different meanings in X.
If either of those arguments is 0, it means +0 in X
terminology. If you need to distinguish these two cases you must create
your own geometry string using Scheme's string and number primitives.
Custom operations are invoked using the procedure
graphics-operation. For example,
(graphics-operation device 'set-foreground-color "blue")
set-border-color and set-mouse-color
immediately change the border and mouse-cursor colors.
set-background-color and set-foreground-color change the
colors to be used when drawing, but have no effect on anything drawn
prior to their invocation. Because changing the background color
affects the entire window, we recommend calling graphics-clear on
the window's device afterwards. Color names include both mnemonic
names, like "red", and intensity names specified in the
"#rrggbb" notation.
graphics-clear on the window's device after
doing so.
XMapWindow and
XWithdrawWindow.
XResizeWindow.
This operation resets the virtual coordinate system and the clip rectangle.
XMoveWindow. Note that the coordinates x and
y do not take the external border into account, and therefore will
not position the window as you might like. The only reliable way to
position a window is to ask a window manager to do it for you.
XGetDefault. Resource and property must be strings.
The operation returns the character string corresponding to the
association of resource and property; if no such association
exists, #f is returned.
#f is returned.
font-structure. A
more complete description of these components appears in documentation
of the XLoadQueryFont Xlib call. start-index is the index
of the first character available in the font. The min-bounds and
max-bounds components are structures of type
x-character-bounds, and the character-bounds component is
a vector of the same type.
x-character-bounds. A more complete description of them appears
in documentation of the XLoadQueryFont Xlib call.
On Hewlett-Packard computers under the HP-UX operating system, Scheme supports graphics through the Starbase graphics library. Note that the default distribution of Scheme for HP computers does not include support for Starbase -- you must rebuild the microcode to get this support.
(make-graphics-device 'starbase device-name driver-name)
where device-name and driver-name are strings that are used
as the device and driver arguments to the Starbase gopen call.
The device is opened with kind OUTDEV and mode 0. The
device is initialized to have a mapping mode of DISTORT, and a
line color index of 1.
#f, this is reversed: the
background is printed as black and the foreground is not printed.
The text drawn by a Starbase device is controlled by the following characteristics:
1.
.1.
0, 90, 180, and
270. 0 draws left-to-right with upright characters;
90 draws top-to-bottom with characters on their right side;
180 draws right-to-left with upside-down characters; 270
draws bottom-to-top with characters on their left side. The default
rotation is 0.
0.
The Win32 implementation is still in a state of development. It is expected that changes will be necessary when MIT Scheme is ported to Windows NT on the DEC Alpha architecture. In particular, the current system is not arranged in a way that adequately distinguishes between issues that are a consequence of the NT operating system and those which are a consequence of the Intel x86 architecture.
Thus this documentation is not definitive, it merely outlines how the current system works. Parts of the system will change and any project implemented using the win32 system must plan for a re-implementation stage.
The Win32 implementation has several components:
Note that all the names in the Win32 support are part of the
win32 package. The names are bound in the (win32)
environment, and do not appear as bindings in the user or root
environments.
An effect of this is that it is far easier to develop Win32 software in
the (win32) package environment or a child environment.
The Win32 foreign function interface (FFI) is a primitive and fairly simple system for calling procedures written in C in a dynamically linked library (DLL). Both user's procedures from a custom DLL and system procedures (e.g. MessageBox) are called using the same mechanism.
Warning: The FFI as it stands has several flaws which make it difficult to use reliably. It is expected that both the interface to and the mechanisms used by the FFI will be changed in the future. We provide it, and this documentation, only to give people an early start in accessing some of the features of Win32 from Scheme. Should you use it in an experiment we welcome any feedback.
The FFI is designed for calling C procedures that use C data types rather than Scheme data objects. Thus it is not possible to write and call a C procedure that returns, for example, a Scheme list. The object returned will always be an integer (which may represent the address of a C data structure).
Warning: It is extremely dangerous to try to pass Scheme callback procedures to C procedures. It is only possible by passing integer `handles' rather than the actual procedures, and even so, if a garbage collection occurs during the execution of the callback procedure objects in Scheme's heap will have moved. Thus in a foreign procedure that has a callback and a string, after calling the callback the string value may no longer be valid. Playing this game requires a profound knowledge of the implementation.
The interface to the FFI has two main components: a language for declaring the types of values passed to and returned from the foreign procedures and a form for declaring foreign procedures.
Foreign types are designed to represent a correspondence between a Scheme data type that is used to represent an object within the Scheme world and a C data type that represents the data object in the C world. Thus we cannot manipulate true C objects in Scheme, nor can we manipulate Scheme objects in C.
Each foreign type has four aspects that together ensure that the correspondence between the Scheme and C objects is maintained. These aspects are all encoded as procedures that either check for validity or convert between representations. Thus a foreign type is not a declarative type so much as a procedural description of how to pass the type. The underlying foreign procedure call mechanism can pass integers and vector-like Scheme objects, and returns integer values. All other objects must be translated into integers or some other basic type, and must be recovered from integers.
The aspects are:
#t if the argument is of an acceptable
Scheme type, otherwise returns #f.
The check procedure is used for type-checking.
#f.
A #f means use the default value, which in the second form means
use the definition provided for model.
The defaults are
(lambda (x) #t), i.e. unchecked.
(lambda (x) x), i.e. no translation performed.
(lambda (x) x), i.e. no translation performed.
(lambda (x y) unspecific), i.e. no update performed
The unchecked windows type (see below) is defined as:
(define-windows-type unchecked #f #f #f #f)
Windows types are not first class values, so they cannot be
stored in variables or defined using define:
(define my-type unchecked) error--> Unbound variable (define-similar-windows-type my-type unchecked) ;; the correct way
Scheme characters must be converted to integers. This is accomplished as follows:
(define-windows-type char char? ; check char->integer ; convert integer->char ; convert return value #f ; cannot be passed by reference )
unchecked values are returned as integers.
0 and 1.
Windows type bool have been defined as:
(define-windows-type bool boolean? (lambda (x) (if x 1 0)) (lambda (x) (if (eq? x 0) #f #t)) #f)
char,
which are indistinguishable from small integers.
char* to the first
character in the string.
#f. The string is passed as a pointer to characters.
The string is correctly null-terminated. #f is passed as the null
pointer. This is an example where there is a more complex mapping
between C objects and Scheme objects. C's char* type is
represented as one of two Scheme types depending on its value. This
allows us us to distinguish between the C string (pointer) that points
to the empty sequence of characters and the null pointer (which doesnt
point anywhere).
hmenu?) and
sensible interlocking with the garbage collector to free the programmer
of the current tedious allocation and deallocation of handles.
Foreign procedures are declared as callable entry-points in a module, usually a dynamically linked library (DLL).
windows-procedure. Name is a string which is the name of a
DLL file. Internally, find-module uses the LoadLibrary
Win32 API, so name should conform to the specifications for this
call. Name should be either a full path name of a DLL, or the
name of a DLL that resides in the same directory as the Scheme binary
`SCHEME.EXE' or in the system directory.
The module returned is a description for the DLL, and the DLL need not necessarily be linked at or immediately after this call. DLL modules are linked on need and unlinked before Scheme exits and when there are no remaining references to entry points after a garbage-collection. This behavior ensures that the Scheme system can run when a DLL is absent, provided the DLL is not actually used (i.e. no attempt is made to call a procedure in the DLL).
LineTo.
MessageBox and SetWindowText.
find-module.
These are the only parts of the form that are evaluated at procedure
creation time.
Name is the name of the procedure and is for documentation
purposes only. This form does not define a procedure called
name. It is more like lambda. The name might be used for
debugging and pretty-printing.
A windows procedure has a fixed number of parameters (i.e. no `rest' parameters or `varargs'), each of which is named and associated with a windows type type. Both the name parameter and the windows type type must be symbols and are not evaluated. The procedure returns a value of the windows type return-type.
The following example creates a procedure that takes a window handle
(hwnd) and a string and returns a boolean (bool) result.
The procedure does this by calling the SetWindowText entry in the
module that is the value of the variable user32.dll. The
variable set-window-title is defined to have this procedure as
it's value.
(define set-window-title
(windows-procedure (set-window-text (window hwnd) (text string))
bool user32.dll "SetWindowText"))
(set-window-title my-win "Hi") => #t
;; Changes window's title/text
set-window-title => #[compiled-procedure ...]
set-window-text error--> Unbound variable
When there are no options the created procedure will (a) check its arguments against the types, (b) convert the arguments, (c) call the C procedure and (d) convert the returned value. No reversion is performed, even if one of the types has a reversion defined. (Reverted types are rare [I have never used one], so paying a cost for this unless it is used seems silly).
The following options are allowed:
with-reversions
expand
with-reversions.
If both options (i.e. with-reversions and Scheme code) are used,
with-reversions must appear first. There can be arbitrarily many
Scheme expression.
This section is a moving target.
The #define values from `wingdi.h' and `winuser.h' are
available as bindings in the (win32) package environment. The
#define symbols are all uppercase; these have been translated to
all lowercase Scheme identifiers, thus WM_LBUTTONUP is the scheme
variable wm_lbuttonup. As Scheme is case insensitive, the
upper-case version may be used and probably should to make the code look
more like conventional Windows code. The Scheme bindings have been
produced automagically. Most of the #define-symbols contain an
underscore so there are not many name clashes. There is one very
notable name clash, however: ERROR is #defined to 0, which
shadows the scheme procedure error in the root package
environment. To signal an error, use access to get error
from the system global environment:
(declare (usual-integrations)) ... ((access error system-global-environment) "Complain" ...)
The set of procedures is incomplete because procedures have been added on a by-need basis for the implementation of other parts of the system, e.g. Scheme Graphics. Look in the implementation for further details.
Win32 API procedure names have been uniformly converted into Scheme identifiers as follows:
Is finally have a
question-mark appended.
Example: applying these rules to IsWindow yields
is-window?, and GetDC is translated into get-dc.
The Device Independent Bitmap (DIB) utilities library `DIBUTILS.DLL' and the associated procedures in `dib.scm' in the Win32 system source is an example of how to use the foreign function interface to access and manipulate non-Scheme objects.
In the Scheme world a DIB is a structure containing information
about the bitmap (specifically the integer that represents the handle).
We also include #f in the dib windows type to mirror the
null handle error value.
(define dib-result
(lambda (handle)
(if (= handle 0)
#f
(make-dib handle))))
(define dib-arg
(lambda (dib)
(if dib
(cell-contents (dib-handle dib))
0)))
(define-windows-type dib
(lambda (thing) (or (dib? thing) (eq? thing #f)))
dib-arg
dib-result)
The following procedures have typed parameters, using the same
convention as windows-procedure.
OpenDIB entry of
`DIBUTILS.DLL'. If the return value is not #f then the file
filename was found, successfully opened, and the contents were
suitable for loading into memory as a device independent bitmap.
WriteDIB entry of
`DIBUTILS.DLL'. Returns #t if the file filename could
be opened and written to. After this operation the file contains the
bitmap data in a standard format that is understood by open-dib
and various system utilities like the bitmap editor. Any problems
resulting in failure are signalled by a #f return value.
BitmapFromDib entry of `DIBUTILS.DLL'. The returned
value is a device dependent bitmap. The colours from the DIB are
matched against colors in palette.
DibFromBitmap entry of `DIBUTILS.DLL'.
DibBlt entry of
`DIBUTILS.DLL'. Similar to the Win32 API BitBlt call, but
draws a DIB rather than a piece of another device context. Draws the
dib on device context hdc at position (x,y). A
rectangle of width w and height h is copied from position
(src-x,src-y) of dib.
Raster-op is supposed to allow the source and destination to be
combined but I don't think I got this right so stick to SRCCOPY.
DeleteDIB entry of `DIBUTILS.DLL'.
Note that the parameter is a handle, and not a dib.
This allows us to destroy a DIB and reclaim its memory by knowing only
the handle value, and not needing the dib record.
The importance of this is that if the dib record is GC-ed then a
GC hook can reclaim the storage knowing only the handle.
%delete-dib to reclaim the storage occupied
by a DIB.
After being deleted, the DIB should not be used.
This procedure allows the programmer to reclaim external heap storage
rather than risking it running out before the next garbage collection.
DibHeight expand entry of `DIBUTILS.DLL', which returns
the height of the bitmap in pixels.
DibWidth entry of `DIBUTILS.DLL', which returns
the width of the bitmap in pixels.
CopyBitmap of `DIBUTILS.DLL', which creates a new
bitmap with the same size and contents as the original.
CreateDIB entry of `DIBUTILS.DLL'.
Creates a DIB of width by height pixels and depth bits
of colour information.
The style parameter determines how the bitmap is stored.
I have only ever used BI_RGB.
If depth<=8 then the palette determines the DIB's colour table.
CropBitmap entry of `DIBUTILS.DLL'.
Returns a new bitmap containing the image from a region of the original.
DIBSetPixelsUnaligned entry of `DIBUTILS.DLL'. Stuffs
bytes from pixels into the bitmap. There are no alignment
constraints on pixels (the usual way of doing this is to use the
SetDIBits function which requires that every scan line of the
bitmap is 32-bit word aligned, even if the scan lines are not a multiple
of 4 bytes long). doing this
The `DIBUTILS.DLL' library is an ordinary DLL. See the standard Microsoft Windows documentation on how to create DLLs. Look at the code in the `WIN32/DIBUTILS' directory of the Scheme source.
Please note:
find-module Scheme function.
Look at `WIN32/DIB.SCM' to see how this is done.
__stdcall and
__cdecl calling conventions but not the __fastcall
calling convention.
MIT Scheme implements the whole tower of numerical types. It has unlimited-precision exact integers and exact rationals. Flonums are used to implement all inexact reals; on machines that support IEEE floating-point arithmetic these are double-precision floating-point numbers.
MIT Scheme implements all of the written notations for numbers.
In MIT Scheme the rational? procedure is the
same as real?, and the complex? procedure is the same as
number?.
MIT Scheme signals an error of type
condition-type:bad-range-argument in this case.
Some of the details in this section depend on the fact that the underlying operating system uses the ASCII character set. This may change when someone ports MIT Scheme to a non-ASCII operating system.
Note that the Control bucky bit is different from
the ASCII control key. This means that #\SOH (ASCII
ctrl-A) is different from #\C-A. In fact, the Control bucky bit
is completely orthogonal to the ASCII control key, making possible
such characters as #\C-SOH.
Because character sets are implemented as strings,
string? returns #t for character set objects. However,
string operations aren't meaningful with character sets.
The above definitions imply that all lists have finite length and are terminated by the empty list.
Note that path is restricted to a machine-dependent range, usually the size of a machine word. On many machines, this means that the maximum length of path will be 30 operations (32 bits, less the sign bit and the "end-of-sequence" bit).
Although
they are often used as predicates, memq, memv, and
member do not have question marks in their names because they
return useful values rather than just #t or #f.
In older dialects of Lisp, uninterned symbols were fairly important. This was true because symbols were complicated data structures: in addition to having value cells (and sometimes, function cells), these structures contained property lists. Because of this, uninterned symbols were often used merely for their property lists -- sometimes an uninterned symbol used this way was referred to as a disembodied property list. In MIT Scheme, symbols do not have property lists, or any other components besides their names. There is a different data structure similar to disembodied property lists: one-dimensional tables (see section 1D Tables). For these reasons, uninterned symbols are not very useful in MIT Scheme. In fact, their primary purpose is to simplify the generation of unique variable names in programs that generate Scheme code.
MIT Scheme
reserves a specific set of interned symbols for its own use. If you use
these reserved symbols it is possible that you could break specific
pieces of software that depend on them. The reserved symbols all have
names beginning with the characters `#[' and ending with the
character `]'; thus none of these symbols can be read by the
procedure read and hence are not likely to be used by accident.
For example, (intern "#[unnamed-procedure]") produces a reserved
symbol.
In MIT Scheme, the returned list is always newly allocated.
This introduction is taken from Common Lisp, The Language, second edition, p. 431.
Although they are often used as predicates,
assq, assv, and assoc do not have question marks in
their names because they return useful values rather than just #t
or #f.
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 call-with-current-continuation and
call-with-input-file or call-with-output-file.
The value returned by a call to peek-char
is the same as the value that would have been returned by a call to
read-char on the same port. The only difference is that the very
next call to read-char or peek-char on that
input-port will return the value returned by the preceding call to
peek-char. In particular, a call to peek-char on an
interactive port will hang waiting for input whenever a call to
read-char would have hung.
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 make sure that characters whose existence has been asserted by
char-ready? cannot be rubbed out. If char-ready? were to
return #f at end of file, a port at end of file would be
indistinguishable from an interactive port that has no ready
characters.
write is
intended for producing machine-readable output and display is for
producing human-readable output.
This description of format is adapted from
Common Lisp, The Language, second edition, section 22.3.3.
Except that if the
argument name is a string, its external representation is
generated by write-string.
This introduction is adapted from Common Lisp, The Language, second edition, section 23.1.
This description is adapted from Common Lisp, The Language, second edition, section 23.1.1.
This document was generated on 29 October 1997 using the texi2html translator version 1.51.