4
$\begingroup$

This result is unexpected:

Trace[MatchQ[{7}, {_?NumberQ, __}], NumberQ] (* ->  {{NumberQ[7], True}} *)

Why evaluate NumberQ if the pattern can't conceivably match? What kind of side-effect might change the expression arity during pattern-matching?

Precisely, due to the unbound side-effects and for performance reasons, I would have thought that the matcher would labor very hard to avoid invoking the evaluator.

Note that other cases are not surprising:

Trace[MatchQ[{7}, {_?NumberQ, _}], NumberQ] (* -> {} *)

Trace[MatchQ[{7}, {_?NumberQ, ___}], NumberQ] (* ->  {{NumberQ[7], True}} *)

The combination of a constraint and BlankSequence seems to make the pattern-matcher overly suspicious. So, "a list of two expressions, first one a number" bypasses the evaluator; "a list of two or more expressions, first one a number" triggers the evaluation of the restriction.

Optimization of pattern-matching is unresolved in general. In the context of expressions in the form head + n parts, however, trying to calculate the lower bound of n for the class of expressions represented by a pattern strikes me as one of the obvious problems to focus on.

Given the experience of these last weeks, though, the struggle between my intuition and Mathematica is always won by the latter. What am I missing, then?

Update:

Mr.Wizard and Leonid Shifrin discussed a few years ago about the uneasy relation between the evaluator and the pattern-matcher.

$\endgroup$
7
  • $\begingroup$ Which Mathematica are you using? In Mathematica 9.0.1 on Windows I get {} for Trace[MatchQ[{7}, {_?OddQ, __}], NumberQ] $\endgroup$ May 10, 2014 at 19:31
  • $\begingroup$ Mathematica 9.0.1.0/Mac OSX 10.9.2 Well, a Mac bug was last in my list of possible explanations. Can anyone else reproduce the issue? $\endgroup$
    – Fallible
    May 10, 2014 at 19:40
  • $\begingroup$ FWIW, I got {} in both V9.0.0 and the development version (Mac OS X 10.7.5). So it must've been a bug in 9.0.1. $\endgroup$ May 10, 2014 at 23:10
  • $\begingroup$ There is an error in the question that may be confusing people. The first line of code should be Trace[MatchQ[{7}, {_?NumberQ, __}], NumberQ], not Trace[MatchQ[{7}, {_?OddQ, __}], NumberQ]. I corrected this in the question. $\endgroup$ May 11, 2014 at 1:22
  • $\begingroup$ I also corrected a BlankSequence/BlankNullSequence confusion. $\endgroup$ May 11, 2014 at 1:27

1 Answer 1

3
$\begingroup$

This is closely related to my own questions posted a few years ago on Stack Overflow:

I still am not convinced that some of these patterns could not be better handled but I have come to accept that such things are not likely to change. Although it can be argued that such methods are "perverse" it can fairly easily be demonstrated that such side-effects can be used. Consider:

i = 0;

count[x_] := (If[x > 0, i++]; True)

Cases[{{1}, {-3}, {2}, {0, 4}}, {_?count, __}, ∞]

i
{{0, 4}}

2

This counts the number of (sub)lists that start with a positive number at the same time as a different match is returned by Cases. Again, I would try to avoid such methods myself, but since these methods have been possible changing the language now could have unintended consequences. At first it might seem that NumberQ is safe from such side-effects, but the language allows its redefinition with e.g. Block so all bets are off.

I'm afraid such changes might only appear, if ever, in a "reboot" of the language; a kind of "Wolfram Language 2.0" I suppose. Sadly I think such things are not a priority to the developers, but I do hope to some day see a smaller, cleaner, and faster core language implemented, with a highly optimized pattern matcher, JIT compilation etc.

As a more realistic alternative perhaps it would be possible to introduce a new Head that affects pattern matching (much as HoldPattern or Verbatim do now) that would declare a pattern to be "pure" and without side-effects, which would trigger additional optimizations. Nevertheless having to use this Head every time you wanted optimal behavior for patterns that do not involve side effects would seem very clumsy.

$\endgroup$
4
  • $\begingroup$ When I hit these issues, I recalled having read something related some days ago, but forgot to check the "other" ME. My notes are spotty yet. I'm sorry, will edit the question. $\endgroup$
    – Fallible
    May 11, 2014 at 16:10
  • $\begingroup$ Yes, the law of unintended consequences is unforgiving. Your example is a neat example of side-effects. What I don't really understand is why {_?count, __} and not {_?count, _}. Why "one or more" triggers the evaluator, and "one" not. If Leonid's right (and I think he is), Blank[] should also evaluates the constraint. $\endgroup$
    – Fallible
    May 11, 2014 at 16:11
  • $\begingroup$ @Fallible Actually I missed that part of your question. I don't know; it does seem inconsistent but I am hesitant to label it a bug without further consideration. $\endgroup$
    – Mr.Wizard
    May 11, 2014 at 16:29
  • 2
    $\begingroup$ Another point is that it's only the Blank*Sequence forms that show inconsistent behavior. If Repeated is used, everything is fine. So, although you certainly have a point that someone might have used this productively in the past, I would really hope that nobody chose such a perverse misfeature as a critical part of their implementation. Anyway, WRI haven't been too coy in changing things where judged necessary, so I wonder how much of a motivation this really is for them. $\endgroup$ May 12, 2014 at 0:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.