function construction - SetAttributes[f,Flat]: Why the order dependence?

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.

Answer

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]