Is Function broken is this example?

Question

This program

f[x_] := g[Function[a, x]];
g[fn_] := Module[{h}, h[a_] := fn[a]; h[0]];
f[999]

returns

Function[0, 999][0]

but if the Function argument name in the definition of f is changed from a to b then it returns

999

This difference was mentioned as a Wolfram language bug in this post and also this other one.

Is it really?

Answer 1

The Details section of the documentation for Function states:

Function is analogous to λ in LISP or formal logic.

Now this is not phrased as an iron-clad specification, so if Mathematica departs from the semantics of the lambda calculus it is in the eye of the beholder whether this is a bug or not.

I think it is a reasonable expectation that Function would take care to avoid incidental variable name collisions during function application (using so-called α-conversion from the lambda calculus). And so it does, but unfortunately not always.

Example of Unexpected Behaviour

We will use a smaller example to simplify the traces:

ClearAll[f, g, h]

f[fn_] := {1} /. {b_} :> fn[b]
g[x_] := a |-> a + x
h[x_] := b |-> b + x

The key point here is that we have separate functions with local scopes two of which happen to use the same local variable name b.

f[g[10]] works as expected:

f[g[10]]
(* 11 *)

... but f[h[10]] fails with an error because of a name collision between the purportedly local variables both named b:

f[h[10]]

Analysis

Let's dig in. If we examine the output of h[10] we can see that Mathematica has correctly identified the risk of potential name collision between the function argument b and an externally supplied value for it:

h[10]
(* Function[b$, b$ + 10] *)

To address this risk, it has generated a fresh variable named b$.

Now, let's take look at the trace of f[x]:

f[x] // Trace // Column

Again, Mathematica has correctly identified that the name b from the left-hand side of the replacement rule might conflict with a symbol from the externally-supplied right-hand side. So again it has generated a fresh name... b$.

We can see where this is going. The strategy for generating fresh names is weak. In certain circumstances, the fresh names are not "fresh" enough and can still conflict. Indeed, we have contrived such a circumstance:

f[h[10]] // Trace // Column

Had Mathematica used the fresh name strategy employed by Module, then we would have had variables with names like b$1234 and b$5678 and no such conflict would have occurred.

All of this unexpected behaviour can be avoided if we use slot notation instead of named variables:

h[x_] := # + x &
f[h[10]]
(* 11 *)

Compiling a function would also enforce local variable scope.

Similar Issues Elsewhere

There are other circumstances in which named function arguments do not play well with certain features, for example With:

ClearAll[f]

f = expr |-> With[{x = 1}, expr];
f[x]
(* x *)

f = With[{x = 1}, #]&;
f[x]
(* 1 *)

Sometimes the first result might be desired and at other times the second. But naively we might think that the two definitions ought to be equivalent.

Assessment

We have seen examples where the behaviour of functions differ depending on whether local variable names in distinct scopes collide. We have also seen examples of different behaviour when using slot notation instead of named function arguments.

On the one hand, we can argue that scope does not really exist in the rule-based replacement process. Under this view we should expect the λ named argument abstraction to be leaky and take explicit steps to avoid name conflicts.

On the other hand, Mathematica is already undertaking some "magic" variable renaming during standard evaluation precisely to avoid circumstances such as these. The renaming strategies are mostly effective but, unfortunately, not always. Under this view, the leaks in the λ abstraction might be considered a bug.

Either way, the λ abstraction is leaky and named function arguments have some pitfalls. In reasonably rare but possible situations they can introduce subtle bugs in user code. Slot notations in functions are safer because they do not suffer the risk of semantic differences due to name collisions.

I hit this issue in real code involving separately developed library and application packages. It took a long time to diagnose. As a result, I now tend to use slot notation almost exclusively (a conclusion confirmed by WRI when I reported the issue). I will occasionally use named function arguments interactively when all variable names are gathered together under my direct control.

Answer 2

The actual output is Function[0, 999][0]. I have guessed (I hope correctly) that the expected value was 999 as from Function[a, 999][0].

In Trace[f[999], TraceOff -> Message], the essential part that is responsible for h[0] is just

h$94073[a$_]:=Function[a$,999][a$]

which can be rewritten more friendly and equivalently as

h[a_] := Function[a, 999][a]

and the problem is still what should be h[0].

Actually Module and g are irrelevant. What I am doing is building a minimal example.

The example can be further minimized. h[0] actually calls

h[0] /. h[a_] :> Function[a, 999][a]

but h is irrelevant as well, so the example further simplifies to

0 /. a_ :> Function[a, 999][a]

(At each step, the value is still Function[0, 999][0].)

By definition of RuleDelayed, what actually occurs is:

Unevaluated[Function[a, 999][a]] /. a -> 0

that is, the replacement occurs before Function can do anything, hence the annoying but very legitimate output.

Had the original programmer been more simple minded, he would have written:

In[1362]:= h = Function[a, 999]

or even

h=Function[999]

so that

In[1363]:= h[0]
Out[1363]= 999

In conclusion, I think that in this case the Wolfram language is perfectly consistent.

In general the rule replace system gives a lot of freedom and if misused in intricate situations it can give surprising results.