Subject: Re: Inserting clauses

From: Jan Wielemaker <[email-masked]>
Date: Wed, 5 Apr 2000 10:22:42 +0200

On Tue, 04 Apr 2000, Robert van Engelen wrote:
>> 	I've got someone who wants to insert clauses in the middle.
>> 
>> This occasionally came up at Quintus, but there was *never* a good reason
>> for it and it was *always* possible to do something far better when we
>> understood what problem the would-be inserter was really trying to solve.
>> Practically the only known use was in some Prolog systems which had
>> in-core editors, and even those would have been better to work with a
>> data structure and replace the _entire_ predicate at the end.
>
>The reason for having to insert clauses in the middle came up as follows. We
>are building a Prolog interpreter for a small experimental computer algebra
>system. This system compiles transformations into Prolog clauses. Compiling
>them makes it faster compared to interpretation, especially when complex
>conditions are tested. Also the hashing capabilities of SWI-Prolog are
>implicitly exploited this way. Believe me, we did some tests to see whether
>it is faster to store the transformations in a data structure or as clauses
>and we found a significant difference. The insertion of clauses is necessary
>when transformations are added later to a precompiled version of the system.
>Transformations can be added interactively that apply more specific rules
>to terms compared to the precompiled transformations. Consider for example the
>following toy example situation. The system can have transformations
>
>f(a+b) => b.
>f(b+a) => b.
>f(X+X) => g(X).
>
>compiled as clauses. Now when the user wants to extend the term rewriting
>system by adding
>
>f(b+X) => c.
>
>the clause has to be inserted after the first two, but before the last clause.
>I use pattern matching to determine the position of the new clause in the
>clauses. The pattern matching technique is comparable to the techniques
>applied in functional programming languages to order function definitions.

This is clear.

>I implement this in SWI-Prolog by retracting the previous definitions of
>function f, insert the clause in a list of clauses, and assert the clauses
>back. Because the retract and assert are expensive operations, even for a
>moderate term rewriting system this takes a long time (half a minute on a
>fast machine to compile 500 rules). Because the transformations are allowed

This is not.  I did a little test using 647 clauses of a predicate with
arity 3 and bodies with an average of about 5 lines long and it takes
0.04 seconds to retract all clauses are assert them back in.  This on
a 450 Mhz Pentium-II machine running Linux.  I would say a moderate
machine today.

Time to run profile/3 and see where the time is spend.  If updating is
not (almost) linear with the number of clauses you might have hit some
implementation error.  In that case, send the program with instructions.

If the slow speed is caused by very complicated bodies, you could split
the head from the body using a unique identifier and only reshuffle the
heads:

a(...) :- very-complicated-body.

a(...) :- b(UniqueId, ...).
b(UniqueId, ...) :- very-complicated-body.

Now you can shuffle the clauses of a without touching those of b.  If
the body is complicated performance will not be harmed significantly.