Movatterモバイル変換

[Panel]

As a rule, "sophisticated" progrmming is pretty boring - optimizingthe unnecessary to speed up theuninteresting. Here, however, is anincredibly sophisticated packageintended for fun and games. Themore you know about software, themore astounded you will become asyou read this.

Zork: The Great Underground Empirepart 1, release 1(c) Copyright 1980 Infocom, Inc. Allrights reserved. Zork is a trademarkof Infocom, Inc.West of House     You are standing in an open fieldwest of a white house, with a boardedfront door.     A rubber mat saying 'Welcome toZork!' lies by the door.     There is a small mailbox here.>OPEN THE SMALL MAILBOX    Opening the mailbox reveals aleaflet.>READ THE LEAFLET(Taken)  Welcome to Zork: The Great Under-ground Empire    Zork: The Great Underground Em-pire is a game of adventvre, danger,and low cunning. In it you will exploresome of the most amazing territoryever seen by mortals.    No computer should be withoutone!    The original ZORK was created byTim Anderson. Marc Blank, BruceDaniels, and Dave Lebling. It wasinspired by the ADVENTURE game ofCrowther and Woods. This version wascreated by Marc Blank, Dave Lebling,Joel Berez, and Scott Cutler.>WALK AROUND THE HOUSENorth of House    You are facing the north side of awhite house. There is no door here,and all the windows are boarded up. Tothe north a narrow path winds throughthe trees.>AGAINBehind House    You are behind the white house. Apath leads into the forest to the east. Inone corner of the house there is a smallwindow which is slightly ajar.>LOOK IN THE WINDOW    You can see what appears to be akitchen.>GO IN    The kitchen window is closed.>OPEN IT    With great effort, you open thewindow far enough to allow entry.>GO INKitchen      You are in the kitchen of the whitehouse. A table seems to have beenused recently for the preparation offood. A passage leads to the west and adark staircase can be seen leadingupward. A dark chimney leads downand to the east is a small window whichis open.      On the table is an elongated brownsack, smelling of hot peppers. A bottleis sitting on the table.     The glass bottle contains:A quantity of water>PICK UPpick up what?>ALL BUT THE SACKkitchen table: An interesting idea . . .glass bottle: Taken.quantity of water: I can't reach that.>GO WESTLiving Room     You are in the living room. There isa door to the east, a wooden door withstrange gothic lettering to the west,which appears to be nailed shut, and alarge oriental rug in the center of theroom.     There is a trophy case here. Abattery-powered brass lantern is onthe trophy case. Above the trophy casehangs an elvish sword of greatantiquity.

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

The original Zork game wasimplemented on a DECsystem-10 atthe MIT Laboratory for ComputerScience in a local Lisp-like languagecalled MDL. This Zork game was latertranslated into a Fortran version forDEC PSP-11 Computers and madeavailable through the DECUS programlibrary. In both versions the program islarge: it occupies most of a process'svirtual storage on a 10, and it requires alarge disk for secondary storage on an11. In converting Zork to run onpersonal computers, the designersneeded some way to shrink it in orderto fit it into the relatively small availablestorage.

One shrinking tactic was to remove the features of MDL that are notneeded in Zork, such as coroutines,associative storage, and fancy input/output. The stripped-down version ofMDL that resulted was named Zork Implementation Language (ZIL).However, that was not enough: a straight-forward compilation ofa ZIL version of the original Zork game into themachine language of any knownpersonal computer would still haveproduced an executable program toolarge to fit.

The solution was to invent a"virtual machine," specifically designedto execute Zork programs; thevirtual "Z-machine" has a machinelanguage called "Z-code", in whichZork programs can be expressed verycompactly. Then all that was neededwas a Zork Interpretive Program (ZIP),written in the machine language of anygiven target personal computer, thatwould imitate a Z-machine in carryingout the Z-code operations. (A compilerthat translates from ZIL to Z-code isalso needed, of course, but the highly-structurednature of MDL, and henceZIL, makes that a relatively simpletask.) A good benchmark for thestorage saved by rewriting Zork in ZILis the Zork parser, which analyzes aplayer's English input: the parser forthe PDP-10 occupies 1OK 36-bit words,while the Z-code parser, which isactually better functionally, occupiesonly 3K 8-bit bytes.

