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, 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.
-