Sample Selection

from Chapter 13

Production Systems with Python

13.1 Overview

In this chapter we further develop Python programming methodology, and at the same time, we examine conceptual tools for designing AI systems. The previous chapter presented the main features and functions of Python. However, in order to solve interesting problems, we need to be able to write Python programs that are more complicated than those we have seen so far. This chapter begins by describing \production systems," which provide a scheme for structuring AI programs. We then develop several Python examples to illustrate the implementation of production systems.

13.2 Production System Methodology

13.2.1 Modularity Revisited

If a computer program is at all complex, it should be built up out of relatively small and understandable parts (modules). This necessity for simplicity and clarity becomes a challenging problem as the size of a program grows. One way to combat the problem is to adopt a simple structure for the entire program, called a \production system." A production system consists of a collection of condition-action pairs called production rules, together with a database of \state information" and a procedure for invoking the production rules. The overall structure of a production system is shown in Figure 13.1.

Each production rule is much like an if statement. It contains a condition that must be satisfied before the action part is performed. In fact, we will often implement our production rules as actual if statements. The database of state information is just a collection of information tested and acted on by the production rules. In Python the database may consist of a list of variables (atoms), their values, and their properties. The invoking procedure is often just a program loop that repeatedly tests the conditions of production rules and executes their actions when satisfied.

A simple example of a production system is now described. The job accomplished by the system is to take an integer x and produce its Roman numeral representation.

Production rules:

(a) If x is null, then prompt the user and read x.
(b) If x is not null and is bigger than 39, then print \too big" and make x null.
(c) If x is not null and is between 10 and 39, then print \X" and reduce x by 10.
(d) If x is not null and is equal to 9, then print \IX" and reduce x to 0.
(e) If x is not null and is between 5 and 8, then print \V" and reduce x by 5.
(f) If x is not null and is equal to 4, then print \IV" and reduce x to 0.
(g) If x is not null and is between 1 and 3, then print \I" and reduce x by 1.
(h) If x is not null and is equal to 0, then print an end-of-line and make x null.

Database: The value of the sole variable x.
Control scheme: Test conditions in an arbitrary order until one is true;

execute corresponding action; repeat indefinitely.

The control scheme here works by having an interpreter scan through a list of the production rules. The rules may be in the order given or any other order. The condition part of each rule is tested in turn, until one of the conditions is found to be true. When one is true, we say that the production rule \fires" or \triggers." Then, the action for that rule is executed by the interpreting procedure. For example, if x has the value 7, then production rule e above would fire and cause the action

print \V" and reduce x by 5 to be performed. After the action is taken, the interpreting procedure starts testing production-rule conditions once again. This process is repeated indefinitely (i.e., forever or until the interpreter is turned off).

An alternative to the indefinite repetition scheme could be to repeat until either no conditions are true any more or an action is taken that explicitly halts the interpreter. However, the particular set of production rules might not allow halting anyway.

The program ROMAN1 is a straightforward (though not the most efficient) implementation of this production system. Here is the Python program ROMAN1:

# Roman1.py
def Roman1():
  """Roman numeral conversion with unordered
      Production System"""
  x = ''; ans = ''
  while True:
     if x=='': x = input('Enter number: ')
     elif x!='' and x > 39:
           print 'too big'; x = ''
     elif x!='' and x < 40 and x > 9:
           ans += 'X'; x -= 10
     elif x!='' and x == 9:
           ans += 'IX'; x = 0
     elif x!='' and x < 9 and x > 4:
           ans += 'V'; x -= 5
     elif x!='' and x == 4:
           ans += 'IV'; x = 0
     elif x!='' and x < 4 and x > 0:
           ans += 'I'; x -= 1
     elif x!='' and x == 0:
           print ans; x = ''; ans = ''
     else: print 'bad number'; break

Thus Roman1 is defined as a function of no arguments (it gets its inputs throughthe action of one of the production rules { rule a). The body of Roman1 contains a loop that provides a straightforward implementation of the control scheme.

There two local variables x and ans that are used to hold all the state information for this simple production system. The portion of the procedure for testing conditions and executing actions is implemented in Roman1 as a series of if and elif forms. Each production rule is represented as one of these. (There are other ways to represent production rules in Python; one alternative is used near the end of this chapter in the LEIBNIZ program.) The production rules are examined in a fixed order here: the order in which they appear in the program.

Purchase, Product Descriptions, Author Bios, Table of Contents