The Inner Product, December 2003
Jonathan Blow (jon@number-none.com)
Last updated 27 January 2004
 

Predicate Logic

Related articles:

Lerp 1 (January 2004)
Lerp 2 (February 2004)
Lerp 3 (March 2004)

I believe we are in the midst of a software engineering crisis. Games are getting larger and more complicated, but our programming tools -- languages, compiler systems, debuggers -- are basically stagnant. So far we've been saved, somewhat, by the fact that computers get faster every year, so our code can be worse and worse, and we still get by. But big, sprawling, complex code will eat up as many man-hours as you can dish out, and this year more than ever we've been seeing the results. Delays and feature-cuts are nothing new in our industry, but now it feels as though we are hitting a wall: there seems to be no cutting-edge game that isn't horribly delayed, its features slashed, released as a mere shadow of its creators' intentions. Consequently, each year's cutting-edge is landing ever closer to the previous year's cutting-edge. It would seem that we are traveling along a convergent series, and we will soon be stuck at the furthest point of complexity to which our development methods can reach.

So we try to improve our development methods. Toward that end, the programmers of our industry have dived head-first into a pool of Object Oriented Development books; they bury their programs' data and flow control deep within tangled nests of C++ features. I suggest that these recently adopted ideas are wrong, that these techniques are failing us. After all, the proof is in the pudding -- if the techniques were working, then games using them would become shining development successes. But to the contrary, the games making heaviest use of C++ features seem to be among the tardiest, most spectacular messes. The programmers of our industry are buying heavily into dogma that has not been sufficiently field-tested.

But if you say such a thing in public, you're likely to be scoffed at. How could that huge stack of OOP books be wrong? What kind of joker are you to deride these things which have become standard practice? Well they can scoff at me, because I'm just not buying any of that crap. I spend a lot of time doing contract work with various developers, and I just see them shooting themselves in the foot with this stuff, over and over and over.

I want to explore alternative programming techniques, in areas far away from the current OOP morass. We're now in the habit of needlessly complicating our programs; we need techniques that simplify programs, that enable us to accomplish more, with less exertion.  I'm not trying to say that the idea of object-oriented design is totally wrong; clearly it's useful in many contexts.  However, we've been trying to take it too far, which is what causes all the problems.  It's time to look for some alternatives to augment the object-oriented design philosohpy.

This month I begin a series of articles investigating one trail away from the beaten path. I don't promise that it will revolutionize programming, but it may help some; if every game studio were doing a little bit of open-minded investigation like this, we'd be much better off.

Data Structures and Redundancies

As experienced game programmers, there are many small problems we just solve by rote -- we just set up some data structures and go, same as we've done for years. I would like to take an example of such a situation and question it.

Suppose you're making a game, and you've got objects in the game world -- Entities -- and some of these Entities are players who can carry other Entities. We need some way to represent who is carrying what. Typically we would implement this as follows: each Entity is represented by an instance of a C++ struct or class, and each of those instances contains a list (or array) of all items carried by that Entity. When a player gives a command to drop an item, we step through his "carrying" list to find that item, and we remove it.

Now suppose we have a magical disappearing Stone that needs to remove itself from our inventory, of its own volition. Starting with only a pointer to the stone, we need to remove that stone from the appropriate carrying list. We could find that list by iterating over all Entities in the world, searching for the stone in every carrying list. But that's a big pain, and it's slow besides; instead we tend to put a pointer on the stone (actually, on every entity) that points to the entity who carries it (or NULL if the stone is not being carried).

Now we face an odd issue. A single fact about the world, "The Dude is carrying the Stone", is represented by two different pieces of state: the carrying list on Dude, and the carried_by pointer on the Stone. Our code must be careful to keep these two pieces of data in sync, or else we're in trouble.

