eval() does not bind variables in lambda expressions
correctly:

>>>def f(g): return eval('lambda x: g(x)')
>>>f(lambda y: y * 2)(17)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<string>", line 1, in <lambda>
NameError: global name 'g' is not defined

The docs say this about eval():

# If both dictionaries are omitted, the expression is
# executed in the environment where eval is called.

and using plain local variables work as expected:

>>>def h(d): return eval('d(10)')
>>>h(lambda y: y * 2)
20

Also, if locals() is presented as the global dict to
eval(), it works:

>>>def f(g): return eval('lambda x: g(x)', locals(),
locals())
>>>f(lambda y: y * 2)(17)
34

but this does not allow the expression to reference
global variables of course.

Logged In: YES 
user_id=593130

I am 99.5% sure that this is 'invalid' (a Resolution category) and 
should be closed.  With the default environment, eval('x') is the 
same as unquoted x.  Variables in Python functions are resolved 
when the function is *called*, not when it is defined.  There is no 
resolution for g in the default globals.  Eval does not change this.  
The NameError is exactly correct.

Logged In: YES 
user_id=432579

>Variables in Python functions are resolved 
>when the function is *called*, not when it is defined.

I'm not sure what you mean by that, since Python obeys
lexical scoping, not dynamic.Consider:

def f(x): lambda y: x + y

When the inner lambda expression above is evaluated, x
inside the lambda body is bound to the parameter of the call
of f, even if x+y is not evaluated until that function is
called.
So since

def f(x): return eval('x')

fetches its definition of x from the lexical variable x, why
shouldn't

def f(g): return eval('lambda x: g(x)')

fetch its definition of g from the lexical variable g? A
lambda expression is just a way of delaying evaluation,
*not* delaying how variables are bound --- this is done
immediately.

Logged In: YES 
user_id=593130

Whoops.  eval('x') ==  x as code snippets has an exception, 
which is the one tripping you up.  When the eval is within a 
function definition (and lambda expressions are abbreviated 
simple function definitions) and 'x' contains a function definition, 
then the body of the contained function definition does not have 
access, when it is run, to the locals of the containing function 
(the lexical scope), whereas it will when x is compiled directly *as 
part of the containing function body*.  eval('x') removes x from 
that part of its context.  eval only has the simple two-level 
globals/locals environment, which can be anything the caller 
passes in, so it compiles x as if it were top-level code.  Hence 
free variables in contained functions are looked up in the global 
passed to  eval when the evaled function is called.

This issue has been discussed on the Python newsgroup/mailing 
list more than once.  If my explanation is not clear, you might be 
able to find others in Google c.l.p archives.  Do consider that 
core functions which have been debugged for over a decade are 
unlike to have many bugs left, although the docs are still being 
improved.

While Python's scoping is lexical, its free variable binding is late.
Consider
>>> def f():
...   x = 0
...   def g(): print x
...   x = 1
...   return g
...
>>> f()()
# What gets printed? 0 or 1?
#  From your comments, I suspect you expect 0.
#  Irregardless, it is
1

Similarly
>>> f()()
1
>>> d={'x': 0}
>>> h=eval('lambda: x', d, d)
>>> h()
0
>>> d['x'] = 1
>>> h()
# now what gets printed?
1

Logged In: YES 
user_id=432579

What you are saying is "it works that way because it is the
way it works". I see no reason at all for this odd behaviour
other than bug-compatibility. I find nothing at all in the
documentation supporting this behaviour either; please
inform me if  I have missed something.

All other languages supporting eval and lexical scoping
(Lisp, Scheme, Perl, Ruby, etc) work in the expected way. I
have no problems if Python wants to be different for
whatever reason, but it should be documented.

I did a quick Google in comp.lang.python but could not find
anything that supported this "exception" or gave a rational
explanation. Kindly direct me to any resource you know of
that could help enlighten me on this issue.

>#  From your comments, I suspect you expect 0.

Of course not. I know very well how lexical scoping works,
so please don't put words in my mouth.

None of your examples have anything to do with scoping. As
we both know, it is not the _values_ of the variables that
is important for variable binding, it is their identity;
which variable is chosen, not what they happen to contain at
the time the lambda expression is evaluated.

Logged In: YES 
user_id=1230541

I think this issue is not special for eval and can be also 
reproduced with a def statement. The point is that at function 
definition time Python does not do any variable binding 
concerning variables not local to the function. Instead Python 
looks for that variable in the namespace of the module in 
which the function was created at the time the function is 
executed. Python determines that module by evaluating the 
variable __module__ at function definition time and 
remembers it by setting the function attribute with the same 
name. That's why only the variable __module__ is relevant at 
function definition time. Simply put, Python does only do a 
module level variable binding at function definition time. This 
is simple and sensible. If you don't agree consider this:

n=2
def f(x): return n*x
del n
f(2) 
# the Python implementation will result in a name error here. 
But what should happen if Python had bound variable n at the 
time of f's definitionf?
# let's define n again
f(2)
# the implementation will return 6, but how about your 
expected implementation?

