Since they are bound to be compared with each other, I thought I would try and summarize the differences in approach between Sergei’s SRFI 257 and my SRFI 262, at least as they are in their current draft state. Obviously I am not unbiased here and would not have submitted SRFI 262 if I didn’t think it were a better design (at least for some purposes – see below on the philosophical difference between the two in their views of what pattern matching is fundamentally for). I hope Sergei will chime in if he feels I have been unfair :-)

• Sergei wrote in his email to me that he considers implementability in pure syntax-rules an explicit goal of his implementation; I, however, believe that it is important that a pattern match implementation be reasonably well optimizing.

  These two goals are not in *exact* opposition to one another (one concern is about hypothetical implementability, and the other about the qualities of specific implementations). But recursive syntax-rules expansions are painful enough as it is, without also trying to do the systematic comparisons between adjacent (expanded) patterns that are needed to do even basic pattern matching optimizations effectively. As such, I believe it’s not even worth considering ‘implementability in pure syntax-rules’ as a design goal for a pattern matcher, because a pure syntax-rules implementation (a tractable one that doesn’t use something like SRFI 148, at least) will never give you the full benefits of pattern matching.

  (I originally wrote a very, very long digression here about the value of an optimizing pattern match compiler. I will instead give this summary: pattern matching is better than writing variable bindings and conditionals by hand not only because it’s better for readability and maintainability, but also because it’s better for efficiency when an optimizing compiler is available. As justification for this claim, I would simply point to figures 6 and 7 in Maranget’s decision tree paper: <http://moscova.inria.fr/~maranget/papers/ml05e-maranget.pdf>. Consider also a pattern like Okasaki’s ‘balance’ function for red-black trees, one of the most beautiful translations of reasoning about structural invariants into functional code <https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/redblack99.pdf>, and trying to find the most efficient way to write it by hand (without redundantly repeating tests!); then later how difficult that code would be to adapt if you wanted to add the two extra cases for the deletion operation by Germane and Might: <https://matt.might.net/papers/germane2014deletion.pdf> vs. just adding the new cases at the end of the pattern match and getting equally efficient code out at the end automatically.)

• In Sergei’s design, you’re limited to writing your pattern syntax transformers with syntax-rules patterns and templates; in mine you can use nearly any high- or low-level macro transformer system your Scheme implementation supports, including ones you may have created yourself. I consider this a major advantage of my design, since there are things you simply can’t do in syntax-rules, and many more things that are possible but not at all easy.

• Sergei’s design embraces non-linear patterns; mine rejects them because I think they compose too badly with too many other features, as described in my SRFI. I think it *is* possible to use non-linear patterns as effective and elegant primitives, in the style of Christian Queinnec – but only without disjunctive or negated patterns, which I prefer over non-linearity, and possibly with problematic restrictions on how sequence patterns can be expressed. (Because my pattern matcher currently lacks pattern guards or early escape/retry, it’s also not very easy to work around this issue. This isn’t a deliberate omission and I would like to restore some functionality for doing this, as mentioned in the Issues list and recently on the mailing list.)

• Apropos of which, SRFI 257 provides escape procedures for moving onto the next clause for this purpose, but they don’t call a continuation to fully escape the clause, and are thus only safe in tail position. I am cautious about doing this; this issue is also under active consideration.

• Sergei’s sequence pattern matchers are based on backtracking; mine do not prescribe or require any particular implementation strategy.

  (Note for completeness and honesty, given what I wrote above about the importance of optimization: while my implementation is currently able to generate optimal code for many patterns, the performance of sequence patterns is not great yet. Efficiency-wise, there’s a lot of low-hanging fruit in that part of the sample implementation, as of writing.)

• Sergei’s design also includes an alternative escape procedure to try and find a different solution to a backtracking problem as expressed in the pattern for the current clause. There is no equivalent of this in mine, and never will be, because my patterns specify a single unambiguous match for any given input. These points about backtracking suggest a deeper philosophical difference, which I hope Sergei will say more about, as he likely understands it better than I do. On the whole, his pattern matcher seems to me to assume that solving logic puzzles will be a fairly frequent use of pattern matching; I see pattern matching as a tool for breaking down cases which are already unambiguous.

• The sample implementation of SRFI 257 does early binding, making pattern variables visible within expressions that are embedded within patterns – although the specification seems to say that this is not expected behaviour: it says variables are ‘made available inside ⟨body⟩’, not that they’re also available in e.g. the ⟨fn⟩ clauses of ~? and ~= patterns. Try e.g. (match procedure? ((~and thing (~? thing)) 'early-binding) (_ 'should-never-happen))

  In an inherently non-optimizing design which supports non-linear variables, this may actually make some kind of sense. I reject it in the context of my pattern matcher, but it might make sense in the context of Sergei’s. (If so, though, the SRFI should be amended to make this clear, and the scoping rules tightly defined.)

• Sergei’s SRFI only includes the basic single-value, multiple-clause ‘match’ form: there’s no multiple-value matching form like match-values, nor syntactic sugar like match-let. An efficient match-values form that supports non-linear variables in distinct value patterns can’t easily be implemented from single-value ‘match’, so this is a real loss. Match-let also can’t easily be implemented with correct semantics without a match-values; the more advanced forms, such as match-letrec[*] and match-define also require additional support from the core of a match implementation.

• Sergei’s ‘match’ form returns an unspecified value when it runs out of patterns to try, unlike every other Scheme pattern matcher I am aware of, including my own, which all signal an error in this case.

Finally, two last points on the design of Scheme pattern matchers in general.

First, I would advise anyone thinking of designing any kind of pattern matcher in Scheme to take a look at the archives of the SRFI 204 discussion list. Designing pattern matching syntax and semantics and implementing them correctly are all fraught with difficulty, and many of the kinds of problems that crop up were already raised back then.

Second, if I *were* restricting myself to what is possible with pure syntax-rules – accepting that performance is not going to be a strong point anyway – I would probably take a long look, and do a lot of experimenting with, Jonathan Rees’s idea of making custom patterns properties of procedures, rather than macros. You would lose efficiency, yes, and some syntactic flexibility – but you might get back other kinds of flexibility. (Normally, procedural interfaces are more flexible than syntactic ones in general! It’s surprising that syntactic interfaces have been favoured here.) It’d be worth finding out what lies that way: that kind of pattern match extension is an area that Lispers haven’t really explored since the late 1980s/early 1990s, before the Wright pattern matcher took over. To my knowledge, nobody ever actually publically released a pattern matcher that worked that way.

Best wishes

Daphne