Background

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:

• What happens if your problem formulation changes? You are forced to modify code. For example, you might decide to extend your language grammar to support more diverse phrases. Each addition requires a change to the corresponding program segment.

• What happens if you need to solve another problem using the same grammar? You face writing an entirely new program. The code you wrote for the original problem confounds the language grammar with its use for a particular problem. In writing the new program, you must again model the grammar in new code.

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.

• Now if the problem formulation changes, you need to make modifications only in the code for the formulation. Adding new components to your grammar requires changes only in the grammar, not the interpreter.

• If you need to solve another problem using the same grammar, you can reuse the grammar as is. You need only write a new interpreter or a program that calls the existing interpreter.

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.

References

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