?

Log in

TADS 3 System Development

Mercury, cont'd: what's there, what's to come

TADS 3 System Development

Mercury, cont'd: what's there, what's to come

Previous Entry Share Next Entry
As promised, more details on the Mercury library I posted yesterday.

First, I should outline my goals with the Mercury project. It was never simply a port of the TADS 2 library to TADS 3 - that would actually make a great separate project, and I think the Mercury parser would serve as a good starting point. If someone wants to pursue that, I'd be all for it. But what I had in mind when I started working on Mercury was a hybrid agenda: I wanted to combine the simplicity of the TADS 2 world model with some of the more important features of the Adv3 parser and command system. I also wanted to fix some of the key deficiencies of the TADS 2 world model; many of those were problems with design rather than oversimplifications, so I felt that I could make improvements without necessarily adding any complexity.

Despite the hybrid goals, Mercury isn't not a hybrid code base. It doesn't inherit any actual code from either the TADS 2 library or Adv3. It doesn't even directly inherit most of the design features of either; as I got going on the project, I tried to re-examine the design of each component, rather than just taking a TADS 2 or Adv3 motif and transplanting it into the new system. So a lot of what's in Mercury is new at the design level - which makes the new library untested not just at the lines-of-code level.

Next, an overview on the major components.

Parser: this looks superficially a lot like the Adv3 parser. It's based on a network of grammar rules using TADS 3 'grammar' objects, because I think the 'grammar' scheme is the right tool for this job. The set of grammar rules in Adv3 is large and complex, but I don't think there's any way around that; English grammar is large and complex. Mercury defines basically the same grammar as Adv3. However, Mercury has what I think is a much smarter division of labor. If you look through the Adv3 English grammar, it has a ton of code defined in the 'grammar' objects. In contrast, the Mercury English grammar has almost none - it's almost purely declarative, just a list of token processing rules. The difference is in how the two parsers represent the results of parsing. Adv3 used the "sentence diagram" that comes out of the grammar tree as the result. Mercury builds what compiler writers call an abstract syntax tree, or AST. An AST operates at a higher level; it represents the semantic elements of the input rather than the tree of words and phrases. This approach greatly simplifies the code that analyzes the parse results. I've found the Mercury parser much easier to work on than the Adv3 parser, and I think game authors will find it much easier to customize.

I've tried to keep the parser's dependencies on the world model to a minimum. The parser obviously needs to interrogate the world model to some extent in order to resolve noun phrases to objects, so some interaction is a given, but I've tried to minimize the interface so that the parser can be used in other offshoot projects.

One slight expansion on the Adv3 parsing model is explicit support for three-object verbs, with a direct, indirect, and "auxiliary" object: PUT THE COIN IN THE SLOT WITH THE TONGS. This is one of those perennial wish-list items that was always a huge pain with Adv3 (and practically impossible with TADS 2), but the new way of representing parsed output actually made it pretty easy to add these, so I did for the sake of completeness. It would probably be equally easy to have four- or ten-object verbs as well, but the playability implications for even three-object verbs are bad enough that I think we can safely rule out the N-object case for all N > 3.

Spelling corrector: Mercury has spelling correction baked into the parser. This of course uses the edit distance calculator built into the Dictionary class - which makes the basic task of producing a candidate correction pool very fast, allowing the correction code in the library to do a lot of higher level analysis to pick good matches. If you fire up the sample game, try playing around with typos - I think the corrector does a really good job, but it'll be interesting to see how it does in actual play.

Parser questions: When the parser asks a question like "Which book do you mean?" or "What do you want to unlock it with?", it uses this neat little feature, which is similar to Special Topics in Adv3 but better generalized.

Distinguishers: Similar to the Adv3 concept, but the implementation is simpler.

