bimbart@kulcs.uucp (Bart Demoen) (08/29/88)
Tutorial No:8 of LP'88 Seattle (R. O'Keefe) makes 'interesting' reading, but be careful not to believe everything without checking it on the system you use; here is an example Section 14 p.159 talks about the foreign interface. It uses gen_symcount/2 as an example of what you should use the foreign interface for instead of Prolog. I took the Prolog version mentioned in the tutorial, the version using the foreign interface mentioned in the tutorial (corrected and adapted to BIMprolog) and I wrote a version in 'pure BIMprolog'; you find them here, suffixed with C, B and OK C version --------- :- extern_load([make_counter,increment_counter] , ['t.o']) . :- extern_predicate(make_counter(pointer : r)) . :- extern_predicate(increment_counter(integer : r , pointer : i)) . get_next_gensym_counterC(_prefix,_count) :- gen_symcount(_prefix,_pcount) , ! , increment_counter(_count,_pcount) . get_next_gensym_counterC(_prefix,_count) :- make_counter(_pcount) , assert(gen_symcount(_prefix,_pcount)) , _count = 1 . unfortunately, I had to change the C code as it stands in the tutorial; perhaps Qprolog is interfacing to some other C ? long *make_counter() { register long *p = (long *)malloc(sizeof *p) ; *p = 1 ; return(p) ; /*WAS MISSING IN THE TUTORIAL this goes right on SUN3 - d0 still contains the return value of malloc - but on VAX this goes wrong see also comp.lang.c these days: topic QuickC */ } long increment_counter(p) register long *p ; { (*p)++ ; /*IN THE TUTORIAL VERSION, THIS WAS: *p++ ; DOING THE SAME AS *(p++) WHICH IS WRONG */ return(*p) ; } BIMprolog version ----------------- get_next_gensym_counterB(_prefix,_count) :- assoc(_prefix,_key) , ! , recorded(_key,_old_count) , _count is _old_count + 1 , rerecord(_key,_count) . get_next_gensym_counterB(_prefix,_count) :- make_key(_prefix,_key) , assert(assoc(_prefix,_key)) , rerecord(_key,1) , _count = 1 . make_key(_prefix,_prefix) . % this could be a more involved predicate, but since % it is only called once, that's not going to make % a big difference Prolog tutorial version ----------------------- get_next_gensym_counterOK(_prefix,_count) :- retract(gen_symcount(_prefix,_old_count)) , ! , _count0 is _old_count + 1 , assert(gen_symcount(_prefix,_count0)) , _count = _count0 . get_next_gensym_counterOK(_prefix,_count) :- assert(gen_symcount(_prefix,1)) , _count = 1 . the timings for 10000 calls to get_next_gensym_counter*(a,_x) (on a SUN 3/50) in seconds: C OK B ------------------- 5.8 30.4 4.9 (the loop overhead of 0.8 sec was not subtracted) gensym is clearly a case in which the foreign interface should NOT be used ... as the BIMprolog manual states: the use of the external interface entails some overhead, resulting in slower programs when using an external routine for a short job in the same section, the tutorial makes the general statement: 'If you need global variables, you might as well implement them in a language which is good at them.' (meaning not Prolog, I suppose). This is not true. Prolog has already the record predicates to do that. bimbart@kulcs.uucp Bart Demoen Dept. of Computer Science Celestijnenlaan 200A B-3030 Leuven Belgium
ok@quintus.uucp (Richard A. O'Keefe) (08/30/88)
In article <1415@kulcs.kulcs.uucp> bimbart@kulcs.UUCP (Bart Demoen) writes: >Tutorial No:8 of LP'88 Seattle (R. O'Keefe) makes 'interesting' reading, but >be careful not to believe everything without checking it on the system >you use; here is an example > How 'kind' of you. The example in question is introduced with the sentence "Here is a good example of a crutch using Quintus Prolog." ^^^^^^^^^^^^^^^^^^^^ Nothing is claimed about the performance of the method in any other Prolog. Demoen cites the following times in seconds using BIM Prolog on a Sun 3/50: > C OK B > ------------------- > 5.8 30.4 4.9 If I understand correctly, C = the foreign interface version, adapted from my tutorial OK = the 'assert' version, adapted from my tutorial B = the 'rerecord' version, written by Demoen. It is something of a relief to find that Demoen reports that using the foreign interface *is* faster than using 'assert', by a fairly large factor. We have an old BIM Prolog manual, but I don't know where it is and it's 10pm, so there's no-one else to ask. I take it that rerecord(Key, Datum) is a BIM Prolog feature which acts like conventional assignment. Other versions of Prolog would have to pick up the old assignment and delete it using recorded/3 and erase/1, which might easily treble the time, or they might have some other method of their own. It came as a further relief to find that the foreign interface version, using Quintus Prolog on a Sun 3/50, took 4.6 seconds, so that my claim that this kind of thing is best done *in Quintus Prolog* via the foreign interface stands up. (Loop overhead was subtracted out of *none* of these figures.) rerecord/2, however efficient it may be, has the problem that the 'recorded' data base is a global resource (that, at least in DEC-10 Prolog, is one of the things it is _for_). If you use the 'recorded' data base to hold gensym counters, you can't use it for anything else. Neither of the two methods described in my tutorial interferes with other uses of any global resource. Demoen found two mistakes in the C code: return p; /* Missing from make_counter() */ ++*p; /* in increment_counter(), had been *p++ */ The first worked by accident in the compiler I was using, the second made no difference to the timings. He kindly refrained from comment on an equally serious mistake, which was that the result of malloc() was being dereferenced without checking that it wasn't NULL, but that one was deliberate sloppiness. Would anyone finding mistakes in any draft of the tutorial please send me E-mail, in case I miss comments sent here? (Please refer to section names rather than page numbers; page numbers change a lot from draft to draft.)
bimbart@kulcs.uucp (Bart Demoen) (08/30/88)
Tutorial No:8 of LP'88 Seattle (R. O'Keefe) makes 'interesting' reading, but don't think that the topics were completely exhausted; here is an example: Section 9 p.106 shows some meta-interpreters and their timings on naive reverse. A very simple change in the representation of the program to be interpreted, gives a much better speed improvement than from defaulty (4.6 KLips) to rule/3 (5.5 KLips) I based my measurements on rule/2, so instead of representing the nrev program as: rule(append([],_l,_l),[]) . rule(append([_x|_l1],_l2,[_x|_l3]),[append(_l1,_l2,_l3)]) . rule(nrev([],[]),[]) . rule(nrev([_x|_r],_o),[nrev(_r,_o1) , append(_o1,[_x],_o)]) . do it as: rule(append(_x,_y,_z),_b) :- append(_x,_y,_z,_b) . rule(nrev(_x,_y),_b) :- nrev(_x,_y,_b) . append([],_l,_l,[]) . append([_x|_l1],_l2,[_x|_l3],[append(_l1,_l2,_l3)]) . nrev([],[],[]) . nrev([_x|_r],_o,[nrev(_r,_o1) , append(_o1,[_x],_o)]) . and the KLips went up from 5.2 to 7.2 (on a SUN3/50 BIMprolog 2.3) in this way, you regain the indexing lost previously This is not the topspeed in meta-interpreting nrev: 10 KLips is also reachable. bimbart@kulcs.uucp Bart Demoen Dept. of Computer Science Celestijnenlaan 200A B-3030 Leuven Belgium
bruno@ecrcvax.UUCP (Bruno Poterie) (09/05/88)
In article <1416@kulcs.kulcs.uucp> bimbart@kulcs.UUCP (Bart Demoen) writes: >Tutorial No:8 of LP'88 Seattle (R. O'Keefe) makes 'interesting' reading, but [...] >instead of representing the nrev program as: > >rule(append([],_l,_l),[]) . >rule(append([_x|_l1],_l2,[_x|_l3]),[append(_l1,_l2,_l3)]) . > >rule(nrev([],[]),[]) . >rule(nrev([_x|_r],_o),[nrev(_r,_o1) , append(_o1,[_x],_o)]) . > >do it as: > >rule(append(_x,_y,_z),_b) :- append(_x,_y,_z,_b) . >rule(nrev(_x,_y),_b) :- nrev(_x,_y,_b) . > >append([],_l,_l,[]) . >append([_x|_l1],_l2,[_x|_l3],[append(_l1,_l2,_l3)]) . > >nrev([],[],[]) . >nrev([_x|_r],_o,[nrev(_r,_o1) , append(_o1,[_x],_o)]) . This may be alright if you seek only efficieny, but: o you cannot use rule/2 for clause retrieval anymore o you increase the size of your database by a non-neglectable factor o you fill up your dictionnary with functors (append/0,append/3,append/4) o you cannot apply this method for the code of the interpret itself, which imply that you have to enter *by hand* the rules for it, destroying partly the interest of the method which was to show that a meta-interpret is a normal prolog program working on normal prolog code in an automatic way, including on itself. So let us keep the name rule/2 for a 'data' representation of the clauses, and use instead another name for this 'executable' representation ... say, exec/2 ??? [it doesn't matter, after all ;-)] There are anyway 2 problems linked with this list representation: (which, by the way, is actually *used* as the internal representation, the basis for the interpretor, and the output of clause/2, by at least one Prolog for PC & up: XILOG (from Bull), which happens to be one of the fastest in its category!). The first one is the representation of if-then-else [ A -> B ; C ]: should the sub-sequences (A,B & C) be themselves sub-lists, with ->/2 & ;/2 built-in inside the meta-interpret, and this, reccursively; or kept as terms? In this case, the code for ;/2 should first transform its argument into a list of goals, before returning control to the meta-interpret (see point 2). The second problem is the metacall: When called, the metacall (call/1) have first to analyse its parameter, transform it into a list of goals, and then pass it to the meta-interpret. This may be costly, and imply as well that any variable in a goal position inside a term being analysed and transformed has to be replaced by a: call(Variable), even if the term is to instantiate to a very simple subgoal, in order to ensure the transformation at run-time. Moreover, it implies that call/1 has to be tightly connected with the meta-interpret (because you can always use it explicitely), unless we use it as a sort of escape to the real Prolog engine :-? After all, time is not the *main* constraint for a meta-interpret, cut and bips are more of a problem! ================================================================================ Bruno Poterie # ... une vie, c'est bien peu, compare' a un chat ... ECRC GmbH # tel: (49)89/92699-161 Tx: 5 216 910 Arabellastrasse 17 # usenet: bruno%ecrcvax.UUCP@Germany.CSNET D-8000 MUNICH 81 # or: bruno%ecrcvax.UUCP@pyramid.pyramid.COM (from USA) West Germany # uucp: ...!mcvax!unido!ecrcvax!bruno EUROPE # or: ...!pyramid!ecrcvax!bruno (from USA) ================================================================================