Object-Oriented Programming

Draft Version 555 (Thu Dec 1 09:18:27 2005)

How should a programmer represent XY points?
- Using a list of two numbers is convenient, but:
  - People reading the code have to remember (or guess) that p[1] means “the Y coordinate”
  - There's nothing to stop someone accidentally appending a third “coordinate”, or setting the X coordinate to "orange"
(Almost) all modern languages encourage programmers to define abstract data types
- Called abstract because they hide the details of their implementation
- Programmers interact with them through a limited set of operations, rather than by manipulating data directly
  - Fewer things can go wrong
  - Easier to read resulting code
  - Makes code easier to maintain, since internals can be changed without changing calling code
An ADT is usually created by defining a class, then creating one or more objects that are instances of that class
- All objects have the same methods (abilities), but their own state
- Changes to one object do not affect the state of others
Comment on this slide

A Naked Class

Define a class in Python using the class keyword
- Like other keywords, class is followed by ":", and introduces block
- Name of the new class is usually followed by object in parentheses
  - We'll see other options later
Create a new instance of the class by “calling” the class name as if it were a function
- If the class's body is pass, this creates a blank object
- See in a moment how to make objects more interesting
Most objects have data members that store their internal state
- A “personal” variable, like “my nose” or “my watch”
- Use the expression obj.data to access the data member of obj
  - Unlike C++ and Java, Python has no notion of “hiding” data members
Create data members simply by referring to them
- The expression obj.x = 3 either:
  - Gives obj a new member x, and assigns it the value 3, or
  - Overwrites the existing member x with the value 3
- Just like creating variables in a function

Example: an XY point

class point2d(object):
    pass

if __name__ == '__main__':
    p = point2d()
    p.x = 0.0
    p.y = 3.0
    print "point is", p
    print "coordiantes are", p.x, p.y

Comment on this slide

Methods

Naked classes are just glorified dictionaries
- Instead of obj['x'], have obj.x
Really become interesting when we start to define methods
- Any function defined inside a class belongs to that class
- When a method is called, Python passes the object itself as the method's first argument
  - Which means that every method must take at least one argument
  - By convention, it is called self
Why use methods?
- Make code easier to understand by grouping operations
- Give programmers a place to check the integrity of their ADTs
The expression obj.meth(arg) is equivalent to:
- Find the class that obj is an instance of
- Call that class's meth method with obj and arg as arguments
When a new object is created, Python checks whether the class has defined a method called __init__
- If it has, Python calls it before doing anything else
- This constructor can give the object its initial data members simply by assigning them values
Inside a method, refer to the object's data member as self.data
- Since the object was passed to the method as the parameter self
- The expression data is not the same as self.data
  - data on its own means “a local variable called data”

Example: a 2D point in the upper right quadrant

class point2d(object):

    # Constructor defines how to create new objects.
    def __init__(self):
        self.x = 0
        self.y = 0

    # Get X coordinate.
    def getX(self):
        return self.x

    # Set X coordinate.
    def setX(self, newX):
        assert newX >= 0
        self.x = newX

    # Get and set Y coordinate.
    def getY(self):
        return self.y

    def setY(self, newY):
        assert newY >= 0
        self.y = newY

    # Calculate norm.
    def norm(self):
        return math.sqrt(self.x ** 2 + self.y ** 2)

The __init__ constructor sets the point's initial coordinates
The getter methods replace raw read access

The setter methods check the constraints on the state of the class

If someone tries to assign a negative coordinate, the class will raise an exception
Fail early, fail often
Note: when testing the class, test the error handling too

# Tests.
if __name__ == '__main__':
    p = point2d()
    assert p.getX() == 0.0
    assert p.getY() == 0.0
    p.setX(3.0)
    p.setY(4.0)
    assert p.getX() == 3.0
    assert p.getY() == 4.0
    assert p.norm() == 5.0
    try:
        p.setX(-1.0)
        assert False
    except AssertionError:
        pass

Keep the memory model in mind when thinking about objects
- Figure 12.1: Memory Model
- A method is just a function that Python can call in a particular way
- You can call it directly if you want to
  - ```
      p = point2d()
      p.setX(9.0)
      p.setY(2.0)
      print "calling getX directly gives", point2d.getX(p)
```
```
  calling getX directly gives 9.0
```
Comment on this slide

Defining a Queue

A queue can do three things:
- Enqueue an item
- Dequeue the front item
  - Which raises an exception if the queue is empty
  - Remember, error behavior is part of a class's interface too
