ZIL and the Z-Machine

When we left off last time, Marc Blank and Joel Berez were considering how to bring Zork to the microcomputer. Really, they were trying to solve three interrelated problems. At the risk of being pedantic, let me lay them out for you:

1. How to get Zork, a massive game that consumed 1 MB of memory on the PDP-10, onto their chosen minimum microcomputer system, an Apple II or TRS-80 with 32 K of RAM and a single floppy-disk drive.

2. How to do so in a portable way that would make it as painless as possible to move Zork not only to the Apple II and TRS-80 but also, if all went well, to many more current and future mutually incompatible platforms.

3. How to use the existing MDL source code to Zork as the basis for the new microcomputer version, rather than having to start all over again and implement the game from scratch in some new environment.

If you like, you can see the above as a ranking of the problems in order of importance, from “absolutely, obviously essential” to “would be really nice.” That’s not strictly necessary, though, because, as we’re about to see, Blank and Berez, with the eventual help of the others, actually solved them all pretty brilliantly. I wish I could neatly deal with each item above one at a time, but, as anyone who’s ever tackled a complicated programming task knows, solutions tend to get tangled up with one another pretty quickly. So instead I’ll have to just ask you to keep those three goals in mind as I explain how Blank and Berez’s design worked as a whole.

When faced with a game that is just too large to fit into a new environment, the most obvious solution is simply to make the game smaller — to remove content. That’s one of the things Infocom did with Zork. Stu Galley:

Dave examined his complete map of Zork and drew a boundary around a portion that included about 100 or so locations: everything “above ground” and a large section surrounding the Round Room. The object was to create a smaller Zork that would fit within the constraints established by the design of Joel and Marc. Whatever wouldn’t fit was to be saved for another game, another day.

By cutting Zork‘s world almost in half, Infocom were able to dramatically reduce the size of the game. 191 rooms became 110; 211 items became 117; 911 parseable words became 617. It wasn’t a complete solution to their problems, but it certainly helped, and still left them with a huge game, about the same size as the original Adventure in numbers of rooms but dwarfing it in terms of items and words, and easily bigger than any other microcomputer adventure game. And, as Galley notes above, it left them with plenty of raw material out of which to build a possible sequel.

There were more potential savings to be had by looking at the MDL compiler. As a language designed to perform many general-purpose computing tasks, many of MDL’s capabilities naturally went unused by an adventure game like Zork. Even unused, however, they consumed precious memory. Infocom therefore took a pair of pruning shears to MDL just as they had to Zork itself, cutting away extraneous syntax and libraries, and retaining only what was necessary for implementing an adventure game. They named the new language ZIL, for Zork Implementation Language; the compiler that enabled the language, which still ran only on the PDP-10, they called Zilch. ZIL remained similar enough to MDL in syntax and approach that porting the old MDL Zork to ZIL was fairly painless, yet the new language not only produced tighter, faster executables but was much cleaner syntactically. In fact, ZIL encouraged Infocom to not just port Zork to the new language but to improve it in some ways; the parser, in particular, became even better when implemented in the more sympathetic ZIL.

Here is Zork‘s lantern in MDL:

<OBJECT ["LAMP" "LANTE" "LIGHT"]
	["BRASS"]
	"lamp"
	<+ ,OVISON ,TAKEBIT ,LIGHTBIT>
	LANTERN
	()
	(ODESCO "A battery-powered brass lantern is on the trophy case."
	 ODESC1 "There is a brass lantern (battery-powered) here."
	 OSIZE 15
	 OLINT [0 >])>

And here’s the same item in ZIL:

