programming grimoire [4]::populating a universe

Greetings, sorcerer. It has been a while.

Indeed, a couple of months ago we told a tale of memory, but I must confess that I was never quite happy with the manner of presentation there; this story has had to be re-ordered a bit. It is not always clear what pillar rests on what in these lands, is it?

We have talked about the types that data can have, a bestiary or demonology of sorts. But that bestiary is not a static thing.

  1. riddles past
    1. The second orb
    2. The third orb
  2. creating new types
    1. structs
    2. enums
    3. pattern matching
    4. sum and product types
    5. generic types, Option
    6. methods
  3. a real example
  4. a fourth orb to ponder

riddles past

First, though, shall we have a quick look at the orbs?

The second orb

In part 2, we were learning about names and scopes; I posed a program, and asked you to figure out what it says. The answer is XYZZY, a magic word of fine vintage. How does it work?

The second orb

Here’s the program:

fn main() {
    let spell = "Y";
    {
        let spell = "X";
        print!("{}", spell);
    }
    {
        print!("{}", spell);
        let spell = "Z";
        print!("{}{}", spell, spell);
    }
    print!("{}", spell);
}

On the first line we store "Y" behind the name spell in the outer scope.

We enter the inner scope, and assign "X" to spell, which shadows the spell of the outer scope. Then we print. The most recent definition of spell available in this scope contains "X", so we print X.

We exit this scope. The inner assignment of spell is dropped, falling away to reveal the spell outside.

We enter a new scope. Now when we print spell, there are no assignments in this scope, but there’s one in the next scope up, which has "Y" behind it. So we’re at ‘XY’.

Now we assign "Z" to the name spell, once again shadowing the outer spell. The print here prints it twice, so we are at ‘XYZZ’.

We exit the scope, and the assignment falls away, once again leaving spell as Y. We print this Y, and we get XYZZY.

That is logically what’s going on. But does the compiler actually do all of this? Let’s drop it into Compiler Explorer and find out. I kind of expected it to be able to see that the program just stores the whole string XYZZY somewhere, but no, it doesn’t seem to be able to simply optimise that away. In fact it produces four separate calls to the print function. Either this machinery is just too opaque or there is some reason the compiler can’t safely make this optimisation.

The third orb

In the third orb, I suggested you could write a program which draws an expanding box by clearing the screen and waiting. Here’s one such program:

fn print_room(width: u32, height: u32) {
    print_horizontal_wall(width);

    for _ in 0..height {
        print!("#");
        for _ in 0..width {
            print!(".");
        }
        println!("#");
    }

    print_horizontal_wall(width);
}

fn print_horizontal_wall(width: u32) {
    for _ in 0..width + 2 {
        print!("#")
    }
    //print a newline to end the row
    println!();
}

fn clear_console() {
    print!("{esc}c", esc = 27 as char);
}

fn main() {
    for tick in 0..60 {
        clear_console();
        print_room(tick, 10);
        std::thread::sleep(std::time::Duration::from_millis(1000 / 60));
    }
}

Each time around, the loop clears away all the current text in the console, prints a slightly bigger room, and then tells the operating system that it’s done with its work for now but please could it be woken up in 1/60 seconds.

Previously our computations were pretty abstract, all we cared to see was the final answer… but here we’re placing our program in the world, and worrying about how much time things take. (Can we be sure that the operating system, which is juggling this and hundreds of other programs, will give us a consistent framerate?) Time will be immensely important later when we do more graphics stuff. But we won’t worry about that yet.

No, there is another part of the temple we need to build in our minds at this point… something we’ve been dancing around a little in the story so far.

creating new types

We have already introduced the idea of binding variables with let, and that variables have types…

let x: u32 = 69420;

So far we mostly talked about number types, and mentioned in string types in passing. (There are some complications to string types in Rust, which we’ll hold off on discussing for now.)

These types can be thought of in a sense as the ‘atoms’ of a program (with bits and bytes and subatomic particles). What defines them is how they interact.

For example, let’s say we have two 32-bit types. One of them has the binary value 10001001 00110100 1010010 00100101 and the other has the value 10000000 10010010 0001111 11011011.

