Re: Survey of indexing features for dynamic clauses

On Thu, 30 Aug 2007 11:39:03 -0400, Neng-Fa Zhou wrote:


More than 15 years ago, inspired by the RETE algorithm I came up with an
indexing scheme called matching trees. This scheme has been in B-Prolog for
many years for compiling static clauses. To assist the compiler in building
multi-level matching trees the user is required to either give mode
declarations or write programs in matching clauses which are very similar to
clauses in committed-choice languages.

I would like to understand this better. RETE is about two things (as
far as I know and understand it). The indexing part (which I thought was
run-off-the-mill database style lookup, possibly enhanced with things also
known in the Prolog context - see the references I posted earlier - for
multiple or structured arguments) and the part which keeps incrementally
the join of a subset of heads of rules in a production rule.

The joining part does not really transpose to Prolog execution, unless one
is prepared to treat conjunctions of Prolog goals in a new way. As far as
I know, B-Prolog (or any other Prolog system) doesn't do that.

If by chance one comes across the ideas in RETE indexing BEFORE one learns
about database indexing (+ the aforementioned enhancements for Prolog) one
could think that RETE has something to add to Prolog indexing. But I
learned it chronologically the other way around, and that's why I thought
that RETE has nothing to add to Prolog indexing.

Perhaps I always missed something essential here and I would like to
learn what exactly, now that I am not yet too old :-)

I would also like to understand the relation with Mercury better: Mercury
requires mode declarations (or must be able to derive them), and for input
arguments does matching (without changing the semantics, because proven at
compile time). To what extend are Mercury input unification, matching
trees in B-Prolog, RETE interrelated ?

I really thought I understood all this, but the recent posts make me doubt
I do.

Cheers

Bart Demoen
.

Relevant Pages