Abstract Data Types (ADTs)
An abstract data type is a set of objects and the operations on those objects. ADTs are an important concept that helps programmers manage complexity in their code. ADTs provide an abstraction easing the ability to pass an object from one part of a program to another, and in doing so provides access not only to the data attributes of the object but also to operations that make it easy to manipulate that data.
Operator Overloading is a programatic way to support the development of ADTs, and plays and important role in polymorphism, particularly for numeric/algebraic classes that implement an ADT.
As an example, let look at an ADT for Rational Numbers. Recall that rational numbers are numbers that can be given by form a/b where a and b are integers. We implement this ADT using the following class definition. In this definition there are two instance variables for the numerator n and denominator d, always stored in its canonical form of lowest terms, i.e., no common factor between n and d.
class Rational:
def __init__(self, a = 0, b = 1):
if b <= 0:
raise ValueError, ("Denom may not be zero or less!")
else:
g = gcd(a, b)
self.n = int(a / g)
self.d = int(b / g)
# Add a rational number to this rational number r2
def __add__(self, r2):
a = self.n * r2.d + self.d * r2.n
b = self.d * r2.d
return Rational(a, b)
# Subtract a rational number from this rational number r2
def __sub__(self, r2):
a = self.n * r2.d - self.d * r2.n
b = self.d * r2.d
return Rational(a, b)
# Multiply a rational number to this rational r2
def __mul__(self, r2):
a = self.n * r2.n
b = self.d * r2.d
return Rational(a, b)
# Divide a rational number by this rational number r2
def __div__(self, r2):
a = self.n * r2.d
b = self.d * r2.n
return Rational(a, b)
def __str__ ( self ):
return str(self.n) + "/" + str(self.d)
#An auxiliary helper function for constructor method of Rational Class
def gcd(a, b):
n1 = abs(a)
n2 = abs(b)
for k in range(1, min(n1,n2)+1):
if (n1 % k == 0) and (n2 % k == 0):
gcd = k
return gcd
#Client Usage
rat1=Rational(2,4)
rat2=Rational(3,9)
rat3 = rat1 + rat2
rat4 = rat1 - rat2
rat5 = rat1 * rat2
rat6 = rat1 / rat2
print rat1, rat2, rat3, rat4, rat5, rat6
#=> 1/2 1/3 5/6 1/6 1/6 3/2
Other Operators to Overload
See this document here for a full list of operators that may be overloaded.
Go ahead now and overload the == operator by defining a method
def __eq__(self, other).
Unit test your code by trying out the following:
if (Rational(1,2) == Rational(2,4)): print "Equality operator test passed" else: print "Test failed"
You may want to think for a bit about how you might implement the overloading of the exponentiation operator **, called __pow__ in Python. In the Lab exercises below, we will see how to solve this problem in a general way.
Exception Handling
Exceptions are another common abstraction in programming to handle cases at runtime that do not conform to usual cases. And since non-conforming cases happen all the time, we see exceptions all over production code. Virtually every module in the standard Python library uses them, and Python itself will raise them in many different circumstances. You’ve already seen some of them when types mismatch or attempts are made to index lists out of bounds. Open a Python shell and enter,
test = [1,2,3]; test[3]
and the interpreter will respond with something like:
IndexError: list index out of range
Traceback (most recent call last): test[3]
IndexError is the type of builtin exception that Python raises when a program tries to access an element that is not within the bounds of an indexable type. The Traceback string following IndexError provides additional information about what caused the exception to occur.
In addition to the type IndexError, other commonly occurring types of exceptions are TypeError, NameError, ZeroDivisionError, and ValueError. This last error type we use in the Rational constructor.
When an exception is raised that causes the program to terminate, we say that an unhandled exception has been raised. An exception does not need to lead to program termination. Exceptions, when raised, can and should be handled by the program. Sometimes an exception is raised because there is a bug in the program (like accessing a variable before it is defined, i.e., doesn’t exist yet), but many times, an exception is something the programmer can and should anticipate. Try-except blocks can be used to alter the flow of control of the program based on whether exceptions are raised, and will be covered in more detail in later chapter.
Monkey Patching
Monkey patching (think of Curious George) is a process of adding code locally to enhance a software system or class. In the following example, we add a float method to the the Rational Class so that we can see some number of decimal digits. Lets use our float patch to see the digits of pi emerge – in a celebration of pi day.
Client Code for Estimating Pi using Rational Class ADT
There are lots of estimates for pi, since mere mortals can only express a finite number of digits. Let us consider an estimate of pi based on throwing darts at random at a unit square. See image below: each random point that lies within the circle is red and those outside are colored blue. What is the ratio of red to blue points expected to be? What happens as the total number of points becomes very large? Suppose you got 4 points for hitting the target circle, and 0 points if you missed. What would you expect your score to be if you threw n darts at random?
import random
def estPi(numDarts):
inCircle = 0
for dart in xrange(1, numDarts + 1):
x = random.random()
y = random.random()
if (x*x + y*y)**0.5 < = 1.0:
inCircle += 1
return Rational(4*inCircle, numDarts)
def __float__(self):
return float(self.n)/float(self.d)
Rational.__float__ = __float__
for e in range(1, 30):
myPi = estPi(2**e)
print str(e) +"\t" + str(myPi) + "\t\t" + str(float(myPi))
>>>
1 2/1 2.0
2 4/1 4.0
3 4/1 4.0
4 3/1 3.0
5 13/4 3.25
6 55/16 3.4375
7 47/16 2.9375
8 205/64 3.203125
9 389/128 3.0390625
10 801/256 3.12890625
11 407/128 3.1796875
12 793/256 3.09765625
13 6393/2048 3.12158203125
14 3215/1024 3.1396484375
15 25613/8192 3.12658691406
16 3225/1024 3.1494140625
17 103051/32768 3.14486694336
18 51445/16384 3.13995361328
19 51399/16384 3.13714599609
20 411421/131072 3.13889312744
21 1647153/524288 3.14169502258
22 3293069/1048576 3.14051532745
23 3292699/1048576 3.14016246796
24 6588621/2097152 3.14169931412
25 26354285/8388608 3.14167559147
My computer can’t seem to reach the 30th estimate. Can yours?
Lab Exercises:
Task 1. Modify the program above using the graphics.py library, to produce an image like the one above.
Task 2. Understand the definition of complex number , and convince yourself that is is an ADT. You will design a class for Complex Numbers where instance variables consists of two floating point numbers a and b representing the real and imaginary parts of the complex number a + ib. The symbol i represents the square root of -1, or equivalently the square of i is – 1.
We have four ADT Operations: Addition, Subtraction Mulitplication, and Division and you can find their definitions here. Convince yourself that these operations are correct using the fact that i^2 = -1.
Write python class Complex for the complex numbers and its implementation, using the class Rational and its implementation as a guide. Implement the four ADT operations and overload the operators +, – , * and /.
Write a main program that has the user input two complex numbers, i.e., two pairs of floats representing the real and imaginary parts of the complex number, and output their sum and product.

