| |
|
|
The
Power of Ellipses
Borrowed from Scheme
|
Like regular expressions, our quasi-literal term-tree patterns
and expressions have quantifiers. These quanitifiers annotate the pattern
or expression to its left.
- '?' means optional -- zero or one occurrence.
- '+' means one or more occurrences.
- '*' means one or more occurrences.
These quantifiers normally just annotate patterns. Why do
we also apply them to expressions? In order to incorporate the expressiveness
of Scheme's "..." notation. This is best explained by transposing
Scheme's example into term trees:
The text in the boxes below is from the Scheme
FAQ.
5.6. How are ellipses (...) "counted" during macro expansion?
Section 4.3.2 of R5RS states
Pattern variables that occur in subpatterns followed by one or more instances
of the identifier ... are allowed only in subtemplates
that are followed by as many instances of .... They are
replaced in the output by all of the subforms they match
in the input, distributed as indicated. It is an error
if the output cannot be built up as specified.
It is important to understand what is meant by "followed"
in the above. Take for example the pattern
(a (b c ...) (d e ...) ...)
What matters is how many ellipsis structurally follow a variable rather than lexically. The variables a, b, c, d and e are followed by three, three, three, two and two ellipses respectively, but
struturally they are followed by none, none, one, one and
two ellipses respectively. The difference between the structural
and lexical ellipsis counts arises because ellipses only apply
to the pattern/template immediatetly preceeding them. Thus,
the above pattern can supply the input for the template
((a c ...) (b d ...) (e ...) ...)
The structural ellipsis count of the template variables matches
that of the pattern, whereas the lexical template count is
completely different.
|
Likewise for term trees of course. For us, the corresponding
example pattern might be
term`[[@a, @c*], [@b, @d*], [@e*]*]`
or, as an expression, with '$'s rather than '@'s. Note that
the square brackes are just syntactic sugar for a term with "tuple"
for a functor name. So the above is equivalent to:
term`tuple(tuple(@a, @c*), tuple(@b, @d*), tuple(@e*)*)`
One issue that is not addressed by the R5RS explanation of macro expansion
is how ellipses templates are expanded when they
combine variables that matched input of different
size. The canonical example for this is
(define-syntax foo
(syntax-rules ()
((foo (a ...) (b ...)) '((a b) ...))))
(foo (1 2) (3 4 5)) ;=> ?
In different Schemes this is either an error or produces
the result '((1 3) (2 4)), i.e. the "oversized" matches are automatically shortend as needed.
|
When these variables are different sizes, since this is
a likely indicator of a bug, and because its easily repaired when it's
intentional, E considers this case to be an error.
? def term`foo([@a*],[@b*])` := term`foo([1,2],[3,4,5])`
# value: term`foo([1, 2],
# [3, 4, 5])`
? a
# value: [term`1`, term`2`]
? b
# value: [term`3`, term`4`, term`5`]
? term`[[$a,$b]*]`
# problem: Failed: Inconsistent shape: 2 vs 3
So let's shorten b and see what success looks
like
? def b2 := b(0,2)
# value: [term`3`, term`4`]
? term`[[$a,$b2]*]`
# value: term`[[1, 3],
# [2, 4]]`
But when the variable is too flat, so to speak (insufficient
dimensions or rank), E takes the same permissive attitute as shown by
the following Scheme example.
Some Schemes relax the above "matching ellipses count" requirement by allowing
allowing template variables to be followed by at least as many ellipses as their corresponding pattern variables. The resulting expansion
repeats the matched input. Thus
(define-syntax foo
(syntax-rules ()
((foo (a ...) (b ...) ...) '(((a b) ...) ...))))
(foo (1 2) (3 4) (5 6 7)) ;=> '(((1 3) (1 4)) ((2 5) (2 6) (2 7)))
produces the desired result. Note however that in any ellipses
sub-template there must be at least one template variable
for which the ellipsis count is exactly the same as in the pattern, otherwise the macro expander would not be able to
determine how many times to repeat the matched input of the
template variables with ellipsis counts higher than in the
pattern.
|
? def term`foo([@a*], [@b*]*)` := term`foo([1,2], [3,4], [5,6,7])`
# value: term`foo([1, 2],
# [3, 4],
# [5, 6, 7])`
? a
# value: [term`1`, term`2`]
? b
# value: [[term`3`, term`4`], [term`5`, term`6`, term`7`]]
? term`[[[$a,$b]*]*]`
# value: term`[[[1, 3],
# [1, 4]],
# [[2, 5],
# [2, 6],
# [2, 7]]]`
Since literal data is repeated as many times as necessary, variables
that are too flat, like a above, are treated in a way that's
intermediate between the treatment of literal data and the treatment of
variables, like b above, of adequate dimensionality.
What are some other good examples of the power of Scheme's "..."
that we should also use here?
Acknowledgements
Who should we acknowledge for Scheme's "..." system?
Matthias Radestock, the editor of the FAQ we quote from above.
Dean Tribble, who suggested incorporating the power of Scheme's "..."
into the quasi-literal handing of Term trees.
|
|