Noun phrase parsing: Noun phrase parsing is both simpler and more sophisticated than in Adv3. It's simpler in that the grammar for a noun phrase is just a list of the words attached to an object, which is similar to Inform 6's approach. This makes it a lot easier to define unusual phrasings like "key to the house" (where we have a preposition in the phrase), "science and progress magazine" (a conjunction in the phrase) or "button 6" (inverting the usual English adj-noun order). Making the noun phrase grammar totally generic with respect to word order means that there's no need to define new grammar rules for unusual phrases like those. But, hey, this is TADS, and we like to separate our parts of speech. So when it comes to resolving noun phrases, the parser still analyzes them according to the parts of speech, so it can still distinguish "pizza" from "pizza box" on the strength of the adjective/noun usage.

(I think this is a successful example of what I've been trying to accomplish with the project: it simplifies the game programming model without reducing the functionality.)

Object states: The parser has a formal mechanism for handling object states - lit/unlit, open/closed, red/green/blue. States are automatically used to resolve noun phrases, so "take the lit match" works without any special coding in the match. There's a State class that defines a state and its associated vocabulary; in order to have a state, an object simply defines the property for the state, such as isLit or isOpen, so in terms of the game programming there's practically no work.

Commands and Doers: These objects are the heart of the execution model. A Command is essentially the AST (see above) for a parsed verb, with slots for the Action (verb) and objects. It's comparable to an Action in Adv3, but it's a bit cleaner in that it's a synthesized object rather than a parse tree. Doer is a new concept. This is where the library and game will define the handling for a particular command. A Doer is a global object that has a template for a command to process; the template is given as a string, which can name verbs, object classes, and individual objects. If you look at the sample/test program, you'll see several examples at the top. Here's one:

Doer cmd = 'put Thing in Thing';

That says we should match the 'put in' command when a Thing is the direct object and another Thing is the indirect object. You can define a more specific one, like

Doer cmd = 'put Thing in Container';

To execute a command, the parser scans the population of Doers for the best match, and then calls its exec() method. There's of course a hierarchy of priorities, one of which is object class specificity - so the Container match will override the Thing match. Another is an explicit "priority" property for times when you want to coerce a particular processing order. There are also ways to attach conditions to a Doer to limit it to specific times or places. This is somewhat similar to the Inform 7 rulebook scheme, but it's simpler and more transparent. This is obviously a new, untested approach, so it remains to be seen if it's effective and scalable. I like it so far, though. One aspect that makes me think it's promising is that it can straightforwardly degenerate to a traditional TADS 2/3 model where everything gets dispatched to the objects: you'd just write the exec() method to delegate to the appropriate objects in the Command object. And then you'd still be able to use Doers to write a few custom overrides at the verb level, before the objects got involved, which is something that got tacked on in the Adv3 model because it's an occasional necessity. But I think it'll turn out that this is a better way to write command handlers in general - especially for two-object verbs, since it creates a formal abstraction point that's separate from either object but aware of both, eliminating the usual confusion in the object-oriented approach over which object's handler runs first and all that.

The rest of the execution model has yet to be fleshed out, along with all of the default handling for all of the basic verbs. For 90% of the pre-defined verbs, a generic 'verb Thing' Doer with an exec() method that displays suitable apologies should be all that's required.


Queries: This is another big new concept (along with Doers). This is another bit of I7 rulebook influence. The idea is that when we have a question about the state of the world model, such as "can actor A see thing B?" or "what's in scope to actor A?", we don't ask the objects involved directly, but instead ask the "world model" as a separate entity. As with Doers, this solves certain problems that the OOP approach has when multiple objects are involved in the questions: with OOP, we always had to worry about whether we ask A if it can see B, or ask B if it can be seen by A, and whether the answers would be consistent. And as with Doers, the scheme allows for a hierarchy of query handlers, so that a particular query's answer can be overridden based on location or current conditions.

The query mechanism looks promising to me in its current state, but I think it might need a few more passes to get right. When you look at it, try to think in terms of the abstraction rather than the syntax, because I don't think this part is quite ready for prime time.

Containment model: I couldn't resist trying to enhance the containment model a bit - another perennial wish-list item. The TADS 2 and Adv3 way of handling different containment types (on, in, under, etc) is to make the type of containment an attribute of the container. That seems simple, but it's not a very match to reality, and it makes things terribly complicated when you want an object with an inside and a top. So this time around I've moved the containment type to the child - so each object has a 'location' property and a 'locType' property that says what type of containment relationship it has with its location. This makes all of the containment code in Thing somewhat more elaborate, but my hope is that it won't matter much to game code, where the main change you'll see is that you can write things like moveOnto() or moveUnder() in addition to moveInto().

Sense model and scoping: This part is pretty much pure TADS 2. The Adv3 sense model with its partial transparencies and so forth is a huge source of Adv3's complexity, and also takes a heck of a lot of computing horsepower. I figured if the library is supposed to be lighter weight, this is the number one thing to cut in terms of the cost/benefit tradeoff. However, I don't think there will be a ton of lost flexibility, thanks to the Query mechanism above - I think that when it came to actual practice, most of the uses for the more advanced Adv3 features were essentially special cases anyway, and the Query scheme should be able to handle those more easily.

Prerequisites: Essentially the same as Adv3 preconditions, but a little bit more generalized, to allow for enforcing condition checks even when they can't be automatically brought into being with an implied command. I think preconditions are among the more useful upgrades in Adv3 vs TADS 2, so I think it's important to keep these in the model.

Output processing: The output processor is much simpler than in Adv3. This might need to get beefed up as the library evolves, but I'd prefer to see this part stay simple; the complex layering of output filtering and capturing in Adv3 is much too fragile, so I'd rather look for other ways to handle as much of that as possible - other ways that don't involve output filtering, but instead making decisions about output before generating it. The output handler does have a good infrastructure for parsing HTML, though, so it'll be technically straightforward to add HTML-level processing as needed.

There is, of course, a good message processor that handles object phrase substitutions, narrative person options ("I don't see that here" vs "You don't see that here"), and verb tenses. I got kind of carried away with the verb tense handling and implemented six English tenses (present, past, perfect, past perfect, future, and future perfect); this was more because the design was flexible enough to accommodate it than for any practical reason, since I very much doubt anyone will want to write a game that says things like "You will not have seen any blue books there." I really should add the subjunctive mood for real completeness.

The message processor is similar to the one in Adv3, although it's actually a bit nicer, I think. Apart from triple the verb tenses, it has a friendlier approach to handling verb conjugation, which is that it uses a dictionary for irregular verbs rather than making you write conjugations in-line in every message. The syntax for writing a message is thus a lot simpler and more readable. The substitution syntax has some other nice features, such as positional parameters that let you use the message processor even when you don't have a Command in progress (with Adv3, the message processor depends on an Action being in progress as the source of the object parameters), spelled-out numbers, and in-line list making. It also lets you define the "terse" version of message in-line with the full message, as in 'Taken.|{I} {pick} up {the dobj}.'.

Translations: Mercury uses the Adv3 approach to translations, of placing the language-specific code in a separate set of English files. Hopefully the size of the translation task will be scaled down from Adv3 in proportion with the rest of the library.

One change from the Adv3 approach is in how message text is coded. In Adv3, message text is all coded as strings in the English message objects. In Mercury, English message text is entered in-line where the message is actually used, using the DMsg macro. The macro takes the actual text of the message along with a unique message ID tag (which is just a string) and any positional substitution arguments for the message. Don't worry - this doesn't mean messages are hard-coded as English. When you compile with LANGUAGE set to English, the macro uses the English text. When you compile with any other LANGUAGE value, the macro generates a lookup using the ID tag. Each language module provides a table of ID tags to message string mappings. The nice thing about this approach is that it makes the code a little easier to read by letting you see the actual text of each message where it's actually generated, rather than having to cross-reference against a separate message list (msg_neu.t in Adv3). I think it'll also make the job of translating slightly easier: the DMsg macro makes an easy grep target, so translators can still easily find all of the messages, but now they can see each English message in its original context without having to cross-reference backwards from the message file to the point(s) of use.

Utilities: util.t has a bunch of useful utility functions and patterns. Among the more interesting: (1) a function prototype matching system that makes it fairly easy to write functions and methods that take different types of parameter lists, and figures out which actual list was passed in. (2) a static object construction system that unifies constructor calling for static and dynamic objects, so that you don't have to create nearly so many explicit PreinitObjects. (3) singleton iterators, which let you invoke a for..in loop on any object, whether it's a collection or a singleton; if it's a singleton, the loop just runs for the single object. (4) a general-purpose list differencing engine (the spelling corrector uses this to display the list of corrected words, but it can be used to get a diff report for any pair of lists).

...

That's most of what's implemented so far. There are a few things missing before this can be used to write anything real. The biggest piece is that the command execution model needs to be completed, and default handlers written for the standard verbs (take, drop, put in, travel, etc). The other big piece is that the code to generate room descriptions and item listings is only sketched out.

There's also a much less than half-baked idea, maybe 1% baked, that I started thinking about and haven't gotten back to yet, in the form of the Effect object. I'm not sure if this is going to be worth pursuing. The idea is that an Effect object represents an executed command; it's the counterpart of the Command object after the command has been carried out. A Command represents an intention to perform some action, and an Effect represents the result of performing the action. So rather than generating text output directly, a command handler would create an Effect object. There'd be a separate Effect subclass for each unique thing that can happen in the game; so, for example, there'd be an Effect subclass that represents an actor taking an object (the actor and object would be properties of the Effect, so there'd be just one Effect subclass for "take", not a separate subclass for each object that can be taken). The Effect object encapsulates the code for executing the operation and a message describing the outcome.

The point of Effect objects is to do something like the Adv3 transcript, but representing things at a higher level to make post-processing easier. Adv3 manages some neat tricks with the transcript mechanism, but the code to pull off those tricks can be awfully hard to write and easy to break. But I'm not sure if Mercury should have any sort of transcript intermediary at all; there's something to be said for the TADS 2 way of doing things where command handlers just do the work and display the results, and those results hit the display immediately without going through miles of convoluted internal plumbing.

  • One thing that might be worth pursuing is built-in support for cross-version save and restore, rather than the inflexible, fixed VM image deltas we have now. Ben has been working on an extension for that, but incorporating it in the actual design of Mercury would probably make things much easier.
    • save and restore, etc.

      That's a great idea. I have the framework for JSON serialization of game state, but ideally it would be baked into the library so authors didn't have to think about it.

      My other wishlist item is a web-based IDE along the lines of playfic.com or wescheme.org. That should be mostly a matter of fitting existing pieces together - adding T3 support to CodeMirror, setting up a build server, possibly integrating with a service like DropBox or GitHub for project storage.

      With that in place we would have a much stronger cross-platform story to tell authors.
      • Re: save and restore, etc.

        Talking about Web-based stuff, I recently toyed with this nifty C++-to-JavaScript compiler called Emscripten. It uses LLVM. You can actually build a JavaScript TADS interpreter with this by compiling the C/C++ sources.

        The problem is that the TADS main loop is not asynchronous, so it blocks the browser forever. If that part of TADS could be refactored, then it would be relatively easy to build a client-side JS terp that runs existing T2/T3 games, including multimedia support.
        • Re: save and restore, etc.

          That's pretty interesting - is it actually fast enough to be playable? That's a lot of layers of cross-compiling and interpretation.

          What are you using for the osifc layer for the cross-build? That would be the place to address the event loop issue. I'm not even sure it's possible to fix, though; the TADS interpreter is a stateful program that calls out to a nested event loop to read input, and browsers are stateful programs that run nested event loops to read input. so there might be a fundamental incompatibility in that both models insist on owning the event loop. In the browser model, the only way that a JS program can do a "read next event" is to terminate and return - using setTimeout with a closure makes it possible to write code that preserves state and resumes a stateful task after the next event comes in, but I don't think it's even remotely tractable to adapt that technique to a large existing body of code like TADS, especially if you want to cross-compile from C++.

          The reason that the TADS Web UI works is that the browser and TADS run in separate threads and coordinate via message queues, so they're each free to block whenever they want without interfering with the other side's event loop. I'm not sure there's any way to make this work in a browser without true JS threads. But maybe someone has a more clever idea than I can come up with on this...

          Edited at 2012-08-16 08:32 pm (UTC)
          • Re: save and restore, etc.

            Indeed that's how emscripten works. You need to have your main() as usual, but then you pass a callback to the system and specify how many times per second it should be called. Then you let your main() exit. The browser then calls the callback you specified. In that callback, you do 1 iteration of your application's event loop and then exit.

            However, the program is stateful. All your static vars and globals are kept between each invocation. A simple example:

            
            int testVar = 0;
            
            void mainLoop(void)
            {
                printf("%d\n", testVar);
            }
            
            int main(void)
            {
                emscripten_set_main_loop(mainLoop, 1);
                testVar = 1;
                return 0;
            }
            


            Even though testVar is initialized to 0 and only set to 1 in main(), after main() exits and the browser calls mainLoop() directly (once per second), testVar is preserved and "1" is printed. This is the above code compiled into JS:

            http://foss.aegean.gr/~realnc/emscripten/test.html

            As for speed, I suppose it would be quite fast. Currently, games, including 3D ones, as well as the Bullet Physics engine have been ported to JS using this. They run quite well. Other stuff has been ported as well, like the full Python interpreter. DOSBox is also in the works (and in this case we're talking about an x86 emulator, including real-mode *and* protected-mode.)

            Browser support is a bit hit and miss right now due to usage of very recent JS features. Mainly the current Firefox and Chrome browsers work. But other browsers should catch up soon.

            The event loop issue will probably need to be resolved at some point anyway; from the three main platforms (Windows, Mac, Linux), only Windows has support for asynchronous application event loops. This is quite a problem with QTads; I managed to hack my way around it by doing some nasty nested event loops and manually advance the GUI event loop. But in Cocoa (Mac) in particular, this isn't really working. The result is a small memory leak due to object deletion not happening until the GUI's event loop runs naturally, which can never happen while a game is running since vm_run_image() never returns until the game quits. So object deletion doesn't happen and thus memory is not freed. But the problem is minor since it only affects GUI objects, and not many of those are created/deleted during a game.

            In the (probably near) future, even the hacky ways I used to deal with it won't be supported anymore. So sooner or later, something will need to be done about this. Moving the game execution into a separate thread will solve this, but in a quite inefficient manner; GUI operations are not allowed from anything other than the main thread. So absolutely everything that changes the screen or needs events (and that's a lot) will need to pass through an IPC mechanism.

            What's needed is for vm_run_image() to set up its internal state and then return. I know this is much easier said than done :-) I tried to refactor Hugo's event loop into an asynchronous one. Hugo is *much* simpler that Tads, and yet it's still a nightmare to do the refactoring (lots of nested *and* recursive event loops that all block.)

            Other than that, there's yield() support in the making for JavaScript (ECMA already put out the framework.) But naturally, it will probably be years before support for this actually lands in browsers. But if/when it does, we can simply yield() at any point in the code and execution will resume directly after the yield() in the code with the call stack and all local vars preserved.

            Btw, there's a very interesting talk about Emscripten, given by its main author at JSConf in 2011. If you're interested in it:

            http://jsconf.eu/2011/emscripten.html

            The geek in me likes those :-)
            • Re: save and restore, etc.

              Nikos - I think the classic solution to this is co-routines. C++ doesn't have a native co-routine mechanism (of course not :)), but on most platforms you can build them out of setjmp/longjmp and a little OS-specific code to set up a new co-routine stack. Plus I wouldn't be surprised if there are some existing semi-portable co-routine libraries for gcc. For QTads, if the nested event loops are a problem, co-routines could be a fairly easy solution. You'd create a co-routine for the t3vm main entrypoint, and a second co-routine for the Qt initialization; whenever any of the tads osifc routines want to do a nested event loop, you instead suspend the t3vm co-routine and transfer control back to the Qt co-routine; and when Qt invokes an event callback, you transfer control back to the t3vm co-routine. If this emscripten thingy has a good enough C++ machine model emulation that it can handle setjmp/longjmp and artificial stacks, the same approach could be used there.
              • Re: save and restore, etc.

                Boost has co-routines, I think. Will need to look into it.

                I don't know if emscripten can work with such code, since it doesn't actually emulate anything. It "just" transforms C++ into JS. So the system calls will be translated too, but they don't exist in JS.

                I don't actually know JS well enough. I've been told that the Firefox implementation of yield cannot be used because the 'yield*' operator is missing.
  • (no subject) - stankaufman
    • Re: Implications for game authors?

      "Will we have to choose and learn one of the several APIs?"

      Obviously. How else can you use something if you don't first learn something about it?

      "Will players have to install different TADS VMs to play different games?"

      No. The T2VM plays T2 games, the T3VM plays T3 games. Mercury is Tads code, not a new VM.

      "Will any of this new code make it easier to port TADS VMs to, say, the iPhone."

      TADS code has zero effect on VM portability. The VM isn't written in TADS (it's written in C and C++).
  • In line with a recent thread at intfiction, what about some basic multiplayer support in Mercury? I understand that this may complicate things past the point of what's intended, but at the same time a lightweight multiplayer component could facilitate uptake. It could feasibly be a Mercury-compatible extension, but I think now is the time to consider how it might fit in.
    • Do you want to take on that piece? If you want to be the point person for this, great. The first question to look into is what you'd need to add to the library in concrete terms to make it multi-player, and assess the impact of those additions on the single-player programming model. If the impact is minimal, I'd be okay with it; if the impact is significant, my proposal would be to do what I suggested about a TADS 2 port, which is to branch the project as a separate library that starts with the Mercury parser core and adapts it into an MPIF library.

      My gut reaction is that the branch approach will work better, but I could be wrong. I do think it'll add non-trivial complexity to the programming model, which would make it a tough sell to add to it the base library; Adv3 is the already kitchen sink library, and there's no point in having two of those. Another reason I think branching makes more sense is that multi-player games tend to be somewhat different in design from single-player IF, so my intuition is that game developers would be better served by building a library around MP design from the ground up rather than adapting a single-player IF library.
      • My thoughts about branching are similar to yours. I've just started watching Jesse McGrew's new work on Guncho (it seems like he's working toward some abstractions for a MPIF library) so before I get into deep with Mercury I want to see where all of that is going.
  • Prereqs

    The multiple levels of check, prereq, and verify added a pretty significant dose of complexity over T2's single verification method. It becomes hard to decide where to put the code for failure, and hard to locate and override the source of unwanted behavior in default classes. I think the many possible phases of failure generation also contributes to the need for the complex transcripting process. Furthermore, the check method (and to some extent the prereqs) are mostly used to disambiguate. Tads 3 stands out from the pack with its sophisticated disambiguation, but it seems to me that most games just don't have a ton of similarly-named objects, and the occasional "Which ball do you mean, the red ball or the green ball?" is a reasonable price to pay for much simpler library and game code.

    You mention that prereqs are particularly valuable, but I remember feeling like the prereqs tended to lead to surprising behavior when there were multiple prereqs, and tended to stand in the way of giving satisfyingly customized responses for Is there a way to streamline all this?
Powered by LiveJournal.com