61A Homework 6

Due by 4pm on Wednesday, 2/29

You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)

cp ~cs61a/lib/hw/hw6.py .

Readings. Chapter 2.5

Q1. In lecture, we made total_deposits a static method, and had a class attribute __total_deposits to keep track of the value that total_deposits is to return. While this is fine as an example to explain a Python feature, it's not particularly good design. For one thing, it assumes that there is only one bank. It would be better to create another class to represent banks. Implement such a class, Bank, eliminating all use of class attributes. Accounts will behave as before, except that the total_deposits method applies only to banks, and the constructor for the Account class can be changed (it is never called directly by clients). We want the following behavior:

>>> third_national = Bank()
>>> second_federal = Bank()
>>> acct0 = third_national.make_account(1000)
>>> acct0.withdraw(100)
>>> acct1 = third_national.make_account(2000)
>>> third_national.total_deposits()
2900
>>> second_federal.total_deposits()
0
>>> acct1.total_deposits()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'Account' object has no attribute 'total_deposits'
>>> acct1.bank().total_deposits()
2900

Q2. Our bank accounts are not particularly secure. Suppose our Bank class wishes to provide additional security for account holders who want it (and presumably pay for it). Extend your solution to Question #1 so that aBank.make_secure_account(1000, "The magic woid") returns an account whose deposit, withdraw, and balance operations all take an extra, trailing argument that must match the passphrase "The magic woid" in order for the operation to work. Furthermore, do this in a particular way:

Do not modify Account, but instead create a subtype, SecureAccount.
Do not actually modify the account balances in SecureAccount. Instead, arrange that the methods of Account continue to handle that.

The desired behavior is like this:

>>> third_national = Bank()
>>> acct3 = third_national.make_secure_account(1000, "The magic woid")
>>> acct3.deposit(1000, 'The magic woid')
>>> acct3.balance('The magic woid')
2000
>>> acct3.balance('Foobar')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
SecurityError: wrong passphrase or account
>>> acct3.balance()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
SecurityError: passphrase missing

Q3. Implement an rlist class that gives us recursive lists, as in previous lectures and homework, but represented as a class.

rlist.empty() should be the empty rlist. There should be only one empty rlist object.
rlist(x, L) should be the rlist whose first is x and whose rest is L.
rlist(x) should be the same as rlist(x, rlist.empty()).
r.first() and r.rest() must provide the values previously provided by first(r) and last(r).
r.__len__() should return the length of r (including the case where r is the empty list). This is what the Python builtin function len calls.
r.__getitem__(k) should return element number k of r (numbering from 0). This is what Python calls to translate r[k].
r.__repr__() should return a string resembling a Python expression that would recreate r. This is partially defined in the skeleton. For the empty list, it should print rlist.empty().

However, any body for __len__ must consist of a single return statement containing only constants, integer arithmetic operations, or recursive calls of __len__ and nothing else! In particular, there may not be any tests of any kind in __len__. This restriction will affect how you implement the empty list. Do not fight this restriction! The idea is not to find a loophole, but rather to get into the spirit of OOP. The following is a sample use:

>>> L = rlist(0, rlist(1, rlist(2)))
>>> len(L)   # Calls L.__len__()
3
>>> L.rest().first()
2
>>> len(rlist.empty())
0

Hint: It's perfectly OK to define a class inside a class. In Python, this is used for defining classes that are used only in the implementation of another class.

Q4. You can make for work on rlists by defining some appropriate methods. Python translates the statement

for x in r: S

into essentially the following loop:

tmp = r.__iter__()
try:
    while True:
        x = tmp.__next__()
        S
except StopIteration:
    pass

That is, it calls a method __iter__ to get some kind of value (called an iterator). It then repeatedly calls the __next__ method of the resulting iterator object to get successive values from r. When the iterator has no more values, it stops the loop with the statement

raise StopIteration

Add the necessary definitions to your solution to Question 3 to allow for loops to work for rlists.

Q5. In lecture, I indicated that Python's object-oriented features are very dynamic compared to those of Java or C++. As one example, in Python, when an attribute reference obj.attr fails because attr is not defined in obj, Python tries evaluating obj.__getattr__("attr") to get the value of the attribute, if obj has the method __getattr__ defined. Then, if this method can't make sense of the request either, it is supposed to raise the exception AttributeError, and otherwise return some reasonable value in place of obj.attr.

