Optimization Techniques

When a defined predicate is invoked the interpreter tries to find a matching clause and then invokes the body of the clause. Normally the interpreter creates a choice point. The choice point is used during backtracking to search for further matching clauses. Choice point elimination optimization refers to the ability of the interpreter to eliminate choice points when it seems clear that no further clauses will match. This is either the case when the last clause has been reached or when a cut has been performed.

From the ISO standard it is indicated to implement the cut via its own choice-point. So that upon back-tracking the cut choice-point will remove all previous choice-points in the scope of the current clause and then fail. Choice-point elimination also refers to the early elimination of choice-points by the cut. The cut then does then not need to create a choice-point on its own and it can deterministically succeed.

The omission of choice points is also possible for system and custom built-ins. A system built-in has full control of the interpreter environment and can voluntarily eliminate choice points. Inside the Prolog API there exists a protocol so that custom built-ins in the form of Java foreign predicates can also omit choice points. The Java method has simply not to set the retry flag upon succeeding and the invocation choice point will be discontinued.

Finally we have implemented optimization techniques that are based on an appropriate generation of an intermediate form for each clause. These techniques can attack the parent stack frame, the body or the head:

The following Prolog flags for the optimization techniques are provided:

sys_choice_point:
Legal values are on and off. The flag indicates whether choice point elimination is enabled for the knowledge base. Default value is on. Value can be changed.
sys_body_variable:
Legal values are on and off. The flag is per knowledge base and is inherited when predicates are created. Default value is on. The value can be changed.
sys_stack_frame:
Legal values are on and off. The flag is per knowledge base and is inherited when predicates are created. Default value is on. The value can be changed.
sys_head_variable:
Legal values are on and off. The flag is per knowledge base and is inherited when predicates are created. Default value is on. The value can be changed.

The following Predicate properties for the optimization techniques are provided:

sys_nobody:
The property indicates that the clauses of the predicate should not have body variable elimination optimization in place. The value can be changed.
sys_nostack:
The property indicates that the clauses of the predicate should not have stack frame elimination optimization in place. The value can be changed.
sys_nohead:
The property indicates that the clauses of the predicate should not have head variable elimination optimization in place. The value can be changed.


Comments