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?

 else 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; local_store; resume_at; store }

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 acc else 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:

LocalsStackResume at:000037d9: 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=0000StackResume at:37e2LocalsStackResume at:00003b3d: 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=0000StackResume at:3b43Locals local0=3e88 local1=ffff local2=0000StackResume at:37e2LocalsStackResume at:00003b55: 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.