A new intelligent backtracking scheme for Prolog: a summary of results

The authors show both analytically and statistically that intelligent backtracking based on a form of unification analysis can conveniently be incorporated into the standard stack-based implementations of sequential Prolog, while the incurred overhead is comparable to that based on the data-dependency analysis approach. They implement the scheme by modifying the Waterloo Prolog system and obtained performance results on some benchmark programs. These results suggest that intelligent backtracking may profitably be considered as a standard component in future implementations of sequential Prolog systems