Drafty cave

This is a tiny cave with entrances west and north, and a dark, forbidding staircase leading down.

> go north

If you think the drafty cave is deliberately designed to be easily confused with the windy cave, you’re probably right!

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

We are at long last in a position to execute code! We just need a little bit more gear.

We need to be able to add — and when we get to returns, remove — frames from the interpreter’s frame set:

let add_frame interpreter frame =
  { interpreter with frames = Frameset.add_frame interpreter.frames frame }

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

Easy. And we never made a helper to set the value of the program counter – that is, the address of the next instruction to execute:

let set_program_counter interpreter program_counter =
  { interpreter with program_counter }

Suppose we have a call. Let’s suppose that we have already decoded the instruction, obtained the routine operand and obtained the routine’s arguments. All the stack pops necessary have already been done. (We’ll show that code in a moment.)

Recall that there are two cases. First, if the routine address is zero then all we do is store zero in the store of the call instruction, and move on to the following instruction.

let handle_call routine_address arguments interpreter instruction =
  if routine_address = 0 then
    let result = 0 in
    let store = Instruction.store instruction in
    let store_interpreter = interpret_store interpreter store result in
    let addr = Instruction.following instruction in
    set_program_counter store_interpreter addr

Second, if the routine address is not zero then we must first decode the packed address into a real routine address. Then to make the new frame we need to know (1) where should it resume when the routine returns? (2) where should the result be stored?

    let routine_address = Packed_routine routine_address in
    let routine_address = Story.decode_routine_packed_address interpreter.story routine_address in
    let resume_at = Instruction.following instruction in
    let store = Instruction.store instruction in

We make a new frame and copy the arguments over into the locals. We obtain the first instruction of the new routine, and finally create an intepreter that has the new frame and the new instruction address:

    let frame = Frame.make interpreter.story arguments routine_address resume_at store in
    let pc = Routine.first_instruction interpreter.story routine_address in
    set_program_counter (add_frame interpreter frame) pc

And we’re done; that’s all there is to a call. Oh, except I never showed how the arguments get copied onto locals. We’ll add a frame factory that does the right thing: first create default-valued locals, then copy the arguments over those locals:

let make story arguments routine_address resume_at store =
  let default_store = Local_store.create_default_locals story routine_address in
  let local_store = Local_store.write_arguments default_store arguments in
    stack = Evaluation_stack.empty;

It is legal for there to be more, as many, or fewer arguments as locals, so we cannot simply copy the arguments over willy-nilly. We need to stop if there are not enough locals to hold them:

let write_arguments local_store arguments =
  let rec aux acc args i =
    match args with
    | [] -> acc
    | arg :: tail ->
      if i > acc.count then
        let new_store = write_local acc (Local i) arg in
        aux new_store tail (i + 1) in
  aux local_store arguments 1

Great. So… how do we actually execute the code? Here, I’ll make a method on the interpreter that means “give me back the new interpreter that is the result of executing the current instruction”.

What do we need to do for every instruction? Decode the instruction, turn the operands into arguments, and dispatch to a helper that implements the semantics of the instruction:

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 opcode = Instruction.opcode instruction in
  match (opcode, arguments) with
  | (VAR_224, routine :: args) -> handle_call routine args interpreter instruction
  | _ -> failwith (Printf.sprintf "TODO: %s " (Instruction.display instruction interpreter.story))

Let’s run it!

let () = 
  let story = Story.load "minizork.z3" in
  let interpreter1 = Interpreter.make story in
  let interpreter2 = Interpreter.step_instruction interpreter1 in
  let interpreter3 = Interpreter.step_instruction interpreter2 in
  let text1 = Interpreter.display interpreter1 in
  let text2 = Interpreter.display interpreter2 in
  let text3 = Interpreter.display interpreter3 in
  Printf.printf "%s\n%s\n%s\n" text1 text2 text3

Before the first instruction is executed, interpreter1 looks like this:

Resume at:0000

37d9: call 3b36 3e88 ffff ->sp

OK, no locals, no stack usage, no return address because we are in the main routine. What are we going to do? Call the routine at 0x3b36, and pass it two arguments: the values 0x3e88 and 0xffff. So we should expect in the stepped interpreter2 to see a new frame with those values copied to the locals:

Locals local0=3e88 local1=ffff local2=0000
Resume at:37e2
Resume at:0000

3b3d: call 3b4a local0 ->local2

Yes! This routine has three locals, and two of them have taken on the values of the arguments. We have two stack frames in the frame set, and the return address of the top frame is the instruction after the call.

The current instruction is, thank goodness, a call, so we can step again. This time we expect that the argument passed will be the value of local0, which is 0x3e88. And sure enough:

Locals local0=3e88 local1=0000 local2=0000 local3=0000 local4=0000
Resume at:3b43
Locals local0=3e88 local1=ffff local2=0000
Resume at:37e2
Resume at:0000

3b55: add g16 b4 ->local2

This routine has five locals, and sure enough, the first has taken on the value of the argument, which was local0 of the previous frame. We have three routines activated, so three frames in the frame set, and our next instruction is an add. Which unfortunately we do not yet know how to interpret.

Next time on FAIC: add is a lot easier to implement than call, believe me. But we’ll actually implement ret first, while we’re thinking about the semantics of call.

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 )

Connecting to %s