Memo relations

The head-driven generator, defined here as a $\cal {R}$($\cal {L}$) 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.

Figure 3.11: A possible implementation of memo-relations in Prolog.

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

In figure 3.11 a possible implementation of memo-relations is defined in Prolog.

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.