- Report whether it is empty or not
  - Which is less powerful than reporting its size
A queue may store items in many different ways
- The simplest in Python is probably to use a list…
- …but it isn't the only one…
- …and whoever is using the class shouldn't care
  - At least, not unless speed and/or memory requirements become an issue

Implementation:

class Queue(object):
    '''Implement a queue.'''

    def __init__(self):
        '''Construct an empty queue.'''
        self.data = []

    def enq(self, val):
        '''Add a new value to the end of the queue.'''
        self.data.append(val)

    def deq(self):
        '''Return the front value of the queue, or raise ValueError if
        the queue is empty.'''
        if len(self.data) == 0:
            raise ValueError, "Can't dequeue from empty queue"
        val = self.data[0]
        self.data = self.data[1:]
        return val

    def empty(self):
        '''Report whether the queue is empty or not.'''
        return len(self.data) == 0

Use docstrings instead of comments to document classes and methods (and functions)

Unlike comments, they are kept at runtime to provide interactive help

    print Queue.__doc__
    print Queue.enq.__doc__
    print q.deq.__doc__

Implement a queue.
Add a new value to the end of the queue.
Return the front value of the queue, or raise ValueError if
        the queue is empty.

raise ValueError instead of using assert when someone tries to dequeue from an empty queue
- The operation isn't a flaw in this code (which is what assertions are for)
- Question: should point2d.setX and point2d.setY have raised ValueError as well?

Always include tests

if __name__ == '__main__':
    q = Queue()
    assert q.empty()
    try:
        x = q.deq()
        assert False
    except ValueError:
        pass
    q.enq('first')
    assert not q.empty()
    q.enq('second')
    assert q.deq() == 'first'
    assert q.deq() == 'second'
    assert q.empty()

We'll see in the next two lectures how to do this systematically

Comment on this slide

Special Methods

__init__ is just one example of a special method
- All have names beginning and ending with double underscore
- Give programmers a way to make their data types look like those built into Python

Most widely used is probably __str__

When Python needs a string representation of an object, it sees if the object's class defines __str__
If it does, Python calls it, and uses the string it returns
If it doesn't, Python creates a default string representation

class first(object):

    def __init__(self, name):
        self.name = name

class second(object):

    def __init__(self, name):
        self.name = name

    def __str__(self):
        return 'second/"%s"' % self.name

f = first("orange")
print "first object is", f
s = second("apple")
print "second object is", s

first object is <__main__.first object at 0x401d982c>
second object is second/"apple"

Other examples:

If obj is an object, len(obj) calls obj.__len__()
- Easy to add to Queue to report how long the queue is
x in obj is equivalent to obj.__contains__(x)
- Would also be easy to add to Queue, but should we?
- Don't want to create “kitchen sink” classes

class Queue(object):

    def __init__(self):
        self.data = []

    def enq(self, val):
        self.data.append(val)

    def deq(self):
        if len(self.data) == 0:
            raise ValueError, "Can't dequeue from empty queue"
        val = self.data[0]
        self.data = self.data[1:]
        return val

    def __len__(self):
        return len(self.data)

    def empty(self):
        return self.__len__() == 0

if __name__ == '__main__':
    q = Queue()
    q.enq('first')
    q.enq('second')
    assert len(q) == 2
    q.deq()
    q.deq()
    assert q.empty()

Comment on this slide

Inheritance

What if we want two types of queue, one with __len__ and one without?
More realistically, suppose we have two types of people: professors and students
- They have a lot in common: names, email addresses, etc.
- But each has things the other doesn't (e.g., an office, or courses taught vs. courses taken)
- Really don't want to write each method twice
  - Anything repeated in two or more places will eventually be wrong in at least one.
The object-oriented solution is inheritance
- One class extends its parent class by adding new state and methods
  - Anything instances of the parent class can do, instances of the child class can do as well
  - But not vice versa
- Extend any class with any number of child classes
  - All children share the behavior of their parent
  - But are completely independent of one another

For example, define a Person as:

class Person(object):
    '''Represent generic traits of any person.'''

    def __init__(self, name, email):
        '''Create a new person with a name and an email address.'''
        self.name = name
        self.email = email

    def getName(self):
        return self.name

    def getEmail(self):
        return self.email

Then derive Professor:

class Professor(Person):
    '''Professors are more than people...'''

    def __init__(self, name, email, office):
        Person.__init__(self, name, email)
        self.office = office

    def getOffice(self):
        return self.office

