Running the following code shows "2 1 4 3", but in reference manual
http://docs.python.org/reference/expressions.html#expression-lists
the evaluation order described as
{expr1: expr2, expr3: expr4}

def f(i):
    print i
    return i

{f(1):f(2), f(3):f(4)}

I found some of past discussions about this problem, for example,
http://mail.python.org/pipermail/python-dev/2002-November/030461.html
http://mail.python.org/pipermail/python-dev/2002-November/030458.html
http://bugs.python.org/issue448679
http://svn.python.org/view?view=rev&revision=30148
, but current implementation seems not to reflect these accomplishment.

In present, which behaviour is legal?

Here's a patch.

Working on a test case too.

It's not so easy as first appeared.

Okay, this looks better.  I was confusing myself with leftover .pyc
files I think.  Test included.

Georg,  I think this might need to sneak into 3.2.

I don't think so -- it's a very minor deviation from the spec and not a critical bug.

3.2 and earlier versions are all frozen, but for 3.3 it might make sense to bump the version number of the bytecode and change STORE_MAP to take the key and value in the opposite order, thus allowing to remove the ROT_TWO I had to add to make this work.

Interesting.  I would actually have expected the observed behavior.  I think of the : in a dictionary literal as an assignment.

BTW, it would be nice to know if this behavior was consistent with the docs at any time (the merge of the AST branch in 2.5 might be an obvious candidate where it was broken).

Also interesting would be what other implementations of Python do.

As Georg suggested, it is correct in 2.4, wrong in 2.5.

<sigh> If only a test had been checked-in eight years ago ...

It looks like a number of things have to be changed in order to bring behavior back to what the docs promise.  Dict literals and dict comprehensions need to be fixed in both the compile.py and compile.c.  To avoid introducing a ROT_TWO, the store STORE_MAP and MAP_ADD opcodes need minor modifications (just switch the u and w variable assignments).

takayuki, a special thanks to you for submitting such a well-researched bug report :-)

> To avoid introducing a ROT_TWO, the store STORE_MAP and MAP_ADD
> opcodes need minor modifications (just switch the u and w variable
> assignments).

Either of which would not be possible in anything other that 3.3 or 
later, right?

How much to change and how far to backport may make for a good python-dev discussion.  

ISTM that changing generated code goes hand-in-hand with changing opcode semantics (as long as the magic number gets bumped).  OTOH, none of this may be worth backporting at all since no one seems to have noticed or cared for eight years.   

I don't have any feelings about it one way or the other, but it would great to see Py3.2.1 get fixed properly.

If I understand, since the present patch uses present opcode semantics, adding a rotate, it could go into 2.7 and 3.2. Correct?

3.3 could get an improved patch that instead changed opcodes to expect key and value in the other order.

Today in pydev thread "chained assignment weirdity" Guido said
http://permalink.gmane.org/gmane.comp.python.devel/135746
"I agree that we should be *very* conservative in changing the
meaning of existing opcodes (adding new one is a different story)."
...
"Hm. I really don't think that is a good development for Python to
compromise in the area of expression evaluation order where side
effects are involved."
...

"I haven't looked at the proposed fixes, but I think correctness is more important than saving an extra bytecode (OTOH keeping the set of opcodes the same trumps both). I can't imagine that this extra opcode will be significant in many cases."

To which Nick C. replied
"Since you've indicated the implementation is in the wrong here and you
also want to preserve opcode semantics, I think Skip's patch is
correct, but also needs to be applied to dict comprehensions (now we
have them). The extra bytecode is only ROT_TWO, which is one of the
cheapest we have kicking around."

To which Guido said "Ok, somebody go for it! (Also please refer to my pronouncement in the bug"

I came across the same problem in #16777.

IMHO the current behavior is better, and the documentation should be fixed instead, for the following reasons:
 1) it's consistent with assignments, where the RHS is evaluated before the LHS (see also msg128500).  This should also be the behavior of the dict(k=v) syntax, and what I personally expect;
 2) changing it back is not backward-compatible with any code written during the last 10 years;
 3) keeping the current behavior and fixing the docs is simpler than fixing the code to match the docs;

In addition, I would avoid writing code with side-effects in a dict literal, even if the order was documented and guaranteed.  The fact that we don't see many reports about this seems to indicate that people don't write such code, or if they do they rely on the current order.

I am sticking with my opinion from before: the code should be fixed.  It doesn't look like assignment to me.

I am fine with making this a "feature" only fixed in 3.4.  (You can even fix the docs in 3.3 as long as you fix them back for 3.4.)

Minor note for Ezio: dict(k=v, ...) doesn't have this problem because k is just a keyword, not an expression.

Since this is documented in the Python Language Reference, it doesn't make much sense to have it describe one way for 3.3 and another for 3.4, does it?  By definition, doesn't that make this an implementation dependency?  We should update the docs to say that pairs in dicts will be evaluated left-to-right, but that the order of key and value is implementation dependent, since it actually is.

I strongly agree with Guido that we should fix the code. To me, defined left-to-right evaluation of sub-expressions within an expression is a feature. C's 'implementation defined' is a nuisance.

I do not think we should temporarily change the doc. In other cases where we have only applied a bugfix to a future version, we have not temporarily doc'ed the bug as 'correct'. The change *should* be in 
What's New.