<!--
	Title: How to Fit a Large Program Into a Small Machine
	Subtitle: or How to fit the Great Underground Empire on your desk-top
	Authors: Marc S. Blank and S. W. Galley
	Source: Creative Computing, v6(7)
	Date: July 1980
	Transcription by Steve Derby
-->

<img class="float-right-wide" src="/public/img/articles/how-to-fit-a-large-program-into-a-small-machine/zork-cartoon-1.png" alt="Cartoon drawing of a house">

<p class="article-sidebar-dark" style="font-size: inherit;" >
As a rule, "sophisticated" programming is pretty boring -- optimizing
the unnecessary to speed up the uninteresting. Here, however, is an
incredibly sophisticated package intended for fun and games. The
more you know about software, the more astounded you will become as
you read this.
</p>

Imagine yourself sitting down at your favorite personal computer,
inserting a diskette, turning on the power, and seeing what follows. Your
typed replies are in capital letters.

<div style="font-style: italic;">

Zork: The Great Underground Empire part 1, release 1

© Copyright 1980 Infocom, Inc. All rights reserved. Zork is a trademark
of Infocom, Inc.

West of House<br>
You are standing in an open field west of a white house, with a boarded
front door.<br>
A rubber mat saying 'Welcome to Zork!' lies by the door.<br>
There is a small mailbox here.

&gt;OPEN THE SMALL MAILBOX<br>
Opening the mailbox reveals a leaflet.

&gt;READ THE LEAFLET<br>
(Taken)<br>
Welcome to Zork: The Great Underground Empire<br>
Zork: The Great Underground Empire is a game of adventure, danger,
and low cunning. In it you will explore some of the most amazing territory
ever seen by mortals.<br>
No computer should be without one!

</div>

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
Z-code strings work out to about five and a half bits per visible character,
which is still significantly more compact than eight bits.
</blockquote>

<div style="font-style: italic;">

The original ZORK was created by Tim Anderson, Marc Blank, Bruce
Daniels, and Dave Lebling. It Was inspired by the ADVENTURE game of
Crowther and Woods. This version was created by Marc Blank, Dave Lebling,
Joel Berez, and Scott Cutter.

&gt;WALK AROUND THE HOUSE<br>
North of House<br>
You are facing the north side of a white house. There is no door here,
and all the windows are boarded up. To the north a narrow path winds through
the trees.

&gt;AGAIN<br>
Behind House<br>
You are behind the white house. A path leads into the forest to the east. In
one corner of the house there is a small window which is slightly ajar.<br>
&gt;LOOK IN THE WINDOW<br>
You can see what appears to be a kitchen.

&gt;GO IN<br>
The kitchen window is closed.

&gt;OPEN IT<br>
With great effort, you open the window far enough to allow entry.

&gt;GO IN<br>
Kitchen<br>
You are in the kitchen of the white house. A table seems to have been
used recently for the preparation of food. A passage leads to the west and a
dark staircase can be seen leading upward. A dark chimney leads down
and to the east is a small window which is open.<br>
On the table is an elongated brown sack, smelling of hot peppers. A bottle
is sitting on the table.<br>
The glass bottle contains:<br>
A quantity of water

&gt;PICK UP<br>
pick up what?

&gt;ALL BUT THE SACK<br>
kitchen table: An interesting idea ...<br>
glass bottle: Taken.<br>
quantity of water: I can't reach that ..

&gt;GO WEST<br>
Living Room<br>
You are in the living room. There is a door to the east, a wooden door with
strange gothic lettering to the west, which appears to be nailed shut, and a
large oriental rug in the center Of the room.<br>
There is a trophy case here. A battery-powered brass lantern is on the trophy
case. Above the trophy case hangs an elvish sword of great antiquity.

</div>

