Explanation of this Python language feature? [x for x in x for x in x] (to flatten a nested list)

[vasudevram]

Hi list,

Can anyone - maybe one of the Python language core team, or someone with knowledge of the internals of Python - can explain why this code works, and whether the different occurrences of the name x in the expression, are in different scopes or not? :

x = [[1,2], [3,4], [5,6]]
[x for x in x for x in x]

I saw this on a Hacker News thread about Python, and here is a post I wrote that gives more details about it, including relevant links, how I found that it can be extended to a triply-nested list, and my thoughts about the scope issue:

http://jugad2.blogspot.in/2014/03/flatten-list-of-lists-with-list.html

A few people commented about it, both on my blog, and on the Python Reddit where I also submitted my post, but I'm not sure I'm convinced of their reasoning or understand it, hence posting the question here.

Thanks,
Vasudev Ram
www.dancingbison.com
jugad2.blogspot.com

[Rustom Mody]

Lets try without comprehending comprehensions :-)

>>> x=[[1,2],[3,4]]
>>> for x in x:
... for x in x:
... print x
...
1
2
3
4
>>>

[vasudevram]

On Saturday, March 22, 2014 2:24:00 AM UTC+5:30, Rustom Mody wrote:
> Lets try without comprehending comprehensions :-)
> >>> x=[[1,2],[3,4]]
>
> >>> for x in x:
>
> ... for x in x:
>
> ... print x
>
> ...
>
> 1
>
> 2
>
> 3
>
> 4

Nice and all, thanks, but doesn't answer the question.

[Rustom Mody]

Which is?



A 'for' introduces a scope:

>>> x = 42
>>> for x in [1,2,3]:

... print x
...
1
2
3

No sign of the 42 --v ie the outer x -- inside because of scope

And so we can do:

>>> x = [1,2,3]

>>> for x in x:
... print x
...
1
2
3

which implies that in a "for var in exp: ..."
the exp is evaluated in outer scope whereas the var has a new scope inside
the "..."

Now repeatedly apply that principle to the nested for.
Same principle for nested for in a comprehension.

[Ian Kelly]

On Fri, Mar 21, 2014 at 3:09 PM, Rustom Mody <rusto...@gmail.com> wrote:
> A 'for' introduces a scope:

This is false.

>>>> x = 42
>>>> for x in [1,2,3]:
> ... print x
> ...
> 1
> 2
> 3
>
> No sign of the 42 --v ie the outer x -- inside because of scope

Try printing x again *after* the for loop:

>>> x = 42
>>> for x in [1,2,3]:

... print(x)
...
1
2
3
>>> print(x)
3

Notice that it's still 3. If the x in the for loop were really a
separately scoped variable, we would have expected to see 42 here. In
fact the x used in the for loop and the x used outside of it are the
same x variable.

The real reason that the OP's example works is because each value that
the x variable holds happens to only need to be read once. Start with
this code, and work through it line-by-line:

x = [[1, 2], [3, 4]]
for x in x:
for x in x:
print(x)

Initially, x is assigned the list. Then we enter the outer for loop.
The expression x is evaluated once to be iterated over. The first
value that the for loop iterator yields is [1, 2], which is then
assigned to x. Now we enter the inner for loop. The expression x is
again evaluated once to be iterated over. It first yields 1, which is
assigned to x, and then printed. The inner for loop iterator then
yields 2, which is also assigned to x and printed. The inner for loop
iterator then raises StopIteration, and the inner for loop terminates.
The outer for loop iterator then yields [3, 4], and this is assigned
to x. The inner for loop evaluates this expression and runs as
before. Afterward, the outer for loop iterator raises StopException,
and that for loop terminates. The final value of x here will be 4:

>>> x = [[1, 2], [3, 4]]

>>> for x in x:
... for x in x:

... print(x)

...
1
2
3
4

>>> print(x)
4

As I hope this makes clear, no nested scopes are needed to make this
happen. It works because nothing that is stored in x needs to remain
there after the next thing is stored in x.

[Gregory Ewing]

Rustom Mody wrote:

> A 'for' introduces a scope:

No, it doesn't!

>>>>x = 42
>>>>for x in [1,2,3]:
> ... print x
> ...
> 1
> 2
> 3
>
> No sign of the 42 --v ie the outer x -- inside because of scope

You're right that there's no sign of the 42, but it's
*not* because of scope, as you'll see if you do one
more print:

>>> print x
3

> And so we can do:
>
>
>>>>x = [1,2,3]
>>>>for x in x:
> ... print x
> ...
> 1
> 2
> 3

Again, if you print x after the loop has finished,
you'll find that it's no longer bound to the original
list. This is because Python's for-loop does *not*
introduce a new scope -- there's only one x, and
the for-loop is sharing it with the rest of the code.

The real question is why the for-loop works in *spite*
of this fact.

The answer is that the for-loop machinery keeps an
internal reference to the list being iterated over,
so once the loop has started, it doesn't matter what
x is bound to any more.

--
Greg

[Rustom Mody]

On Saturday, March 22, 2014 3:00:10 AM UTC+5:30, Ian wrote:

> On Fri, Mar 21, 2014 at 3:09 PM, Rustom Mody wrote:
> > A 'for' introduces a scope:

> This is false.

And

On Saturday, March 22, 2014 3:04:48 AM UTC+5:30, Gregory Ewing wrote:

> > A 'for' introduces a scope:

> No, it doesn't!


Ha -- funny that *I* missed that one. Thanks both Ian and Gregory

In fact one of my grumbles against python is that list comprehension's
are a poor imitation of haskell's comprehensions.

And then I promptly forgot about it!

Actually there are two leakages in python 2, one of which is corrected
in python 3.

One: a comprehension variable leaks outside after the comprehension
This is corrected in python3.
Two: A comprehension variable is not bound but reassigned across the
comprehension. This problem remains in python3 and causes weird behavior when
lambdas are put in a comprehension

>>> fl = [lambda y : x+y for x in [1,2,3]]
>>> [fl[i](2) for i in [0,1,2]]
[5, 5, 5]

The same in haskell:

Prelude> let fl = [\ y -> x + y | x <- [1,2,3]]
Prelude> [(fl!!i) 0 | i<- [0,1,2]]
[1,2,3]

[Chris Angelico]

On Sat, Mar 22, 2014 at 1:06 PM, Rustom Mody <rusto...@gmail.com> wrote:
> Two: A comprehension variable is not bound but reassigned across the
> comprehension. This problem remains in python3 and causes weird behavior when
> lambdas are put in a comprehension
>
>>>> fl = [lambda y : x+y for x in [1,2,3]]
>>>> [fl[i](2) for i in [0,1,2]]
> [5, 5, 5]

To clarify, what you're saying here is that x in the first
comprehension's closures should be bound to separate values for x,
yes?

I'm not sure how that ought to be done. Having closures that can
reference and modify each other's variables is important.

def func_pair():
x = 0
def inc():
nonlocal x; x+=1
return x
def dec():
nonlocal x; x-=1
return x
return inc, dec

fooup, foodn = func_pair()
barup, bardn = func_pair()
>>> fooup(), fooup(), fooup(), foodn()
(1, 2, 3, 2)
>>> barup(), barup(), bardn(), bardn()
(1, 2, 1, 0)

Those functions are fundamentally linked. Very useful with callbacks.
A nice alternative to doing everything with bound methods.

So if that's not going to be broken, how is this fundamentally different?

def func_loop():
for x in 1,2,3:
yield (lambda: x)

one, two, three = func_loop()
one(), one(), two(), two(), three(), three()

This one does NOT work the way the names imply, and I can see that
you'd like to fix it. But I can't pinpoint a significant difference
between them. How do you distinguish?

ChrisA

[Rustom Mody]

On Saturday, March 22, 2014 8:11:27 AM UTC+5:30, Chris Angelico wrote:

> On Sat, Mar 22, 2014 at 1:06 PM, Rustom Mody wrote:
> > Two: A comprehension variable is not bound but reassigned across the
> > comprehension. This problem remains in python3 and causes weird behavior when
> > lambdas are put in a comprehension
> >>>> fl = [lambda y : x+y for x in [1,2,3]]
> >>>> [fl[i](2) for i in [0,1,2]]
> > [5, 5, 5]

> To clarify, what you're saying here is that x in the first
> comprehension's closures should be bound to separate values for x,
> yes?

Yes

> I'm not sure how that ought to be done.

Thats an implementation question -- see below.

> Having closures that can
> reference and modify each other's variables is important.

Yes

> def func_pair():
> x = 0
> def inc():
> nonlocal x; x+=1
> return x
> def dec():
> nonlocal x; x-=1
> return x
> return inc, dec

> fooup, foodn = func_pair()
> barup, bardn = func_pair()
> >>> fooup(), fooup(), fooup(), foodn()
> (1, 2, 3, 2)
> >>> barup(), barup(), bardn(), bardn()
> (1, 2, 1, 0)

> Those functions are fundamentally linked. Very useful with callbacks.
> A nice alternative to doing everything with bound methods.

Yes

> So if that's not going to be broken, how is this fundamentally different?

> def func_loop():
> for x in 1,2,3:
> yield (lambda: x)

Thats using a for-loop
A 'for' in a comprehension carries a different intention, the matching names
being merely coincidental.

This 'pun' causes cognitive dissonance in all these questions, including
my gaffe above

> one, two, three = func_loop()
> one(), one(), two(), two(), three(), three()

> This one does NOT work the way the names imply, and I can see that
> you'd like to fix it. But I can't pinpoint a significant difference
> between them. How do you distinguish?

Using closures for carrying state is a different question

As for comprehensions, the appropriate *intention* would be like this:

Given

fl = [lambda y : x+y for x in [1,2,3]]

It means:

def rec(l):
if not l: return []
else:
x,ll = l[0],l[1:]
return [lambda y: x + y] + rec(ll)

followed by
fl = rec([1,2,3])

Naturally a reasonable *implementation* would carry this *intention* more
efficiently with standard techniques like
1. Using list extend/append methods
2. Using lambda y, x=x: x+y

Inside an implementation this is fine
Forcing such tricks as kosher on a programmer is not (IMHO)

