summaryrefslogtreecommitdiffstats
path: root/slib.info-3
diff options
context:
space:
mode:
Diffstat (limited to 'slib.info-3')
-rw-r--r--slib.info-3859
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.
+