Abstract Interpretation of Prolog programs
: Optimizations of an implementation

Student thesis: Master typesMaster in Computer science


Abstract interpretation of Prolog programs is a technique for static analysis of these programs that is achieved in order to improve Prolog compilers. But this technique is arduous, it consumes a lot of time and a lot of memory. On the basis of an original abstract interpretation program that requires at least a workstation, we have implemented several optimizations among which two especially retain our attention. The first one is based on a thorough examination of the execution of the algorithm. The second one is more general, it aims at caching the longest repetitive operations. These optimizations allow a considerable gain of execution time and of memory space and make possible to run the program on a personal computer. Finally, two other techniques, one based on the detection of strictly increasing structures, the other based on the reexecution of some goals, also allow to obtain more accurate results. This report develop all these optimizations and discuss the results on two different domains, with a series of test programs.
Date of Award1992
Original languageEnglish
Awarding Institution
  • University of Namur
SupervisorBaudouin LE CHARLIER (Supervisor)

Cite this