🚀 go-pugleaf

In news letter, we found a solution to the triangle problem, to which we will
refer as the ......program: not naming the author nor the company he works for,
is not out of maliciousness, rather because the not mentioned author refuses
systematically to name BIMprolog when naming other prolog implementations.

During a coffee break (no, if you think ......program stands for KOffeeprogram,
your are wrong, yes you are :-), we asked ourselves 2 questions:

1. how easy is it to write a program that is faster than the ......program and
   still readable
2. how relevant is the figure 0.75 quoted for finding the first solution
   (to be honest: ...... himself says that this figure 'doesn't mean much')


Before we looked at the ......program, we wrote our own, which we will refer to
as the BIMprogram. 


Our findings are summarized in the following table: there are 15 possible
starting positions, numbered from 1 to 15, as in the triangle below:

                        1
                      2   3
                    4   5   6
                  7   8   9   10
                11  12  13  14  15


The figures mentioned in the column under BIMprogram and ......program,
represent the cputime in seconds needed to find the first solution.


start position		BIMprogram		......program
--------------		----------		-------------
 1			 0.500000		 0.660000
 2			 9.780001		12.740001
 3			42.760002		55.980000
 4			 0.539997		 0.680000
 5			25.719997		33.900002
 6			 0.059998		 0.080002
 7			 0.520004		 0.659996
 8			18.820000		24.659996
 9			10.680000		14.000000
10			 0.519997		 0.660004
11			 9.779999		12.779999
12			32.980003		43.180008
13			 0.520004		 0.659988
14			32.660004		42.800003
15			10.300003		14.079987

4 conclusions:

1. the BIMprogram is systematically about 30% faster than the ......program
2. the figure 0.75 is absolutely no indication of the quality
   of the prolog program or the prolog implementation: the order of the facts
   (or rules) for 'jump' is the most important factor determining the time
   needed to find the (a !) first solution
3. the BIMprogram is really a partially evaluated version of the ......program,
   but not at all less readable ...
   just to give you the flavour:
   
   the 12th startposition is represented by:
   
   	start(12,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1).


   and the 'jump' facts are replaced by rules:
   
   jump(_A,1,_C,_D,1,_F,_G,_H,0,_J,_K,_L,_M,_N,_O,['2 to 9'|_restjumps],_n) :-
        _m is _n - 1,
        jump(_A,0,_C,_D,0,_F,_G,_H,1,_J,_K,_L,_M,_N,_O,_restjumps,_m) .


   the stop condition is :
   
   jump(_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,[],1) .

	/*put at the end and not first, although it is a simple case*/

   and the query to get the first solution from starting position 12 is:
   
   ?- start(12,_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_s),
        jump(_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_jumplist,14) ,
        write(_jumplist) .

4. why is the BIMprogram faster ?

   less ALLOCATE's
   no creation on the heap of new structures; no UNIFY's
   a lot of optimised away GET_'s and PUT_'s
   
   the disadvantage of having longer choicepoints does not outweight the above
   advantages
   
   moreover, a lot less heap and local stack are used !


bimbart@kulcs.uucp		andre@sunbim
Bart Demoen			Andre Marien
Dept. of Computer Science	BIM
Celestijnenlaan 200A		Kwikstraat 4
B-3030 Leuven			B-3078 Everberg
Belgium				Belgium