Task 3. Computing Euler’s Famous Formula
We will empirically test the famous formula for complex numbers attributed to Leonhard Euler (d. 1783):
Wait! you say, how do you compute with an exponent that is complex. See this note concerning how exponentiation was extended in a historical progression from positive integers to negative integers, to rational numbers and finally to complex numbers, thus giving rise to the true meaning of Euler’s formula.
So to compute the exponential e^iπ we will use a series of objects from your Complex number ADT. Here you will be employing the following approximation (taken from the first few terms of Taylor-Maclaurin series expansion, an important concept from Calc2) for the exponential function f(z) = e^z :
e^z ≈ 1/0! + z/1! + z^2/2! + z^3/3! = 1 + z + (z*z)/2 + (z*z*z)/6.
Construct a new complex number object for each term of the series, then sum them up to see if your code and Euler’s result agrees.
Task 4a. (Analytic: Extra credit Homework)
Overload the ** power/exponentiation operation for the complex number class by defining the __pow__(self,c2) method. Your implementation should make use of the change of bases formula x^y = e^(logx)y, and make use of the Taylor-Maclaurin series expansion. Also you should throw a ValueError exception for when the base x of the exponential (x ** y) is not a positive real, for it is not as clear how to extend the definition of exponentiation. For example, (-1)^(1/2) could well be i or -i, (-1)^(1/3) could be -1, 1/2 + sqrt(3)i/2, or 1/2 – sqrt(3)i/2, and so on. Some values of x and y give infinitely many candidates for x^y, all equally plausible. You should create a set of unit tests, and include a check using the pow operator the correctness of Euler’s formula:
>>math.e**(math.pi)
23.140692632779263
>> Complex(math.e)**(Complex(0,1) * Complex(math.pi))
-1.0
Task 4b. (Creative: Extra credit Homework)
Python, unlike the language Ruby, does not allow us to do monkey patching to change the behavior of Python’s builtin types. However, within Python it is easy to just create a subclass of a class we would like to add a behavior to. For this assignment you are to create an algebraic language of string operations. You will do this by creating a subclass of the type str string class, and overloading operations for +,*,-,/, and any other symbols you would like to add to your algebraic language. Here is an example that adds the * operation to strings.
class mystr(str):
def __add__(self, other):
return (str(self) + str(other))
def __mul__(self, other):
return (str(other) + str(self))
x = mystr("abc")
y = mystr("cde")
print x+y, x*y
#=>abccde cdeabc
Compuzzle 
Discussion
No comments yet.