Subject: Re: Inserting clauses

From: Robert van Engelen <[email-masked]>
Date: Tue, 4 Apr 2000 16:58:48 -0400 (EDT)

> 	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.

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
to be defined anywhere in a transformation file and also over multiple
files, it would be a pain to collect them and insert them in the right order.

> 	Anyone around with strong feeling on whether or not to add such a
> 	beast to the system, and if yes, name and semantics?

It would at least help me tackle the inefficiency beast of repeated
retract/asserts.

> I am strongly opposed because I have never yet seen a clean design.
> Anything that says "insert in the middle" has to say _where_ in the
> middle.  Some of the ways are
> 
>     assertn(N, Clause)
> 	assert Clause as the Nth clause of its predicate.
> 	What if N < 1?  What if N-1 > #clauses(predicate_of(Clause))?
> 
>     assert_after(DbRef, Clause)
> 	assert Clause just after the clause identified by DbRef.
> 	What if DbRef identifies a record, not a clause?
> 	What if the thing DbRef used to point to has been erased?
> 	What if DbRef points to a clause in a different predicate?
> 	How do you use this to insert into an empty predicate?
> 
>     assert_after(OldClause, NewClause)
> 	assert Clause just after the last clause equivalent to OldClause,
> 	pretending that there is such an equivalent clause just before
> 	the first real clause of the predicate.
> 	What if OldClause and NewClause belong to different predicates?
> 	I broke the tie by choosing the last such clause, but that's
> 	arbitrary; why not the first such clause?
> 	Just how hard should you work to tell if two clauses are
> 	equivalent anyway?  Do
> 	    assert_after((p :- q, (r, s)), X)
> 	and
> 	    assert_after((p :- (q, r), s), X)
> 	always do the same thing, sometimes do the same thing, or
> 	never do the same thing?  (If they never do the same thing,
> 	some implementations that wanted to flatten clauses for
> 	good reason can't; if they always do the same thing, some
> 	implementations that wanted NOT to flatten clauses, for
> 	good reason, must; if they only sometimes do the same thing
> 	the operation is too unreliable to use).
> 

What about the following:

To insert a clause before an exising clause referenced by Reference:

asserta_at(+NewClause, ?Reference, ?NewReference)

To insert a clause after an exising clause referenced by Reference:

assertz_at(+NewClause, ?Reference, ?NewReference)

NewReference is the reference of the new clause. When Reference is not
instantiated, we have the usual semantics of assert:

asserta(C, R) :- asserta_at(C, _, R).
assertz(C, R) :- assertz_at(C, _, R).

Also, one can add the capability to override an existing clause by using

asserta_at(C, R, R).

that enforces the new reference to be identical to the old reference, hence
overriding an old definition.

Maybe the suffix _at can be removed from the predicate name. Would that be
acceptable?

Robert

-- 
   Robert van Engelen: Assistant Professor, Computer Science Department
   Florida State University, 206 Love Bldg., Tallahassee, FL32306-4530
   Offices: 150C DSL/101B MCH, (850)645-0309/644-9661, Fax: (850)645-0300
   Email: [email-masked], URL: http://www.cs.fsu.edu/~engelen