{ "cells": [ { "cell_type": "markdown", "id": "b098f5b8-9643-40eb-8dd5-cffd2d047c12", "metadata": {}, "source": [ "

ACOL106: Data Structures

\n", "

(Recap: Python Module 5)

\n", "(IMPORTANT NOTE: This module is not copied entirely from the book. I have kept only relevant material within this notebook. So, students are advised to read the book to get the full picture.)

\n", "\n", "We start this module with a discussion on inheritance, an essential concept in Object-oriented programming.\n", "\n", "

1. Inheritance

\n", "A natural way to organize various structural components of a software package is in a hierarchical fashion, with similar abstract definitions grouped together in a level-by-level manner that goes from specific to more general as one traverses up the hierarchy. An example of such a hierarchy is shown in the figure below. Using mathematical notations, the set of houses is a subset of the set of buildings, but a superset of the set of ranches. The correspondence between levels is often referred to as an “is a” relationship, as a house is a building, and a ranch is a house.\n", "\n", "\n", "\n", "A hierarchical design is useful in software development, as common functionality can be grouped at the most general level, thereby promoting the reuse of code, while differentiated behaviors can be viewed as extensions of the general case. In object-oriented programming, the mechanism for a modular and hierarchical organization is a technique known as inheritance. This allows a new class to be defined based upon an existing class as the starting point. In object-oriented terminology, the existing class is typically described as the base class, parent class, or superclass, while the newly defined class is known as the subclass or child class. There are two ways in which a subclass can differentiate itself from its superclass. A subclass may specialize an existing behavior by providing a new implementation that overrides an existing method. A subclass may also extend its superclass by providing brand new methods.\n", "\n", "

An example: Python's Exception hierarchy

\n", "Another example of a rich inheritance hierarchy is the organization of various exception types in Python. We introduced many of those classes in an earlier module, but did not discuss their relationship with each other. The figure below illustrates a (small) portion of that hierarchy. The BaseException class is the root of the entire hierarchy, while the more specific Exception class includes most of the error types that we have discussed. Programmers are welcome to define their own special exception classes to denote errors that may occur in the context of their application. Those user-defined exception types should be declared as subclasses of Exception.\n", "\n", "\n", "\n", "

1.1 Extending the CreditCard class

\n", "\n", "To demonstrate the mechanisms for inheritance in Python, we revisit the CreditCard class discussed in an earlier section. The class is given in the code segment below for experimentation." ] }, { "cell_type": "code", "execution_count": 1, "id": "e7211d10-aa5b-441f-98f5-5278aafb113f", "metadata": {}, "outputs": [], "source": [ "class CreditCard:\n", " \"\"\"A consumer credit card\"\"\"\n", "\n", " def __init__(self, customer, bank, actn, limit):\n", " \"\"\"Create a new credit card instance.\n", " The initial balance is zero.\n", "\n", " customer the name of the customer (e.g., John Bowman )\n", " bank the name of the bank (e.g., California Savings )\n", " acnt the acount identifier (e.g., 5391 0375 9387 5309 )\n", " limit credit limit (measured in dollars)\n", " \"\"\"\n", " self._customer = customer\n", " self._bank = bank\n", " self._account = actn\n", " self._limit = limit\n", " self._balance = 0\n", "\n", " def get_customer(self):\n", " \"\"\"Return the name of the customer\"\"\"\n", " return(self._customer)\n", "\n", " def get_bank(self):\n", " \"\"\"Return the bank's name\"\"\"\n", " return(self._bank)\n", "\n", " def get_account(self):\n", " \"\"\"Return the card identifying number (stored as a string)\"\"\"\n", " return(self._account)\n", "\n", " def get_limit(self):\n", " \"\"\"Return the current credit limit\"\"\"\n", " return(self._limit)\n", "\n", " def get_balance(self):\n", " \"\"\"Return the current balance\"\"\"\n", " return self._balance\n", "\n", " def charge(self, price):\n", " \"\"\"Charge given price to the card, assuming sufficient credit limit.\n", " Return True if charge was processed; False if charge was denied.\n", " \"\"\"\n", " if price+self._balance > self._limit:\n", " return(False)\n", " else:\n", " self._balance += price\n", " return(True)\n", "\n", " def make_payment(self, amount):\n", " \"\"\"Process customer payment that reduces the balance\"\"\"\n", " self._balance -= amount\n", " " ] }, { "cell_type": "markdown", "id": "b7d44d23-a947-471f-9dea-84a18b763035", "metadata": {}, "source": [ "We shall implement a subclass that, for lack of a better name, we name PredatoryCreditCard. The new class will differ from the original in two ways: (1) if an attempted charge is rejected because it would have exceeded the credit limit, a $5 fee will be charged, and (2) there will be a mechanism for assessing a monthly interest charge on the outstanding balance, based upon an Annual Percentage Rate (APR) specified as a constructor parameter.
\n", "\n", "In accomplishing this goal, we demonstrate the techniques of specialization and extension. To charge a fee for an invalid charge attempt, we override the existing charge method, thereby specializing it to provide the new functionality (although the new version takes advantage of a call to the overridden version). To provide support for charging interest, we extend the class with a new method named process_month. The figure below provides an overview of our use of inheritance in designing the new PredatoryCreditCard class, and the code segment below gives a complete Python implementation of that class.\n", "\n", "" ] }, { "cell_type": "code", "execution_count": 2, "id": "95a6fb21-6124-4ef2-9ccb-e7b88ef2cac2", "metadata": {}, "outputs": [], "source": [ "class PredatoryCreditCard(CreditCard):\n", " \"\"\"An extension to CreditCard that compounds interest and fees.\"\"\"\n", "\n", " def __init__(self, customer, bank, acnt, limit, apr):\n", " \"\"\"Create a new predatory credit card instance.\n", "\n", " The initial balance is zero.\n", "\n", " customer the name of the customer (e.g., John Bowman )\n", " bank the name of the bank (e.g., California Savings )\n", " acnt the acount identifier (e.g., 5391 0375 9387 5309 )\n", " limit credit limit (measured in dollars)\n", " apr annual percentage rate (e.g., 0.0825 for 8.25% APR)\n", " \"\"\"\n", " super().__init__(customer, bank, acnt, limit) # call super constructor\n", " self._apr = apr\n", "\n", " def charge(self, price):\n", " \"\"\"Charge given price to the card, assuming sufficient credit limit.\n", "\n", " Return True if charge was processed.\n", " Return False and assess 5 fee if charge is denied.\n", " \"\"\"\n", " success = super().charge(price) # call inherited method\n", " if not success:\n", " self._balance += 5 # assess penalty\n", " return success # caller expects return value\n", "\n", " def process_month(self):\n", " \"\"\"Assess monthly interest on outstanding balance.\"\"\"\n", " if self._balance > 0:\n", " # if positive balance, convert APR to monthly multiplicative factor\n", " monthly_factor = pow(1 + self._apr, 1/12)\n", " self._balance *= monthly_factor" ] }, { "cell_type": "markdown", "id": "6fd97792-e9a4-468e-911f-ed8fc9fdcaec", "metadata": {}, "source": [ "To indicate that the new class inherits from the existing CreditCard class, our definition begins with the syntax, class PredatoryCreditCard(CreditCard). The body of the new class provides three member functions: \\_\\_init\\_\\_, charge, and process_month. The \\_\\_init\\_\\_ constructor serves a very similar role to the original CreditCard constructor, except that for our new class, there is an extra parameter to specify the annual percentage rate. The body of our new constructor relies upon making a call to the inherited constructor to perform most of the initialization (in fact, everything other than the recording of the percentage rate). The mechanism for calling the inherited constructor relies on the syntax, super(). Specifically, the command:\n", "
\n",
    "    super().__init__(customer, bank, acnt, limit)\n",
    "
\n", "calls the \\_\\_init\\_\\_ method that was inherited from the CreditCard superclass. Note well that this method only accepts four parameters. We record the APR value in a new field named _apr.
\n", "\n", "In a similar fashion, our PredatoryCreditCard class provides a new implementation of the charge method that overrides the inherited method. Yet, our implementation of the new method relies on a call to the inherited method, with syntax super().charge(price). The return value of that call designates whether the charge was successful. We examine that return value to decide whether to assess a fee, and in turn, we return that value to the caller of the method, so that the new version of charge has a similar outward interface as the original.
\n", "\n", "The process_month method is a new behavior, so there is no inherited version upon which to rely. In our model, this method should be invoked by the bank once each month to add new interest charges to the customer’s balance. The most challenging aspect in implementing this method is making sure we have a working knowledge of how an annual percentage rate translates to a monthly rate. We do not simply divide the annual rate by twelve to get a monthly rate (that would be too predatory, as it would result in a higher APR than advertised). The correct computation is to take the twelfth root of 1 + self._apr, and use that as a multiplicative factor. For example, if the APR is 0.0825 (representing 8.25%), we compute (1.0825)^(1/12) ≈ 1.006628, and therefore charge 0.6628% interest per month. In this way, each 100 units of debt will amass 8.25 units of compounded interest in a year.\n", "\n", "

Protected Members

\n", "Our PredatoryCreditCard subclass directly accesses the data member self._balance, which was established by the parent CreditCard class. The underscored name, by convention, suggests that this is a nonpublic member, so we might ask if it is okay that we access it in this fashion. While general users of the class should not be doing so, our subclass has a somewhat privileged relationship with the superclass. Several object-oriented languages (e.g., Java, C++) draw a distinction between nonpublic members, allowing declarations of protected or private access modes. Members that are declared as protected are accessible to subclasses, but not to the general public, while members that are declared as private are not accessible to either. In this respect, we are using _balance as if it were protected (but not private).
\n", "\n", "Python does not support formal access control, but names beginning with a single underscore are conventionally akin to protected, while names beginning with a double underscore (other than special methods) are akin to private. In choosing to use protected data, we have created a dependency in that our PredatoryCreditCard class might be compromised if the author of the CreditCard class were to change the internal design. Note that we could have relied upon the public get_balance() method to retrieve the current balance within the process_month method. But the current design of the CreditCard class does not afford an effective way for a subclass to change the balance, other than by direct manipulation of the data member. It may be tempting to use charge to add fees or interest to the balance. However, that method does not allow the balance to go above the customer’s credit limit, even though a bank would presumably let interest compound beyond the credit limit, if warranted. If we were to redesign the original CreditCard class, we might add a nonpublic method, set_balance, that could be used by subclasses to affect a change without directly accessing the data member _balance.\n", "\n", "

1.2 Another example: Hierarchy of numeric progressions

\n", "As a second example of the use of inheritance, we develop a hierarchy of classes for iterating numeric progressions. A numeric progression is a sequence of numbers, where each number depends on one or more of the previous numbers. For example, an arithmetic progression determines the next number by adding a fixed constant to the previous value, and a geometric progression determines the next number by multiplying the previous value by a fixed constant. In general, a progression requires a first value and a way of identifying a new value based on one or more previous values.
\n", "\n", "To maximize the reusability of code, we develop a hierarchy of classes stemming from a general base class that we name Progression (see Figure below). Technically, the Progression class produces the progression of whole numbers: 0, 1, 2, .... However, this class is designed to serve as the base class for other progression types, providing as much common functionality as possible, and thereby minimizing the burden on the subclasses.\n", "\n", "\n", "\n", "Our implementation of the basic Progression class is provided in the code segment below. The constructor for this class accepts a starting value for the progression (0 by default) and initializes a data member, self._current, to that value." ] }, { "cell_type": "code", "execution_count": 3, "id": "67ac4aa2-7b4a-4c6c-a299-3cf1f38372e0", "metadata": {}, "outputs": [], "source": [ "class Progression:\n", " \"\"\"Iterator producing a generic progression.\n", "\n", " Default iterator produces the whole numbers 0, 1, 2, ...\n", " \"\"\"\n", "\n", " def __init__(self, start=0):\n", " \"\"\"Initialize current to the first value of the progression.\"\"\"\n", " self._current = start\n", "\n", " def _advance(self):\n", " \"\"\"Update self. current to a new value.\n", "\n", " This should be overridden by a subclass to customize progression.\n", "\n", " By convention, if current is set to None, this designates the\n", " end of a finite progression.\n", " \"\"\"\n", " self._current += 1\n", "\n", " def __next__(self):\n", " \"\"\"Return the next element, or else raise StopIteration error.\"\"\"\n", " if self._current is None: # our convention to end a progression\n", " raise StopIteration()\n", " else:\n", " answer = self._current # record current value to return\n", " self._advance() # advance to prepare for next time\n", " return answer # return the answer \n", "\n", " def __iter__(self):\n", " \"\"\"By convention, an iterator must return itself as an iterator.\"\"\"\n", " return self\n", "\n", " def print_progression(self, n):\n", " \"\"\"Print next n values of the progression.\"\"\"\n", " print(' '.join(str(next(self)) for j in range(n)))" ] }, { "cell_type": "markdown", "id": "b13cb238-cbfa-4aa6-8dba-4fa3280557d0", "metadata": {}, "source": [ "The Progression class implements the conventions of a Python iterator, namely the special \\_\\_next\\_\\_ and \\_\\_iter\\_\\_ methods. If a user of the class creates a progression as seq = Progression(), each call to next(seq) will return a subsequent element of the progression sequence. It would also be possible to use a for-loop syntax, for value in seq:, although we note that our default progression is defined as an infinite sequence.
\n", "\n", "To better separate the mechanics of the iterator convention from the core logic of advancing the progression, our framework relies on a nonpublic method named _advance to update the value of the self._current field. In the default implementation, _advance adds one to the current value, but our intent is that subclasses will override _advance to provide a different rule for computing the next entry. For convenience, the Progression class also provides a utility method, named print_progression, that displays the next n values of the progression.\n", "\n", "

An arithmetic progression class

\n", "Our first example of a specialized progression is an arithmetic progression. While the default progression increases its value by one in each step, an arithmetic progression adds a fixed constant to one term of the progression to produce the next. For example, using an increment of 4 for an arithmetic progression that starts at 0 results in the sequence 0,4,8,12,....
\n", "\n", "The code segment below presents our implementation of an ArithmeticProgression class, which relies on Progression as its base class. The constructor for this new class accepts both an increment value and a starting value as parameters, although default values for each are provided. By our convention, ArithmeticProgression(4) produces the sequence 0,4,8,12,... , and ArithmeticProgression(4, 1) produces the sequence 1,5,9,13,....
\n", "\n", "The body of the ArithmeticProgression constructor calls the super constructor to initialize the _current data member to the desired start value. Then it directly establishes the new _increment data member for the arithmetic progression. The only remaining detail in our implementation is to override the _advance method so as to add the increment to the current value." ] }, { "cell_type": "code", "execution_count": 4, "id": "f321783b-ecfa-4492-af3f-96f724567354", "metadata": {}, "outputs": [], "source": [ "class ArithmeticProgression(Progression): \n", " \"\"\"Iterator producing an arithmetic progression.\"\"\"\n", " # inherit from Progression\n", "\n", " def __init__(self, increment=1, start=0):\n", " \"\"\"Create a new arithmetic progression.\n", "\n", " increment 8 start the fixed constant to add to each term (default 1)\n", " the first term of the progression (default 0)\n", " \"\"\"\n", " super().__init__(start) # initialize base class\n", " self._increment = increment\n", "\n", " def _advance(self): \n", " \"\"\"Update current value by adding the fixed increment.\"\"\"\n", " self._current += self._increment" ] }, { "cell_type": "markdown", "id": "4fdbe783-db4b-4d50-97b4-492a9af6c946", "metadata": {}, "source": [ "

A geometric progression class

\n", "Our second example of a specialized progression is a geometric progression, in which each value is produced by multiplying the preceding value by a fixed constant, known as the base of the geometric progression. The starting point of a geometric progression is traditionally 1, rather than 0, because multiplying 0 by any factor results in 0. As an example, a geometric progression with base 2 proceeds as 1,2,4,8,16,....
\n", "\n", "The code segment below presents our implementation of a GeometricProgression class. The constructor uses 2 as a default base and 1 as a default starting value, but either of those can be varied using optional parameters." ] }, { "cell_type": "code", "execution_count": 5, "id": "cf31a0d8-73c9-493f-89e1-146afbe7197e", "metadata": {}, "outputs": [], "source": [ "class GeometricProgression(Progression):\n", " \"\"\"Iterator producing a geometric progression.\"\"\"\n", " # inherit from Progression\n", "\n", " def __init__(self, base=2, start=1):\n", " \"\"\"Create a new geometric progression.\n", "\n", " base the fixed constant multiplied to each term (default 2)\n", " start the first term of the progression (default 1)\n", " \"\"\"\n", " super().__init__(start)\n", " self._base = base\n", "\n", " def _advance(self): # override inherited version\n", " \"\"\"Update current value by multiplying it by the base value.\"\"\"\n", " self._current *= self._base" ] }, { "cell_type": "markdown", "id": "deb26df9-a4bc-46ee-aa90-ea9d06c9f54d", "metadata": {}, "source": [ "

A Fibonacci progression class

\n", "As our final example, we demonstrate how to use our progression framework to produce a Fibonacci progression. Each value of a Fibonacci series is the sum of the two most recent values. To begin the series, the first two values are conventionally 0 and 1, leading to the Fibonacci series 0,1,1,2,3,5,8,.... More generally, such a series can be generated from any two starting values. For example, if we start with values 4 and 6, the series proceeds as 4,6,10,16,26,42,....
\n", "\n", "We use our progression framework to define a new FibonacciProgression class, as shown in the code segment below. This class is markedly different from those for the arithmetic and geometric progressions because we cannot determine the next value of a Fibonacci series solely from the current one. We must maintain knowledge of the two most recent values. The base Progression class already provides storage of the most recent value as the _current data member. Our FibonacciProgression class introduces a new member, named _prev, to store the value that preceded the current one.
\n", "\n", "With both previous values stored, the implementation of advance is relatively straightforward. (We use a simultaneous assignment) However, the question arises as to how to initialize the previous value in the constructor. The desired first and second values are provided as parameters to the constructor. The first should be stored as _current so that it becomes the first one that is reported. Looking ahead, once the first value is reported, we will do an assignment to set the new current value (which will be the second value reported), equal to the first value plus the “previous.” By initializing the previous value to (second− first), the initial advancement will set the new current value to first + (second− first) = second, as desired." ] }, { "cell_type": "code", "execution_count": 6, "id": "cc9ea849-ebf1-485c-9f62-3f541a658357", "metadata": {}, "outputs": [], "source": [ "class FibonacciProgression(Progression):\n", " \"\"\"Iterator producing a generalized Fibonacci progression.\"\"\"\n", "\n", " def __init__(self, first=0, second=1):\n", " \"\"\"Create a new fibonacci progression.\n", "\n", " first the first term of the progression (default 0)\n", " second the second term of the progression (default 1)\n", " \"\"\"\n", " super().__init__(first) # start progression at first\n", " self._prev = second - first # fictitious value preceding the first\n", "\n", " def _advance(self):\n", " \"\"\"Update current value by taking sum of previous two.\"\"\"\n", " self._prev, self._current = self._current, self._prev + self._current" ] }, { "cell_type": "markdown", "id": "d10919f2-6a8c-4c29-9816-8cd24a00215b", "metadata": {}, "source": [ "Let's experiment with our progression classes:" ] }, { "cell_type": "code", "execution_count": 7, "id": "5fbf541e-a5b4-44da-a572-7f2626dd4ddc", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Default progression:\n", "0 1 2 3 4 5 6 7 8 9\n", "Arithmetic progression with increment 5:\n", "0 5 10 15 20 25 30 35 40 45\n", "Arithmetic progression with increment 5 and start 2:\n", "2 7 12 17 22 27 32 37 42 47\n", "Geometric progression with default base:\n", "1 2 4 8 16 32 64 128 256 512\n", "Geometric progression with base 3:\n", "1 3 9 27 81 243 729 2187 6561 19683\n", "Fibonacci progression with default start values:\n", "0 1 1 2 3 5 8 13 21 34\n", "Fibonacci progression with start values 4 and 6:\n", "4 6 10 16 26 42 68 110 178 288\n" ] } ], "source": [ "if __name__ == '__main__':\n", " print('Default progression:')\n", " Progression().print_progression(10)\n", " \n", " print('Arithmetic progression with increment 5:')\n", " ArithmeticProgression(5).print_progression(10)\n", " \n", " print('Arithmetic progression with increment 5 and start 2:')\n", " ArithmeticProgression(5, 2).print_progression(10)\n", " \n", " print('Geometric progression with default base:')\n", " GeometricProgression().print_progression(10)\n", " \n", " print('Geometric progression with base 3:')\n", " GeometricProgression(3).print_progression(10)\n", " \n", " print('Fibonacci progression with default start values:')\n", " FibonacciProgression().print_progression(10)\n", " \n", " print('Fibonacci progression with start values 4 and 6:')\n", " FibonacciProgression(4, 6).print_progression(10)\n", " " ] }, { "cell_type": "markdown", "id": "05efa3e1-b463-499d-a9ec-602baca88468", "metadata": {}, "source": [ "

1.3 Abstract Base Class

\n", "When defining a group of classes as part of an inheritance hierarchy, one technique for avoiding repetition of code is to design a base class with common functionality that can be inherited by other classes that need it. As an example, the progression hierarchy from includes a Progression class, which serves as a base class for three distinct subclasses: ArithmeticProgression, GeometricProgression, and FibonacciProgression. Although it is possible to create an instance of the Progression base class, there is little value in doing so because its behavior is simply a special case of an ArithmeticProgression with increment 1. The real purpose of the Progression class was to centralize the implementations of behaviors that other progressions needed, thereby streamlining the code that is relegated to those subclasses.
\n", "\n", "In classic object-oriented terminology, we say a class is an abstract base class if its only purpose is to serve as a base class through inheritance. More formally, an abstract base class is one that cannot be directly instantiated, while a concrete class is one that can be instantiated. By this definition, our Progression class is technically concrete, although we essentially designed it as an abstract base class.
\n", "\n", "In statically typed languages such as Java and C++, an abstract base class serves as a formal type that may guarantee one or more abstract methods. This provides support for polymorphism, as a variable may have an abstract base class as its declared type, even though it refers to an instance of a concrete subclass. Because there are no declared types in Python, this kind of polymorphism can be accomplished without the need for a unifying abstract base class. For this reason, there is not as strong a tradition of defining abstract base classes in Python, although Python’s abc module provides support for defining a formal abstract base class.
\n", "\n", "Our reason for focusing on abstract base classes in our study of data structures is that Python’s collections module provides several abstract base classes that assist when defining custom data structures that share a common interface with some of Python’s built-in data structures. These rely on an object-oriented software design pattern known as the template method pattern. The template method pattern is when an abstract base class provides concrete behaviors that rely upon calls to other abstract behaviors. In that way, as soon as a subclass provides definitions for the missing abstract behaviors, the inherited concrete behaviors are well defined.
\n", "\n", "As a tangible example, the collections.Sequence abstract base class defines behaviors common to Python’s list, str, and tuple classes, as sequences that support element access via an integer index. More so, the collections.Sequence class provides concrete implementations of methods, count, index, and \\_\\_contains\\_\\_ that can be inherited by any class that provides concrete implementations of both \\_\\_len\\_\\_ and \\_\\_getitem\\_\\_. For the purpose of illustration, we provide a sample implementation of such a Sequence abstract base class in the code segment below." ] }, { "cell_type": "code", "execution_count": 8, "id": "8f4d6a65-e1b7-49e8-b58e-6c923472b0d3", "metadata": {}, "outputs": [], "source": [ "from abc import ABCMeta, abstractmethod # need these definitions\n", "\n", "class Sequence(metaclass=ABCMeta):\n", " \"\"\"Our own version of collections.Sequence abstract base class.\"\"\"\n", "\n", " @abstractmethod\n", " def __len__(self):\n", " \"\"\"Return the length of the sequence.\"\"\"\n", "\n", " @abstractmethod\n", " def __getitem__(self, j):\n", " \"\"\"Return the element at index j of the sequence.\"\"\"\n", "\n", " def __contains__(self, val):\n", " \"\"\"Return True if val found in the sequence; False otherwise.\"\"\"\n", " for j in range(len(self)):\n", " if self[j] == val: # found match\n", " return True\n", " return False\n", "\n", " def index(self, val):\n", " \"\"\"Return leftmost index at which val is found (or raise ValueError).\"\"\"\n", " for j in range(len(self)):\n", " if self[j] == val: # leftmost match\n", " return j\n", " raise ValueError('value not in sequence') # never found a match\n", "\n", " def count(self, val):\n", " \"\"\"Return the number of elements equal to given value.\"\"\"\n", " k = 0\n", " for j in range(len(self)):\n", " if self[j] == val: # found a match\n", " k += 1\n", " return k" ] }, { "cell_type": "markdown", "id": "394cbe2a-ba6b-4180-b1c2-dbbb3c63e80d", "metadata": {}, "source": [ "This implementation relies on two advanced Python techniques. The first is that we declare the ABCMeta class of the abc module as a metaclass of our Sequence class. A metaclass is different from a superclass, in that it provides a template for the class definition itself. Specifically, the ABCMeta declaration assures that the constructor for the class raises an error.
\n", "\n", "The second advanced technique is the use of the @abstractmethod decorator immediately before the \\_\\_len\\_\\_ and \\_\\_getitem\\_\\_ methods are declared. That declares these two particular methods to be abstract, meaning that we do not provide an implementation within our Sequence base class, but that we expect any concrete subclasses to support those two methods. Python enforces this expectation by disallowing instantiation for any subclass that does not override the abstract methods with concrete implementations.
\n", "\n", "The rest of the Sequence class definition provides tangible implementations for other behaviors, under the assumption that the abstract \\_\\_len\\_\\_ and \\_\\_getitem\\_\\_ methods will exist in a concrete subclass. If you carefully examine the source code, the implementations of methods \\_\\_contains\\_\\_, index, and count do not rely on any assumption about the self instances, other than that syntax len(self) and self[j] are supported (by special methods \\_\\_len\\_\\_ and \\_\\_getitem\\_\\_, respectively). Support for iteration is automatic as well, as described earlier.
\n", "\n", "In the remainder of this book, we omit the formality of using the abc module. If we need an “abstract” base class, we simply document the expectation that subclasses provide assumed functionality, without a technical declaration of the methods as abstract. But we will make use of the wonderful abstract base classes that are defined within the collections module (such as Sequence). To use such a class, we need only rely on standard inheritance techniques.
\n", "\n", "For example, our Range class, from the previous module, is an example of a class that supports the \\_\\_len\\_\\_ and \\_\\_getitem\\_\\_ methods. But that class does not support the methods count or index. Had we originally declared it with Sequence as a superclass, then it would also inherit the count and index methods. The syntax for such a declaration would begin as:\n", "
\n",
    "    class Range(collections.Sequence):\n",
    "
\n", "Finally, we emphasize that if a subclass provides its own implementation of an inherited behavior from a base class, the new definition overrides the inherited one. This technique can be used when we have the ability to provide a more efficient implementation of a behavior than is achieved by the generic approach. As an example, the general implementation of contains for a sequence is based on a loop used to search for the desired value. For our Range class, there is an opportunity for a more efficient determination of containment. For example, it is evident that the expression, 100000 in Range(0, 2000000, 100), should evaluate to True, even without examining the individual elements of the range, because the range starts with zero, has an increment of 100, and goes until 2 million; it must include 100000, as that is a multiple of 100 that is between the start and stop values.\n", "\n", "

1.4 Namespace and Object-orientation

\n", "A namespace is an abstraction that manages all of the identifiers that are defined in a particular scope, mapping each name to its associated value. In Python, functions, classes, and modules are all first-class objects, and so the “value” associated with an identifier in a namespace may in fact be a function, class, or module.
\n", "\n", "In an earlier module, we explored Python’s use of namespaces to manage identifiers that are defined with global scope, versus those defined within the local scope of a function call. In this section, we discuss the important role of namespaces in Python’s management of object-orientation.\n", "\n", "

1.4.1 Instance and class namespaces

\n", "We begin by exploring what is known as the instance namespace, which manages attributes specific to an individual object. For example, each instance of our CreditCard class maintains a distinct balance, a distinct account number, a distinct credit limit, and so on (even though some instances may coincidentally have equivalent balances or equivalent credit limits). Each credit card will have a dedicated instance namespace to manage such values.\n", "\n", "There is a separate class namespace for each class that has been defined. This namespace is used to manage members that are to be shared by all instances of a class, or used without reference to any particular instance. For example, the make_payment method of the CreditCard class is not stored independently by each instance of that class. That member function is stored within the namespace of the CreditCard class. The CreditCard class namespace includes the functions: \\_\\_init\\_\\_, get_customer, get_bank, get_account, get_balance, get_limit, charge, and make_payment. Our PredatoryCreditCard class has its own namespace, containing the three methods we defined for that subclass: \\_\\_init\\_\\_, charge, and process_month.
\n", "\n", "The figure below provides a portrayal of three such namespaces: a class namespace containing methods of the CreditCard class, another class namespace with methods of the PredatoryCreditCard class, and finally a single instance namespace for a sample instance of the PredatoryCreditCard class. We note that there are two different definitions of a function named charge, one in the CreditCard class, and then the overriding method in the PredatoryCreditCard class. In a similar fashion, there are two distinct \\_\\_init\\_\\_ implementations. However, process_month is a name that is only defined within the scope of the PredatoryCreditCard class. The instance namespace includes all data members for the instance (including the _apr member that is established by the PredatoryCreditCard constructor).\n", "\n", "\n", "\n", "
How Entries Are Established in a Namespace
\n", "It is important to understand why a member such as _balance resides in a credit card’s instance namespace, while a member such as make_payment resides in the class namespace. The _balance is established within the \\_\\_init\\_\\_ method when a new credit card instance is constructed. The original assignment uses the syntax self._balance = 0, where self is an identifier for the newly constructed instance. The use of self as a qualifier for self._balance in such an assignment causes the _balance identifier to be added directly to the instance namespace.
\n", "\n", "When inheritance is used, there is still a single instance namespace per object. For example, when an instance of the PredatoryCreditCard class is constructed, the _apr attribute, as well as attributes such as _balance and _limit all reside in that instance’s namespace, because all are assigned using a qualified syntax, such as self._apr.
\n", "\n", "A class namespace includes all declarations that are made directly within the body of the class definition. For example, our CreditCard class definition included the following structure:\n", "
\n",
    "    class CreditCard:\n",
    "        def make payment(self, amount):\n",
    "        ...\n",
    "
\n", "Because the make payment function is declared within the scope of the CreditCard class, that function becomes associated with the name make payment within the CreditCard class namespace. Although member functions are the most typical types of entries that are declared in a class namespace, we next discuss how other types of data values, or even other classes, can be declared within a class namespace.\n", "\n", "
Class Data Members
\n", "A class-level data member is often used when there is some value, such as a constant, that is to be shared by all instances of a class. In such a case, it would be unnecessarily wasteful to have each instance store that value in its instance namespace. As an example, we revisit the PredatoryCreditCard introduced earlier. That class assesses a 5 dollar fee if an attempted charge is denied because of the credit limit. Our choice of 5 dollars for the fee was somewhat arbitrary, and our coding style would be better if we used a named variable rather than embedding the literal value in our code. Often, the amount of such a fee is determined by the bank’s policy and does not vary for each customer. In that case, we could define and use a class data member as follows:\n", "
\n",
    "    class PredatoryCreditCard(CreditCard):\n",
    "        OVERLIMIT_FEE = 5 # this is a class-level member\n",
    "        \n",
    "        def charge(self, price):\n",
    "            success = super().charge(price)\n",
    "            if not success:\n",
    "                self._balance += PredatoryCreditCard.OVERLIMIT_FEE\n",
    "            return success\n",
    "
\n", "The data member, OVERLIMIT_FEE, is entered into the PredatoryCreditCard class namespace because that assignment takes place within the immediate scope of the class definition, and without any qualifying identifier.\n", "\n", "
Nested classes
\n", "It is also possible to nest one class definition within the scope of another class. This is a useful construct, which we will exploit several times in this book in the implementation of data structures. This can be done by using a syntax such as\n", "
\n",
    "    class A: # the outer class\n",
    "        class B: # the nested class        \n",
    "            ...\n",
    "
\n", "In this case, class B is the nested class. The identifier B is entered into the namespace of class A associated with the newly defined class. We note that this technique is unrelated to the concept of inheritance, as class B does not inherit from class A.
\n", "\n", "Nesting one class in the scope of another makes clear that the nested class exists for the support of the outer class. Furthermore, it can help reduce potential name conflicts because it allows for a similarly named class to exist in another context. For example, we will later introduce a data structure known as a linked list and will define a nested node class to store the individual components of the list. We will also introduce a data structure known as a tree that depends upon its own nested node class. These two structures rely on different node definitions, and by nesting those within the respective container classes, we avoid ambiguity.
\n", "\n", "Another advantage of one class being nested as a member of another is that it allows for a more advanced form of inheritance in which a subclass of the outer class overrides the definition of its nested class. We will make use of that technique when specializing the nodes of a tree structure.\n", "\n", "

1.4.2 Name Resolution and Dynamic Dispatch

\n", "In the previous section, we discussed various namespaces and the mechanism for establishing entries in those namespaces. In this section, we examine the process that is used when retrieving a name in Python’s object-oriented framework. When the dot operator syntax is used to access an existing member, such as obj.foo, the Python interpreter begins a name resolution process, described as follows: \n", "
    \n", "
  1. The instance namespace is searched; if the desired name is found, its associated value is used.
    2. \n", "
  2. Otherwise, the class namespace, for the class to which the instance belongs, is searched; if the name is found, its associated value is used.
    3. \n", "
  3. If the name was not found in the immediate class namespace, the search continues upward through the inheritance hierarchy, checking the class namespace for each ancestor (commonly by checking the superclass class, then its superclass class, and so on). The first time the name is found, its associated value is used.
    4. \n", "
  4. If the name has still not been found, an AttributeError is raised.
    5. \n", "
\n", "As a tangible example, let us assume that mycard identifies an instance of the PredatoryCreditCard class. Consider the following possible usage patterns.\n", "\n", "In the last case shown, notice that the existence of a charge function in the PredatoryCreditCard class has the effect of overriding the version of that function that exists in the CreditCard namespace. In traditional object-oriented terminology, Python uses what is known as dynamic dispatch (or dynamic binding) to determine, at run-time, which implementation of a function to call based upon the type of the object upon which it is invoked. This is in contrast to some languages that use static dispatching, making a compile-time decision as to which version of a function to call, based upon the declared type of a variable.\n", "\n", "

1.5 Shallow and Deep Copying

\n", "In the first module, we emphasized that an assignment statement foo = bar makes the name foo an alias for the object identified as bar. In this section, we consider the task of making a copy of an object, rather than an alias. This is necessary in applications when we want to subsequently modify either the original or the copy in an independent manner.
\n", "\n", "Consider a scenario in which we manage various lists of colors, with each color represented by an instance of a presumed color class. We let identifier warmtones denote an existing list of such colors (e.g., oranges, browns). In this application, we wish to create a new list named palette, which is a copy of the warmtones list. However, we want to subsequently be able to add additional colors to palette, or to modify or remove some of the existing colors, without affecting the contents of warmtones. If we were to execute the command:\n", "
\n",
    "    palette = warmtones\n",
    "
\n", "This creates an alias, as shown in the figure below. No new list is created; instead, the new identifier palette references the original list.\n", "\n", "\n", "\n", "Unfortunately, this does not meet our desired criteria, because if we subsequently add or remove colors from palette, we modify the list identified as warmtones. We can instead create a new instance of the list class by using the syntax:\n", "
\n",
    "    palette = list(warmtones)\n",
    "
\n", "In this case, we explicitly call the list constructor, sending the first list as a parameter. This causes a new list to be created, as shown in the figure below; however, it is what is known as a shallow copy. The new list is initialized so that its contents are precisely the same as the original sequence. However, Python’s lists are referential, and so the new list represents a sequence of references to the same elements as in the first.\n", "\n", "\n", "\n", "This is a better situation than our first attempt, as we can legitimately add or remove elements from palette without affecting warmtones. However, if we edit a color instance from the palette list, we effectively change the contents of warmtones. Although palette and warmtones are distinct lists, there remains indirect aliasing, for example, with palette[0] and warmtones[0] as aliases for the same color instance.
\n", "\n", "We prefer that palette be what is known as a deep copy of warmtones. In a deep copy, the new copy references its own copies of those objects referenced by the original version. See figure below.\n", "\n", "\n", "\n", "

Python's copy module

\n", "To create a deep copy, we could populate our list by explicitly making copies of the original color instances, but this requires that we know how to make copies of colors (rather than aliasing). Python provides a very convenient module, named copy, that can produce both shallow copies and deep copies of arbitrary objects.\n", "\n", "This module supports two functions: the copy function creates a shallow copy of its argument, and the deepcopy function creates a deep copy of its argument. After importing the module, we may create a deep copy for our example, as shown in the figure below, using the command:\n", "
\n",
    "    palette = copy.deepcopy(warmtones)\n",
    "
\n", "\n", "\n", "\n", "\n", "

Module endnote

\n", "We have covered most of the Python programming concepts. There are certain concepts that we will pick up as and when required during the course. You can use the code segment below to experiment with some of the concepts discussed above.\n" ] }, { "cell_type": "code", "execution_count": 9, "id": "f5d3393c-c769-45f6-8ffe-263f2fa211d6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[249, 124, 43], [169, 163, 52]]\n", "[[250, 124, 43], [169, 163, 52]]\n", "[[250, 124, 43], [169, 163, 52]]\n", "[[251, 124, 43], [169, 163, 52]]\n" ] } ], "source": [ "C1 = [249, 124, 43]\n", "C2 = [169, 163, 52]\n", "warmtones = [C1, C2]\n", "print(warmtones)\n", "palette = warmtones\n", "palette[0][0] = 250\n", "print(warmtones)\n", "import copy\n", "palette = copy.deepcopy(warmtones)\n", "palette[0][0] = 251\n", "print(warmtones)\n", "print(palette)" ] }, { "cell_type": "code", "execution_count": null, "id": "f17fba42-8141-4d79-a686-504a2b202a2f", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.6" } }, "nbformat": 4, "nbformat_minor": 5 }