Extra Homework 3
Due by 11:59pm on Thursday, 05/02
Instructions
Download extra03.zip. Inside the archive, you will find a file called extra03.py, along with a copy of the Ok autograder.
Submission: When you are done, submit with
python3 ok --submit
. You may submit more than once before
the deadline; only the final submission will be scored.
Using Ok
The ok
program helps you test your code and track your progress.
The first time you run the autograder, you will be asked to log in with your
@berkeley.edu account using your web browser. Please do so. Each time you run
ok, it will back up your work and progress on our servers.
You can run all the doctests with the following command:
python3 ok
To test a specific question, use the -q
option with the
name of the function:
python3 ok -q <function>
By default, only tests that fail will appear. If you
want to see how you did on all tests, you can use the -v
option:
python3 ok -v
If you do not want to send your progress to our server or you have any
problems logging in, add the --local
flag to block all
communication:
python3 ok --local
When you are ready to submit, run ok
with the
--submit
option:
python3 ok --submit
Readings: You might find the following references useful:
Alternative
If you enter the Scheme Recursive Art Contest (with a submission that demonstrates reasonable effort or creativity), then you can skip this extra homework assignment.
Q1: Interleave
Executing multiple threads in parallel can result in multiple different behaviors.
In many cases, there are only a finite set of possible environments that can result from executing a set of threads in parallel. The goal of this problem is to enumerate all of these possibilities. For this problem, we'll assume that an environment is just a single local frame.
Implement all_final_frames
, a function that takes an initial frame and a list
of threads. It returns a list of all possible final frames that could result
from executing those threads in parallel.
A frame is represented by a Python dictionary from names to values. A thread is
an instance of the Thread
class below. (Read it!)
class Thread:
"""A sequence of Python statements to be executed in order.
statements -- a list of strings; each string contains a Python statement.
lock (bool) -- whether all of the statements are executed atomically.
"""
def __init__(self, statements):
self.statements = statements
self.lock = False
If the lock
field of a Thread
instance is True
, then all of its statements
are executed atomically, without any other threads' statements interleaved.
Otherwise, its statements are still executed in order, but statements from other
threads may be interleaved.
The all_final_frames
function takes a dictionary called initial_state
and a
list of Thread
instances called threads
. The returned list of dictionaries
can have any order and can contain duplicates, as long as it contains all and
only the frames that result from fully executing all of the threads.
To simulate executing a single statement in a single-frame environment,
call execute
, which is provided for you:
def execute(statement, frame):
"""Execute a statement in the context of a frame and return the updated frame.
statement (string) -- contains a valid Python statement.
frame (dict) -- contains the values for local names.
>>> f = {'x': 2}
>>> execute('y = x + 3', f) == {'x': 2, 'y': 5}
True
>>> f
{'x': 2}
"""
assert 'statement' not in frame, frame
assert 'frame' not in frame, frame
assert 'statement' not in statement, statement
assert 'frame' not in statement, statement
locals().update(frame)
exec(statement)
result = locals().copy()
# Remove the formal parameters of execute before returning
result.pop('statement')
result.pop('frame')
return result
One way to implement all_final_frames
uses a recursive execute_all
helper function that populates a list of final_frames
.
increment = Thread(['y = x', 'x = y + 1'])
double = Thread(['z = x', 'x = z * 2'])
square = Thread(['t = x', 'x = t * t'])
def all_final_frames(initial_frame, threads):
"""
Return a list of all final frames that can result from executing a list
of threads in parallel.
Increment and double in parallel with no locks (like the diagram):
>>> s = all_final_frames({'x' : 10}, [increment, double])
>>> sorted(set(u['x'] for u in s))
[11, 20, 21, 22]
>>> sorted(set((u['x'], u['y'], u['z']) for u in s)) # x, y, z triples
[(11, 10, 10), (20, 10, 10), (21, 20, 10), (22, 10, 11)]
Increment then double, or double then increment (no interleaving):
>>> increment.lock = True
>>> double.lock = True
>>> s = all_final_frames({'x' : 10}, [increment, double])
>>> sorted(set(u['x'] for u in s))
[21, 22]
Increment, double, and square in parallel with no locks:
>>> increment.lock = False
>>> double.lock = False
>>> s = all_final_frames({'x' : 2}, [increment, double, square])
>>> sorted(set(u['x'] for u in s))
[3, 4, 5, 6, 8, 9, 10, 16, 17, 18, 25, 36]
...with two locks:
>>> increment.lock = True
>>> double.lock = True
>>> s = all_final_frames({'x' : 2}, [increment, double, square])
>>> sorted(set(u['x'] for u in s))
[4, 5, 8, 9, 10, 16, 17, 18, 25, 36]
...with three locks:
>>> square.lock = True
>>> s = all_final_frames({'x' : 2}, [increment, double, square])
>>> sorted(set(u['x'] for u in s))
[9, 10, 17, 18, 25, 36]
"""
final_frames = []
def execute_all(frame, threads):
"*** YOUR CODE HERE ***"
execute_all(initial_frame, threads)
return final_frames
Note: A typical implementation of execute_all
will include 15-25 lines of
code.
Use Ok to test your code:
python3 ok -q all_final_frames