As you see, changing the implementation would either make 
Pythons semantics more complicated or would remove much 
of Pythons dynanism.

Logged In: YES 
user_id=1230541

Obviously I forgot a statement in my previous comment's 
code example. So here's the complete version:

n=2
def f(x): return n*x
del n
f(2) 
# the Python implementation will result in a name error here. 
But what should happen if Python had bound variable n at the 
time of f's definitionf?
# let's define n again
n=3
f(2)
# the implementation will return 6, but how about your 
expected implementation?

Logged In: YES 
user_id=432579

No, this issue is specific to eval of lambda expressions.
Please read my problem description. Please refer to the
Python documentation if you are confused with how standard
function declaration or lexical scoping works.

Logged In: YES 
user_id=593130

No, this issue is not specific to either eval or lambda:

>>> def f(g):
...   exec 'def h(x): return g(x)'
...   return h
...
>>> f(lambda y: y * 2)(17)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<string>", line 1, in h
NameError: global name 'g' is not defined

It is specific to creating a function at top-level in a separate 
execution environment, as done, by design, by both eval and 
exec, and with either a def statement or lambda abbreviation 
thereof.

In Python, lexical scoping works because nested functions are 
compiled along with the outer function, so that scoped variables 
can be identified and both functions adjusted so that the coupling 
works.  In particular, the scoped variable has to not be deleted 
when the outer function returns.  Eval/exec compile their string 
only later, when the function is called.

"it works that way because it is the way it works".
Those are your words, not mine.  If you want Python to work 
differently, write a PEP or a patch, or raise the question in the 
newsgroup/mailing list. I'm done discussing it here.

Logged In: YES 
user_id=432579

>No, this issue is not specific to either eval or lambda:

Right, so let me rephrase: The bug occurs when explicitly
evaluating a lambda expression or function definition
statement using eval or exec. (This is an artifact of
Python's strong separation of statements and expressions.)

If this is done "by design", why cannot I find anything
anywhere describing this? If this is just a documentation
oversight, please say so, but then I would also like to have
an explanation of the behaviour.

The fact remains that

    def f(x): eval('x')

works as expected and

    def f(g): eval('lambda x: g(x)')

does not. Why? Both are evaluated at the same time and use
the same environment to look up their variables. The fact
that the 'g' variable in the second case is not evaluated
immediately does not affect its scoping, because that is how
lambda expressions work.

>If you want Python to work 
>differently, write a PEP or a patch, or raise the question in
>the newsgroup/mailing list.

www.python.org told me that this is the place to report bugs
in Python. If that is wrong, we should change the web site.

Logged In: YES 
user_id=80475

Jeremy, would you update the pep and docs to cover the OP's
examples.

Logged In: YES 
user_id=593130

After more carefully reading the eval doc in Lib Ref 2.1, I agree 
that it needs improvement.  My suggestions (assuming that my 
experiment-based inferences are correct):

In 
"The expression argument is parsed and evaluated as a Python 
expression (technically speaking, a condition list) using the 
globals and locals dictionaries as global and local name space."
insert "in a new top-level environment" before 'using'. This says 
right-off, even if indirectly, that lexical scoping does not work 
across the eval call.

In
"If the locals dictionary is omitted it defaults to the globals 
dictionary."
insert "only" after "If'.  If both are omitted, it does not so default.  
Add a comma after 'omitted', as in the next sentence.

In
"If both dictionaries are omitted, the expression is executed in 
the environment where eval is called."
replace  "the expression ... is called", which I believe to be 
incorrect as well as misleading, with something like "they default 
to current globals() and locals()."  This parallels the previous 
sentence and is, I believe, more correct.  Within a function, 
locals() is not the current local namespace, and the following 
shows that the difference can make a visible difference:

>>> def g1(): return op.setitem(locals(), 'x', 1), x
...
>>> g1()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 1, in g1
NameError: global name 'x' is not defined
>>> def h1(): return eval("op.setitem(locals(), 'x', 1), x")
...
>>> h1()
(None, 1)

After
"The return value is the result of the evaluated expression. "
add something like
It does not depend on the lexical position of the eval call and 
hence the expression should not contain names that require 
lexical scoping reaching outside the eval call to be valid."

Note that eval scope blocking, the OP's pseudobug, does not 
require a lambda within the eval-ed expression:
>>> def f(x): return lambda: x
...
>>> f(1)()
1
>>> def g(x): return lambda: eval('x')
...
>>> g(1)()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 1, in <lambda>
  File "<string>", line 0, in ?
NameError: name 'x' is not defined

This might be another example for the PEP.

Logged In: YES 
user_id=593130

"   def f(x): eval('x') works as expected and
    def f(g): eval('lambda x: g(x)') does not. Why?"

For the same reason
  def f(g,s): return eval(s)
 f(lambda x: x, 'lambda x: g(x)')(1)
and
  def g(x): return lambda: eval('x')
do not 'work'.  eval is a builtin C function whose behavior 
depends on its arguments (including the somewhat magical 
defaulting to globals(), local()) and not on its lexical position.

" Both are evaluated at the same time and use
the same environment to look up their variables."

No, the lambda in your second example introduces a new local 
namespace that is different from the one passed in.

" The fact that the 'g' variable in the second case is not evaluated
immediately does not affect its scoping"

The delay and change of scoping are correlated. Evaluation is 
delayed because g is inside a lambda function def which 
introduces a new local scope which does not contain g, even 
though the original one did. 

Logged In: YES 
user_id=31392

The source of the problem is that scoping decisions are made
statically.  If a variable is determined to be local at
compile time, it can't be access as a free variable in
dynamically compiled code.  The compiler has already
determined that the variable is *not* free in the containing
function.  If a variable is free in a nested function, the
compiler treats it differently than if it is merely local to
the function.

In the most recent cases considered,
def f(x): eval('x') -- works because x is a local variable in f.
def f(g): eval('lambda x: g(x)') -- does not work because
the compiler has determined that g is not used a free
variable in f.  It isn't possible to change that static
analysis at runtime using eval or exec.

I agree that the documentation could be clearer here.

Logged In: YES 
user_id=432579

>The source of the problem is that scoping decisions are made
>statically.

No, because other languages with lexical scope and
permitting evaluation at runtime have no problem whatsoever
with this. They just answer the question:

Q: In what environment is the eval() argument evaluated?

typically in one of three ways:

A1. In an empty environment with no bindings at all, or just
the language-defined standard bindings.
A2. In the (or a) top-level environment; local, lexically
bound variables where the eval() takes place are not visible
to the argument expression.
A3. In the same lexical environment as the eval() call itself.

Perl and Ruby both say A3. Scheme (R5RS) lets the user
specify A1 or A2. Common Lisp answers A2.

Observe that none of the answers depend on what the
expression looks like.

Now, let's be crystal clear about this: The rules of where x
is looked up in the expressions

1) x

