23
$\begingroup$

I'm experiencing a strange phenomenon. Here's a (quite artificial) test case:

The following definition work just fine:

f[x___Real]:={x}
g[a_,f[n_Integer]]:={a,n}
SetAttributes[f,Flat]

f[a,f[b,c]]
(*
 --> f[a,b,c]
*)

g[f[1.0],3]
(*
 --> g[{1.},3]
*)

As do the following (in a fresh kernel):

f[x___Real]:={x}
SetAttributes[f,Flat]
g[a_,f[n_Integer]]:={a,n}

f[a,f[b,c]]
(*
 --> f[a,b,c]
*)

g[f[1.0],3]
(*
 --> g[{1.},3]
*)

However, the following (evaluated in a fresh kernel again) hangs on the definition of g:

SetAttributes[f,Flat]
f[x___Real]:={x}
g[a_,f[n_Integer]]:={a,n}

Now I don't see any reason why the definition of g should depend on whether I've first defined f or first set the Flat attribute on it. Can anyone explain the mystery?

PS: If anyone can think of a better title, feel free to change it accordingly.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Using TracePrint[] on your third input in your last bit is rather telling... for that matter, try TracePrint[f[n_Integer]] after your second input and watch the growth from f[n_Integer] to f[{}, n_Integer] to f[{}, {}, n_Integer] to... $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jan 19, 2012 at 18:00
  • 1
    $\begingroup$ On the other hand, if you use f[x__Real] := {x} (i.e. BlankSequence instead of BlankNullSequence), you don't bump into the problem. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jan 19, 2012 at 18:08
  • $\begingroup$ N.B. One doesn't need to do a kernel restart when trying out each code blob. Just precede each code blob with Remove[f, g] for a clean evaluation. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jan 19, 2012 at 18:11
  • 1
    $\begingroup$ If you're going to play around with TracePrint[], you probably would want to lower your value of $IterationLimit to a small integer, say 20. For instance: Block[{$IterationLimit = 20}, TracePrint[f[n_Integer]]]. $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jan 19, 2012 at 18:14
  • $\begingroup$ @J.M.: Actually for my tests I used "Notebook's Default Context → Unique to Each Cell Group" and just started a new section for each test. $\endgroup$
    – celtschk
    Commented Jan 19, 2012 at 18:17

2 Answers 2

Reset to default
19
$\begingroup$

Ok, I'm going to try to explain my best conjuecture as to how this happens, and don't even try to answer why.

There are three reasons for this behaviour:

SetDelayed left hand side evaluation

As others have mentioned, even though SetDelayed has attributes that indicate it holds the lhs, it does evaluate the head and the arguments of it, just not the expression as a whole.

How the Attribute Flat affects the final evaluation of the expression

Ok, so the evaluator is now trying to transform the expression (with head Flat) as a whole. It has already evaluated the head and arguments, or not, as it was supposed to. It has already flattened everything. It has already tried the UpValues, nothing fit.

Now it checks, in order, one DownValue at a time:

1* If it matches the expression as is, we're good. It applies the transformation rule.

2* If it doesn't, then it modifies the expression, gathering arguments. Tries combinations of head[prev__, head[some__], aft__] with args being different subsequences of arguments taken from expression. If some subexpression fits the pattern, it transforms it and restarts the process.

Example

In[27]:= ClearAll[f];
SetAttributes[f, {Flat, HoldAll}];
f[b, c] := 8;
f[a, b, c, d]

Out[30]= f[a, 8, d]

3* If it doesn't then IT TRIES TO MATCH THE EXPRESSION head[] WITH NO ARGUMENTS. If it succeeds, then IT PREPENDS THE UNEVALUATED TRANSFORMATION OF head[] TO THE EXPRESSION AND RESTARTS THE EVALUATION PROCESS

Some examples:

In[18]:= ClearAll[f1, f2, f3, f4];
SetAttributes[{f1, f2, f3, f4}, Flat];
f1[2, 2, 2, 2] := "Yeahh";
f1[2] = "bo";
f1[] := (Print["here"]; 2);

f2[2] = "bo";
f2[2, 2, 2, 2] := "Yeahh";
f2[] := (Print["here"]; 2);

f3[] := (Print["here"]; 2);
f3[2, 2, 2, 2] := "Yeahh";
f3[2] = "bo";

