Inheritance

Inheritance

Source: this section is heavily based on Chapter 23 of [ThinkCS] though adapted to better fit with the contents, terminology and notations of this particular course.

Inheritance

The language feature most often associated with object-oriented programming is inheritance. Inheritance is the ability to define a new class that is a modified version of an existing class.

The primary advantage of this feature is that you can add new methods to a class without modifying the existing class. It is called inheritance because the new class inherits all of the methods of the existing class. Extending this metaphor, the existing class is sometimes called the parent class. The new class is called the child class or sometimes subclass.

Inheritance is a powerful feature. Some programs that would be complicated without inheritance can be written concisely and simply with it. Also, inheritance facilitates code reuse, since you can customise the behaviour of parent classes without having to modify them. In some cases, the inheritance structure reflects the natural structure of a problem, which makes the program easier to understand.

On the other hand, inheritance can sometimes make programs difficult to read. When a method is invoked, it is sometimes not clear where to find its definition, since the relevant code may be scattered among several classes. If the natural structure of a problem does not lend itself to inheritance, sometimes a more elegant solution without using inheritance is more appropriate. In general, as a computer scientist it is good to know a few different programming paradigms so that you can always choose the one that is most suited for the problem at hand.

In this chapter we will demonstrate the use of inheritance as part of a program that plays the card game [OldMaid]. One of our goals is to write the program in such a way that parts of its code could easily be reused to implement other card games. Furthermore, to implement the card game we will build upon the Card and Deck classes which we already introduced in the previous chapter.

A hand of cards

For almost any card game, we need to represent a hand of cards, i.e. the set of cards a player is holding in his hand. A Hand is similar to a Deck. Both are made up of a set of cards, and both require operations like adding and removing cards. Also, we might like the ability to shuffle both decks and hands.

/syllabus/info1-theory/assets/playing-cards.jpg

But a Hand is also different from a Deck in certain ways. Depending on the game being played, we might want to perform some operations on hands that don't make sense for a deck. For example, in poker we might classify a hand (straight, flush, etc.) or compare it with another hand. In bridge, we might want to compute a score for a hand in order to make a bid.

This situation suggests the use of inheritance. If Hand is a subclass of Deck, it will have all the methods of Deck, but new methods can be added.

We add the code in this chapter to our Cards.py file from the previous chapter. In the class definition, the name of the parent class appears in parentheses:

class Hand(Deck):
    pass

This statement indicates that the new Hand class inherits from the existing Deck class. Such an empty child class would provide exactly the same behaviour as its super class. (In other words, instances of the child class understand exactly the same methods as instances of the super class.) This is not very useful, unless we add a few additional methods and instance variables.

We start by adding a constructor that initialises the attributes for a Hand, which are name and cards. The string name identifies this hand, probably by the name of the player that holds it. The name is an optional parameter with the empty string as default value. cards is the list of cards in the hand, initialised to the empty list:

class Hand(Deck):
    def __init__(self, name=""):
        self.cards = []
        self.name = name

For just about any card game, it is necessary to add and remove cards from a hand. Removing cards is already taken care of, since Hand inherits remove from Deck. (In other words, since the super or parent class Deck already implements the method remove, any instance of class Hand will automatically understand that method as well.) But we still have to implement an add method:

class Hand(Deck):
    ...
    def add(self, card):
        self.cards.append(card)

Again, the ellipsis ... indicates that we have omitted other methods. The list append method adds the new card to the end of the list of cards held in the hand.

Dealing cards

Now that we have a Hand class, we want to deal cards from the Deck into hands. It is not immediately obvious whether this method should go in the Hand class or in the Deck class, but since it operates on a single deck and (possibly) several hands, it is more natural to put it in Deck.

deal should be fairly general, since different games will have different requirements. We may want to deal out the entire deck at once or add one card to each hand.

deal takes two parameters, a list (or tuple) of hands and the total number of cards to deal. If there are not enough cards in the deck, the method deals out all of the cards and stops:

class Deck:
    ...
    def deal(self, hands, num_cards=None):
        if num_cards==None :             # if no value given for how many cards
            num_cards = len(self.cards)  # to deal then deal all cards in deck
        num_hands = len(hands)
        for i in range(num_cards):
            if self.is_empty():
                break                    # Break if out of cards
            card = self.pop()            # Take the top card
            hand = hands[i % num_hands]  # Whose turn is next?
            hand.add(card)               # Add the card to the hand

The second parameter, num_cards, is optional; if no value is given for how many cards to deal, then we set the value to the size of the deck, so that all of the cards in the deck will get dealt.

