dowding@ai.sri.com (John Dowding) (11/17/90)
I was poking around in some old code, and came across the following clauses (names changed to protect the inocent): foo(Term, Term):- (var(Term) ; atomic(Term)), !. foo([Head|Tail], Result):- ... I was wondering if the following is more efficient: foo(Term, Term):- var(Term), !. foo(Term, Term):- atomic(Term), !. foo([Head|Tail], Result):- ... Are Prolog compilers (particularly, Quintus version 2.4) smart enough index correctly on the 1st argument in either or both of these cases? Thanks, John Dowding dowding@ai.sri.com
zhou@hiromi.csce.kyushu-u.junet (Neng Fa Zhou) (11/20/90)
In article <DOWDING.90Nov16140150@palm.ai.sri.com> dowding@ai.sri.com (John Dowding) writes: > I was poking around in some old code, and came across the following > clauses (names changed to protect the inocent): > > foo(Term, Term):- > (var(Term) ; atomic(Term)), > !. > foo([Head|Tail], Result):- > ... > > > I was wondering if the following is more efficient: > > foo(Term, Term):- > var(Term), > !. > foo(Term, Term):- > atomic(Term), > !. > foo([Head|Tail], Result):- > ... Yes, it is more efficient than the original one. > > Are Prolog compilers (particularly, Quintus version 2.4) smart enough > index correctly on the 1st argument in either or both of these cases? > The compiler for the TOAM is smart enough to compile this program to efficient code. The compiler first infers modes for a program, then transforms the program to a canonical form based on the inferred modes. Suppose [d,f] is the mode of foo/2, the canonical form of the predicate is foo(Term, NewTerm):- var(Term), !, NewTerm = Term. foo(Term, NewTerm):- atomic(Term), !, NewTerm = Term. foo([Head|Tail], Result):- ... The code of this canonical form is efficient because (1) no choice point will be created, and (2) it does not contain instructions for the cuts. Neng-Fa Zhou Kyushu University
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (11/23/90)
In article <DOWDING.90Nov16140150@palm.ai.sri.com>, dowding@ai.sri.com (John Dowding) writes: > I was wondering if the following is more efficient: > > foo(Term, Term):- > var(Term), > !. > foo(Term, Term):- > atomic(Term), > !. > foo([Head|Tail], Result):- > ... There is only one way to tell: MEASURE IT AND SEE. I am profoundly suspicious of a piece of code which tests for var, atomic, and then list. I suspect that there are far grosser efficiency issues to worry about. If it calls (=..)/2 you should eliminate that _first_. > Are Prolog compilers (particularly, Quintus version 2.4) smart enough > index correctly on the 1st argument in either or both of these cases? *CORRECTLY* yes, in that the code will work. Was QP2.4 first-argument indexing aware of type tests? No. Should you worry about that? It all depends on what the rest of your code is like: if you have calls to univ (=..) in there, you have more important things to worry about. -- I am not now and never have been a member of Mensa. -- Ariadne.
mattias@arnold.csd.uu.se (Mattias Waldau) (11/26/90)
In article <ZHOU.90Nov20145919@hiromi.csce.kyushu-u.junet> zhou@hiromi.csce.kyushu-u.junet (Neng Fa Zhou) writes: In article <DOWDING.90Nov16140150@palm.ai.sri.com> dowding@ai.sri.com (John Dowding) writes: > I was poking around in some old code, and came across the following > clauses (names changed to protect the inocent): > > foo(Term, Term):- > (var(Term) ; atomic(Term)), > !. > foo([Head|Tail], Result):- > ... > > > I was wondering if the following is more efficient: > > foo(Term, Term):- > var(Term), > !. > foo(Term, Term):- > atomic(Term), > !. > foo([Head|Tail], Result):- > ... Yes, it is more efficient than the original one. > > Are Prolog compilers (particularly, Quintus version 2.4) smart enough > index correctly on the 1st argument in either or both of these cases? > The compiler for the TOAM is smart enough to compile this program to efficient code. The compiler first infers modes for a program, then transforms the program to a canonical form based on the inferred modes. Suppose [d,f] is the mode of foo/2, the canonical form of the predicate is foo(Term, NewTerm):- var(Term), !, NewTerm = Term. foo(Term, NewTerm):- atomic(Term), !, NewTerm = Term. foo([Head|Tail], Result):- ... This canonical form was probably what the original program should have looked like anyway. The intension was probably that the first clause should have been the only that should have be applicable if the first argument is a variable. However, the call :-foo(X,frobozz) matches the last clause, which is probably wrong. It is a very common error to write the clause bar(X,X) :- foo(X), !. instead of the clause bar(X,Y) :- foo(X), !, X=Y. The last program is more efficient, since the unification X=Y is only done if the predicate foo(X) before the cut succeeds. If foo is a predicate like atomic, var... the indexing of SICStus will make the program above very efficient. (I also believe that SICStus will expand the disjunction into two clauses.) -- Mattias Waldau Computing Science Department mattias@emil.csd.uu.se P.O. Box 520, S-751 20 Uppsala, Sweden Phone: +46-18-181055