summaryrefslogtreecommitdiffstats
path: root/slib.info-4
diff options
context:
space:
mode:
Diffstat (limited to 'slib.info-4')
-rw-r--r--slib.info-41248
1 files changed, 1248 insertions, 0 deletions
diff --git a/slib.info-4 b/slib.info-4
new file mode 100644
index 0000000..3d3da19
--- /dev/null
+++ b/slib.info-4
@@ -0,0 +1,1248 @@
+This is Info file slib.info, produced by Makeinfo-1.64 from the input
+file slib.texi.
+
+ This file documents SLIB, the portable Scheme library.
+
+ Copyright (C) 1993 Todd R. Eigenschink Copyright (C) 1993, 1994, 1995
+Aubrey Jaffer
+
+ Permission is granted to make and distribute verbatim copies of this
+manual provided the copyright notice and this permission notice are
+preserved on all copies.
+
+ Permission is granted to copy and distribute modified versions of this
+manual under the conditions for verbatim copying, provided that the
+entire resulting derived work is distributed under the terms of a
+permission notice identical to this one.
+
+ Permission is granted to copy and distribute translations of this
+manual into another language, under the above conditions for modified
+versions, except that this permission notice may be stated in a
+translation approved by the author.
+
+
+File: slib.info, Node: Syntactic Closures, Next: Syntax-Case Macros, Prev: Macros That Work, Up: Macros
+
+Syntactic Closures
+==================
+
+ `(require 'syntactic-closures)'
+
+ - Function: macro:expand EXPRESSION
+ - Function: synclo:expand EXPRESSION
+ Returns scheme code with the macros and derived expression types of
+ EXPRESSION expanded to primitive expression types.
+
+ - Function: macro:eval EXPRESSION
+ - Function: synclo:eval EXPRESSION
+ `macro:eval' returns the value of EXPRESSION in the current top
+ level environment. EXPRESSION can contain macro definitions.
+ Side effects of EXPRESSION will affect the top level environment.
+
+ - Procedure: macro:load FILENAME
+ - Procedure: synclo:load FILENAME
+ FILENAME should be a string. If filename names an existing file,
+ the `macro:load' procedure reads Scheme source code expressions and
+ definitions from the file and evaluates them sequentially. These
+ source code expressions and definitions may contain macro
+ definitions. The `macro:load' procedure does not affect the
+ values returned by `current-input-port' and `current-output-port'.
+
+Syntactic Closure Macro Facility
+--------------------------------
+
+ A Syntactic Closures Macro Facility
+
+ by Chris Hanson
+
+ 9 November 1991
+
+ This document describes "syntactic closures", a low-level macro
+facility for the Scheme programming language. The facility is an
+alternative to the low-level macro facility described in the `Revised^4
+Report on Scheme.' This document is an addendum to that report.
+
+ The syntactic closures facility extends the BNF rule for TRANSFORMER
+SPEC to allow a new keyword that introduces a low-level macro
+transformer:
+ TRANSFORMER SPEC := (transformer EXPRESSION)
+
+ Additionally, the following procedures are added:
+ make-syntactic-closure
+ capture-syntactic-environment
+ identifier?
+ identifier=?
+
+ The description of the facility is divided into three parts. The
+first part defines basic terminology. The second part describes how
+macro transformers are defined. The third part describes the use of
+"identifiers", which extend the syntactic closure mechanism to be
+compatible with `syntax-rules'.
+
+Terminology
+...........
+
+ This section defines the concepts and data types used by the syntactic
+closures facility.
+
+ "Forms" are the syntactic entities out of which programs are
+ recursively constructed. A form is any expression, any
+ definition, any syntactic keyword, or any syntactic closure. The
+ variable name that appears in a `set!' special form is also a
+ form. Examples of forms:
+ 17
+ #t
+ car
+ (+ x 4)
+ (lambda (x) x)
+ (define pi 3.14159)
+ if
+ define
+
+ An "alias" is an alternate name for a given symbol. It can appear
+ anywhere in a form that the symbol could be used, and when quoted
+ it is replaced by the symbol; however, it does not satisfy the
+ predicate `symbol?'. Macro transformers rarely distinguish
+ symbols from aliases, referring to both as identifiers.
+
+ A "syntactic" environment maps identifiers to their meanings.
+ More precisely, it determines whether an identifier is a syntactic
+ keyword or a variable. If it is a keyword, the meaning is an
+ interpretation for the form in which that keyword appears. If it
+ is a variable, the meaning identifies which binding of that
+ variable is referenced. In short, syntactic environments contain
+ all of the contextual information necessary for interpreting the
+ meaning of a particular form.
+
+ A "syntactic closure" consists of a form, a syntactic environment,
+ and a list of identifiers. All identifiers in the form take their
+ meaning from the syntactic environment, except those in the given
+ list. The identifiers in the list are to have their meanings
+ determined later. A syntactic closure may be used in any context
+ in which its form could have been used. Since a syntactic closure
+ is also a form, it may not be used in contexts where a form would
+ be illegal. For example, a form may not appear as a clause in the
+ cond special form. A syntactic closure appearing in a quoted
+ structure is replaced by its form.
+
+Transformer Definition
+......................
+
+ This section describes the `transformer' special form and the
+procedures `make-syntactic-closure' and `capture-syntactic-environment'.
+
+ - Syntax: transformer EXPRESSION
+ Syntax: It is an error if this syntax occurs except as a
+ TRANSFORMER SPEC.
+
+ Semantics: The EXPRESSION is evaluated in the standard transformer
+ environment to yield a macro transformer as described below. This
+ macro transformer is bound to a macro keyword by the special form
+ in which the `transformer' expression appears (for example,
+ `let-syntax').
+
+ A "macro transformer" is a procedure that takes two arguments, a
+ form and a syntactic environment, and returns a new form. The
+ first argument, the "input form", is the form in which the macro
+ keyword occurred. The second argument, the "usage environment",
+ is the syntactic environment in which the input form occurred.
+ The result of the transformer, the "output form", is automatically
+ closed in the "transformer environment", which is the syntactic
+ environment in which the `transformer' expression occurred.
+
+ For example, here is a definition of a push macro using
+ `syntax-rules':
+ (define-syntax push
+ (syntax-rules ()
+ ((push item list)
+ (set! list (cons item list)))))
+
+ Here is an equivalent definition using `transformer':
+ (define-syntax push
+ (transformer
+ (lambda (exp env)
+ (let ((item
+ (make-syntactic-closure env '() (cadr exp)))
+ (list
+ (make-syntactic-closure env '() (caddr exp))))
+ `(set! ,list (cons ,item ,list))))))
+
+ In this example, the identifiers `set!' and `cons' are closed in
+ the transformer environment, and thus will not be affected by the
+ meanings of those identifiers in the usage environment `env'.
+
+ Some macros may be non-hygienic by design. For example, the
+ following defines a loop macro that implicitly binds `exit' to an
+ escape procedure. The binding of `exit' is intended to capture
+ free references to `exit' in the body of the loop, so `exit' must
+ be left free when the body is closed:
+ (define-syntax loop
+ (transformer
+ (lambda (exp env)
+ (let ((body (cdr exp)))
+ `(call-with-current-continuation
+ (lambda (exit)
+ (let f ()
+ ,@(map (lambda (exp)
+ (make-syntactic-closure env '(exit)
+ exp))
+ body)
+ (f))))))))
+
+ To assign meanings to the identifiers in a form, use
+ `make-syntactic-closure' to close the form in a syntactic
+ environment.
+
+ - Function: make-syntactic-closure ENVIRONMENT FREE-NAMES FORM
+ ENVIRONMENT must be a syntactic environment, FREE-NAMES must be a
+ list of identifiers, and FORM must be a form.
+ `make-syntactic-closure' constructs and returns a syntactic closure
+ of FORM in ENVIRONMENT, which can be used anywhere that FORM could
+ have been used. All the identifiers used in FORM, except those
+ explicitly excepted by FREE-NAMES, obtain their meanings from
+ ENVIRONMENT.
+
+ Here is an example where FREE-NAMES is something other than the
+ empty list. It is instructive to compare the use of FREE-NAMES in
+ this example with its use in the `loop' example above: the examples
+ are similar except for the source of the identifier being left
+ free.
+ (define-syntax let1
+ (transformer
+ (lambda (exp env)
+ (let ((id (cadr exp))
+ (init (caddr exp))
+ (exp (cadddr exp)))
+ `((lambda (,id)
+ ,(make-syntactic-closure env (list id) exp))
+ ,(make-syntactic-closure env '() init))))))
+
+ `let1' is a simplified version of `let' that only binds a single
+ identifier, and whose body consists of a single expression. When
+ the body expression is syntactically closed in its original
+ syntactic environment, the identifier that is to be bound by
+ `let1' must be left free, so that it can be properly captured by
+ the `lambda' in the output form.
+
+ To obtain a syntactic environment other than the usage
+ environment, use `capture-syntactic-environment'.
+
+ - Function: capture-syntactic-environment PROCEDURE
+ `capture-syntactic-environment' returns a form that will, when
+ transformed, call PROCEDURE on the current syntactic environment.
+ PROCEDURE should compute and return a new form to be transformed,
+ in that same syntactic environment, in place of the form.
+
+ An example will make this clear. Suppose we wanted to define a
+ simple `loop-until' keyword equivalent to
+ (define-syntax loop-until
+ (syntax-rules ()
+ ((loop-until id init test return step)
+ (letrec ((loop
+ (lambda (id)
+ (if test return (loop step)))))
+ (loop init)))))
+
+ The following attempt at defining `loop-until' has a subtle bug:
+ (define-syntax loop-until
+ (transformer
+ (lambda (exp env)
+ (let ((id (cadr exp))
+ (init (caddr exp))
+ (test (cadddr exp))
+ (return (cadddr (cdr exp)))
+ (step (cadddr (cddr exp)))
+ (close
+ (lambda (exp free)
+ (make-syntactic-closure env free exp))))
+ `(letrec ((loop
+ (lambda (,id)
+ (if ,(close test (list id))
+ ,(close return (list id))
+ (loop ,(close step (list id)))))))
+ (loop ,(close init '())))))))
+
+ This definition appears to take all of the proper precautions to
+ prevent unintended captures. It carefully closes the
+ subexpressions in their original syntactic environment and it
+ leaves the `id' identifier free in the `test', `return', and
+ `step' expressions, so that it will be captured by the binding
+ introduced by the `lambda' expression. Unfortunately it uses the
+ identifiers `if' and `loop' within that `lambda' expression, so if
+ the user of `loop-until' just happens to use, say, `if' for the
+ identifier, it will be inadvertently captured.
+
+ The syntactic environment that `if' and `loop' want to be exposed
+ to is the one just outside the `lambda' expression: before the
+ user's identifier is added to the syntactic environment, but after
+ the identifier loop has been added.
+ `capture-syntactic-environment' captures exactly that environment
+ as follows:
+ (define-syntax loop-until
+ (transformer
+ (lambda (exp env)
+ (let ((id (cadr exp))
+ (init (caddr exp))
+ (test (cadddr exp))
+ (return (cadddr (cdr exp)))
+ (step (cadddr (cddr exp)))
+ (close
+ (lambda (exp free)
+ (make-syntactic-closure env free exp))))
+ `(letrec ((loop
+ ,(capture-syntactic-environment
+ (lambda (env)
+ `(lambda (,id)
+ (,(make-syntactic-closure env '() `if)
+ ,(close test (list id))
+ ,(close return (list id))
+ (,(make-syntactic-closure env '()
+ `loop)
+ ,(close step (list id)))))))))
+ (loop ,(close init '())))))))
+
+ In this case, having captured the desired syntactic environment,
+ it is convenient to construct syntactic closures of the
+ identifiers `if' and the `loop' and use them in the body of the
+ `lambda'.
+
+ A common use of `capture-syntactic-environment' is to get the
+ transformer environment of a macro transformer:
+ (transformer
+ (lambda (exp env)
+ (capture-syntactic-environment
+ (lambda (transformer-env)
+ ...))))
+
+Identifiers
+...........
+
+ This section describes the procedures that create and manipulate
+identifiers. Previous syntactic closure proposals did not have an
+identifier data type - they just used symbols. The identifier data
+type extends the syntactic closures facility to be compatible with the
+high-level `syntax-rules' facility.
+
+ As discussed earlier, an identifier is either a symbol or an "alias".
+An alias is implemented as a syntactic closure whose "form" is an
+identifier:
+ (make-syntactic-closure env '() 'a)
+ => an "alias"
+
+ Aliases are implemented as syntactic closures because they behave just
+like syntactic closures most of the time. The difference is that an
+alias may be bound to a new value (for example by `lambda' or
+`let-syntax'); other syntactic closures may not be used this way. If
+an alias is bound, then within the scope of that binding it is looked
+up in the syntactic environment just like any other identifier.
+
+ Aliases are used in the implementation of the high-level facility
+`syntax-rules'. A macro transformer created by `syntax-rules' uses a
+template to generate its output form, substituting subforms of the
+input form into the template. In a syntactic closures implementation,
+all of the symbols in the template are replaced by aliases closed in
+the transformer environment, while the output form itself is closed in
+the usage environment. This guarantees that the macro transformation
+is hygienic, without requiring the transformer to know the syntactic
+roles of the substituted input subforms.
+
+ - Function: identifier? OBJECT
+ Returns `#t' if OBJECT is an identifier, otherwise returns `#f'.
+ Examples:
+ (identifier? 'a)
+ => #t
+ (identifier? (make-syntactic-closure env '() 'a))
+ => #t
+ (identifier? "a")
+ => #f
+ (identifier? #\a)
+ => #f
+ (identifier? 97)
+ => #f
+ (identifier? #f)
+ => #f
+ (identifier? '(a))
+ => #f
+ (identifier? '#(a))
+ => #f
+
+ The predicate `eq?' is used to determine if two identifers are
+ "the same". Thus `eq?' can be used to compare identifiers exactly
+ as it would be used to compare symbols. Often, though, it is
+ useful to know whether two identifiers "mean the same thing". For
+ example, the `cond' macro uses the symbol `else' to identify the
+ final clause in the conditional. A macro transformer for `cond'
+ cannot just look for the symbol `else', because the `cond' form
+ might be the output of another macro transformer that replaced the
+ symbol `else' with an alias. Instead the transformer must look
+ for an identifier that "means the same thing" in the usage
+ environment as the symbol `else' means in the transformer
+ environment.
+
+ - Function: identifier=? ENVIRONMENT1 IDENTIFIER1 ENVIRONMENT2
+ IDENTIFIER2
+ ENVIRONMENT1 and ENVIRONMENT2 must be syntactic environments, and
+ IDENTIFIER1 and IDENTIFIER2 must be identifiers. `identifier=?'
+ returns `#t' if the meaning of IDENTIFIER1 in ENVIRONMENT1 is the
+ same as that of IDENTIFIER2 in ENVIRONMENT2, otherwise it returns
+ `#f'. Examples:
+
+ (let-syntax
+ ((foo
+ (transformer
+ (lambda (form env)
+ (capture-syntactic-environment
+ (lambda (transformer-env)
+ (identifier=? transformer-env 'x env 'x)))))))
+ (list (foo)
+ (let ((x 3))
+ (foo))))
+ => (#t #f)
+
+ (let-syntax ((bar foo))
+ (let-syntax
+ ((foo
+ (transformer
+ (lambda (form env)
+ (capture-syntactic-environment
+ (lambda (transformer-env)
+ (identifier=? transformer-env 'foo
+ env (cadr form))))))))
+ (list (foo foo)
+ (foobar))))
+ => (#f #t)
+
+Acknowledgements
+................
+
+ The syntactic closures facility was invented by Alan Bawden and
+Jonathan Rees. The use of aliases to implement `syntax-rules' was
+invented by Alan Bawden (who prefers to call them "synthetic names").
+Much of this proposal is derived from an earlier proposal by Alan
+Bawden.
+
+
+File: slib.info, Node: Syntax-Case Macros, Next: Fluid-Let, Prev: Syntactic Closures, Up: Macros
+
+Syntax-Case Macros
+==================
+
+ `(require 'syntax-case)'
+
+ - Function: macro:expand EXPRESSION
+ - Function: syncase:expand EXPRESSION
+ Returns scheme code with the macros and derived expression types of
+ EXPRESSION expanded to primitive expression types.
+
+ - Function: macro:eval EXPRESSION
+ - Function: syncase:eval EXPRESSION
+ `macro:eval' returns the value of EXPRESSION in the current top
+ level environment. EXPRESSION can contain macro definitions.
+ Side effects of EXPRESSION will affect the top level environment.
+
+ - Procedure: macro:load FILENAME
+ - Procedure: syncase:load FILENAME
+ FILENAME should be a string. If filename names an existing file,
+ the `macro:load' procedure reads Scheme source code expressions and
+ definitions from the file and evaluates them sequentially. These
+ source code expressions and definitions may contain macro
+ definitions. The `macro:load' procedure does not affect the
+ values returned by `current-input-port' and `current-output-port'.
+
+ This is version 2.1 of `syntax-case', the low-level macro facility
+proposed and implemented by Robert Hieb and R. Kent Dybvig.
+
+ This version is further adapted by Harald Hanche-Olsen
+<hanche@imf.unit.no> to make it compatible with, and easily usable
+with, SLIB. Mainly, these adaptations consisted of:
+
+ * Removing white space from `expand.pp' to save space in the
+ distribution. This file is not meant for human readers anyway...
+
+ * Removed a couple of Chez scheme dependencies.
+
+ * Renamed global variables used to minimize the possibility of name
+ conflicts.
+
+ * Adding an SLIB-specific initialization file.
+
+ * Removing a couple extra files, most notably the documentation (but
+ see below).
+
+ If you wish, you can see exactly what changes were done by reading the
+shell script in the file `syncase.sh'.
+
+ The two PostScript files were omitted in order to not burden the SLIB
+distribution with them. If you do intend to use `syntax-case',
+however, you should get these files and print them out on a PostScript
+printer. They are available with the original `syntax-case'
+distribution by anonymous FTP in
+`cs.indiana.edu:/pub/scheme/syntax-case'.
+
+ In order to use syntax-case from an interactive top level, execute:
+ (require 'syntax-case)
+ (require 'repl)
+ (repl:top-level macro:eval)
+ See the section Repl (*Note Repl::) for more information.
+
+ To check operation of syntax-case get
+`cs.indiana.edu:/pub/scheme/syntax-case', and type
+ (require 'syntax-case)
+ (syncase:sanity-check)
+
+ Beware that `syntax-case' takes a long time to load - about 20s on a
+SPARCstation SLC (with SCM) and about 90s on a Macintosh SE/30 (with
+Gambit).
+
+Notes
+-----
+
+ All R4RS syntactic forms are defined, including `delay'. Along with
+`delay' are simple definitions for `make-promise' (into which `delay'
+expressions expand) and `force'.
+
+ `syntax-rules' and `with-syntax' (described in `TR356') are defined.
+
+ `syntax-case' is actually defined as a macro that expands into calls
+to the procedure `syntax-dispatch' and the core form `syntax-lambda';
+do not redefine these names.
+
+ Several other top-level bindings not documented in TR356 are created:
+ the "hooks" in `hooks.ss'
+
+ the `build-' procedures in `output.ss'
+
+ `expand-syntax' (the expander)
+
+ The syntax of define has been extended to allow `(define ID)', which
+assigns ID to some unspecified value.
+
+ We have attempted to maintain R4RS compatibility where possible. The
+incompatibilities should be confined to `hooks.ss'. Please let us know
+if there is some incompatibility that is not flagged as such.
+
+ Send bug reports, comments, suggestions, and questions to Kent Dybvig
+(dyb@iuvax.cs.indiana.edu).
+
+Note from maintainer
+--------------------
+
+ Included with the `syntax-case' files was `structure.scm' which
+defines a macro `define-structure'. There is no documentation for this
+macro and it is not used by any code in SLIB.
+
+
+File: slib.info, Node: Fluid-Let, Next: Yasos, Prev: Syntax-Case Macros, Up: Macros
+
+Fluid-Let
+=========
+
+ `(require 'fluid-let)'
+
+ - Syntax: fluid-let `(BINDINGS ...)' FORMS...
+
+ (fluid-let ((VARIABLE INIT) ...)
+ EXPRESSION EXPRESSION ...)
+
+ The INITs are evaluated in the current environment (in some
+unspecified order), the current values of the VARIABLEs are saved, the
+results are assigned to the VARIABLEs, the EXPRESSIONs are evaluated
+sequentially in the current environment, the VARIABLEs are restored to
+their original values, and the value of the last EXPRESSION is returned.
+
+ 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 values of
+each INIT to the binding (determined by the rules of lexical scoping)
+of its corresponding VARIABLE.
+
+
+File: slib.info, Node: Yasos, Prev: Fluid-Let, Up: Macros
+
+Yasos
+=====
+
+ `(require 'oop)' or `(require 'yasos)'
+
+ `Yet Another Scheme Object System' is a simple object system for
+Scheme based on the paper by Norman Adams and Jonathan Rees: `Object
+Oriented Programming in Scheme', Proceedings of the 1988 ACM Conference
+on LISP and Functional Programming, July 1988 [ACM #552880].
+
+ Another reference is:
+
+ Ken Dickey. Scheming with Objects `AI Expert' Volume 7, Number 10
+(October 1992), pp. 24-33.
+
+* Menu:
+
+* Yasos terms:: Definitions and disclaimer.
+* Yasos interface:: The Yasos macros and procedures.
+* Setters:: Dylan-like setters in Yasos.
+* Yasos examples:: Usage of Yasos and setters.
+
+
+File: slib.info, Node: Yasos terms, Next: Yasos interface, Prev: Yasos, Up: Yasos
+
+Terms
+-----
+
+"Object"
+ Any Scheme data object.
+
+"Instance"
+ An instance of the OO system; an "object".
+
+"Operation"
+ A METHOD.
+
+*Notes:*
+ The object system supports multiple inheritance. An instance can
+ inherit from 0 or more ancestors. In the case of multiple
+ inherited operations with the same identity, the operation used is
+ that from the first ancestor which contains it (in the ancestor
+ `let'). An operation may be applied to any Scheme data
+ object--not just instances. As code which creates instances is
+ just code, there are no "classes" and no meta-ANYTHING. Method
+ dispatch is by a procedure call a la CLOS rather than by `send'
+ syntax a la Smalltalk.
+
+*Disclaimer:*
+ There are a number of optimizations which can be made. This
+ implementation is expository (although performance should be quite
+ reasonable). See the L&FP paper for some suggestions.
+
+
+File: slib.info, Node: Yasos interface, Next: Setters, Prev: Yasos terms, Up: Yasos
+
+Interface
+---------
+
+ - Syntax: define-operation `('OPNAME SELF ARG ...`)' DEFAULT-BODY
+ Defines a default behavior for data objects which don't handle the
+ operation OPNAME. The default default behavior (for an empty
+ DEFAULT-BODY) is to generate an error.
+
+ - Syntax: define-predicate OPNAME?
+ Defines a predicate OPNAME?, usually used for determining the
+ "type" of an object, such that `(OPNAME? OBJECT)' returns `#t' if
+ OBJECT has an operation OPNAME? and `#f' otherwise.
+
+ - Syntax: object `((NAME SELF ARG ...) BODY)' ...
+ Returns an object (an instance of the object system) with
+ operations. Invoking `(NAME OBJECT ARG ...' executes the BODY of
+ the OBJECT with SELF bound to OBJECT and with argument(s) ARG....
+
+ - Syntax: object-with-ancestors `(('ANCESTOR1 INIT1`)' ...`)'
+ OPERATION ...
+ A `let'-like form of `object' for multiple inheritance. It
+ returns an object inheriting the behaviour of ANCESTOR1 etc. An
+ operation will be invoked in an ancestor if the object itself does
+ not provide such a method. In the case of multiple inherited
+ operations with the same identity, the operation used is the one
+ found in the first ancestor in the ancestor list.
+
+ - Syntax: operate-as COMPONENT OPERATION SELF ARG ...
+ Used in an operation definition (of SELF) to invoke the OPERATION
+ in an ancestor COMPONENT but maintain the object's identity. Also
+ known as "send-to-super".
+
+ - Procedure: print OBJ PORT
+ A default `print' operation is provided which is just `(format
+ PORT OBJ)' (*Note Format::) for non-instances and prints OBJ
+ preceded by `#<INSTANCE>' for instances.
+
+ - Function: size OBJ
+ The default method returns the number of elements in OBJ if it is
+ a vector, string or list, `2' for a pair, `1' for a character and
+ by default id an error otherwise. Objects such as collections
+ (*Note Collections::) may override the default in an obvious way.
+
+
+File: slib.info, Node: Setters, Next: Yasos examples, Prev: Yasos interface, Up: Yasos
+
+Setters
+-------
+
+ "Setters" implement "generalized locations" for objects associated
+with some sort of mutable state. A "getter" operation retrieves a
+value from a generalized location and the corresponding setter
+operation stores a value into the location. Only the getter is named -
+the setter is specified by a procedure call as below. (Dylan uses
+special syntax.) Typically, but not necessarily, getters are access
+operations to extract values from Yasos objects (*Note Yasos::).
+Several setters are predefined, corresponding to getters `car', `cdr',
+`string-ref' and `vector-ref' e.g., `(setter car)' is equivalent to
+`set-car!'.
+
+ This implementation of setters is similar to that in Dylan(TM)
+(`Dylan: An object-oriented dynamic language', Apple Computer Eastern
+Research and Technology). Common LISP provides similar facilities
+through `setf'.
+
+ - Function: setter GETTER
+ Returns the setter for the procedure GETTER. E.g., since
+ `string-ref' is the getter corresponding to a setter which is
+ actually `string-set!':
+ (define foo "foo")
+ ((setter string-ref) foo 0 #\F) ; set element 0 of foo
+ foo => "Foo"
+
+ - Syntax: set PLACE NEW-VALUE
+ If PLACE is a variable name, `set' is equivalent to `set!'.
+ Otherwise, PLACE must have the form of a procedure call, where the
+ procedure name refers to a getter and the call indicates an
+ accessible generalized location, i.e., the call would return a
+ value. The return value of `set' is usually unspecified unless
+ used with a setter whose definition guarantees to return a useful
+ value.
+ (set (string-ref foo 2) #\O) ; generalized location with getter
+ foo => "FoO"
+ (set foo "foo") ; like set!
+ foo => "foo"
+
+ - Procedure: add-setter GETTER SETTER
+ Add procedures GETTER and SETTER to the (inaccessible) list of
+ valid setter/getter pairs. SETTER implements the store operation
+ corresponding to the GETTER access operation for the relevant
+ state. The return value is unspecified.
+
+ - Procedure: remove-setter-for GETTER
+ Removes the setter corresponding to the specified GETTER from the
+ list of valid setters. The return value is unspecified.
+
+ - Syntax: define-access-operation GETTER-NAME
+ Shorthand for a Yasos `define-operation' defining an operation
+ GETTER-NAME that objects may support to return the value of some
+ mutable state. The default operation is to signal an error. The
+ return value is unspecified.
+
+
+File: slib.info, Node: Yasos examples, Prev: Setters, Up: Yasos
+
+Examples
+--------
+
+ (define-operation (print obj port)
+ (format port
+ (if (instance? obj) "#<instance>" "~s")
+ obj))
+
+ (define-operation (SIZE obj)
+ (cond
+ ((vector? obj) (vector-length obj))
+ ((list? obj) (length obj))
+ ((pair? obj) 2)
+ ((string? obj) (string-length obj))
+ ((char? obj) 1)
+ (else
+ (error "Operation not supported: size" obj))))
+
+ (define-predicate cell?)
+ (define-operation (fetch obj))
+ (define-operation (store! obj newValue))
+
+ (define (make-cell value)
+ (object
+ ((cell? self) #t)
+ ((fetch self) value)
+ ((store! self newValue)
+ (set! value newValue)
+ newValue)
+ ((size self) 1)
+ ((print self port)
+ (format port "#<Cell: ~s>" (fetch self)))))
+
+ (define-operation (discard obj value)
+ (format #t "Discarding ~s~%" value))
+
+ (define (make-filtered-cell value filter)
+ (object-with-ancestors ((cell (make-cell value)))
+ ((store! self newValue)
+ (if (filter newValue)
+ (store! cell newValue)
+ (discard self newValue)))))
+
+ (define-predicate array?)
+ (define-operation (array-ref array index))
+ (define-operation (array-set! array index value))
+
+ (define (make-array num-slots)
+ (let ((anArray (make-vector num-slots)))
+ (object
+ ((array? self) #t)
+ ((size self) num-slots)
+ ((array-ref self index) (vector-ref anArray index))
+ ((array-set! self index newValue) (vector-set! anArray index newValue))
+ ((print self port) (format port "#<Array ~s>" (size self))))))
+
+ (define-operation (position obj))
+ (define-operation (discarded-value obj))
+
+ (define (make-cell-with-history value filter size)
+ (let ((pos 0) (most-recent-discard #f))
+ (object-with-ancestors
+ ((cell (make-filtered-call value filter))
+ (sequence (make-array size)))
+ ((array? self) #f)
+ ((position self) pos)
+ ((store! self newValue)
+ (operate-as cell store! self newValue)
+ (array-set! self pos newValue)
+ (set! pos (+ pos 1)))
+ ((discard self value)
+ (set! most-recent-discard value))
+ ((discarded-value self) most-recent-discard)
+ ((print self port)
+ (format port "#<Cell-with-history ~s>" (fetch self))))))
+
+ (define-access-operation fetch)
+ (add-setter fetch store!)
+ (define foo (make-cell 1))
+ (print foo #f)
+ => "#<Cell: 1>"
+ (set (fetch foo) 2)
+ =>
+ (print foo #f)
+ => "#<Cell: 2>"
+ (fetch foo)
+ => 2
+
+
+File: slib.info, Node: Numerics, Next: Procedures, Prev: Macros, Up: Top
+
+Numerics
+********
+
+* Menu:
+
+* Bit-Twiddling:: 'logical
+* Modular Arithmetic:: 'modular
+* Prime Testing and Generation:: 'primes
+* Prime Factorization:: 'factor
+* Random Numbers:: 'random
+* Cyclic Checksum:: 'make-crc
+* Plotting:: 'charplot
+* Root Finding::
+
+
+File: slib.info, Node: Bit-Twiddling, Next: Modular Arithmetic, Prev: Numerics, Up: Numerics
+
+Bit-Twiddling
+=============
+
+ `(require 'logical)'
+
+ The bit-twiddling functions are made available through the use of the
+`logical' package. `logical' is loaded by inserting `(require
+'logical)' before the code that uses these functions.
+
+ - Function: logand N1 N1
+ Returns the integer which is the bit-wise AND of the two integer
+ arguments.
+
+ Example:
+ (number->string (logand #b1100 #b1010) 2)
+ => "1000"
+
+ - Function: logior N1 N2
+ Returns the integer which is the bit-wise OR of the two integer
+ arguments.
+
+ Example:
+ (number->string (logior #b1100 #b1010) 2)
+ => "1110"
+
+ - Function: logxor N1 N2
+ Returns the integer which is the bit-wise XOR of the two integer
+ arguments.
+
+ Example:
+ (number->string (logxor #b1100 #b1010) 2)
+ => "110"
+
+ - Function: lognot N
+ Returns the integer which is the 2s-complement of the integer
+ argument.
+
+ Example:
+ (number->string (lognot #b10000000) 2)
+ => "-10000001"
+ (number->string (lognot #b0) 2)
+ => "-1"
+
+ - Function: logtest J K
+ (logtest j k) == (not (zero? (logand j k)))
+
+ (logtest #b0100 #b1011) => #f
+ (logtest #b0100 #b0111) => #t
+
+ - Function: logbit? INDEX J
+ (logbit? index j) == (logtest (integer-expt 2 index) j)
+
+ (logbit? 0 #b1101) => #t
+ (logbit? 1 #b1101) => #f
+ (logbit? 2 #b1101) => #t
+ (logbit? 3 #b1101) => #t
+ (logbit? 4 #b1101) => #f
+
+ - Function: ash INT COUNT
+ Returns an integer equivalent to `(inexact->exact (floor (* INT
+ (expt 2 COUNT))))'.
+
+ Example:
+ (number->string (ash #b1 3) 2)
+ => "1000"
+ (number->string (ash #b1010 -1) 2)
+ => "101"
+
+ - Function: logcount N
+ Returns the number of bits in integer N. If integer is positive,
+ the 1-bits in its binary representation are counted. If negative,
+ the 0-bits in its two's-complement binary representation are
+ counted. If 0, 0 is returned.
+
+ Example:
+ (logcount #b10101010)
+ => 4
+ (logcount 0)
+ => 0
+ (logcount -2)
+ => 1
+
+ - Function: integer-length N
+ Returns the number of bits neccessary to represent N.
+
+ Example:
+ (integer-length #b10101010)
+ => 8
+ (integer-length 0)
+ => 0
+ (integer-length #b1111)
+ => 4
+
+ - Function: integer-expt N K
+ Returns N raised to the non-negative integer exponent K.
+
+ Example:
+ (integer-expt 2 5)
+ => 32
+ (integer-expt -3 3)
+ => -27
+
+ - Function: bit-extract N START END
+ Returns the integer composed of the START (inclusive) through END
+ (exclusive) bits of N. The STARTth bit becomes the 0-th bit in
+ the result.
+
+ Example:
+ (number->string (bit-extract #b1101101010 0 4) 2)
+ => "1010"
+ (number->string (bit-extract #b1101101010 4 9) 2)
+ => "10110"
+
+
+File: slib.info, Node: Modular Arithmetic, Next: Prime Testing and Generation, Prev: Bit-Twiddling, Up: Numerics
+
+Modular Arithmetic
+==================
+
+ `(require 'modular)'
+
+ - Function: extended-euclid N1 N2
+ Returns a list of 3 integers `(d x y)' such that d = gcd(N1, N2) =
+ N1 * x + N2 * y.
+
+ - Function: symmetric:modulus N
+ Returns `(quotient (+ -1 n) -2)' for positive odd integer N.
+
+ - Function: modulus->integer MODULUS
+ Returns the non-negative integer characteristic of the ring formed
+ when MODULUS is used with `modular:' procedures.
+
+ - Function: modular:normalize MODULUS N
+ Returns the integer `(modulo N (modulus->integer MODULUS))' in the
+ representation specified by MODULUS.
+
+The rest of these functions assume normalized arguments; That is, the
+arguments are constrained by the following table:
+
+For all of these functions, if the first argument (MODULUS) is:
+`positive?'
+ Work as before. The result is between 0 and MODULUS.
+
+`zero?'
+ The arguments are treated as integers. An integer is returned.
+
+`negative?'
+ The arguments and result are treated as members of the integers
+ modulo `(+ 1 (* -2 MODULUS))', but with "symmetric"
+ representation; i.e. `(<= (- MODULUS) N MODULUS)'.
+
+If all the arguments are fixnums the computation will use only fixnums.
+
+ - Function: modular:invertable? MODULUS K
+ Returns `#t' if there exists an integer n such that K * n == 1 mod
+ MODULUS, and `#f' otherwise.
+
+ - Function: modular:invert MODULUS K2
+ Returns an integer n such that 1 = (n * K2) mod MODULUS. If K2
+ has no inverse mod MODULUS an error is signaled.
+
+ - Function: modular:negate MODULUS K2
+ Returns (-K2) mod MODULUS.
+
+ - Function: modular:+ MODULUS K2 K3
+ Returns (K2 + K3) mod MODULUS.
+
+ - Function: modular:- MODULUS K2 K3
+ Returns (K2 - K3) mod MODULUS.
+
+ - Function: modular:* MODULUS K2 K3
+ Returns (K2 * K3) mod MODULUS.
+
+ The Scheme code for `modular:*' with negative MODULUS is not
+ completed for fixnum-only implementations.
+
+ - Function: modular:expt MODULUS K2 K3
+ Returns (K2 ^ K3) mod MODULUS.
+
+
+File: slib.info, Node: Prime Testing and Generation, Next: Prime Factorization, Prev: Modular Arithmetic, Up: Numerics
+
+Prime Testing and Generation
+============================
+
+ `(require 'primes)'
+
+ This package tests and generates prime numbers. The strategy used is
+as follows:
+
+ First, use trial division by small primes (primes less than 1000)
+ to quickly weed out composites with small factors. As a side
+ benefit, this makes the test precise for numbers up to one million.
+
+ Second, apply the Miller-Rabin primality test to detect (with high
+ probability) any remaining composites.
+
+ The Miller-Rabin test is a Monte-Carlo test--in other words, it's fast
+and it gets the right answer with high probability. For a candidate
+that *is* prime, the Miller-Rabin test is certain to report "prime"; it
+will never report "composite". However, for a candidate that is
+composite, there is a (small) probability that the Miller-Rabin test
+will erroneously report "prime". This probability can be made
+arbitarily small by adjusting the number of iterations of the
+Miller-Rabin test.
+
+ - Function: probably-prime? CANDIDATE
+ - Function: probably-prime? CANDIDATE ITER
+ Returns `#t' if `candidate' is probably prime. The optional
+ parameter `iter' controls the number of iterations of the
+ Miller-Rabin test. The probability of a composite candidate being
+ mistaken for a prime is at most `(1/4)^iter'. The default value of
+ `iter' is 15, which makes the probability less than 1 in 10^9.
+
+
+ - Function: primes< START COUNT
+ - Function: primes< START COUNT ITER
+ - Function: primes> START COUNT
+ - Function: primes> START COUNT ITER
+ Returns a list of the first `count' odd probable primes less (more)
+ than or equal to `start'. The optional parameter `iter' controls
+ the number of iterations of the Miller-Rabin test for each
+ candidate. The probability of a composite candidate being
+ mistaken for a prime is at most `(1/4)^iter'. The default value
+ of `iter' is 15, which makes the probability less than 1 in 10^9.
+
+
+* Menu:
+
+* The Miller-Rabin Test:: How the Miller-Rabin test works
+
+
+File: slib.info, Node: The Miller-Rabin Test, Prev: Prime Testing and Generation, Up: Prime Testing and Generation
+
+Theory
+------
+
+ Rabin and Miller's result can be summarized as follows. Let `p' (the
+candidate prime) be any odd integer greater than 2. Let `b' (the
+"base") be an integer in the range `2 ... p-1'. There is a fairly
+simple Boolean function--call it `C', for "Composite"--with the
+following properties:
+ If `p' is prime, `C(p, b)' is false for all `b' in the range `2
+ ... p-1'.
+
+ If `p' is composite, `C(p, b)' is false for at most 1/4 of all `b'
+ in the range ` 2 ... p-1'. (If the test fails for base `b', `p'
+ is called a *strong pseudo-prime to base `b'*.)
+
+ For details of `C', and why it fails for at most 1/4 of the potential
+bases, please consult a book on number theory or cryptography such as
+"A Course in Number Theory and Cryptography" by Neal Koblitz, published
+by Springer-Verlag 1994.
+
+ There is nothing probablistic about this result. It's true for all
+`p'. If we had time to test `(1/4)p + 1' different bases, we could
+definitively determine the primality of `p'. For large candidates,
+that would take much too long--much longer than the simple approach of
+dividing by all numbers up to `sqrt(p)'. This is where probability
+enters the picture.
+
+ Suppose we have some candidate prime `p'. Pick a random integer `b'
+in the range `2 ... p-1'. Compute `C(p,b)'. If `p' is prime, the
+result will certainly be false. If `p' is composite, the probability
+is at most 1/4 that the result will be false (demonstrating that `p' is
+a strong pseudoprime to base `b'). The test can be repeated with other
+random bases. If `p' is prime, each test is certain to return false.
+If `p' is composite, the probability of `C(p,b)' returning false is at
+most 1/4 for each test. Since the `b' are chosen at random, the tests
+outcomes are independent. So if `p' is composite and the test is
+repeated, say, 15 times, the probability of it returning false all
+fifteen times is at most (1/4)^15, or about 10^-9. If the test is
+repeated 30 times, the probability of failure drops to at most 8.3e-25.
+
+ Rabin and Miller's result holds for *all* candidates `p'. However,
+if the candidate `p' is picked at random, the probability of the
+Miller-Rabin test failing is much less than the computed bound. This
+is because, for *most* composite numbers, the fraction of bases that
+cause the test to fail is much less than 1/4. For example, if you pick
+a random odd number less than 1000 and apply the Miller-Rabin test with
+only 3 random bases, the computed failure bound is (1/4)^3, or about
+1.6e-2. However, the actual probability of failure is much less--about
+7.2e-5. If you accidentally pick 703 to test for primality, the
+probability of failure is (161/703)^3, or about 1.2e-2, which is almost
+as high as the computed bound. This is because 703 is a strong
+pseudoprime to 161 bases. But if you pick at random there is only a
+small chance of picking 703, and no other number less than 1000 has
+that high a percentage of pseudoprime bases.
+
+ The Miller-Rabin test is sometimes used in a slightly different
+fashion, where it can, at least in principle, cause problems. The
+weaker version uses small prime bases instead of random bases. If you
+are picking candidates at random and testing for primality, this works
+well since very few composites are strong pseudo-primes to small prime
+bases. (For example, there is only one composite less than 2.5e10 that
+is a strong pseudo-prime to the bases 2, 3, 5, and 7.) The problem
+with this approach is that once a candidate has been picked, the test is
+deterministic. This distinction is subtle, but real. With the
+randomized test, for *any* candidate you pick--even if your
+candidate-picking procedure is strongly biased towards troublesome
+numbers, the test will work with high probability. With the
+deterministic version, for any particular candidate, the test will
+either work (with probability 1), or fail (with probability 1). It
+won't fail for very many candidates, but that won't be much consolation
+if your candidate-picking procedure is somehow biased toward troublesome
+numbers.
+
+
+File: slib.info, Node: Prime Factorization, Next: Random Numbers, Prev: Prime Testing and Generation, Up: Numerics
+
+Prime Factorization
+===================
+
+ `(require 'factor)'
+
+ - Function: factor K
+ Returns a list of the prime factors of K. The order of the
+ factors is unspecified. In order to obtain a sorted list do
+ `(sort! (factor k) <)'.
+
+ *Note:* The rest of these procedures implement the Solovay-Strassen
+primality test. This test has been superseeded by the faster *Note
+probably-prime?: Prime Testing and Generation. However these are left
+here as they take up little space and may be of use to an
+implementation without bignums.
+
+ See Robert Solovay and Volker Strassen, `A Fast Monte-Carlo Test for
+Primality', SIAM Journal on Computing, 1977, pp 84-85.
+
+ - Function: jacobi-symbol P Q
+ Returns the value (+1, -1, or 0) of the Jacobi-Symbol of exact
+ non-negative integer P and exact positive odd integer Q.
+
+ - Function: prime? P
+ Returns `#f' if P is composite; `#t' if P is prime. There is a
+ slight chance `(expt 2 (- prime:trials))' that a composite will
+ return `#t'.
+
+ - Function: prime:trials
+ Is the maxinum number of iterations of Solovay-Strassen that will
+ be done to test a number for primality.
+
+
+File: slib.info, Node: Random Numbers, Next: Cyclic Checksum, Prev: Prime Factorization, Up: Numerics
+
+Random Numbers
+==============
+
+ `(require 'random)'
+
+ - Procedure: random N
+ - Procedure: random N STATE
+ Accepts a positive integer or real N and returns a number of the
+ same type between zero (inclusive) and N (exclusive). The values
+ returned have a uniform distribution.
+
+ The optional argument STATE must be of the type produced by
+ `(make-random-state)'. 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' operation.
+
+ - Variable: *random-state*
+ Holds a data structure that encodes the internal state of the
+ random-number generator that `random' uses by default. The nature
+ of this data structure is implementation-dependent. It may be
+ printed out and successfully read back in, but may or may not
+ function correctly as a random-number state object in another
+ implementation.
+
+ - Procedure: make-random-state
+ - Procedure: make-random-state STATE
+ Returns a new object of type suitable for use as the value of the
+ variable `*random-state*' and as a second argument to `random'.
+ If argument STATE is given, a copy of it is returned. Otherwise a
+ copy of `*random-state*' is returned.
+
+ If inexact numbers are support by the Scheme implementation,
+`randinex.scm' will be loaded as well. `randinex.scm' contains
+procedures for generating inexact distributions.
+
+ - Procedure: random:uniform STATE
+ Returns an uniformly distributed inexact real random number in the
+ range between 0 and 1.
+
+ - Procedure: random:solid-sphere! VECT
+ - Procedure: random:solid-sphere! VECT STATE
+ Fills VECT with inexact real random numbers the sum of whose
+ squares is less than 1.0. Thinking of VECT as coordinates in
+ space of dimension N = `(vector-length VECT)', the coordinates are
+ uniformly distributed within the unit N-shere. The sum of the
+ squares of the numbers is returned.
+
+ - Procedure: random:hollow-sphere! VECT
+ - Procedure: random:hollow-sphere! VECT STATE
+ Fills VECT with inexact real random numbers the sum of whose
+ squares is equal to 1.0. Thinking of VECT as coordinates in space
+ of dimension n = `(vector-length VECT)', the coordinates are
+ uniformly distributed over the surface of the unit n-shere.
+
+ - Procedure: random:normal
+ - Procedure: random:normal STATE
+ Returns an inexact real in a normal distribution with mean 0 and
+ standard deviation 1. For a normal distribution with mean M and
+ standard deviation D use `(+ M (* D (random:normal)))'.
+
+ - Procedure: random:normal-vector! VECT
+ - Procedure: random:normal-vector! VECT STATE
+ Fills VECT with inexact real random numbers which are independent
+ and standard normally distributed (i.e., with mean 0 and variance
+ 1).
+
+ - Procedure: random:exp
+ - Procedure: random:exp STATE
+ Returns an inexact real in an exponential distribution with mean
+ 1. For an exponential distribution with mean U use (* U
+ (random:exp)).
+