Prose Generation Techniques for Small Platforms

One odd omission in the interactive fiction authoring tool Inform 7 is its inability to instantly change the story away from second person present tense. This job is left to extensions. Over the years the original extension to do this became such a maintenance nightmare for its writer that this past November I rewrote it from the ground up, keeping in mind the tight memory restrictions of the target platform: the Z-machine, a virtual machine suitable for cell phones. What follows is some optimization techniques for light prose generation for similarly constrained platforms.

To support changing the viewpoint and tense at runtime, the new set of messages contained embedded functions to fetch the appropriate pronouns, auxiliary verbs, etc. at the moment of printing. Coded naively, that's a function with a lot of if-statements. So the first trick used was bitfields. A bit is the smallest unit of computer memory, being either a zero or a one at any given time. (Hence a 16-bit computer uses that many bits to represent a single number.) A bitfield gives each individual bit a separate meaning, so every combination of circumstance can be represented as a single number. For example, conjugation has the first bit representing present (0) and past (1) tense; the second bit represents the perfect aspect, and the third bit the continuous aspect. All eight combinations are represented as a single number zero through seven, and answering runtime questions like "is this verb conjugation in the continuous?" or "is this past-perfect tense?" is very efficient.

A second optimization used those bitfields as a row number in a lookup table. For example, the declension bitfield combines viewpoint with case.  There are eight viewpoints: second person, third person feminine, first person plural, etc.  There are five supported cases: subjective ("I", "we", etc.); objective ("me", "us"); possessive ("mine", "ours"); reflexive ("myself", "ourselves"); plus the oddball possessive adjective ("my", "our").   Combined, they give the appropriate pronoun for the current position within the containing sentence and for the current viewpoint of the story.  Out of those forty combinations, a single lookup finds the correct pronoun.  No if-statements needed.

Third was an interesting inversion of making the exception the rule. Verbs have several inflected forms: the present ("-s"), past ("-ed"), present participle ("-ing"), and past participle ("-en", frequently identical to the past). Irregular verbs do not follow the suffix rule, so must be listed and looked up similar to the pronouns. But, by treating the standard suffixes as a single irregular verb themselves, the irregular verb's code handled regular verbs as well:  the rule became an exception. And this code is mildly recursive: when printing the present form of the irregular "take", the text may or may not need the -s suffix for subject-verb agreement. So, the irregular verb TAKE appends (or not) the 'irregular suffix verb' as appropriate. 

Future tense is a curious case of function not following form. Semantically, future tense is a tense, to be grouped with past and present tenses. But syntactically, English indicates future tense via the word will placed in front of the verb phrase. This categorizes future tense with other modals such as could, would, and should (which can be handy for games). Indeed, a quick dictionary search shows that would is the past tense of will just as could is the past tense of can. Since one bit was already defined as past/present tense, two additional bits were added to the bitfield for the modalities can/could, will/would, and shall/should (not to mention "none of the above").

The astute reader may wonder whether I (or why I did not) treat entire verb phrases as a lookup similar to the pronouns, with entries like "could have been carried" preceding "could have been being carried" and the like. Memory is the reason. The bitfield allowed a bit for "not", a bit for mood (inquisitive versus indicative), and a bit for voice (active versus passive). The commonest question words who, when, why, etc. were allowed another 3 bits. All told, such a lookup table would have tens of thousands of rows, each being multiple letters (bytes) long, and with a lot of repetition. While I can't say I'm completely happy with the code that disentangles it all, it is at least fairly concise.

Of course, this extension had more constraints than just memory. Source-level backward compatibility with the original extension entices authors to switch. Both extensions have a "light" version for authors who need only to rewrite messages, not alter the tense and viewpoint, so my new extension has two different directions for "backward" compatibility. Inform itself now supports source-level code replacement, and this was put to good use. The popular Plurality extension somewhat overlaps the prose generation features, so a self-censoring section looks for Plurality's inclusion to avoid duplicating functionality.  Similarly, source-level replacement removed the original set of messages stuck in second person present tense. The latter step alone saved an astounding 10K.

And if all that weren't enough, the new extension needed to be very easy to use because writers comprise much of Inform 7's audience.  Writers do not put up with whiny, needy code. For this, a pre-release version in the forums produced many excellent corrections and suggestions, the best of which involved renaming key features to something much more writer-friendly.

The final result can be seen here.  Comments and suggestions are always welcome.