Next: New Models
Up: Sequential Efficiency
Previous: Sequential Efficiency
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
Next: New Models
Up: Sequential Efficiency
Previous: Sequential Efficiency
'Enrico
Tue Mar 19 14:37:09 MST 1996