and

2) lambda: x

should reasonably be the same - after all, this is
fundamentally how lexical scoping works. And Python does
indeed work this way, to everybody's satisfaction.

In case 2), the evaluation of x is delayed, but that is
irrelevant; the decision of what x means is taken at the
same time in both cases, and the decision will be the same.

Most people would expect Python to answer question Q above
with one of the answers A1-3, but it does not, and it does
not document what the answer is. The Python answer is rather:

A4. A mixed hybrid environment of some kind: The identifiers
representing variables that are to be evaluated immediately
are looked up in the lexical environment of the eval
expression; identifiers representing variables in
delayed-evaluation positions use the global environment.

This answer is not very satisfactory and I'm inclined to
consider a design bug; it is different from what everyone
else does and not very intuitive. However, I can accept that
it is hard to change now for compatibility reasons. But this
answer A4 should be documented.

Logged In: YES 
user_id=432579

Lest my last comment be interpreted as overly arrogant,
please  be assured that it was not meant as anything other
than an explanation of why I reported this as a bug in the
first place. I do understand that Python works the way it
does; I just want it to be even better. :-)

I guess I should get back to this bug report at least once a year.  I'm trying to understand how Scheme handles eval.  If I look at R5RS or R6RS, I see that the eval procedure takes an environment as an argument.  The procedures that create environment all seem to create variants of the top-level environment (an empty environment, the interactive environment, etc.).  I don't see any way to create an environment that contains the bindings visible in a particular region of code.  Am I missing something?

That is quite correct; standard Scheme does not have the ability to eval expressions in a lexical environment. There are of course good performance reasons for that (we don't want to keep all lexical environments around in symbolic form, just in case someone would EVAL an expression referring to a name inside one of them).

It would be fine for Python to have a similar rule, but now it's just weirdly inconsistent.

I think this should be closed as rejected.  It is a vague wish that
Python change its scoping rules in a way that is extremely unlikely and
which would require a PEP in any case.  I might sometime recheck my
suggested doc changes versus the current versions, but that would be a
different issue.

This is not a vague wish at all. The implementation is at odds with the
documentation, and in fact nobody has been able to explain just how
Python works or should work. Read msg24424 again - it all boils down to
explaining why the variable x in

    def f(x): return eval('x')

and

    def f(x): return eval('lambda: x')

should be interpreted differently, whereas in

    def f(x): return x

and
    def f(x): return lambda: x

the same x is used in both cases.

issue5044 describe a similar case with generator expressions:

def f():
   a = 'a'
   eval("sum(a[0]=='a' for j in 'a')")

eval( "sum(   a[0]=='a' for j in 'a'   )", {}, dict(a='a'))

The current docs cover this case:
http://docs.python.org/reference/executionmodel.html#interaction-with-dynamic-features

It basically says that code compiled via exec / eval can't access free
variables.