Conflict with hidden names

Question

The following code hangs Mathematica 12.0.0:

D[Log[1 - 1/p^Cos[t]], {t, 4}]
Unprotect[Plus];
Plus[x_?Positive, j_Gap] := 0;
Protect[Plus];
1 + 1
D[Log[1 - 1/p^Cos[t]], {t, 4}]

The weird line 3 is defining how to add numbers to objects with head "Gap", which is a structure I'm defining. (The right side of that line doesn't seem to matter, so I've made it 0 to simplify.) If one only asks for a 3rd derivative, or a fourth derivative of a simpler function, there is no problem.

But here's the surprise (to me): change "Gap" to "gap" or to "Gappe" and the issue disappears. My guess is that somewhere deep inside the trig simplification triggered by this derivative is a variable or function named "Gap", and somehow that's causing problems at the surface for me.

My question is simply this: What did I do wrong? Is this a bug, or is this behavior expected? Do I have to abandon using the head "Gap"? Is there a safer way to overload built-in functions?

Answer 1

First, you should never give Plus a downvalue. Always give your symbol upvalues instead by using TagSetDelayed. Giving such a basic symbol in Mathematica a downvalue is sure to cause problems.

Now, I'm only guessing here, but this is my guess as to what is happening. When you give binary definitions to a Flat, Orderless function like Plus, it can very easily lead to combinatorical explosions, where Mathematica tries lots of different orderings of the arguments to see if the binary rule will fire. I think that's what is happening in your example. For example, if we take the 3rd derivative, and then differentiate partial sums, we see an increase in timing consistent with a combinatorial explosion:

Unprotect[Plus];
Clear[Plus];
Plus[x_?Positive, j_Gap]:=0;
Protect[Plus];
r3 = D[Log[1-1/p^Cos[t]],{t,3}];
D[r3[[;;3]],t];//AbsoluteTiming
D[r3[[;;4]],t];//AbsoluteTiming
D[r3[[;;5]],t];//AbsoluteTiming

{0.033469, Null}

{1.05953, Null}

{29.367, Null}

I didn't have the patience to wait for the 6 term version to finish.

Now, for the hidden conflict question. Since Plus is such an essential function, and it needs to be as fast as possible, I believe that internally Plus will sometimes short circuit checking all possible orderings when an internal bloom filter says it is not needed. In this case, if Gap is absent, then the downvalue can be avoided.

How does this bloom filter work? Basically, the bloom filter does a hash on an expression, and checks if the variable hash is absent. This means that if you choose a variable whose hash is not in the expression, then the code will be fast. If you choose a variable whose hash is in the expression, then the slow, combinatorial explosion causing code will be executed. This is why the code is fast for some variables, but not others.

See this answer for an overview for how this works. The upshot is the following:

With[{e = r3}, IntegerDigits[System`Private`GetContentCode[e], 2, 30]]
IntegerDigits[System`Private`GetContentCode[Gap], 2, 30]
IntegerDigits[System`Private`GetContentCode[gap], 2, 30]
IntegerDigits[System`Private`GetContentCode[Gappe], 2, 30]

{1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}

Notice how Gap has an overlap with r3, while gap and Gappe don't.