Cards

There are 52 cards in a deck, each of which belongs to one of 4 suits and one of 13 ranks. The suits are Spades (♠), Hearts (♥), Diamonds (♦), and Clubs (♣). The ranks are Ace (A), 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack (J), Queen (Q), and King (K). Depending on the game that you are playing, an Ace may be higher than a King or lower than a 2.

If we want to define a new object to represent a playing card, it is obvious what the attributes should be: rank and suit. It is not as obvious what type the attributes should be. One possibility is to use strings containing words like "Spade" for suits and "Queen" for ranks. One problem with this implementation is that it would not be easy to compare cards to see which had a higher rank or suit.

An alternative is to use integers to encode the ranks and suits. In this context, “encode” means that we are going to define a mapping between numbers and suits, or between numbers and ranks. This kind of encoding is not meant to be a secret (that would be “encryption”).

For example, we might map the suits to integer codes as follows:

• ♠ $\mapsto$ 4

• ♥ $\mapsto$ 3

• ♦ $\mapsto$ 2

• ♣ $\mapsto$ 1

This makes it easy to compare cards; because higher suits map to higher numbers, we can compare suits by comparing their codes.

I am using the $\mapsto$ symbol to make it clear that these mappings are not part of the Julia program. They are part of the program design, but they don’t appear explicitly in the code.

The struct definition for Card looks like this:

struct Card
    suit :: Int64
    rank :: Int64
    function Card(suit::Int64, rank::Int64)
        @assert(1 ≤ suit ≤ 4, "suit is not between 1 and 4")
        @assert(1 ≤ rank ≤ 13, "rank is not between 1 and 13")
        new(suit, rank)
    end
end

To create a Card, you call Card with the suit and rank of the card you want:

julia> queen_of_diamonds = Card(2, 12)
Card(2, 12)

Global Variables

In order to print Card objects in a way that people can easily read, we need a mapping from the integer codes to the corresponding ranks and suits. A natural way to do that is with arrays of strings:

const suit_names = ["♣", "♦", "♥", "♠"]
const rank_names = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J",
                    "Q", "K"]

The variables suit_names and rank_names are global variables. The const declaration means that the variable can only be assigned once. This solves the performance problem of global variables.

Now we can implement an appropriate show method:

function Base.show(io::IO, card::Card)
    print(io, rank_names[card.rank], suit_names[card.suit])
end

The expression rank_names[card.rank] means “use the field rank from the object card as an index into the array rank_names, and select the appropriate string.”

With the methods we have so far, we can create and print Card:

julia> Card(3, 11)
J♥

Comparing Cards

For built-in types, there are relational operators (<, >, ==, etc.) that compare values and determine when one is greater than, less than, or equal to another. For programmer-defined types, we can override the behavior of the built-in operators by providing a method named <.

The correct ordering for cards is not obvious. For example, which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit. In order to compare cards, you have to decide whether rank or suit is more important.

The answer might depend on what game you are playing, but to keep things simple, we’ll make the arbitrary choice that suit is more important, so all of the Spades outrank all of the Diamonds and so on.

With that decided, we can write <:

import Base.isless

function isless(c1::Card, c2::Card)
    (c1.suit, c1.rank) < (c2.suit, c2.rank)
end

Unit Testing

Unit testing allows you to verify the correctness of your code by comparing the results of your code to what you expect. This can be useful to be sure that your code is still correct after modifications, and it is also a way to predefine the correct behavior of your code during development.

Simple unit testing can be performed with the @test macro:

julia> using Test

julia> @test Card(1, 4) < Card(2, 4)
Test Passed
julia> @test Card(1, 3) < Card(1, 4)
Test Passed

@test returns a "Test Passed" if the expression following it is true, a "Test Failed" if it is false, and an "Error Result" if it could not be evaluated.

Decks

Now that we have Cards, the next step is to define Decks. Since a deck is made up of cards, it is natural for each Deck to contain an array of Cards as an attribute.