<OBJECT LANTERN 
           (LOC LIVING-ROOM) 
           (SYNONYM LAMP LANTERN LIGHT) 
           (ADJECTIVE BRASS) 
           (DESC "brass lantern") 
           (FLAGS TAKEBIT LIGHTBIT) 
           (ACTION LANTERN-F) 
           (FDESC "A battery-powered lantern is on the trophy 
             case.") 
           (LDESC "There is a brass lantern (battery-powered) 
             here.") 
           (SIZE 15)>

Just for the record, I’ll give a quick explanation of the ZIL code shown above for those interested. The first line simply tells us that what follows will describe an item — or, in ZIL terminology, “object” — called “lantern.” The next line tells us it is in the living room of the white house. Then we see that it can be referred to by the player as “lamp,” “lantern,” or “light,” with the optional adjective “brass” (which might come in handy to distinguish it from the broken lantern found in another part of the game). The so-called short description — more properly the name under which it shows up in inventory listings and other places where it must be plugged into the text — is “brass lantern.” The TAKEBIT flag means that it is an item the player can pick up and carry around with her; the LIGHTBIT means that it casts light, illuminating any dark room in which it is placed or carried. LANTERN-F is the special action routine for the lantern, a bit of code that allows us to write special “rules” for the lantern that apply only to it, such as routines to allow the player to turn it off and on; as I discussed earlier, this level of programmability and the associated object-oriented approach really make MDL, and by extension ZIL, stand out from other adventure-game development systems of their era. The FDESC is the description of the lantern that appears before it has been moved, as part of the room description for the living room; the LDESC appears after it has been moved and set down somewhere else. Finally, the SIZE determines the size and weight of the lantern for purposes of deciding how much the player can carry with her at one time. The rather messier MDL source I’ll leave as an exercise for you to translate…

So, at this point Infocom have largely addressed problem #3, and at least come a long way with problem #1. That left them still with problem #2. You might think it would be easy enough to design an adventure-engine / database partnership like that Scott Adams came up with. However, this was problematic. Remember that one of the things that made Zork‘s development environment, whether it be MDL or ZIL, so unique was its programmability. To go to a solution like that of Adams would force them to sacrifice that, and ZIL in the process. For ZIL to work, it needed to be able to run code to handle those special interactions like turning the lamp on or off; it needed, in other words, to be a proper, Turing-complete programming language, not just a data-entry system. But how to do that while also having a system that was portable from machine to (incompatible) machine? The answer: they would design a virtual machine, an imaginary computer optimized just for playing text adventures in the same way that ZIL was for coding them, then code an interpreter to simulate that computer on each platform for which they decided to release Zork.

Virtual machines are everywhere today. The apps you run on your Android smartphone actually run inside a virtual machine. You might use something like VMWare on your desktop machine to let you run Linux inside Windows, or vice versa. Big mainframe installations and, increasingly, high-end servers running operating systems like Linux often run in virtual machines abstracted from the underlying hardware, which amongst other benefits lets one carve one giant mainframe up into a number of smaller mainframes. Scenarios like that aside, virtual machines are so appealing for essentially two reasons; virtually (ha!) everyone who decides to employ one does so for one or the other, or, often, both. First, they are much more secure. If malicious code such as a virus gets introduced into a virtual machine, it is contained there rather than infecting the host system, and code that crashes the virtual machine — whether it does so intentionally or accidentally — crashes only the virtual machine, not the host system as a whole. Second, a virtual machine allows one to run the same program on otherwise incompatible devices. It is “write once, run everywhere,” as Java zealots used to say. In their case, each target platform need only have a current implementation of the Java virtual machine (not necessarily the language; just the virtual machine). Virtual machines do also have one big disadvantage: because the host platform is emulating another computer, they tend to be much, much slower than native code run on the same platform. (Yes, technologies like just-in-time compilation can do a lot to alleviate this, but let’s not get any further afield.) Still, computing power is cheap and ubiquitous these days, so this generally doesn’t present such a problem. In fact, the modern situation can get kind of ridiculous; my Kindle version of The King of Shreds and Patches is actually built from one virtual machine (Glulx) running inside another virtual machine (the Java virtual machine), all running on a tiny handheld e-reader — and performance is still acceptable.

Even in 1979 the virtual machine was not a new idea. Between 1965 and 1967, a team at IBM had worked in close partnership with MIT’s Lincoln Laboratory to create an operating system called CP-40, under which up to 14 users were each able to log into their own, single-user computer — simulated entirely in software running on a big IBM mainframe. CP-40 eventually became the basis of the appropriately named VM operating system, first released by IBM in 1972 and still widely used on mainframes today. In 1978, a Pascal implementation known as UCSD Pascal introduced the P-Machine, a portable virtual machine that allowed programs written in UCSD Pascal to run on many disparate machines, including even the Apple II following the release of Apple Pascal in August of 1979. The P-Machine became a major influence on Infocom’s own virtual machine, the Z-Machine.

In opting for a virtual machine they would of course have to pay the performance penalty all virtual machines exact, but this wouldn’t be quite as big as you might expect. Just as they had optimized ZIL, Blank and Berez made the Z-Machine as light and efficient as they possibly could, including only those features really useful for running adventure games. They would implement each platform’s interpreter entirely in highly optimized assembly language, with the result that Zork would, even running inside a virtual machine, still run much, much faster than the BASIC adventures that were common at the time. Anyway, the processing powers of the micros, limited as they were, had never been their real concern in getting Zork onto them — memory was the bottleneck. Yes, they would have to sacrifice some additional memory for the interpreter, but they could save even more by building efficiencies into the Z-Machine. For instance, a special encoding scheme allowed them to store most characters in 5 rather than 8 bits, and to replace the most commonly used words with abbreviations in the code. Such text compression was very significant considering that text is, after all, most of what makes up a text adventure. With such compression techniques, along with all of the slicing and dicing of the game itself and the ZIL language, they ended up with a final game just 77 K in size, not counting of course the virtual-machine interpreter needed to run it; this latter Infocom called Zip (not to be confused with the file-compression format). The 77 K game file itself, which Infocom took to calling the “story file,” is essentially a snapshot of the virtual machine’s memory in its opening state.

When we talk about the storage capacity of a computer, we’re really talking about (much to the confusion of parents and grandparents everywhere) two separate figures: disk capacity and memory (RAM) capacity. An Apple II could store 140 K on a single floppy disk, while the TRS-80 actually did a bit better, managing 180 K. Thus, Infocom now had a game that could fit quite comfortably along with the necessary interpreter on a single disk. RAM was the problem: even if we forget about the necessary interpreter, 77 K just doesn’t go into 32 K, no matter how much you try to force it. Or does it?

It was not unheard of even at this time to use the disk as a sort of secondary memory, reading bits and pieces of data from there into RAM and then discarding them when no longer needed. Microsoft had used just this technique to fit Adventure into the 32 K TRS-80; each bit of text, all stored in a file external to the game itself as per Crowther and Woods’s original design, was read in from disk only when it needed to be printed. However, Infocom’s more sophisticated object-oriented system necessarily intermingled its text with its code, making such a segregated approach impractical. Blank and Berez therefore went a step further: having already designed a virtual machine, they now added an implementation of virtual memory to accompany it.

The concept of virtual memory was also then not a new one in the general world of computer science. In fact, virtual memory dates back even further than the virtual machine, to an early supercomputer developed at the University of Manchester called the Atlas, officially commissioned in 1962. In a virtual-memory system, each program does not have an “honest” view of the host computer’s physical memory. It rather is given a sort of idealized memory map to play with, which may have little to do with the real layout of its host computer’s physical RAM. When it reads from and writes to pieces of this map, the host automatically translates the virtual addresses into real addresses inside its physical memory, transparently. Why bother with such a thing, especially as it necessarily adds processing overhead? Once again, for two main reasons, both of which are usually taken as applicable to a multitasking operating system only, something that was little more than a dream for a microcomputer of 1979 or 1980. First, by effectively sandboxing each program’s memory from every other program’s memory, as well as that being used by the operating system itself, virtual memory assures that a program cannot, out of malice or simple bugginess, go rogue and trash other programs or even bring down the whole system. Second, it gives a computer a fallback position of sorts — an alternative to outright failure — should the program(s) running on it ask for more physical memory than it actually has to give. When that happens, the operating system looks through its memory to find pieces that aren’t being used very often. It then caches these away on disk, making room in physical RAM to allocate the new request. When cached areas are accessed again, they must of course be read back into RAM, possibly being swapped with other chunks if memory is still scarce. All of this happens transparently to the program(s) in question, which continue to live within their idealized view of memory, blissfully unaware of the huffing and puffing the underlying system is doing to keep everything going. Virtual memory has been with us for many years now in the desktop PC world. Of course, there inevitably comes a point of diminishing returns with such a scheme; if you’ve ever opened lots and lots of windows or programs on an older PC and seen everything get really, really slow while the hard disk grinds like a saw mill, now you know what was going on (assuming you didn’t already know, of course; we assume no default level of technical knowledge here at Digital Antiquaria Central).

For the Z-Machine, Berez and Blank employed a much simpler version of virtual memory than you’ll find in the likes of Windows, Linux, or OS X. While such important dynamic information as the current position of the items in the game world must of course always be tracked and updated dynamically, most of the data that makes up a game like Zork is static, unchanging: lots and lots of text, of course, along with lots of program code. Berez and Blank were able to design the ZIL compiler in such a way that it placed all of the stuff that could conceivably change, which we’ll called the dynamic data, first in the story file. Everything else, which we’ll call the static data, came afterward. As it turned out, the 77 K Zork story file contained only 18 K of dynamic data. So, here’s what they did…

The dynamic data — memory the virtual machine will write to as well as read — is always stored in the host computer’s RAM. The static data, however, is loaded in and out of RAM by the interpreter as needed in 1 K blocks known as pages. Put another way: from the perspective of the game program, it has fully 77 K of memory to work with. The interpreter, meanwhile, is frantically swapping blocks of memory in and out of the much more limited physical RAM to maintain this illusion. Like the virtual machine itself, this virtual-memory scheme obviously brings with it a speed penalty, but needs must. On a 32 K system with 18 K reserved for dynamic data, Infocom still had 14 K left over to host the VM interpreter itself, a small stack (an area where programs store temporary information needed for moment-to-moment processing), and a page or two of virtual memory. Sure, it was a bit sluggish at times, but it worked. And, when run on a system with, say, 48 K, the interpreter could automatically detect and use this additional memory to keep more static data in physical RAM, thus speeding things along and rewarding the user for her hardware investment.

With the ZIL / Z-Machine scheme as a whole, Infocom had created a robust, reusable system that could have life far beyond this one-time task of squeezing Zork onto the TRS-80 and Apple II. I trust I’m not spoiling anything if I reveal that that’s exactly what happened.

With this technical foundation, we’ll look next time at the process of actually getting Zork onto the market.