7
$\begingroup$

So, I've come across something strange, and wanted to get a deeper understanding of what was going on. Consider the following code:

f[a : {{__}..}, k_ : 0] := 1

a = Table[Table[0, {5}], {10000}]

f[a, 2]

So, f takes a list of lists and a single optional expression, which can take the default value 0. This should obviously give 1, right? After all, the arguments seem ok: MatchQ[a, {{__}..}] gives True, and even MatchQ[{a, 2}, {{{__}..}, _}] gives True. More closely, even,

MatchQ[{a, 2}, {{{__}..}, _ | PatternSequence[] }]

gives True.

However, instead of producing 1, f[a, 2] gives an error message "General::maxrec: Recursion limit exceeded; positive match might be missed." and does not evaluate further.

This behavior is also present when defining Default[f]. And, indeed, as soon as we use the Optional pattern in MatchQ[{a,2}, {{__}..}, k_:0}], MatchQ breaks down and gives the same error message as f does. But it can be avoided by removing the default value and providing it in a different (but still definitional) way, e.g.

(* Works: *)

f1[a : {{__}..}] := f1[a : {{__}..}, 0]

f1[a : {{__}..}, k_] := 1

(Also, it doesn't happen with the shallower pattern a : {__}.)

Now, I'm not the first person to notice this behavior and ask about it here. The answer there says it was an intentional change, and I understand there were probably good reasons—I'm not asking for the rationale, or how to change it. But this is not a duplicate question (at least not to that one), because I'm trying to figure something that wasn't asked there:

Why does the Optional pattern, e.g. k_:0, put a recursion limit on matching the pattern occurring before it? Why does it do so when apparently equivalent pattern matchings (such as k:(_ | PatternSequence[]), the alternative implementation of a default value for f, or a match made in isolation) don't?

Note: A previous version of this question asked why the behavior of pattern matching for function definitions didn't agree with the behavior of pattern matching for MatchQ, until @WReach pointed out in the comments that they do, in fact, agree! I simply wasn't using the same pattern verbatim to check.

Possibly related question: the linked answer says something about "dynamic backtracking"; what is that, and is that somehow present for Optional matching but not the other working matchings shown here?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ In V12.2 MatchQ[{a,2}, {a:{{__}..}, k_:0}] fails in the same way as the function definition and also succeeds if we drop the optional argument value. So (in 12.2 at least) there is no essential difference between MatchQ and a definition. They both also succeed if we SetSystemOptions["MaxPatternMatchRecursion"->30005]. So perhaps the question reduces to: why does adding a default value for the second argument cause the pattern matcher to start back-tracking in the deeper levels of the first argument? $\endgroup$
    – WReach
    Commented Mar 2, 2021 at 6:03
  • $\begingroup$ Its only a guess, but perhaps the presence of the default value causes the pattern matcher to fall back from an optimized special case to a general purpose algorithm. Variable-length sequences complicate pattern-matching at the best of times, so maybe the presence of default values or other less common patterns cause the matcher to resort to brute force recursive matching. $\endgroup$
    – WReach
    Commented Mar 2, 2021 at 6:37
  • 1
    $\begingroup$ @DanielHuber It depends on the table size because the pattern matcher uses a recursive back-tracking algorithm and the recursion depth it can hit depends on that table size. $\endgroup$
    – Daniel Lichtblau
    Commented Mar 2, 2021 at 20:36
  • 1
    $\begingroup$ I'm not sure offhand. It could be a missed optimization in the pattern matching code internals. I'm not convinced the alternative is exactly equivalent though, since it does not provide a default value. (This might or might not be relevant to whether there is a missed optimization.) $\endgroup$
    – Daniel Lichtblau
    Commented Mar 3, 2021 at 15:49
  • 2
    $\begingroup$ At a low level it works by magic, like most of the pattern matcher. (I thought everyone knew that.) $\endgroup$
    – Daniel Lichtblau
    Commented Mar 4, 2021 at 15:03

0

Reset to default

Your Answer

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