Slide room

This small chamber appears to have been part of a coal mine. To the west and south are passages, and a steep metal slide twists downward.

> go west


Well I guess now we know where the unclimbable steep metal ramp in the cellar comes from. But I cannot help but think that the topography of the great underground empire lacks a certain consistency. Somehow this slide goes under the reservoir?

Code for this episode can be found in https://github.com/ericlippert/flathead/tree/blog14.

We can divide instructions into four categories:

  • Weird instructions, like call, ret, quit, restore, and so on, which make major changes to interpreter state and control flow.
  • Instructions which both cause a state change and produce a result, like inc_chk, which both increments a variable and branches depending on its value.
  • Instructions which compute a value but do not change interpreter state to do so. The result is then either stored, or used as the Boolean in a conditional branch. (Or, in some rare cases, both.)
  • Instructions which compute no value, but do change the interpreter state. storew, for example, writes a value into an array but the instruction has neither a store nor a branch portion.

Weird instructions get their own custom handlers. For all the rest I want to make helper methods so that the handlers for each instruction can be concerned with the “body” of that instruction, rather than the common details of how to handle the store and branch:

let interpret_instruction interpreter instruction handler =
  let (result, handler_interpreter) = handler interpreter in
  let store = Instruction.store instruction in
  let store_interpreter = interpret_store handler_interpreter store result in
  interpret_branch store_interpreter instruction result

let interpret_value_instruction interpreter instruction handler =
  let result = handler interpreter in
  let store = Instruction.store instruction in
  let store_interpreter = interpret_store interpreter store result in
  interpret_branch store_interpreter instruction result

let interpret_effect_instruction interpreter instruction handler =
  let handler_interpreter = handler interpreter in
  let result = 0 in
  let store = Instruction.store instruction in
  let store_interpreter = interpret_store handler_interpreter store result in
  interpret_branch store_interpreter instruction result

All three helpers take a function – handler – which they invoke with the current interpreter. (This is of course the interpreter state after the operands have been determined.) The first helper expects the handler to return both a result and a new interpreter; the handler for instructions that produce a value just returns the value, and the handler for instructions that produce an effect returns no value. That we might use the logic already in interpret_branch, I just pass a zero to that thing. Most of the time the result will be ignored and the following instruction will become the new program counter, as we saw last time.

There is some duplicated code here that I could move into a helper method, but meh, it’s a few lines. I’m not worried about it.

Our handler functions are now trivial. Here, let me implement five of them.

let handle_add a b interpreter =
  a + b

let handle_sub a b interpreter =
  a - b

let handle_mul a b interpreter =
  a * b

let handle_div a b interpreter =
  let a = signed_word a in
  let b = signed_word b in
  a / b

let handle_mod a b interpreter =
  let a = signed_word a in
  let b = signed_word b in
  a mod b

A few points to note here.

First, none of these need the interpreter. Most of the instructions that produce a value are not “pure” like these, but rather depend on interpreter or story state.

Second, the specification notes that these do “signed” 16 bit integer arithmetic. The arguments have just been read from constants or variables, so they are unsigned 16 bit integers. The result will be written to a variable as an unsigned 16 bit integer. The question then is: under what circumstances is the stored┬áresult wrong if we do the arithmetic in unsigned arithmetic? Addition, subtraction and multiplication all give the same results whether they are signed or unsigned, so we just do those normally and let the store truncate them back to 16 bits. Division and remainder operators need to operate on signed quantities because they are sensitive to magnitudes in a way that addition is not.

We seem to have the right set of parts now, but you might be wondering how all these parts fit together. interpret_value_instruction takes a handler, that handler is a function that takes an interpreter, not two integers and an interpreter. But remember in OCaml we have the power of partial evaluation! In fact I am going to use partial evaluation a whole bunch of times right here:

let step_instruction interpreter =
  let instruction = Instruction.decode interpreter.story interpreter.program_counter in
  let operands = Instruction.operands instruction in
  let (arguments, interpreter) = operands_to_arguments interpreter operands in
(*let interpret_instruction = interpret_instruction interpreter instruction in*)
  let value = interpret_value_instruction interpreter instruction in
(*let effect = interpret_effect_instruction interpreter instruction in*)
  let opcode = Instruction.opcode instruction in
  match (opcode, arguments) with
  | (OP2_20, [a; b]) -> value (handle_add a b)
  | (OP2_21, [a; b]) -> value (handle_sub a b)
  | (OP2_22, [a; b]) -> value (handle_mul a b)
  | (OP2_23, [a; b]) -> value (handle_div a b)
  | (OP2_24, [a; b]) -> value (handle_mod a b)
  | (OP1_139, [result]) -> handle_ret result interpreter 
  | (VAR_224, routine :: args) -> handle_call routine args interpreter instruction
  | _ -> failwith (Printf.sprintf "TODO: %s " (Instruction.display instruction interpreter.story))

I’ve commented out the helper functions that we’re not using yet.

“value” is a partially-evaluated interpret_value_instruction. I could have also made it a nested function that closed over interpreter and instruction but I decided to do it this way instead, for no particular reason. Either works. The result is a function that takes a handler.

Each of the handlers passed to value is then itself a partially-evaluated function. Calling handle_add a b returns a function which takes an interpreter. The addition is not actually executed until interpret_value_instruction invokes it with the interpreter.

Our interpreter can now handle seven instructions. Let’s make a little endless loop and run the thing until it crashes!

let rec interpreter_loop interpreter =
  Printf.printf "%s" (Interpreter.display_current_instruction interpreter);
  flush stdout;
  interpreter_loop (Interpreter.step_instruction interpreter)

let () = 
  let story = Story.load "minizork.z3" in
  interpreter_loop (Interpreter.make story)

And when we run it:

37d9: call 3b36 3e88 ffff ->sp
3b3d: call 3b4a local0 ->local2
3b55: add g16 b4 ->local2
3b59: add g16 g35 ->local3
3b5d: je local3 local2  ?~3b77
Exception: Failure "TODO: 3b5d: je local3 local2  ?~3b77 \n ".

Next time on FAIC: I guess we know what instruction we’re adding next.

Advertisements

5 thoughts on “Slide room

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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