2 Replacement Forms
2.1 Singlefold Rewriting
| (replace rule-spec ...) |
| |
| rule-spec | | = | | (pat ... --> expr) | | | | | | | (pat ... --> (=> id) expr) | | | | | | | (pat ... --> (? guard) expr) |
|
Transforms to a function which applies rules specified by rule-spec in an attempt to transform the entire input expression. If no rules could be applied, input expression is left unchanged.
pat — any pattern suitable for the match form. The sequence of patterns correspond to a sequence of arguments to which a rewriting function is applied.
expr — any expression. In contrast to match the right-hand side part of the rule should contain only one expression. Use begin for sequencing.
Examples: |
| | | > (f 4) | 16 | | > (f 4 5) | 20 | | > (f 4 5 6) | '(4 5 6) |
|
If none of patterns match, the input arguments are returned as a list.
An optional (=> id) between patterns and the expr is bound to a failure procedure of zero arguments. It works in the same way as in the match form.
An optional (? guard) between patterns and the expr is used to guard the rule. The guard is evaluated with bindings given by patterns. If guard evaluates to #f evaluation process escapes back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match. Otherwards the rule is applied.
Transforms to a procedure which applies rules specified by rule-spec in an attempt to transform each subpart of the input expression. If no rules could be applied, input expression is left unchanged.
Examples: |
| > ((/. 'a --> 'x) '(a b a d a)) | '(x b x d x) | | > ((/. 'a --> 'x) '(a (b (a) d) a)) | '(x (b (x) d) x) | | > ((/. 'a --> 'b 'b --> 'a) '(a (b (a) b) a)) | '(b (a (b) a) b) |
|
Only unary rules could be applied to subexpressions.
At the same time multiary rules could be applied to a sequence of input arguments.
Examples: |
| | | > (g 4) | 16 | | > (g '(4 5)) | '(16 25) | | > (g 4 5) | 20 |
|
2.2 Repetitive Rewriting
Repetitive rewriting rules could be either regular or terminal.
Application of repetitive rewriting rules follows the algorithm:
Consequently try to apply given rules to the expression.
If a pattern, corresponding to a regular rule matches, make rewriting and apply rules to the result, starting from the beginning of the rule sequence.
If a pattern, corresponding to a terminal rule matches, make rewriting, stop the rewriting process and return the result.
The rewriting process stops either if expression does not change after rewriting, or if the last applied rule was terminal.
| (replace-repeated rule-spec ...) |
| |
| rule-spec | | = | | (pat ... ar expr) | | | | | | | (pat ... ar (=> id) expr) | | | | | | | (pat ... ar (? guard) expr) | | | | | | | | ar | | = | | --> | | | | | | | -->. |
|
Transforms to a function which applies rules, specified by rule-spec, repeatedly in an attempt to get the normal form of the entire input expression.
Arrows --> and -->. correspond to regular and terminal rewriting rules, respectively.
Transforms to a procedure which repeatedly performs rewriting in every part of the given expression until either result no longer changes, or terminal rule is applied. It performs one complete pass over the expression using
replace-all, then carries out the next pass.
Each pass is done using preorder traversal of nested list structure.
Example: |
| > ((//. 'a --> 'b | | 'b --> 'c | | 'c --> 'd) '(a b c)) |
| '(d d d) |
|
Using a terminal rule
| > ((//. 'a -->. 'b | | 'b --> 'c | | 'c --> 'a) '(a b c)) |
|
'(b b b) |
If rewriting proceeds with multiple values, these values could be accepted as arguments during repeating iterations.
Example. Calculation of GCD:
Let’s compare three functions which iteratively calculate the n-th Fibonacci number. The first of them is defined in a regular recursive way, the second implements recursion via rewriting, and the third one uses repetitive rewriting.
|
|
| cpu time: 1020 real time: 1028 gc time: 232 | cpu time: 884 real time: 896 gc time: 64 | cpu time: 1016 real time: 1027 gc time: 52 |
| #t |
|