Twisting passage

This is a crooked corridor from the north, with forks to the southwest and south.

> go north
> go west
> go south
> go up
> put the skull and the emerald in the trophy case

crystal skull: Done.
large emerald: Done.

> go east
> open the sack

Opening the brown sack reveals a clove of garlic, and a lunch.

> take the garlic


> go west
> go down
> go northeast
> go north
> go north

Nine down, six more treasures to go.

Code for this and the next episode can be found in

All right, let’s at long last create an interpreter type. Our interpreter will have to maintain a lot more state than this as we add features, but it is nicely svelte in the beginning. An interpreter is just a thin wrapper around three pieces of information: the story state, the set of stack frames, and the address of the instruction we are about to execute:

type t =
  story : Story.t;
  program_counter : instruction_address;
  frames : Frameset.t;

In the beginning we have a story. The first instruction to execute is found in the story header. And the frame set has a first frame with no locals, no return address, and an empty evaluation stack:

let make story =
    program_counter = Story.initial_program_counter story;
    frames = Frameset.make Frame.empty;

As we discussed last time, the primary services we’ll need to execute any instruction are (1) reading values of variables mentioned in operands, and (2) writing values of variables mentioned in stores. So let’s make some helper methods for each of those.

Again note that one-line methods are the methods most likely to be correct.

let current_frame interpreter =
  Frameset.current_frame interpreter.frames

let peek_stack interpreter =
  Frameset.peek_stack interpreter.frames

let pop_stack interpreter =
  { interpreter with frames = Frameset.pop_stack interpreter.frames }

let push_stack interpreter value =
  { interpreter with frames = Frameset.push_stack interpreter.frames value }

let read_local interpreter local =
  Frameset.read_local interpreter.frames local

let write_local interpreter local value =
  { interpreter with frames = Frameset.write_local interpreter.frames local value }

let read_global interpreter global = interpreter.story global

let write_global interpreter global value =
  { interpreter with story = Globals.write interpreter.story global value }

Since reading an operand can change the state of our immutable interpreter, unfortunately the read code has to return both a value and the new interpreter, as a tuple. The writer just returns the new interpreter.

let read_variable interpreter variable =
  match variable with
  | Stack -> (peek_stack interpreter, pop_stack interpreter)
  | Local_variable local -> (read_local interpreter local, interpreter)
  | Global_variable global -> (read_global interpreter global, interpreter)

let write_variable interpreter variable value =
  match variable with
  | Stack -> push_stack interpreter value
  | Local_variable local -> write_local interpreter local value
  | Global_variable global -> write_global interpreter global value

Something to note about those last couple of functions: remember how I said that it was a bit arcane that we could have multiple levels of wrapper? That the number 5 was in fact Local_variable (Local 5), for instance. Well, that is sure paying off now. What does write_local take? a Local of int. What is the value wrapped by a Local_variable? a Local of int! It all works out beautifully, and the type system makes sure that I cannot accidentally pass a global variable number to my local store or vice versa.

Now that we have the ability to read and write any variable, interpreting an operand is easy. (Again, reading an operand can change state, so it must return both the value and the new interpreter.)

let read_operand interpreter operand =
  match operand with
  | Large large -> (large, interpreter)
  | Small small -> (small, interpreter)
  | Variable v -> read_variable interpreter v

We can then use this helper to produce a sequence of argument values along with the new interpreter state:

let operands_to_arguments interpreter operands =
  let rec aux (args, interp) ops =
    match ops with
    | [] -> (args, interp)
    | h :: t ->
      let (argument, new_interpreter) = read_operand interp h in
      aux ((argument :: args), new_interpreter) t in
  let (args_rev, final_interpreter) = aux ([], interpreter) operands in
  ((List.rev args_rev), final_interpreter)

Notice that the accumulated state comes out the other end in the wrong order, so we have to call rev on it. I suppose it was overkill to make this method tail recursive since there are never more than 8 operands to any instruction.

Handling the store portion of an instruction is easy; it’s just an optional variable:

let interpret_store interpreter store result =
  match store with
  | None -> interpreter
  | Some variable -> write_variable interpreter variable result

And for debugging purposes a couple of handy helper methods:

let display_current_instruction interpreter =
  let address = interpreter.program_counter in
  let instruction = Instruction.decode interpreter.story address in
  Instruction.display instruction interpreter.story

let display interpreter =
  let frames = Frameset.display interpreter.frames in
  let instr = display_current_instruction interpreter in
  Printf.sprintf "\n---\n%s\n%s\n" frames instr

All right, we are in very good shape here. Next time on FAIC: we’ll copy the arguments to locals and actually do the call!


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