Program 2

Classes, Overloaded Operators, and Iterators

ICS-33: Intermediate Programming


Introduction This programming assignment is designed first to ensure that you know how to write a simple (numeric) class that overloads many of the standard Python operators by defining various double-underscore methods. It also ensures that you know how to write a class that implements iterators, by defining both the __iter__ and __next__ methods. Finally it ensure that you know how to write iterator decorators by using special generators (similar to functions, but using yield instead of return) in a module.

There are three separate parts to this assignment. In the first part you will write a module defining a single, large numeric class that overloads many operators (including those performing arithmetic and relational comparisons). In the second part you will write a medium-size class, which defines various methods, including some double-underscore methods and specifically the iterator protocol methods (__iter__ and __next__). In the third part you will write a module that defines various iterator decorators implemented by generators: each iterator decorator has argument(s) that are iterators and is itself used an iterator.

You should download the program2 project folder and unzip it to produce an Eclipse project with three modules. You will write classes in the first two modules, which can be tested in the standard driver using the batch self-check files I supplied; you will write generators in the third module, which can also be tested by a batch self-check I supplied, but can are tested by a special generatordriver.py module included in this project. Eventually you will submit each of the three modules you write separately to Checkmate.

It is recommend that you work on this assignment in pairs, with someone in your lab section. Try to find someone who lives near you, with similar programming skills, and work habits/schedule: e.g., talk about whether you prefer to work mornings, nights, or weekends; what kind of commitment you will make to submit program early.

Only one student should submit all parts of the the assignment, but both student's names should appear in the comments at the top of each submitted .py file. It should look something like


# Romeo Montague, Lab 1
# Juliet Capulet, Lab 1
# We certify that we worked cooperatively on this programming
#   assignment, according to the rules for pair programming
If you do not know what the terms cooperatively and/or rules for pair programming mean, please read about Pair Programming before starting this assignment. Please turn in each program as you finish it, so that I can accurately assess the progress of the class as a whole during this assignment.

Print this document and carefully read it, marking any parts that contain important detailed information that you find (for review before you turn in the files). The code you write should be as compact and elegant as possible, using appropriate Python idioms.


Problem #1: Interval Class (operators)

Problem Summary:

Write a class that represents and defines operators for Interval numbers, which are represented by a pair numeric values: int, float or mixed. We use intervals to represent approximate numbers, whose exact value we do not know. For example, in physics we might know that the acceleration produced by the the force of gravity (g) at sea level is 9.8 m/s2 +/- .05 m/s2, which we will write as 9.8(+/-.05) m/s2. With this class we can perform numeric calculations on Interval objects, which automatically keep track of the precision for each calculated value.

For example, the formula sqrt(d/(2*g)) computes the amount of time it takes for an object at sea level to fall a given distance (d) in a vacuum. Given our approximation for g, and a distance that is 100(+/-1) m, we can use the Interval class to compute the amount of time it takes for an object to drop this amount as follows, including the precision with which we know the answer.

  g = Interval.mid_err(9.8,.05)
  d = Interval.mid_err(100,1)
  t = (d/(2*g)).sqrt()
  print(t)
So, with g known +/-.05 m/s2, and d known +/-1 m, the results print as 2.2587923826805945(+/-0.017056289680373204)), which indicates that the time will be somewhere between about 2.24 and 2.28 seconds, having a relative error of about 7.6%. Note that each Interval object will store the minimum and maximum value in the interval. So 9.8(+/-.05) is stored as an Interval with a minimum of 9.75 and a maximum of 9.85.