What happens when you add them together? Well, if they’re floating point values, the answer is 10001001 00110101 01101101 0101101, and if they’re unsigned integers, the answer is 10000100 11100011 01100010 00000000.

Types tell you (and the compiler!) which one of these operations is the relevant one for ‘add these two values together’. They’re pretty important.

However, for complex behaviour, we need more than just numbers. It’s time to introduce two new keywords of Rust: struct and enum.

structs

We’ll start with struct because that’s slightly simpler.

Like naming a variable or a function, bestowing a name to a type brings “something” new into existence—at least, the nebulous ‘as-if’ existence that is bestowed to computer programs. In the simplest case, we can do it like so…

struct AmuroRay;

This declares a new type to our program (get it ha ha). If, somewhere in the names known to the module, this struct has been declared, it is possible to create new variables which have that type. In this case, the name of the type is used both to state the value of that type, and to name the type itself.

let x: AmuroRay = AmuroRay;

That is, x has both the type AmuroRay and the value AmuroRay. The type AmuroRay has exactly one possible value, that being AmuroRay. We call this kind of struct a unit struct, and it takes up zero space.

Is this of much use? In the types of programs we’ve created so far, not yet. We could declare a function which requires an AmuroRay…

fn get_in_the_robot(pilot: AmuroRay) -> Gundam {
    //who knows how to construct a gundam really
}

…which would mean that we would only be able to call this function if we’re able to construct an AmuroRay. But mostly I just want to get the basics down. More likely, we want a struct that can take multiple values. To do this, we can use one of the existing types…

struct CharAznable(u8);

Now, we’ve wrapped a u8 type piece of data inside a CharAznable piece of data.

This means that the CharAznable type takes up the same amount of space as a u8 (one byte). In fact, its representation bits is exactly the same as a u8. Types only exist in the compiler.

Types determine the rules of what can be done with a piece of data (and how to do it). For example, if you have two u8s, you can add them together…

let a : u8 = 12;
let b : u8 = 25;
let c : u8 = a + b;//no problem!

But if you try to add a CharAznable to a u8 you get an error…

let a = CharAznable(15);
let b = 10;
let c = a + b; //compiler error!

In order to determine what happens when you add CharAznable to something, we would need to define the relevant trait; we’ll get to that subject soon. What we can do is use a pattern match to extract the inner value:

let char = CharAznable(10);
let CharAznable(char_number) = char;//now we have moved 10 into the name char_number
println!("char_number: {}", char_number);//prints 'char_number: 10

Why would we want to wrap up a value like this? Hold on, we’re building up to something cool—but at this stage, one simple reason is to make the compiler have our back.

Let’s say we have a program with some values in metres, and some in feet. We don’t want to make the mistake of using metres when we mean feet or vice versa—that sort of thing can crash a space probe. So let’s make some types…

struct Metres(f32);

struct Feet(f32);

We can then define addition for metres to metres, and feet to feet, and more importantly, functions which do the relevant conversion for adding measurements in different units together. (I won’t write the code here just yet, since we need to first explain traits and generics.)

Still, so far it’s probably hard to see what the fuss is all about.

The third way of writing a struct lets you combine multiple pieces of data (called fields) into one type. This is written like so, listing the type of each field:

struct Mech {
    height: Metres,
    weapon: Weapon,
}

Then, we can create a new instance of this type by filling out the fields:

let gundam = Mech {
    height: Metres(18.0),
    weapon: Weapon::BeamRifle,
};

Every instance of a Mech must have a height and a weapon. It’s impossible (as in, the compiler won’t let you!) to create a Mech without defining its height and its weapon.

So we’ve created a type which is a combination of several other types! It takes at least as much space as the space of all the fields added together.

One reason we might want to do this whenever we want to bundle several pieces of data together. For example, we might have a list of all the enemies in an area, and each one has all the stats associated with it stored inside. We could imagine having a big list of all the enemies. Then, if the player casts a fireball, we could go down the list of enemies, checking whether each is close enough to be affected and modifying its hit points if so.

There are other more exciting reasons, but first let’s visit the other way to create new types in Rust.

enums

A struct made of several other smaller types can hold any combination of the values of those types. Sometimes, however, this is not what we want. Sometimes we want to limit the number of possible values of a type.

By writing an enum, we list all the possible values of a type, giving each one a name. In the simplest case it can be just that…

