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

Rustom Mody rustompmody at gmail.com
Sat Mar 22 19:42:42 CET 2014

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

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)

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.

More information about the Python-list mailing list