Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!quintus!ok From: ok@quintus.UUCP (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: Re: triangle puzzle (496-497) Message-ID: <695@cresswell.quintus.UUCP> Date: 26 Feb 88 03:23:21 GMT References: <1153@kulcs.UUCP> Organization: Quintus Computer Systems, Mountain View, CA Lines: 137 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.