enum Weapon {
    BeamRifle,
    BeamSaber,
    HeavenPiercingDrill,
    HyperBazooka,
}

and we can create these individual values by first writing the name of the type, then ::, then the name of the value:

let my_cool_sword: Weapon = Weapon::BeamSaber;

Internally, Rust picks a numerical type to store which variant of thing is being made (for example, in this case the BeamRifle is 0, the BeamSaber is 1, etc.), but as far as your program is concerned, you deal only with these names.

So far, this is similar to enums in a language like C: a handy way to give names to specific values and make your program easier to read.

However, Rust enum variants can do something else: they can have data associated with them, just like a struct!

enum Weapon {
    BeamRifle {
        //a variant with a named field
        beams: u32,
    },
    BeamSaber {
        length: f32,
    },
    HyperBazooka(u32),   //a variant with an unnamed field
    HeavenPiercingDrill, //a unit variant with no fields
}

pattern matching

OK, here’s one of the coolest programming language features ever invented. It won’t seem like much at first, but this thing will be your best friend and you’ll miss it in every other language.

Supposing we have a value of this type, we can handle different variants using a match statement and pattern matching…

fn weapon_damage(weapon: Weapon) -> u32 {
    match weapon {
        //this binds the name 'beams', just for this arm
        Weapon::BeamRifle { beams } => beams * 1234,
        //if you're not using certain fields you can indicate this with ..
        Weapon::BeamSaber { .. } => 3000,
        //for unnamed fields, you can use any name you please
        //you can also write conditions for a match arm with 'if'
        Weapon::HyperBazooka(missiles) if missiles > 0 => missiles * 9000
        //if you're not using the field, you can use the name _ to say so
        Weapon::HyperBazooka(_) => 5 //5 damage from throwing the empty hyper bazooka
        Weapon::HeavenPiercingDrill => 10000,
    }
}

When you use a match statement, you must cover every possible variant of its input. The compiler will insist on it, in fact!

That said, if you only care about what to do for few of them, you can use _ as a wildcard to cover the rest…

fn is_a_melee_weapon(weapon: Weapon) -> bool {
    match weapon {
        Weapon::BeamSaber { .. } => true,
        Weapon::HeavenPiercingDrill => true,
        _ => false
    }
}

There is a small risk here: if you were to later go back and add new Weapon variants, the compiler wouldn’t warn you that you aren’t handling those cases. So it’s sometimes better to list them all. It Depends.

As a bonus, you can combine multiple conditions with the symbol |, which is generally used to represent the ‘or’ operation in programming languages. (On most English-language keyboards, that’s shift-backslash.)

fn is_a_melee_weapon(weapon: Weapon) -> bool {
    match weapon {
        //the | character can be used to combine multiple conditions
        Weapon::BeamSaber { .. } | Weapon::HeavenPiercingDrill => true,
        _ => false
    }
}

(This particular match expression could be simplified to a macro, but that’s a lesson for another day.)

The really cool thing about match statements is that you can pin down whichever parts of the pattern to be matched, bind variables, all sorts of stuff, all in one expression. Let’s say we wanted to handle mechs which are taller than \(10\unit{m}\) and carry a beam rifle…

//assume we defined Scariness already

fn mech_scariness(mech: Mech) -> Scariness {
    match mech {
        Mech {
            height: Metres(m), //we bind the name m here
            weapon: Weapon::BeamRifle { beams },
        } if m > 10.0 && beams > 0 => Scariness::ReallyScary,
        Mech {
            weapon: Weapon::HyperBazooka(5),
            .. //ignore height for this pattern
        } => Scariness::OhGodOhGodHelp,
        _ => Scariness::PrettyScaryIGuess,
    }
}

If you leave any cases out, the compiler will tell you! And it will put together all the logic needed to efficiently check which branch to go down.

If you want to take away one bit of magical wisdom here, it’s that match statements are amazing and wonderful things.

sum and product types

OK, what we’ve told you so far is perfectly sufficient to get going with programming, but would you indulge a little theoretical aside?

Rust’s enums are one of my favourite features of the language, but they’re actually borrowed from an entirely different branch of the programming language family tree: functional programming languages, such as Haskell. We won’t talk too much about how those work in this article, but let me give another angle on structs and enums with this in mind.

