Re: efficiency of Function
- To: mathgroup@smc.vnet.net
- Subject: [mg11545] Re: efficiency of Function
- From: Robert Villegas <villegas@wolfram.com>
- Date: Sat, 14 Mar 1998 13:56:00 -0500
- Organization: Wolfram Research
> The following test shows that Function that uses Slot as its formal
> parameters are significantly faster than explicit naming of its formal
> parameters. i.e. Function[Slot[1]^2] is faster than Function[{x},x^2].
> My question is: why the speed difference stick with the function? I
> assume that functions with identical behaviors should be identical
> internally too. (theoretically, of course)
>
> Is this something we can expect improvement, or are there situations
> where f1 and f2 behaves differently? (or are there subtle situations
> where constructs using Slot and explicit naming can effect the meaning
> of the function?)
Xah,
Function does behave differently when its variables are named Symbol
variables instead of #n and ##n. The difference in meaning applies
when the body of the function contains other scoping constructs
(Function, Module, Rule, Set, Condition, et al).
When Function's variables are named Symbols
Function[{v1, ..., vn}, body]
it is more careful to respect other scoping constructs that may be
inside 'body'. Like Module and With, Function respects the local
variables and bodies of nested scoping constructs in two ways:
(1) When the outer and inner scoping construct both declare 'x' local,
the outer will not go into the inner's body and tag or replace
occurrences of 'x'. The inner construct owns all the variables
that
it declares local.
(2) When the outer construct declares 'x' local but the inner
construct
doesn't, then if 'x' occurs in the body of the inner construct,
the
outer will rename all the inner's local variables (using the
var -> var$ scheme). This is because if the outer construct owns
any
variables in the inner's body, then it's possible that by
coincidence, the outer will substitute values into the inner that
happen to be the same as the local symbols of the inner.
For both of these, the inner construct must be well-formed in some
sense, which means it must at least have the correct number of
arguments. A Function with eight arguments isn't well-formed and won't
be respected.
A "respectful" scoping construct bears the burden of scanning its entire
body to decide which instances of its declared symbols it owns --and to
tag them as such, and which it does not own. This takes time, and if
renaming must be applied to inner constructs to protect them, it takes
more time.
When Function has just one argument, meaning its variables are Slot #n
and SlotSequence ##n expressions, then it doesn't respect nested
scoping constructs. It plows right on through everything except other
Function's of one argument. When it encounters a Function of one
argument, it can simply skip that entire subexpression, since all #n
and ##n in there will be owned by something else. Also, all
one-argument Function use the same variables, #n and ##n, so there is
no renaming to do. Slot variables always belong to the nearest
enclosing one-argument Function, but no other scoping construct can use
Slot variables (actually, Compile can, but you shouldn't take advantage
of that).
Since a one-argument Function has no restrictions on its handling of the
body other than "don't descend into one-argument Function
subexpressions", it's easier for it to decide what it owns in the body,
and consequently, it's faster. If speed is your ultimate concern, and
you don't need Module-style scoping behavior, then pure functions with
# variables are faster than With[vars, body] and Function[vars, body].
Here are some examples to exhibit the scoping behaviors.
The outer Function won't overwrite the inner Function's x with 0:
In[16]:= Function[x, Function[x, x + 1]][0]
Out[16]= Function[x, x + 1]
The outer Function owns x inside the body of the inner Function, so it
renames the inner Function's variables as a precaution:
In[17]:= Function[x, Function[a, a + x]][0]
Out[17]= Function[a$, a$ + 0]
The following illustrates the motivation for automatic renaming of
variables:
In[19]:= Function[x, Function[u, u + x]][u]
Out[19]= Function[u$, u$ + u]
If renaming didn't occur, the result would have been Function[a, a + a].
The inner's u has become confused with a happenstance value of u
inserted by the outer. This would violate the principle that local
variables are dummy variables whose names are immaterial.
HoldForm can be used to freeze the body, to see how the outer scoping
construct has affected its form:
In[20]:= Function[x, HoldForm @ Module[{u = 2}, u + x]][u]
Out[20]= Module[{u$ = 2}, u$ + u]
In[22]:= Module[{x = u}, HoldForm @ With[{u = 1}, u + x]]
Out[22]= With[{u$ = 1}, u$ + x$8]
Finally, here's an example which demonstrates that although the inner's
local variables themselves are protected, their _initial values_ are
computed in the outside scope:
In[33]:= Function[x, HoldForm @ Module[{x = x^2 + 1}, {x}]] [2]
2
Out[33]= Module[{x = 2 + 1}, {x}]
In[34]:= ReleaseHold[%]
Out[34]= {5}
Robby Villegas