Personal Blogs

To turn the current stack implementation into an OOP one: working in PyCharm's project tree select 'stack.py'. Copy and then paste it back to Stacks with a name say, 'my_OOP_stack.py'. In the new file drag the cursor to select all the existing operations and press Tab once to move them within the record body. Then, with the functions still selected (complete lines required), press Ctrl + R. Find and Replace opens. In the top edit type stack and in the bottom edit self. Click [Replace all] and press Escape to close Find and Replace. The ADT stack is now an OOP class.

Moving the functions within the body has turned them into instance methods of stack. Generation of a new object using the class name as a function and the initialization provided by __init__ comprise a constructor for the class:

class stack:
    def __init__(self, max_size):
        self.array = array_(max_size)
        self.SP = 0     # the stack pointer
        self._max_size = max_size
    
    # .........

    def push(self, item):
        self.array[self.SP] = item
        self.SP += 1

    def pop(self):
        self.SP -= 1
        return self.array[self.SP]

Instance methods are fields of an instance and can be accessed like any other field using dot notation:

a_stack = stack(6)

push_stack = a_stack.push  # push is a field of a_stack
push_stack('||')           # pushes '||' onto a_stack

This is not normal usage and simply demonstrates the field properties of instance methods.

Here OOP brings two advantages: once an instance is created its instance methods are bound to that instance and the problem that a method might belong another class does not arise. Secondly, this binding means we can call a method without passing the instance as an explicit argument:

a_stack.push('item')
top_item = a_stack.pop()
print('stack size:', a_stack.size(), '  top:', a_stack(top)
# etc ...

The instance is passed implicitly to the self variable in the method's parameter list.

Should we wish to do so we can obtain an free (unbound) reference to a method from the class and pass the relevant instance to self explicitly

stack.push(a_stack, '22')

As of right now I can't think of any circumstance where this would be required. It allows an instance of one class to be passed to an instance method of another but doing that sounds quite fraught.

Testing the OOP stack

To test your OOP stack open the file my_OOP_stack_test.py. If you did not name your OOP stack script as suggested above modify the import command to import your version. Have a look at the code: it uses try...except to handle exceptions when they occur. Run the file and compare the output with the location of print statements in the code. When the final item 666 is pushed onto the corrupted stack it is at index 4 not at index 0 where it should be. 

All that remains is to fix the problem of stack corruption found in testing. In your my_OOP_stack.py modify push() and pop() to:

   def push(self, item):
       assert self.size() < self._max_size, 'stack overflow'
       self._array[self.SP] = item
       self.SP += 1

   def pop(self):
       assert self.size() > 0, 'stack underflow'
       self.SP -= 1
       return self.array[self.SP]

The assertions enforce the preconditions of push() and pop() by raising an AssertionError exception when the precondition is not satisfied. Note that assert is an operator not a function. Enclosing both its arguments with brackets will render the assertion always true. my_OOP_stack_test.py handles the exceptions raised by the assertions allowing execution to continue normally. Pushing 666 places it at index 0 where it should be.

Summary

In this section method binding to an instance was investigated, an aspect of OOP. A bound method was assigned to a variable and called. The more usual procedure of calling a method against an instance of a class with dot notation was used in the stack test script.

When a method is called in this way with the call directed to a method bound to the object currently referenced by a variable, the mechanism involved is known as dynamic dispatch. Languages like C++ that use static typing may also supply static dispatch: the method called depends on the declared type of the variable. Clearly this cannot be an alternative in Python where the type of an object is determined at runtime.

There are several flavours of dynamic dispatch: single dispatch as above, double dispatch and multiple dispatch where one or more argument types also figure in deciding the method the call is directed to. Python does not feature multiple dispatch out of the box but looks suited to implementing it fairly transparently. It uses late binding looking up methods by name in a dictionary subject to runtime modification when permitted by the class.

It seems there are also flavours of late binding: the Wikipedia article (Wikipedia 2015) notes use of a v-table as an example of early binding. This is the mechanism used by C++, noted in the same article as providing late binding even though the content and location of the v-table storing the addresses of dynamically dispatched methods is are computed at compile time.

The assertions introduced after testing prevented stack overflow and underflow when the preconditions of the stack operations push() and pop() were violated. Generally assertions are only used for debugging purposes and more permanent ways of dealing with this kind of problem will be discussed in a later article.

Algorithms 12 will investigate some more basic OOP features including inheritance and polymorphism.

Reference

Wikipedia (2015) Late Binding [Online], 1 August 2015. Available at https://en.wikipedia.org/wiki/Late_binding (Accessed 1 August 2015). 

[Algorithms 11: An OOP stack  (c) Martin Humby 2015]