The first of the two maps below gives strange result due to the nested
generator expression (I guess it should give the same result as the
second map).

In [1]: map(list, [(x+y for y in 'c') for x in 'ab'])
Out[1]: [['bc'], ['bc']]

In [2]: map(list, [[x+y for y in 'c'] for x in 'ab'])
Out[2]: [['ac'], ['bc']]

By using a generator expression, you are deferring evaluation of the
expression until map() is actually invoked. By that time, the closure
over 'x' has been changed to 'b', so when the genexp is forced, 'x'
yields 'b' each time.

I'd already written then when Benjamin posted his answer, but rather
than waste having written it I'm going to post it anyway :)

You must remember that the purpose of a generator is to evaluate lazily.
 Your expression involving the generator would unwrap this way:

def g1():
    for y in 'c':
        yield x+y
l = []
for x in 'ab':
    l.append(g1())
print l
print map(list, l)

If you run this you will note that 'l' is a pair of generator instances.
 These are not run until the 'map' is executed. By that point the for
loop has completed, and x has its final value, 'b'.  g1 is evaluated
twice, and both times x is 'b', so you get ['bc', 'bc']

This is a crazy and unexpected behavior.  (Moreover, the fact that Python has dynamic scope *only if you forget to initialize a variable* is even more crazy and unexpected.)  To provide unsurprising behavior (i.e. behavior compatible with that of a list comprehension) the generator above should "unwrap" (i.e. reduce) to:

def g1(x):
    for y in 'c':
        yield x+y
l = []
for x in 'ab':
    l.append(g1(x))
print l
print map(list, l)

i.e. the variables referenced by, but not initialized by, the innermost generator should add extra parameters to the generated generator function.

Also tested and broken in Py3k.

The behavior is deeply baked into how Python does closures and scoping. It shows up elsewhere than generators (eg: nested function definitions; usually encountered when using lambdas).  So, this behavior isn't going to change, it's just one of a relatively small handful of odd things you have to learn in order to grok Python.  (And yes, it is surprising...that's why there's a FAQ for it.)

Only the implementation of *generators* needs to change to remedy this bug.  Please see the example I included.  By closing the generated generator function over free the free variables in the generator expression, you can avoid dynamic scoping entirely and provide expected behavior.

The reason I claim this behavior is surprising and incorrect is because generator expressions are touted as being able to replace list comprehensions, when in fact they are not due to this bug.  Even the generator expression PEP claims: "This PEP introduces generator expressions as a high performance, memory efficient generalization of list comprehensions".

Until this bug is fixed, generator expressions are NOT a generalization of list comprehensions, and hence CPython is in violation of the PEP as accepted.

Quote from Guido:

"""In general the value of every free variable used anywhere 
except in the outer expression should be captured; [...] This 
should give the least surprising semantics in a variaty of use 
cases."""

Source: http://bugs.python.org/issue872326#msg45190

I hear what you are saying, but the "generalization" does not mean that they work exactly the same way.  The whole point of generators is that execution is lazy, which is what leads to the difference in behavior.  

The generator function *is* closed over the free variables.  That's what leads to the difference in behavior: the generator uses the value the free variable has when the generator executes.  I don't believe there is any practical way to implement what you are suggesting, even if we wanted to...which we would not be, since it would constitute a backward incompatible change in behavior.

Note also that this behavior of closures is not unique to Python.  See for example http://www.javascriptkit.com/javatutors/closures2.shtml.

To be honest I don't understand the sentence from Guido that you are quoting (even reading the issue I don't think I have the full context), but what we wound up with was what he wound up wanting.

> I hear what you are saying, but the "generalization" does not mean
> that they work exactly the same way.

Correct.  But it does mean that the functionality of one (generator expressions) is a superset of the functionality of the other (list comprehensions).  That is currently not the case.

> The whole point of generators is that execution is lazy, which is
> what leads to the difference in behavior.

No.  That the innermost generator isn't closed over its free variables is what leads to the difference in behavior.

> The generator function *is* closed over the free variables.  That's
> what leads to the difference in behavior: the generator uses the
> value the free variable has when the generator executes.

We're using the term "closure" in two different ways.  Coming from a FP background (where comprehensions first found their way into programming languages), I mean it to close over the value of the variable.  I understand that in Python it closes over the variable itself.  In the context of a comprehension, I claim that the latter is useless and surprising behavior.

> I don't believe there is any practical way to implement what you are
> suggesting

Again, please see the example in my original post.  The generic algorithm is simple: for every generator expression syntactically nested inside another, walk the AST of the inner generator expression's output expression.  Do not enter lambdas.  Recursively apply this algorithm for any generator expressions syntactically nested in the inner generator expression.  For every variable referenced which is not bound by the inner generator expression, add it as a parameter to the generated inner generator function, and add it as an argument when calling the inner generator function from the outer generator function.

> even if we wanted to...which we would not be, since it would
> constitute a backward incompatible change in behavior.

You can't honestly tell me anyone relies on the current behavior of nested generators.

Furthermore, my assertion is that the current behavior is in violation of the language specification.  If "backward-incompatible changes in behavior" was a legitimate excuse for refusing to remedy implementation/specification disparities, then it would apply to every Python bug ever.

Well, we're a bit more nuanced about backward compatibility than that :)

I doubt that people *intentionally* rely on the behavior, true, so a change could conceivably be made in a new release.

At this point you need to take your arguments to python-ideas or python-dev (probably the latter), where the people who built this PEP and its implementation can address your concerns better than I can.  I could be wrong, since I'm just a user of generators, not one of the implementors.

*At this point you need to take your arguments to python-ideas or python-dev (probably the latter),*

I used Python once and will probably never use it again.  I'm not nearly invested enough to evangelize on several mailing lists the validity of a bug that I've already reported.

If you want treat take my bug report as the ramblings of a selfish kook who doesn't know squat about language design or development, then you need take no further action.

However if you'd rather consider that someone with little investment in the language who took the time to form a cogent argument pointing out a surprising and possibly buggy behavior might in fact represent the sentiments of Python user base at large, then you should consider re-opening this bug.

In my experience the devs are pretty well in touch with the user base (though they don't always acknowledge its input). If you leave a programming language at the first sign of  wart I fear yo may eventually run out of languages.