Up a tree

You are ten feet above the ground, nestled among large branches. Beside you on the branch is a small bird's nest. In the bird's nest is a large egg encrusted with precious jewels, apparently scavenged by a childless songbird.

> take the egg

Taken.

> go down
> go south
> go east

Source code for this episode can be found here: https://github.com/ericlippert/flathead/tree/blog2

All right, enough bit twiddling and philosophizing. Let's start talking about the actual Z-machine architecture here. It is a very straightforward little virtual machine. We begin by dividing the state of the game up into two distinct buckets.

In the first bucket is a large array of bytes that is logically the "memory" of the virtual machine. This bucket contains all the code, all the strings, and data structures representing every object in the game. It also includes all the global variables. This first bucket we will call the "story state", for reasons which will become apparent.

In the second bucket we have local variables, the call stack, and temporary storage. We'll call this bucket the "interpreter state".

An interpreter implementation takes as its input a file which is simply a straight up serialization of the story state. We'll spend a lot of time in this series talking about how to decode that thing, but first, I need to go back to my first principles here. Remember that I said I was going to build this thing in a purely functional style: no side effects. How can that possibly work? The story contains all kinds of state which is constantly changing: the values of global variables, the relationships between game objects, and so on.

Well, remember how this works for immutable lists and stacks and dictionaries and whatnot. When you apply a change to an object, you don't change the object. You make a new object that looks just like the old one, except slightly different. Isn't that inefficient? No! Since the old object doesn't change, you can reuse as much of its state as possible in the new object!

But how on earth am I going to make an immutable array of bytes that emulates a mutable array of bytes? Well, it turns out that in the Z-machine, almost all of the memory stays the same all the time. All the code, all the strings, they don't ever change. In Zork, for example, there are only a few thousand bytes that change through the course of the game, and very few of them change on any given instruction.

Keeping track of a few thousand byte changes is nothing. We can easily do that. We'll just keep a copy of the original state, and an immutable lookup table that describes every byte that has changed.

So let's start with that. I want a data type which represents an immutable array of bytes where a write causes a new object to be created that contains the changed state. I want the interface to this data type to be:

• reading takes a byte array and an address and produces a byte
• writing takes a byte array, an address, and a byte, and produces a new byte array

What is an address? An integer obviously" NO WAIT! We decided last time that naked integers are to be avoided in a world where it is so cheap and convenient to tag them with their semantics. So let's start by defining a type:

type byte_address = Byte_address of int

I feel better already. We're also going to need an immutable map from integers to bytes. Fortunately one comes built-in:

module IntMap = Map.Make(struct type t = int let compare = compare end)

This one is a bit complicated. Both modules and types can be generic in OCaml, and this is the odd syntax for saying "I would like a module containing a generic dictionary from int to something to be specified later please."

I need to know if an address is valid. Remember, there is nothing too small to be put into a helper function:

let is_in_range (Byte_address address) size = 0 <= address && address < size let is_out_of_range address size = not (is_in_range address size)

Note that OCaml uses double-ampersand for Boolean-and, the usual less-than operators, but uses "not" rather than ! for Boolean negation.

And now our abstract data type. I'm going to put it in its own file, which logically defines a module; I'll talk about what precisely a module is in more detail later, but you can think of it as being a bit like a class and a bit like a namespace. Let's go through the immutable bytes module line by line:

open Typeopen Utility

This is like a using namespace directive in C#; it says that members of these modules can be used without qualification.

type t ={ original_bytes : string; edits : char IntMap.t}

We have here a new kind of user-defined type. Before we just made wrappers around ints. This is more like a struct; we have two fields, one of type string and one of type "map from integer to char". Think of IntMap.t as being like Dictionary<int, V>, and char IntMap.t is like Dictionary<int, char>.

Yes, generic types are specified backwards in OCaml; I'm not sure why the type parameter comes before the generic type. This strikes me as odd and I don't understand it yet.

The primary type in a module is traditionally called t for reasons having to do with generic modules that I'm not going to go into. Since inside the module it will almost never be referred to by name, and outside the module it will be Immutable_bytes.t, it doesn't matter that this name is not descriptive in the least.

Notice that the fields in the record type are separated by semis, not terminated by semis.