This transcript shows the beginning of an adventure into a land of
Zork. Zork was originally a single "computerized fantasy simulation"
game in which the object is to explore a labyrinth, called the Great Underground
Empire, comprising a variety of interesting caves or rooms, and to find
hidden treasures and return safely with them. We now say that Zork is a
computer-game environment in which different games, with different scenarios
and different puzzles to solve, can be written. A Zork player converses
with a Zork program by typing commands in a kind of restricted
English and reading the program's English responses. A longer description
of the original game and program can be found in
"[Zork: A Computerized Fantasy Simulation Game](/library/zork-a-computerized-fantasy-simulation-game)"
by Lebling, Blank, and Anderson (IEEE Computer,
April 1979, pp. 51-59).

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
Status bits represent qualities of a Thing, both permanent (edible, burnable,
fightable, "room," etc.) and temporary ("lit," "open," etc.).
</blockquote>

The original Zork game was implemented on a DECsystem-10 at
the MIT Laboratory for Computer Science in a local Lisp-like language
called MDL. This Zork game was later translated into a Fortran version for
DEC PDP-11 computers and made available through the DECUS program
library. In both versions the program is large: it occupies most of a process's
virtual storage on a 10, and it requires a large disk for secondary storage on
an 11. In converting Zork to run on personal computers, the designers
needed some way to shrink it in order to fit it into the relatively small available
storage.

One shrinking tactic was to remove the features of MDL that are not
needed in Zork, such as coroutines, associative storage, and fancy
input/output. The stripped-down version of MDL that resulted was named Zork
Implementation Language (ZIL). However, that was not enough: a straight-forward
compilation of a ZIL version of the original Zork game into the
machine language of any known personal computer would still have
produced an executable program too large to fit.

<img class="float-right-wide" src="/public/img/articles/how-to-fit-a-large-program-into-a-small-machine/zork-cartoon-2.png" alt="Cartoon Zork Image">

The solution was to invent a "virtual machine," specifically designed
to execute Zork programs; the virtual "Z-machine" has a machine
language called "Z-code," in which Zork programs can be expressed very
compactly. Then all that was needed was a Zork Interpretive Program (ZIP),
written in the machine language of any given target personal computer, that
would imitate a Z-machine in carrying out the Z-code operations. (A compiler
that translates from ZIL to Z-code is also needed, of course, but the
highly-structured nature of MDL, and hence ZIL, makes that a relatively simple
task.) A good benchmark for the storage saved by rewriting Zork in ZIL
is the Zork parser, which analyzes a player's English input: the parser for
the PDP-10 occupies 10K 36-bit words, while the Z-code parser, which is
actually better functionally, occupies only 3K 8-bit bytes.

This Z-code approach is similar to that of compiling a Pascal program
into "P-code," (although there are now P-code machines, like Western Digital's
Pascal Microengine™, that are real and not just virtual). In effect, Z-code is
like P-code: a string of subprogram calls, with the bodies of the subprograms
executed by a Z-machine or ZIP. Any often-used sequence of
operations in Zork programs could, in principle, be compressed into a Z-code
instruction, thereby moving the sequence of operations into the Z-machine
or ZIP, where it needs to appear only once. The Z-machine
designer just has to be judicious in choosing Z-code bit patterns and
subprogram parametrizations to get the most benefit from this virtual
machine method.

Besides compressing the space needed by Zork programs, the Z-code
approach also makes conversion to another (real) computer easier, because,
assuming that the design of Z-code is reasonably machine-independent,
all one needs to do is to implement ZIP on the new machine.

## Z-code objects:

Z-code is an object-oriented language (as are Lisp and MDL and
ZIL). In this section the various kinds of objects and the possible operations on
them are described. Excerpts from a transcript of a game are used to
illustrate the uses of these objects.

All Z-code objects occupy one or two bytes in storage, and exactly two
bytes while they are being processed. Like MDL, ZIL uses "type codes" to
distinguish among the different types of objects, but Z-code does not, to save
space; the ZIL compiler checks for proper use of types, but ZIP doesn't
bother. A Z-code operation that yields a truth-value (integer 0 or 1) is called
(as in Lisp) a "predicate"; the Z-code operation-codes for all predicates
include a bit for inverting the sense of the test, another space-saving
measure.

