debray@arizona.edu (Saumya Debray) (07/13/88)
In article <6899@burdvax.PRC.Unisys.COM>, dowding@macbeth.PRC.Unisys.COM (John Dowding) writes: > I did some experiements ... and found that it slowed the > program down. I think that this is because current Prolog compilers > dont handle very large clauses well. Consider this example: > > p(X):- q(X), r(X), s(Y). > % ^^^ author probably meant s(X) -- skd > q(tree(_,_,_,_)). > > If we turn q into a macro, then the resulting clause for p is: > > p(tree(A,B,C,D)):- r(tree(A,B,C,D)), s(tree(A,B,C,D)). The problem, as the author points out, is that the compiler isn't factoring common subterms. As a result, multiple copies of the same structure are being created on the heap. Factoring common subterms in this example would give p(X) :- X = tree(_,_,_,_), q(X), s(X). While common subterm factoring looks very attractive, one problem with doing it incautiously is that indexing capabilities can be weakened because a nonvariable term is being pulled from the head into the body (as in the above example). The resulting choice point creation may well wipe out any benefits obtained from creating fewer structures on the heap. Some years back, I looked at incorporating common subterm factoring into the SB-Prolog compiler. My experience was that people (well, OK, Prolog hackers who were at Stony Brook at the time) didn't usually write code with a lot of common subterms to be factored. This, together with the complications arising from having to make sure that indexing didn't suffer from such factoring, made the cost of common subterm factoring unattractive. The current SB-Prolog compiler therefore does only a limited form of common subterm factoring: the clause p(f(a,b)) :- q(f(a,b)), r(f(a,b)). is compiled with three copies of the term f(a,b), but the clause p(f(g(a))) :- q(h(g(a))), r(f(g(a))). is compiled as p(f(X)) :- X = g(a), q(h(X)), r(f(X)). -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray
chik@icot21.icot.junet (Chikayama Takashi) (07/13/88)
debray@arizona.edu (Saumya Debray) writes: > While common subterm factoring looks very attractive, one problem with > doing it incautiously is that indexing capabilities can be weakened > because a nonvariable term is being pulled from the head into the body > (as in the above example). The resulting choice point creation may well > wipe out any benefits obtained from creating fewer structures on the heap. I see no reason why the compiler cannot index clauses properly. This may be true if factoring should be done in the source level BEFORE the compilation. However, the compiler can be as clever as generating indexing code based on the original source program and then factorize common structures when generating each clause. By the way, the PSI machine has an extended WAM instructions named "get_structured_constant" and "put_structured_constant". These have two arguments, an argument register and a pointer to a structure allocated in the CODE AREA in the compilation (or rather, program loading) phase. Its spec is similar to "get_value" or "put_value" except that one of the arguments is a constant structure. The same applies to the "unify_structured_constant" instruction. Consider, for example, a predicate such as: roman(N, R) :- arg(N, f(i, ii, iii, iv, v, vi, vii, viii, ix, x), R). Using only the original WAM instructions, it will be compiled to something like: put_value A2, A3 put_functor f/10, A2 unify_constant i unify_constant ii ... unify_constant x execute arg/3 which is, at least to me, never acceptable. Of course, the call to the built-in predicate arg/3 may be compiled out, but I'm not interested in it here. The "put_structured_constant" instruction can substitute the put_functor instruction and 10 following unify_constant instructions. For this specific example, writing the predicate as: roman(1, i). roman(2, ii). ... roman(10, x). may do almost as good, but the first program looks more compact and probably more efficient when "put_structured_constant" is used. Using this, if there are many common structures, the same structure in the code area can be shared, minimizing the code size. It won't help, however, when the common structure contains variables. T.Chikayama (ICOT)
micha@ecrcvax.UUCP (Micha Meier) (07/14/88)
In article <6206@megaron.arizona.edu> debray@arizona.edu (Saumya Debray) writes: > ... the clause > > p(f(g(a))) :- q(h(g(a))), r(f(g(a))). > >is compiled as > > p(f(X)) :- X = g(a), q(h(X)), r(f(X)). >-- I have also thought about factoring common terms, however it seems to me that recognizing them can become *very* costly, especially when many lists occur in the clause, or do you have some clever algorithm? On the other hand, it is possible to factor out even the top-level compound term from the head, you only have to remember its reference in a variable when the indexed argument is unified; this, of course, cannot be done using a source-to-source transformation, it must be done inside the compiler: p(f(X)) :- q(f(X)), r(f(X)). ... switch_on_functor A1, ... ... get_variable Y1, A1 % so Y = f(X) is part of the head get_structure f/1, A1 unify_variable Y2 call q/1 % no instruction necessary, anyway put_value Y1, A1 deallocate execute r/1 --Micha
chik@icot21.icot.junet (Chikayama Takashi) (07/15/88)
In article <561@ecrcvax.UUCP> micha@ecrcvax.UUCP (Micha Meier) writes:
I have also thought about factoring common terms, however it seems
to me that recognizing them can become *very* costly, especially
when many lists occur in the clause, or do you have some
clever algorithm?
The cost is expected to be not much more than linear with the size of
the program. You can compute some hash function for all the
structures occurring in a clause, and register them in a hash table.
On registration, occurrences of the same structure appeared before can
be recognized.
The cost for computing the hash function can be linear with the size
for the lowest level structure. If the hashing function is designed
so that the hash value for upper-level structure only depends on the
hash value of its elements, total cost for computing the hash function
is still linear (you don't have to recompute for elements).
The cost for registration is constant when the same structure is _not_
already in the table, as far as the hash table is not too densely
populated and the hashing function is designed properly to avoid too
many accidental collisions. When the same structure is already there,
matching takes cost proportional to the size of the structure. Thus,
in the worst case, the total cost is proportional to square of the
clause size. However, as this _worst_ case is the _best_ case for
common subterm factoring, it pays off, doesn't it?
If your compiler is written in a language in which efficient hashing
is difficult, such as _standard_ Prolog, it's a thousand pities :-)
T.Chikayama