Rule-Based Programming

(...Notes Towards...)

Getting Started

In fall of 2003, as Graham Nelson was working on what would become Inform 7, I got into a discussion with him on what I thought an ideal IF design language would look like.

My intuition (based on many years of IF design work) was that the best model is a collection of rules. A rule is like a partial function: it describes how to handle a particular action, under particular conditions. Many rules might cover the same action, under different conditions.

For example, the "examine" command should print "You see nothing special" in the general case; but should print the description of the Elvish sword if the command's object is the sword, and the contents of the ancient book if the object is the book; but if you haven't learned the book's language, it should complain instead; and if the lights are out, it should in any case say "It's too dark to see that." All of these strictures can be formulated as rules, with various conditions and outcomes.

The traditional way to handle this in IF is an object-oriented model, where the object's "examine" method is run. But this needs to be extended, because not all conditions are distinguished by the command's object. There are environmental properties (darkness), properties of the player (known languages), and properties of the entire world (time of day). You can force this back into an O-O structure with a sort of code harness, which checks methods on the object, the room, the player, and so on. That's how Inform 6 works. But there's still a degree of mish-moshedness to it. I found myself designing games as rule collections, and then "porting" that design into I6.

So I suggested a structure which was all rules.

This sounds great, but there are lots of unresolved problems. Rules frequently conflict. Then you need to decide which rule to follow. (In the above example, the "nothing special" rule must be pre-empted by all the others; the "too dark" rule must pre-empt all the others; and so on.) You can often make an "obvious" choice about which rules take precedence, but the game author has to be able to make the final decision. (Does the "I don't know that language" rule pre-empt "too dark"? What if the book is luminescent -- or the language is Braille? Games will vary.)

I bounced the problem around for several months, but I failed to come up with a complete and satisfactory solution.

Rules in Inform 7

In the meantime, Graham was making I7 come together. He incorporated some of the ideas that had come out of our discussion. Rules and rulebooks are a fundamental I7 mechanism, and actions are largely structured as collections of rules. The precedence problem is handled by a mix of logical specificity (exceptions pre-empt general cases) and source-code order (later rules pre-empt earlier ones).

However, conditions are not handled uniformly or universally across the language. I7 actions, activities, and phrases all support slightly different models of conditions and outcomes. There are structures hardwired into I7 (check/carry-out rules, etc) which I think ought to be handled as rules, no different from any other rules in the system. And the mechanism for re-ordering rules is -- to me, at least -- awkward and inflexible.

This is not a condemnation of I7. I don't have a rule model which is powerful enough to do what I7 does. So I'm in no position to propose a replacement. But I have continued to think about the problem.

Online Discussion

I still don't have a solution, but I have written some long posts which (I hope) are beginning to creep in the right direction. Google archive links:

Properties and more (thread index)
...which takes on the idea of "object properties", and extends them into a rule model which also covers the common notion of "object class". Buried in the thread is this post, which gives some of the underlying concepts of the rule model.
Rule ordering by grouping (thread index)
...which takes the grouping idea from above, and turns it into a model for deciding precedence without driving the game author crazy. I hope.

Designing My Language

Or rather, "not yet designing my language, but..."

In spring of 2009, I wrote this presentation, which gives the case for the rule model in more detail: Rule-Based Programming in Interactive Fiction (with nifty slides!)

In May of 2010, I took part in an online chat with William Byrd and Doug Orleans, where we discussed the problems and possible solutions. You can read the transcript.

Relevant Research

Since I don't come out of the academic world -- or rather, I came out of it after college and never looked back -- it didn't occur to me that people might have already researched this stuff.

Chung-chieh Shan pointed me at some papers. (Thanks!) The stuff I'm talking about -- particularly the "properties" idea -- looks a lot like a model in computer science called defeasible logic. (As in, "These logical rules are not incontrovertible; they can be defeated by other logical rules." In other words, rules with exceptions.)

Defeasible Logic (Donald Nute)
Nute invented the idea.
Propositional Defeasible Logic has Linear Complexity (Michael J. Maher)
Has a simple introduction to defeasible logic. Gives an algorithm for working out consequences of rulesets in linear time (i.e., proportional to the number of rules).
An Argument-Based Approach to Reasoning with Specificity (Phan Minh Dung, Tran Cao Son)
A way of attacking the precedence problem.
I am not, mind you, planning to jam the whole defeasible-logic propositional calculus into an IF language. It's more providing a guide to what kind of model to use. For example, I didn't have a clear idea of what rule precedence was until I read Nute, who assumes precedence is an acyclic binary relation on rules. Okay, that makes sense; that's the target. I need to take my ideas about precedence, and use them to generate an acyclic binary relation.

I also asked around for books on logic programming, in both Prolog (the classical logic-programming language) and other languages. I haven't started to dig into these yet, but I'll post the list. (Also includes some references to natural language in Prolog, which is interesting for IF for completely separate reasons.)

The Reasoned Schemer
Daniel P. Friedman, William E. Byrd and Oleg Kiselyov
Prolog Programming in Depth
Michael A. Covington, Donald Nute, Andre Vellino
Concepts, Techniques and Models of Computer Programming
Peter Van Roy
Prolog and natural-language analysis
Fernando C. N. Pereira and Stuart M. Shieber (available online)
Natural Language Computing: An English Generative Grammar in Prolog
Ray Dougherty

Last updated June 16, 2010.

Zarfhome (map) (down)