Dynamic Objects update

I've submitted version 6 of Dynamic Objects, which adds compatibility with Inform 7 build 6G60. There were two compatibility issues, both involving the way Dynamic Objects uses undocumented I7 properties to add cloned objects to the per-kind linked lists.

First, the "IK_0" property was renamed to "KD_Count". This property contains the numeric index of each object's kind. For example, an object whose immediate kind is "person" will have a KD_Count of 8, since "person" is K8_person in I6.

Second, the logic for matching a kind name to the link property had to be changed to account for new properties. This deserves more explanation.

All things in an I7 game are connected via one or more linked lists, which helps to optimize kind-based loops. When we write "repeat with X running through people", the game doesn't have to loop through every object, checking each one to see if it's a person. Instead, it starts at the first person, which is referenced in the IK8_First constant, and proceeds to each subsequent person by following the IK8_Link properties.

Whenever we clone an object, Dynamic Objects has to add the new object to each of the appropriate linked lists. A cloned man has to be added to the list of men, the list of people, and the list of things.

The easy way to add something to a linked list is to add it at the beginning: change the head to point to the new item, then change the new item's "next" field to point to the old head. But we can't do that, because the head is stored in a compile-time constant like IK8_First. So we add it at the end, by starting from the old object (which we know is already in the list) and following the link property until we reach the end.

But finding out which link property to use is tricky in itself. The I7 compiler has an easy enough time knowing that it should write "IK8_Link" for loops involving "K8_person" -- even Ayn Rand knew that 8 IS 8 -- but the *values* of IK8_Link (a property number) and K8_person (an object address) are unrelated. They're similarly named, but those names are only for compile time, right?

As it turns out, no! Even in release builds, the I6 names of objects and properties are still available at runtime via the "print (object) x" and "print (property) x" syntaxes. So Dynamic Objects loops over every property, printing each one's name to a buffer and looking for the one whose name contains the same number as the name of the kind object. It's ugly but it works.

That's where the compatibility issue came in. Since the names don't match exactly ("K8_person" vs. "IK8_Link"), Dynamic Objects was only comparing the part between the K and the underscore. But 6G60 added new properties with names like "IK8_Count", which threw off that comparison. The extension now checks the character after the underscore to make sure it's an L.

Incidentally, if you use Dynamic Objects, please vote for this suggestion. A more stable way for the extension to get at this information would keep it from breaking with each new build, and adding more information for the extension to use at runtime would make it work more smoothly with indexed text properties.

Branch optimization in ZAPF

I recently moved some unfinished changes from ZAPF's trunk into a development branch. Some have asked what these changes are all about, anyway, so here's an explanation.

The Z-machine's branch instructions, of which there are many, can take an offset in either "long" or "short" form. Long form takes two bytes and can hold any signed 14 bit offset, whereas short form takes one byte but can only hold an unsigned 6 bit offset. In order to save space, we always want to use the short form wherever possible: that is, whenever an instruction branches forward by up to 61 bytes. (Not 63: these offsets are biased by +2.)

But branching forward means we encounter the branch instruction before its target label, so how do we know how far it's branching? It's not easy, especially if there are other branch instructions in between this one and its target -- we can't know the true distance until we know what form those will be assembled in.

ZAPF's current approach is to make repeated passes over each function until all the label positions are discovered. When it sees a branch instruction targeting a label that hasn't been defined yet, it remembers the name of that label, then assembles the branch in long mode. Once the label's definition is encountered, ZAPF remembers its location and rewinds to the beginning of the function.

The next time it encounters the branch instruction, it can make a better judgment of the distance, which may allow it to use short mode. The next time it encounters the label definition, it compares the new location to the old location; if it has changed, it remembers the new position and rewinds again. It only reaches the end of the function once every label's final location has been discovered and every branch has been assembled correctly.

Unfortunately, this approach doesn't always work. Some inputs cause ZAPF to get stuck in a function and never reach the end. I haven't investigated too thoroughly because the algorithm is hard to reason about, inefficient, and silly enough that I decided to just rewrite it.

I found an interesting replacement algorithm in a 1978 paper by Thomas G. Szymanski called "Assembling Code for Machines with Span-Dependent Instructions". The paper proves that minimizing program length is NP-complete in the general case, when branch targets are allowed to be specified as arbitrary expressions of constants and labels, but presents an efficient algorithm for a restricted subset of expressions -- which works just fine for ZAPF.

The algorithm works by assuming in a first pass that all instructions can be assembled in short form, and remembering the location of every label and every branch instruction, then studying them after that pass to trace the dependencies between branch instructions, and forcing into long mode only the instructions that need it. The label locations are adjusted -- advanced forward by one byte for every preceding branch that was changed from short to long -- and the set of adjusted locations is used in a second pass to assemble each branch in the correct mode.

There's one more complication, though: the Z-machine's packed address system. Every routine must begin at an address divisible by 2, 4, or 8 (depending on the Z-code version), so there are usually a few padding bytes between routines. The algorithm works on all labels in the game at once, but because of the padding issue, forcing a branch into long mode doesn't actually push every following label ahead by one byte: for labels in subsequent routines, it's either zero bytes (when the extra byte can be absorbed by the next padding section) or 2/4/8 bytes (when it can't). And that's the part that isn't finished yet.

Hello World

I'm vaporware, and this is my IF blog.

Who am I, anyway? You may have encountered some of my IF-related projects:

• FyreVM - The modified Glulx interpreter that runs Textfyre's games.
  
• Guncho - An online multiplayer IF system based on Inform 7.
  
• Snack - A language similar to TADS 2 that compiles to Glulx.
  
• Yomin - An integrated development environment (IDE) for Inform 6 and ZIL.
• ZAPF - A Z-machine assembler and disassembler.
  
• ZILF - A compiler for Infocom's ZIL language.
  
• ZLR - A Z-machine interpreter.

I've also contributed template code to Inform 7 and currently run the bug tracker site. I've written several extensions, and I was the technical editor on Aaron Reed's Creating Interactive Fiction with Inform 7.

Why this blog? Well, occasionally I come up with something cool that I want to talk about in greater detail than one or two lines on ifMUD. Don't expect a lot of comp reviews or storytelling tips: I intend to focus on more technical topics, from the status of the projects above to Inform tricks to VM implementation details.