Windy cave

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

> wait

Time passes…
A gust of wind blows out your candles!

> go down


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

Last time we saw how to find the default values for locals in a routine activation. Now let’s actually create the local variable store.

The operations we need to perform on a local store (so far) are (1) initialize all the locals to their default values, (2) read a local, and (3) write a local. Of course the first and third operations return a new local store; a local store is immutable, like all the data structures in this purely functional interpreter will be.

The store maps integer local numbers – from 1 to 15 – onto unsigned word values. Our old friend the integer map seems like a good candidate.

For reasons which will become clear later, we also need to keep track of two numbers. First, how many locals are there? And second, a routine call causes the arguments of the call to be copied to the locals of the newly-activated routine; we will later need to know how many arguments were provided vs how many locals there were.

type t =
{
  locals : int IntMap.t;
  count : int;
  arguments_supplied : int;
}

I like to have an empty object for cases where it makes sense.

let empty =
  { locals = IntMap.empty; count = 0; arguments_supplied = 0 }

Reading is straightforward. When writing we ensure that we have an unsigned value. (In an earlier version of my interpreter I was accidentally writing negative numbers as local values and things got very messed up!)

let read_local local_store (Local local) =
  IntMap.find local local_store.locals

let write_local local_store (Local local) value =
  let value = unsigned_word value in
  let locals = IntMap.add local value local_store.locals in
  { local_store with locals }

Here’s where we deal with creating a new local store given a routine.

let add local_store (Local n) default_value =
  let locals = IntMap.add n default_value local_store.locals in
  let count = max local_store.count n in
  { local_store with locals; count }

let create_default_locals story routine_address =
  let count = Routine.locals_count story routine_address in
  let rec aux acc i =
    if i > count then
      acc
    else
      let default_value = Routine.local_default_value story routine_address i in
      let new_store = add acc (Local i) default_value in
      aux new_store (i + 1) in
aux empty 1

And finally I like to have a helper method for displaying my work:

let display local_store =
  let to_string local value =
    Printf.sprintf "local%01x=%04x " (local - 1) value in
  let folder local value acc =
    acc ^ (to_string local value) in
  let locals = local_store.locals in
  IntMap.fold folder locals ""

Note the use of IntMap.fold, which is the logical equivalent of List.fold_left.

Now we can pick a routine address and create a local store with the default values:

let () = 
  let story = Story.load "minizork.z3" in
  let locals = Local_store.create_default_locals story (Routine 0x3b36) in
  let text = Local_store.display locals in
  Printf.printf "%s\n" text

which outputs

local0=0000 local1=0000 local2=0000

All right, maybe not very interesting there, and now we see why in version 5 they simply initialized every local to zero. The majority of the time that’s how it goes.

We said that interpreter state is a stack of frames, each frame consists of a local store and an evaluation stack. We’ve got the store. Next time on FAIC: we’ll implement the evaluation stack. It’ll be pretty straightforward.

Advertisements

1 thought on “Windy cave

  1. I’m really enjoying this blog series. I’ve been following along to try and learn some Haskell, but have picked up a bit more on the way. I hope that you are able to find some time to pick up again where you have currently left off.

    Anyway, this is probably not a big deal for others, but I got stuck for a bit based on this sentence:
    “Note the use of IntMap.fold, which is the logical equivalent of List.fold_left.”

    I think this should be:
    “Note the use of IntMap.fold, which is the logical equivalent of List.fold_right”

    The type signature for fold is (http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.Make.html):
    val fold : (key -> ‘a -> ‘b -> ‘b) -> ‘a t -> ‘b -> ‘b

    The type signature for fold_left is (http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html):
    val fold_left : (‘a -> ‘b -> ‘a) -> ‘a -> ‘b list -> ‘a

    But compare that to fold_right (http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html):
    fold_right : (‘a -> ‘b -> ‘b) -> ‘a list -> ‘b -> ‘b

    FWIW, I ended up using (in Haskell’s Data.IntMap.Lazy):
    foldrWithKey :: (Key -> a -> b -> b) -> b -> IntMap a -> b

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 )

Google photo

You are commenting using your Google 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