If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.
You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!

Homework2

Page history last edited by Ras Bodik 13 years, 7 months ago

Homework 2: Improve Python's Desugaring of FOR constructs

Due: Monday, September 13, 10pm.

Edit: A hint has been added at the end of this handout. (Sunday 11:15am)

Submission Instructions: Please hand-in the homework using your instructional accounts. Submit a pdf file named "hw2.pdf" using the submit command. You can create the solutions in, say, Word or PowerPoint, from which you can export the pdf file.

The Problem: Python's implementation of for statements leads to surprising behavior. The root reason is not easy to spot; some even blame Python's lambdas rather than fors. Your goal is to understand the problem and propose implementation of for that does not lead to this surprising behavior.

Start by reading this post.

Next, understand our Python program that exposes this surprising behavior. We say that this program is surprising because we expected it to output

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

0 0

1 1

2 2

3 3

4 4

5 5

6 6

7 7

8 8

9 9

What does it output instead? You don't have to put the answer to this into your submission.

a = []
for i in xrange(0,10):
    a.append(lambda: i)
for j,v in enumerate(a):
    print j,v()
for i,v in enumerate(a):
    print i,v()

To help you understand the source of the surprising behavior, we show here (roughly) how Python desugars for loops into while loops. Let's assume that the above program is translated into this program by the parser.

a = []

# for i in xrange(0,10):

# a.append(lambda: i)

iterator = xrange(0,10).__iter__()

try:

while True:

i = iterator.next()

a.append(lambda: i)

except StopIteration:

pass

# for j,v in enumerate(a):

# print j,v()

iterator = enumerate(a).__iter__()

try:

while True:

j,v = iterator.next()

print j,v()

except StopIteration:

pass

# for i,v in enumerate(a):

# print i,v()

iterator = enumerate(a).__iter__()

try:

while True:

i,v = iterator.next()

print i,v()

except StopIteration:

pass

1. Draw the environment at the end of the 5th iteration of the last for loop. See below for instructions on how to draw the environment.

2. Develop an alternative desugaring that produces the desired output. Your solution must not use lambda's default values, i.e. by changing the lambda to lambda i=i: i.

3. Draw the environment at the end of the 5th iteration of the last loop in program desugared with your scheme.

How to draw the environment: your figures must show

the list a and its elements
all frames (scopes) still in use
all closure values still in use
the bodies of the functions (represent them as empty nodes)
(you must show where the variables i and j are stored and what their values are)

Hints:

When rewriting (ie, desugaring) the for loop, do not modify the body of the for statement. Typical desugaring works without the knowledge of what the code in the body is. It rewrites the for loop and then plugs in the body into the desugared for-loop code. So, you are asked to find desugaring of for such that the body of the remains a.append(lambda: i).