Lecture: Two Polymorphisms

Dear Computer

Chapter 12: Polymorphism Revisited

Lecture: Two Polymorphisms

Dear students:

Programmers love reuse more than is perhaps healthy. Nothing feels greater than making a piece of code work for \(n\) types, even when \(n\) is only 2. Polymorphism is the name we give to the notion of having one chunk of code serve multiple types, and there are two very different mechanisms for achieving it. They are subtype polymorphism and parametric polymorphism. Both are present in Java, C++, and Rust. Today we examine them in Rust as we bumble our way through some data structures. First we'll look at modeling a game using subtype polymorphism. Then we'll try building a binary search tree using parametric polymorphism.

Which Polymorphism?

First, though, let's have a discussion. We have two polymorphisms, and both make code reusable. That doesn't mean they are interchangeable. We must use the one that's suited to our circumstances. Consider these five scenarios that could benefit from polymorphic abstraction. For each, do we employ subtype polymorphism or parametric polymorphism?

  1. You are developing a graphical user interface library. Clients will add their widgets to your layout manager.
  2. You are developing a sort routine.
  3. You are developing a wrapper abstraction that adds a color to the wrapped value. That way you can have yellow or orange strings, black or red numbers, red or yellow alerts, and so on.
  4. You are developing a logger that logs serialized versions of your program's data.
  5. You are developing a method that computes the average of a very large set of numeric values.

Terminal Game

Suppose we're building a game in which a player moves a fish around on a grid. Because graphics cards have gotten too expensive, the game is played in the terminal with help from Curses. We have prototyped this Game struct:

Rust
use ncurses::*;

pub struct GameState {
  pub is_over: bool,
  pub hit_points: i32,
  pub location: (i32, i32),
}

pub struct Game {
  state: GameState,
}

impl Game {
  pub fn new() -> Self {
    Game {
      state: GameState {
        hit_points: 10,
        is_over: false,
        location: (3, 3),
      }
    }
  }

  pub fn play(&mut self) {
    while !self.state.is_over {
      clear();

      mvaddstr(0, 0, &format!("Hit points: {:5}", self.state.hit_points)).unwrap();
      mvaddstr(self.state.location.1, self.state.location.0, "🐟").unwrap();

      let input = getch();
      if input == 'q' as i32 {
        self.state.is_over = true;
      } else if input == KEY_LEFT {
        self.state.location.0 -= 1;
      } else if input == KEY_RIGHT {
        self.state.location.0 += 1;
      } else if input == KEY_UP {
        self.state.location.1 -= 1;
      } else if input == KEY_DOWN {
        self.state.location.1 += 1;
      }
    }
  }
}
use ncurses::*;

pub struct GameState {
  pub is_over: bool,
  pub hit_points: i32,
  pub location: (i32, i32),
}

pub struct Game {
  state: GameState,
}

impl Game {
  pub fn new() -> Self {
    Game {
      state: GameState {
        hit_points: 10,
        is_over: false,
        location: (3, 3),
      }
    }
  }

  pub fn play(&mut self) {
    while !self.state.is_over {
      clear();

      mvaddstr(0, 0, &format!("Hit points: {:5}", self.state.hit_points)).unwrap();
      mvaddstr(self.state.location.1, self.state.location.0, "🐟").unwrap();

      let input = getch();
      if input == 'q' as i32 {
        self.state.is_over = true;
      } else if input == KEY_LEFT {
        self.state.location.0 -= 1;
      } else if input == KEY_RIGHT {
        self.state.location.0 += 1;
      } else if input == KEY_UP {
        self.state.location.1 -= 1;
      } else if input == KEY_DOWN {
        self.state.location.1 += 1;
      }
    }
  }
}

And we write this main function that enables Unicode, initializes Curses, and starts up a Game:

Rust
use ncurses::*;

mod game;
use game::*;

fn main() {
  let locale_conf = LcCategory::all;
  setlocale(locale_conf, "en_US.UTF-8").unwrap();

  initscr();
  curs_set(CURSOR_VISIBILITY::CURSOR_INVISIBLE);
  keypad(stdscr(), true);
  noecho();

  let mut game = Game::new();
  game.play();
  endwin();
}
use ncurses::*;

mod game;
use game::*;

