Extra Homework 3

Due by 11:59pm on Thursday, 05/02


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:


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}
    >>> 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

    result = locals().copy()

    # Remove the formal parameters of execute before returning
    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