Note that it's Professor(Person) instead of Professor(object)
- Signals that Professor extends Person instead of the generic built-in object class
Note also that Professor's constructor calls Person's
- Ensures that all of Person's initialization is done without duplicating code
- Ensures that changes to Person will automatically be reflected in Person

Now define Student:

class Student(Person):
    '''Students are more than people too...'''

    def __init__(self, name, email, program):
        Person.__init__(self, name, email)
        self.program = program

    def getProgram(self):
        return self.program

And run a few tests:

if __name__ == '__main__':
    tb = Professor('Tycho Brahe', 't.brahe@copenhagen.dk', 'Room 241')
    print tb.getName(), tb.getEmail(), tb.getOffice()

    jk = Student('Johannes Kepler', 'j.kepler@uraniborg.org', 'B.A.')
    print jk.getName(), jk.getEmail(), jk.getProgram()

Tycho Brahe t.brahe@copenhagen.dk Room 241
Johannes Kepler j.kepler@uraniborg.org B.A.

Comment on this slide

Polymorphism

Suppose we define Person.__str__, then override it with more specific definitions in Professor and Student

When Python looks for a method, it checks the object's class, then its parent class, and so on
Figure 12.2: Method Lookup
Result is that Python calls the most appropriate method for an object

class Person(object):
    def __init__(self, name, email):
        self.name = name
        self.email = email
    ...

    def __str__(self):
        return '%s (%s)' % (self.name, self.email)

class Professor(Person):
    def __init__(self, name, email, office):
        Person.__init__(self, name, email)
        self.office = office
    ...

    def __str__(self):
        result = Person.__str__(self)
        result += ' Room %s' % self.office
        return result

class Student(Person):
    def __init__(self, name, email, program):
        Person.__init__(self, name, email)
        self.program = program
    ...

    def __str__(self):
        result = Person.__str__(self)
        result += ' Program %s' % self.program
        return result

if __name__ == '__main__':
    crowd = [
        Professor('Tycho Brahe', 't.brahe@copenhagen.dk', 'Room 241'),
        Student('Johannes Kepler', 'j.kepler@uraniborg.org', 'B.A.')
    ]
    for person in crowd:
        print person

Tycho Brahe (t.brahe@copenhagen.dk) Room Room 241
Johannes Kepler (j.kepler@uraniborg.org) Program B.A.

Polymorphism means “having more than one form”
- In object-oriented programming, it means being able to treat different types of things as interchangeable
- E.g., if every class derived from Shape defines a method area, then obj.area() will return the area of obj without the caller having to know if obj is actually a square or a circle
Comment on this slide

The Substitution Principle

Python looks up each method when it's called
- So any two classes that define the same set of methods can be used interchangeably
However, the usual way to implement polymorphism is via inheritance
- Only override things that need to change
The Liskov Substitution Principle states that it should always be possible to replace an instance of a parent class with an instance of the child class
- Means that if Parent.meth returns a string, Child.meth must also return a string
- If Parent.meth returns a non-empty string with at least three vowels, Child.meth must as well
Often expressed in terms of pre-conditions and post-conditions
- Child.meth must satisfy all the post-conditions of Parent.meth, and may impose more
  - In other words, Child.meth's possible output is a subset of Parent.meth's
  - So any code that works correctly using the output of Parent.meth will continue to work if given an instance of Child instead
- Child.meth may ignore some of Parent.meth's pre-conditions, but may not impose more
  - Equivalently, Child.meth accepts everything thatParent.meth did, and possibly more
  - So any code that could call Parent.meth correctly is guaranteed to call Child.meth correctly too
Comment on this slide

Class Members

Sometimes want to share data between all instances of a class
- Constants, a count of the number of class instances created, etc.

Any data members defined inside the class block belong to the class as a whole

class Counter(object):

    num = 0     # Number of Counter objects created.

    def __init__(self, name):
        Counter.num += 1
        self.name = name

if __name__ == '__main__':
    print 'initial count', Counter.num
    first = Counter('first')
    print 'after creating first object', Counter.num
    second = Counter('second')
    print 'after creating second object', Counter.num

initial count 0
after creating first object 1
after creating second object 2

Can also define methods that belong to the class, rather than to particular objects
- Out of scope for this course, but often useful
Comment on this slide

Overloading Operators