Details

  1. Define a class named Interval in a module named interval.py

  2. Define an __init__ method that has two parameters; their arguments specify the minimum and maximum values in the interval respectively. Store them in the self variables min and max. Programmers will not use this method directly to construct Interval objects; instead, they will use the static Interval.min_max and Interval.mid_err methods (described below).

    For information about static methods, read the Class Review lecture notes (look for the entry on Static Methods near the bottom, before the problems).

  3. Define a static min_max method that has two parameters; their arguments specify the minimum and maximum values in the interval. The second parameter is optional, with None as its default value. This method should raise an AssertionError exception, with an appropriate message, if (a) the first argument is not an int or float numeric type or (b) if the second argument is not a numeric type or None, or (c) the first argument is greater than the second; if the second argument is None, use the first argument for both the minimum and maximum value (creating an interval with one value representing exactly that number). Return the appropriate Interval object.

  4. Define a static mid_err method that has two parameters; their arguments specify the middle value and the +/- error for the interval. The second parameter is optional, with 0 as its default value. This method should raise an AssertionError exception, with an approprate message, if (a) the first argument is not an int or float numeric type, or (b) if the second argument is not a numeric type, or (c) if the second argument is negative. Return the appropriate Interval object. For example, Interval.mid_err(9.8,.5). would produce the same object as Interval.min_max(9.75,9.85).

  5. Define the methods best, error, and relative_error
    • best returns the best approximation for the Interval (the value at its middle).
    • error returns the error for the Interval: half the distance between its minimum and maximum values.
    • relative_error returns the absolute value of the ratio between the error over the best approximation as a percentage (multiply by 100).

  6. Define a __repr__ method that returns a string, which when passed to eval returns a newly constructed Interval with the same value as the object __repr__ was called on.

  7. Define a __str__ method that returns a string, with the best approximation for the Interval followed in parentheses by +/- followed by error bounds on the Interval. For example, str(Interval.mid_err(9.8,.5)) returns 9.8(+/-.5)

  8. Define a __bool__ method that returns True if the Interval represents an interval whose error is not zero: it has different minimum and maximum values.

  9. Define all the underscore methods needed to ensure the prefix +/- work correctly: + returns the same interval while - returns the appropriate negated interval.

  10. Define all the underscore methods needed to ensure that the add, subtract, multiply, and true divide (/) operators produce the correct answers when their operands are any combination of an Interval object with an Interval, int, or float object.

    Treat int and float values as exact/precise values (with no error). In all cases, carefully determine from the minimum and maximum values of the operand Interval(s), what the minimum and maximum values are in the result Interval: doing so requires a bit of deep thinking about arithmetic operators; in some cases it is useful to think about whether Interval is all negative, all positive, or contains 0: having a minimum <= 0 and maximum >= 0.

    If Python tries to apply an arithmetic operator to an Interval object and any other type of value, raise the standard TypeError exception with the standard messsage about unsupported operand types: see what 1+'a' produces in the Python interpreter. If a divisor's interval includes zero, it should raise the ZeroDivisionError, including an appropriate message with the offending denominator.

  11. Define all the underscore methods needed to ensure that the exponentiate operator (**) produces the correct answers when their left operand is an Interval object and their right operand is restricted to be an int object. Use repeated multiplication to solve this problem. In any other case, raise the standard TypeError exception with the standard messsage about unsupported operand types. Note that if p is negative, computing a**p is equivalent to computing (1/a)**(-p).

  12. Define all the underscore methods needed to ensure that we can compare Interval objects using the six standard relational operators, with any combination of an Interval object and an Interval, int, or float object.

    If Python tries to apply a relational operator to an Interval object and any other type of value, raise the standard TypeError exception with the standard messsage about unsupported operand types: see what 1<'a' produces in the Python interpreter.

    For == two Intervals are equal if they have the same minimum and maximum values; they != if either is different. Likewise, an int or float is never == to an Interval but always != to and Interval.

    For <, <=, >, >= the rules are more complex: they depend on whether the Interval class's compare_mode attribute is set to 'liberal' or 'conservative'. For example, when using the < operator in 'liberal' mode, the left argument is < the right when its best value is < the right's best value (or the right itself, if it is an int or float). When using the < operator in 'conservative' mode, the left argument is < the right when its maximum value is < the right's minimum value (or the right itself, if it is an int or float). The other operators work simliarly in 'liberal' and 'conservative' mode.

    In fact, these four operators should raise an AssertionError, with an appropriate message, if the Interval class has no compare_mode attribute or this attribute is bound to anything other than 'liberal' or 'conservative'.

  13. Python automatically provides meanings for +=, -=, *=, /=, and **=.

  14. Define
    • an __abs__ method for Interval values.
    • a sqrt method for Interval values.

  15. Define a __setattr__ method that ensures objects in the Interval class are immutable. The methods that you will write should never bind any instance name (except in __init__, which initializes them) but exclusively returns newly constructed Interval objects with the correct values. If an attempt is made to mutate an object (by defining a new attribute or rebinding an existing attribute), raise an AssertionError with an appropriate message.