[But then I find Lisp and much of basic haskell natural and most of C++ not,
so my views are likely prejudiced :-)

[Steven D'Aprano]

On Fri, 21 Mar 2014 19:06:06 -0700, Rustom Mody wrote:

> Two: A comprehension variable is not bound but reassigned across the
> comprehension. This problem remains in python3 and causes weird behavior
> when lambdas are put in a comprehension

I don't know why you say the behaviour in Python is a problem. It's
somewhat unexpected if you don't think about what's going on, but it's
actually quite logical. On the contrary, I find the Haskell version weird.

>>>> fl = [lambda y : x+y for x in [1,2,3]]
>>>> [fl[i](2) for i in [0,1,2]]
> [5, 5, 5]

This makes perfect sense: by the time you call the functions, the name x
has been rebound to the value 3. If x were a global, or if comprehensions
leaked their variable, that would be obvious: you could print x and see
exactly what value it has. But visible or not, that's exactly what
happens. Since x is 3, you're adding 3+2 and should get 5 no matter which
function you call.

Unroll the first comprehension, and it's obvious what is going on:

def unrolled():
fl = []
x = 0
def lambda_(y):
return x + y
fl.append(lambda_)
x = 1
def lambda_(y):
return x + y
fl.append(lambda_)
x = 2
def lambda_(y):
return x + y
fl.append(lambda_)
return [f(2) for f in fl]

Don't be fooled by the coincidence that the three "lambda_" functions
have the same name and body. They could have different names and
different bodies, Either way, it is completely natural that they all
closures over the same x -- that's how you wrote them.


But the Haskell version, on the other hand, is just weird:

> The same in haskell:
>
> Prelude> let fl = [\ y -> x + y | x <- [1,2,3]]
> Prelude> [(fl!!i) 0 | i<- [0,1,2]]
> [1,2,3]

For this to be the case, the functions in fl have to somehow "look back
in time" to see the value of x, not as it is *now* when the function is
called, but how it *was* when it was created. That's very weird indeed.
If x were a global, it would be astonishing. The fact that x comes from a
closure instead makes it no less surprising. Unroll the loop, and the
magic is obvious.

Now I'm not sure precisely how Haskell implements this trick, but it
suggests to me that it creates a different closure each time around the
loop of the comprehension. That could end up being very expensive.



--
Steven D'Aprano
http://import-that.dreamwidth.org/

[Chris Angelico]

On Sat, Mar 22, 2014 at 3:39 PM, Rustom Mody <rusto...@gmail.com> wrote:
>> So if that's not going to be broken, how is this fundamentally different?
>
>> def func_loop():
>> for x in 1,2,3:
>> yield (lambda: x)
>
> Thats using a for-loop
> A 'for' in a comprehension carries a different intention, the matching names
> being merely coincidental.

So what you're saying is that these two are fundamentally different:

def unrolled():
x = 1
yield (lambda: x)
x = 2
yield (lambda: x)
x = 3
yield (lambda: x)

def loop():

for x in 1,2,3:
yield (lambda: x)

In other words, a loop should be implemented as a separate binding
each time, not a rebinding. That's an interesting point, and it does
make some sense; effectively, what you want is for the body of a for
loop to be a new scope, a unique scope every iteration of the loop,
and one that automatically closes over all variables in the parent
scope (including for assignments) except for the loop
iteration/counter variable.

That does make some sense, but it doesn't really fit Python's concept.
It would, however, fit a more C-like language, where locals are
declared (in Python, you'd have to put a whole lot of implicit
'nonlocal' statements at the top of the loop).

ChrisAg

[Mark H Harris]

On 3/21/14 11:39 PM, Rustom Mody wrote:
> Given

> fl = [lambda y : x+y for x in [1,2,3]]

> It means:

> def rec(l):
> if not l: return []
> else:
> x,ll = l[0],l[1:]
> return [lambda y: x + y] + rec(ll)
>
> followed by
> fl = rec([1,2,3])

> Naturally a reasonable *implementation* would carry this *intention*

{snip}

> [But then I find Lisp and much of basic haskell natural and most of C++ not,
> so my views are likely prejudiced :-)

This discussion (the entire thread) comes up again and again over the
years because python tries to be all things to all people, without much
reason behind the motivation. I'm speaking of Lambda (filter, map, reduce).

Python is not Lisp. (I love Lisp too). Python is not Haskell (I love
Haskell too).

Lambda is a problem, if only because it causes confusion. What's the
problem? Glad you asked. The constructs DO NOT work the way most people
would expect them to, having limited knowledge of python! I ran into
this thing about seven years ago (when I was studying Haskell, and
Scheme) and I wanted to see how "pure functional" python was (well, not
at all really).

I can see uses for python's lambda. But, honestly, I think python could
deprecate its use and in five years just remove it from the language;
along with filter, map, and reduce !

I'm just saying;

marcus

[Chris Angelico]

On Sat, Mar 22, 2014 at 3:47 PM, Steven D'Aprano
<steve+comp....@pearwood.info> wrote:
> Now I'm not sure precisely how Haskell implements this trick, but it
> suggests to me that it creates a different closure each time around the
> loop of the comprehension. That could end up being very expensive.

It needn't be terribly expensive, if you make a "scope stack" or
"scope chain". Imagine, if you will, a system of scopes like this:

current_scope = None
class Scope:
def __init__(self, *a, **kw):
self.names = dict(*a, **kw)
global current_scope
self.parent = current_scope
current_scope = self
def __getitem__(self, name):
try:
return self.names[name]
except KeyError:
if self.parent is None: raise
return self.parent[name]
def __setitem__(self, name, value):
self.names[name] = value
def exit_scope():
global current_scope
current_scope = current_scope.parent

Creating a new scope would be fairly cheap (and a lot more so if this
were implemented in C without the object overhead, of course). Lookups
would scan up through a series of namespaces, same as they currently
do (local, module, builtins), there'd just be more of them. And the
compiler could be smart enough to skip creating a scope if there are
no assignments. There'd need to be some handling in there for the
'nonlocal' keyword, but my expectation is that 'global' is handled by
retaining a reference to the current_scope at module level, and
starting the search there for a LOAD_GLOBAL.

Each iteration of the loop could begin with Scope() and end with
exit_scope(), and there you are, each iteration in its own closable
scope.

I'm not saying it would be a good thing to do - and it'd be a bad fit
for Python, I think, as I said in my other post - but it could be
done.

ChrisA

[Rustom Mody]

On Saturday, March 22, 2014 10:21:13 AM UTC+5:30, Chris Angelico wrote:

> On Sat, Mar 22, 2014 at 3:39 PM, Rustom Mody wrote:
> >> So if that's not going to be broken, how is this fundamentally different?
> >> def func_loop():
> >> for x in 1,2,3:
> >> yield (lambda: x)
> > Thats using a for-loop
> > A 'for' in a comprehension carries a different intention, the matching names
> > being merely coincidental.

> So what you're saying is that these two are fundamentally different:

> def unrolled():
> x = 1
> yield (lambda: x)
> x = 2
> yield (lambda: x)
> x = 3
> yield (lambda: x)

> def loop():
> for x in 1,2,3:
> yield (lambda: x)

Well almost...

Except that the 'loop' I am talking of is one of

def loop():
return [yield (lambda: x) for x in [1,2,3]]
or
return (yield (lambda: x) for x in [1,2,3])
or just plain ol
(lambda x: for x in [1,2,3])

IOW loop is an imperative construct, comprehensions are declarative

Progressing through a loop in a sequential order is natural and to
be expected

Comprehensions being declarative, progressing through them
in some order is incidental.

> In other words, a loop should be implemented as a separate binding
> each time, not a rebinding. That's an interesting point, and it does
> make some sense; effectively, what you want is for the body of a for
> loop to be a new scope, a unique scope every iteration of the loop,
> and one that automatically closes over all variables in the parent
> scope (including for assignments) except for the loop
> iteration/counter variable.

> That does make some sense, but it doesn't really fit Python's concept.

Yes it does not fit in with imperative programming.

Its good to remember the history.
Haskell did not invent comprehensions

In programming, they started with Miranda where they were called
'ZF-expressions' after the Zermelo/Fraenkel of axiomatic set theory.

Because Russell's paradox had shaken the (intended) foundations of mathematics,
the way out (actually the one chosen by Zermelo and Fraenkel) was to
add a *comprehension axiom*

http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#3._Axiom_schema_of_specification_.28also_called_the_axiom_schema_of_separation_or_of_restricted_comprehension.29

What this basically mandates is that set constructions like
{x | Pred(x) } are disqualified (called unrestricted comprehension)

Only
{x ∈ S | Pred(x) } is a valid.

IOW sets cannot be concocted out of the blue but only out of other sets.

Fast forward 50 years and what David Turner – inventor of Miranda –- realized
is that if the programming language is sufficiently mathematical – ie no
imperative constructs plus lazy evaluation, then comprehensions are
actually constructive enough to make make into programming constructs.

However as Mark Harris points out imperative and functional thinking styles
remain somewhat inconsistent with each other.

[Rustom Mody]

On Saturday, March 22, 2014 10:21:13 AM UTC+5:30, Chris Angelico wrote:

> On Sat, Mar 22, 2014 at 3:39 PM, Rustom Mody wrote:
> >> So if that's not going to be broken, how is this fundamentally different?
> >> def func_loop():
> >> for x in 1,2,3:
> >> yield (lambda: x)
> > Thats using a for-loop
> > A 'for' in a comprehension carries a different intention, the matching names
> > being merely coincidental.

> So what you're saying is that these two are fundamentally different:



> def unrolled():
> x = 1
> yield (lambda: x)
> x = 2
> yield (lambda: x)
> x = 3
> yield (lambda: x)

> def loop():
> for x in 1,2,3:
> yield (lambda: x)

Well almost

Except that the 'loop' I am talking of is one of

def loop():
return [yield (lambda: x) for x in [1,2,3]]
or
return (yield (lambda: x) for x in [1,2,3])
or just plain ol
(lambda x: for x in [1,2,3])

IOW loops is an imperative construct, comprehensions are declarative

Progressing through a loop in a sequential order is natural and to
be expected

Comprehensions being declarative, progressing through them
in some order is incidental.

> In other words, a loop should be implemented as a separate binding
> each time, not a rebinding. That's an interesting point, and it does
> make some sense; effectively, what you want is for the body of a for
> loop to be a new scope, a unique scope every iteration of the loop,
> and one that automatically closes over all variables in the parent
> scope (including for assignments) except for the loop
> iteration/counter variable.

> That does make some sense, but it doesn't really fit Python's concept.

Yes it does not fit in with imperative programming.

Its good to remember the history.
Haskell did not invent comprehensions

In programming, they started with Miranda where they were called
'ZF-expressions' after the Zermelo/Fraenkel of axiomatic set theory.

Because Russell's paradox had shaken the (intended) foundations of mathematics,
the way out (actually the one chosen by Zermelo and Fraenkel) was to
add a *comprehension axiom*

http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#3._Axiom_schema_of_specification_.28also_called_the_axiom_schema_of_separation_or_of_restricted_comprehension.29

What this basically mandates is that set constructions like
{x | Pred(x) } are disqualified (called unrestricted comprehension)

Only
{x ∈ S | Pred(x) } is a valid.

IOW sets cannot be concoted out of the blue but only out of other sets.

FF 50 years and what David Turner – inventor of Miranda –- realized is that

if the programming language is sufficiently mathematical – ie no
imperative constructs plus lazy evaluation, then comprehensions are
actually constructive enough to make make into programming constructs.

However as Mark Harris points out imperative and functional thinking styles

remain confusingly inconsistent.

[Ian Kelly]

On Fri, Mar 21, 2014 at 8:06 PM, Rustom Mody <rusto...@gmail.com> wrote:
> Two: A comprehension variable is not bound but reassigned across the
> comprehension. This problem remains in python3 and causes weird behavior when
> lambdas are put in a comprehension

Because Python as a language only has the concept of assignment, not
binding. I think it would be weird and confusing if variables worked
this way in comprehensions and nowhere else.

> >>> fl = [lambda y : x+y for x in [1,2,3]]
> >>> [fl[i](2) for i in [0,1,2]]
> [5, 5, 5]

You can get the desired effect by adding a layer of indirection:

>>> fl = [(lambda x: lambda y: x+y)(x) for x in [1,2,3]]

>>> [f(2) for f in fl]

[3, 4, 5]

If that's too ugly then give the wrapper a proper name:

>>> def make_function(x):
... return lambda y: x+y
...
>>> fl = [make_function(x) for x in [1,2,3]]

>>> [f(2) for f in fl]

[3, 4, 5]

There is also the default argument trick:

>>> fl = [lambda y, *, x=x: x+y for x in [1,2,3]]

>>> [f(2) for f in fl]

[3, 4, 5]

[Steven D'Aprano]

On Fri, 21 Mar 2014 23:51:38 -0500, Mark H Harris wrote:

> Lambda is a problem, if only because it causes confusion. What's the
> problem? Glad you asked. The constructs DO NOT work the way most people
> would expect them to, having limited knowledge of python!

Why is that a problem? Would you consider it a problem that people who
don't understand BASIC can't understand BASIC? ("I don't get the
difference between GOTO and GOSUB. Obviously GOSUB is a problem and
should be throw out.") Do you think that the fact that people who have
never used a TI-89 calculator before may have trouble used a TI-89
calculator means that TI-89 calculators are "a problem"? (I've taught
school children who didn't know how to use their calculator.)

The problem is ignorance, not the calculator, and not lambda.

You've told us that "most people" (which people? dentists? lawyers?
illiterate tribesmen from the Amazon? professional programmers?) are
surprised by lamba's behaviour, but you haven't actually told us what
behaviour is surprising, or what "most people" expect lambda to do.
Perhaps you ought to?

> I ran into
> this thing about seven years ago (when I was studying Haskell, and
> Scheme) and I wanted to see how "pure functional" python was (well, not
> at all really).

Python is not a pure functional language, but you can write functional
code in it. If you want a pure functional language, you know where to
find one.

(I wonder whether, say, Haskell has the people coming along and demanding
that it should become more like Python?)

> I can see uses for python's lambda. But, honestly, I think python could
> deprecate its use and in five years just remove it from the language;
> along with filter, map, and reduce !

Python could deprecate many things. It would make Python a worse language.

By the way, are you aware that lambda is *identical* to def except for
three things?

- lambda is an expression, not a statement like def;

- the body of a function created with lambda is limited to a
single expression, not a block;

- the function object created with lambda has a generic name.


So unless the surprising behaviour about lambda that you're about to tell
us about relates to one of those three things, I *guarantee* that
functions created with def have the same surprising behaviour.

[Marko Rauhamaa]

Steven D'Aprano <steve+comp....@pearwood.info>:

> This makes perfect sense: by the time you call the functions, the name x
> has been rebound to the value 3.

> [...]

> Now I'm not sure precisely how Haskell implements this trick, but it
> suggests to me that it creates a different closure each time around
> the loop of the comprehension. That could end up being very expensive.

Haskell does not rebind variables. I guess Haskell simply physically
substitutes object references for each syntactic occurrence of a
variable.

If Python worked analogously, the following loop:

for i, x in enumerate([1, 2, 3]):
f[i] = lambda y: x + y

would unroll as follows:

f[0] = lambda y: 1 + y
f[1] = lambda y: 2 + y
f[2] = lambda y: 3 + y

That is actually how classic lambda calculus does it. Variables are
substituted, not "bound" or "assigned". They are syntactic slots. There
is no heap, there is no stack, there is no memory apart from the
expression itself.


Marko

[Marko Rauhamaa]

Ian Kelly <ian.g...@gmail.com>:

> You can get the desired effect by adding a layer of indirection:
>
>>>> fl = [(lambda x: lambda y: x+y)(x) for x in [1,2,3]]

A trick to remember! Variable lifetime reduction by function invocation.


Marko

[Mark Lawrence]

On 22/03/2014 02:06, Rustom Mody wrote:
>
> The same in haskell:
>
> Prelude> let fl = [\ y -> x + y | x <- [1,2,3]]
> Prelude> [(fl!!i) 0 | i<- [0,1,2]]
> [1,2,3]
>

My really big complaint about Python is that it's nothing like CORAL 66.
I think I'll raise this on python ideas in an attempt to get this
glaring deficiency corrected.

--
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com

[Rustom Mody]

On Saturday, March 22, 2014 2:39:56 PM UTC+5:30, Ian wrote:

> On Fri, Mar 21, 2014 at 8:06 PM, Rustom Mody wrote:
> > Two: A comprehension variable is not bound but reassigned across the
> > comprehension. This problem remains in python3 and causes weird behavior when
> > lambdas are put in a comprehension

> Because Python as a language only has the concept of assignment, not
> binding. I think it would be weird and confusing if variables worked
> this way in comprehensions and nowhere else.

Bizarre viewpoint!

When you do this:

> There is also the default argument trick:

> >>> fl = [lambda y, *, x=x: x+y for x in [1,2,3]]
> >>> [f(2) for f in fl]
> [3, 4, 5]

how is that not-a-binding solution?

More generally, insofar as variable-scopes can be made and exited, there
is binding. Its just that imperative languages have
- assignment wherein the shape of the environment is preserved but
its content is changed
- there are binding-constructs -- functions, methods, classes etc etc
-- which leave extant bindings intact but create/remove new ones.

Ok, functional languages have only the latter.
But only the former?? Beyond assembly language I dont know what
that would/could be...

[Mark Lawrence]

On 22/03/2014 09:09, Ian Kelly wrote:

> On Fri, Mar 21, 2014 at 8:06 PM, Rustom Mody <rusto...@gmail.com> wrote:
>> Two: A comprehension variable is not bound but reassigned across the
>> comprehension. This problem remains in python3 and causes weird behavior when
>> lambdas are put in a comprehension
>

> Because Python as a language only has the concept of assignment, not
> binding. I think it would be weird and confusing if variables worked
> this way in comprehensions and nowhere else.
>

My understanding has always been that an expression of the rhs is bound
to a name of the lhs. So is my understanding wrong, or is the above
wrong, or are we talking at cross purposes, or what?

[Marko Rauhamaa]

Mark Lawrence <bream...@yahoo.co.uk>:

> On 22/03/2014 09:09, Ian Kelly wrote:
>> Because Python as a language only has the concept of assignment, not
>> binding. I think it would be weird and confusing if variables worked
>> this way in comprehensions and nowhere else.
>
> My understanding has always been that an expression of the rhs is
> bound to a name of the lhs. So is my understanding wrong, or is the
> above wrong, or are we talking at cross purposes, or what?

Hard to say without knowing more of your understanding.

Even Scheme doesn't have purely classical variable binding because
variables can be assigned to. You will notice that right away when you
try to implement a lisp dialect; a purely binding (substituting)
implementation fails with set!/setq because there is no variable to
assign a value to.

Python variables are named memory slots you can peek and poke into. Not
so in a purely functional language where variables are physically
removed from the code before the code is executed.

Example:

def redouble(x):
return x + x

redouble(17 + 4)

If Python were simply binding variables in the purely functional sense,
the interpreter would first evaluate 17 + 4 and then make a copy of the
"redouble" function substituting the result (21) for each syntactic
occurrence of x:

def __redouble__234001942():
return 21 + 21

The interpreter would then proceed to evaluate the variable-less
function instance.

If you leave out assignment, there is really no difference between the
two models. Only if you don't have assignment, you don't need to
complicate your computational model with memory. Instead, you deal with
things like continuations.

In fact, even "def" violates the classic functional paradigm. For
example, to calculate 10's factorial without assignments, you can do
this (even in Python):

(lambda n: (lambda fac: fac(fac, n)) \
(lambda fac, n: 1 if n < 2 else n * fac(fac, n - 1)))(10)


Marko

[Rustom Mody]

The foll is fairly standard fare in denotational semantics -- please excuse
the length!

In order to understand (formally) the concept of 'variable'
we need to have at the least a concept of name(or identifier) -> value mapping.
This mapping is called an 'environment'

If we stop at that we get the 'simplest' (at least from a mathematical
pov!!) language -- λ calculus.

However programming languages also need to be implemented -- typically
on von Neumann machines. So we make 'Variable' a composition of two functions:
Env : Identifier -> Location
Store : Location -> Value

This seems fine and dandy until we realize that if the compositon is of
non one-one onto functions all kinds of troubles result; eg
-- Two locations going to one value -- aliasing
-- Store partial at a location -- uninitialized variable
etc etc the most innocuous looking…
-- assignment becomes a higher order function
because it converts a starting id -> -> value mapping to a new mapping


Seeing all these difficulties, some religious zealots (aka functional
programmers) decide that this composite mapping is the root of the problem
-- throw it out -- no aliasing, no assignment, no time. [Minor problem --
How to implement -- remains!]

The non-religious bigots (also called C programmers) see that managing
the Env at one time and the Store at a later time (the two times
are usually called compile-time and run-time but like bell-bottoms these
words are currently unfashionable!) can produce very effective engineering
expedience.

So strictly speaking whenever we have variables we have binding
[Probably mathematica is an exception... dunno for sure]

More loosely and conventionally if the mapping is a single direct one:
Env: Variable -> Value
as in λ calculus, functional languages etc, they are called binding-languages

To distinguish, the 'other' languages which need a
compose of Environment and Store are called variously:

- imperative language
- reference semantics
- conventional (imperative) variable (vs mathematical variable)
etc

IOW in most (normal) languages we have constructs to change the shape
of the environment and we have constructs to change the content of the
environment. The single pre-eminent way for the latter is assignment,
function is the typical way for the former.

[Unfortunately this is not universally true:
In C we have initialized variables that look like assignment but is not.
In python the exception is what Ian calls the default variable trick:
x=x would be a rather asinine assignment. But its not an assignment at all,
it just looks like one]

So no...

> My understanding has always been that an expression of the rhs is bound
> to a name of the lhs. So is my understanding wrong, or is the above
> wrong, or are we talking at cross purposes, or what?

assignment changes the content of the env, functions change the shape
-- which latter you may call binding.

[vasudevram]

Thanks to all those who answered.

- Vasudev

[Rhodri James]

On Sat, 22 Mar 2014 05:26:26 -0000, Rustom Mody <rusto...@gmail.com>
wrote:

> Well almost...
> Except that the 'loop' I am talking of is one of
> def loop():
> return [yield (lambda: x) for x in [1,2,3]]
> or
> return (yield (lambda: x) for x in [1,2,3])
> or just plain ol
> (lambda x: for x in [1,2,3])
> IOW loop is an imperative construct, comprehensions are declarative

I'm sorry, you've made a logical leap too far here. I understand loops
being imperative, but how are comprehensions declarative? What do they
declare that the loop equivalent doesn't.

You've made a great deal of the "for" in a comprehension not having the
same meaning as the "for" in a loop. That may well be true in the
equivalent Haskell constructs (I don't speak or write Haskell), but I
think you are wrong in Python. If so, please stop trying to write Haskell
in Python; you'll be as happy as the friend of mine I've finally persuaded
to stop writing Fortran in Python, I promise!

--
Rhodri James *-* Wildebeest Herder to the Masses

[Ian Kelly]

On Sat, Mar 22, 2014 at 6:32 PM, Rhodri James <rho...@wildebst.org.uk> wrote:
> On Sat, 22 Mar 2014 05:26:26 -0000, Rustom Mody <rusto...@gmail.com>
> wrote:
>
>> Well almost...
>> Except that the 'loop' I am talking of is one of
>> def loop():
>> return [yield (lambda: x) for x in [1,2,3]]
>> or
>> return (yield (lambda: x) for x in [1,2,3])
>> or just plain ol
>> (lambda x: for x in [1,2,3])
>> IOW loop is an imperative construct, comprehensions are declarative
>
>
> I'm sorry, you've made a logical leap too far here. I understand loops
> being imperative, but how are comprehensions declarative? What do they
> declare that the loop equivalent doesn't.

I'm with Rustom on this point. A list comprehension is a syntax for
building a list by declaring a transformation from some other iterable
object. Forget comprehensions for a moment and think of literals.
Would you not consider this to be declarative?

x = [1, 2, 3]

A comprehension is syntactically similar to a literal, with just a
different type of construction in mind.

Where I disagree is on the question of whether Python should therefore
break its established closure rules for lambdas that are nested inside
comprehensions versus functions that are not. It breaks the
equivalence between comprehensions and loops, and to my mind it
introduces significant complexity for relatively little gain.

[Rustom Mody]

On Sunday, March 23, 2014 8:16:28 AM UTC+5:30, Ian wrote:

> On Sat, Mar 22, 2014 at 6:32 PM, Rhodri James wrote:
> > wrote:
> >> Well almost...
> >> Except that the 'loop' I am talking of is one of
> >> def loop():
> >> return [yield (lambda: x) for x in [1,2,3]]
> >> or
> >> return (yield (lambda: x) for x in [1,2,3])
> >> or just plain ol
> >> (lambda x: for x in [1,2,3])
> >> IOW loop is an imperative construct, comprehensions are declarative
> > I'm sorry, you've made a logical leap too far here. I understand loops
> > being imperative, but how are comprehensions declarative? What do they
> > declare that the loop equivalent doesn't.

> I'm with Rustom on this point. A list comprehension is a syntax for
> building a list by declaring a transformation from some other iterable
> object. Forget comprehensions for a moment and think of literals.
> Would you not consider this to be declarative?

> x = [1, 2, 3]

> A comprehension is syntactically similar to a literal, with just a
> different type of construction in mind.

Aha! Very elegantly put!

> Where I disagree is on the question of whether Python should therefore
> break its established closure rules for lambdas that are nested inside
> comprehensions versus functions that are not.

No... see below

> It breaks the
> equivalence between comprehensions and loops, and to my mind it
> introduces significant complexity for relatively little gain.

[I am not completely sure whether the following can be proved/is true]

1. One can change lambda's closure rules which would amount to

"significant complexity for relatively little gain"

2. One can change comprehension rules to not reassign to the
running comprehension running varible but to rebind, using a recursive
function as the simulation of the comprehension rather than a for loop

3. 2 is semantically equivalent to 1
- trivially for normal (ie non-lambda containing) expressions
- and also for lambda containing expressions if your
default-argument trick is implemented by the python compiler
[This is the claim I am not completely sure of and would love to hear
of/if counter examples]

Assuming its true:

One *semantically specifies* a comprehension with a recursive function,
not a for loop

One *implements* a comprehension with the standard use of append
method inside a for as the expansion of a comprehension with the extra
caveat that interior lambdas are automatically wrapped inside a
default-argument binding for all outer comprehension variables.

A vanilla python programmer need not know anything about this any
more than a vanilla C programmer knows about
- strength reduction
- code hoisting
- loop unrolling
etc

that goes on inside an optimizing C compiler

[Ian Kelly]

On Sat, Mar 22, 2014 at 9:16 PM, Rustom Mody <rusto...@gmail.com> wrote:
> [I am not completely sure whether the following can be proved/is true]
>
> 1. One can change lambda's closure rules which would amount to
> "significant complexity for relatively little gain"
>
> 2. One can change comprehension rules to not reassign to the
> running comprehension running varible but to rebind, using a recursive
> function as the simulation of the comprehension rather than a for loop
>
> 3. 2 is semantically equivalent to 1

Well, if you accept that 1) amounts to significant complexity for
relatively little gain, and if 2) is semantically equivalent to 1),
then it follows that 2) also amounts to significant complexity for
relatively little gain. My statement was in regard to the complexity
of the language, not the implementation of the language.

