🚀 go-pugleaf

                       A Proposal for
         ***********************************************
         *** BENCHMARK PROGRAMS FOR PROLOG SYSTEMS   ***
         ***********************************************
                       Part 3 (of 3)

2. Small Prolog programs.

2.1 Introduction.

Here we deal with prolog programs that do something, while
being still small but representative of some well-known prolog
computations. This set should be augmented by other programs,
some of them might come from your ideas.

Some  of  the  following  programs  were taken from the Berkeley
paper by Peter Van Roy "A Prolog Compiler for the PLM".  Other  programs
were  kindly  donated  by  the  following  ECRC members: Helmut Simonis,
Mehmet Dincbas  and  Pascal  Vanhentenryck.

The  programs  have  been  statically analysed and they represent fairly
standard programs as far as the statistical averages are concerned. That
is  the  arity  of  most  clauses is 2 or 3 and there are usually 2 or 3
clauses per predicate. The programs range from fairly  trivial  programs
like fibonacci series to problems such as Hamiltonian graph traversal.

We have included two versions of main - one for the muprolog and one for
the cprolog (default) dialect.
In case neither work for your  prolog  system,  you should  modify
these to write an appropriate message and use a stopwatch for the timing.

These benchmarks were run on a VAX 785 with 8 Meg of memory,  under  4.2
BSD Unix. The interpreter was C-Prolog version 1.5.

This entire file (without mail/net headers) contains 502 lines.

2.2. Program names and main figures.

Name      |      Call by      |  # of Inferences  | KLips (C-Prolog)
----------+-------------------+-------------------+-----------
mainm     | for use as a template only  ---       |   ---
----------+-------------------+-------------------+-----------
fib       | fibonacci(1).     |        4932       |   1.97
----------+-------------------+-------------------+-----------
map       | map(200).         |          68       |   1.29
----------+-------------------+-------------------+-----------
mham      | mham(1).          |      493824       |   1.69
----------+-------------------+-------------------+-----------
mutest    | mutest(1).        |        1366       |   2.34
----------+-------------------+-------------------+-----------
quicksort | qs(10).           |         605       |   1.90
----------+-------------------+-------------------+-----------
queens    | qu(10).           |         684       |   1.70
----------+-------------------+-------------------+-----------
query     | query(1).         |        2294       |   0.90
----------+-------------------+-------------------+-----------

2.3. Program source listings.

% This is the main loop for Mu-Prolog systems.
% It loops 200 times (for use with naive and map)

main :-utime X,
       loop(200),
       utime Y,
       compens_loop(200),
       utime N,
       Real is Y - N,
       write('Realtime is :'),
       write(Real), nl.

compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).

loop(0).
loop(X) :- top, Y is X - 1, loop(Y).

% Here is the normal main loop for Mu-Prolog...

main :-utime X, top, utime Y,
       write(Y),
       write(' millseconds'), nl.

% Note: has to be not(top) for the 4-queens and query !
-------------------------CUT HERE------------------------------
% Common functions...
print_times(T1,T2,T3,L) :-
        TT1 is T2 - T1,
        TT2 is T3 - T2,
        TT is TT1 - TT2,
        write('Net Time is : '), write(TT), nl,
        Lips is L / TT,
        Klips is Lips / 1000,
        write('KLips are: '), write(Klips), nl.

compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).

el(X,[X|L]).
el(X,[Y|L]):-el(X,L).
%---------------------------------------------------
% Fibonacci Series the slow way
% fibonacci(1) will do...

fibonacci(N) :- X is cputime,
          fib_loop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 4932 * N,
          print_times(X,Now,M,Li).


fib_loop(0).
fib_loop(X) :- top_fib(15,Z), Y is X - 1, fib_loop(Y).

top_fib(0,1).
top_fib(1,1).
top_fib(X,Y):- X1 is X-1,
               X2 is X-2,
               top_fib(X1,Y1),
               top_fib(X2,Y2),
               Y is Y1+Y2.
%------------------------------------
% Map colouring problem
% map(200) is advised.

map(N) :- X is cputime,
          map_loop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 68 * N,
          print_times(X,Now,M,Li).

map_loop(0).
map_loop(X) :- map_top, Y is X - 1, map_loop(Y).