I'm using a string as the backing store for my immutable array of bytes. Yes, apparently OCaml lives in the world of 8-bit chars and non-Unicode strings. Parts of this language definitely feel like they're based on forty year old C libraries. (There is a mutable byte array type, but I'm pretty sure it's just a thin wrapper around a string, and I don't need mutability.)

Moving on. We know how to construct an instance of a wrapper type, but what about these record types? The traditional way to do it is to make a constructor function called make:

let make bytes = { original_bytes = bytes; edits = IntMap.empty }

To construct the actual instance we just put assignments to all the fields inside curly braces. We don't have to say we are constructing a Immutable_bytes.t. OCaml deduces from the fact that all the fields are supplied what the type should be.

It will be handy to know what the largest possible address is:

let size bytes = String.length bytes.original_bytes 

Note that fields of records are accessed with dots.

Is computing the length of a string O(1) as it is in C#, or O(n) in the size of the string as strlen is in C? I honestly don't know, and the documentation I've looked at doesn't seem to say. It would seem unfortunate to have to count the size of a large immutable string every time you access memory, but then again I haven't seen any unacceptable performance problem yet, so I'm not going to stress about it. If it turned out to be a problem I could easily cache the string length in another field in the record. It's only a few more bytes.

What does the read function do? It takes an Immutable_bytes.t record and an address, verifies that the address is in range, and then produces the byte:

let read_byte bytes address = if is_out_of_range address (size bytes) then failwith "address is out of range"

Several interesting points here.

We are seeing conditional expressions for the first time. Though they have a syntax reminiscent of a conditional statement, they have the semantics of a conditional expression. (That is, a ? : expression in C#.)

The consequence produces a failure exception which does not affect type inference. Note that since there are no statements per se, producing a failure exception is permitted as an expression, unlike in C#.

Again, nothing is manifestly typed. Note that in particular there is no annotation on bytes:

 else let (Byte_address addr) = address in let c = if IntMap.mem addr bytes.edits then IntMap.find addr bytes.edits else bytes.original_bytes.[addr] in int_of_char c

Bizarrely, for a language that has "option" types (which are like nullable value types in C#; either "some value" or "none") the map type requires you to check for membership ("mem") before trying to look up an item. I would have expected a method that returned the value if it existed and the "none" option otherwise. More on option types in a later episode!

Anyways, we check to see if we have an edit in the map of edits. If not then we go to the original string.

The indexing operator for strings is .[ ] which I think is charming.

The writing code takes a bytes record, an address and the new value, which is deduced to be an int.

We could check to see if the value being "changed" already has the given value, and if so, do nothing - simply return bytes. But setting a thing to itself seems unlikely, and so this is probably not a big win.

let write_byte bytes address value = if is_out_of_range address (size bytes) then failwith "address is out of range" else let (Byte_address addr) = address in let b = char_of_int value in { bytes with edits = IntMap.add addr b bytes.edits }

I find it slightly odd that the arguments to add are key, value, map, and not map, key, value, but whatever.

OCaml has no implicit conversions; the char_of_int method is necessary to convert an int to a char.

Again, remember, everything here is immutable. To construct a new record we could write another make-like function, but we have a nice syntactic sugar here for "I want a record that has all the fields the same as bytes, except I want field edits replaced with the value of that name given here". We could also have said

 let new_edits = IntMap.add address b bytes.edits in { bytes with edits = new_edits }

Or, even nicer, I could have used this syntactic sugar:

 let edits = IntMap.add address b bytes.edits in { bytes with edits }

OCaml figures that I want to make a copy of the record with field "edits" replaced by the value of local "edits".

All right, we have a very simple abstract data type. Let's take it out for a spin:

let () = let addr1 = Byte_address 1 in let bytes_a = Immutable_bytes.make "Hello world" in let bytes_b = Immutable_bytes.write_byte bytes_a addr1 65 in let b_a = Immutable_bytes.read_byte bytes_a addr1 in let b_b = Immutable_bytes.read_byte bytes_b addr1 in Printf.printf "%d %d\n" b_a b_b

And sure enough, the "mutated" version is different but the original version retains it's state.

Next time on FAIC: We'll build a slightly more complicated memory model on top of this foundation.