jclaude@ecrcvax.UUCP (Jean Claude Syre) (04/28/86)
A Proposal for
***********************************************
*** BENCHMARK PROGRAMS FOR PROLOG SYSTEMS ***
***********************************************
Part 1 (of 3)
J.C. SYRE
ECRC (European Computer-industry Research Center)
Arabellastr. 17
D-8000 MUNICH 81
WEST GERMANY
This set of benchmark programs is a collective work done
by the Logic Programming Group and the Computer Architecture
Group of ECRC, the European Computer-Industry Research Centre,
in Munich.
For convenience, you can send messages to Hans Benker
(replace "jclaude" by "hans" in this net address), or
myself.
The designers of the benchmark programs are: H. Benker, J. Noye,
S. Schmitz, J.C. Syre, and ****many others**** from ECRC.
The first section deals with simple programs whose single
purpose is to evaluate a single feature of prolog execution.
The times we give correspond to an interpretation using Cprolog
on a VAX11/785 under UNIX BSD4.2, in a "quiet" environment
(which may be obtained on a sunny Sunday with all other logins
prohibited). They are subject to a 10 percent inaccuracy due to
paging and timecounts.
The second section presents more complex programs, which may
still run on small Prolog systems. We are open to suggestions
to improve the significance of the benchmark. The programs
include many of the programs taken by the University of
Berkeley for their evaluation of the PLM1 prolog machine. We
are looking for more programs dealing with other domains where
Prolog may be appropriate (natural language, data bases,
reasoning, etc.). Proposals can be sent to me, but do not
forget that the programs must be kept short at exec time.
There should be a third section, that we have not fully built yet,
and we count on you to build it. Those
programs should be representative of real scale prototypes of
large Prolog applications. CHAT80 is an example of such
programs for this section. If you feel embarassed to propagate
one of your programs having properties that you are reluctant to
make public, you may think of modifying it or truncate it so
that it becomes hardly readable, or useless for actual use by
others.
So, here is the first version. We do not pretend at any
originality, we expect to have a large feedback from you,
either to improve this version (through comments, new proposals
or new programs), or to have your evaluation results on your
system. I will report on the next versions and your feelings in
the near future. Have fun !
1. Simple Benchmark programs.
These simple (or simplistic) programs aim at evaluating a
single feature of the Prolog System. Here a Prolog System is
understood as either a pair <Prolog software, Host machine>,
where the Prolog software is an interpreter, a compiler, a
combination of both, and the Host machine is a conventional
machine (with its operating system and workload),
a simulator of a prolog processor, or a real piece of
Prolog hardware (direct interpreter, or PLM processor, or
anything else).
The "single feature" mentioned above means that the performance
results will show how well the Prolog System can handle a
particular characteristic of the language.
The phenomena we measure are:
o calls
o non-determinism
o handling of environments
o unification
o indexing
There are many more which would be interesting to measure, e.g. efficiency
of built-ins, "assert" and "retract", I/O and tail recursion optimisation.
However for now the above 5 criteria seemed to be the most interesting and
maybe somebody on the net can design benchmarks for the remaining features.
Measuring a single feature of a language is difficult. One single execution
of a tiny program testing a particular feature takes not enough time to
measure it precisely. To get a better precision one has to execute the
test program hundreds of times. There are two ways to do this: Write down
the test program as often as one wants to execute it or include it in a
loop. The first solution implies that one has to write programs with
hundreds of lines of code, where each line does the same job.
This is not convenient and it is desirable to use loops. In the case of
our benchmark programs however, the time spent executing the loop is not
negligible, due to the very small size of our test programs. Therefore we
used a combination of both methods, i.e. sequences of repeated code
surrounded with a loop. In order to minimise the effect of the loop, we
actually run as well an "empty" loop, without the benchmark program. We call
this "compensation loop" and subtract its execution time from the execution
time of the loop including the benchmark program. This increases of course
the relative error on the time measurement, but we have decreased the
influence of the unavoidable loop.
The repeated code can be generated by your favorite editor. How much
repeated code you need to get a sufficient precision of course depends on
the implementation of your particular Prolog system. However we put as much
repeated code into each benchmark program as we think is apropriate to most
Prolog implementations. So we think you should get sufficient precision
without modifying our programs in that respect.
The listings of the programs follow below. For each simple program we try to
give the characteristics of it and some remarks about what it measures.
Note that "cputime" in C-Prolog on the VAX gives you the possibility to
measure runtime. This may be different in other Prolog systems. All the
rest of the programs should be portable to any other system without any
problem.
1.1. Program to test calls (boresea).
This is the one you always dreamed to test! Like all benchmarks, it uses a
loop calling the actual benchmark program. The benchmark program consists of
a sequence of 200 predicates having no arguments, no choice points, NOTHING.
200 is chosen to have sufficient accuracy in measuring the execution time.
The results show the effect of pure calls, and the Klips performance can be
called the peak performance of the prolog system. Note that the peak
performance has very little significance to classify the overall performance
of a Prolog system.
---------------- cut here - beginning of program listing ---------------------
/* This program is called with the query "?-boresea(X)." */
/* X is the number of loop iterations executed. It should be big */
/* enough to give significant results. */
/* suggested value for X: 100 for interpreted code*/
/* 1000 for compiled code */
/* average values for C-prolog interpreter: */
/* X=1000, Tloop=27.1 T.comp=1.0 Tnet=26.1 Klips=7.7 */
boresea(X)
:- T1 is cputime,
do_max_KLips(X), /* calls the loop to execute the */
T2 is cputime, /* sequence of 200 predicates */
compens_loop(X), /* compensation loop */
T3 is cputime,
print_times(T1,T2,T3,X,200). /* compute and print results */
compens_loop(0). /* compensation loop */
compens_loop(X) :- Y is X - 1, compens_loop(Y).
print_times(T1,T2,T3,X,I) :- /* prints the results */
TT1 is T2 - T1,
TT2 is T3 - T2,
TT is TT1 - TT2,
write('T overall loop: '),write(TT1), nl,
write('T compens loop: '),write(TT2), nl,
write('T net: '),write(TT),nl,
write('KLips: '),
Li is I * X,
Lips is Li / TT,
KLips is Lips / 1000,
write(KLips),nl,nl.
do_max_KLips(0). /* loop calling the actual benchmark */
do_max_KLips(X) :- lips1, Y is X - 1, do_max_KLips(Y).
/* predicates to test call */
lips1 :- lips2.
lips2 :- lips3.
lips3 :- lips4.
lips4 :- lips5.
lips5 :- lips6.
lips6 :- lips7.
lips7 :- lips8.
lips8 :- lips9.
lips9 :- lips10.
lips10 :- lips11.
lips11 :- lips12.
lips12 :- lips13.
lips13 :- lips14.
lips14 :- lips15.
lips15 :- lips16.
lips16 :- lips17.
lips17 :- lips18.
lips18 :- lips19.
lips19 :- lips20.
lips20 :- lips21.
lips21 :- lips22.
lips22 :- lips23.
lips23 :- lips24.
lips24 :- lips25.
lips25 :- lips26.
lips26 :- lips27.
lips27 :- lips28.
lips28 :- lips29.
lips29 :- lips30.
lips30 :- lips31.
lips31 :- lips32.
lips32 :- lips33.
lips33 :- lips34.
lips34 :- lips35.
lips35 :- lips36.
lips36 :- lips37.
lips37 :- lips38.
lips38 :- lips39.
lips39 :- lips40.
lips40 :- lips41.
lips41 :- lips42.
lips42 :- lips43.
lips43 :- lips44.
lips44 :- lips45.
lips45 :- lips46.
lips46 :- lips47.
lips47 :- lips48.
lips48 :- lips49.
lips49 :- lips50.
lips50 :- lips51.
lips51 :- lips52.
lips52 :- lips53.
lips53 :- lips54.
lips54 :- lips55.
lips55 :- lips56.
lips56 :- lips57.
lips57 :- lips58.
lips58 :- lips59.
lips59 :- lips60.
lips60 :- lips61.
lips61 :- lips62.
lips62 :- lips63.
lips63 :- lips64.
lips64 :- lips65.
lips65 :- lips66.
lips66 :- lips67.
lips67 :- lips68.
lips68 :- lips69.
lips69 :- lips70.
lips70 :- lips71.
lips71 :- lips72.
lips72 :- lips73.
lips73 :- lips74.
lips74 :- lips75.
lips75 :- lips76.
lips76 :- lips77.
lips77 :- lips78.
lips78 :- lips79.
lips79 :- lips80.
lips80 :- lips81.
lips81 :- lips82.
lips82 :- lips83.
lips83 :- lips84.
lips84 :- lips85.
lips85 :- lips86.
lips86 :- lips87.
lips87 :- lips88.
lips88 :- lips89.
lips89 :- lips90.
lips90 :- lips91.
lips91 :- lips92.
lips92 :- lips93.
lips93 :- lips94.
lips94 :- lips95.
lips95 :- lips96.
lips96 :- lips97.
lips97 :- lips98.
lips98 :- lips99.
lips99 :- lips100.
lips100:- lips101.
lips101 :- lips102.
lips102 :- lips103.
lips103 :- lips104.
lips104 :- lips105.
lips105 :- lips106.
lips106 :- lips107.
lips107 :- lips108.
lips108 :- lips109.
lips109 :- lips110.
lips110 :- lips111.
lips111 :- lips112.
lips112 :- lips113.
lips113 :- lips114.
lips114 :- lips115.
lips115 :- lips116.
lips116 :- lips117.
lips117 :- lips118.
lips118 :- lips119.
lips119 :- lips120.
lips120 :- lips121.
lips121 :- lips122.
lips122 :- lips123.
lips123 :- lips124.
lips124 :- lips125.
lips125 :- lips126.
lips126 :- lips127.
lips127 :- lips128.
lips128 :- lips129.
lips129 :- lips130.
lips130 :- lips131.
lips131 :- lips132.
lips132 :- lips133.
lips133 :- lips134.
lips134 :- lips135.
lips135 :- lips136.
lips136 :- lips137.
lips137 :- lips138.
lips138 :- lips139.
lips139 :- lips140.
lips140 :- lips141.
lips141 :- lips142.
lips142 :- lips143.
lips143 :- lips144.
lips144 :- lips145.
lips145 :- lips146.
lips146 :- lips147.
lips147 :- lips148.
lips148 :- lips149.
lips149 :- lips150.
lips150 :- lips151.
lips151 :- lips152.
lips152 :- lips153.
lips153 :- lips154.
lips154 :- lips155.
lips155 :- lips156.
lips156 :- lips157.
lips157 :- lips158.
lips158 :- lips159.
lips159 :- lips160.
lips160 :- lips161.
lips161 :- lips162.
lips162 :- lips163.
lips163 :- lips164.
lips164 :- lips165.
lips165 :- lips166.
lips166 :- lips167.
lips167 :- lips168.
lips168 :- lips169.
lips169 :- lips170.
lips170 :- lips171.
lips171 :- lips172.
lips172 :- lips173.
lips173 :- lips174.
lips174 :- lips175.
lips175 :- lips176.
lips176 :- lips177.
lips177 :- lips178.
lips178 :- lips179.
lips179 :- lips180.
lips180 :- lips181.
lips181 :- lips182.
lips182 :- lips183.
lips183 :- lips184.
lips184 :- lips185.
lips185 :- lips186.
lips186 :- lips187.
lips187 :- lips188.
lips188 :- lips189.
lips189 :- lips190.
lips190 :- lips191.
lips191 :- lips192.
lips192 :- lips193.
lips193 :- lips194.
lips194 :- lips195.
lips195 :- lips196.
lips196 :- lips197.
lips197 :- lips198.
lips198 :- lips199.
lips199 :- lips200.
lips200.
--------------------cut here - end of program listing-------------------------
1.2. Program to test non deterministic behaviour
This program contains a series of 3 different benchmark predicates.
The predicate "choice_point(N)" tests calls invoking the creation of a
choice point, i.e. a branch point where the execution will possibly come
back to in case of backtracking. It does NOT backtrack.
We then present two predicates to evaluate the mechanism of backtracking
during execution. Both predicates create one choice_point and then backtrack
20 times on every loop iteration step. "baktrak1(N)" exhibits a kind of
backtracking called "deep", while "baktrak2(N)" deals with "shallow"
backtracking. Both are worth being tried, whatever your particular
Prolog System is.
----------------------cut here - beginning of program listing----------------
/* program to benchmark non deterministic behaviour of Prolog Systems */
/* The predicates are called: */
/* o "choice_point(N)" - creation of choice points */
/* o "baktrak1(N)" - deep backtracking */
/* o "baktrak2(N)" - shallow backtracking */
/* N is the number of loop iterations executed */
/* predicate to test creation of choice points without backtracking */
/* suggested value for N: 1000 */
/* results for Cprolog N=1000 */
/* Tloop=5.95 Tcompens=0.98 Tnet=4.97 Klips=4.02 */
choice_point(N):-T1 is cputime,
cre_CP(N), T2 is cputime,
compens_loop(N), T3 is cputime,
print_times(T1,T2,T3,N,20).
/* Predicate to test the (deep) backtracking mechanism. */
/* suggested value for N: 1000 (interp), 2000(comp) */
/* results for Cprolog: N=1000 */
/* Tloop=9.63 Tcomp=1 Tnet=8.63 Klips=2.32 */
baktrak1(N)
:- T1 is cputime,
deep_back(N),
T2 is cputime,
compens_loop(N),
T3 is cputime,
print_times(T1,T2,T3,N,20).
/* Predicate to test the (shallow) backtracking mechanism */
/* suggested value for N: 1000 (interp), 2000 (comp) */
/* results for Cprolog: N=1000 */
/* Tloop=6.63 Tcomp=0.97 Tnet=5.67 Klips=3.53 */
baktrak2(X)
:- T1 is cputime,
shallow_back(X), T2 is cputime,
compens_loop(X), T3 is cputime,
print_times(T1,T2,T3,X,20).
/* compensation loop, used to measure the time spent in the loop */
compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).
/* loop to test choice point creation */
cre_CP(0).
cre_CP(N):-M is N-1, ccp1(0,0,0), cre_CP(M).
/* loop to test deep backtracking */
deep_back(0).
deep_back(X) :- pd(X1,X2,X3), Y is X - 1, deep_back(Y).
/* loop to test shallow backtracking */
shallow_back(0).
shallow_back(X) :- ps(X1,X2,X3), Y is X - 1, shallow_back(Y).
print_times(T1,T2,T3,X,I) :- /* prints the results */
TT1 is T2 - T1,
TT2 is T3 - T2,
TT is TT1 - TT2,
write('T overall loop: '),write(TT1), nl,
write('T compens loop: '),write(TT2), nl,
write('T net: '),write(TT),nl,
write('KLips: '),
Li is I * X,
Lips is Li / TT,
KLips is Lips / 1000,
write(KLips),nl,nl.
/* ccp1 creates 20 choice points */
/* ccp1 is the beginning of a set of predicates */
/* composed of 2 clauses each. Every invokation of nd0 will create */
/* a sequence of 20 choice points. The body of the clauses are */
/* limited to one goal, thus avoiding a creation of environment */
/* when the clause is activated. nd0, and its successors, have */
/* three arguments to comply with our average static analysis */
/* results made on more than 30 real Prolog programs. */
ccp1(X,Y,Z):-ccp2(X,Y,Z).
ccp1(X,Y,Z).
ccp2(X,Y,Z):-ccp3(X,Y,Z).
ccp2(X,Y,Z).
ccp3(X,Y,Z):-ccp4(X,Y,Z).
ccp3(X,Y,Z).
ccp4(X,Y,Z):-ccp5(X,Y,Z).
ccp4(X,Y,Z).
ccp5(X,Y,Z):-ccp6(X,Y,Z).
ccp5(X,Y,Z).
ccp6(X,Y,Z):-ccp7(X,Y,Z).
ccp6(X,Y,Z).
ccp7(X,Y,Z):-ccp8(X,Y,Z).
ccp7(X,Y,Z).
ccp8(X,Y,Z):-ccp9(X,Y,Z).
ccp8(X,Y,Z).
ccp9(X,Y,Z):-ccp10(X,Y,Z).
ccp9(X,Y,Z).
ccp10(X,Y,Z):-ccp11(X,Y,Z).
ccp10(X,Y,Z).
ccp11(X,Y,Z):-ccp12(X,Y,Z).
ccp11(X,Y,Z).
ccp12(X,Y,Z):-ccp13(X,Y,Z).
ccp12(X,Y,Z).
ccp13(X,Y,Z):-ccp14(X,Y,Z).
ccp13(X,Y,Z).
ccp14(X,Y,Z):-ccp15(X,Y,Z).
ccp14(X,Y,Z).
ccp15(X,Y,Z):-ccp16(X,Y,Z).
ccp15(X,Y,Z).
ccp16(X,Y,Z):-ccp17(X,Y,Z).
ccp16(X,Y,Z).
ccp17(X,Y,Z):-ccp18(X,Y,Z).
ccp17(X,Y,Z).
ccp18(X,Y,Z):-ccp19(X,Y,Z).
ccp18(X,Y,Z).
ccp19(X,Y,Z):-ccp20(X,Y,Z).
ccp19(X,Y,Z).
ccp20(X,Y,Z).
ccp20(X,Y,Z).
/* deep backtracking */
/* The call to pd creates a choice point, and invokes a */
/* call to q. It will fail and there will be a backtracking step */
/* to try the next clause defining pd. pd has 21 clauses,thus failure */
/* occurs 20 times */
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3) :- q(X1,X2,a).
pd(X1,X2,X3).
q(X1,X2,b).
/* shallow backtracking */
/* The ps predicate fails 20 times. The shallow backtracking */
/* will not restore all current state registers in Prolog */
/* systems which perform this optimisation, while others will. */
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3) :- fail.
ps(X1,X2,X3).
---------------------cut here - end of program listing-----------------------jclaude@ecrcvax.UUCP (Jean Claude Syre) (04/28/86)
A Proposal for
***********************************************
*** BENCHMARK PROGRAMS FOR PROLOG SYSTEMS ***
***********************************************
Part 2 (of 3)
1.3. Program to test the handling of environments (envir).
The creation of environments is an important feature in prolog
machines. The following program attempts to evaluate that.
A usual condition to have environments is that the clause is
made of several goals. Thus there will be calls in the clause
creating environments, and some work to set the parameters of
each call. Three arguments per goal were chosen because this number
comes close to the average number of arguments of a predicate and to
the average number of permanent variables in an environment.
The arguments were arranged in different orders for every goal,
because we did not want to measure the merits of register transfer
optimisations.
-----------------cut here - beginning of program listing--------------------
/* creates 79 environments and 158 calls */
/* suggested value for N: 1000 (interp), 1000 (comp) */
/* results for Cprolog: N=1000 */
/* Tloop=38.6 Tcomp=0.97 Tnet=37.6 Klips=4.23 */
envir(N):-T1 is cputime,
cre_env(N), T2 is cputime,
compens_loop(N), T3 is cputime,
print_times(T1,T2,T3,N,159).
cre_env(0).
cre_env(N):-M is N-1, env0(X,Y,Z), cre_env(M).
compens_loop(0).
compens_loop(N):-M is N-1,compens_loop(M).
env0(X,Y,Z):-env1(Z,X,Y),env2(Y,Z,X). /* creates 79 environments */
env1(X,Y,Z):-env3(Z,Y,X),env4(Y,Z,X).
env2(X,Y,Z):-env3(Z,Y,X),env4(Y,Z,X). /* and 158 calls */
env3(X,Y,Z):-env5(Z,Y,X),env6(Y,Z,X).
env4(X,Y,Z):-env5(Z,Y,X),env6(Y,Z,X).
env5(X,Y,Z):-env7(Z,Y,X),env8(Y,Z,X).
env6(X,Y,Z):-env7(Z,Y,X),env8(Y,Z,X).
env7(X,Y,Z):-env9(Z,Y,X),env10(Y,Z,X).
env8(X,Y,Z):-env9(Z,Y,X),env10(Y,Z,X).
env9(X,Y,Z):-env11(Z,Y,X),env12(Y,Z,X).
env10(X,Y,Z):-env12(Z,Y,X),env12(Y,Z,X).
env11(X,Y,Z):-env12(Z,Y,X),env12(Y,Z,X).
env12(X,Y,Z).
print_times(T1,T2,T3,X,I) :- /* prints the results */
TT1 is T2 - T1,
TT2 is T3 - T2,
TT is TT1 - TT2,
write('T overall loop: '),write(TT1), nl,
write('T compens loop: '),write(TT2), nl,
write('T net: '),write(TT),nl,
write('KLips: '),
Li is I * X,
Lips is Li / TT,
KLips is Lips / 1000,
write(KLips),nl,nl.
----------------------------cut here - end of program listing----------------
1.4. Program to test indexing mechanisms.
We give only one test for indexing, i.e. the selection of a clause due to
the type of an argument. This program does not test the merits of indexing
on an argument other than the first one. It does not test for multiple
indexing either. It does not show the inefficiency which occurs if 2 choice
points per clause are created. This may happen e.g. in Warren's indexing
scheme.
Each of these tests would require an extra benchmark program. The program
given below tests the main point in indexing. Right now we think it is not
worth adding all this complexity to the benchmarks, in order to measure all
the details in indexing. Therefore we give only this single test.
-----------------------cut here - beginning of program listing---------------
/* This program is called with "index(N)" */
/* It tests the efficiency of simple indexing on the first argument */
/* suggested value for N: 500 (interp), 2000(comp) */
/* results for Cprolog: N=500 */
/* Tloop=8.98 Tcomp=0.52 Tnet=8.47 Klips=1.24 */
index(N)
:- T1 is cputime,
index_loop(N), T2 is cputime,
compens_loop(N), T3 is cputime,
print_times(T1,T2,T3,N,21).
/* loop with calls to the actual benchmark program for indexing */
index_loop(0).
index_loop(X) :- p(a), p([a]), p(s(a)), /* queries to the actual */
p(b), p([b]), p(s(b)), /* benchmark program */
p(c), p([c]), p(s(c)),
p(d), p([d]), p(s(d)),
p(e), p([e]), p(s(e)),
p(f), p([f]), p(s(g)),
p(g), p([g]), p(s(g)),
Y is X - 1, index_loop(Y).
/* compensation loop */
compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).
/* test program which can be optimised by indexing */
p(a).
p([a]).
p(s(a)).
p(b).
p([b]).
p(s(b)).
p(c).
p([c]).
p(s(c)).
p(d).
p([d]).
p(s(d)).
p(e).
p([e]).
p(s(e)).
p(f).
p([f]).
p(s(f)).
p(g).
p([g]).
p(s(g)).
print_times(T1,T2,T3,X,I) :- /* prints the results */
TT1 is T2 - T1,
TT2 is T3 - T2,
TT is TT1 - TT2,
write('T first loop: '),write(TT1), nl,
write('T compens loop: '),write(TT2), nl,
write('T net: '),write(TT),nl,
write('KLips: '),
Li is I * X,
Lips is Li / TT,
KLips is Lips / 1000,
write(KLips),nl,nl.
-------------------cut here - end of program listing-------------------------
1.5. Programs to test unification.
We have 6 programs to evaluate the process of unification in
the Prolog system. As usual, we will use the "compens_loop" predicate as
a compensation for the extra work done for looping a little,
and the "print_times" predicate to print results.
--------------------cut here - beginning of program listing-----------------
/* The predicates are called with: */
/* benchmark_name(X). */
/* where benchmark_name is the name of the predicate */
/* and X is the number of (external) loop iterations */
/* The benchmarks on this file are: construct_list */
/* match_list */
/* construct_structure */
/* match_structure */
/* match_nested_structure */
/* general_unification */
/* Test of list construction via unification */
/* suggested value for N: 100 (interp), 500(comp) */
/* results for Cprolog: N=100 */
/* Tloop=1.77 Tcomp=0.1 Tnet=1.67 Klips=6.0 */
construct_list(X) /* uses unification to */
:- T1 is cputime, /* construct a list of 100 elts */
do_construct_list(X),
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,100).
/* Test of list matching unification */
/* suggested value for N: 100 (interp), 1000(comp) */
/* results for Cprolog: N=100 */
/* Tloop=2.47 Tcomp=0.1 Tnet=2.39 Klips=4.2 */
match_list(X)
:- list100(Z), /* construction of the matching list is done */
T1 is cputime, /* outside of the loop, in order not to count */
do_match_list(X,Z), /* the construction of the list */
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,100).
/* Test of structure construction via unification */
/* this program is equivalent to construct_list, except that it uses */
/* the standard structure representation instead of the simplified */
/* list notation */
/* suggested value for N: 100 (interp), 500(comp) */
/* results for Cprolog: N=100 */
/* Tloop=1.75 Tcomp=0.08 Tnet=1.67 Klips=6 */
construct_structure(X)
:- T1 is cputime,
do_construct_structure(X),
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,100).
/* Test of structure matching via unification */
/* this predicate matches a list of 100 elements in structure notation */
/* suggested value for N: 100 (interp), 100(comp) */
/* results for Cprolog: N=100 */
/* Tloop=2.42 Tcomp=0.08 Tnet=2.34 Klips=4.3 */
match_structure(X)
:- structure100(Z),
T1 is cputime,
do_match_structure(X,Z),
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,100).
/* Test to match a nested structure */
/* this predicate tests the (compiled) unification of a complex structure */
/* suggested value for N: 200 (interp), 200(comp) */
/* results for Cprolog: N=200 */
/* Tloop=1.34 Tcomp=0.17 Tnet=1.18 Klips=0.17 */
match_nested_structure(X)
:- nested_structure1(Z), /* the structure to match is constructed */
/* outside the loop, in order to measure */
/* only the matching time */
T1 is cputime,
do_match_nested_structure(X,Z),
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,1).
/* Test of general unification of 2 complex structures */
/* this predicate tests general unification, i.e. unification which */
/* cannot be compiled */
/* suggested value for N: 200 (interp), 500(comp) */
/* results for Cprolog: N=200 */
/* Tloop=1.38 Tcomp=0.18 Tnet=1.20 Klips=0.17 */
general_unification(X) :-
nested_structure1(A),
nested_structure2(B),
T1 is cputime,
do_general_unification(X,A,B),
T2 is cputime,
compens_loop(X),
T3 is cputime,
print_times(T1,T2,T3,X,1).
/* predicate to print the results of the benchmarking */
print_times(T1,T2,T3,X,I) :-
TT1 is T2 - T1,
TT2 is T3 - T2,
TT is TT1 - TT2,
write('T overall loop: '),write(TT1), nl,
write('T compens loop: '),write(TT2), nl,
write('T benchmark: '),write(TT),nl,
write('KLips: '),
Li is I * X,
Lips is Li / TT,
KLips is Lips / 1000,
write(KLips),nl,nl.
/* compensation loop, used to measure the time spent in the loop */
compens_loop(0).
compens_loop(X) :- Y is X - 1, compens_loop(Y).
/* list constructing loop */
do_construct_list(0).
do_construct_list(X) :- cl1(Z), Y is X - 1, do_construct_list(Y).
/* list matching loop */
do_match_list(0,Z).
do_match_list(X,Z) :- cl1(Z), Y is X - 1, do_match_list(Y,Z).
/* structure constructing loop */
do_construct_structure(0).
do_construct_structure(X) :- cs1(Z), Y is X - 1, do_construct_structure(Y).
/* structure matching loop */
do_match_structure(0,Z).
do_match_structure(X,Z) :- cs1(Z), Y is X - 1,
do_match_structure(Y,Z).
/* loop to match a nested structure */
do_match_nested_structure(0,Z).
do_match_nested_structure(X,Z) :-
nested_structure2(Z),
Y is X - 1,
do_match_nested_structure(Y,Z).
/* loop for general unification */
do_general_unification(0,A,B).
do_general_unification(X,A,B) :-
unify(A,B),
Y is X - 1,
do_general_unification(Y,A,B).
/* general unification */
unify(X,X).
/* complex structure as example for unification tests */
/* the same structure is given twice, in order to make sure that */
/* even implementations using structure sharing execute the unification */
/* and do not just pass pointers */
nested_structure1(
[a( [a1([1,2,3],a),a2([4,5,6],b),a3([7,8,9],c)],
[a4([0,1,2],d),a5([3,4,5],e),a6([6,7,8],f)],
[a7([9,0,1],g),a8([2,3,4],h),a9([5,6,7],i)]),
b( [b1([1,2,3],a),b2([4,5,6],b),b3([7,8,9],c)],
[b4([0,1,2],d),b5([3,4,5],e),b6([6,7,8],f)],
[b7([9,0,1],g),b8([2,3,4],h),b9([5,6,7],i)]),
c( [c1([1,2,3],a),c2([4,5,6],b),c3([7,8,9],c)],
[c4([0,1,2],d),c5([3,4,5],e),c6([6,7,8],f)],
[c7([9,0,1],g),c8([2,3,4],h),c9([5,6,7],i)])]).
nested_structure2(
[a( [a1([1,2,3],a),a2([4,5,6],b),a3([7,8,9],c)],
[a4([0,1,2],d),a5([3,4,5],e),a6([6,7,8],f)],
[a7([9,0,1],g),a8([2,3,4],h),a9([5,6,7],i)]),
b( [b1([1,2,3],a),b2([4,5,6],b),b3([7,8,9],c)],
[b4([0,1,2],d),b5([3,4,5],e),b6([6,7,8],f)],
[b7([9,0,1],g),b8([2,3,4],h),b9([5,6,7],i)]),
c( [c1([1,2,3],a),c2([4,5,6],b),c3([7,8,9],c)],
[c4([0,1,2],d),c5([3,4,5],e),c6([6,7,8],f)],
[c7([9,0,1],g),c8([2,3,4],h),c9([5,6,7],i)])]).
/* list of 100 elements used for match_list */
list100([a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,
a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,
a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a]).
/* structure of 100 elements used for match_structure */
structure100(st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,st(a,
st(a,st(a,st(a,st(a,nil)
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
)))))))))))))))))))))))))))))))))))))))).
/* predicates to test unification of lists */
cl1([a|X]) :- cl2(X).
cl2([a|X]) :- cl3(X).
cl3([a|X]) :- cl4(X).
cl4([a|X]) :- cl5(X).
cl5([a|X]) :- cl6(X).
cl6([a|X]) :- cl7(X).
cl7([a|X]) :- cl8(X).
cl8([a|X]) :- cl9(X).
cl9([a|X]) :- cl10(X).
cl10([a|X]) :- cl11(X).
cl11([a|X]) :- cl12(X).
cl12([a|X]) :- cl13(X).
cl13([a|X]) :- cl14(X).
cl14([a|X]) :- cl15(X).
cl15([a|X]) :- cl16(X).
cl16([a|X]) :- cl17(X).
cl17([a|X]) :- cl18(X).
cl18([a|X]) :- cl19(X).
cl19([a|X]) :- cl20(X).
cl20([a|X]) :- cl21(X).
cl21([a|X]) :- cl22(X).
cl22([a|X]) :- cl23(X).
cl23([a|X]) :- cl24(X).
cl24([a|X]) :- cl25(X).
cl25([a|X]) :- cl26(X).
cl26([a|X]) :- cl27(X).
cl27([a|X]) :- cl28(X).
cl28([a|X]) :- cl29(X).
cl29([a|X]) :- cl30(X).
cl30([a|X]) :- cl31(X).
cl31([a|X]) :- cl32(X).
cl32([a|X]) :- cl33(X).
cl33([a|X]) :- cl34(X).
cl34([a|X]) :- cl35(X).
cl35([a|X]) :- cl36(X).
cl36([a|X]) :- cl37(X).
cl37([a|X]) :- cl38(X).
cl38([a|X]) :- cl39(X).
cl39([a|X]) :- cl40(X).
cl40([a|X]) :- cl41(X).
cl41([a|X]) :- cl42(X).
cl42([a|X]) :- cl43(X).
cl43([a|X]) :- cl44(X).
cl44([a|X]) :- cl45(X).
cl45([a|X]) :- cl46(X).
cl46([a|X]) :- cl47(X).
cl47([a|X]) :- cl48(X).
cl48([a|X]) :- cl49(X).
cl49([a|X]) :- cl50(X).
cl50([a|X]) :- cl51(X).
cl51([a|X]) :- cl52(X).
cl52([a|X]) :- cl53(X).
cl53([a|X]) :- cl54(X).
cl54([a|X]) :- cl55(X).
cl55([a|X]) :- cl56(X).
cl56([a|X]) :- cl57(X).
cl57([a|X]) :- cl58(X).
cl58([a|X]) :- cl59(X).
cl59([a|X]) :- cl60(X).
cl60([a|X]) :- cl61(X).
cl61([a|X]) :- cl62(X).
cl62([a|X]) :- cl63(X).
cl63([a|X]) :- cl64(X).
cl64([a|X]) :- cl65(X).
cl65([a|X]) :- cl66(X).
cl66([a|X]) :- cl67(X).
cl67([a|X]) :- cl68(X).
cl68([a|X]) :- cl69(X).
cl69([a|X]) :- cl70(X).
cl70([a|X]) :- cl71(X).
cl71([a|X]) :- cl72(X).
cl72([a|X]) :- cl73(X).
cl73([a|X]) :- cl74(X).
cl74([a|X]) :- cl75(X).
cl75([a|X]) :- cl76(X).
cl76([a|X]) :- cl77(X).
cl77([a|X]) :- cl78(X).
cl78([a|X]) :- cl79(X).
cl79([a|X]) :- cl80(X).
cl80([a|X]) :- cl81(X).
cl81([a|X]) :- cl82(X).
cl82([a|X]) :- cl83(X).
cl83([a|X]) :- cl84(X).
cl84([a|X]) :- cl85(X).
cl85([a|X]) :- cl86(X).
cl86([a|X]) :- cl87(X).
cl87([a|X]) :- cl88(X).
cl88([a|X]) :- cl89(X).
cl89([a|X]) :- cl90(X).
cl90([a|X]) :- cl91(X).
cl91([a|X]) :- cl92(X).
cl92([a|X]) :- cl93(X).
cl93([a|X]) :- cl94(X).
cl94([a|X]) :- cl95(X).
cl95([a|X]) :- cl96(X).
cl96([a|X]) :- cl97(X).
cl97([a|X]) :- cl98(X).
cl98([a|X]) :- cl99(X).
cl99([a|X]) :- cl100(X).
cl100([a]).
/* predicates to test unification of structures */
cs1(st(a,X)) :- cs2(X).
cs2(st(a,X)) :- cs3(X).
cs3(st(a,X)) :- cs4(X).
cs4(st(a,X)) :- cs5(X).
cs5(st(a,X)) :- cs6(X).
cs6(st(a,X)) :- cs7(X).
cs7(st(a,X)) :- cs8(X).
cs8(st(a,X)) :- cs9(X).
cs9(st(a,X)) :- cs10(X).
cs10(st(a,X)) :- cs11(X).
cs11(st(a,X)) :- cs12(X).
cs12(st(a,X)) :- cs13(X).
cs13(st(a,X)) :- cs14(X).
cs14(st(a,X)) :- cs15(X).
cs15(st(a,X)) :- cs16(X).
cs16(st(a,X)) :- cs17(X).
cs17(st(a,X)) :- cs18(X).
cs18(st(a,X)) :- cs19(X).
cs19(st(a,X)) :- cs20(X).
cs20(st(a,X)) :- cs21(X).
cs21(st(a,X)) :- cs22(X).
cs22(st(a,X)) :- cs23(X).
cs23(st(a,X)) :- cs24(X).
cs24(st(a,X)) :- cs25(X).
cs25(st(a,X)) :- cs26(X).
cs26(st(a,X)) :- cs27(X).
cs27(st(a,X)) :- cs28(X).
cs28(st(a,X)) :- cs29(X).
cs29(st(a,X)) :- cs30(X).
cs30(st(a,X)) :- cs31(X).
cs31(st(a,X)) :- cs32(X).
cs32(st(a,X)) :- cs33(X).
cs33(st(a,X)) :- cs34(X).
cs34(st(a,X)) :- cs35(X).
cs35(st(a,X)) :- cs36(X).
cs36(st(a,X)) :- cs37(X).
cs37(st(a,X)) :- cs38(X).
cs38(st(a,X)) :- cs39(X).
cs39(st(a,X)) :- cs40(X).
cs40(st(a,X)) :- cs41(X).
cs41(st(a,X)) :- cs42(X).
cs42(st(a,X)) :- cs43(X).
cs43(st(a,X)) :- cs44(X).
cs44(st(a,X)) :- cs45(X).
cs45(st(a,X)) :- cs46(X).
cs46(st(a,X)) :- cs47(X).
cs47(st(a,X)) :- cs48(X).
cs48(st(a,X)) :- cs49(X).
cs49(st(a,X)) :- cs50(X).
cs50(st(a,X)) :- cs51(X).
cs51(st(a,X)) :- cs52(X).
cs52(st(a,X)) :- cs53(X).
cs53(st(a,X)) :- cs54(X).
cs54(st(a,X)) :- cs55(X).
cs55(st(a,X)) :- cs56(X).
cs56(st(a,X)) :- cs57(X).
cs57(st(a,X)) :- cs58(X).
cs58(st(a,X)) :- cs59(X).
cs59(st(a,X)) :- cs60(X).
cs60(st(a,X)) :- cs61(X).
cs61(st(a,X)) :- cs62(X).
cs62(st(a,X)) :- cs63(X).
cs63(st(a,X)) :- cs64(X).
cs64(st(a,X)) :- cs65(X).
cs65(st(a,X)) :- cs66(X).
cs66(st(a,X)) :- cs67(X).
cs67(st(a,X)) :- cs68(X).
cs68(st(a,X)) :- cs69(X).
cs69(st(a,X)) :- cs70(X).
cs70(st(a,X)) :- cs71(X).
cs71(st(a,X)) :- cs72(X).
cs72(st(a,X)) :- cs73(X).
cs73(st(a,X)) :- cs74(X).
cs74(st(a,X)) :- cs75(X).
cs75(st(a,X)) :- cs76(X).
cs76(st(a,X)) :- cs77(X).
cs77(st(a,X)) :- cs78(X).
cs78(st(a,X)) :- cs79(X).
cs79(st(a,X)) :- cs80(X).
cs80(st(a,X)) :- cs81(X).
cs81(st(a,X)) :- cs82(X).
cs82(st(a,X)) :- cs83(X).
cs83(st(a,X)) :- cs84(X).
cs84(st(a,X)) :- cs85(X).
cs85(st(a,X)) :- cs86(X).
cs86(st(a,X)) :- cs87(X).
cs87(st(a,X)) :- cs88(X).
cs88(st(a,X)) :- cs89(X).
cs89(st(a,X)) :- cs90(X).
cs90(st(a,X)) :- cs91(X).
cs91(st(a,X)) :- cs92(X).
cs92(st(a,X)) :- cs93(X).
cs93(st(a,X)) :- cs94(X).
cs94(st(a,X)) :- cs95(X).
cs95(st(a,X)) :- cs96(X).
cs96(st(a,X)) :- cs97(X).
cs97(st(a,X)) :- cs98(X).
cs98(st(a,X)) :- cs99(X).
cs99(st(a,X)) :- cs100(X).
cs100(st(a,nil)).jclaude@ecrcvax.UUCP (Jean Claude Syre) (04/29/86)
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.