Import Upstream version 2a6upstream/2a6

1 files changed, 859 insertions, 0 deletions

diff --git a/slib.info-3 b/slib.info-3
new file mode 100644
index 0000000..7109890
--- /dev/null
+++ b/slib.info-3
@@ -0,0 +1,859 @@
+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: Weight-Balanced Trees,  Next: Structures,  Prev: Relational Database,  Up: Data Structures
+
+Weight-Balanced Trees
+=====================
+
+  `(require 'wt-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 an comprehensive implementation of
+weight-balanced binary trees which has several advantages over the
+other data structures for large aggregates:
+
+   * In addition to the usual element-level operations like insertion,
+     deletion and lookup, there is a full complement of collection-level
+     operations, like set intersection, set union and subset test, all
+     of which are implemented with good orders of growth in time and
+     space.  This makes weight balanced trees ideal for rapid
+     prototyping of functionally derived specifications.
+
+   * An element in a tree may be indexed by its position under the
+     ordering of the keys, and the ordinal position of an element may
+     be determined, both with reasonable efficiency.
+
+   * Operations to find and remove minimum element make weight balanced
+     trees simple to use for priority queues.
+
+   * The implementation is *functional* rather than *imperative*.  This
+     means that operations like `inserting' an association in a tree do
+     not destroy the old tree, in much the same way that `(+ 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 associations 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.
+
+* Menu:
+
+* Construction of Weight-Balanced Trees::
+* Basic Operations on Weight-Balanced Trees::
+* Advanced Operations on Weight-Balanced Trees::
+* Indexing Operations on Weight-Balanced Trees::
+
+
+File: slib.info,  Node: Construction of Weight-Balanced Trees,  Next: Basic Operations on Weight-Balanced Trees,  Prev: Weight-Balanced Trees,  Up: Weight-Balanced Trees
+
+Construction of Weight-Balanced Trees
+-------------------------------------
+
+  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 which 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.
+
+ - procedure+: make-wt-tree-type KEY<?
+     This procedure creates and returns a new tree type based on the
+     ordering predicate KEY<?.  KEY<? must be a total ordering, having
+     the property that for all key values `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'.
+
+ - variable+: number-wt-type
+     A standard tree type for trees with numeric keys.  `Number-wt-type'
+     could have been defined by
+
+          (define number-wt-type (make-wt-tree-type  <))
+
+ - variable+: string-wt-type
+     A standard tree type for trees with string keys.  `String-wt-type'
+     could have been defined by
+
+          (define string-wt-type (make-wt-tree-type  string<?))
+
+ - procedure+: make-wt-tree WT-TREE-TYPE
+     This procedure creates and returns a newly allocated weight
+     balanced tree.  The tree is empty, i.e. it contains no
+     associations.  WT-TREE-TYPE is a weight balanced tree type
+     obtained by calling `make-wt-tree-type'; the returned tree has
+     this type.
+
+ - procedure+: singleton-wt-tree WT-TREE-TYPE KEY DATUM
+     This procedure creates and returns a newly allocated weight
+     balanced tree.  The tree contains a single association, that of
+     DATUM with KEY.  WT-TREE-TYPE is a weight balanced tree type
+     obtained by calling `make-wt-tree-type'; the returned tree has
+     this type.
+
+ - procedure+: alist->wt-tree TREE-TYPE ALIST
+     Returns a newly allocated weight-balanced tree that contains the
+     same associations as ALIST.  This procedure is equivalent to:
+
+          (lambda (type alist)
+            (let ((tree (make-wt-tree type)))
+              (for-each (lambda (association)
+                          (wt-tree/add! tree
+                                        (car association)
+                                        (cdr association)))
+                        alist)
+              tree))
+
+
+File: slib.info,  Node: Basic Operations on Weight-Balanced Trees,  Next: Advanced Operations on Weight-Balanced Trees,  Prev: Construction of Weight-Balanced Trees,  Up: Weight-Balanced Trees
+
+Basic Operations on Weight-Balanced Trees
+-----------------------------------------
+
+  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.
+
+ - procedure+: wt-tree? OBJECT
+     Returns `#t' if OBJECT is a weight-balanced tree, otherwise
+     returns `#f'.
+
+ - procedure+: wt-tree/empty? WT-TREE
+     Returns `#t' if WT-TREE contains no associations, otherwise
+     returns `#f'.
+
+ - procedure+: wt-tree/size WT-TREE
+     Returns the number of associations in WT-TREE, an exact
+     non-negative integer.  This operation takes constant time.
+
+ - procedure+: wt-tree/add WT-TREE KEY DATUM
+     Returns a new tree containing all the associations in WT-TREE and
+     the association of DATUM with KEY.  If WT-TREE already had an
+     association for KEY, the new association overrides the old.  The
+     average and worst-case times required by this operation are
+     proportional to the logarithm of the number of associations in
+     WT-TREE.
+
+ - procedure+: wt-tree/add! WT-TREE KEY DATUM
+     Associates DATUM with KEY in WT-TREE and returns an unspecified
+     value.  If WT-TREE already has an association for KEY, that
+     association is replaced.  The average and worst-case times
+     required by this operation are proportional to the logarithm of
+     the number of associations in WT-TREE.
+
+ - procedure+: wt-tree/member? KEY WT-TREE
+     Returns `#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.
+
+ - procedure+: wt-tree/lookup WT-TREE KEY DEFAULT
+     Returns the datum associated with KEY in WT-TREE.  If WT-TREE
+     doesn't contain an association for KEY, DEFAULT is returned.  The
+     average and worst-case times required by this operation are
+     proportional to the logarithm of the number of associations in
+     WT-TREE.
+
+ - procedure+: wt-tree/delete WT-TREE KEY
+     Returns a new tree containing all the associations in WT-TREE,
+     except that if WT-TREE contains an association for KEY, it is
+     removed from the result.  The average and worst-case times required
+     by this operation are proportional to the logarithm of the number
+     of associations in WT-TREE.
+
+ - procedure+: wt-tree/delete! WT-TREE KEY
+     If WT-TREE contains an association for KEY the association is
+     removed.  Returns an unspecified value.  The average and worst-case
+     times required by this operation are proportional to the logarithm
+     of the number of associations in WT-TREE.
+
+
+File: slib.info,  Node: Advanced Operations on Weight-Balanced Trees,  Next: Indexing Operations on Weight-Balanced Trees,  Prev: Basic Operations on Weight-Balanced Trees,  Up: Weight-Balanced Trees
+
+Advanced Operations on Weight-Balanced Trees
+--------------------------------------------
+
+  In the following the *size* of a tree is the number of associations
+that the tree contains, and a *smaller* tree contains fewer
+associations.
+
+ - procedure+: wt-tree/split< WT-TREE BOUND
+     Returns a new tree containing all and only the associations in
+     WT-TREE which have a key that is less than BOUND in the ordering
+     relation of the tree type of WT-TREE.  The average and worst-case
+     times required by this operation are proportional to the logarithm
+     of the size of WT-TREE.
+
+ - procedure+: wt-tree/split> WT-TREE BOUND
+     Returns a new tree containing all and only the associations in
+     WT-TREE which have a key that is greater than BOUND in the
+     ordering relation of the tree type of WT-TREE.  The average and
+     worst-case times required by this operation are proportional to the
+     logarithm of size of WT-TREE.
+
+ - procedure+: wt-tree/union WT-TREE-1 WT-TREE-2
+     Returns a new tree containing all the associations from both trees.
+     This operation is asymmetric: when both trees have an association
+     for the same key, the returned tree associates the datum from
+     WT-TREE-2 with the key.  Thus if the trees are viewed as discrete
+     maps then `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 time required is at worst proportional to
+     the logarithm of the size of the larger tree.
+
+ - procedure+: wt-tree/intersection WT-TREE-1 WT-TREE-2
+     Returns a new tree containing all and only those associations from
+     WT-TREE-1 which have keys appearing as the key of an association
+     in WT-TREE-2.  Thus the associated data in the result are those
+     from WT-TREE-1.  If the trees are being used as sets the result is
+     the set intersection of the arguments.  As a discrete map
+     operation, `wt-tree/intersection' computes the domain restriction
+     of WT-TREE-1 to (the domain of) WT-TREE-2.  The time required by
+     this operation is never worse that proportional to the sum of the
+     sizes of the trees.
+
+ - procedure+: wt-tree/difference WT-TREE-1 WT-TREE-2
+     Returns a new tree containing all and only those associations from
+     WT-TREE-1 which have keys that *do not* appear as the key of an
+     association in WT-TREE-2.  If the trees are viewed as sets the
+     result is the asymmetric set difference of the arguments.  As a
+     discrete map operation, it computes the domain restriction of
+     WT-TREE-1 to the complement of (the domain of) WT-TREE-2.  The
+     time required by this operation is never worse that proportional to
+     the sum of the sizes of the trees.
+
+ - procedure+: wt-tree/subset? WT-TREE-1 WT-TREE-2
+     Returns `#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.
+
+ - procedure+: wt-tree/set-equal? WT-TREE-1 WT-TREE-2
+     Returns `#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.
+
+ - procedure+: wt-tree/fold COMBINER INITIAL WT-TREE
+     This procedure reduces WT-TREE by combining all the associations,
+     using an reverse in-order traversal, so the associations are
+     visited in reverse order.  COMBINER is a procedure of three
+     arguments: a key, a datum and the accumulated result so far.
+     Provided COMBINER takes time bounded by a constant, `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)
+
+ - procedure+: wt-tree/for-each ACTION WT-TREE
+     This procedure traverses the tree in-order, applying ACTION to
+     each association.  The associations are processed in increasing
+     order of their keys.  ACTION is a procedure of two arguments which
+     take the key and datum respectively of the association.  Provided
+     ACTION takes time bounded by a constant, `wt-tree/for-each' takes
+     time proportional to in the size of WT-TREE.  The example prints
+     the tree:
+
+          (wt-tree/for-each (lambda (key value)
+                              (display (list key value)))
+                            WT-TREE))
+
+
+File: slib.info,  Node: Indexing Operations on Weight-Balanced Trees,  Prev: Advanced Operations on Weight-Balanced Trees,  Up: Weight-Balanced Trees
+
+Indexing Operations on Weight-Balanced Trees
+--------------------------------------------
+
+  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.
+
+ - procedure+: wt-tree/index WT-TREE INDEX
+ - procedure+: wt-tree/index-datum WT-TREE INDEX
+ - procedure+: wt-tree/index-pair WT-TREE INDEX
+     Returns the 0-based INDEXth association of WT-TREE in the sorted
+     sequence under the tree's ordering relation on the keys.
+     `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 an error if the tree is empty, if
+     INDEX`<0', or if INDEX is greater than or equal to the number of
+     associations in the tree.
+
+     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 (-1+ (wt-tree/size WT-TREE)))
+
+ - procedure+: wt-tree/rank WT-TREE KEY
+     Determines the 0-based position of KEY in the sorted sequence of
+     the keys under the tree's ordering relation, or `#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.
+
+ - procedure+: wt-tree/min WT-TREE
+ - procedure+: wt-tree/min-datum WT-TREE
+ - procedure+: wt-tree/min-pair WT-TREE
+     Returns the association of WT-TREE that has the least key under
+     the tree's ordering relation.  `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))
+
+ - procedure+: wt-tree/delete-min WT-TREE
+     Returns a new tree containing all of the associations in WT-TREE
+     except the association with the least key under the WT-TREE's
+     ordering relation.  An error is signalled if the tree is empty.
+     The average and worst-case times required by this operation are
+     proportional to the logarithm of the number of associations in the
+     tree.  This operation is equivalent to
+
+          (wt-tree/delete WT-TREE (wt-tree/min WT-TREE))
+
+ - procedure+: wt-tree/delete-min! WT-TREE
+     Removes the association with the least key under the WT-TREE's
+     ordering relation.  An error is signalled if the tree is empty.
+     The average and worst-case times required by this operation are
+     proportional to the logarithm of the number of associations in the
+     tree.  This operation is equivalent to
+
+          (wt-tree/delete! WT-TREE (wt-tree/min WT-TREE))
+
+
+File: slib.info,  Node: Structures,  Prev: Weight-Balanced Trees,  Up: Data Structures
+
+Structures
+==========
+
+  `(require 'struct)' (uses defmacros)
+
+  `defmacro's which implement "records" from the book `Essentials of
+Programming Languages' by Daniel P. Friedman, M.  Wand and C.T. Haynes.
+Copyright 1992 Jeff Alexander, Shinnder Lee, and Lewis Patterson
+
+  Matthew McDonald <mafm@cs.uwa.edu.au> added field setters.
+
+ - Macro: define-record TAG (VAR1 VAR2 ...)
+     Defines several functions pertaining to record-name TAG:
+
+      - Function: make-TAG VAR1 VAR2 ...
+
+      - Function: TAG? OBJ
+
+      - Function: TAG->VAR1 OBJ
+
+      - Function: TAG->VAR2 OBJ
+     ...
+
+      - Function: set-TAG-VAR1! OBJ VAL
+
+      - Function: set-TAG-VAR2! OBJ VAL
+     ...
+
+     Here is an example of its use.
+
+          (define-record term (operator left right))
+          => #<unspecified>
+          (define foo (make-term 'plus  1 2))
+          => foo
+          (term-left foo)
+          => 1
+          (set-term-left! foo 2345)
+          => #<unspecified>
+          (term-left foo)
+          => 2345
+
+ - Macro: variant-case EXP (TAG (VAR1 VAR2 ...) BODY) ...
+     executes the following for the matching clause:
+
+          ((lambda (VAR1 VAR ...) BODY)
+             (TAG->VAR1 EXP)
+             (TAG->VAR2 EXP) ...)
+
+
+File: slib.info,  Node: Macros,  Next: Numerics,  Prev: Data Structures,  Up: Top
+
+Macros
+******
+
+* Menu:
+
+* Defmacro::                    Supported by all implementations
+
+* R4RS Macros::                 'macro
+* Macro by Example::            'macro-by-example
+* Macros That Work::            'macros-that-work
+* Syntactic Closures::          'syntactic-closures
+* Syntax-Case Macros::          'syntax-case
+
+Syntax extensions (macros) included with SLIB.  Also *Note Structures::.
+
+* Fluid-Let::                   'fluid-let
+* Yasos::                       'yasos, 'oop, 'collect
+
+
+File: slib.info,  Node: Defmacro,  Next: R4RS Macros,  Prev: Macros,  Up: Macros
+
+Defmacro
+========
+
+  Defmacros are supported by all implementations.
+
+ - Function: gentemp
+     Returns a new (interned) symbol each time it is called.  The symbol
+     names are implementation-dependent
+          (gentemp) => scm:G0
+          (gentemp) => scm:G1
+
+ - Function: defmacro:eval E
+     Returns the `slib:eval' of expanding all defmacros in scheme
+     expression E.
+
+ - Function: defmacro:load FILENAME
+     FILENAME should be a string.  If filename names an existing file,
+     the `defmacro:load' procedure reads Scheme source code expressions
+     and definitions from the file and evaluates them sequentially.
+     These source code expressions and definitions may contain defmacro
+     definitions.  The `macro:load' procedure does not affect the values
+     returned by `current-input-port' and `current-output-port'.
+
+ - Function: defmacro? SYM
+     Returns `#t' if SYM has been defined by `defmacro', `#f' otherwise.
+
+ - Function: macroexpand-1 FORM
+ - Function: macroexpand FORM
+     If FORM is a macro call, `macroexpand-1' will expand the macro
+     call once and return it.  A FORM is considered to be a macro call
+     only if it is a cons whose `car' is a symbol for which a `defmacr'
+     has been defined.
+
+     `macroexpand' is similar to `macroexpand-1', but repeatedly
+     expands FORM until it is no longer a macro call.
+
+ - Macro: defmacro NAME LAMBDA-LIST FORM ...
+     When encountered by `defmacro:eval', `defmacro:macroexpand*', or
+     `defmacro:load' defines a new macro which will henceforth be
+     expanded when encountered by `defmacro:eval',
+     `defmacro:macroexpand*', or `defmacro:load'.
+
+Defmacroexpand
+--------------
+
+  `(require 'defmacroexpand)'
+
+ - Function: defmacro:expand* E
+     Returns the result of expanding all defmacros in scheme expression
+     E.
+
+
+File: slib.info,  Node: R4RS Macros,  Next: Macro by Example,  Prev: Defmacro,  Up: Macros
+
+R4RS Macros
+===========
+
+  `(require 'macro)' is the appropriate call if you want R4RS
+high-level macros but don't care about the low level implementation.  If
+an SLIB R4RS macro implementation is already loaded it will be used.
+Otherwise, one of the R4RS macros implemetations is loaded.
+
+  The SLIB R4RS macro implementations support the following uniform
+interface:
+
+ - Function: macro:expand SEXPRESSION
+     Takes an R4RS expression, macro-expands it, and returns the result
+     of the macro expansion.
+
+ - Function: macro:eval SEXPRESSION
+     Takes an R4RS expression, macro-expands it, evals the result of the
+     macro expansion, and returns the result of the evaluation.
+
+ - Procedure: macro: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'.
+
+
+File: slib.info,  Node: Macro by Example,  Next: Macros That Work,  Prev: R4RS Macros,  Up: Macros
+
+Macro by Example
+================
+
+  `(require 'macro-by-example)'
+
+  A vanilla implementation of `Macro by Example' (Eugene Kohlbecker,
+R4RS) by Dorai Sitaram, (dorai@cs.rice.edu) using `defmacro'.
+
+   * generating hygienic global `define-syntax' Macro-by-Example macros
+     *cheaply*.
+
+   * can define macros which use `...'.
+
+   * needn't worry about a lexical variable in a macro definition
+     clashing with a variable from the macro use context
+
+   * don't suffer the overhead of redefining the repl if `defmacro'
+     natively supported (most implementations)
+
+Caveat
+------
+
+  These macros are not referentially transparent (*note Macros:
+(r4rs)Macros.).  Lexically scoped macros (i.e., `let-syntax' and
+`letrec-syntax') are not supported.  In any case, the problem of
+referential transparency gains poignancy only when `let-syntax' and
+`letrec-syntax' are used.  So you will not be courting large-scale
+disaster unless you're using system-function names as local variables
+with unintuitive bindings that the macro can't use.  However, if you
+must have the full `r4rs' macro functionality, look to the more
+featureful (but also more expensive) versions of syntax-rules available
+in slib *Note Macros That Work::, *Note Syntactic Closures::, and *Note
+Syntax-Case Macros::.
+
+ - Macro: define-syntax KEYWORD TRANSFORMER-SPEC
+     The KEYWORD is an identifier, and the TRANSFORMER-SPEC should be
+     an instance of `syntax-rules'.
+
+     The top-level syntactic environment is extended by binding the
+     KEYWORD to the specified transformer.
+
+          (define-syntax let*
+            (syntax-rules ()
+              ((let* () body1 body2 ...)
+               (let () body1 body2 ...))
+              ((let* ((name1 val1) (name2 val2) ...)
+                 body1 body2 ...)
+               (let ((name1 val1))
+                 (let* (( name2 val2) ...)
+                   body1 body2 ...)))))
+
+ - Macro: syntax-rules LITERALS SYNTAX-RULE ...
+     LITERALS is a list of identifiers, and each SYNTAX-RULE should be
+     of the form
+
+     `(PATTERN TEMPLATE)'
+
+     where the PATTERN and  TEMPLATE are as in the grammar above.
+
+     An instance of `syntax-rules' produces a new macro transformer by
+     specifying a sequence of hygienic rewrite rules.  A use of a macro
+     whose keyword is associated with a transformer specified by
+     `syntax-rules' is matched against the patterns contained in the
+     SYNTAX-RULEs, beginning with the leftmost SYNTAX-RULE.  When a
+     match is found, the macro use is trancribed hygienically according
+     to the template.
+
+     Each pattern begins with the keyword for the macro.  This keyword
+     is not involved in the matching and is not considered a pattern
+     variable or literal identifier.
+
+
+File: slib.info,  Node: Macros That Work,  Next: Syntactic Closures,  Prev: Macro by Example,  Up: Macros
+
+Macros That Work
+================
+
+  `(require 'macros-that-work)'
+
+  `Macros That Work' differs from the other R4RS macro implementations
+in that it does not expand derived expression types to primitive
+expression types.
+
+ - Function: macro:expand EXPRESSION
+ - Function: macwork:expand EXPRESSION
+     Takes an R4RS expression, macro-expands it, and returns the result
+     of the macro expansion.
+
+ - Function: macro:eval EXPRESSION
+ - Function: macwork: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: macwork: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'.
+
+  References:
+
+  The `Revised^4 Report on the Algorithmic Language Scheme' Clinger and
+Rees [editors].  To appear in LISP Pointers.  Also available as a
+technical report from the University of Oregon, MIT AI Lab, and Cornell.
+
+            Macros That Work.  Clinger and Rees.  POPL '91.
+
+  The supported syntax differs from the R4RS in that vectors are allowed
+as patterns and as templates and are not allowed as pattern or template
+data.
+
+     transformer spec  ==>  (syntax-rules literals rules)
+     
+     rules  ==>  ()
+              |  (rule . rules)
+     
+     rule  ==>  (pattern template)
+     
+     pattern  ==>  pattern_var      ; a symbol not in literals
+                |  symbol           ; a symbol in literals
+                |  ()
+                |  (pattern . pattern)
+                |  (ellipsis_pattern)
+                |  #(pattern*)                     ; extends R4RS
+                |  #(pattern* ellipsis_pattern)    ; extends R4RS
+                |  pattern_datum
+     
+     template  ==>  pattern_var
+                 |  symbol
+                 |  ()
+                 |  (template2 . template2)
+                 |  #(template*)                   ; extends R4RS
+                 |  pattern_datum
+     
+     template2  ==>  template
+                  |  ellipsis_template
+     
+     pattern_datum  ==>  string                    ; no vector
+                      |  character
+                      |  boolean
+                      |  number
+     
+     ellipsis_pattern  ==> pattern ...
+     
+     ellipsis_template  ==>  template ...
+     
+     pattern_var  ==>  symbol   ; not in literals
+     
+     literals  ==>  ()
+                 |  (symbol . literals)
+
+Definitions
+-----------
+
+Scope of an ellipsis
+     Within a pattern or template, the scope of an ellipsis (`...') is
+     the pattern or template that appears to its left.
+
+Rank of a pattern variable
+     The rank of a pattern variable is the number of ellipses within
+     whose scope it appears in the pattern.
+
+Rank of a subtemplate
+     The rank of a subtemplate is the number of ellipses within whose
+     scope it appears in the template.
+
+Template rank of an occurrence of a pattern variable
+     The template rank of an occurrence of a pattern variable within a
+     template is the rank of that occurrence, viewed as a subtemplate.
+
+Variables bound by a pattern
+     The variables bound by a pattern are the pattern variables that
+     appear within it.
+
+Referenced variables of a subtemplate
+     The referenced variables of a subtemplate are the pattern
+     variables that appear within it.
+
+Variables opened by an ellipsis template
+     The variables opened by an ellipsis template are the referenced
+     pattern variables whose rank is greater than the rank of the
+     ellipsis template.
+
+Restrictions
+------------
+
+  No pattern variable appears more than once within a pattern.
+
+  For every occurrence of a pattern variable within a template, the
+template rank of the occurrence must be greater than or equal to the
+pattern variable's rank.
+
+  Every ellipsis template must open at least one variable.
+
+  For every ellipsis template, the variables opened by an ellipsis
+template must all be bound to sequences of the same length.
+
+  The compiled form of a RULE is
+
+     rule  ==>  (pattern template inserted)
+     
+     pattern  ==>  pattern_var
+                |  symbol
+                |  ()
+                |  (pattern . pattern)
+                |  ellipsis_pattern
+                |  #(pattern)
+                |  pattern_datum
+     
+     template  ==>  pattern_var
+                 |  symbol
+                 |  ()
+                 |  (template2 . template2)
+                 |  #(pattern)
+                 |  pattern_datum
+     
+     template2  ==>  template
+                  |  ellipsis_template
+     
+     pattern_datum  ==>  string
+                      |  character
+                      |  boolean
+                      |  number
+     
+     pattern_var  ==>  #(V symbol rank)
+     
+     ellipsis_pattern  ==>  #(E pattern pattern_vars)
+     
+     ellipsis_template  ==>  #(E template pattern_vars)
+     
+     inserted  ==>  ()
+                 |  (symbol . inserted)
+     
+     pattern_vars  ==>  ()
+                     |  (pattern_var . pattern_vars)
+     
+     rank  ==>  exact non-negative integer
+
+  where V and E are unforgeable values.
+
+  The pattern variables associated with an ellipsis pattern are the
+variables bound by the pattern, and the pattern variables associated
+with an ellipsis template are the variables opened by the ellipsis
+template.
+
+  If the template contains a big chunk that contains no pattern
+variables or inserted identifiers, then the big chunk will be copied
+unnecessarily.  That shouldn't matter very often.
+