<div style="font-style: italic;">

Dam Lobby<br>
This room appears to have been the waiting room for groups touring
the dam. There are exits here to the north and east marked 'Private,'
though the doors are open, and an exit to the south.<br>
Some guidebooks entitled 'Flood Control Dam #3' are on the reception
desk. There is a matchbook whose cover says 'Visit Beautiful FCD#3' here.

&gt;COUNT MATCHES<br>
You have 5 matches.

&gt;COUNT NOSES<br>
I don't know the word 'noses.'

</div>

## Integer:

An integer, such as the number of matches left in a matchbook, is stored
in two bytes, according to the normal bit-level representation used by the
hardware. Operations on integers Include the four normal arithmetic
functions, remainder or modular reduction, and generation of a random
integer in the range 1-N. (Modular reduction - calculating the remainder
in a division - is useful for stepping through a set of English responses
cyclically. Random-integer generation is useful for choosing a response at
random from a set of similar responses.) Predicates test for one
integer being less than, greater than, or equal to another integer, and for an
integer being zero. (Since the sense of a test can be reversed using one of the
bits in its operation code, this means implicitly that there are also predicates
to test for greater-than-or-equal, less-than-or-equal, not-equal, and not-zero.)
Testing for zero may seem redundant, given an equality test, but it
is used often enough that the cost of using another operation code is
outweighed by the value of eliminating the byte that would be used to hold a
zero in every instance. Naturally, there is an operation to "print" an integer in
the output stream -- though, of course most personal computers display
characters on a CRT rather than printing them on paper.

In some situations an integer is treated as a string of 16 independent
bits; for this case there are operations for Boolean "and" and "or" and "not,"
and for testing individual bits. The characters in the player's input are also
stored as integers, using the ASCII code; for this case there is an output
operation to print a single character, as shown in the last response above.

<div style="font-style: italic;">

The Troll Room<br>
This is a small room with passages to the east and south and a forbidding
hole leading west. Bloodstains and deep scratches (perhaps made by an
axe) mar the walls.<br>
A nasty-looking troll, brandishing a bloody axe, blocks all passages out
of the room.<br>
Your sword has begun to glow very brightly.

&gt;KILL TROLL WITH KNIFE<br>
The blow lands, making a shallow gash in the troll's arm! The troll swings
his axe, and it nicks your arm as you dodge.

&gt;AGAIN<br>
The quickness of your thrust knocks the troll back, stunned. The
troll slowly regains his feet.

&gt;AGAIN<br>
A quick stroke, but the troll is on guard. The troll swings his axe, but it
misses.

&gt;AGAIN<br>
A good slash, but it misses the troll by a mile. The axe crashes against the
rock, throwing sparks!

&gt;AGAIN<br>
The troll is disarmed by a subtle feint past his guard. The troll, now
worried about this encounter, recovers his bloody axe.

</div>

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
The name of a Thing Identifies It uniquely to the player throughout the
whole game, e.g., "kitchen," "bottle," "thief."
</blockquote>

## String:

As you can see, Zork programs tend to be wordy, so strings of
characters need to be stored as compactly as possible. Three characters
can fit in two bytes, if each character uses only five bits. But five
bits can encode only 32 characters directly, and that is obviously not
enough. The solution is to use different "contexts" and to reserve one or more
"characters" for switching among contexts. (This technique is similar to
the five-bit Baudot code, which was used by early Teletypes before ASCII
was invented.) Z-code strings use three contexts - lower case, upper
case, and digits/punctuation - and several characters for switching
among the contexts, either "permanently" or only for the next character,
the latter in order to capitalize a word or use a single punctuation mark.
Because of the extra characters used to switch contexts, Z-code strings
work out to about f1ve and a half bits per visible character, which is still
significantly more compact than eight bits.

