diff options
Diffstat (limited to 'slib.info-3')
| -rw-r--r-- | slib.info-3 | 859 |
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. + |