What is the distinction between DownValues, UpValues, SubValues, and OwnValues?
In Mathematica, all functions are really just patterns, and there are different kinds of those.
Let's start with OwnValues, which is the pattern type of a variable as you know it from other programming languages. The symbol having the OwnValue has, as the name suggests, intrinsic, "own", value.
In[1] := a = 2; OwnValues[a]
Out[1] := {HoldPattern[a] :> 2}
A DownValue is defined when the variable itself does not have a meaning, but can get one when combined with the proper arguments. This is the case for the most function definitions
f[x_] := x^2
This defines a pattern for f specifying that each time f[...] is encountered, it is to be replaced by ...^2. This pattern is meaningless if there is a lonely f,
In[2] := f
Out[2] := f
However, when encountered with an argument downwards (i.e. down the internal structure of the command you entered), the pattern applies,
In[3] := f[b]
Out[3] := b^2
You can see the generated rule using
In[4] := DownValues[f]
Out[4] := {HoldPattern[f[x_]] :> x^2}
The next type of pattern concerns UpValues. Sometimes, it's convenient not to associate the rule to the outermost symbol. For example, you may want to have a symbol whose value is 2 when it has a subscript of 1, for example to define a special case in a sequence. This would be entered as follows:
c /: Subscript[c, 1] := 2
If the symbol c is encountered, neither of the discussed patterns apply. c on its own has no own hence no OwnValue, and looking down the command tree of c when seeing Subscript[c,1] yields nothing, since c is already on an outermost branch. An UpValue solves this problem: a symbol having an UpValue defines a pattern where not only the children, but also the parents are to be investigated, i.e. Mathematica has to look up the command tree to see whether the pattern is to be applied.
In[5] := UpValues[c]
Out[5] := {HoldPattern[Subscript[c, 1]] :> 2}
The last command is SubValues, which is used for definitions of the type
d[e][f] = x;
This defines neither an OwnValue nor a DownValue for d, since it does not really define the value for the atomic object d itself, but for d[e], which is a composite. Read the definition above as (d[e])[f]=x.
In[6] := SubValues[d]
Out[6] := {HoldPattern[d[e][f]] :> x}
(Intuitively, an OwnValue for d[e] is created, however calling for this results in an error, i.e. OwnValues[d[e]] creates Argument d[e] at position 1 is expected to be a symbol.)
Preamble
In addition to the differences between these global rules reflected in the patterns for which assignment operators put the global rule into one or another ...Value, there is another, and IMO,no less important difference, and that is in how these rules are used in the evaluation sequence.
Evaluation: OwnValues
The OwnValues represent symbols themselves, and therefore they are applied when symbols are evaluated. If these symbols are atomic elements inside some expression, and evaluation comes to them, they are (normally) replaced with the r.h.s. of their OwnValues. The more interesting situation is when the symbols are heads of some normal expressions. In this case, since heads are evaluated very early in the evaluation sequence, these symbols are also replaced with what their OwnValues instruct, but now as heads.
This has several consequences. Here is one example:
In[75]:=
ClearAll[f,h];
SetAttributes[f,{Orderless,SequenceHold}];
f=h;
f[5,4,3,2,1]
Out[78]= h[5,4,3,2,1]
In[79]:= f[Sequence[1,2,3]]
Out[79]= h[1,2,3]
As you can see, none of the Attributes assigned to f actually had a chance to play, since f was replaced by h before the attributes were even considered by the evaluator. The same will happen when we add some definitions (as DownValues, UpValues or SubValues):
In[106]:=
g[x_]:=x^2;
g=h;
g[5]
Out[108]= h[5]
Once again, these definitions had no chance to execute.
These cases may seem contrived, and indeed they do not happen very often as results of a deliberate coding, but they can quite often happen due to a mistake, and then are hard to debug. One very relevant discussion is here. To complete this part, let me mention another very insidious case. Let us just take the last example and reverse the order in which we were creating definitions:
In[109]:= ClearAll[g,h]
g=h;
g[x_]:=x^2;
g[5]
Out[112]= 25
Somewhat miraculously, the code worked, seemingly contradicting my previous statements. But let us look closer:
?g
Global`g
g=h
is all right, but this
?h
Global`h
h[x_]:=x^2
may be a surprise. This is an example of evaluation during assigments. A more complete discussion can be found e.g. here. This is just another pitfall to watch out for.
Evaluation: DownValues vs SubValues
It is useful to know that DownValues are applied before SubValues. Therefore, here we get:
ClearAll[f];
f[1][x_]:=x^2;
f[n_]:=n;
In[118]:= f[1][3]
Out[118]= 1[3]
Had I reversed the order of definitions, and we'd have got this:
ClearAll[f];
f[n_]:=n;
f[1][x_]:=x^2;
SetDelayed::write: Tag Integer in 1[x_] is Protected. >>
This is another case of evaluation during an assigment: the first definition for f evaluated inside SetDelayed when we attempted to create the second one.
Another important difference: functions defined via DownValues can hold all their arguments if needed, through the HoldAll or HoldAllComplete attributes. Functions defined with SubValues, however, can only normally hold the "innermost" group of arguments:
In[125]:= ClearAll[g];
SetAttributes[g,HoldAll];
g[x_][y_]:={Head[Unevaluated[x]],Head[Unevaluated[y]]}
In[128]:= g[Print[1]][Print[2]]
During evaluation of In[128]:= 2
Out[128]= {Print,Symbol}
The only workaround I am aware of, when such construct is needed, is this:
In[129]:= ClearAll[g];
SetAttributes[g,HoldAll];
g[x_]:=Function[y,{Head[Unevaluated[x]],Head[Unevaluated[y]]},HoldAll]
In[132]:= g[Print[1]][Print[2]]
Out[132]= {Print,Print}
Similar situation holds for some other attributes, e.g. Listable. This topic is discussed in more detail e.g. here
DownValues vs UpValues: System-wide changes vs. locality
There are several important ways in which UpValues are different from DownValues. One very important aspect is that they allow you to "softly" overload some system functions only on certain symbols. The importance of this can not be emphasized enough - this makes the effect of your code local, and drastically reduces the chances that your code can globally interact and affect some other part of the system or other piece of user-defined code, unlike when you Unprotect system symbols and add some DownValues to them.
In addition to being safe and local, such redefinitions may also be quite general, if one uses constructs like yourSymbol/:f_[_yourSymbol,rest___]:=.... These should be used with care, but can sometimes give very concise and simple solutions. Here is one example where one code can be used to "overload" several system functions at once, giving them additional non-trivial functionality.
DownValues vs UpValues: Order of evaluation
The next point is evaluation. 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 particular, it does not mean that UpValues for g will be applied before DownValues for g - if g[args] can evaluate inside f because g has appropriate DownValues, it will (unless f has one of the Hold-attributes), and the presence of UpValues won't prevent that, because (for standard evaluation), evaluation of g[args] happens before the evaluation of f[result-of-evaluation-of g[args]]. For example, here:
In[133]:=
ClearAll[f, g];
f[x_] := x^2;
g /: f[g[x_]] := Sin[g[x]];
g[x_] := Cos[x];
In[137]:= f[g[y]]
Out[137]= Cos[y]^2
The UpValues for g had no chance to apply, since g[y] is transformed into Cos[y] at the previous evaluation step. The situation would be different for non-standard evaluation - either if we give f attributes HoldAll or HoldFirst, or if we wrap g[y] in Unevaluated - in both cases we give the evaluator the instruction to skip the evaluation of g[y]:
In[138]:= f[Unevaluated[g[y]]]
Out[138]= Sin[Cos[y]]
DownValues vs UpValues: Hold-attributes
This one is related to the previous point: one should be aware that search for UpValues is performed even inside heads with Hold- attributes, and therefore, UpValue-based definitions may evaluate even when similarly-looking DownValue - based ones won't. Example:
In[139]:= ClearAll[f,ff];
f[x_]:=Print["Evaluated"];
ff/:h_[ff[x_]]:=Print["Evaluated"];
In[142]:= Hold[f[1]]
Out[142]= Hold[f[1]]
In[143]:= Hold[ff[1]]
During evaluation of In[143]:= Evaluated
If one wants to absolutely prevent the search for UpValues, one should give a function the HoldAllComplete attribute. For example:
In[144]:= {HoldComplete[f[1]],HoldComplete[ff[1]]}
Out[144]= {HoldComplete[f[1]],HoldComplete[ff[1]]}
Summary
I tried to outline and illustrate several technical points which pop up quite frequently in practice and can be frustrating at first. My main message is that a huge difference between different kinds of rules is induced by the way they are used in the main evaluation sequence. This difference may not be immediately apparent, but it affects all aspects of how these rules are used in practice.