3.4.5 Grade modifiers for minimal model tabling

Mercury supports several forms of tabling, most of which must be explicit enabled for each procedure that are intended to apply to (see Tabled evaluation in The Mercury language Reference Manual). (Recall that a procedure is one mode of a predicate or function.) Tabling operates by recording (in a table, hence the name), for each vector of input values to a procedure, the set of vectors of output values the procedure returns as results. (For det code, the set will contain exactly one vector; for semidet code, the set will contain at most one vector.) For later calls to a tabled procedure, the Mercury implementation will automatically check whether the current vector of values of the input arguments has occurred before. If it has, it will return the recorded set of answers. If it has not, it will compute the result or results, and record it or them.

This system has a problem if the tabled procedure calls itself recursively, either directly or indirectly, with the exact same vector of input values, before its initial invocation has completed, because in that case, there will be an entry recording the input vector, but the corresponding set of output value vectors will not yet be available. With the most frequently used form of tabling, i.e. memoization, this is a fatal error, and the Mercury implementation will automatically abort the program. However, for nondet predicates, there is a way to avoid this abort, at the cost of a much more complicated execution model.

This solution gets its name, minimal model tabling, from the fact that it is intended to return, for each query, all the answers that match that query in a specific minimal model of the program, named the perfect model. (We call it “minimal model tabling” instead of “perfect model tabling” because the former is the standard terminology for this kind of tabling in the logic programming literature.)

Minimal model tabling consists of

• recording that state of the computation at the point of the recursive call;
• continuing execution as if the call failed;
• when the top-level call to the procedure with the given vector of input argument values finds a new solution, restoring the recorded state of the computation, and restarting its execution, but this time behaving as if the recursive call just returned the new solution.
• This restarted execution may obviously return even more solutions, which have to be fed back to the recursive call (or in the general, the recursive calls, plural). The process ends when all restarted calls lead either to no solution, or to solutions that have all previously been not just recorded, but also fed back to all recursive call sites.

The execution mechanisms required for this are quite complicated, and impose significant overheads in both time and space, even on the parts of the program that do not benefit from it. This is why in the absence of the following grade modifiers, the Mercury compiler generates executables that do not support minimal model tabling.

.mm

Compiling programs in a grade that includes the .mm grade modifier generates executables that support minimal model tabling.

This grade modifier is compatible only with LLDS base grades.

.mmsc

The grade modifier ‘.mmsc’ is a synonym for ‘.mm’, standing for “minimal model via stack copying”, since the standard implementation works by copying parts of the stack. The synonym exists because Mercury also has another implementation of minimal model tabling. This other implementation, which is incomplete and was only ever useful for experiments, is based on a completely different implementation technique.