Article 1BQ2N Slide room

Slide room

by
ericlippert
from Fabulous adventures in coding on (#1BQ2N)

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 resultlet 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 resultlet 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 + blet handle_sub a b interpreter = a - blet handle_mul a b interpreter = a * blet handle_div a b interpreter = let a = signed_word a in let b = signed_word b in a / blet 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 ->sp3b3d: call 3b4a local0 ->local23b55: add g16 b4 ->local23b59: add g16 g35 ->local33b5d: je local3 local2 ?~3b77Exception: Failure "TODO: 3b5d: je local3 local2 ?~3b77 \n ".

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


4270 b.gif?host=ericlippert.com&blog=67759120
External Content
Source RSS or Atom Feed
Feed Location http://ericlippert.com/feed
Feed Title Fabulous adventures in coding
Feed Link https://ericlippert.com/
Reply 0 comments