Examples

Table modes are useful for the declarative description of dynamic programming problems [6,20]. The following program encodes the Dijkstra's algorithm, which is for finding the minimum-weight path between a pair of nodes.

      :-table sp(+,+,-,min).
      sp(X,Y,[(X,Y)],W) :-
          edge(X,Y,W).
      sp(X,Y,[(X,Z)|Path],W) :-
          edge(X,Z,W1),
          sp(Z,Y,Path,W2),
          W is W1+W2.

The predicate edge(X,Y,W) defines a given weighted directed graph, where W is the weight of the edge from node X to node Y. The predicate sp(X,Y,Path,W) states that Path is a path from X to Y with the smallest weight W. Note that, whenever the predicate sp/4 is called, the first two arguments are always instantiated. Therefore, only one answer is tabled for each pair.

Note that, if table modes are not respected, or if there is no bound for an optimized argument, a program may give unexpected answers. For example, if the weights of some edges are negative, then there will be no lower bound for the optimized argument; hence, the program will never stop.

Consider a variant of the problem, where the goal is to find a shortest path among the paths that have the minimum weight for each pair of nodes. The following gives a program:

      :-table sp(+,+,-,min).
      sp(X,Y,[(X,Y)],(W,1)) :-
          edge(X,Y,W).
      sp(X,Y,[(X,Z)|Path],(W,Len)) :-
          edge(X,Z,W1),
          sp(Z,Y,Path,(W2,Len1)),
          Len is Len1+1,
          W is W1+W2.

Since only one argument can be optimized, a compound term, (W,Len), is used in order to denote the optimized value, where W is the weight of a path, and Len is the length of the path. Note that the order is important. If the term would be (Len,W), the program would find a shortest path, breaking ties by selecting a path that has the minimum weight.

The cardinality limit of a tabled predicate can be dynamically changed by using the built-in table_cardinality_limit.

• table_cardinality_limit(p/n,C): If C is a variable, it is bound to the current cardinality limit for p/n. If C is a positive integer, the cardinality limit for p/n is changed to C.

• table_cardinality_limit(p,n,C): This is the same as table_cardinality_limit(p/n,C), except that the functor and the arity are given as two separate arguments.