I want to quantify this situation. Suppose that the concept of "carrying" represents one unit of game functionality (because it's difficult to see how you might subdivide "carrying" into sub-concepts that make sense on their own). How many units of work it cost us to implement this one unit of functionality, "carrying"? As described above, we need to (1) implement the "carrying" list, then (2) implement the "carried_by" pointer, and then (3) maintain the constraint between them. By a naively simple method of accounting, this is 3 units of work, yieliding 1 unit of functionality. (Probably item 3 is more expensive than the other two, as it is more subtle and is a long-term concern).

Ideally to implement 1 unit of functionality, we want to do 1 unit of work (or less!). Now, taken in just the isolated case of "carrying", this 3-unit situation is not a huge problem -- we just do the work and then move on. But as our program becomes larger, filled with analogous cases, and becomes host to a tangle of interdependent concepts, suddenly we find that we're spending great piles of work units for mere handfulls of functionality units. We can use all the simplicity we can get.

High-Level Languages?

Typically the stated goal of a high-level language is to reduce the amount of work required to create software. However, I think most such languages take insufficient approaches toward this goal (this is especially true of the scripting languages we have been developing for games!) Often they provide features that make programming a little easier, but they fall well short of the dramatic changes we need. Using a language like Lisp or Objective CAML to implement our "carrying" functionality, we may end up typing a little bit less, so our 3 units of work will become slimmer; but they are still 3 pieces of work, and that is bad.

Here I will make an analogy to the situation of optimizing a program's CPU usage. Suppose you profile your program, and there are some frequently-called functions that are taking up a lot of time. The straightforward approach -- streamlining these functions to make them faster -- will give you a speed benefit. But experienced optimizers know that it's much more effective to redesign the code to eliminate those functions (if possible!). A function that you think is fast, is infinitely slower than a function that does not exist.

We face the same situation with this other optimization problem: reducing the time we spend creating software. Many languages have set out to reduce the amount of typing you have to perform in order to make thingsdg happen; but if data manipulation and flow control still occur at roughly the level of C++, then there's a limit to how fast programming can go, and it's not all that much faster than what we already have. Rather than trying to make our small-grained manipulations faster, we should find ways to eliminate them altogether.

The Predicate Logic Experiment

Which brings us to the title of this article. To eliminate redundancies like carries/carried_by, I want to use an unstructured database that just holds facts about who carries what. There are several ways to build such a database, but I chose the style of First-Order Predicate Logic. Predicate logic has been deeply studied throughout the history of computer science so a simple web search provides lots of reference material.

To use predicate logic for our "carrying" example, we just want to insert a fact into the database that says "Dude is carrying Stone." Only that single fact represents the carrying relation, so there is no redundancy. We can perform queries like "What is Dude carrying?" and "Who is carrying the Stone?" with equal ease -- The database engine uses a matching system to generate the answers.

To represent facts, my syntax is a set of arguments enclosed in parentheses, with the predicate listed first. So the fact "Dude is carrying Stone" is written like this: (carrying dude stone). The "carrying" is just an arbitrary label that we are free to choose. In a real game, you would want "dude" and "stone" to be identifiers of instantiated entities. For this simple example, though, we will just use labels for them.

To ask what Dude is carrying, we perform the following query: (carrying dude ?x). The question mark indicates that "x" is a variable. The database engine looks for any facts that are 3 arguments long and have "carrying" and "dude" as the first two arguments. It returns a list of all possible values for x, in other words, everything that Dude is carrying. If we want to know who is carrying the stone, we can make this query: (carrying ?x stone); now we will get back a list containing everyone who is carrying the stone (which should be only 1 or 0 items long.)

As programmers who care about the speed of things, we might worry: when there are a lot of facts in the database, how do we organize them so that these queries can be answered quickly? My answer for now is, we're simply not going to optimize. All database items will be stored in one big linked list and the search will proceed through them all. That's because I will be changing this system rapidly over the next few articles, so it needs to be very simple and flexible. In the long term, when we care about speed, we can let the programmer set policies about which labels or argument slots get indexed by primary hashes, and secondary hashes, etc -- decisions that are hopefully informed by a good profile report. These policies would be set late in development, allowing for a rapid development model where the programmer can create initial functionality worrying about speed.

Interestingly, we now have a full implementation of the "carrying" functionality without performing any of the 3 work units listed earlier. We have no inter-data constraints to maintain, and we don't even have to declare anything either, assuming we can just dump all the "carrying" facts into a global namespace. I would say that there's about 1 work unit here, which involves remembering that the label "carrying" has been used, and that it's a predicate with two arguments, first the guy who carries, second the guy being carried. Though this isn't directly comparable with our earlier implementation method, it seems to be much less effort.

With this predicate logic approach applied across an entire codebase, the resulting simplification would be significant. Just to speak of lists of Entities: in my current game, implemented the old-school C++ way, I have many views of the same set of data: one hash table of all Entities that exist, mapped by an integer ID; one list for each type of Entity (containing all of that type), lists for Entities that have been created but not fully initialized by network traffic, lists of Entities that have been fully initialized but not yet added to the world, or that have been removed from the world but not yet destroyed; lists for Entities that are "awake" or "asleep" according to the physics system. All of these are just the poor C++ programmer's method of performing simple hardcoded database operations. (There are further redundant views that are beyond our scope today, like spatial partitionings of Entities for visibility culling or collision management.) Properly juggling entities between all these lists, in response to game events, can be a challenge.

Within a fact-database framework, we can perform database queries directly, and most of the lists above simply disappear -- they go away and are replaced by nothing. It is infinitely easier to program nothing than to program a lot of small things.

The Logic Part

Besides adding bare facts to the database, we can also add rules of inference: if such-and-such things are true, that implies that this other thing is true. The implied fact can be queried about, just like facts that have been asserted directly into the database.

Let's look at a time-honored example, the "sister scenario", which seems to have been expounded in every tutorial ever written about the programming language Prolog. We have some people, Ann, Mark, and Don, and some facts about them: (female ann) -- "Ann is Female"; (parent ann don) -- "A parent of Ann is Don", et cetera. See Listing 1 for the full set of asserted facts. In addition to these, we can assert an inference rule, "Is y the sister of x?":

(sister ?x ?y) <- (female ?y), (parent ?x ?p), (parent ?y ?p), (notequal ?x ?y).

The "<-" means "is implied by", and the comma is a logical AND. So y is the sister of x if y is female, the parent of x is some p, the parent of y is that same p, and x and y are not equal (assume notequal is a built-in primitive). Now suppose we want to perform a query, like "Who is Mark's sister?", in other words, (sister mark ?s). The database engine will match this query against the rule for sister, substituting the arguments mark for ?x and ?s for ?y, giving us the following temporary rule:

(sister mark ?s) <- (female ?s), (parent mark ?p), (parent ?s ?p), (notequal mark ?s)

The engine will then attempt to handle all the queries on the right-hand side. If each query can be resolved (whether by a direct assertion or another inference rule!), then a result will be returned, a binding for the ?s in (sister mark ?s). In this case, the query will return Ann as the result. See Listing 1 for more examples of queries we can perform. More complex inference rules can be asserted, including recursive ones (as we will see next month). The general framework of predicate logic can include other operations besides what we have described here. However, just with assertion and implication, we can do some very interesting things.

Sample Code, and Next Month

This month's sample code provides a simple predicate logic assertion and querying system. Next month we'll expand the power of this system, building it into the larger framework of a full programming language.