Notes from the Dawn of Time #7:

Matching

by Richard Bartle
November 28, 2001

Last time, I showed what the inheritance hierarchy looked like for functions. However, I drew it as a tree, rather than as a full hierarchy. Now I’m going to explain why. (You might want to refer to the tree as I go through this).

In theory, { dexterity player } should have both { dexterity creature } and { attribute player } as parents, because in the atom hierarchy DEXTERITY is a kind of ATTRIBUTE and PLAYER is a kind of CREATURE. Nevertheless, I only gave it one parent, { dexterity creature }. The reason for this is because of an inheritance clash.

As { dexterity player } has no code defined for itself, it must inherit it from one of its parents. Strictly speaking, the choice is arbitrary, but in practice it doesn’t matter so long as it always chooses to inherit from the same parent (remember how I used this line of argument when talking about the advantages of multiple inheritance over single inheritance?).

In the example, I chose to make [ dexterity player ]() inherit from { dexterity creature }. This was not an arbitrary decision: I used an algorithm. I did this because programmers need to know the order in which code will be evaluated, so things like output come in the right order. Thus, I matched atoms in a function call left-to-right against definitions, choosing the most specific first. DEXTERITY is an exact match against DEXTERITY but is in a subclass relationship with ATTRIBUTE, therefore the code for { dexterity creature } would be found before that for { attribute player } from a call to [ dexterity player ]().

It’s possible to inherit both, of course. For example, the code for { drop penny } might be exactly the same as for { drop object } except that it prints a message first ("The penny drops"). It seems sensible, therefore, to make { drop penny } a subclass of { drop object } that prints the message and then inherits the general code defined for { drop object } to perform the actual dropping function. This would give it a backtracking facility akin to that possessed by the language Prolog.

Purity versus Pragmatism

I tried this with MUD2, but rejected it.

First of all, the backtracking has to be explicit (you had to say "backtrack at this point", rather than as in Prolog where you’d say "don’t backtrack past this point"); this is because there are so many catch-all error messages ("You can’t drop that!" etc.) that if backtracking were implicit you’d need to switch it off after practically every function call. Explicit backtracking is not necessarily a bad thing in itself, though.

Secondly, I found that I simply didn’t have much use for it. Implementationally, the overheads involved in keeping track of function call matches just in case a backtrack was asked for at some point were sufficiently great that I dropped the idea so I could write a faster run-time system. It did run faster as a consequence, but I believe this pragmatism to have been a mistake: I later realized that it was possible at compile-time to figure out which functions needed to be backtrackable and which didn’t, which would have let me keep the necessary functionality without burdening the program except when it was going to be used. Oh well, you live and learn!

The point is, though, that in practice you have to invoke backtracking so infrequently that you don’t really need it at all. A function call has to match but one definition, and therefore it effectively has only one parent. Although { dexterity player } matches both { dexterity creature } and { attribute player }, if it only ever inherits code from { dexterity creature } then effectively it doesn’t have { attribute player } as a parent at all. That’s why I didn’t draw the connection in the OOP hierarchy.

Advocates of single inheritance who haven’t gone to sleep by now are permitted at this point to smirk and say, "See! You used it in the end!".

Methods

I guess I’d better explain what we have now, given that I’m bound to have lost most readers somewhere along the way with my incoherent ramblings...

Things in the game (what you might colloquially call "objects") are represented by atoms. They are arranged in a multiple inheritance hierarchy, the atom hierarchy. Atoms have no methods directly associated with them.

Examples: PENNY, COIN, MONEY, TREASURE, OBJECT.

Also in the atom hierarchy are atoms representing actions and verbs. These don’t have any methods associated with them either.

Examples: SMITE, HIT, KILL, ACTION.

Functions do have methods associated with them. A function definition is a list of atoms from the atom hierarchy, plus the associated executable code. This executable code is the only method a function ever has.

Example: { density penny }: [ mass penny ]()/[ volume penny ]()

When a function is called, if that function is defined exactly then its associated code is executed. Otherwise, the function inherits the code it is to execute from a superior function in the OOP hierarchy (or function hierarchy). A left-to-right, most-specific-first match of atoms in the call against atoms in the definitions determines which function’s code is to be inherited.

And that’s what it’s taken me 6 articles to derive.

Summary

The above system describes what I designed and implemented for MUD2 in 1985, as the core of my programming language, MUDDLE. I can’t believe there aren’t far better languages to use for writing MUDs, but then I can scarcely believe that most MUDs today are written using approaches quite as archaic as they are! I don’t expect anyone to use my solutions for improvement, or even to adapt them, but if people at least look at different ways to advance MUD engine design, well, that’s enough for me.

Next article I’ll tidy up a few remaining loose ends with inheritance, which will hopefully lead seamlessly to a new topic entirely...