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

One 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 )

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