fn main() {
  let locale_conf = LcCategory::all;
  setlocale(locale_conf, "en_US.UTF-8").unwrap();

  initscr();
  curs_set(CURSOR_VISIBILITY::CURSOR_INVISIBLE);
  keypad(stdscr(), true);
  noecho();

  let mut game = Game::new();
  game.play();
  endwin();
}

In the game, the fish should go around and collect powerups or other collidables. Let's support these:

The game should maintain a collection of these powerups, display them, detect collisions, and delegate to them so they can apply their effect on the game state. But it shouldn't know anything about any particular powerup, and it shouldn't ask about their type. Yet somehow it must be able to call methods on these powerups. How is this possible? Each object maintains a directory of its methods. At runtime, we call an object's method by looking up its entry in this directory. This is dynamic dispatch. In Rust, dynamic dispatch is achieved through traits. We define this trait that abstracts all elements:

Rust
pub trait Powerup {
  fn draw(&self, location: &(i32, i32));
  fn apply(&self, game: &mut GameState);
}
pub trait Powerup {
  fn draw(&self, location: &(i32, i32));
  fn apply(&self, game: &mut GameState);
}

Once we have this trait, we proceed to add a collection of powerups to the Game type. Let's use a HashMap so we know where the powerups are located. If Rust were more like Java, we'd write this:

Rust
use std::collections::HashMap;

struct Game {
  powerups: HashMap<(i32, i32), Powerup>,
  // ...
}
use std::collections::HashMap;

struct Game {
  powerups: HashMap<(i32, i32), Powerup>,
  // ...
}

But this fails. Powerup is not a type. It's a trait, which describes a set of methods that a type can implement. Rust demands that we have a HashMap of some actual type, but we are purposefully trying to be vague about the type. The fix is to use a Box with a trait as its type parameter modified by dyn:

Rust
struct Game {
  powerups: HashMap<(i32, i32), Box<dyn Powerup>>,
  // ...
}
struct Game {
  powerups: HashMap<(i32, i32), Box<dyn Powerup>>,
  // ...
}

The dyn qualifier announces that a pointer to the type's method directory—the virtual table—is tacked onto the value. We like as much stuff to get figured out at compile time as possible. But when Document has a collection of arbitrary elements, the compiler's not going to know exactly what to_html methods to call. That will have to get figured out at runtime. Rust makes it clear that a dynamic lookup is going to happen by demanding the dyn qualifier.

That covers the data definition. Now let's think about behaviors. We want to initialize the HashMap, draw the powerup glyphs, detect collisions, and apply effects:

Rust
use ncurses::*;

pub struct GameState {
  pub is_over: bool,
  pub hit_points: u32,
  pub location: (i32, i32),
}

pub struct Game {
  powerups: HashMap<(i32, i32), Box<dyn Powerup>>,
  state: GameState,
}

impl Game {
  pub fn new() -> Self {
    Game {
      powerups: HashMap::new(),
      state: GameState {
        hit_points: 10,
        is_over: false,
        location: (3, 3),
      }
    }
  }

  pub fn add_powerup(&mut self, location: (i32, i32), powerup: Box<dyn Powerup>) {
    self.powerups.insert(location, powerup);
  }

  pub fn play(&mut self) {
    while !self.state.is_over {
      clear();

      mvaddstr(0, 0, &format!("Hit points: {:5}", self.state.hit_points)).unwrap();
      mvaddstr(self.state.location.1, self.state.location.0, "🐟").unwrap();

      for (location, powerup) in self.powerups.iter() {
        powerup.draw(location);
      }

      let input = getch();
      if input == 'q' as i32 {
        self.state.is_over = true;
      } else if input == KEY_LEFT {
        self.state.location.0 -= 1;
      } else if input == KEY_RIGHT {
        self.state.location.0 += 1;
      } else if input == KEY_UP {
        self.state.location.1 -= 1;
      } else if input == KEY_DOWN {
        self.state.location.1 += 1;
      }

      if let Some(powerup) = self.powerups.get(&self.state.location) {
        powerup.apply(&mut self.state);
      }
    }
  }
}
use ncurses::*;

pub struct GameState {
  pub is_over: bool,
  pub hit_points: u32,
  pub location: (i32, i32),
}

pub struct Game {
  powerups: HashMap<(i32, i32), Box<dyn Powerup>>,
  state: GameState,
}

