11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ you might consider using TagSetDelayed instead of making changes to Plus: e.g., Gap /: Plus[x_?Positive, Gap[___]] := 0 $\endgroup$ – kglr Sep 20 at 18:02
  • 1
    $\begingroup$ btw Names["*`Gap"] gives {"ComputationalGeometry`Dump`Gap"} $\endgroup$ – kglr Sep 20 at 18:05
  • 1
    $\begingroup$ Remember how lots of times you see someone write something like: "In Mathematica built-in Symbols start with capital letters. Therefore it is accepted practice to not start user created symbol names with capital letters."? You have found another reason. $\endgroup$ – bill s Sep 20 at 18:27
  • $\begingroup$ Changing "Gap" to "gap12" leads to the same problem. It is not about capitalization. $\endgroup$ – Kevin O'Bryant Sep 20 at 20:06
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is the spelling of "Gap" relevant? $\endgroup$ – Kevin O'Bryant Sep 20 at 19:35
  • 2
    $\begingroup$ @KevinO'Bryant Hopefully my update clarifies things. $\endgroup$ – Carl Woll Sep 20 at 19:52
  • 1
    $\begingroup$ Indeed, using "gap12" (which has the same hash as "Gap") gives the same problem. Thanks! $\endgroup$ – Kevin O'Bryant Sep 20 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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