A thesis submitted in partial fulfillment of the requirement for the degree of Master of Engineering, School of Engineering and Technology

Thesis (M.Eng.) - Asian Institute of Technology,1988

Keyr-1ords: Prolog, Naive .Interpreter, History-based Interpreter, Depth First Search, Cause of Fai1ure, SLD Tree, AND/OR Tree, Intelligent Backtracking, Data- Dependency Analysis, Execution History. In t his thesis , a History - Based backtracking (HBB ) interpreter for Prolog is developed and evaluated. Based on an analysis the causes o[ failures, the causes are stored in the history and are used to avoid repeating the same failures . Four basic rules for t he scheme have been derived and justified in the thesis. Two interpreters, a conventional and t he other based on the scheme proposed for a Prolog dialect are implemented using Turbo Pas ca l (version 4 ) . The scheme requires an analysis to determine for each failure , t h e cause of t h e failure. A history of the causes leading to failures is maintained and used to avoid repeating these failures. Th ese interpreters are used to compare and evaluate the proposed scheme with respect to the naïve interpreter and the schemes based on intelligent backtracking. We conclude t hat the proposed scheme is better than those based on data dependency analysis and is easier to implement t h an the in Telligent backtracking schemes.