| dc.description.abstract | Logic programming languages are being used extensively in the Fifth Generation Computer Project and in the areas of artificial intelligence, knowledge representation, expert systems and other reasoning systems. One very great advantage of a logic programming language is that it is declarative and hence it is more natural and easy to write programs in such a language.
The control that a logic programming language uses is built-in so that the programmer need not bother about how a problem is solved. Although this feature is a boon to the programmers, the execution of such programs involves a lot of redundancies. This arises due to the high nondeterminism of the logic programming languages. Especially when multiple solutions are required, the whole search space of the search tree is analyzed by a naive PROLOG interpreter.
There are several models proposed in the literature that prune a part of the search tree that is not bound to contain any solution. Such a pruning of the search tree corresponds to the selection of a better backtrack literal. There are methods that can determine better backtrack literals but with very high runtime overheads. There are also methods proposed that have very little runtime overhead but do not always select better backtrack literals.
The aim is to reduce the space and time overheads but at the same time select the best backtrack literal. These two requirements are conflicting and hence a trade-off is to be reached. In this thesis, a scheme called the variable-based scheme has been proposed that has very little space and time overhead, compared to the schemes proposed earlier, and at the same time selects a better backtrack literal. In this scheme, the information provided by the variables is used for selecting the backtrack literal. It has been observed that variables provide more information than the predicates (also called literals). In the variable-based scheme, the information required for selecting the backtrack literal is determined at runtime and hence can easily handle non-ground instantiations also.
A new scheme of redundancy elimination called the data-based scheme has also been proposed that selects a better backtrack literal than any of the earlier schemes. This scheme however requires slightly more overhead than the variable-based scheme. In data-based backtracking, the mutual constraints imposed by one variable on another help in selecting a better backtrack literal. In the worst case, this method will choose the same backtrack literal as chosen by the variable-based scheme. This method depends on the data values associated with the facts of the program and hence the backtrack literal chosen will vary dynamically, depending on these values. Two types of failures, namely the failure due to non-existence and the failure due to constraints, have been identified and the data-based scheme handles both these failures.
An algorithm that takes into account all these redundancy elimination mechanisms has been presented. It has also been shown that all the proposed redundancy elimination mechanisms are complete. The order of reporting solutions also remains the same as that of the conventional PROLOG programs. A basic interpreter that incorporates these schemes has been implemented using LISP.
The advantage of the variable-based scheme is that it can easily handle the extensions required for incorporating the data-based scheme. Further, a lot of redundant processes are created during the AND-parallel execution of logic programs. It has been shown that the variable-based and data-based schemes help in eliminating redundancies that exist in AND-parallel execution models.
When a predicate fails during the process of the execution of a logic program, not all the previous literals need be reconsidered to cure the failure. It is possible to skip some of them and backtrack to a literal evaluated much earlier. In this thesis, such a redundancy elimination has been proposed and called backward redundancy elimination. This has been achieved through a variable-based backtracking scheme.
Another type of redundancy elimination, called forward redundancy elimination, has been identified and a method has been proposed to overcome this type of redundancy. In this type of redundancy elimination, it is not required to re-evaluate all literals that lie between the failed literal and the backtrack literal. This scheme determines the minimal number of literals that need to be re-evaluated after the failure has been rectified. | |