The following is a struct definition for Deck. The constructor creates the field cards and generates the standard set of 52 Cards:

struct Deck
    cards :: Array{Card, 1}
end

function Deck()
    deck = Deck(Card[])
    for suit in 1:4
        for rank in 1:13
            push!(deck.cards, Card(suit, rank))
        end
    end
    deck
end

The easiest way to populate the deck is with a nested loop. The outer loop enumerates the suits from 1 to 4. The inner loop enumerates the ranks from 1 to 13. Each iteration creates a new Card with the current suit and rank, and pushes it to deck.cards.

Here is a show method for Deck:

function Base.show(io::IO, deck::Deck)
    for card in deck.cards
        print(io, card, " ")
    end
    println()
end

Here’s what the result looks like:

julia> Deck()
A♣ 2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ Q♣ K♣ A♦ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ 10♦ J♦ Q♦ K♦ A♥ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ Q♥ K♥ A♠ 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠

Add, Remove, Shuffle, and Sort

To deal cards, we would like a function that removes a Card from the Deck and returns it. The function pop! provides a convenient way to do that:

function Base.pop!(deck::Deck)
    pop!(deck.cards)
end

Since pop! removes the last Card in the array, we are dealing from the bottom of the Deck.

To add a Card, we can use the function push!:

function Base.push!(deck::Deck, card::Card)
    push!(deck.cards, card)
    deck
end

A method like this that uses another method without doing much work is sometimes called a veneer. The metaphor comes from woodworking, where a veneer is a thin layer of good-quality wood glued to the surface of a cheaper piece of wood to improve the appearance.

In this case push! is a “thin” method that expresses an array operation in terms appropriate for decks. It improves the appearance, or interface, of the implementation.

As another example, we can write a method named shuffle! using the function Random.shuffle!:

using Random

function Random.shuffle!(deck::Deck)
    shuffle!(deck.cards)
    deck
end

Abstract Types and Subtyping

We want a type to represent a “hand”; that is, the cards held by one player. A hand is similar to a deck: both are made up of a collection of cards, and both require operations like adding and removing cards.

A hand is also different from a deck; there are operations we want for hands that don’t make sense for a deck. For example, in poker we might compare two hands to see which one wins. In bridge, we might compute a score for a hand in order to make a bid.

So, we need a way to group related concrete types. In Julia this is done by defining an abstract type that serves as a parent for both Deck and Hand. This is called subtyping.

Let’s call this abstract type CardSet:

abstract type CardSet end

A new abstract type is created with the abstract type keyword. An optional “parent” type can be specified by putting <: after the name, followed by the name of an already existing abstract type.

When no supertype is given, the default supertype is Any—a predefined abstract type that all objects are instances of and all types are subtypes of.

We can now express that Deck is a descendant of CardSet:

struct Deck <: CardSet
    cards :: Array{Card, 1}
end

function Deck()
    deck = Deck(Card[])
    for suit in 1:4
        for rank in 1:13
            push!(deck.cards, Card(suit, rank))
        end
    end
    deck
end

The operator isa checks whether an object is of a given type:

julia> deck = Deck();

julia> deck isa CardSet
true

A hand is also a kind of CardSet:

struct Hand <: CardSet
    cards :: Array{Card, 1}
    label :: String
end

function Hand(label::String="")
    Hand(Card[], label)
end

Instead of populating the hand with 52 new Cards, the constructor for Hand initializes cards with an empty array. An optional argument can be passed to the constructor giving a label to the Hand:

julia> hand = Hand("new hand")
Hand(Card[], "new hand")

Abstract Types and Functions

We can now express the common operations between Deck and Hand as functions having a CardSet as an argument:

function Base.show(io::IO, cs::CardSet)
    for card in cs.cards
        print(io, card, " ")
    end
end

function Base.pop!(cs::CardSet)
    pop!(cs.cards)
end

function Base.push!(cs::CardSet, card::Card)
    push!(cs.cards, card)
    nothing
end

We can use pop! and push! to deal a card:

julia> deck = Deck()
A♣ 2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ Q♣ K♣ A♦ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ 10♦ J♦ Q♦ K♦ A♥ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ Q♥ K♥ A♠ 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠
julia> shuffle!(deck)
4♠ Q♦ A♣ 9♦ Q♠ 6♣ 10♣ Q♥ A♦ 8♥ 9♥ Q♣ 4♦ 5♥ 9♠ 10♥ A♠ 7♣ 2♠ 5♠ 2♦ K♣ J♠ 10♠ 7♦ 2♥ 3♦ 7♠ 8♦ A♥ K♥ 7♥ J♥ 6♦ J♦ 6♥ K♦ 8♠ 5♦ 4♥ 8♣ J♣ 9♣ 3♠ 2♣ K♠ 3♥ 5♣ 6♠ 10♦ 4♣ 3♣
julia> card = pop!(deck)
3♣
julia> push!(hand, card)

A natural next step is to encapsulate this code in a function called move!:

function move!(cs1::CardSet, cs2::CardSet, n::Int)
    @assert 1 ≤ n ≤ length(cs1.cards)
    for i in 1:n
        card = pop!(cs1)
        push!(cs2, card)
    end
    nothing
end

move! takes three arguments, two CardSet objects and the number of cards to deal. It modifies both CardSet objects, and returns nothing.

In some games, cards are moved from one hand to another, or from a hand back to the deck. You can use move! for any of these operations: cs1 and cs2 can be either a Deck or a Hand.

Type Diagrams

So far we have seen stack diagrams, which show the state of a program, and object diagrams, which show the attributes of an object and their values. These diagrams represent a snapshot of the execution of a program, so they change as the program runs.

They are also highly detailed—for some purposes, too detailed. A type diagram is a more abstract representation of the structure of a program. Instead of showing individual objects, it shows types and the relationships between them.

There are several kinds of relationships between types:

• Objects of a concrete type might contain references to objects of another type. For example, each Rectangle contains a reference to a Point, and each Deck contains references to an array of Cards. This kind of relationship is called has-a, as in, “a Rectangle has a Point.”

• A concrete type can have an abstract type as a supertype. This relationship is called is-a, as in, “a Hand is a kind of a CardSet.”

• One type might depend on another, in the sense that objects of one type take objects of the second type as parameters, or use objects of the second type as part of a computation. This kind of relationship is called a dependency.

Figure 18-1. Type diagram

The arrow with a hollow triangle head represents an is-a relationship; in this case it indicates that Hand has CardSet as a supertype.

The standard arrowhead represents a has-a relationship; in this case a Deck has references to Card objects.

The star (*) near the arrowhead is a multiplicity; it indicates how many Cards a Deck has. A multiplicity can be a simple number, like 52; a range, like 5:7; or a star, which indicates that a Deck can have any number of Cards.

There are no dependencies in this diagram. They would normally be shown with a dashed arrow. Or if there are a lot of dependencies, they are sometimes omitted.

A more detailed diagram might show that a Deck actually contains an array of Cards, but built-in types like array and dictionaries are usually not included in type diagrams.

Debugging

Subtyping can make debugging difficult because when you call a function with an object as an argument, it might be hard to figure out which method will be invoked.

Suppose you are writing a function that works with Hand objects. You would like it to work with all kinds of Hands, like PokerHands, BridgeHands, etc. If you invoke a method like sort!, you might get the version defined for an abstract type Hand, but if a method sort! with any of the subtypes as an argument exists, you’ll get that version instead. This behavior is usually a good thing, but it can be confusing:

function Base.sort!(hand::Hand)
    sort!(hand.cards)
end

Any time you are unsure about the flow of execution through your program, the simplest solution is to add print statements at the beginning of the relevant methods. If shuffle! prints a message that says something like Running shuffle! Deck, then as the program runs it traces the flow of execution.

As a better alternative, you can use the @which macro:

julia> @which sort!(hand)
sort!(hand::Hand) in Main at REPL[5]:1

This tells us that the sort! method for hand is the one having as an argument an object of type Hand.