The loop variable i goes from 0 to num_cards-1. Each time through the loop, a card is removed from the deck using the list method pop, which removes and returns the last item in the list.

The modulus operator (%) allows us to deal cards in a round robin (one card at a time to each hand). When i is equal to the number of hands in the list, the expression i % num_hands wraps around to the beginning of the list (index 0).

Printing a Hand

To print the contents of a hand, we can take advantage of the __str__ method inherited from Deck. For example:

>>> deck = Deck()
>>> deck.shuffle()
>>> hand = Hand("frank")
>>> deck.deal([hand], 5)
>>> print(hand)
2 of Spades
 3 of Spades
  4 of Spades
   Ace of Hearts
    9 of Clubs

Although it is convenient to inherit the existing method, there is additional information in a Hand object we might want to include when we print one. To do that, we can provide a __str__ method in the Hand class that overrides the one in the Deck class:

class Hand(Deck)
    ...
    def __str__(self):
        s = "Hand " + self.name
        if self.is_empty():
            s += " is empty\n"
            return s
        else:
            s += " contains\n"
            return s + Deck.__str__(self)

Initially, s is a string that identifies the hand. If the hand is empty, the program appends the words is empty and returns s.

Otherwise, the program appends the word contains and the string representation of the Deck, computed by invoking the __str__ method in the Deck class on self.

>>> deck = Deck()
>>> deck.shuffle()
>>> hand = Hand("frank")
>>> deck.deal([hand], 5)
>>> print(hand)
Hand frank contains
2 of Spades
 3 of Spades
  4 of Spades
   Ace of Hearts
    9 of Clubs

Method overriding and super calls

Let us analyse the previous string conversion method a bit more closely. Something very interesting is going on there! The method __str__ of the Hand class is said to override the one of the Deck class.

The word override has a very specific meaning here. It is not synonymous with the word overwrite. We do more than simply overwriting the parent class' implementation of __str__ by replacing it with a new one. In fact, the new implementation refines the old one, by making use of it, and doing a bit more. This combination of overwriting a method of the parent class, while at the same time refining it in such a way that the new implementation makes use of the old one, is called method overriding.

In the code above this happens in the expression Deck.__str__(self) inside the implementation of the method __str__(self) of the Hand class. This is an example of an explicit super call. The Hand's method __str__(self) calls __str__(self) on the super class Deck by explicitly referring to that super class.

Note that in the expression Deck.__str__(self), it may seem odd to pass self, which refers to the current Hand, to a Deck method, until you remember that a Hand is a kind of Deck. Hand objects can do everything Deck objects can, so it is legal to pass a Hand to a Deck method.

In general, it is always legal to use an instance of a subclass in place of an instance of a parent class.

An alternative way to write the __str__ method in the Hand class would be to make use of the special super() method in Python:

class Hand(Deck)
    ...
    def __str__(self):
        s = "Hand " + self.name
        if self.is_empty():
            s += " is empty\n"
            return s
        else:
            s += " contains\n"
            return s + super().__str__()

The only change with respect to the previous implementation is the last line. Rather than referring to the super class Deck explicitly, the super() method allows us to refer to that super class implicitly. Also note that we don't have to pass self as an argument anymore when making such a super call.

The main advantage of using super() is that it allows us to avoid referring to the super class explicitly by name. This is considered as good object-oriented programming style. Most other object-oriented programming languages have a similar super keyword to allow methods overriding a method in their parent class, to call and extend that parent method.

The CardGame class

The CardGame class takes care of some basic chores common to all games, such as creating the deck and shuffling it:

class CardGame:
    def __init__(self):
        self.deck = Deck()
        self.deck.shuffle()

This is the first case we have seen where the initialisation method performs a significant computation, beyond initialising attributes. For more complex classes, like this one, that will often be the case. (As a side note, the initialisation method of a subclass will also often refine the initialisation method of its parent class using a super call. That is not the case here since CardGame is not a subclass.)

To implement specific games, we can inherit from CardGame and add features for the new game. As an example, we'll write a simulation for the [OldMaid] card game.

The object of Old Maid is to get rid, as soon as possible, of all the cards in your hand. You do this by matching cards by rank and colour. For example, the 4 of Clubs ♣︎ matches the 4 of Spades ♠︎ since they have the same rank (4) and both suits (♣︎,♠︎) are black. The Jack of Hearts ♥︎ matches the Jack of Diamonds ♦︎ since both Jacks are of the red colour.

