What makes a pattern more general?

Question

This is a rewording of the question. The original post is below.

How come that a pattern for an expression with a specific head is not more specific than a pattern for an expression with a generic head?

The code below provides the example. The original wording of the question includes references to "evaluation procedure" in an effort to make the case that the order in which Mathematica tried the patterns is not what I expected.

---

According to The Ordering of Definitions:

[Mathematica] follows the principle of trying to put more general definitions after more specific ones.

Also, from The Standard Evaluation Procedure

In the standard evaluation procedure, [Mathematica] first evaluates the head of an expression and then evaluates each element of the expression …

With that in mind, consider the following code:

Clear[h];
h /: _[___, _h, ___] := "Pattern 2";
h /: f[_h, ___] := "Pattern 1";
f[h[1]]
(*"Pattern 2"*)

In my understanding of the two quotes above, the output should be "Pattern 1". My reasoning is that when patterns are evaluated, their heads are evaluated first and f is less general than _.

From this answer, I gather that those two patterns are incomparable:

Internal`ComparePatterns[_[___, _h, ___], f[_h, ___]]
(*Incomparable*)

That explains the "Pattern 2" outcome. I need help to catch the error in my reasoning though.

---

Update to address a comment.

The answers in a previous question suggest

[the algorithm used internally for pattern ordering] might forever remain an implementation secret, like the 'canonical order'.

Even if that is true, that secret implementation should conform to the published documents. Hence my question is whether there are any flaws in my reasoning. For example, it might be possible that pattern evaluation does not follow The Standard Evaluation Procedure. If so, is there some documentation about it? If there is no error in my previous statement

when patterns are evaluated, their heads are evaluated first and f is less general than _

does the code above show a bug?

Answer 1

From this very nice answer by Leonid Shifrin:

The common statement you can encounter is that "UpValues are applied before DownValues". This must be clarified: for f[g[args]] it means that UpValues for g are applied before DownValues for f, provided that the evaluation process already went all they way "down" to innermost parts, and then went back "up".

In the OP's example, the upvalues for h are applied before any downvalues of f (of which none are given).

The other factor, which OP has already figured out, is that because the patterns are incomparable, they are applied in the order made. Reverse the definitions and you get "Pattern 1":

ClearAll[hh];
hh /: ff[_hh, ___] := "Pattern 1";
hh /: _[___, _hh, ___] := "Pattern 2";
ff[hh[1]]
(*  "Pattern 1"  *)

The ordering of the upvalues can been seen by using UpValues:

UpValues[hh]
(*
  {HoldPattern[ff[_hh, ___]] :> "Pattern 1", 
   HoldPattern[_[___, _hh, ___]] :> "Pattern 2"}
*) 

Finally, somewhat of an aside. The OP quotes a part of "The Standard Evaluation Procedure" about evaluating the head first. This means in f[h[1]] that f itself is evaluated. But the upvalues for h will still be applied before the downvalues for f. Evaluating the head first makes a difference when the head itself evaluates to a different expression. The effect of this rule can be seen in the following:

g = f;
g[x___] := Length@{x};
g[h[1]]
(*  "Pattern 2"  *)

If you use Trace, you can see the steps {{g, f}, f[h[1]], "Pattern 2"}; but Trace does not tell you which rule is applied.

Note the definition g[x___] defined a downvalue for f, not for g (see Why is the first argument of the SetDelayed evaluated? and the SO Q&A Unwanted evaluation in assignments in Mathematica):

DownValues[f]
DownValues[g]
(*
  {HoldPattern[f[x___]] :> Length[{x}]}
  {}
*)

OwnValues[g]
(*  {HoldPattern[g] :> f}  *)

Answer 2

The example at hand

One part of the confusion seems to arise from the fact that the patterns that are compared differ in two aspects: The additional ___ and the head (f vs _). Let us first consider two separate examples, where the definitions only differ in one aspect.

Additional ___

We see the same behavior (i.e. patterns are incomparable) for the following simpler function definition (no upvalues and a fixed head):

Clear@f
f[___, 1, ___] := 1
f[1, ___] := 2
f[1]
(* 1 *)

Clear@f
f[1, ___] := 2
f[___, 1, ___] := 1
f[1]
(* 2 *)

This demonstrates (without having to rely on any undocumented function) that MMA deems the patterns incomparable. I have no idea why this particular example behaves the way it does, as it seems rather trivial to decide which one is more general…

Head f vs _

To show that the issue has nothing to do with f vs _, consider the following example:

Clear@h
h /: f[_h, ___] := 1
h /: _[_h, ___] := 2
f[h[1]]
(* 1 *)

Clear@h
h /: _[_h, ___] := 2
h /: f[_h, ___] := 1
f[h[1]]
(* 1 *)

As can be seen, the pattern with head f is correctly identified as more specific.

So the question "why a pattern with f as the head is not more specific than a pattern with any head" is based on a false premise.

"The ordering of patterns" vs. "The standard evaluation procedure"

Second, I think you're confusing the ordering of definitions with the evaluation procedure: When you define a new rule for a function, the rule is inserted into the down/up-values of the associated symbol according to it's specificity. This is what the linked question is all about - i.e. how MMA decides where to insert a given rule. This has nothing to do with the second statement, "heads are evaluated first". This only affects how an expression is evaluated, given the rules that are already present at this point. Consider the following example:

h = Hold
h[Print@1]
(* Hold[Print[1]] *)

As you can see, the head of the expression, h is first evaluated to Hold, before the Print@1 expression is evaluated.

So, to summarize:

• When a new rule for a symbol is defined, the left and right side of the assignment are first evaluated as appropriate (in most cases this means not at all). The rule is then inserted according to its specificity.
• When an expression is evaluated, the head is evaluated first, before any of the arguments. For h[a][b], this means h, then a, then h[a], then b, then h[a][b].