Matching problem with long list of list?

Questions
1

I have a function f[zs] and a function fb[zs, base] with a parameter zs that is a list of nonempty lists of integers. The parameter is defined as zs:{{__Integer}…}

For short lists the functions can be called without problem.

When the list gets longer (e.g. about 5000 elements) the parameter match of fb[zs, base] no longer works. I get an error: “General::maxrec: Recursion limit exceeded; positive match might be missed.”.
f[zs] still works.

f[zs] seems to remain working for even very long lists.

Can anybody explain this behavior? Is this a bug within Wolfram or is there a mistake within my coding?

Block[{digits = 8, maxAnz = 5000, f, fb, zs},
 f[zs : {{__Integer} ...}] := {Length[zs]};
 fb[zs : {{__Integer} ...}, base_Integer : 10] := {base, Length[zs]};
 Echo[$RecursionLimit, ".$RecursionLimit: "];
 (* Make zs = List of Lists *)
 zs = Partition[Range[maxAnz*digits], digits];
 Echo[Column[{{digits, Length[zs]}, Short[zs, 7]}], 
  ".{digits,Length[zs]},zs}: "];
 (* Test zs-Pattern within f[zs] *)
 Echo[Short[f[zs], 7], ".f[zs]: "];
 (* Test zs-Pattern within fb[zs,base] *)
 Echo[Short[fb[zs, digits], 7], ".fb[zs,digits]: "];
 (* The List of List - Pattern is ok *)
 Echo[zs = Take[zs, 5], ".zs begin:"];
 Trace[MatchQ[zs, {{__Integer} ...}]]
 ]
2

Weird. No answers, but some observations:

(1) This form works, but assumes that your matrix is rectangular:

fb[stuff_, base_Integer : 10] := {base, Length@stuff} /; MatrixQ[stuff, IntegerQ]

You didn’t explicitly say that it should be rectangular, but your example is. I assume you can replace the condition with a more accurate one for your context. This also “works” without the condition, but then you’re losing your constraints on the first argument.

(2) This also “works”, but doesn’t use your default:

fb[stuff : {{__Integer} ..}, base_Integer] := {base, Length@stuff}

So, it seems very much related to the default value.

(3) It doesn’t help to use Default explicitly:

Default[fb] = 10;
fb[stuff : {{___} ...}, base_.] := {base, Length@stuff}

It works for small arguments, and breaks at 4999.

(4) Default values work without the extra pattern stuff:

Default[fb, 1] = {};
Default[fb, 2] = 10;
fb[stuff_., base_.] := {base, Length@stuff}

But again, you lose your other constraints.

(*) My conclusion is that this seems like a bug. But it’s fascinating that there is some interaction across the argument patterns. It’s also interesting that it breaks at 4999. I don’t see how that’s related to the recursion limit.

3

Thanks, Eric, for your hints and work.

Since my list of lists is rectangular indeed I will use your MatrixQ condition in the form:

f[zs_ /; MatrixQ[zs, IntegerQ]] := {Length[zs]};
fb[zs_ /; MatrixQ[zs, IntegerQ], base_Integer : 10] := {base, Length[zs]};

I will lose only the condition that list entries shall be nonempty list. Which doesn’t matter.

For the original problem: Like you I am now pretty convinced that this kind of interaction between a parameter pattern and the default of another parameter is just a bug within Wolfram Language.

4

I reported the issue to Wolfram Support.

5

Wolfram Support has reproduced and accepted the issue and passed it to the developers.

6

It’s intentional behavior. Pattern matching in some cases uses recursion. There is a brake in place to avoid kernel crashes from subroutine stack exhaustion. A brief history can be found here.

7

I’m curious to know more, but that link doesn’t look right to me. Or it’s not obvious where the relevant discussion starts. Can you check it or give some explanation?

8

I’ll track it down later. Morning coffee and a ten year old iPad…

I should be glad this bit of hardware isn’t a defiant teenager.

Later edit:
I think the link should work now. No idea how that previous one got copied to clipboard. The iPad keeps its secrets.

9

Thanks! The link does work now. There’s not much there about the root cause. I see something about backtracking, which is intriguing. I guess what flummoxed me is that it seems to only happen when one argument is given a default value, which doesn’t intuitively (to me) seem like it should matter all that much. It seems like the argument patterns aren’t independent–somehow it’s the full argument-list-pattern that’s being evaluated at once, maybe?

Anyway, it’s not important, but if you had time to describe the implementation details enough to explain this behavior, I’d find it interesting. Or point to a reference with more details.

10

Eric,

I do not remember those details at all well. Indeed, I have to remind myself how things work any and every time I need to work with pattern matching code (I suppose that holds for pretty much all code I look at).

The rough idea is this. Certain pattern types, such as Blank(Null)Sequence and Repeated(Null), can match things of varying length. These tend to be “hard” cases, and will go into code that relies on recursion to try different possible partial matches. When these patterns are nested this can go into deep recursion.

Some other pattern types can similarly cause trouble. One is Alternatives, since the different possibilities can have vary different partial match features. So again there can be deep recursion.

I realize this is on the vague side of nebulous. It’s not that I do not care to share more detail, so much as I do not want to drag myself back into that code. At least not until the next (mis-)assigned bug report takes me there.

11

Thanks!

12

Hi Daniel, I can’t say that for me your explanations and the link explained much.
What is surprising is that there is interaction between parameter patterns at all. And even between a parameter and the default of another parameter. You would think that the first thing to do is isolate the individual parameters in the function definition and call, and only then would the pattern matching begin.

I’m curious to see what Wolfram Support will answer me.

13

From my Email conversation with Wolfram Support I learned now that your posts here where the official Wolfram development statements concerning my CASE:4955075.

Well, if so, I miss one statement: Considers Wolfram this behavior as a bug being repaired sometimes? Or do we have to live with it?

Thanks Daniel

14

It’s a limitation. Improving on it (by removing the need for recursion) is something I do not know how to do. Hard to say if another developer will find a way in future.

In older versions the example might work. But at 10000 instead of 5000 it would crash the kernel on pretty much any operating system.

15

OK, Daniel. I can live with it. It needs just omitting the default for the other parameters.