The only operation on strings is to print them, i.e., show them to the
player. There is no need to manipulate them, except to print strings sequentially
so that they form sentences for the player. (Actually, simply because it
occurs so often, there is also an operation for printing a string and then
returning from a function call.) Most strings are stored without "new-line"
characters, and ZIP takes care of "folding" the output into lines of a size
convenient for the particular display being used; a few rigidly-formatted
strings do use new-lines in order to draw a crude picture with the characters.

<div style="font-style: italic;">

&gt;SWIM<br>
I don't really see how.

&gt;SWIM<br>
I think that swimming is best performed in water.

&gt;SWIM<br>
Perhaps it is your head that is swimming.

&gt;TAKE HOUSE<br>
What a concept!

&gt;AGAIN<br>
A valiant attempt.

&gt;AGAIN<br>
You can't be serious.

&gt;AGAIN<br>
Not bloody likely.

&gt;AGAIN<br>
An interesting idea...

</div>

## Table:

A table is used to keep a set of related objects (like the responses
above) together, as a list is used in Lisp or a record is used In Pascal. A table is
stored as a number of two-byte (or sometimes one-byte) objects one after
another. The length of a table is sometimes stored in its first element - to be
used by parts of a program that need to step through all the elements - and
sometimes not - if the program itself knows how long the table is. Operations
on a table can get a word (two bytes) out of it and put a word into it;
get a single byte our and put one in; and move the pointer along to another
element (like CDR in Lisp) or backwards to a previous one (like BACK in
MDL). (Actually, since a pointer to a table Is just a plain address, ordinary
addition and subtraction are used to move a pointer forward and backward
in a table.)

## Thing:

"Things" are probably the most interesting objects, since they represent
the player, rooms, enemies, weapons, treasures and so on - the
stuff of which a game is made. To avoid confusion, "Thing" will always be
written with a capital "T" when it refers to this kind of Z-code object. Since
there are relatively few Things used in a Zork game, but they are used very
frequently, each Thing is designated by a one-byte number rather than, say,
its two-byte address in storage, This design decision limits the number of
possible Things in one game to 255, with the number zero reserved to mean
"no Thing." (There are also "pseudo-Things", whose names the parser will
recognize as significant but which have no interesting properties.)

A Thing's number can be easily translated into its address in storage,
where its parts are found: status bits, contents, and properties. These parts
are stored sequentially, as in a table, in a very strict format: four bytes for
status, three bytes for contents, and two bytes holding the address of the
property table - so ZIP needs to know only the address of the first Thing in
order to translate a Thing number into its address.

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
Operations that do deal directly with ojects include the operation, go-to (jump,
branch), call a function, return a value to the calling function, return
"true" or "false" or whatever is on top of the stack to the calling function.
</blockquote>

Each Thing has 32 *status bits*, which can be turned off or on or tested
individually by Z-code operations. Status bits represent qualities of a
Thing, both permanent (edible, burnable, fightable, "room," etc.) and
temporary ("lit," "open," etc.).

<div style="font-style: italic;">

&gt;TAKE SACK<br>
Taken.

&gt;LOOK IN SACK<br>
The brown sack is closed,

&gt;OPEN SACK<br>
Opening the brown sack reveals a lunch, and a clove of garlic.

&gt;TAKE LUNCH OUT<br>
Taken.

&gt;TAKE CLOVE THEN PUT BOTTLE IN SACK<br>
Taken.<br>
Done.

&gt;LOOK IN SACK<br>
The brown sack contains:<br>
A glass bottle<br>
The glass bottle contains:<br>
&nbsp;&nbsp;A quantity of water

</div>

