In this post, we’re going to start down the path of implementing the basics of a Z-Machine. Crucial to this start, however, is making sure it’s understood how the Z-Machine actually works in terms of taking in zcode to execute and what, exactly, is executing. Spoiler alert: it’s 0’s and 1’s all the way down.
The above image shows an example of a story file (zcode) being executed by a Z-Machine interpreter. This is exactly what Grue aims to do. To explain how Grue will operate, it’s necessary to dig into the Z-Machine architecture a bit and how zcode programs run on that architecture.
What is Grue Going to Be?
Let’s start with this statement: Grue is a Python-based implementation of a ZIP that allows for emulating the Z-Machine.
What does that mean? Well, let’s break it down a bit.
The goal of Grue is to be an emulator, as was talked about in the previous post. The goal behind any emulator is to be able to execute the binary files from some specific machine directly.
Let’s consider another retro-gaming example. Atari 2600 cartridges contained binary files that were the instructions for how the game would play once the cartridge was plugged into a console. So you can build an Atari 2600 emulator that is able to take one of those binary files, usually called a ROM, and execute it as if it were running on an Atari 2600. The same applies to any machine, such as a Gameboy or a PlayStation or whatever else. The binary files that execute on these machines are always assembly level instructions.
So what does that mean for Grue?
- The machine to be emulated is the Z-Machine.
- The binary files to be executed are called story files that contain zcode.
Unlike the binary files for the Atari 2600, the story files in question never ran on an actual processor of a machine. Instead, they ran on a virtual machine and it was this virtual machine that ran on the actual processor. So, as an example, a (virtual) Z-Machine might be running on an (actual) Commodore 64 or an (actual) Apple II.
Here’s the Zork 1 zcode running on an actual Commodore 64:
And here’s the same zcode running on a Commodore Amiga:
And, just for good measure, the exact same zcode running on an Apple II:
What all of the above means is that the Z-Machine was never a physical computing device made of circuits; thus it was never physical hardware. The Z-Machine was instead a virtual computing device that had to be implemented in software. That is one part of what Grue needs to be. Grue needs to be able emulate a the Z-Machine.
Just as the binary files for the Atari 2600 were made up of assembly instructions for graphical games, the story files I’m referring to are made up of assembly instructions for text adventure games. These text adventure games, and the Z-Machine on which they ran, were created by Infocom back in the late 1970s and through most of the 1980s.
In the case of the Atari 2600, the binary files were written directly in 6502 assembly language. In the case of the story files, the assembly instructions are actually a compiled form of z-language, which was more often known as ZIL (Zork Implementation Language). This compiled assembly code is referred to as z-machine code or just zcode.
In fact, this is actually a form of code known as bytecode, which is code that makes up an instruction set that has been designed to be run on a particular interpreter. This is identical to the concept of Java bytecode which is the instruction set for code that can run on a Java Virtual Machine (JVM) via a JRE (Java Runtime Engine). The language used to create the bytecode doesn’t necessarily matter. For example, you can compile Java programs, or Groovy programs, or Clojure programs and they all create bytecode that run on the JVM. Similar to Microsoft’s .NET implementation of the CLR (Common Language Runtime) that can execute compiled C#, F# and VB.NET.
The same applies in this context. Someone can compile a story file using a tool like ZILF, Dialog, or Inform and as long as those tools produce the appropriate bytecode, that bytecode will run on the Z-Machine.
Thus a “Z-Language Interpreter” or a “ZIL Interpreter” is basically designed to execute the instruction set of the zcode which was, in turn, designed to be executed on a Z-Machine (virtual) processor. What language was used to create that zcode is largely irrelevant.
Thus Grue will be one of those interpreters; a type of ZIP. A ZIP (Z-Language Interpreter Program) was a program, or rather a series of programs, written by Infocom. Infocom referred to their own interpreters by the following designations:
- ZIP (versions 1 to 3)
- EZIP / LZIP (version 4) (“extended” or “expanded”)
- XZIP (version 5) (“experimental”)
- YZIP (version 6) (“successor to X”)
There was apparently a version called GZIP (Graphical ZIP) but was used for a one-off project from Infocom called Fooblitzky. That game was apparently intended to be a multiplayer strategy game.
From surviving notes from the company, it appears that Infocom did think about the possibility of an interpreter capable of running all versions. “One interpreter to rule them all,” so to speak. It’s unknown how far they took this idea but they certainly didn’t release such an interpreter.
The point here is that each ZIP was a program that emulated the hardware instruction set specified for the Z-Machine. Even though the Z-Machine was never actually hardware, the basics of how it operated was just like any processor that communicated with input and output devices and performed operations via instructions.
Here are a few starting points that are crucial to understand:
- The Z-Machine is a virtual computer.
- The machine language of the Z-Machine is called zcode.
- There are six Infocom versions of the Z-Machine.
- There are two Inform versions of the Z-Machine.
- The structure and operation of zcode can differ between the versions.
Here “Inform” refers to a development system that was created to allow for compiling text adventures down into a bytecode format that could be read by the Z-Machine. Many saw this tool as the successor to the Infocom compiler, which was known as ZILCH.
The Z-Machine was originally a closed proprietary technology. The implementation of this machine, although not its general existence, was guarded pretty closely by Infocom since this provided their competitive advantage over all other rivals at the time. It was essentially their “secret sauce.” It was in the early to mid 1990s, when it was clear that Infocom was dissolving and would be no more, that various people tried to reverse engineer what made the Infocom games work.
Regarding those versions, the specification says:
Eight Versions of the Z-machine exist, and the first byte of any “story file” (that is: any Z-machine program) gives the Version number it must be interpreted under.
You can think of these versions as emulations of the architecture. Consider how Apple released the Apple I (1976), Apple II (1977), Apple III (1980), and Apple Lisa (1983). Each of these was effectively an evolution of a processing architecture. The same applies to the Z-Machine versions even though that architecture was entirely virtual.
The Z-Machine specification says:
The design’s cardinal principle is that any game is 100% portable to different computers: that is, any legal program exactly determines its behaviour.
In this context, a legal program refers to a program that adheres to the Z-Machine specification. The specification defines how the Z-Machine should behave, including how it should interpret and execute the instructions provided by zcode programs.
By stating that any legal program exactly determines its behavior, the specification is emphasizing that the behavior of a zcode program running on the Z-Machine is entirely determined by the program itself, according to the rules defined in the Z-Machine specification. This means that a zcode program should behave the same way regardless of the computer or operating system it’s running on, as long as the Z-Machine implementation is correct and adheres to the specification.
Any such “legal program” is made up of bits and bytes and so we can turn to that next.
Bits and Bytes
Let’s start with a high-level statement of what the Z-Machine is. The Z-Machine is a 16-bit byte-oriented virtual machine using big endian addressing.
There’s already a few things to unpack there, such as bits, being byte-oriented, and the notion of endian-ness. It may all seem very academic but without having this knowledge, it’s hard to get started.
The specification says:
Like any computer, it stores its information (mostly) in an array of variables numbered from 0 up to some large number: this is called its memory.
In the context of the Z-Machine, we have primary kinds of value that are semantically meaningful. There’s the byte (8 bits) and the 2-byte word (16 bits). In the latter, the first byte is considered to be the most-significant byte.
You deal with bits and bytes a whole lot when building a Z-Machine, so let’s make sure we level set on this.
The Z-Machine specification says:
The bits in a byte are numbered 0 to 7, 0 being the least significant and the top bit, 7, the most.
Schematically, what that means is this:
top bottom 1 0 0 1 0 1 0 1
The least significant bit is the 1 at the far right and is called the “bottom bit.” The most significant bit is the 1 at the far left and is called the “top bit.” The concept of the most-significant byte in a two-byte word in the Z-Machine is related to the concept of endianness.
Bits are numbered from right-to-left and numbered from 0 to 7. Bit 0 is the rightmost and the smallest (least significant bit or LSB); bit 7 is leftmost and largest (most significant bit or MSB). Let’s break this down:
0 1 0 0 1 0 0 1 The LSB is the far right: 1 The MSB is the far left: 0 bit number: 7 6 5 4 3 2 1 0 0 1 0 0 1 0 0 1 bit value: 128 64 32 16 8 4 2 1
This shows bits 6, 3, and 0 set to 1. The value of this byte is thus 64 + 8 + 1 or 73. With a single byte like this, the concept of endian-ness doesn’t matter. If you have two bytes, you would have something like this:
And with that, endian-ness does matter. When you read multi-byte data, a program has to essentially ask: “where does the biggest byte appear?” It breaks down like this:
- On a “big endian machine”, the data is stored “big-end first.” That means that when looking at multiple bytes, the first byte (lowest address) is the biggest.
- On a “little endian machine”, the data is stored “little-end first.” That means that when looking at multiple bytes, the first byte (lowest address) is the smallest.
Thus endianness refers to the order in which bytes are stored in multi-byte data types, such as words or integers, in computer memory.
So when I said above that the Z-Machine uses “big endian addressing” what this is referring to is big endian byte order. What that means is that the most significant byte (the “big end”) of the data is placed at the byte with the lowest address. This is contrasted with little endian byte order, where the least significant byte (the “little end”) of the data is placed at the byte with the lowest address. Fun fact: apparently the big-endian/little-endian naming comes from Gulliver’s Travels in which the Lilliputians argue over whether to break eggs on the little-end or the big-end.
In the case of the Z-Machine, it follows a specific endianness convention, known as big-endian. In big-endian representation, the most-significant byte is stored at the lower memory address, and the least-significant byte is stored at the higher memory address. This means that when interpreting a two-byte word in the Z-Machine, the most significant byte comes first in memory.
A byte refers to a unit of information that consists of 8 bits. A byte can represent a range of values from 0 to 255. It is the smallest addressable unit of memory in the Z-Machine.
On the other hand, a 2-byte word in the Z-Machine comprises 16 bits, which allows for a larger range of values to be represented. The first byte in a 2-byte word is considered the most-significant byte. This means that it holds the higher-order bits, which contribute more to the overall value of the word. Conversely, the second byte, known as the least-significant byte, contains the lower-order bits, which contribute less to the value.
When interpreting a 2-byte word in the Z-Machine, it’s important to consider the most-significant byte first to determine the value it represents. This byte holds the more significant part of the word, and combining it with the least-significant byte forms the complete value of the word. This will come up in decoding the instruction set of the Z-Machine.
Here’s a painfully simple representation of this:
+-----------------------+------------------------+ | Most Significant Byte | Least Significant Byte | +-----------------------+------------------------+ | 01010101 | 11001100 | +-----------------------+------------------------+ | Byte 1 | Byte 2 | +-----------------------+------------------------+
There’s also the concept of a “bit-field” or “bit-field flags” that you’ll have to come to grips with. Bit-field flags are stored in one or more bytes, with the bit number 0 starting at the least-significant bit of the least-significant byte, and bit number 8N-1 at the most-significant bit of the most significant byte. Let’s unpack what that actually means.
In the Z-Machine, bit-field flags are used to represent a collection of individual Boolean flags or indicators. These flags are stored in one or more bytes of memory. Each bit within the byte(s) represents a specific flag, and its value indicates the state of that flag (0 or 1). It’s an extremely compact way to represent a series of data conditions.
The bit numbering within the bit-field starts at 0, which corresponds to the least-significant bit of the least-significant byte. The least-significant bit holds the lowest-order or rightmost position within a byte. As we move towards higher bit numbers, we progress towards the most-significant bit of the most significant byte. Consider a scenario where we have a bit-field spanning two bytes:
+-------------------------------------+-------------------------------+ | Most Significant Byte | Least Significant Byte | +-------------------------------------+-------------------------------+ | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | +-------------------------------------+-------------------------------+ | Byte 1 | Byte 2 | +-------------------------------------+-------------------------------+
In the above schematic, the bit-field flags are spread across two bytes. The least significant bit of the least significant byte is labeled as bit number 0, while the most significant bit of the most significant byte is labeled as bit number 8N-1, where N represents the total number of bytes in the bit-field.
The “8N-1” expression is a general formula used to calculate the highest bit number in a sequence of bytes. It assumes that each byte contains 8 bits. In this formula, “N” represents the total number of bytes in the sequence. For example, if we have a bit-field spanning two bytes, the highest bit number using the “8N-1” formula would be:
Highest bit number = 8 × 2 – 1 = 16 – 1 = 15
So in this case, the highest bit number would be 15, corresponding to the most significant bit of the most significant byte.
What all of this tells us is that the Z-Machine is fundamentally byte-addressable. Let me expand on that thought.
Byte-addressability refers to the ability to access and manipulate individual bytes of memory within a computing system. In the context of the Z-Machine, it means that the Z-Machine’s memory is organized and accessed at the granularity of individual bytes.
In the Z-Machine, the memory is typically implemented as a large contiguous array of bytes. Each byte within this array is assigned a unique address, starting from 0 and incrementing by one for each subsequent byte. This addressing scheme allows for direct and efficient access to any specific byte in the Z-Machine’s memory.
What this further means is that any address in the Z-Machine ultimately resolves to a byte offset from the beginning of memory. Thus everything really comes down to that idea of memory. That’s what we’ll start digging into in the next post and we’ll get started on looking at some of the initial code we need to write.