rete implementation in swi-prolog

[Dan]

Hello, 

Does there exist an open implementation of the rete algorithm for swi-prolog

thanks,

Dan

[Peter Ludemann]

http://www.amzi.com/ExpertSystemsInProlog/05forward.php

http://www.amzi.com/ExpertSystemsInProlog/08performance.php

I recall a conversation with some people at DEC about their RETE-based system that was used for configuring VAXes ... apparently it took a team of 5 or so people to maintain it and it became almost impossible to maintain with more than 150 rules.

(This memory might be wrong -- see https://en.wikipedia.org/wiki/Xcon )

(Or, it could be two different definitions of "rule")

In the early 1990s, I looked into configurators and concluded that it was easier to implement them in Prolog than with a forward-chaining system; but I did little more than some proof-of-concept implementation. YMMV.

--
You received this message because you are subscribed to the Google Groups "SWI-Prolog" group.
To unsubscribe from this group and stop receiving emails from it, send an email to swi-prolog+...@googlegroups.com.
Visit this group at https://groups.google.com/group/swi-prolog.
For more options, visit https://groups.google.com/d/optout.

[Dan]

thanks, 

 its good to see an example. 

It seems to me that rete is further optimized in the manner the rule clauses are arranged ...

I am also wondering, why in OPS5 its important to narrow down the triggering of a rule to one -- why can't all the rules be fired, perhaps orderd by specificity, from most to least specific -- it would be up to the rule design to ensure that there are no overlaps, i guess. 

Dan

[Peter Ludemann]

On Sat, 8 Sep 2018 at 16:12, Dan <gros...@gmail.com> wrote:

thanks, 

 its good to see an example. 

It seems to me that rete is further optimized in the manner the rule clauses are arranged ...

I am also wondering, why in OPS5 its important to narrow down the triggering of a rule to one -- why can't all the rules be fired, perhaps orderd by specificity, from most to least specific -- it would be up to the rule design to ensure that there are no overlaps, i guess. 

There's no backtracking in RETE, so the "best" rule is chosen to fire. I think that if all applicable rules were fired, there would be an exponential increase in the data. Also, it's difficult enough to understand the behaviour when single-firing; if all were fired, it would be even more difficult to understand. (And some rule firings would invalidate other matches, so could result in inconsistencies?)

For the R1/XCON configurator, I suspect that a constraint-based design would be more effective (I don't think that constraint solving was very advanced back then). For other applications, something like Linda is probably cleaner.

But others are probably more knowledgeable on this than I am.  (And backward-chaining has sufficed for most things that I've worked on)

- peter

[Dan]

Hi, 

Thank you for the explanation. 

I am considering the use of rete as a basis for truth maintenance -- it seems to me that rete would be efficient for that. 

Dan

[Peter Ludemann]

Apparently there is a newer, faster version of RETE.

https://en.wikipedia.org/wiki/Rete_algorithm#Rete-NT

RETE has always seemed complex to me; perhaps something similar would be better for truth maintenance?

There's a hint here: https://en.wikipedia.org/wiki/Constraint_Handling_Rules#Execution_of_CHR_programs

To decide which rule should "fire" on a given constraint store, a CHR implementation must use some pattern matching algorithm. Candidate algorithms include RETE and TREATS, but most implementation use a lazy algorithm called LEAPS.^[9]  

[Dan]

Hi Peter, 

Thank you. 

I read the Rete thesis, and its actually quite nice. I like the idea that the Rete algorithm doesn't work on the knowledge store itself, but only via the Add/Remove actions of product rules. 

And, that the LHS of production rules are essentially "compiled" into the Rete graph thereby making execution time more efficient. I am trying to avoid Lazy evaluations, if possible.

I started looking at LEAPS and TREAT as well ...

thank you

Daniel

[Dan]

a really nice master thesis, summarizing various matching works ...

https://swa.informatik.uni-hamburg.de/files/abschlussarbeiten/Diplomarbeit_Eryk_Lagun.pdf