Hint: I wrote five helper methods (all starting with _) to perform common tasks (four were static methods) in my class. If you find yourself writing similar code over and over, try to define and call a helper method to do the job. I made use of the form f(*g(..)) where function g returns a 2-tuple which * turns into 2 arguments for calling f.

Testing

The interval.py module includes a script that calls driver.driver(). The project folder contains a bsc1.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class: for example, getting one arithmetic (or relational) operator working correctly will create a pattern for the others.

Note that when exceptions are raised, they are printed by the driver but the Command: prompt sometimes appears misplaced.

We can write other code at the bottom of your interval.py module, before calling the driver, to test our Interval class: e.g., when testing + we can just define two Intervals and print their sum. You can also type such code into the driver as illustrated below, but if you want to perform the same test over and over again when debugging, it it better to put this code before the driver is called. Notice the default for each command is the command previously entered.

  Driver started
  Command[!]: from interval import Interval as I
  Command[from interval import Interval as I]: g = I.mid_err(9.8,1)
  Command[g = I.mid_err(9.8,1)]: print(g)
  9.8(+/-1.0)
  Command[print(g)]: print(2*g)
  19.6(+/-2.0)
  Command[print(2*g)]: I.compare_mode = 'conservative'
  Command[I.compare_mode = 'conservative']: print(9.75<g)
  False
  Command[print(9.75<g)]: print('9.75'<g)
  Traceback (most recent call last):
    ...
  TypeError: unorderable types: interval.Interval()>str()
  Command[print('9.75'<g)]: quit
  Driver stopped

Problem #2: Bag Class (iterators)

Problem Summary:

Write a class that represents and defines methods, operators, and iterators for a Bag class. Bags are similar to sets, and have similar operations (of which we will implement just the most important) but they can store multiple copies of items. Fundamentally, we will store bags as dictionaries (use defaultdict) whose elements are keys and whose values are the number of times the key occurs in the bag. You must store Bags using this data type as specified

