Next: Indexing in RELFUN Up: Future Extensions Previous: Assert

Compiling Higher Order PROLOG Extensions

In [Bol90] Harold Boley described how to reduce higher-order RELFUN clauses to constant-operator clauses.

The second-order characteristics of the constant-operator fact


is dependent on ancestor's use as a first-order relation:

   Rel(A,C) :- transitive(Rel), Rel(A,B), Rel(B,C).

Higher-order procedures like this cannot be directly compiled into the WAM, but a simple transformation of all clause heads and goals allows compilation:

For the above example, this transformation results in

   ap(transitive, ancestor).
   ap(Rel,A,C) :- ap(transitive,Rel), ap(Rel,A,B), ap(Rel,B,C).

With the standard PROLOG indexing, a significant loss of efficiency results because indexing on only the first argument selects the clauses just by their procedure name but does not look at their (real) arguments. The MN- and MV-Algorithms overcome this problem by looking at all arguments (see section 11.2).

Michael Sintek -