Forest path

This is a path through a dimly lit forest, curving from south to east. A large tree with low branches stands by the edge of the path. On the ground is a pile of leaves.

> count the leaves

69,105.

> climb the tree

Code for this episode can be found at

https://github.com/ericlippert/flathead/tree/blog1

Instructions for installing OCaml can be found in the readme, or in the first episode in this series.

Last time we explored the question "how do I get some number of bits out of a word, starting at a particular bit?" The code we came up with was:

let fetch_bits high length word = let mask = lnot (-1 lsl length) in (word lsr (high - length + 1)) land mask

I wrote this helper method and a few others like it and everything was great, right up until I spent I kid you not a solid hour trying to figure out why a computation was wrong:

blah blah blah (fetch_bits branch 5 6) blah blah blah

Now I've made it pretty clear where the mistake is here, but I assure you it was by no means clear what was wrong when the program started giving me completely crazy results.

The problem of course is that we have a function that takes three integers and I passed them in the wrong order. This gets 5 bits of the number 6, starting at bit "branch", when I intended to say 6 bits of number "branch" starting at bit 5.

This is of course an easy bug in most languages. In C#, if I had a similar helper method, I could easily have written FetchBits(b, 5, 6) just as easily, and been just as wrong.

There are a number of things I could have done to prevent the bug. OCaml, like C#, allows arguments to be annotated with the name of the corresponding parameter, which certainly would have been a big help. But I am not in the habit of using this feature, and I was thinking: surely in a language with excellent type inference, there ought to be a way to have the compiler itself detect the error.

Writing this bug really got me thinking about how powerful a tool the type checker is in a statically typed language, and what limited use we make of it. A statically typed language is a tool for producing a partial proof that the program is correct, or at least not broken in some obvious, detectable way.

I also started thinking about how many different things the Z-machine uses integers for. We're only a couple episodes in and we've seen bit numbers, bits and words. The Z-machine uses integers to identify addresses, variables, branch modes, opcodes, characters, screen widths, and dozens upon dozens more things, none of which make any sense to be assigned to each other. So:

Principle #3: Use "naked" primitive types like integers and bools as little as possible. Use the type system to both express meaning and provide evidence of correctness.

As we'll see, by using the type system wisely we can also make the code easier to understand and to emphasize its meaning, rather than its mechanisms.

A nice idea. How do we do it?

OCaml both allows and encourages creation of super-lightweight "wrapper" types around any other type; I think of them as "tagging" the underlying type with a meaning, much the same way that an enumerated type in C# is essentially just a meaningful wrapper around an integral type. (They are not exactly enumerated types; later on we'll use a similar technique to make enumerated types in OCaml.) The type declaration could not be simpler:

type bit_number = Bit_number of inttype bit_size = Bit_size of int

The left of the equality gives a name to the type. The right of the equality gives a constructor: to construct an instance of bit_number, we say what constructor we want to use: Bit_number. Let's try it out:

let b = fetch_bits (Bit_number 5) (Bit_size 6) 0xBEEF

Hmm. That gives us a type checking error:

Error: This expression has type bit_number but an expression was expected of type int

We will need to do bit arithmetic on the wrapped number, which means that there needs to be a way to unwrap it. Let's rewrite fetch_bits as follows:

let fetch_bits (Bit_number high) (Bit_size length) word = let mask = lnot (-1 lsl length) in (word lsr (high - length + 1)) land mask

And now our call succeeds. OCaml's type checker says "I need something in the first argument that matches the pattern an integer wrapped in a bit number, and I wish to name that integer high".

Now, on the one hand we now have solved the problem; an attempt to pass a naked integer for either the bit number or the bit size will fail, and similarly so will any attempt to swap the number and the size. The type system now guarantees that I cannot write my bug! But at what cost?

let result = fetch_bits (Bit_number 5) (Bit_size 6) word

Ugly! But hey, if I am going to be passing constants to those things then why don't I just define some constants?

let bit0 = Bit_number 0let bit1 = Bit_number 1...let size1 = Bit_size 1let size2 = Bit_size 2...

I can easily define all the constants I need. And now my code looks like this:

let result = fetch_bits bit5 size6 word

The code is not only completely type-safe, preventing me from making stupid transposition bugs, but it is also far more self-documenting than any of my earlier attempts. The code does not prevent stupid bugs like asking for ten bits starting at bit two, but I think I am unlikely to write that bug now; if I felt that I was then I could put additional checks into the helper method.

If you take a look at the code for this episode on github you'll notice that I've put the type declarations and utility functions and main method all in separate files. Obviously that is a bit silly for such a small example, but we'll be adding a lot more code soon and it will be convenient to have logical areas separated into different modules. More on that later.

All right, that's enough on bit twiddling. Next time in this series: we'll take a look at the "story file", which is the heart of the Z-machine.