f4[2, 2, 2, 2] := "Yeahh";
f4[] := (Print["here"]; 2);
f4[2] = "bo";

In[32]:= Scan[Print[DownValues[#][[All, 1]]] &, {f1, f2, f3, f4}]

During evaluation of In[32]:= {HoldPattern[f1[2,2,2,2]],HoldPattern[f1[2]],HoldPattern[f1[]]}

During evaluation of In[32]:= {HoldPattern[f2[2]],HoldPattern[f2[2,2,2,2]],HoldPattern[f2[]]}

During evaluation of In[32]:= {HoldPattern[f3[]],HoldPattern[f3[2,2,2,2]],HoldPattern[f3[2]]}

During evaluation of In[32]:= {HoldPattern[f4[2,2,2,2]],HoldPattern[f4[]],HoldPattern[f4[2]]}

In[33]:= f1[2]
f2[2]
f4[2]

Out[33]= "bo"

Out[34]= "bo"

During evaluation of In[33]:= here

During evaluation of In[33]:= here

During evaluation of In[33]:= here

Out[35]= "Yeahh"

So, in our case, when the expression f[n_Integer] fails to match the pattern f[x___Real], it evaluates f[] to get {}, and tries matching f[{}, f[n_Integer]], which doesn't match so it loops infinately.

If this is a case, then a good tip would be to always take care that all definitions of Flat symbols that match without arguments should go last...

How the order of setting attributes matter

Flat affects evaluation in 3 different moments:

  1. After evaluating the arguments of an expression, it automatically flattens it's head
  2. Changes the pattern-matching (more on this later)
  3. Changes what the evaluator does when an expression didn't match a DownValue

The 1.th and 2.th part seems to only care about Flat being set at the time of evaluation. But 3., it seems that that peculiar behaviour (see 2* and 3* above) of the evaluator trying to match the no-arguments version is PER DOWNVALUE, and it seems to me that, at the time the DownValue is set, MMA records somewhere if Flat was or not set at the time.

So, the previous f3 example that looped infinitely wouldn't loop infinitely if the no argument version was defined while the Flat attribute wasn't set.

ClearAll[f3];
f3[] := (Print["here"]; 2);
SetAttributes[{f1, f2, f3, f4}, Flat];
f3[2, 2, 2, 2] := "Yeahh";
f3[2] = "bo";

In[65]:= f3[2]

Out[65]= "bo"

The previous f4 example would also differ. You don't even need to set the Flat attribute back up in the end for the behaviour to remain

In[66]:= ClearAll[f4];
SetAttributes[f4, Flat];
f4[2, 2, 2, 2] := "Yeahh";
ClearAttributes[f4, Flat];
f4[] := (Print["here"]; 2);
SetAttributes[f4, Flat];
f4[2] = "bo";

In[73]:= f4[2]

Out[73]= "bo"

The same actually applies to (see 2*) the evaluator testing the different combinations of gathered arguments... So

In[37]:= ClearAll[f];
SetAttributes[f, {Flat, HoldAll}];
f[b, c] := 8;
ClearAttributes[f, Flat];
f[e, g] := 9;
f[a, b, c, d]
f[a, e, g, d]

Out[42]= f[a, 8, d]

Out[43]= f[a, e, g, d]

Extra for less incompleteness

Flat also affects the pattern matcher. When the pattern matcher finds itself comparing arguments of an expression whose head (let's call it head) has attribute Flat, it behaves differently: patterns of length one (_, r_, Conditions, PatternTests) trigger the pattern matcher to automatically wrap a head around the respective arguments of the expression so both the expression and the pattern have the same number of arguments (could also be a single argument, but it never leaves it as is. Don't know the purpose). In cases where more than one option is possible due to having __s as arguments, it just starts trying one way and if it doesn't match, tries the next).

In[47]:= ClearAll[f]; SetAttributes[f, {Flat, HoldAllComplete}];
         Cases[Hold@f[1], Hold@f[i_] :> Hold[i], {0}]
         Cases[Hold@f[1, 2, 3, 4], Hold@f[1, i_, 4] :> Hold[i], {0}]
         Cases[Hold@f[1, 2, 3, 4], Hold@f[i_, __] :> Hold[i], {0}]
         Cases[Hold@f[1, 2, 3, 4], 
            Hold@f[i_, j__ /; Length[{j}] === 2] :> Hold[i], {0}]

Out[48]= {Hold[f[1]]}

Out[49]= {Hold[f[2, 3]]}

Out[50]= {Hold[f[1]]}

Out[51]= {Hold[f[1, 2]]}

Conclusion

The problem is: Will the evaluation of f[n_Integer] in our definition of g trigger an infinite loop or not? It does evaluate because of the peculiar evaluation rules of Set functions. f[n_Integer] doesn't match the only DownValue it has at the time: f[x___Real]. In the 2 cases that work, that DownValue wasn't defined while f had the attribute Flat, so it just returns unevaluated. However, in the third case, the DownValue was defined while the symbol had Flat. So after failing, it tries to evaluate f[], returning {} and now reevaluates the whole expression as f[{}, n_Integer]

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks for this great post. It's really a good piece of reverse engineering. Since it finally completely answers in detail my question, I've moved the accepted answer to yours. $\endgroup$
    – celtschk
    Commented Jan 27, 2012 at 18:27
  • $\begingroup$ Totally agree with @celtschk. Great piece of work! I actually never completely understood this topic, and your investigation added some missing bits, thanks a lot. $\endgroup$
    – Leonid Shifrin
    Commented Jan 27, 2012 at 18:33
  • $\begingroup$ This post was made right after the confusion of testing and testing, and it is more confusing than necessary. I should edit it some time $\endgroup$
    – Rojo
    Commented May 12, 2013 at 16:45
15
$\begingroup$

Generally, a good advice would be to set attributes before giving definitions to the function.

The difference in your case is caused by the effect that I call evaluation during assignments. There was a question devoted to it in the past, where I contributed an answer with a detailed analysis of the problem. I also mentioned this problem in my recent answer. The bottom line is that functions generally do evaluate inside the l.h.s. of SetDelayed, using those definitions that they already have by that moment.

As to why things hang, I can offer some analysis but no explanation. Let's trace it:

ClearAll[f, g];
SetAttributes[f, {Flat}]
f[x___Real] := (If[n++ > 5, Throw[$Failed]])

Now, 

In[150]:= Block[{n=0},Trace[Catch@f[1],_f]]
Out[150]= 
{{f[1],f[If[n++>5,Throw[$Failed]],1],f[Null,1],
f[If[n++>5,Throw[$Failed]],Null,1],f[Null,Null,1],f[If[n++>5,Throw[$Failed]],Null,Null,1],
f[Null,Null,Null,1],f[If[n++>5,Throw[$Failed]],Null,Null,Null,1],
f[Null,Null,Null,Null,1],f[If[n++>5,Throw[$Failed]],Null,Null,Null,Null,1],
f[Null,Null,Null,Null,Null,1],f[If[n++>5,Throw[$Failed]],Null,Null,Null,Null,Null,1],
f[Null,Null,Null,Null,Null,Null,1],
f[If[n++>5,Throw[$Failed]],Null,Null,Null,Null,Null,Null,1]}}

You can see that the function is applied as f[arg] -> f[arg, result-of-previous-computation-of-f], and since your pattern allows for any number of arguments, it never stops. This may be a bug, or may be I do not understand Flat attribute sufficiently well.

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ @J.M. Good point about TracePrint! I forgot about this possibility. $\endgroup$
    – Leonid Shifrin
    Commented Jan 19, 2012 at 18:19
  • 1
    $\begingroup$ I think it's more the combination of Flat and BlankNullSequence that does the function in... $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Jan 19, 2012 at 18:20
  • $\begingroup$ @J.M. Yes, but the effect is observed during the evaluation of an assignment for g, and that happens because f inside of the l.h.s. evaluates. $\endgroup$
    – Leonid Shifrin
    Commented Jan 19, 2012 at 18:26
  • 3
    $\begingroup$ +1 TimeConstrained is also useful in tracing situations such as this. For example, try TracePrint[TimeConstrained[f[n_Integer], 0.005]] using the original definition of f. Adjust the constant 0.005 to match the speed of your CPU. $\endgroup$
    – WReach
    Commented Jan 19, 2012 at 18:53
  • 2
    $\begingroup$ @WReach Thanks for the hint ( I seldom use TracePrint and was unaware of this trick either), and also for the upvote. It's good that you are here. Many questions here would benefit from your answers. $\endgroup$
    – Leonid Shifrin
    Commented Jan 19, 2012 at 19:01

Your Answer

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

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