map_top:-
el(X1,[b]),
el(X2,[r]),
el(X7,[g]),
el(X13,[w]),
el(X3,[b,r,g,w]),
not(X2=X3),
not(X3=X13),
el(X4,[b,r,g,w]),
not(X2=X4),
not(X7=X4),
not(X3=X4),
el(X5,[b,r,g,w]),
not(X13=X5),
not(X3=X5),
not(X4=X5),
el(X6,[b,r,g,w]),
not(X13=X6),
not(X5=X6),
el(X8,[b,r,g,w]),
not(X7=X8),
not(X13=X8),
el(X9,[b,r,g,w]),
not(X13=X9),
not(X4=X9),
not(X8=X9),
el(X10,[b,r,g,w]),
not(X4=X10),
not(X5=X10),
not(X6=X10),
not(X9=X10),
el(X11,[b,r,g,w]),
not(X11=X13),
not(X11=X10),
not(X11=X6),
el(X12,[b,r,g,w]),
not(X12=X13),
not(X12=X11),
not(X12=X9),
display([X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13]),nl.

map_top.

%------------------------------------
% Hamiltonian Graphs...
% long (nearly half a million LI's !)

mham(N) :- X is cputime,
          mham_loop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 493824 * N,
          print_times(X,Now,M,Li).

mham_loop(0).
mham_loop(X) :- mham_top, Y is X - 1, mham_loop(Y).

mham_top:-
        cycle_ham([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t],X),
        write(X),nl,
        fail.
mham_top.

cycle_ham([X|Y],[X,T|L]):-
        chain_ham([X|Y],[],[T|L]),
        edge(T,X).

chain_ham([X],L,[X|L]).
chain_ham([X|Y],K,L):-
        delete(Z,Y,T),
        edge(X,Z),
        chain_ham([Z|T],[X|K],L).

delete(X,[X|Y],Y).
delete(X,[U|Y],[U|Z]):-
        delete(X,Y,Z).

edge(X,Y):-
        connect(X,L),
        el(Y,L).

connect(0,[1,2,3,4,5,6,7,8,9]).
connect(1,[0,2,3,4,5,6,7,8,9]).
connect(2,[0,1,3,4,5,6,7,8,9]).
connect(3,[0,1,2,4,5,6,7,8,9]).
connect(4,[0,1,2,3,5,6,7,8,9]).
connect(5,[0,1,2,3,4,6,7,8,9]).
connect(6,[0,1,2,3,4,5,7,8,9]).
connect(7,[0,1,2,3,4,5,6,8,9]).
connect(8,[0,1,2,3,4,5,6,7,9]).
connect(9,[0,1,2,3,4,5,6,7,8]).

connect(a,[b,j,k]).
connect(b,[a,c,p]).
connect(c,[b,d,l]).
connect(d,[c,e,q]).
connect(e,[d,f,m]).
connect(f,[e,g,r]).
connect(g,[f,h,n]).
connect(h,[i,g,s]).
connect(i,[j,h,o]).
connect(j,[a,i,t]).
connect(k,[o,l,a]).
connect(l,[k,m,c]).
connect(m,[l,n,e]).
connect(n,[m,o,g]).
connect(o,[n,k,i]).
connect(p,[b,q,t]).
connect(q,[p,r,d]).
connect(r,[q,s,f]).
connect(s,[r,t,h]).
connect(t,[p,s,j]).

%------------------------------------
%  Hofstader's mu math (mutest) proving muiiu
%       from Godel Escher Bach
mutest(N) :- X is cputime,
          mu_loop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 1366 * N,
          print_times(X,Now,M,Li).

mu_loop(0).
mu_loop(X) :- mu_top, Y is X - 1, mu_loop(Y).

mu_top:- theorem(5,[m,u,i,i,u]).

rules(S, R) :- rule3(S,R).
rules(S, R) :- rule4(S,R).
rules(S, R) :- rule1(S,R).
rules(S, R) :- rule2(S,R).

rule1(S,R) :-
        append(X, [i], S),
        append(X, [i,u], R).

rule2([m | T], [m | R]) :- append(T, T, R).

rule3([], -) :- fail.
rule3(R, T) :-
        append([i,i,i], S, R),
        append([u], S, T).
rule3([H | T], [H | R]) :- rule3(T, R).

rule4([], -) :- fail.
rule4(R, T) :- append([u, u], T, R).
rule4([H | T], [H | R]) :- rule4(T, R).

theorem(Depth, [m, i]).
theorem(Depth, []) :- fail.

theorem(Depth, R) :-
        Depth > 0,
        D is Depth - 1,
        theorem(D, S),
        rules(S, R).

append([], X, X).
append([A | B], X, [A | B1]) :-
        !,
        append(B, X, B1).
%------------------------------------
% Quicksort of 50 element list
%
qs(N) :- X is cputime,
          qs_loop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 605 * N,
          print_times(X,Now,M,Li).

qs_loop(0).
qs_loop(X) :- qs_top, Y is X - 1,qs_loop(Y).

qs_top:-
        list50(L),
        qsort(L,X,[]),
        write(X),nl.

qsort([X|L],R,R0) :-
      partition(L,X,L1,L2),
      qsort(L2,R1,R0),
      qsort(L1,R,[X|R1]).
qsort([],R,R).

partition([X|L],Y,[X|L1],L2) :- X =< Y,!,
      partition(L,Y,L1,L2).
partition([X|L],Y,L1,[X|L2]) :-
      partition(L,Y,L1,L2).
partition([],_,[],[]).

list50([27,74,17,33,94,18,46,83,65,2,
       32,53,28,85,99,47,28,82,6,11,
       55,29,39,81,90,37,10,0,66,51,
        7,21,85,27,31,63,75,4,95,99,
       11,28,61,74,18,92,40,53,59,8]).
%------------------------------------
% Queens on a chess board problem...
% Only two solution on a 4x4 board...
% about 5 - 10 is advised for N.
qu(N) :- X is cputime,
          qu_nloop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 684 * N,
          print_times(X,Now,M,Li).

qu_nloop(0).
qu_nloop(X) :- not(qu_top), Y is X - 1, qu_nloop(Y).

qu_top :-  run(4,X), fail.

size(4).
snint(1).
snint(2).
snint(3).
snint(4).

run(Size, Soln) :- get_solutions(Size, Soln), inform(Soln).

get_solutions(Board_size, Soln) :- solve(Board_size, [], Soln).

%       newsquare generates legal positions for next queen

newsquare([], square(1, X)) :- snint(X).
newsquare([square(I, J) | Rest], square(X, Y)) :-
        X is I + 1,
        snint(Y),
        not(threatened(I, J, X, Y)),
        safe(X, Y, Rest).

%       safe checks whether square(X, Y) is threatened by any
%       existing queens

safe(X, Y, []).
safe(X, Y, [square(I, J) | L]) :-
        not(threatened(I, J, X, Y)),
        safe(X, Y, L).

%       threatened checks whether squares (I, J) and (X, Y)
%       threaten each other

threatened(I, J, X, Y) :-
        (I = X),
        !.
threatened(I, J, X, Y) :-
        (J = Y),
        !.
threatened(I, J, X, Y) :-
        (U is I - J),
        (V is X - Y),
        (U = V),
        !.
threatened(I, J, X, Y) :-
        (U is I + J),
        (V is X + Y),
        (U = V),
        !.

%       solve accumulates the positions of occupied squares

solve(Bs, [square(Bs, Y) | L], [square(Bs, Y) | L]) :- size(Bs).
solve(Board_size, Initial, Final) :-
        newsquare(Initial, Next),
        solve(Board_size, [Next | Initial], Final).

inform([]) :- nl.
inform([M | L]) :- write(M), nl, inform(L).
%------------------------------------
% Query does simple database queries.
%

query(N) :- X is cputime,
          que_nloop(N),
          Now is cputime,
          compens_loop(N),
          M is cputime,
          Li is 2294 * N,
          print_times(X,Now,M,Li).

que_nloop(0).
que_nloop(X) :- not(que_top), Y is X - 1, que_nloop(Y).

que_top:-
         que(X),
         write(X),nl,
         fail.

que([C1,D1,C2,D2]) :-
      density(C1,D1),
      density(C2,D2),
      D1>D2,
      20*D1<21*D2.

density(C,D) :-
      pop(C,P),
      area(C,A),
      D is (P*100)/A.

pop(china,8250).
pop(india,5863).
pop(ussr,2521).
pop(usa,2119).
pop(indonesia,1276).
pop(japan,1097).
pop(brazil,1042).
pop(bangladesh,750).
pop(pakistan,682).
pop(w_germany,620).
pop(nigeria,613).
pop(mexico,581).
pop(uk,559).
pop(italy,554).
pop(france,525).
pop(philippines,415).
pop(thailand,410).
pop(turkey,383).
pop(egypt,364).
pop(spain,352).
pop(poland,337).
pop(s_korea,335).
pop(iran,320).
pop(ethiopia,272).
pop(argentina,251).

area(china,3380).
area(india,1139).
area(ussr,8708).
area(usa,3609).
area(indonesia,570).
area(japan,148).
area(brazil,3288).
area(bangladesh,55).
area(pakistan,311).
area(w_germany,96).
area(nigeria,373).
area(mexico,764).
area(uk,86).
area(italy,116).
area(france,213).
area(philippines,90).
area(thailand,200).
area(turkey,296).
area(egypt,386).
area(spain,190).
area(poland,121).
area(s_korea,37).
area(iran,628).
area(ethiopia,350).
area(argentina,1080).
%--------------------------------------------------*/

3. Real Prolog programs.

This section is empty for now. We would like to have your
advice and/or your programs, with comments on how significant
they are to be considered candidates for benchmarking, and
figures on how long they take, which kinds of queries are
advisable, etc... . Thank you for your collaboration.