The inference rules will be embedded in an agenda-based control regime along the line of [Shieber1988]. An agenda consists of a list of tasks and a policy for managing it. A task is simply an item. Whenever an inference rule creates a new item it is added as a new task to the agenda and sorted according to the given priority function PRIO. If the agenda chooses a task as the next item, and this item is not blocked, it is added to the state set. Using the agenda mechanism in this way has the effect that the subsumption operation (performed inside the blocking test) is delayed until an item is explicitly chosen by the agenda control. If our agenda control follows, for example, a depth-first strategy, then only ``useful'' items are considered. In chapter 5 we show the importance of this behaviour for the case of performing self-monitoring and revision during natural language generation.
We will assume the following operations to be defined for agendas:
MAKE-AGENDA() creates a new agenda.
EMPTY-AGENDA-P(Agenda) is true if the specified agenda
is empty.
GET-HIGHEST-PRIO-TASK(Agenda) removes and returns the
task with the highest priority.
ADD-TASK-TO-AGENDA(Tasks,Prio,Agenda) adds new Tasks
with priority Prio to the specified Agenda.
PRIO(Task) determines the priority for the task Task.
The particular agenda that we use is denoted by the global variable Agenda. The control regime denoted as PROCESS will manage the agenda. During the course of PROCESS it dequeues tasks from the agenda until the agenda is empty. However, note that the inference rules force the agenda to add new tasks.
Each dequeued task is added to the table S. This operation is performed by the function ADD-ITEM. However, ADD-ITEM only adds a new item to the table if it is not blocked. In that case the task (that actually has been become a real item) is passed to the procedure APPLY-TASK which applies the inference rules that eventually cause the creation of new tasks.
Figure 4.5: An agenda-based control mechanism.
Figure 4.6: The procedure that adds new items to the table if they are not
blocked.
The procedure PROCESS (see figure 4.5)
receives as input the goal Goal to prove and returns as a result
either rejection or a list of answers (line (1)). It first creates a
start item StartItem using the function MAKE-START-ITEM and adds
it to the Agenda.
Then, while the Agenda is not empty (i.e., there are still tasks
waiting to apply), GET-HIGHEST-PRIO-TASK determines the next task
to process (and removes it from the agenda). If the new CurrentTask is
not blocked by some item already in the table S it is added
to S (this test and operation is performed by the function ADD-ITEM, see figure 4.6).
In that case the new Task is applied on the inference
rules (which is performed by the function APPLY-TASK).
Note that the inference rules called by this procedure
will eventually create new tasks. If the state set contains a new answer
this is added to the Result list.
Figure 4.7: The procedure APPLY-TASK.
The procedure APPLY-TASK (see figure 4.7) applies the inference rules to the task Task (line (1)). If the current task is a passive item (line (2)) PASSIVE-COMPLETION is called (line (3)). Otherwise (line (4)) it is checked whether ACTIVE-COMPLETION returns true, which means that new items have been added to the agenda. If this is not the case PREDICTION and SCANNING are called. The reason why we only consider prediction and scanning if active-completion returns false (i.e., creates no new task) is that if active-completion is successful this means that for the selected element of the current active item there already exists a derived phrase (made for the same substring or partial semantics) and hence, prediction and scanning would be redundant.