A struct is known as a ‘product’ type (as in, multiplication). You can think of it like this: if type A has \(a\) possible values, and type B has \(b\) possible values, then if you have a struct like…

struct C {
    a: A,
    b: B,
}

then how many possible values can C have? Well, it can have any combination of A and B values, so the total is \(a\times b\).

For example, if there were three possible values of A, let’s call them A::A1, A::A2, and A::A3, and two values of B called B::B1 and B::B2, you’d get the following six combos:

let c11 = C { a: A::A1, b: B::B1 }; let c12 = C { a: A::A1, b: B::B2 }; 
let c21 = C { a: A::A2, b: B::B1 }; let c22 = C { a: A::A2, b: B::B2 }; 
let c31 = C { a: A::A3, b: B::B1 }; let c32 = C { a: A::A3, b: B::B2 };

and there are indeed \(2\times3=6\) values.

For this reason, we call a struct a ‘product type’.

Now let’s say we make an enum which can have variants containing A and B:

enum E {
    VariantA(A),
    VariantB(B),
}

How many variants can E have? Well, if it’s E::VariantA, then it can have as many values as the inner A; likewise if it’s E::VariantB it can have as many values as the inner B; so the total is A+B.

With the same A and B, that looks like:

let ea1 = E::VariantA(A::A1);
let ea2 = E::VariantA(A::A2);
let ea3 = E::VariantA(A::A3);

let eb1 = E::VariantA(A::B1);
let eb2 = E::VariantA(A::B2);

which is \(3+2=5\) possible values, as you’d expect.

For this reason, an enum is known as a ‘sum type’. It’s much rarer for a programming language to have sum types than product types.

generic types, Option

I’m just going to introduce this briefly now, but they’re so fundamental it’s worth knowing about them already.

When you create a type, instead of defining just one type, you can represent a whole set of different types, all depending on some other type. We call these ‘generics’, and they’re written like this:

struct IHeardYouLikeTypes<T> {
    type_in_your_type: T,
}

In effect, this creates a whole variety of different types. There can be an IHeardYouLikeTypes<f32>, an IHeardYouLikeTypes<Mech>, and anything else. Most of the useful types the Rust standard library gives you like Vec, Arc, Box, Pin and so on are generic types.

There are two particularly special generic types which are used all over Rust. One is the Option type. This is Rust’s way of representing a thing that isn’t necessarily there.

Unlike other programming languages, there is no null in Rust. It’s avoiding what Tony Hoare called his billion dollar mistake. In Rust, if something is allowed to be absent, you have to say so explicitly.

We already know how to write our own Option…

enum Option<T> {
    Some(T),
    None
}

So, you can put an Option<T> in a field if there isn’t always something there, but you want to make space for it. You can return an Option from a function if it’s not guaranteed to return a result.

But Option comes with all kinds of useful methods—hold on, what’s that? We haven’t explained methods yet?

methods

OK, so, we can define functions that ‘belong to’ a particular type. The behaviours of a type are defined with an impl block, which is short for ‘implementation’. In this block we can use Self instead of the type name.

impl Mech {
    fn new(height: Metres, weapon: Weapon) -> Self {
        Self {
            height,
            metres,
        }
    }

    //this function (with '&self') looks up information on the thing it's called on
    fn has_melee_weapon(&self) -> f32 {
        is_a_melee_weapon(self.weapon)
    }

    //this function (with '&mut self') can modify the thing it's called on
    fn pick_up_weapon(&mut self, weapon: Weapon) {
        self.weapon = weapon;
    }

    //this function (with 'self') consumes the thing it's called on
    fn transform(self) -> Self {
        Self {
            height: self.height * 10000.0,
            weapon: self.weapon,
        }
    }
}

This gives you the other half of creating new types: defining what can be done with them.

If there is no self, &self or &mut self argument, you can call the function like this with ::. We call this an ‘associated function’, because it’s a function that’s (get this) associated with a type…

let gurren_lagann = Mech::new(Metres(12.0), Weapon::HeavenPiercingDrill);

If there is a self argument, it’s called a ‘method’! We can take any existing mech and call it with ., with the thing it’s called on going into the self argument.

