Dynamic methods and lambda functions

[Mark Wooding]

Steve Holden <steve at holdenweb.com> writes:

> Mark Wooding wrote:
>>   * Assignment stores a new (reference to a) value in the variable.
>> 
>>   * Binding modifies the mapping between names and variables.
>> 
> I realise I have omitted what was doubtless intended to be explanatory
> detail, but I am having trouble reconciling those sentences. Would you
> mind explaining "in vacuuo" what you see as the difference between
> assignment and binding?

OK.  This turned into something of an essay.  I hope that it's of use to
somebody...

A name is a kind of expression.  Expressions can be evaluated to yield
values.  Therefore, a name can be evaluated to yield a value.  How does
this happen?  There are two distinct mappings involved.

The first mapping is from names to variables.  This mapping is usually
called the `environment', and is acted upon by `binding'.  The extent of
the program text whose meaning is affected by a binding is called the
`scope' of the binding[1].  In Python, the scope can be determined
statically by analysing the program text (`lexical scope').  In some
languages the scope can only be determined at run time (`dynamic
scope'); other languages have a mixture of the two.

Binding in Python is done in two ways:

  * /Explicit/ binding is done by `def' or `lambda': the parameters are
    bound, and the scope of the bindings is the entire function body
    (i.e., it does not include the default arguments).

  * /Implicit/ binding may be performed when a name as a result of an
    assignment operation -- either an assignment statement or one of a
    number of features which work by assignment, including `for' loops,
    list comprehensions, and `def' blocks.  The scope of the binding in
    this case depends on the nature of the block in which the binding
    occurs: within `def' and `lambda'[2], the scope is the entire
    function body; within `class' and module toplevels, the scope is
    from the first-executed assignment to the end of the block.

In all cases, names are bound to fresh variables when the scope of the
binding begins.

The environment within a binding block is formed by extending the
environment of the surrounding program text.  In the case of function
definitions, in particular, we say that the function `closes over' the
environment in which it is defined.

The second mapping is from variables to values.  This mapping doesn't
seem to have a common name, though it's referred to as the `store' in
some formal semantics (e.g., R5RS Scheme).  The store is acted upon by
assignment (and assignment-like operations such as `for' loops and list
comprehensions).  An assignment

        NAME = VALUE

alters the store as follows: the variable bound to NAME becomes mapped
to the result of evaluating VALUE.

We can now consider some example programs.

        In [23]: def simple(x):
           ....:   def inner():
           ....:     return x
           ....:   return inner
           ....:

When the function is invoked, say by

        In [24]: simple('boo!')()

the name x is bound to a new variable, and the variable is assigned the
value `boo!'.  The body of `simple' is then executed.  First, a function
`inner' is defined: `def' is an assignment-like operation, which causes
`inner' to be implicitly bound to a fresh variable on entry to the
function.  When the `def' is executed, that variable is assigned the
value of a function.  Finally, we return the result of evaluating
`inner', i.e., the function we just constructed.

The next pair of parentheses invoke the function `inner'.  That function
was defined within an environment in which x was bound to a variable
that had been assigned the value 'boo!'.  It therefore returns this
value:

        Out[24]: 'boo!'

Next example:

        In [26]: def mutant(x):
           ....:   def inner():
           ....:     return x
           ....:   x = 'changed!'
           ....:   return inner
           ....:

Suppose we invoke this one as

        In [27]: mutant('same')()

The first steps are the same: x is bound to a fresh variable which is
assigned the value 'same'; `inner' is bound to a fresh variable which is
assigned a function value.  Now the line `x = 'changed!'' is executed.
This assigns the string 'changed!' to the variable bound to x.  Finally,
we return the function value.  That function is now invoked.  It was
defined in an environment where x was bound to a variable whose last
assigned value was 'changed!'.  Therefore:

        Out[27]: 'changed!'

The original poster's question can be illustrated by this example:

        In [28]: def problem():
           ....:   return [lambda: i for i in xrange(3)]
           ....:

        In [29]: [f() for f in problem()]

This is actually the same as the mutant example in disguise.  There is
no parameter to bind, but `for' in a list comprehension is an assignment
operation, and therefore i is implicitly bound when `problem' is
invoked.  

The list comprehension performs three iterations.  On each iteration,
the `lambda' is evaluated.  It produces a different function value each
time:

        In [30]: problem()
        Out[30]:
        [<function <lambda> at 0x9a731ec>,
         <function <lambda> at 0x9a73064>,
         <function <lambda> at 0x9a730d4>]

And each time through, the variable bound to i is assigned a different
value: first 0, then 1, and finally 2.  The resulting functions are
gathered into a list, which is returned as the value of `problem()'.

However, it was textually the same `lambda', and so they closed over the
/same/ environment -- that of the body of `problem' -- in which i is
bound to the same variable.  That variable was last assigned the value
2.  Therefore, when we invoke any of the functions, we get the same
result:

        Out[29]: [2, 2, 2]

Two fixes were suggested.  I suggested this one:

        In [31]: def bind_fix():
           ....:   def hack(i): return lambda: i
           ....:   return [hack(i) for i in xrange(3)]
           ....:

        In [32]: [f() for f in bind_fix()]
        Out[32]: [0, 1, 2]

How does this work?  Each iteration invokes the `hack' function.
Invocation binds i to a new variable, and assigns it the value of the
argument (which is 0, 1, or 2 according to which iteration we're on).
The `lambda' which `hack' returns closes over /this/ environment, and
the variable bound to i in `hack''s environment is not assigned again,
so the problem doesn't occur.  The function `hack' is basically a
one-line version of the `simple' example above.  While `hack' closes
over the environment of `bind_fix', this isn't important: `hack''s
binding of i `shadows' the outer binding of `bind_fix'.  It's where it
is to avoid cluttering up the toplevel namespace.

The other fix uses default arguments, and it was suggested by Steven
D'Aprano and Brian Vanderburg.

        In [33]: def defarg_fix():
           ....:   return [lambda i = i: i for i in xrange(3)]
           ....:

        In [34]: [f() for f in defarg_fix()]
        Out[34]: [0, 1, 2]

This is conceptually rather simpler; I didn't suggest it because it
doesn't teach the concepts I was exploring as well.  The important point
about default arguments in Python is that they're evaluated at the same
time as the function is being defined, rather than on every call[3].
There are three functions defined, one for each iteration of the list
comprehension; since i is assigned a different value on each iteration,
and the default argument is evaluated on each definition, each function
acquires a distinct defalt argument for its parameter i.

Chapter 3 of the Structure and Interpretation of Computer Programs, by
Abelson and Sussman explains this stuff in a more discursive and
approachable manner.  If you're still confused by my explanation (and by
nature I tend to err on the side of precision rather than clarity, a
fault which I know impairs my teaching ability), you may find theirs
more useful:

 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-19.html#%_chap_3

Nonetheless, I hope that this description has been of some use.


[1] Under lexical binding, a particular binding always affects the same
    region of program text.  That doesn't mean that the same binding is
    used every time that text is executed!

[2] Yes, `lambda' acts as a binding block.  I leave construction of a
    program exhibiting this behaviour as an exercise.

[3] This is unlike default arguments in, for example, Common Lisp.  Both
    behaviours are useful.  Python's behaviour was especially valuable
    before the language provided true closures.

-- [mdw]