Define a class Monitor that acts as a wrapper around objects that counts the number of times each attribute of that object is evaluated. A "monitored object" will behave just like the object itself, but as a side effect will maintain a dictionary mapping method names to counts of the number of times that method is called. We want the following behavior as an example (your solution should work for any type of object, not just Accounts):

>>> B = Bank()
>>> acct = B.make_account(1000)
>>> mon_acct = Monitor(acct)
>>> mon_acct.balance()
1000
>>> for i in range(10): mon_acct.deposit(100)
>>> mon_acct.withdraw(20)
>>> mon_acct.balance()
1980
>>> mon_acct.access_count('balance')
2
>>> mon_acct.access_count('deposit')
10
>>> mon_acct.access_count('withdraw')
1
>>> mon_acct.access_count('clear')
0
>>> L = list(mon_acct.attributes_accessed())
>>> L.sort()
>>> L
['balance', 'deposit', 'withdraw']

Q6. When dealing with a textual interface, it's often convenient to be able to abbreviate command names---using "con" instead of "continue" for example. We'd like a class that provides this feature. The class is instantiated with a list of command names. It has a method, complete, that takes an input input, cmnd, and, if possible, returns the full command name of which cmnd is an abbreviation. It succeeds if either cmnd is already the full name of a command in the original list, or cmnd is a prefix of exactly one command in the list. Another method, minimal_abbreviation, takes as input the full name of a command from the original list and returns the shortest string that uniquely abbreviates the command:

class Abbrev:
    """An abbreviation map."""

    def __init__(self, full_names):
        """Initialize self to handle abbreviations for the words
        in the sequence of strings full_names.  It is an error if
        a name appears twice in full_names."""
        # YOUR CODE HERE

    def complete(self, cmnd):
        """The member of my word list that the string cmnd
        abbreviates, if it exists and is unique.  cmnd abbreviates
        a string S in my word list if cmnd == S, or cmnd is a
        prefix of S and of no other command in my word list.
        Raises ValueError if there is no such S.
        >>> a = Abbrev(['continue', 'catch', 'next',
        ...             'st', 'step', 'command'])
        >>> a.complete('ne')
        'next'
        >>> a.complete('co')
        Traceback (most recent call last):
           ...
        ValueError: not unique: 'co'
        >>> a.complete('st')
        'st'
        >>> a.complete('foo')
        Traceback (most recent call last):
           ...
        ValueError: unknown command: 'foo'
        """
        # YOUR CODE HERE

    def minimal_abbreviation(self, cmnd):
        """The string, S, of shortest length such that
        self.complete(S) == cmnd.
        >>> a = Abbrev(['continue', 'catch', 'next',
        ...             'st', 'step', 'command'])
        >>> a.minimal_abbreviation('continue')
        'con'
        >>> a.minimal_abbreviation('next')
        'n'
        >>> a.minimal_abbreviation('step')
        'ste'
        >>> a.minimal_abbreviation('ste')
        Traceback (most recent call last):
           ...
        ValueError: unknown command: 'ste'
        """
        # YOUR CODE HERE

Q7. [Extra for experts] Another kind of wrapper class you might imagine to be useful is one that records all the arguments that are passed to a certain object's methods. Produce a class, ArgumentMonitor, that wraps around any object and keeps track of a set of all arguments, with the number of times each combination of arguments is used. For example:

>>> B = Bank()
>>> acct = B.make_account(1000)
>>> mon_acct = ArgumentMonitor(acct, ['balance', 'withdraw', 'deposit'])
>>> mon_acct.balance()
1000
>>> for i in range(10): mon_acct.deposit(100)
>>> mon_acct.withdraw(20)
>>> mon_acct.withdraw(10)
>>> mon_acct.balance()
1970
>>> d = mon_acct.argument_counts('balance')
>>> d[()]
2
>>> d = mon_acct.argument_counts('deposit')
>>> list(d.items())
[((100,), 10)]
>>> d = mon_acct.argument_counts['withdraw']
>>> d[(10,)]
1
>>> d[(20,)]
1
"""
# YOUR CODE HERE