Altar

Standing by the temple's altar, you can see a small hole in the floor which leads into darkness. The rest of the temple is north of here.
On the two ends of the altar are burning candles.
On the altar is a large black book, open to page 569.

> go down

You haven't a prayer of getting the coffin down there.

> pray

This is getting exciting. Last time we managed to spit out the object tree, but in a manner that was quite difficult to read. Let's fix that.

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

And oh my goodness, we have been programming in a purely functional style in OCaml for weeks now and have yet to see so much as a single list! Lists are traditionally the data structure you use for nigh everything in functional languages, starting from Lisp on down. Let's look at how lists are represented in OCaml first, and then we'll reorganize that tree structure.

Lists are recursively defined, as you might imagine. The empty list is a list, and is notated []. There are two ways to notate non-empty lists. You can either notate a list as "here's the head, an element, and here's the tail, a list":

1 :: []

That would be the list with one element at the head, and an empty tail. Since that is a list, it can be the tail of another list:

3 :: 1 :: []

That list has two elements. 3 is at the head, and 1 :: [] is the tail.

Since this syntax is somewhat bulky for large lists there is a sugar:

[ 3; 1 ]

is another syntax for the same list.

Lists work extremely well with pattern matching because both of these syntaxes may be used as a pattern. We'll see plenty of examples of that in later episodes. For now we'll stick with just plain list construction.

The first thing I'm going to need is a list of every "root" object - that is, all the objects where the parent is the invalid object.

let roots story = let rec aux obj acc = let current = Object obj in if current = invalid_object then acc else if (parent story current) = invalid_object then aux (obj - 1) (current :: acc) else aux (obj - 1) acc in aux (count story) []

All right, once again we are using this auxilliary function as a looper, but this time instead of passing in an empty string as the accumulator, we pass in an empty list to start with. Objects are numbered from 1 to count, so we start with count and loop until we get down to zero. Every time through the loop we ask "is the current object parentless?" If it is then we recurse, having prepended the root object to our accumulation. If not, then we recurse without prepending.

Though this time we are doing two recursions, we are still tail recursive here because for both, the recursion is the last thing the function does. And for that matter we could easily have rewritten it to use one recursion:

 else let new_acc = if (parent story current) = invalid_object then current :: acc else acc in aux (obj - 1) new_acc in

Whatever; doesn't matter to me. Point is that we recursively construct a list containing all the root objects.

Now suppose we have a root object, any root object. How are we going to print that as a tree?

 let rec aux acc indent obj = if obj = invalid_object then acc else let name = name story obj in let child = child story obj in let sibling = sibling story obj in let object_text = Printf.sprintf "%s%s\n" indent name in let with_object = acc ^ object_text in let new_indent = " " ^ indent in let with_children = aux with_object new_indent child in aux with_children indent sibling in let to_string obj = aux "" "" obj in

What's our strategy here? We solve the problem recursively. Every recursive solution has the same form: if you can solve the problem without recursion do so, otherwise reduce it to one or more smaller problems, solve each recursively, and then combine the solutions. This is no different.

The base case is: if we are trying to print out an invalid object then just produce the accumulated state.

If not, then we have two smaller problems to solve. First, accumulate the printed tree for all my children, indented more. Next, accumulate the printed tree for all my siblings, indented the same as me.

So we can produce such a string for any object, but we want to produce such a string for all the roots. How can we do that? This seems very similar to the problem I've already solved: doing so for a sequence of integers that map to strings. Now I want to do it for a list of objects that map to strings.

The standard library for lists has a powerful function called fold_left that will seem very familiar if you've been paying attention to how my string accumulator works. A fold operation takes a list, an accumulation value, and a function that maps an element of the list and an accumulation onto a new accumulation. It then applies that function in turn to every element of the list. For example:

let accumulate_strings to_string items = let folder text item = text ^ (to_string item) in List.fold_left folder "" items

Here I have another little helper method. As with my looping string accumulator, it takes a to_string function, but this function does not (necessarily) take an integer. Rather, it takes an element of the list of items I've given, and produces some value.

We then define another little nested helper function that takes text - the accumulated state - and an item from the list. It produces a new accumulated state by turning that item into a string, and concatenating the result onto the accumulation.

That little function is then passed to fold_left, which starts with an empty string and calls the folder on every item in the list. So what happens is, the folder calls to_string on every element of the list, and concatenates up all the strings as it goes.

Putting it all together, we have

let display_object_tree story = let rec aux acc indent obj = if obj = invalid_object then acc else let name = name story obj in let child = child story obj in let sibling = sibling story obj in let object_text = Printf.sprintf "%s%s\n" indent name in let with_object = acc ^ object_text in let new_indent = " " ^ indent in let with_children = aux with_object new_indent child in aux with_children indent sibling in let to_string obj = aux "" "" obj in accumulate_strings to_string (roots story)

Isn't that lovely? And now we can call it:

let tree = Object.display_object_tree story in Printf.printf "%s\n" tree

and see the entire object tree laid out for us:

... Altar altar pair of candles black book Egyptian Room gold coffin sceptre Temple prayer brass bell pedestal torch Dome Room wooden railing...

Holy goodness, there is a sceptre in the coffin! That might come in handy.

Next time on FAIC: We've decoded the dictionary and the object table, which are the primary data structures of the story file. (I am not counting the parsing tables because those are entirely the business of the game developer; I probably will not decode the parsing tables in this series, but we'll see.) Let's get on to the real heart of the matter and start looking at code.