White Cliffs Beach

…in the magic boat

You are on a narrow strip of beach between the White Cliffs and the Frigid River. A tiny passage leads west into the cliff.

> get out of the boat

You are on your own feet again.

> open the buoy

Opening the buoy reveals a large emerald.

> take the emerald and drop the buoy


> go west

Round room

> go southeast

Dome room

> go southeast

There is a brass bell here.

> take the bell


> go south

On the two ends of the altar are burning candles.
On the altar is a large black book, open to page 569.

> take the candles and the book

pair of candles: Taken.
black book: Taken.

> go down

Let’s review. So far we’ve got the ability to read and write any byte in story state, decode any string, look up any item in the dictionary, determine the topology of the entire object tree, and disassemble any instruction. We are in good shape here, but still some way from being able to run code.

We’ve concentrated almost entirely on story state thus far. What will we need for an interpreter?

When a routine is called we need to keep track of the evaluation stack and local variables, as well as information about how to get back to the calling code when the current routine returns. My preferred term for such a thing would be an “activation record”, as it is a record of all the stuff you need when a routine is “activated” by calling it. But since traditionally all this information has been stored by pushing it onto a single stack, it is often called a “stack frame”. So that’s what I’ll call it.

There is no reason for me to model the interpreter as having a single stack of bytes that stores all of the activation information, as we typically do on, say, the x86 processor. I’m going to have my interpreter maintain a stack of frames, and then each frame itself keeps track of an evaluation stack and a collection of locals.

The collection of locals seems nicely straightforward: a bunch of 16 bit unsigned integers, indexed by numbers from 1 to 15. But there are some subtleties here; we need to first understand how routines are encoded. You might have noticed last time, for instance, that the routine address in the call instruction was not the address of the first instruction in the routine.

A routine begins with a one-byte header that says how many locals it has. On versions 1 through 4, that many words then follows, giving the initial values for all those locals. In version 5 and above, locals are initialized to zero, and the words are not there. After that comes the first instruction.

We can code that up easily enough, in routine.ml. Code for this episode is in https://github.com/ericlippert/flathead/tree/blog12.

I want functions that give me the number of locals in a routine, the default value of a given local, and the address of the first instruction in the routine:

let locals_count story (Routine routine_address) =
  Story.read_byte story (Byte_address routine_address)

let first_instruction story (Routine routine_address) =
  if Story.v4_or_lower (Story.version story) then
    let count = locals_count story (Routine routine_address) in
    Instruction (routine_address + 1 + count * word_size)
    Instruction (routine_address + 1)

let local_default_value story (Routine routine_address) n =
  if Story.v4_or_lower (Story.version story) then
    let addr = Word_address(routine_address + 1) in
    Story.read_word story (inc_word_addr_by addr (n - 1))

Next time on FAIC: we’ll make a local variable store that knows how to initialize itself to its default values.


5 thoughts on “White Cliffs Beach

  1. Just wanted to say that this is the most awesome series ever. I’m following along in a CSharpy way. Keep it up!

  2. Inspired by this series, I recently wrote a simple parser for a very tiny “DSL”, which I approached in a functional way. C# has gained quite a few functional features, but the lack of robust tuple support was painfully evident Still, the result is pleasantly immutable, since all of the “variables” are assigned values but never modified.

    • It is bizarre to me that tuples have taken so long to get into not just C# but so many languages. We could even get by without tuples of arbitrary size; even just having *pairs* as a first-class language element would go a long way. This is not a conceptually difficult thing to do, and once you have pairs, you have a huge amount of power. You can think of Lisp as being just a nice syntax on top of cons cells, which are pairs, and Lisp is pretty powerful.

      • Totally agree. In my recent example there was not a single place where anything other than a first class pair was needed. Arbitrary tuples are icing, but pairs are invaluable!

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