This Z-code approach is similar tothat of compiling a Pascal programinto "P-code," (although there are nowP-code machines, like Western Digital's Pascal Microengine^TM,that are real and not just virtual). In effect, Z-code islike P-code: a string of subprogramcalls, with the bodies of the subprograms executed by a Z-machine orZIP. Any often-used sequence ofpperations in Zork programs could, inprinciple, be compressed into a Z-codeinstruction, thereby moving the sequence of operations into theZ-machine or ZIP, where it needs toappear only once. The Z-machinedesigner just has to be judicious inchoosing Z-code bit patterns andsubprogram parametrizations to getthe most benefit from this virtual-machine method.

Besides compressing the spaceneeded by Zork programs, the Z-codeapproach also makes conversion toanother (real) computer easier, because, assuming that the design ofZ-code is reasonably machine-independent, all one needs to do is toimplement ZIP on the new machine.

Z-code obiects:

Z-code is an object-orientedlanguage (as are Lisp and MDL andZIL). In this section the various kinds ofobjects and the possible operations onthem are described. Excerpts from atranscript of a game are used toillustrate the uses of these objects.

All Z-code objects occupy one ortwo bytes in storage, and exactly twobytes while they are being processed.Like MDL, ZIL uses "type codes" todistinguish among the different typesof objects, but Z-code does not, to savespace: the ZIL compiler checks forproper use of types, but ZIP doesn'tbother. A Z-code operation that yieldsa truth-value (integer 0 or 1) is called(as in Lisp) a "predicate"; the Z-codeoperation-codes for all predicatesinclude a bit for inverting the sense ofthe test, another space-savingmeasure.

Dam Lobby    This room appears to have beenthe waiting room for groups touringthe dam. There are exits here to thenorth and east marked 'Private,'though the doors are open, and an exitto the south.    Some guidebooks entitled 'FloodControl Dam #3' are on the receptiondesk. There is a matchbook whosecover says 'Visit Beautiful FCD#3' here.>COUNT MATCHESYou have 5 matches.>COUNT NOSESI don't know the word 'noses.'

Integer:

An integer, such as the number ofmatches left in a matchbook, is storedin two bytes, according to the normalbit-level representation used by thehardware. Operations on integersinclude the four normal arithmeticfunctions, remainder or modularreduction, and generation of a randominteger in the range 1-N. (Modularreduction - calculating the remainderin a division - is useful for steppingthrough a set of English responsescyclically. Random-integer generationis useful for choosing a response atrandom from a set of similar responses.)Predicates test for oneinteger being less than, greater than, orequal to another integer, and for aninteger being zero. (Since the sense ofa test can be reversed using one of thebits in its operation code, this meansimplicitly that there are also predicatesto test for greater-than-or-equal,less-than-or-equal, not-equal, and not-zero.)Testing for zero may seemredundant, given an equality test, but itis used often enough that the cost ofusing another operation code isoutweighed by the value of eliminatingthe byte that would be used to hold azero in every instance. Naturally, thereis an operation to "print&uot; an integer inthe output stream - though, of coursemost personal computers displaycharacters on a CRT rather thanprinting them on paper.

In some situations an integer istreated as a string of 16 independentbits; for this case there are operationsfor Boolean "and" and "or" and "not,"and for testing individual bits. Thecharacters in the player's input are alsostored as integers, using the ASCIIcode; for this case there is an outputoperation to print a single character, asshown in the last response above.

The Troll Room    This is a small room with passagesto the east and south and a forbiddinghole leading west. Bloodstains anddeep scratches (perhaps made by anaxe) mar the walls.    A nasty-looking troll, brandishinga bloody axe, blocks all passages outof the room.    Your sword has begun to glowvery brightly.>KILL TROLL WITH KNIFE    The blow lands, making a shallowgash in the troll's arm! The troll swingshis axe, and it nicks your arm as youdodge.>AGAIN    The quickness of your thrustknocks the troll back, stunned. Thetroll slowly regains his feet.>AGAIN    A quick stroke, but the troll is onguard. The troll swings his axe, but itmisses.>AGAIN    A good slash, but it misses the trollby a mile. The axe crashes against therock, throwing sparks!>AGAIN    The troll is disarmed by a subtlefeint past his guard. The troll, nowworried about this encounter, recovershis bloody axe.

String:

As you can see, Zork programstend to be wordy, so strings ofcharacters need to be stored ascompactly as possible. Three characters can fit in two bytes, if eachcharacter uses only five bits. But fivebits can encode only 32 charactersdirectly, and that is obviously notenough. The solutlon is to use different"contexts" and to reserve one or more"characters" for switching amongcontexts. (This technique is similar tothe five-bit Baudot code, which wasused by early Teletypes before ASCIIwas invented.) Z-code strings usethree contexts - lower case, uppercase, and digits/punctuation - andseveral characters for switchingamong the contexts, either "permanently"or only for the next character,the latter in order to capitalize a wordor use a single punctuation mark.Because of the extra characters usedto switch contexts, Z-code stringswork out to about five and a half bitsper visible character, which is stillsignificantly more compact than eightbits.

The only operation on strings is toprint them, i.e., show them to theplayer. There is no need to manipulatethem, except to print strings sequentially so that they form sentences forthe player. (Actually, simply because itoccurs so often, there is also anoperation for printing a string and thenreturning from a function call.) Moststrings are stored without "new-line"characters, and ZlP takes care of"folding" the output into lines of a sizeconvenient for the particular displaybeing used; a few rigidly-formattedstrings do use new-lines in order todraw a crude picture with the characters.

>SWIMI don't really see how.>SWIMI think that swimming is best performed in water.>SWIMPerhaps it is your head that isswimming....>TAKE HOUSEWhat a concept!>AGAINA valiant attempt.>AGAINYou can't be serious.>AGAINNot bloody likely.>AGAINAn Interesting idea...

Table:

A table is used to keep a set ofrelated objects (like the responsesabove) together, as a list is used in Lispor a record is used in Pascal. A table isstored as a number of two-byte (orsometimes one-byte) objects one afteranother. The length of a table is sometimes stored in its first elemcnt - to beused by parts of a program thst need tostep through all the elements - andsometimes not - if the program itselfknows how long the table is. Operations on a table can get a word (twobytes) out of it and put a word into it;get a single byte out, and put one in;and move the pointer along to anotherelement (like CDR in Lisp) or backwards to a previous one (like BACK inMDL); (Actually; since a pointer to atable is just a plain address, ordinaryaddition and subtraction are used tomove a pointer forward and backwardin a table.)

Thing:

"Things" are probably the mostinteresting objects, since they represent the player, rooms, enemies,weapons, treasures and so on - thestuff of which a game is made. To avoidconfusion, "Thing" will always bewritten with a capital "T" when it refersto this kind of Z-code object. Sincethere are relatively few Things used ina Zork game, but they are used veryfrequently, each Thing is designatedby a one-byte number rather than, say,its two-byte address in storage. Thisdesign decision limits the number ofpossible Things in one game to 255,with the number zero reserved to mean"no Thing." (There are also "pseudo-Things", whose names the parser willrecognize as significant but whichhave no interesting properties.)

A Thing's number can be easilytranslated into its address in storagewhere its parts are found: status bits,contents, and properties. These partsare stored sequentially, as in a table, ina very strict format: four bytes forstatus, three bytes for contents, andtwo bytes holding the address of theproperty table - so ZlP needs to knowonly the address of the first Thing inorder to translate a Thing number intoits address.

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

>TAKE SACKTaken.>LOOK IN SACKThe brown sack is closed.>OPEN SACKOpening the brown sack reveals alunch, and a clove of garlic.>TAKE LUNCH OUTTaken.>TAKE CLOVER THEN PUTBOTTLE IN SACKTaken.Done.>LOOK IN SACKThe brown sack contains:A glass bottleThe glass bottle contains:  A quantity of water

A Thing'scontents part relates itspatially to other Things in three ways:as a parent ("container") as a chlld("containee"), and as a sibling ("inmate").For example, if the knife andthe bottle are in the kitchen, then thekitchen's "child" slot would hold thenumber of the knife, the knife's "sibling" slot would hold the number ofthe bottle, and the knife's (and bottle's)"parent" slot would hold the number ofthe kitchen. (Of course, depending onhow they got there, the knife and thebottle might be interchanged in thisdata structure.) Such a data structureis commonly called a list: Things canbe added to or removed from a listsimply by moving the appropriatenumbers into the slots. Manipulatinglist structures of this kind - the reasonLisp was invented - is essential inZork games, as Things get moved hereand there by the player. For convenience,"contents" has a more generalmeaning in ZIL: for example, theplayer's baggage is "contained in" theplayer Thing. The operations oncontents 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'ssibling slot).

     This is the attic. The only exit is astairwey leading down. On a table is anasty-looking knife. A large coil ofrope is lying in the corner.>TAKE NASTY KNIFETaken....Maze     This is part ot a maze of twisty littlepassages, all alike.     A skeleton, probably the remainsof a luckless adventurer, lies here.Beside the skeleton is a rusty knife.     The deceased adventurers use-less lantern is here. There is a skeletonkey here. An old leather bag, bulgingwith coins, is here.>TAKE RUSTY KNIFE     As you pick up the rusty knife,your sword gives a single pulse ofblinding blue light.

Finally, each Thing has a table (inthe format described previously) of itsproperties, such as name, size, capacity, score value, verbose description,north neighbor, synonyms, and actionroutines; the last can be seen in thetranscript above involving the twoknives. (The name of a Thing identifiesit uniquely to the player throughout thewhole game, e.g., "kitchen," "bottle,""thief." There is a special Z-codeoperation for printing a Thing's name.)Since there are a limited number ofproperties a Thing can have, and not allof them require the same smount ofstorage, a special format is used tostore them in this table: the first byte ofeach property has a five-bit propertynumber (allowing 32 different properties) and a three-bit count of thenumber of immediately following bytesused to store the property. Theoperations on properties are "getproperty Y of Thing X," "store Z asproperty Y of Thing X," "get the storageaddress of property Y of Thing X," and"get the next property of Thing X following this property."

>SCORE    Your score would be 10 (total of375 points), in 9 moves. This scoregives you the rank of Beginner.

Variable:

Variables are used to keep track ofthe situation all through the game.(Parts of Things are used also.) Forexample, the player's current score is avariable, called a "global" variablebecause it is the same no matter whatfunctions have been called. LikeThings, variables are identified by aone-byte number. A special number isused to identify the top of the "stack,"and fifteen more numbers identify"local" variables used by the functioncurrently executing. (The stack isdescribed later.) The remaining 240numbers identify global variables.Operations on variables store andretrieve the current value, increment ordecrement an integer value by one andoptionally test it for crossing a giventhreshold, push a value onto the stack,pop a value of the stack, and print thevalue.

Other operations:

The remaining Z-code operationsdo not deal directly with objects. Theseoperations include the null operation,go-to (jump, branch), call a function,return a value to the calling function,and return "true" or "false" or whateveris on top of the stack to the callingfunction. Also there are special operationsto input a line from the player andfind the significant words in it using avocabulary table, save the gamesituation on a disk or tape, restore asituation saved previously, quit playingor start afresh.

Z-code format:

Each Z-code instruction beginswith a byte containing the operationcode, which includes bits describinghow the operands (or arguments) areaddressed. Some operations alwaysuse a certain number of operands, andsome operations use an unpredictablenumber of operands, from zero to four.Each operand that is used can be eithera "small" (8-bit) integer, a "large"(16-bit) integer, or a variable (8 bits) . (Astring is an operand for only oneoperation code, the print routine.)Following the operation-code byte arethe operands. An operation thatreturns a value has another bytefollowing the operands that tells inwhat variable to store the value. Apredicate operation has another byteor two that tells where to go to, relativeto this current instruction, if thepredicate is true.

A sub-program is called with aspecial "call" operation code, whoseoperands are the address of thesub-program and the (zero to three)arguments or parameters for this call.

Z-code uses a single stack to storeboth temporary values and returnaddresses for pending function calls.Z-code doesn't distinguish betweenaddresses and other kinds of data but- because ZIL is a "structured"programming language - the ZILcompiler produces Z-code that usesthe stack in a disciplined way,"pushing" and "popping" words in thecorrect order and not confusing onedatum for another.

Storage management:

The address space of a personalcomputer running ZIP is divided intothree parts: impure storage, residentpure storage, and non-resident purestorage. "Impure" means that the datain storage can be modified; impurestorage is where all the Things,variables, stack, and so on live. To"save" the game situation just requireswriting this part of storage onto a diskor tape, and to "restore" is theopposite; all other parts of the programare pure and unchanging, so they don'tneed to be saved.

Resident pure storage holds ZIPitself. "Resident" means that the codeis loaded from disk at the start ofexecution and resides in primarymemory throughout the game. Non-resident pure storage is paged(physical storage divided into pageframes and Z-code program dividedinto pages, typically with 256 byteseach) and swapped (program pagesare kept on disk until needed and thenread in to a suitable page frame forinterpretation). It may be necessary toswap in a page to read the nextsequential byte (if the next byte lies onthe next page) or during a go-to, call,return, or print-string Z-code instruction (if the target address lies onanother page). Fortunately. the firstsituation is easy to test for, since thefirst byte of any page always has zerosfor the least significant bits of theaddress; the second situation occursinfrequently and is easily handled bythe parts of ZIP that interpret thoseinstructions. ZIP keeps track of whichpages are currently in which frames byusing a page table, which holds thefirst virtual address of each page that iscurrently swapped in. ZIP must alsotranslate addresses accordlng towhich frame currently holds whichpage.

All the objects used by a Z-codeprogram are set up in their properlocations and formats by the ZILcompiler. There is no need to createnew objects while the Z-code programruns, and so there is no need to reclaimstorage used by old objects with aLisp-like garbage collector.

With ZIP needs to know to startrunning a game are the first address ofthe three parts of the address space;the first address of Thing storage,global-variable storage, and thevocabulary table used by the "input" Z-code instruction (whence it can findthe number and size of vocabularyentries); and the address of the firstexecutable instruction in the game.

Conclusion:

We have described how a largeprogram can be squeezed into a smallmachine by using a "virtual-machine"approach to encoding the program.Essentially, the designers identifiedsub-programs within the large program (and within a whole series ofsimilar programs) and chose ways toencode invocations of those sub-programs as compactly as possible.Then duplicate copies of those sub-programs couid be removed, and thewhole program could be encoded inthe "machine language" of a virtualZ-machine. This technique follows along line of tradition in computerprogramming that encourages identifying sub-programs and making themmodular and easy to use.

Using this technique, versions ofZork games for personal computerssuch as Radio Shack TRS-80 andApple have been developed byInfocom, Inc., P.O. Box 120, KendallStation, Cambridge, MA 02142. Forinformation about distribution andsales, contact Personal Software, Inc.,1330 Bordeaux Drive, Sunnyvale, CA94086.