Specialisation

From Version 1.4.0 on, the XSB compiler automatically performs specialisation of partially instantiated calls. Specialisation can be thought as a source-level program transformation of a program to a residual program in which partially instantiated calls to predicates in the original program are replaced with calls to specialised versions of these predicates. The expectation from this process is that the calls in the residual program can be executed more efficiently that their non-specialised counterparts. This expectation is justified mainly because of the following two basic properties of the specialisation algorithm:

Compile-time Clause Selection

The specialised calls of the residual program directly select (at compile time) a subset containing only the clauses that the corresponding calls of the original program would otherwise have to examine during their execution (at run time). By doing so, laying down unnecessary choice points is at least partly avoided, and so is the need to select clauses through some sort of indexing.

Factoring of Common Subterms

Non-variable subterms of partially instantiated calls that are common with subterms in the heads of the selected clauses are factored out from these terms during the specialisation process. As a result, some head unification ( get_* or unify_*) and some argument register ( put_*) WAM instructions of the original program become unnecessary. These instructions are eliminated from both the specialised calls as well as from the specialised versions of the predicates.

Though these properties are sufficient to get the idea behind specialisation, the actual specialisation performed by the XSB compiler can be better understood by the following example. The example shows the specialisation of a predicate that checks if a list of HiLog terms is ordered:

ordered([]). ordered([X]). ordered([X,Y|Z]) :- X @=< Y, ordered([Y|Z]).

$\longrightarrow$

ordered([]). ordered([X]). ordered([X,Y|Z]) :- X @=< Y, _$ordered(Y, Z). :- index _$ordered/2-2. _$ordered(X, []). _$ordered(X, [Y|Z]) :- X @=< Y, _$ordered(Y, Z).

The transformation (driven by the partially instantiated call ordered([Y|Z])) effectively allows predicate ordered/2 to be completely deterministic (when used with a proper list as its argument), and to not use any unnecessary heap-space for its execution. We note that appropriate :- index directives are automatically generated by the XSB compiler for all specialised versions of predicates.

The default specialisation of partially instantiated calls is without any folding of the clauses that the calls select. Using the spec_repr compiler option (see Section 3.8.2) specialisation with replacement of the selected clauses with the representative of these clauses is performed. Using this compiler option, predicate ordered/2 above would be specialised as follows:

ordered([]).
ordered([X|Y]) :- _$ordered(X, Y).

:- index _$ordered/2-2.
_$ordered(X, []).
_$ordered(X, [Y|Z]) :- X @=< Y, _$ordered(Y, Z).

We note that in the presense of cuts or side-effects, the code replacement operation is not always sound, i.e. there are cases when the original and the residual program are not computationally equivalent (with respect to the answer substitution semantics). The compiler checks for sufficient (but not necessary) conditions that guarantee computational equivalence, and if these conditions are not met, specialisation is not performed for the violating calls.

The XSB compiler prints out messages whenever it specialises calls to some predicate. For example, while compiling a file containing predicate ordered/1 above, the compiler would print out the following message:

% Specialising partially instantiated calls to ordered/1

The user may examine the result of the specialisation transformation by using the spec_dump compiler option (see Section 3.8.2).

Finally, we have to mention that for technical reasons beyond the scope of this document, specialisation cannot be transparent to the user; predicates created by the transformation do appear during tracing.