A Thing's *contents* part relates it spatially to other Things in three ways:
as a parent ("container") as a child ("containee"), and as a sibling ("inmate").
For example, if the knife and the bottle are in the kitchen, then the
kitchen's "child" slot would hold the number of the knife, the knife's
"sibling" slot would hold the number of the bottle, and the knife's (and bottle's)
"parent" slot would hold the number of the kitchen. (Of course, depending on
how they got there, the knife and the bottle might be interchanged in this
data structure.) Such a data structure is commonly called a list: Things can
be added to or removed from a list simply by moving the appropriate
numbers into the slots. Manipulating list structures of this kind -- the reason
Lisp was invented -- is essential in Zork games, as Things get moved here
and there by the player. For convenience, "contents" has a more general
meaning in ZIL: for example, the player's baggage is "contained in" the
player Thing. The operations on contents are

- "move X into Y,"
- "remove X from everything" (e.g., if it is eaten or otherwise destroyed),
- "is X in Y?" and "what is X in (if anything)?" (using X's parent slot),
- "what is the first Thing (if any) in X?" (using X's child slot), and
- "what is the next Thing (if any) in the same Thing that X is in?" (using X's sibling slot).

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
Program pages are kept on disk until needed and then read in to a suitable page frame for interpretation.
</blockquote>

<div style="font-style: italic;">

This is the attic. The only exit is a stairway leading down. On a table is a
nasty-looking knife. A large coil of rope is lying in the corner.

&gt;TAKE NASTY KNIF£<br>
Taken.<br>

...

Maze<br>
This is part of a maze oftwisty little passages, all alike.<br>
A skeleton, probably the remains of a luckless adventurer, lies here.
Beside the skeleton is a rusty knife.<br>
The deceased adventurer's useless lantern is here. There is a skeleton
key here. An old leather bag, bulging with coins, is here.

&gt;TAKE RUSTY KNIFE<br>
As you pick up the rusty knife, your sword gives a single pulse of
blinding blue light.

</div>

<img class="float-right-wide" src="/public/img/articles/how-to-fit-a-large-program-into-a-small-machine/zork-cartoon-3.png" alt="Cartoon drawing of a troll">

Finally, each Thing has a table (in the format described previously) of its
properties, such as name, size, capacity, score value, verbose description,
north neighbor, synonyms, and action routines; the last can be seen in the
transcript above involving the two knives. (The name of a Thing identifies
it uniquely to the player throughout the whole game, e.g., "kitchen," "bottle,"
"thief." There is a special Z-code operation for printing a Thing's name.)
Since there are a limited number of properties a Thing can have, and not all
of them require the same amount of storage, a special format is used to
store them in this table: the first byte of each property has a five-bit property
number (allowing 32 different properties) and a three-bit count of the
number of immediately following bytes used to store the property. The
operations on properties are "get property Y of Thing X," "store Z as
property Y of Thing X," "get the storage address of property Y of Thing X," and
"get the next property of Thing X following this property."

*>SCORE<br>
Your score would be 10 (total of 375 potnts), in 9 moves. This score
gives you the rank of Beginner.*

## Variable:

Variables are used to keep track of the situation all through the game.
(Parts of Things are used also.) For example, the player's current score is a
variable, called a "global" variable because it is the same no matter what
functions have been called. Like Things, variables are identified by a
one-byte number. A special number is used to identify the top of the "stack,"
and fifteen more numbers identify "local" variables used by the function
currently executing. (The stack is described later.) The remaining 240
numbers identify global variables. Operations on variables store and
retrieve the current value, increment or decrement an integer value by one and
optionally test it for crossing a given threshold, push a value onto the stack,
pop a value off the stack, and print the value.

## Other operations:

The remaining Z-code operations do not deal directly with objects. These
operations include the null operation, go-to (jump, branch), call a function,
return a value to the calling function, and return "true" or "false" or whatever
is on top of the stack to the calling function. Also there are special operations
to input a line from the player and find the significant words in it using a
vocabulary table, save the game situation on a disk or tape, restore a
situation saved previously, quit playing or start afresh.

## Z-code format:

Each Z-code instruction begins with a byte containing the operation
code, which includes bits describing how the operands (or arguments) are
addressed. Some operations always use a certain number of operands, and
some operations use an unpredictable number of operands, from zero to four.
Each operand that is used can be either a "small" (8-blt) integer, a "large"
(16-bit) integer, or a variable (8 bits). (A string is an operand for only one
operation code, the print routine.) Following the operation-code byte are
the operands. An operation that returns a value has another byte
following the operands that tells in what variable to store the value. A
predicate operation has another byte or two that tells where to go to, relative
to this current instruction, if the predicate is true.

A subprogram is called with a special "call" operation code, whose
operands are the address of the subprogram and the (zero to three)
arguments or parameters for this call.

Z-code uses a single stack to store both temporary values and return
addresses for pending function calls. Z-code doesn't distinguish between
addresses and other kinds of data, but -- because ZIL is a "structured"
programming language -- the ZIL compiler produces Z-code that uses
the stack in a disciplined way, "pushing" and "popping" words in the
correct order and not confusing one datum for another.

## Storage management:

The address space of a personal computer running ZIP is divided into
three parts: impure storage, resident pure storage, and non-resident pure
storage. "Impure" means that the data in storage can be modified; impure
storage is where all the Things, variables, stack, and so on live. To
"save" the game situation just requires writing this part of storage onto a disk
or tape, and to "restore" is the opposite; all other parts of the program
are pure and unchanging, so they don't need "to be saved.

Resident pure storage holds ZIP itself. "Resident" means that the code
is loaded from disk at the start of execution and resides in primary
memory throughout the game. Nonresident pure storage is paged
(physical storage divided into page frames and Z-code program divided
into pages, typically with 256 bytes each) and swapped (program pages
are kept on disk until needed and then read in to a suitable page frame for
interpretation). It may be necessary to swap in a page to read the next
sequential byte (if the next byte lies on the next page) or during a go-to, call,
return, or print-string Z-code instruction (if the target address lies on
another page). Fortunately, the first situation is easy to test for, since the
first byte of any page always has zeros for the least significant bits of the
address; the second situation occurs infrequently and is easily handled by
the parts of ZIP that interpret those instructions. ZIP keeps track of which
pages are currently in which frames by using a page table, which holds the
first virtual address of each page that is currently swapped in. ZIP must also
translate addresses according to which frame currently holds which page.

<blockquote style = "border-top: solid 0.25em; border-bottom: solid 0.25em; font-size: 1.5em;">
We have described how a large program can be squeezed into a small
machine by using a "virtual-machlne" approach to encoding the program.
</blockquote>

All the objects used by a Z-code program are set up in their proper
locations and formats by the ZIL compiler. There is no need to create
new objects while the Z-code program runs, and so there is no need to reclaim
storage used by old objects with a Lisp-like garbage collector.

With ZIP needs to know to start running a game are the first address of
the three parts of the address space; the first address of Thing storage,
global-variable storage, and the vocabulary table used by the "input" Z-code
instruction (whence it can find the number and size of vocabulary
entries); and the address of the first executable instruction in the game.

## Conclusion:

We have described how a large program can be squeezed into a small
machine by using a "virtual-machine" approach to encoding the program.
Essentially, the designers identified sub-programs within the large
program (and within a whole series of similar programs) and chose ways to
encode invocations of those subprograms as compactly as possible.
Then duplicate copies of those subprograms could be removed, and the
whole program could be encoded in the "machine language" of a virtual
Z-machine. This technique follows a long line of tradition in computer
programming that encourages identifying sub-programs and making them
modular and easy to use.

Using this technique, versions of Zork games for personal computers
such as Radio Shack TRS-80 and Apple have been developed by
Infocom, Inc., P.O. Box 120, Kendall Station, Cambridge, MA 02142. For
information about distribution and sales, contact Personal Software, Inc.,
1330 Bordeaux Drive, Sunnyvale, CA 94086.

<div class="smaller" style="border-top: 1px solid;">
Marc S. Blank. 2315 Stearns Hill Rd., Waltham,
MA 02154, and S. W. Galley, 285 Gray St., Arlington,
MA 02174.
</div>
