Experiments

Consider the program example in Section 1. The curry2prolog compiler of PAKCS [2] produces the following set of rules (clauses), as a result of the compilation of the original program (written in Curry - see next section):

    f(A,B,C) :- hnf(A,F), f_1(F,B,C).
    f_1(a,A,B) :- hnf(A,E), f_1_a_1(E,B).
    f_1_a_1(a,a).

    g(A,B) :- hnf(A,E), g_1(E,B).
    g_1(a,a).
    g_1(b,b).

Now, f(A,B,C) is a predicate where A and B are input arguments and C is an output argument which returns the result of a computation, and there is a close correspondence with the previous simple uniform program. This means that the left-to-right selection strategy of Prolog exploits the inductive positions of $f$ in the same order as in the execution of the simple uniform program under uniform lazy narrowing (see the definition of the predicate hnf in Section 3).

The equivalence between needed narrowing and uniform lazy narrowing suggests the following improvement in the implementations of needed narrowing, where the original program is compiled into a ``uniform-like'' set of clauses which are run in the Prolog implementation also. Now, the rule defining the function $f$ in the program of Section 1 can be compiled into the following set of Prolog clauses:

    imf(A,B,C) :- hnf(A,F),hnf(B,G),imf_1(F,G,C).
    imf_1(a,a,a).

Let us notice that uniform clauses may require an extra pattern-matching effort, in comparison with the corresponding simple uniform rules. In a experimental evaluation of the method, we have measured a speedup of $1.29$ w.r.t. the performance of the simple uniform rules, when we execute sufficiently big (nested) terms (see Section 3). Here speedups are the ratio between the execution of the Prolog program obtained by the curry2prolog compiler of PAKCS, and the runtimes, for the same input term, of the ``uniform-like'' set of clauses. Our figures are the average of 10 executions. Runtimes were measured on a Compaq Armada 6500 machine, with a 300 MHz Pentium II processor, running under Linux v7.1 and SWI-Prolog v3.2.9-1. As the complexity of definitional trees grows, the improvements brought by the proposed optimization also increase, as we show in our last example: Given the uniform program

$$\begin{array}{ll} R_1: geq(0,0) \to true &    R_3: geq(0,s(... ...),0) \to true &    R_4: geq(s(X),s(Y)) \to geq(X,Y) \end{array}$$

Section 3 shows the set of Prolog clauses which result from the translation of the original (Curry) program by the curry2prolog compiler of PAKCS, as well as the optimized code for this program:

vobeyspacesimgeq(A,B,C):-hnf(A,F), hnf(B,G), imgeq_1(F,G,C). imgeq_1(zero,zero,'True'). imgeq_1(zero,succ(_),'False'). imgeq_1(succ(_),zero,'True'). imgeq_1(succ(A),succ(B),C):- imgeq(A,B,C).

For this last example and input term $geq(s^{100000}(0),s^{99999}(0))$, we obtain a speedup of $1.67$.