You are on what used to be a large lake, but which is now a large mud pile. There are “shores” to the north and south. Half-buried in the mud is an old trunk, bulging with jewels.
A suspicious-looking individual with a large bag just wandered through and quietly abstracted some valuables from the room.

> go north

What a jerk! Makes you want to, oh, I don’t know, hit the thief with the axe or something.

Code for this and the next couple episodes is at

Before I get to the real subject of this episode, a quick note about OCaml modules. We know that physical files declare modules. (There is also a way to declare sub-modules within a file but I’m not going to use it.) And we know that to access a member of a module from outside the module, you have to either say open Module_name or fully qualify the access: Story.version story. What if you want to access a member of a record from outside the module? If I create a new module, how do I access, say, the opcode field of an instruction record instr? The syntax is instr.Instruction.opcode which I find distateful in two ways.

First I find that putting the qualifying name in the middle of the expression just weird. It makes me feel like Instruction should be a field itself. Second, all my years of C# are yelling “fields are private implementation details of a type; write property accessor functions to access fields!” So, I don’t know if this is good OCaml style or not, but that’s what I’ve done. I’ve added

let opcode instr = instr.opcode 

accessors, and now they can be used out-of-module via Instruction.opcode instr, which I find much more pleasant to the eye.

There is, incidentally, a way in OCaml to say “only the following members are public members of this module”; I haven’t used it yet but I might start doing so as the modules get more complicated.

Moving on. Today I want to answer the question “where does this instruction go next?” It should come as no surprise that instructions in the Z-machine are organized into routines which call each other; I am going to limit myself to the question “where does this instruction go in this routine?” I’m not going to worry about either calls, which go to another routine, or returns, which go to the instruction following the call. Rather, I’ll treat calls as simply going to their next instruction, and returns as going nowhere.

This question is easily answered. There are three possibilities: some instructions go to the immediately-following-in-memory instruction. Instructions with branches might go to that instruction, or the might also go to the branch target. And jump instructions – opcode OP1_140 – evaluate the operand and do an unconditional relative jump.

First things first. There are nine instructions which do not go on to the following instruction:

let continues_to_following opcode =
  match opcode with
  | OP2_28 (* throw *)
  | OP1_139 (* ret *)
  | OP1_140 (* jump *)
  | OP0_176 (* rtrue *)
  | OP0_177 (* rfalse *)
  | OP0_179 (* print_ret *)
  | OP0_183 (* restart *)
  | OP0_184 (* ret_popped *)
  | OP0_186 (* quit *) -> false
  | _ -> true

This helper method is a bit odd. You would think it would return an expression of type instruction option, but it returns instruction list. I have my reasons, which will become apparent soon.

let following_instruction instr =
  if Instruction.continues_to_following (Instruction.opcode instr) then
    let (Instruction addr) = Instruction.address instr in
    let length = Instruction.length instr in
    [Instruction (addr + length)]

Second, branches. We already deduced the absolute address when we created the branch:

let branch_target_instruction instr =
  match Instruction.branch instr with
  | None
  | Some (_, Return_false)
  | Some (_, Return_true) -> []
  | Some (_, Branch_address address) -> [address]

Third, the jump instruction is not a branch instruction; it jumps unconditionally. Its operand is permitted to be any operand – a large constant, small constant, local variable, global variable or stack pop – but in practice it is rare to see anything other than a large constant. The operand is interpreted as a signed quantity, and the computation of the absolute address is analogous to how it is done for branches:

let jump_address instruction offset =
  let (Instruction addr) = instruction.address in
  Instruction (addr + instruction.length + offset - 2)

Again we do this odd thing with returning a list instead of an option:

let jump_target_instruction instr =
  match (Instruction.opcode instr, Instruction.operands instr) with
  | (OP1_140, [Large offset]) ->
    let offset = signed_word offset in
    [ Instruction.jump_address instr offset ]
  | _ -> []

Next time on FAIC: we’ll put everything in this and the previous episode together.


One thought on “Reservoir

  1. You don’t have to use fully qualified record fields, you can use type-based disambiguation like so:

    module M = struct type t = { a : int } end
    let f (m : M.t) = m.a

    Now, it requires type annotations, if the immediate context doesn’t allow to predict the type of the record . However I find it better behaved than putting fully qualified paths, because of this:
    module M2 = struct type t = M.t end
    let f m = m.M2.a (* doesn’t type, you’d need to have type t = M.t = { a : int } above for that to work *)
    let f (m : M2.t) = m.a (* types *)

    Second, records are frequently abstract for the same reason any other type is abtract (and in that case, it is frequent to have the kind of accessor functions you wrote). But saying in general “the fields are an implementation detail” sounds strange to me: if so, tuples and sum types would also always be immediately hidden behind functions to extract information from them, rendering pattern matching useless. Sometimes, the interface of a piece of data is its implementation, like for options and lists.

    And finally, ocaml has nested disjunctive patterns, which can be very nice:
    let branch_target_instruction instr =
    match Instruction.branch instr with
    | None
    | Some (_, (Return_false | Return_true)) -> []
    | Some (_, Branch_address address) -> [address]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s