The head-driven generator, defined here as a
() meta-interpreter,
uses the depth-first backtrack search strategy described in
section 2.3. The motivation of the head-driven generation
strategy lies in the *reduction* of the search space that is
obtained. How to search this reduced search space is quite an
independent matter. Therefore, it may be useful to investigate
alternative search strategies. For example, the algorithm could be
defined using a chart, as for example proposed in
[12,24].

Another, related, possibility consists of the implementation of so-called `memo-relations' (also called `well-formed sub-string tables' in the context of parsing). The idea is that, to prove some goal Goal, we first check whether such a goal has already been proven before. In that case we pick up the results of that previous call. If the goal has not been tried before, we will go about finding all solutions to this goal (and assert each of them in the database). If no more solutions can be found, then we assert that all solutions for that goal have been found, and we pick up a possible solution. This in effect turns the search strategy into a breadth-first one.

memo(Goal):- copy_term(Goal,Frozen), % make copy of goal numbervars(Frozen,0,_), % and numbervar it memo(Goal,Frozen). % for subsumption checks later memo(Goal,Frozen) :- done(Frozen), % more general goal is known !, item(Frozen,_,Goal). % get result w.r.t. goal memo(Goal,Frozen) :- copy_term(Goal,Result), % copy such that goal does not change retractall(item(_,Goal,_), % retract more specific goals call(Result), % find a result assertz(item(Goal,Frozen,Result)), % assert it fail. % fail to find other results memo(Goal,Frozen) :- assertz(done(Goal)), % assert that goal is known now item(Frozen,_,Goal). % get result w.r.t. goal |

The predicate `memo(Goal)` searches
for `Goal` using a tabular breadth-first search technique.
Results are asserted as `item(Goal,FrozenGoal,Result)` where
`FrozenGoal` is a numbervarred copy of `Goal` for later
subsumption checks. Goals are asserted as `done(Goal)`. Such a
goal is only asserted once all solutions are found. Hence, the resulting
program has the same termination properties. As a further
improvement of this technique a user-provided definition of what
constitutes the real `goal' information of a given goal might be
investigated. This would e.g. provide a hook for Shieber's
restriction technique. Furthermore, this would allow for the incorporation
of more complex constraints for which subsumption checking would not be
possible.

This implementation improves upon the one discussed in [55,64] in that the implementation is much more general (not restricted to parsing), and that results are indexed with respect to the goal which produces that result. This implies that subsumption checks are limited to goals, and no subsumption checks on full results is necessary. Clearly, goals are (much) `smaller' than results in practice, and hence the costs of overhead is reduced. It should be stressed, though, that in the case of constraint-based grammars it is clear that such memo-relations do not improve on the worst-case behavior of the program (as there generally is an unbounded number of possible categories), and maybe not even on the practical behavior of the program (because of the overhead involved in copying and subsumption checking).

Even though the overhead involved in the implementation of such memo-relations is still considerable, it turns out that for many grammars the head-driven generator is more efficient if implemented as a memo-relation, along the lines of figure 3.11. For example this technique has been used in order to improve upon the efficiency of the head-driven generation algorithm by a factor 4 for typical grammars.

1998-09-30