Compile-time Analysis

Most of the complexity of executing Prolog programs comes from the lack of a-priori knowledge regarding the development of the execution. This forces the engine to either

• make conservative choices; or
• introduce additional run-time checks to guarantee safe execution and direct the computation in the correct direction.

For example, during compilation, the lack of knowledge regarding the instantiation state of the arguments of a subgoal obliges the compiler to generate code capable of handling all the different situations (e.g., arguments are unbound variables, arguments are ground terms, etc.). The selection of the proper sequence of instructions will be done at run-time--with the cost of checking the status of each argument.

A great deal of improvement could be obtained by increasing the amount of knowledge available during program compilation. This knowledge can be either supplied by the programmer, through declarations and pragmas in the source code (e.g. Mercury [122]), or automatically extracted using abstract interpretation and other compile-time techniques [22, 77, 12].

The natural question at this point is the following: ``which kind of information are useful to improve program compilation and execution ?'' A wide variety of information may actually turn out to be useful during program translation, but the main sources of improvement may be represented by having a good knowledge about the following features of the execution:

• Types: Prolog, as most of the other logic languages proposed, is a typeless language. It is based on a single-sort language--there is virtually no distinction between different classes of terms. The lack of types makes the language more elegant and more clear from the semantical point of view, it represents a considerable source of inefficiency at the implementation level. The term representation inside the abstract machine needs to explicitly maintain type information (to support type-checking, memory management, etc.)--actual values need to be ``boxed'' with the type information. During execution values cannot be directly used, but they first need to be unboxed, and the eventual type checks performed. Knowledge about the type of the terms used in every point of the execution would allows various improvements, like avoidance of the boxing of terms, removal of run-time type checking and improved clause indexing. Various systems make use of type information (either collected through compile-time analysis [90, 107, 25] or supplied by the programmer [61, 122]) to improve execution.
• Modes: in general terms, a mode of a predicate indicates how its arguments will be instantiated when that predicate is called. More formally, the mode of a predicate is a mapping from the initial state of instantiation of its arguments to their final state of instantiation. Given a tree representing a type, an instantiation tree is obtained by associating a value of instantiatedness (either free or bound) to each or-node of the tree. This annotated tree (called instantiatedness tree in [122]) tells which variables are bound and which are not. A mode is a mapping between instantiatedness trees.

  Knowledge of modes allows considerable optimizations during execution, like improved clause selection, transformation of unification to matching, and detection of producer/consumer relationships.

• Determinism: considering a given mode for a predicate, determinism knowledge is used to categorize the mode according to the number of solutions that can be returned by the predicate when called with such mode. The traditional classification distinguishes determinate--i.e., producing at most one solution--and nondeterminate modes--i.e., which may produce more than one solution. A subgoal which is known to be determinate can be executed very efficiently--it does not require any additional support with respect to execution of imperative programs. Furthermore, knowledge of determinacy allows many optimization of the execution (e.g., it could be feasible to reuse determinate subgoals on backtracking, instead of recomputing them each time). Certain systems go to the extent of adopting different execution algorithms depending on the nature of the subgoal to be executed (e.g., Mercury distinguishes four levels in the categorization based on determinacy, with three different execution schemes).

  
  

  
  

  Web Tour

  
  
  • Abstract Interpretation Bibliography
  • CLIP Papers Repository
  • Aquarius Prolog