Like regular expressions, our quasi-literal term-tree patterns and expressions have quantifiers. These quanitifiers annotate the pattern or expression to its left.
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 examples into term trees:
The text in the boxes below is from the Scheme FAQ.
Likewise for term trees of course. For us, the corresponding example quasi-literal expression ("template" above) might be
term`[[$a, $c*], [$b, $d*], [$e*]*]`
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*)*)`
Here's a full example where we use a quasi-literal pattern ("pattern" above) to bind the variables, which we then use as input for the above expression ("template"):
? pragma.syntax("0.8") ? def term`[@a, [@b, @c*], [@d, @e*]*]` := term`[1, [2, 3, 4], , [6, 7, 8]]` # value: term`[1, # [2, 3, 4], # , # [6, 7, 8]]` ? a # value: term`1` ? b # value: term`2` ? c # value: [term`3`, term`4`] ? d # value: [term`5`, term`6`] ? e # value: [, [term`7`, term`8`]] ? term`[[$a, $c*], [$b, $d*], [$e*]*]` # value: term`[[1, 3, 4], # [2, 5, 6], # , # [7, 8]]`
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 attitude as shown by the following Scheme example.
? 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?
Who should we acknowledge for Scheme's "..." system? Darius Bacon writes:
I'm not sure, but the earliest I've seen it was in a Compiler Construction volume around 1972 -- there was a paper (by William Waite? can't remember) about an essentially equivalent rewriting system with a different syntax. The Scheme report did not acknowledge it, so I guess it's a reinvention.
(any further information about the origin of the idea would be appreciated)
We also thank 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.
Unless stated otherwise, all text on this page which is either unattributed or by Mark S. Miller is hereby placed in the public domain.