Speak the Problem's Language

A Data-Driven Design Pattern

Eugene Wallingford
© 1997


Learning to write AI programs introduces you to different techniques of programming, most of which can be used even when not writing AI programs. One such technique is demonstrated throughout Chapter 2 of Peter Norvig's Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp. I like to call this programming pattern "Speak the Problem's Language".

This is a first draft of the pattern based on Norvig's discussion. I hope to improve the pattern by adding code for a running example and by broadening it to include other folks' experience with the same idea.

The Pattern

You are writing a program to model behavior in a complex domain. Many different problems can be solved in the domain, but you are faced with one problem in particular.

How do you construct your model?

Often, the simplest approach is to map the problem directly onto constructs in your programming language. Consider Norvig's problem of generating random English sentences. You can take the language grammar and create for each arm a Common Lisp function that generates that part of the grammar.

You are likely to encounter a number of problems when you use this approach:

Therefore, use the most natural notation possible to describe and solve your problem. Then write an interpreter to operate over that notation.

This solution requires more work, since you now have two distinct steps before you reach working code. But the result is programs that are more flexible, easier to modify and extend, and easier to apply to new problems.

For small problems, the extra effort will seem unfruitful. However, ask yourself: are you always certain that the problem or set of applications will remain small over time? I usually am not.

The idea behind this pattern "is to work with the problem as much as possible on its own terms and to minimize the part of the solution that is written directly" in your programming language. [Norvig, Page 42].

If your language grammar is specified inductively, consider using Structural Recursion to implement your interpreter.

External Patterns

Roundabout is a pattern language for recursive programming over inductively-defined data types.


  1. Peter Norvig, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann, San Mateo, California, 1992.

Eugene Wallingford ==== wallingf@cs.uni.edu ==== September 1, 1997