Here’s a design suggestion: when you override a method, the interface of the new method should be the same as the old one. It should take the same parameters, return the same type, and obey the same preconditions and postconditions. If you follow this rule, you will find that any function designed to work with an instance of a supertype, like a CardSet, will also work with instances of its subtypes (Deck and Hand).

If you violate this rule, which is called the “Liskov substitution principle,” your code will collapse like (sorry) a house of cards.

The function supertype can be used to find the direct supertype of a type:

julia> supertype(Deck)
CardSet

Data Encapsulation

The previous chapters demonstrated a development plan we might call “type-oriented design.” We identified objects we needed—like Point, Rectangle, and MyTime—and defined structs to represent them. In each case there was an obvious correspondence between the object and some entity in the real world (or at least a mathematical world).

But sometimes it is less obvious what objects you need and how they should interact. In that case you need a different development plan. In the same way that we discovered function interfaces by encapsulation and generalization, we can discover type interfaces by data encapsulation.

Markov analysis, described in “Markov Analysis”, provides a good example. If you look at my solution to “Exercise 13-8”, you’ll see that it uses two global variables—suffixes and prefix—that are read and written from several functions:

suffixes = Dict()
prefix = []

Because these variables are global, we can only run one analysis at a time. If we read two texts, their prefixes and suffixes would be added to the same data structures (which makes for some interesting generated text).

To run multiple analyses, and keep them separate, we can encapsulate the state of each analysis in an object. Here’s what that looks like:

struct Markov
    order :: Int64
    suffixes :: Dict{Tuple{String,Vararg{String}}, Array{String, 1}}
    prefix :: Array{String, 1}
end

function Markov(order::Int64=2)
    new(order, Dict{Tuple{String,Vararg{String}}, Array{String, 1}}(), Array{String, 1}())
end

Next, we transform the functions into methods. For example, here’s processword:

function processword(markov::Markov, word::String)
    if length(markov.prefix) < markov.order
        push!(markov.prefix, word)
        return
    end
    get!(markov.suffixes, (markov.prefix...,), Array{String, 1}())
    push!(markov.suffixes[(markov.prefix...,)], word)
    popfirst!(markov.prefix)
    push!(markov.prefix, word)
end

Transforming a program like this—changing the design without changing the behavior—is another example of refactoring (see “Refactoring”).

This example suggests a development plan for designing types:

• Start by writing functions that read and write global variables (when necessary).

• Once you get the program working, look for associations between global variables and the functions that use them.

• Encapsulate related variables as fields of a struct.

• Transform the associated functions into methods with as argument objects of the new type.

Glossary

encode

To represent one set of values using another set of values by constructing a mapping between them.

unit testing

A standardized way to test the correctness of code.

veneer

A method or function that provides a different interface to another function without doing much computation.

concrete type

A type that can be constructed.

abstract type

A type that can act as a parent for another type.

subtyping

The ability to define a hierarchy of related types.

supertype

An abstract type that is the parent of another type.

subtype

A type that has as its parent an abstract type.

type diagram

A diagram that shows the types in a program and the relationships between them.

has-a relationship

A relationship between two types where instances of one type contain references to instances of the other.

is-a relationship

A relationship between a subtype and its supertype.

dependency

A relationship between two types where instances of one type use instances of the other type, but do not store them as fields.

multiplicity

A notation in a type diagram that shows, for a has-a relationship, how many references there are to instances of another class.

data encapsulation

A program development plan that involves a prototype using global variables and a final version that makes the global variables into instance fields.

Exercises

abstract type PingPongParent end

struct Ping <: PingPongParent
    pong :: PingPongParent
end

struct Pong <: PingPongParent
    pings :: Array{Ping, 1}
    function Pong(pings=Array{Ping, 1}())
        new(pings)
    end
end

function addping(pong::Pong, ping::Ping)
    push!(pong.pings, ping)
    nothing
end

pong = Pong()
ping = Ping(pong)
addping(pong, ping)