Before starting the game, the Queen of Clubs is removed from the deck. (Other variants of the [OldMaid] game exist where the card removed from the deck is another one, but that doesn't change the essence of the game.) As a consequence of having removed the Queen of Clubs, its corresponding card, the Queen of Spades, will never be matched during the game. The player who remains with this card, the old maid, at the end of the game, loses the game.

The 51 remaining cards are now dealt to the players in a round robin fashion. After the deal, all players can discard all matching pairs of cards they have in their hand.

When no more matches can be made, the actual play begins. In turn, each player picks a card (without looking) from his closest neighbor to the left who still has cards. If the chosen card matches a card in the player's own hand, he can discard this pair from his hand. Otherwise, the chosen card is added to the player's hand. Eventually, as the game continues, all possible matches are made, except for the Queen of Spades (for which no match exists, as the Queen of Clubs was removed from the deck before starting the game). The player who remains with the Queen of Spades in his hand loses the game. (This game is particular in the sense that it has a unique loser, not a winner.)

In our computer simulation of the game, the computer will play all hands. Unfortunately, some funny nuances of the real game are lost. In a real game, the player with the Old Maid goes to some effort to get their closest neighbor to pick that card, by displaying it a little more prominently, or perhaps failing to display it more prominently, or even failing to fail to display that card more prominently. The computer simply picks a neighbor's card at random.

OldMaidHand class

A hand for playing the Old Maid game requires some abilities beyond the general abilities of a Hand, such as the ability to remove matching cards from the hand. We will therefore define a new class, OldMaidHand, that inherits from Hand to reuse its functionality, and provides an additional method called remove_matches:

class OldMaidHand(Hand):

    def remove_matches(self):
        count = 0
        original_cards = self.cards.copy()
        for i in range(0,len(original_cards)):
            card = original_cards[i]
            for j in range(i+1,len(original_cards)):
                match = original_cards[j]
                if match == Card(3 - card.suit, card.rank):
                    self.cards.remove(card)
                    self.cards.remove(match)
                    count += 1
                    print("Hand {0}: {1} matches {2}".format(self.name, card, match))
                    break
        return count

We start by making a copy of the list of cards, so that we can traverse the copy while removing cards from the original. Since self.cards will be modified in the loop, we don't want to use it to control the traversal. Python (or any other programming language, for that matter) can get quite confused if it is traversing a list that is changing while being traversed!

For each card in our hand (outer loop), we iterate over all the remaining cards in our hand (inner loop) to check whether they match that card. In the inner loop, we are smart and only consider cards after the current card being compared, since all the ones before have already been compared.

We have a match if the match has the same rank and the other suit of the same color. Conveniently, the expression 3 - card.suit turns a Club ♣︎ (suit 0) into a Spade ♠︎ (suit 3) and a Diamond ♦︎ (suit 1) into a Heart ♥︎ (suit 2). You should satisfy yourself that the opposite operations also work. This clever trick works because of how we encoded suits as numbers. A clever encoding often may make certain operations surprisingly easy.

Whenever we find a match, we remove both the card and its match from our hand, and jump out of the inner loop, since no other matches for this card will be found.

The following example demonstrates how to use remove_matches:

>>> game = CardGame()
>>> hand = OldMaidHand("frank")
>>> game.deck.deal([hand], 13)
>>> print(hand)
Hand frank contains
  2 of Hearts
   6 of Diamonds
    9 of Clubs
     6 of Hearts
      Jack of Diamonds
       7 of Diamonds
        10 of Spades
         7 of Clubs
          3 of Hearts
           7 of Hearts
            3 of Spades
             10 of Clubs
              8 of Clubs
>>> count = hand.remove_matches()
Hand frank: 6 of Diamonds matches 6 of Hearts
Hand frank: 7 of Diamonds matches 7 of Hearts
Hand frank: 10 of Spades matches 10 of Clubs
>>> print("{} matches found".format(count))
3 matches found
>>> print(hand)
Hand frank contains
  2 of Hearts
    9 of Clubs
      Jack of Diamonds
        7 of Clubs
          3 of Hearts
            3 of Spades
              8 of Clubs

Notice that there is no __init__ method for the OldMaidHand class. We inherit it from Hand.

Alternative implementation

Here's an alternative and slightly more compact implementation of the remove_matches method. Which one you prefer is a matter of personal taste.

class OldMaidHand(Hand):

    def remove_matches(self):
        count = 0
        original_cards = self.cards.copy()
        for card in original_cards:
            match = Card(3 - card.suit, card.rank)
            if match in self.cards:
                self.cards.remove(card)
                self.cards.remove(match)
                count += 1
                print("Hand {0}: {1} matches {2}".format(self.name, card, match))
        return count

OldMaidGame class

Now we can turn our attention to the game itself. OldMaidGame is a subclass of CardGame. Since __init__ is inherited from CardGame, a new OldMaidGame object already contains a new shuffled deck. OldMaidGame defines a new method called play that takes a list of player names as a parameter. Calling this play method launches the game:

OldMaidGame().play(["kim","charles","siegfried"])

The play method is defined as follows:

class OldMaidGame(CardGame):
    ...
    def play(self, names):
        # Remove Queen of Clubs
        queen_clubs = Card(0,12)
        self.deck.remove(queen_clubs)

        # Make a hand for each player
        self.hands = []
        for name in names:
            self.hands.append(OldMaidHand(name))

        # Deal the cards
        self.deck.deal(self.hands)
        print("---------- Cards have been dealt")
        self.print_hands()

        # Remove initial matches
        print("---------- Discarding matches from hands")
        matches = self.remove_all_matches()
        print("---------- Matches have been discarded")
        self.print_hands()

        # Play until all 50 cards are matched
        # in other words, until 25 pairs have been matched
        print("---------- Play begins")
        turn = 0
        num_players = len(names)
        while matches < 25:
            matches += self.play_one_turn(turn)
            turn = (turn + 1) % num_players

        print("---------- Game is Over")
        self.print_hands()

Some of the steps of the game have been separated into methods. The auxiliary method print_hands is pretty straightforward:

class OldMaidGame(CardGame):
    ...
    def print_hands(self):
        for hand in self.hands:
            print(hand)

remove_all_matches traverses the list of hands and invokes remove_matches on each:

class OldMaidGame(CardGame):
    ...
    def remove_all_matches(self):
        count = 0
        for hand in self.hands:
            count += hand.remove_matches()
        return count

count is an accumulator that adds up the number of matches in each hand. When we've gone through every hand, the total is returned (count). We need this count to stop the game after 25 matches have been found. Indeed, when the total number of matches reaches 25, we know that 50 cards have been removed from the hands, which means that only 1 card is left (the old maid) and the game is over.

The variable turn keeps track of which player's turn it is. It starts at 0 and increases by one each time; when it reaches num_players, the modulus operator wraps it back around to 0.

The method play_one_turn takes a parameter that indicates whose turn it is. The return value is the number of matches made during this turn:

class OldMaidGame(CardGame):
    ...
    def play_one_turn(self, i):
        print("Player" + str(i) + ":")
        if self.hands[i].is_empty():
            return 0
        neighbor = self.find_neighbor(i)
        picked_card = self.hands[neighbor].pop()
        self.hands[i].add(picked_card)
        print("Hand", self.hands[i].name, "picked", picked_card)
        count = self.hands[i].remove_matches()
        self.hands[i].shuffle()
        return count

If a player's hand is empty, that player is out of the game, so he or she does nothing and 0 matches are returned.

Otherwise, a turn consists of finding the first player on the left that has cards, taking one card from the neighbor, and checking for matches. Before returning, the cards in the hand are shuffled so that the next player's choice is random.

The method find_neighbor starts with the player to the immediate left and continues around the circle until it finds a player that still has cards:

class OldMaidGame(CardGame):
    ...
    def find_neighbor(self, i):
        num_hands = len(self.hands)
        for next in range(1,num_hands):
            neighbor = (i + next) % num_hands
            if not self.hands[neighbor].is_empty():
                return neighbor

If find_neighbor ever went all the way around the circle without finding cards, it would return None and cause an error elsewhere in the program. Fortunately, we can prove that that will never happen (as long as the end of the game is detected correctly).

Putting it all together

In the appendix chapter you will find the full code of all classes we defined above, as well as a sample output of a run of the game.

Glossary

ancestor class
A parent class, or an ancestor of the parent class.
child class
A new class created by inheriting from an existing class; also called a subclass.
inheritance
The ability to define a new class that is a modified version of a previously defined class.
method overriding
When, in addition to overwriting a method higher up the hierarchy, the implementation of that new method also refines the old one, by making use of it through a super call, and doing a bit more.
method overwriting
When a method defined in a child class replaces the implementation of a method with the same name defined in a parent or ancestor class.
parent class
The class from which a child class inherits; also called a superclass
subclass
Another word for child class.
superclass
another word for parent class.
super call
A super call can be used to gain access to inherited methods – from a parent or ancestor class – that have been overridden in a child class. This can either be done by explicitly referring to that parent class, or implicitly by using the special super() function.

References

[ThinkCS]How To Think Like a Computer Scientist --- Learning with Python 3
[OldMaid](1, 2, 3) https://en.wikipedia.org/wiki/Old_maid_(card_game)

Page précédente Page suivante