let melee = gurren_lagann.has_melee_weapon();
let super_galaxy_gurren_lagann = gurren_lagann.transform();

Note that there are three ways to use self here which behave differently. That’s because we’re sneakily introducing references—they’re explained in detail in the next article.

For now, just note:

There is a great deal more to say about this (including what those useful methods are that I teased on the Option type), but we could stand to make this all a bit more concrete.

a real example

We have, at this point, built something like one wall of a house. The other walls include ‘Traits’, which let you write functions which work with multiple different types at once, without knowing about their internal details. But that’s a pretty abstract concept to swallow, so hold on for now.

So far, this story has been made of silly toy examples that exist more to illustrate a point than do anything we’d really want to do. Let’s try doing something a bit more concrete: a piece of the dungeon game we’ve been sketching.

We would like there to be things to inhabit our dungeon. For example, players, monsters and so on. These things probably want to have a position where they live, so let’s make a struct for that…

struct Position {
    x: u32,
    y: u32,
}

We can represent the various things that might live underground with an enum…

enum CreatureType {
    Player,
    Gremlin,
    Slime,
    RustMonster,
    MindFlayer,
    Minotaur,
    Dragon,
    Lich,
}

Maybe creatures can carry items too…

enum Item {
    BrokenBottle,
    Sword,
    EstrogenPotion,
    ProgrammingGrimoire,
    HyperBazooka,
}

We have two bits of data, so let’s put them together in a struct…

struct Creature {
    position: Position,
    nature: CreatureType,
    carrying: Option<Item>,
}

Let’s say we want a function which checks if a creature is in a particular location, and a function which picks a suitable character to represent it.

impl Creature {
    fn is_at(&self, point: Point) -> bool {
        self.position.x == point.x && self.position.y == point.y
    }

    fn visual(&self) -> char {
        self.nature.visual()
    }
}

impl CreatureType {
    fn visual(&self) -> char {
        //brings Player, Gremlin etc. into scope as type names
        use CreatureType::*;
        
        match self {
            Player => '@',
            Gremlin => 'g',
            Slime => 'P',
            RustMonster => 'R',
            MindFlayer => 'h',
            Minotaur => 'H',
            Dragon => 'D',
            Lich => 'L',
        }
    }
}

Now, let’s modify our dungeon drawing function.

fn print_room(width: u32, height: u32, creature_1: Creature, creature_2: Creature) {
    print_horizontal_wall(width);

    for row in 0..height {
        print!("#");
        for column in 0..width {
            if creature_1.is_at(Position { x: column, y: row }) {
                print!("{}", creature_1.visual())
            } else if creature_2.is_at(Position { x: column, y: row }) {
                print!("{}", creature_2.visual())
            } else {
                print!(".");
            }
        }
        println!("#");
    }

    print_horizontal_wall(width);
}

fn print_horizontal_wall(width: u32) {
    for column in 0..width+2 {
        print!("#")
    }
    //print a newline to end the row
    println!();
}

Now, for each location, we check whether any creatures are there. If there is a creature there, we draw that creature; otherwise, we draw a ‘.’.

We can call this function with some creatures:

fn main() {
    let player = Creature {
        position: Position { x: 3, y: 0 },
        nature: CreatureType::Player,
        carrying: Some(Item::ProgrammingGrimoire),
    };
    let rust_monster = Creature {
        position: Position { x: 8, y: 2 },
        nature: CreatureType::RustMonster,
        carrying: None,
    };
    print_room(11, 3, player, rust_monster);
}

Run this, and we will see them hanging out in the dungeon:

#############
#...@.......#
#...........#
#........R..#
#############

We’re still a long way from Nethack! But hopefully this gives a glimpse of how we might build up the skeleton of our program with its types.

Still, it’s clear we’re missing a few pieces of the puzzle. What if we have more than two creatures? How will we respond to input?

Before we get there, though, I need to tell you a bit about where all these variables actually live.

a fourth orb to ponder

OK, this orb is pretty multifarious.

Right now, our position code has y = 0 at the top of the dungeon. If we wanted it to count up from the bottom row of the dungeon instead, how would you modify this code?

Now, give these a shot to make this a bit more like a dungeon game…

Comments

Add a comment
[?]