Details

  • Define a class named Bag in a module named bag.py

  • Define an __init__ method that has one parameter, an iterable of values that initalize the bag. Writing Bag() constructs an empty bag. Writing Bag(['d','a','b','d','c','b','d']) construct a bag with one 'a', two 'b's, one 'c', and three 'd's.

  • Define a __repr__ method that returns a string, which when passed to eval returns a newly constructed bag with the same value (==) to the object __repr__ was called on. For example, for the Bag in the discussion of __init__ the __repr__ method would print its result as Bag(['a', 'c', 'b', 'b', 'd', 'd', 'd']). Bags like sets are not sorted, so these 7 values can appear in any order. We might require that information in the list is sorted, but not all values we might put in a bag may be ordered (and therefore not sortable).

  • Define a __str__ method that returns a string that more compactly shows a bag. For example, for the Bag in the discussion of __init__ the __str__ method would print its result as Bag(a[1], c[1], b[2], d[3]). Bags like sets are not sorted, so these 7 values can appear in any order.

  • Define a __len__ method that returns the total number of values in the Bag. For example, for the Bag in the discussion of __init__ the __len__ method would return 7.

  • Define a unique method that returns the number of different (unique) values in the Bag. For example, for the Bag in the discussion of __init__ the unique method would return 4, because there are four different values in the Bag; contrast this method with __len__.

  • Define a __contains__ method that returns whether or not its argument is in the Bag (one or more times).

  • Define a count method that returns the number of times its argument is in the Bag: 0 if the argument is not in the Bag.

  • Define an add method that adds its argument to the Bag: if that value is already in the Bag, its count is incremented by 1; if it is not already in the Bag, it is added to the Bag with a count of 1.

  • remove removes its argument from the Bag: if that value is already in the Bag, its count is decremented by 1 (and if the count reduces to 0 it is removed from the dict; if it is not in the Bag, raise a ValueError exception, with an appropriate message that includes the value that could not be removed.

  • Define __eq__/__ne__ methods that return whether one Bag is equal/not equal to another: contains the same values the same number of times. Comparing a Bag for equality to a non-Bag should raise a TypeError. Be careful and ensure that this method does not change either Bag.

  • Define an __iter__ method that that returns an object on which next can be called to produce every value in the Bag: all len of them. For example, for the Bag in the discussion of __init__, the following code
      for i in x:
          print(i,end='')
    would print
      acbbddd
    Bags like sets are not sorted, so these 7 values can appear in any order.

    Ensure that the iterator produces those values in the Bag at the time the iterator starts executing; so mutating the Bag during iteration will not affect what values it produces.

    Hint: I defined a generator as the class method to do this job.

I have shown only examples of Bags storing strings, because they are convenient to write. But bags can store any type of data. The __repr__, __str__, and __iter__/__next__ methods must be written independently: neither should call the other to get things done.

Testing

The bag.py module includes a script that calls driver.driver(). The project folder contains a bsc2.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class; check each method as you write it.

Note that when exceptions are raised, they are printed by the driver but the Command: prompt sometimes appears misplaced.

You can write other code at the bottom of your bag.py module to test the Bag class, or type code into the driver as illustrated below. Notice the default for each command is the command previously entered.

  Driver started
  Command[!]: from bag import Bag
  Command[from bag import Bag]: b = Bag(['d','a','b','d','c','b','d'])
  Command[b = Bag(['d','a','b','d','c','b','d'])]: print(b)
  Bag(a[1], b[2], c[1], d[3])
  Command[len(b)]: print(len(b))
  7
  Command[print(len(b))]: print(b.count('d'))
  3
  Command[print(b.count('d'))]: quit
  Driver stopped

Problem #3: Module of Decorators (iterators)

Problem Summary:

Write the following iterator decorators (iterators that operate on iterators) using Python generators. Write each function to be self contained, not calling any other functions or generators and do not use itertools.py module (or any other module that would trivialize this code); you may also not call the zip function.

Note that the argument passed to these generators can be anything that we can iterate: that includes strings, lists, tuples, dictionaries, and other generators: so, you cannot compute the len of the parameter because although strings, lists, tuples, and dictionariess have simple to compute lengths, generators don't.

Define space-efficient functions. They should not create temporary/local lists or tuples with all the values in their iterable parameters.

  • transform takes any iterable and any function whose domain includes all the iterated values: it produces transformed (by the function) values. For example
      for i in transform('abCdeFg',str.upper):
          print(i,end='')
    produces the values 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.

  • running_count takes any iterable and any predicate function (taking one argument and returning a bool value): it produces a running count of how many values up to (and including) the one just iterated over, satisfied the predicate. For example
      for i in count('bananastand', lambda x : x in 'aeiou'): # is vowel
        print(i,end=' ')
    produces the values 0, 1, 1, 2, 2, 3, 3, 3, 4, 4, and 4.

  • n_with_pad takes any iterable, an int n and a pad (whose default value is None): it produces the first n values from the iterable, padded by pad if there are fewer than n values in the iterable.
      for i n_with_pad('abcdefg',3):
        print(i,end=' ')
    produces the values 'a', 'b' and 'c'
      for i n_with_pad('abcdefg',10,'?'):
        print(i,end=' ')
    produces the values 'a', 'b', 'c', 'd', 'e', 'f', 'g', '?', '?' and '?'. Hint: use a for loop with a try/catch and explicit calls to iter and next.

  • sequence takes any number of iterables as parameters: it produces all the values in the first iterable, followed by all in the second, ... , all values in the last iterable. For example
      for i in sequence('abcd','ef','ghij'):
          print(i,end='')
    produces the values 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', and 'j'.

  • alternate takes any number of iterables as parameters: it produces the first value from the first parameter, then the first value from the the second parameter, ..., then the first value from the last parameter; then the second value from the first parameter, then the second value from the the second parameter, ..., then the second value from the last parameter; etc. If an iteratable produces no more values, it disappears from the alternation, and the process continues until there are no more iterables left.
      for i in alternate('abcde','fg','hijk'):
          print(i,end='')
    produces the values 'a', 'f', 'h', 'b', 'g', 'i', 'c', 'j', 'd', k, and 'e'. Hint: use a for loop nested in while loop with a try/catch and explicit calls to iter and next, along with a list of still active iteratables.

    Testing

    The generator.py module includes a script that calls driver.driver(). The project folder contains a bsc3.txt file (examine it) to use for batch-self-checking your class. These are rigorous but not exhaustive tests. Incrementally write and test your class; check each function as you write it.

    I have also provided the generatordriver.py module, which has the same tests as bsc3.txt but in a form more amenable for debugging these generators.