Submatches vs. Recursion in ThiNG Patterns

Submatching in a pattern, +var@pattern, looks suspiciously similar to recursion in a value, var=value. In each case, we expect a value which is both named and processed, and in each case, a binding is introduced into code. The processing in the submatch case is a further pattern-match operation, and in the recursion case it is a nested evaluation.

The main difference, besides the overall context, between the two forms is the scope of the introduced binding: in the submatch, the pattern variable to the left of the @ sign is bound only in the right-hand-side of the overall pattern, at present, whereas in the recursive value the variable to the left of the = is bound in the right-hand-side of the recursion itself. Another important difference is that in the submatch context, the +var is clearly just a binding form, whereas in the recursion context, var can be seen as acting both as a binding form and a reference to the bound value. Another way of looking at it, though, has the var acting solely as a binding form, with the right-hand-side of the = being the actual result of the expression — the fact that the left and right-hand-sides are equivalent is not relevant, in this interpretation.

What if the two forms were unified, based on their similarities, using either var=pattern-or-value or +var=pattern-or-value for both pieces of syntax? The former seems out-of-place for submatches, since we want to clearly mark bindings that will propagate their bound value into the code on the right-hand-side of an object clause; and the latter seems out-of-place in a recursive value, since +var implies a binding object, which is a first-class datum in ThiNG.

Compare and contrast the following — a string-interleaving routine using the current syntax for both submatch and recursion:

sepList: [+s: loop=[(cons +x +more@(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

The same routine using +var=pattern-or-value for both:

sepList: [+s: +loop=[(cons +x +more=(cons _ _)): (x ++ s ++ loop more)
                     (cons +x _): x
                     _: EmptyString]]

Finally, the same routine using var=pattern-or-value for both:

sepList: [+s: loop=[(cons +x more=(cons _ _)): (x ++ s ++ loop more)
                    (cons +x _): x
                    _: EmptyString]]

Finally, there's the question of scope: if the same syntax is used for both submatch and for recursion, what happens if we adjust the scoping rules to be as similar as possible? It doesn't make sense for recursive-value's scoping rule to be changed to be the same as submatch's scoping rule — there's no right-hand-side in a value for the binding to be visible in! — but the other way around might be worth considering: let the binding introduced as part of a submatch be visible as part of the right-hand-side of the submatch. What happens then? Do we end up with infinite patterns? Do we instead end up with a kind of unification-constraint in which an object matching a submatch that is referred to within that same submatch is constrained to have the same recursive topology as the pattern itself?

[Update: Something I forgot to mention — with the scope rule for submatches as it stands, it's possible to evaluate and then compile patterns ahead of execution time. Changing the scope rule can make compilation of ThiNG code more difficult, forcing the system to be more late-bound than perhaps it needs to be.]