Package org.projog.core.predicate.udp

Class TailRecursivePredicate

  • All Implemented Interfaces:
    Predicate
    Direct Known Subclasses:
    InterpretedTailRecursivePredicate
    public abstract class TailRecursivePredicate
extends java.lang.Object
implements Predicate
    A template for implementations of Predicate that are tail recursive.

    It is common for Prolog developers to define predicates using recursion. Although recursive programs can be concise and elegant they do require increased stack space for each iteration - which after many iterations will cause a java.lang.StackOverflowError. Where it can determine it is safe to do, Projog converts recursive user defined predicates into iterative versions - requiring a constant stack space regardless of the number of iterations. This technique is known as tail recursion optimisation or last call optimisation. The algorithm for implementing tail recursion optimisation is encapsulated in TailRecursivePredicate. Subclasses of TailRecursivePredicate can implement the logic of evaluating the clauses of a specific user defined predicate without having to redefine the tail recursion optimisation algorithm.

    For a user defined predicate to be implemented using TailRecursivePredicate it must be judged as eligible for tail recursion optimisation using the criteria used by TailRecursivePredicateMetaData.

    See Also:
    TailRecursivePredicateMetaData

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected abstract void backtrack()
      Backtracks the arguments to before the last attempt to match the first rule.
      boolean evaluate()
      Attempts to satisfy the goal this instance represents.
      protected abstract void logCall()  
      protected abstract void logExit()  
      protected abstract void logFail()  
      protected abstract void logRedo()  
      protected abstract boolean matchFirstRule()
      Match the first rule of the tail recursive predicate.
      protected abstract boolean matchSecondRule()
      Match the second rule of the tail recursive predicate.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • retrying

        private boolean retrying

      • succeededOnPreviousGo

        private boolean succeededOnPreviousGo

    • Constructor Detail

      • TailRecursivePredicate

        public TailRecursivePredicate()

    • Method Detail

      • evaluate

        public final boolean evaluate()
        Description copied from interface: Predicate
        Attempts to satisfy the goal this instance represents.

        Calling this method multiple times on a single instance allows all possible answers to be identified. An attempt to find a solution carries on from where the last successful call finished.

        If PredicateFactory.isRetryable() returns false then this method should only be called once per individual query (no attempt should be made to find alternative solutions).

        If PredicateFactory.isRetryable() returns true then, in order to find all possible solutions for an individual query, this method should be recalled on backtracking until it returns false.

        Specified by:
        evaluate in interface Predicate
        Returns:
        true if it was possible to satisfy the clause, false otherwise
        See Also:
        PredicateFactory.getPredicate(Term[])

      • matchFirstRule

        protected abstract boolean matchFirstRule()
        Match the first rule of the tail recursive predicate.

        If the head of the first rule is matched then the rule has been successfully evaluated.

        Returns:
        true if the first rule is matched, else false

      • matchSecondRule

        protected abstract boolean matchSecondRule()
        Match the second rule of the tail recursive predicate.

        If the second rule is matched then the attempt at evaluating the rule continues for another level of recursion.

        Returns:
        true if the second rule is matched, else false

      • backtrack

        protected abstract void backtrack()
        Backtracks the arguments to before the last attempt to match the first rule.

      • logCall

        protected abstract void logCall()

      • logRedo

        protected abstract void logRedo()

      • logExit

        protected abstract void logExit()

      • logFail

        protected abstract void logFail()