(Almost) every feature of Python objects can be overridden by defining the right special method
- If done carefully, makes code much easier to read
- If done haphazardly, makes it almost impossible to understand
One common use is operator overloading
- The symbol "+" is just a shorthand for a function that takes two arguments
- If a class defines a method __add__, it takes precedence over the built-in “function”
  - So x + y calls x.__add__(y)
Of course, it's not quite that simple
- 2 + x and x + 2 don't always do the same thing
  - String concatenation
  - Matrix multiplication
- Classes can define right-hand versions of operators, e.g., __radd__ instead of __add__
  - If x has an __add__ method, call that
  - Otherwise, if y has an __radd__ method, call that
  - Otherwise, try Python's built-ins
Example: a vector is sparse if most of its entries are zero
- No point padding eleven actual values with nine million zeroes
- So use a dictionary to record non-zero values and their indices
- Addition: create a new vector with a non-zero value wherever either operand had a non-zero value
- Dot product: add up products of matching non-zero values
- Length: return one more than the index of the largest non-zero value
  - “One more” to be consistent with Python's lists
  - Hm…what is the length of v after:
```
v = SparseVector() # all values initialized to 0.0
v[27] = 1.0        # length is now 28
v[43] = 1.0        # length is now 44
v[43] = 0.0        # is the length still 44, or 28?
```
- This isn't a programming question; it's a data modeling question
  - What does the data in the program have to do to model the real world accurately?

The easy stuff

Construction creates an empty sparse vector
Its length is the largest index ever seen
- May or may not be sensible, but it's easy to implement

class SparseVector(object):
    '''Implement a sparse vector.  If a value has not been set
    explicitly, its value is zero.'''

    def __init__(self):
        '''Construct a sparse vector with all zero entries.'''
        self.values = {}

    def __len__(self):
        '''The length of a vector length is the largest index ever seen.'''
        if len(self.values):
            return max(self.values.keys())
        return 0

Making it look like a vector

Subscripting with [] is just a binary operator too
- obj[index] is implemented as obj.__getitem__(index)
- obj[index] = value is obj.__setitem(index, value)
- Note: all programming languages do this—the only question is whether they let you see it

    def __getitem__(self, key):
        '''Return an explicit value, or 0.0 if none has been set.'''
        if key in self.values:
            return self.values[key]
        return 0.0

    def __setitem__(self, key, value):
        '''Assign a new value to a vector entry.'''
        self.values[key] = value

Dot product
- The other object (on the right side of "*") is usually called other
- No reason to insist that it be a sparse vector
  - Could equally well be a list of values
- So loop over the indices of our own values, multiply by corresponding values in other object
  - Any index not encountered in this loop doesn't matter, since it corresponds to something that's zero
- ```
    def __mul__(self, other):
        '''Calculate cross product of a sparse vector with something else.'''

        result = 0.0
        for k in self.values.keys():
            result += self.values[k] * other[k]
        return result

    def __rmul__(self, other):
        return self.__mul__(other)
```
- Note: __rmul__ = __mul__ makes __rmul__ point to the same code as __mul__
  - There's no magic here: methods are functions, are objects, are things you can assign to names

Addition

Trickier than multiplication: result is non-zero wherever either argument is non-zero
Don't want to loop over all the zeroes of either argument
Solution: if the other object is a sparse vector, cheat
- I.e., reach inside it, and rely on details of its implementation

    def __add__(self, other):
        '''Add something to a sparse vector.'''

        # Initialize result with all non-zero values from this vector.
        result = SparseVector()
        result.values.update(self.values)

        # If the other object is also a sparse vector, add non-zero values.
        if isinstance(other, SparseVector):
            for k in other.values.keys():
                result[k] = result[k] + other[k]

        # Otherwise, use brute force.
        else:
            for i in range(len(other)):
                result[i] = result[i] + other[i]

        return result

    # Right-hand add does the same thing as left-hand add.
    __radd__ = __add__

And finally, some tests

if __name__ == '__main__':

    x = SparseVector()
    x[1] = 1.0
    x[3] = 3.0
    x[5] = 5.0
    print 'len(x)', len(x)
    for i in range(len(x)):
        print '...', i, x[i]

    y = SparseVector()
    y[1] = 10.0
    y[2] = 20.0
    y[3] = 30.0

    print 'x + y', x + y
    print 'y + x', y + x

    print 'x * y', x * y
    print 'y * x', y * x

    z = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5]

    print 'x + z', x + z
    print 'x * z', x * z
    print 'z + x', z + x

Comment on this slide