Class TailRecursivePredicateMetaData

java.lang.Object
org.projog.core.predicate.udp.TailRecursivePredicateMetaData
public final class TailRecursivePredicateMetaData extends Object
Defines the characteristics of a tail recursive user defined predicate.

Projog uses the following rules to determine if a user defined predicate is "tail recursive" (and therefore suitable for tail recursion optimisation using a TailRecursivePredicate):

  • The user defined predicate must consist of exactly 2 rules.
  • It must be possible to detect, at the point that the user defined predicate is defined, that the antecedent of the first rule will never generate multiple solutions per-query.
  • If the antecedent of the second rule is not a conjunction, it must be a call to itself (i.e. the user defined predicate being defined) - this is what makes the predicate recursive.
  • If the antecedent of the second rule is a conjunction, the final element (i.e. the tail) of the conjunction must be a call to itself (i.e. the user defined predicate being defined) - this is what makes the predicate recursive. It must be possible to detect, at the point that the user defined predicate is defined, that all elements prior to the final element of the conjunction will never generate multiple solutions per-query.

Examples of tail recursive predicates suitable for tail recursion optimisation: 

:- list([]).
list([X|Xs]) :- list(Xs).

r(N).
r(N) :- N > 1, N1 is N-1, r(N1).

writeAndRepeat(N) :- write(N), nl.
writeAndRepeat(N) :- N > 1, N1 is N-1, writeAndRepeat(N1).
See Also:

  • Field Details

    • firstClause

      private final ClauseModel firstClause

    • secondClause

      private final ClauseModel secondClause

    • isPotentialSingleResult

      private final boolean isPotentialSingleResult

    • isTailRecursiveArgument

      private final boolean[] isTailRecursiveArgument

    • isSingleResultIfArgumentImmutable

      private final boolean[] isSingleResultIfArgumentImmutable

  • Constructor Details

  • Method Details

    • create

      public static TailRecursivePredicateMetaData create(KnowledgeBase kb, List<ClauseModel> clauses)
      Returns a new TailRecursivePredicateMetaData representing the user defined predicate defined by the specified clauses or null if the predicate is not tail recursive.
      Parameters:
      clauses - the clauses that the user defined predicate consists of
      Returns:
      a new TailRecursivePredicateMetaData or null if the predicate is not tail recursive

    • isTailRecursive

      private static boolean isTailRecursive(KnowledgeBase kb, List<ClauseModel> terms)

    • isAntecedentRecursive

      private static boolean isAntecedentRecursive(KnowledgeBase kb, ClauseModel secondTerm)

    • isTail

      private static boolean isTail(Term list, Term term)

    • getFinalFunction

      private Term getFinalFunction(Term t)

    • getFirstClause

      public ClauseModel getFirstClause()

    • getSecondClause

      public ClauseModel getSecondClause()

    • isPotentialSingleResult

      public boolean isPotentialSingleResult()

    • isTailRecursiveArgument

      public boolean isTailRecursiveArgument(int idx)

    • isSingleResultIfArgumentImmutable

      public boolean isSingleResultIfArgumentImmutable(int idx)