impl Game {
  pub fn new() -> Self {
    Game {
      powerups: HashMap::new(),
      state: GameState {
        hit_points: 10,
        is_over: false,
        location: (3, 3),
      }
    }
  }

  pub fn add_powerup(&mut self, location: (i32, i32), powerup: Box<dyn Powerup>) {
    self.powerups.insert(location, powerup);
  }

  pub fn play(&mut self) {
    while !self.state.is_over {
      clear();

      mvaddstr(0, 0, &format!("Hit points: {:5}", self.state.hit_points)).unwrap();
      mvaddstr(self.state.location.1, self.state.location.0, "🐟").unwrap();

      for (location, powerup) in self.powerups.iter() {
        powerup.draw(location);
      }

      let input = getch();
      if input == 'q' as i32 {
        self.state.is_over = true;
      } else if input == KEY_LEFT {
        self.state.location.0 -= 1;
      } else if input == KEY_RIGHT {
        self.state.location.0 += 1;
      } else if input == KEY_UP {
        self.state.location.1 -= 1;
      } else if input == KEY_DOWN {
        self.state.location.1 += 1;
      }

      if let Some(powerup) = self.powerups.get(&self.state.location) {
        powerup.apply(&mut self.state);
      }
    }
  }
}

These methods take advantage of subtype polymorphism. They will work with any type from the Powerup hierarchy. Game never has to ask an element what type it is in order to call draw or apply. The runtime will find the right method by dereferencing each element's vpointer.

Let's add a type to the Powerup hierarchy to check that this works. Heart models a hit point boost. We implement it like this:

Rust
struct Heart {
  strength: i32;
}

impl Powerup for Heart {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "💗").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.hit_points += self.strength;
    return true;
  }
}
struct Heart {
  strength: i32;
}

impl Powerup for Heart {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "💗").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.hit_points += self.strength;
    return true;
  }
}

Now we can add a Heart to the game in main:

Rust
use ncurses::*;

mod game;
use game::*;

// Heart definition

fn main() {
  let locale_conf = LcCategory::all;
  setlocale(locale_conf, "en_US.UTF-8").unwrap();

  initscr();
  curs_set(CURSOR_VISIBILITY::CURSOR_INVISIBLE);
  keypad(stdscr(), true);
  noecho();

  let mut game = Game::new();
  game.add_powerup((20, 10), Box::new(Heart {
    strength: 12,
  }));
  game.play();
  endwin();
}
use ncurses::*;

mod game;
use game::*;

// Heart definition

fn main() {
  let locale_conf = LcCategory::all;
  setlocale(locale_conf, "en_US.UTF-8").unwrap();

  initscr();
  curs_set(CURSOR_VISIBILITY::CURSOR_INVISIBLE);
  keypad(stdscr(), true);
  noecho();

  let mut game = Game::new();
  game.add_powerup((20, 10), Box::new(Heart {
    strength: 12,
  }));
  game.play();
  endwin();
}

The Fire powerup ends the game:

Rust
struct Fire {}

impl Powerup for Fire {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "🔥").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.is_over = true;
    return false;
  }
}
struct Fire {}

impl Powerup for Fire {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "🔥").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.is_over = true;
    return false;
  }
}

The Portal powerup relocates the player to some designated location:

Rust
struct Portal {
  destination: (i32, i32),
}

impl Powerup for Portal {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "🌀").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.location = self.destination;
    return true;
  }
}
struct Portal {
  destination: (i32, i32),
}

impl Powerup for Portal {
  fn draw(&self, location: &(i32, i32)) {
    mvaddstr(location.1, location.0, "🌀").unwrap();
  }

  fn apply(&self, state: &mut GameState) {
    state.location = self.destination;
    return true;
  }
}

Our hierarchy only includes three types currently, but we could add many more. Game will never need to change as we add new types. They will all fit under the Powerup hierarchy.

Binary Search Tree

Subtype polymorphism was the de facto polymorphism of the golden age of object-oriented programming. But parametric polymorphism has advantages over subtype polymorphism. The compiler knows the types and can therefore make decisions earlier—it can achieve static dispatch. Let's explore parametric polymorphism in Rust by implementing a binary search tree.

There are several ways we define the type. In Java, we'd create a Node class with three pieces of state: the node payload and two references to child nodes. We could do something similar in Rust, but we have other options. This enum makes every node either a leaf node or an internal node:

Rust
enum Tree<T> {
  Empty,
  Node {
    value: T,
    left: Box<Tree<T>>,
    right: Box<Tree<T>>
  },
}
enum Tree<T> {
  Empty,
  Node {
    value: T,
    left: Box<Tree<T>>,
    right: Box<Tree<T>>
  },
}

Using an enum with an empty variant is a lot like using using the None variant of Option to mark the leaf nodes. We need Box because otherwise we have a recursive type whose size can't be determined.

We'll implement just two behaviors on Tree today and save some others for lab. The first is contains. This method should only be available for trees that hold comparable values, so we add a type constraint to T and then examine how the target value compares the node's value as we recurse down to a leaf:

Rust
impl<T: PartialOrd> Tree<T> {
  fn contains(&self, target: T) -> bool {
    match self {
      Tree::Empty => false,
      Tree::Node { value, left, right } => {
        return if target < *value {
          left.contains(target)
        } else if target > *value {
          right.contains(target)
        } else {
          true
        };
      }, 
    }
  }
}
impl<T: PartialOrd> Tree<T> {
  fn contains(&self, target: T) -> bool {
    match self {
      Tree::Empty => false,
      Tree::Node { value, left, right } => {
        return if target < *value {
          left.contains(target)
        } else if target > *value {
          right.contains(target)
        } else {
          true
        };
      }, 
    }
  }
}

This method can't be tested unless we have a way to populate the tree with elements. The add method walks the tree until it hits the appropriate leaf node, at which point it overwrites the leaf with a non-empty node:

Rust
impl<T: PartialOrd> Tree<T> {
  fn add(&mut self, new_value: T) {
    match self {
      Tree::Empty => {
        *self = Tree::Node {
          value: new_value,
          left: Box::new(Tree::Empty),
          right: Box::new(Tree::Empty),
        };
      },
      Tree::Node { value, left, right } => {
        if new_value < *value {
          left.add(new_value);
        } else if new_value > *value {
          right.add(new_value);
        }
      }
    }
  }
}
impl<T: PartialOrd> Tree<T> {
  fn add(&mut self, new_value: T) {
    match self {
      Tree::Empty => {
        *self = Tree::Node {
          value: new_value,
          left: Box::new(Tree::Empty),
          right: Box::new(Tree::Empty),
        };
      },
      Tree::Node { value, left, right } => {
        if new_value < *value {
          left.add(new_value);
        } else if new_value > *value {
          right.add(new_value);
        }
      }
    }
  }
}

Here we make a Tree of u32 and populate it:

Rust
fn main() {
  let mut tree = Tree::<u32>::Empty;
  tree.add(3);
  tree.add(4);
  tree.add(5);
  println!("tree.contains(3): {:?}", tree.contains(3));
  println!("tree.contains(4): {:?}", tree.contains(4));
  println!("tree.contains(5): {:?}", tree.contains(5));
  println!("tree.contains(6): {:?}", tree.contains(6));
}
fn main() {
  let mut tree = Tree::<u32>::Empty;
  tree.add(3);
  tree.add(4);
  tree.add(5);
  println!("tree.contains(3): {:?}", tree.contains(3));
  println!("tree.contains(4): {:?}", tree.contains(4));
  println!("tree.contains(5): {:?}", tree.contains(5));
  println!("tree.contains(6): {:?}", tree.contains(6));
}

There are no vtables or vpointers when this code gets compiled. Instead, the compiler sees what types I plug in to the Tree, and it makes a separate compilation for each different use. Each is tailored to the type. The Tree for i32 will have machine code instructions that work with i32. The Tree for String will have machine code instructions that work with String. Because the types are known by the compiler, the execution will be faster than with subtype polymorphism. But parametric polymorphism only serves a single type, not a whole hierarchy.

TODO

Here's your list of things to do before we meet next:

Complete the middle quiz as desired.
One ready date remains. It is your final extension.
Canvas isn't expressive enough to calculate your final grade. However, you can calculate it just fine with some code or a spreadsheet. Weights are listed in the syllabus. Take the greater of your front and middle quiz scores. I started one in Google Sheets that you can copy.

See you next time.

Sincerely,

P.S. It's time for a haiku!

First it was NY Now you can ❤️ anything Because they're T-shirts
← Ad Hoc PolymorphismLab: Binary Search Tree →