diff options
Diffstat (limited to 'slib.info-3')
| -rw-r--r-- | slib.info-3 | 859 |
1 files changed, 0 insertions, 859 deletions
diff --git a/slib.info-3 b/slib.info-3 deleted file mode 100644 index 7109890..0000000 --- a/slib.info-3 +++ /dev/null @@ -1,859 +0,0 @@ -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. - |