🚀 go-pugleaf

In article <1153@kulcs.UUCP>, bimbart@kulcs.uucp (Bart Demoen) writes:
> 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.

Do you get the idea that he might be talking about me?  I did.
News for you, playmate:  I don't name BIM Prolog because I haven't
anything to say about it.  I have had some nasty things to say about
various Prolog implementations in this newsgroup, and to avoid legal
trouble, have avoided naming names.  If the people at BIM thought it was
their implementation which I have been criticising all along, I can only
say that I regret that they found this credible.  Here is my personal
assurance:  I do not recall intending to criticise BIM Prolog or its
implementors in this newsgroup in the last year.  If I have something
good to say about BIM Prolog, I shall certainly name it!

> 1. how easy is it to write a program that is faster than the ......program and
>    still readable

Readability is to some extent in the eye of the beholder.
I find something like this

>    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) .

about as readable as a hex dump, whereas the same thing expressed as

jump(			A,
		      1,  C,
		    D,  1,  F,
		  G,  H,  0,  J,
		K,  L,  M,  N,  O,	['2 to 9'|Jumps], Count0) :-
	Count is Count0-1,
	jump(		A,
		      0,  C,
		    D,  0,  F,
		  G,  H,  1,  J,
		K,  L,  M,  N,  O,	Jumps, Count).

conveys quite clearly what is going on.  The triangular layout is
specific to this particular problem:  it is important to be able 
to SEE the jump (look for a line of numbers) so that you can check it.
The human eye is reasonably good at detecting straight lines; it is
not so good at seeing the same pattern in the flattened layout Demoen
(and Covington et al) used.  This is in fact the best example I have
ever seen to prove that a rigid layout style (such as I normally
advocate) is not always a good idea.

Why didn't I do this in the first place?  As Bart Demoen says:

> 3. the BIMprogram is really a partially evaluated version of the ......
>    program ...

Quite right.  However, the Covington et al book appears to be aimed at
micro-computer users.  (Special attention is given to Arity Prolog and
Turbo Prolog.)  One of the nicer Prologs on micro-computers is ALS Prolog,
which had a limit of 14 or 15 arguments to a predicate the last time I
looked.  The partially executed version has 17 arguments.  I would look
remarkably silly advising Covington et al's readers to do something
they COULDN'T do, wouldn't I?  (I assume that many readers of this
newsgroup are trying to use Prolog on PCs.  I think it's fair enough
for me to suggest things that I know will work in one affordable PC Prolog.)

> 1. the BIMprogram is systematically about 30% faster than the ......program

I'm not surprised that the improvement is so slight.  I have often found that
it wasn't worth the bother of unpacking a record.  This is about as good as
it gets.

> 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

Wrong.  It is correct that the order of the facts in the jump table is the
most significant thing.  That's why in my version of the program I was
careful to use exactly the same order of jump facts as Covington et al did.
I went through a back-of-an-envelope proof that my program searched the
same tree as theirs in the same order.  With that held constant, the time
IS an indication of the quality.  For example, Demoen's unfolded version
IS 30% faster than my version, and that DOES mean something.

> 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 outweigh the above
>    advantages
>    
>    moreover, a lot less heap and local stack are used !
> 

We can put it in less implementation-oriented terms.
The version that looked like
	driver(...) :- ...
	driver(...) :- jump(...), driver(...)

	jump(#, f(...), f(...)).
did three things at every step that Demoen's program doesn't.

(1) There was an extra procedure call driver->jump.
    The "clausal join" of driver with jump avoids this.
    This I take the "less ALLOCATEs" to mean.

(2) jump had to unpack the first f().  The joined version doesn't.
    This is the "no UNIFYs" bit.

(3) jump had to pack the second f() back together.  The joined
    version doesn't.  This is the "no creation on the heap" bit.

These are general features of this kind of unfolding.

There is another point.  I explicitly wanted to represent jumping
as a relation between two states.  With my program, it was possible
for me to ask questions like
    "how many solutions of jump(_,X,Y), jump(_,Y,Z) are there?"
    "how many solutions of jump(_,X,Y), jump(_,Y,Z), jump(_,Z,W)?"
It seemed plausible that it might be profitable to precompute a table
of two-step jumps and then search two jumps at a time.  It would also
be possible to make a table of *final* states and work backwards from
it, producing a table of all the states 3 (say) steps from the end.
One could then switch over to that table at the end.

This kind of change is also a form of partial execution.  The kind of
partial execution exemplified by Bart Demoen's program buys you a
constant factor (30% is not to be sneezed at), but that's all.  Doing
computations like double-stepping and backwards analysis from can buy
you an exponential speedup in some problems.  One of the things I was
trying to get across in my message about the triangle program (apart
from things like the importance of layout in making it easier to check
ones tables...) was this point about making more of a program
declarative so that this sort of "high-leverage" partial execution can
be done.