> - trivially for normal (ie non-lambda containing) expressions
> - and also for lambda containing expressions if your
> default-argument trick is implemented by the python compiler
> [This is the claim I am not completely sure of and would love to hear
> of/if counter examples]

The disadvantage of the default argument trick is that it does modify
the function's signature, by adding an extra argument with a default,
so they're not entirely equivalent.

> Assuming its true:
>
> One *semantically specifies* a comprehension with a recursive function,
> not a for loop

The problem with this is a cognitive one. The comprehension *looks
like* a for loop, not a recursive function. It is natural to reason
about it as if it were a for loop, not a recursive function. This is
that added complexity I was talking about.

> A vanilla python programmer need not know anything about this any
> more than a vanilla C programmer knows about
> - strength reduction
> - code hoisting
> - loop unrolling
> etc
>
> that goes on inside an optimizing C compiler

Until they go to unroll their comprehension into a for loop because
they need to add some imperative construct to it, and their code
breaks as a result. From there you'll get the programmers who will
add functions with side effects to their comprehensions because they
want the comprehension binding behavior while still performing
imperative tasks within the loop.

[Rhodri James]

On Sun, 23 Mar 2014 02:46:28 -0000, Ian Kelly <ian.g...@gmail.com>
wrote:

> On Sat, Mar 22, 2014 at 6:32 PM, Rhodri James <rho...@wildebst.org.uk>
> wrote:
>> On Sat, 22 Mar 2014 05:26:26 -0000, Rustom Mody <rusto...@gmail.com>
>> wrote:
>>
>>> Well almost...
>>> Except that the 'loop' I am talking of is one of
>>> def loop():
>>> return [yield (lambda: x) for x in [1,2,3]]
>>> or
>>> return (yield (lambda: x) for x in [1,2,3])
>>> or just plain ol
>>> (lambda x: for x in [1,2,3])
>>> IOW loop is an imperative construct, comprehensions are declarative
>>
>>
>> I'm sorry, you've made a logical leap too far here. I understand loops
>> being imperative, but how are comprehensions declarative? What do they
>> declare that the loop equivalent doesn't.
> I'm with Rustom on this point. A list comprehension is a syntax for
> building a list by declaring a transformation from some other iterable
> object. Forget comprehensions for a moment and think of literals.
> Would you not consider this to be declarative?
>
> x = [1, 2, 3]

I'm not sure I would. I look at that line of code and think of it as
"Create a list...", very much in an imperative manner. Then again,
compared with C structs and typedefs and actual honest-to-God type
declarations, there's precious little in Python I would consider truly
declarative.