Benchmark Programs

This section shows the benchmark programs considered in the experiments and the kind of manipulations performed on them.

We have instrumented the Prolog code obtained from the compilation of the following small Curry program into Prolog using the compiler curry2prolog of PAKCS [2].

   data natural = zero | succ natural

   data abc = a | b | c

   geq zero zero         = True
   geq (succ _) zero     = True
   geq zero (succ _)     = False
   geq (succ x) (succ y) = geq x y

   f a a = a

   g a   = a
   g b   = b

After dropping the clauses of the Curry prelude, and by simplifying some notational conventions used by the compiler, we get the following final code (used in our experiments):

   %% Some auxiliary predicates:

   % to build natural numbers:
   built_nat(0, zero) :- !.
   built_nat(I, succ(N)) :- NextI is I - 1, built_nat(NextI, N).

   % to build nested terms:
   built_f(0, A) :- !.
   built_f(I, f(f(g(B), N), a)) :- NextI is I - 1, built_f(NextI, N).

   % to build nested terms (2):
   built_imf(0, A) :- !.
   built_imf(I, imf(imf(g(B), N), a)) :- NextI is I - 1, built_imf(NextI, N).

   %% Function 'geq':
   geq(A,B,C) :- hnf(A,F), geq_1(F,B,C).

   geq_1(zero,A,B) :- hnf(A,E), geq_1_zero_1(E,B).
   geq_1_zero_1(zero,'True').
   geq_1_zero_1(succ(_),'False').

   geq_1(succ(A),B,C) :- hnf(B,F), geq_1_succ_2(F,A,C).
   geq_1_succ_2(zero,_,'True').
   geq_1_succ_2(succ(A),B,C) :- geq(B,A,C).

   %% Improved function 'geq':
   imgeq(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).

   %% Function 'f':
   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).

   %% Improved function 'f':
   imf(A,B,C) :- hnf(A,F), hnf(B,G), imf_1(F,G,C).
   imf_1(a,a,a).

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

   %% Predicate hnf (head normal form):
   hnf(A,B) :- var(A), !, B=A.
   hnf(geq(A,B),C) :- !, geq(A,B,C).
   hnf(imgeq(A,B),C) :- !, imgeq(A,B,C).
   hnf(f(A,B),C) :- !, f(A,B,C).
   hnf(imf(A,B),C) :- !, imf(A,B,C).
   hnf(g(A),B) :- !, g(A,B).
   hnf(A,A).

   %% Predicate nf (normal form):
   nf(A,B) :- hnf(A,E), nf_hnf(E,B).

   nf_hnf(A,B) :- var(A), !, B=A.
   nf_hnf('True','True') :- !.
   nf_hnf('False','False') :- !.
   nf_hnf(zero,zero) :- !.
   nf_hnf(succ(A),succ(B)) :- !, nf(A,B).
   nf_hnf(a,a) :- !.
   nf_hnf(b,b) :- !.
   nf_hnf(c,c) :- !.

   %% Goals considered in the experiments:
   
   g1 :- write('goal 1:'), nl,
         built_nat(100000, N1), built_nat(99999, N2),
         T1 is cputime, nf(geq(N2, N1), _),
         T2 is cputime, T is T2 - T1,
         write('Curry: '), write(T), TT1 is cputime,
         nf(imgeq(N2, N1), _), TT2 is cputime, TT is TT2 - TT1,
         write('   Improved: '), write(TT),
         write('   Speedup: '), Sup is (T / TT), write(Sup),
         nl.

   g2 :- write('goal 2:'), nl,
         built_f(5000, F), built_imf(5000, IF),
         T1 is cputime, nf(F, _),
         T2 is cputime, T is T2 - T1,
         write('Curry: '), write(T), TT1 is cputime,
         nf(IF, _), TT2 is cputime, TT is TT2 - TT1,
         write('   Improved: '), write(TT),
         write('   Speedup: '), Sup is (T / TT), write(Sup),
         nl.

The code associated with predicates ``imgeq'' and ``imf'' have been introduced by hand.