Sunday, September 27, 2009

Limitations of the Z-machine standard

"It is wrong in all cases to believe on insufficient evidence; and where it is presumption to doubt and to investigate, there it is worse than presumption to believe." - The Ethics of Belief, William Kingdon Clifford

  When writing an interpreter, despite the very useful Z-machine standard, there are small areas of behavior which are undefined. There are also a very small number of errors in the standard itself. I have to say that overall the 1.0 version standard is very thorough, although I believe the 1.1 standard was not as well conceived in a number of areas. I won't go into the 1.1 standard just yet. Today I am talking about a design decision regarding instruction decoding.

  In my last post I described how to decode an instruction and execute it. I deliberately left out one part of the instruction format mentioned in the standard because I don't deal with it at that point, but rather during the execution itself. There are three special types of instructions: branch, store, and text. Branch instructions are followed by one or two bytes which contain information as to whether the branch occurs on true or false and an offset address. Store instructions are followed by a byte containing a variable number in which to store the result of the operation. Text instructions are followed by a string of text to print.

  I do not read these extra pieces of the instruction and store them during decoding although many, but not all, interpreters do. Rather I delay the reading of this information until the operation concludes. For example: We read a new instruction from the PC and the byte is 0x14 (20 decimal) which is the 'add' opcode. It is a 2-op instruction with two small constant operands. The next two bytes contain these constants. This is a store instruction therefore it is followed by a byte which contains the variable number to put the result in. We do not read this during decoding, instead we wait until the end of the operation itself. Here is the add operation (which uses signed addition):
protected override void Op20()
  var num1 = (short)this.Operands[0];
  var num2 = (short)this.Operands[1];
  this.Store((ushort)(num1 + num2));

and the store method:
protected void Store(ushort value)
  byte variable = this.Memory.ReadByte(this.CallStack.ProgramCounter++);
  this.WriteVariable(variable, value);

  Why is this important? Can't we just read the storage byte ahead of time during decoding and cache it somewhere? After all it is part of the instruction and the standard doesn't say how the instruction should be read. Well, yes, but there really are no compelling reasons to do so, yet there are some not to:

  First, caching the result causes complications for the save/restore opcodes. Versions 1-3 of the Z-machine used branch opcodes for save and restore (later versions use store instead). If we read ahead, then when we encounter a save opcode, the PC that is saved will point just past the branching information. When a restore is performed, execution picks up at this point, but cannot know what to do as the save format includes memory and the stack, but no information about the current operation, thus the branch information is lost. Because the branch information can be one or two bytes, backward parsing from the current location is ugly. To fix it, we need to save the PC from the location before we read the branch or store information in order to be able to continue after the restore. When we read these values at the end of the operation, we don't need to do these PC gymnastics and everything 'just works'.

  Second and more interestingly, if only from a theoretical point of view, is if the instruction is a 'call' instruction which starts a routine and stores the return value, then reading ahead presupposes the routine will not change the value of the storage byte during execution. We can imagine this routine sits in dynamic memory where it can rewrite itself while running. Read ahead caching of the storage location would break this code! Through testing I found that Infocom's own interpreters do not read the storage location until after a routine returns. Thus the original implementations of the Z-machine have always had this capability and a modern interpreter which does not is unnecessarily limiting possible behavior of the Z-machine. I avoid creating limitations wherever possible.


  1. A call instruction in dynamic memory whose storage byte is overwritten by the called routine is an interesting curiosity, but I wouldn't expect it to work in all interpreters. It would be rather hard to implement in a JIT interpreter, for instance: ZLR has little choice but to read the entire instruction at once. It would be good to put together a test case and see which interpreters actually support it.

  2. I do have a test file which I ran on several interpreters. It worked on mine, Infocom's DOS interpreter and Frotz, but failed on Zoom, Nitfol, and Filfre. I can't remember others I may have tested as it was several years ago, but I have the file still.

  3. I dug up my test file. If I get some time I'll run it through some more interpreters.

    I imagine ZLR could handle this as a special case when routines lie in dynamic memory. The question would be "Is it worth it?" Routines in dynamic memory are a rarity and this particular case vanishingly rare (probably nonextant outside my test file). Since ZLR's stated goals are to run a subset of Z-machine files which already excludes the bulk of Infocom's catalog, I would not think it worthwhile to implement this. However, for my project whose aim is to run all possible Z-machine software, it definitely is.

    There are a few other Z-machine oddities like this that aren't covered by the standard. They'll come up later.

  4. ZLR does have some special case code to support routines in dynamic memory (the IL code isn't cached, as it is for routines in static memory). In fact, I'm about to release an extension that creates routines in dynamic memory, so it is a scenario that interests me. But I don't think it'd be worth implementing special instruction parsing logic for this case, when the behavior it would allow is not part of the standard and has never been used, even by Infocom.

    (Aside: I'm thinking about expanding the scope of ZLR, at least to include V3-V4 support, since I'm now using it as the debugger engine in my Inform/ZIL IDE.)

  5. Taradino C. -

    I think it's great you are thinking of adding V3-V4 support.

    I agree with you about it probably not being worth implementing in ZLR's case. I do find it fascinating that Infocom's interpreters supported this, even if accidentally, so I'd probably support it in mine even if it weren't already the simplest solution in my case.