The Inverse Parser

LESSON 61

Experiment with intransitive combat relationships.

I had rejected the notion of using a parser at the outset of the project. My initial concept was that people communicated by pointing to icons on their Interspecies Iconic Language card, which would be reproduced on the Macintosh screen. The player would click on icons to communicate. I soon realized that the icons could not be clicked on willy-nilly I had to impose some sort of ordering scheme on the player's actions. In other words, I needed to create a syntax.

Here my designer instincts served me well. Rather than try to create a syntax based on natural languages, I instead set out to create a syntax based solely on word order. This, it turns out, was a crucially important decision. Had I attempted to mimic natural syntax, I would have been caught up in a great many difficult problems. For example, natural syntax makes heavy use of "function words." These are articles such as "the," "a," "an," prepositions, and conjunctions, that serve no direct semantic purpose but instead specify the relationships among the meaningful words in the sentence. They're the glue that bind the words in the sentence. Computationally, they can be a real pain in the butt, but I avoided the need for Designer's Preparation H by simply skipping them. In the same way, I avoided all use of conjugation and declension, those special endings that we tack onto nouns and verbs to indicate how they function in a sentence. Instead, I concentrated on just one simple mechanism for syntax: word order.

Fortunately, I had one other advantage in this problem: a two-dimensional display instead of the one-dimension medium of sound that spoken language uses. For example, consider this simple sentence: "I put it in the box that was broken by the dog." You have no problem understanding that the box referred to was damaged by the actions of the dog. But what about this sentence: "I put it in the box that was broken by the fireplace." In this case, you have no problem figuring out that the box was broken and was positioned close to the fireplace. After all, fire places can't break things, and dogs aren't useful as positional indicators because they move around, so you can disambiguate the sentences easily enough. But if you're a computer and you don't know anything about dogs, boxes, and fireplaces, then you could never figure out which meaning applied.

Now look at the two sentences as they might be displayed graphically (see Figure 23.2).

23.2. Two-dimensional display disambiguates one-dimensional language.

A two-dimensional representation of a sentence shows its structure more clearly. At this point, I took a wrong turn. I was so enamored of the idea of graphically representing the language that I got carried away and tried to include special connector icons that would indicate the nature of the relationship between two adjacent words. I wasted lots of time designing a clever system with vertical lines, horizontal lines, slanted lines, and so forth to indicate all sorts of special things. Then reality caught up with me: I realized that people can stick two words together without all those function words. Indeed, all of the function words can be stripped out of the graph of the sentence, and it is just as computable as the first version (see Figure 23.3).

23.3. "Look Ma, no function words!"

LESSON 62

Always delete clever ideas that don't add to the design.

So I threw out all the clever little connector icons.

At this point, I had a collection of word icons and a scheme for placing them on the screen to organize them into a sentence. I had been thinking solely in terms of output: how the game would talk to the user. But then I had a stroke of genius, so simple and obvious that I didn't even recognize it at the time. I decided to make the input system the same as the output system. Actually, this idea had been implicit in my earliest concepts for the game. The Interspecies Iconic Language card that I had imagined was an intrinsically bi-directional communication device. I had not realized the vast implications of the idea at the time. I simply plugged ahead, devising an input scheme in which the user clicked on icons with the mouse to build his sentence. The killer problem I faced was this: How was I to show the user all the icons in the word set? There were too many to fit comfortably on the screen, and I was anticipating making many more such icons. Somehow I needed to pare down the list of words. I needed an algorithm that would figure out which words were appropriate to choose from in any given situation. What I needed was an inverse parser. So I invented one.

So what, exactly, is an inverse parser? The easiest way to understand an inverse parser is to compare it with a conventional parser. The user enters a string of commands or keystrokes and the parser takes apart the string, identifies the basic components, and figures out whether those components fit together in a meaningful way. If so, it executes the command. If not, it issues an error message and the user must try again. A good deal of algorithmic complexity is required to parse some commands, requiring big hunks of code. Good parsers take years to build.

For the inverse parser, we simply invert the process. First the computer does lots and lots of work figuring out which commands are available given the current context; then it presents that list to the user, who selects one from the list. The inverse parser gobbles up tons of machine cycles, because the computer has to apply all of its syntactical tests to every possible word. By contrast, the regular parser is more parsimonious, because it applies only those syntactical tests that are called for by the user's actual input. But what the hell, machine cycles are cheap and brain cycles are expensive: Let the computer do the work!

Although the inverse parser requires lots of machine cycles to do its job, it doesn't require any extra code. The same code that checks the string after the user inputs it can check a potential string before the user inputs it. It's the same code executed in the opposite order.

NOTE

I later learned that my concept of the inverse parser had already been patented by Texas Instruments back in 1980. It is obvious from their patent that they did not realize the full extent of the implications of the concept. Their implementation of the concept was much narrower than my own. But the basic concept of narrowing words from a set based on context was theirs.

An inverse parser for a natural language would be a horribly complicated affair, because natural languages are so messy. In particular, they permit all sorts of word orders. All sorts of word orders are permitted by them. Word orders of all sorts are permitted by them. They permit word orders of all sorts. Gack!

But my language had a specified word order, and that made all the difference. There were 128 words in my language, so I created a 128x128 array of flags, requiring just 2K of memory (which was still precious in those days). The flags indicated whether word X could be followed by word Y. So if the user had already clicked on word X, then the inverse parser needed to scan only the X-row in the matrix. If the Yth column of the X row contained a value of 0, then the inverse parser concluded that word Y was not an appropriate successor for word X, and eliminated it from consideration. But if that value were a 1, then the inverse parser concluded that word Y was an appropriate successor for word X. With one simple trick, I had eliminated vast amounts of complexity from my inverse parser.

There were, of course, plenty of other considerations as to what words were appropriate in any given context, and I had to write Boolean formulas for each consideration. But it was no special matter to include those Boolean formulas in the code.