Ingeniero

M´ ta-compilation non intrusive du filtrage par contraintes e
Non intrusive meta-compilation of matching by constraints

Sous Projet 1 RETE et r´ ecriture e´
inria-00280938, version 1 - 20 May 2008

Production Systems and Rete Algorithm Formalisation
Description : The rete algorithm is a well-known algorithm for efficiently addressing the many patterns/many objects match problem, and it hasbeen widely used and implemented in several applications, mainly production systems. But despite of the wide usage of production systems and the rete algorithm, to the best of our knowledge there has been just one proposition for a formal definition of the rete algorithm given by Fages and Lissajoux [FL92], but no attempt to give a formal description of production systems as a whole, giving rise tolots of ambiguities and incompatibilities between the different implementations. Therefore, the need for a formalisation is clear and we present in this report a first approach to it, refining Fages and Lissajoux’s approach to fit it in our general model of production systems. Auteur(s) : Horatiu C, Claude K, Michael M, Pierre-Etienne M M / Sous Projet 1 / Fourniture 1.1/ V0.9 31 aout 2004 ˆ a valider ` 0.9

R´ f´ rence : ee Date : Statut : Version :

R´ seau National des Technologies Logicielles e Projet subventionn´ par le Minist` re de l’´ conomie, des finances et de l’industrie e e e ILOG, INRIA Lorraine, INRIA Rocquencourt

M – M´ ta-compilation non intrusive du filtrage par contraintes e

Historique
31 aout 2004 ˆ 15 septembre 2004 V 0.9V1.0 cr´ ation du document e version finale

Contents
1 Introduction to production systems 1.1 Informal presentation of production systems . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivation for a formal description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Formal Description of Production Systems 2.1 General Production systems . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 2.2 Restricted Production systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Formal Abstract Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 The Rete Algorithm 3.1 Informal Description of the Rete Network . . . . . . 3.2 Rete Network Execution for our Fibonacci Example 3.3 Formal Definition of the Rete Network . . . . . . . . 3.4Execution of the Rete Algorithm . . . . . . . . . . . 4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 5 5 5 8 10 12 12 13 15 17 18

inria-00280938, version 1 - 20 May 2008

Projet RNTL : M / Sous Projet 1 / Fourniture 1.1 / V0.9 ILOG, INRIA Lorraine, INRIA Rocquencourt

2M – M´ ta-compilation non intrusive du filtrage par contraintes e

Introduction
The rete algorithm is a well-known algorithm for efficiently addressing the many patterns/many objects match problem. It has been first described in [For74], but it gains in popularity just after publication of [For82] where a more precise description is given. Implementation issues related to this algorithmhave been widely studied [TR89, The90, ´ MBLG90, Alb89, Ish94a], and applications include, for instance, Petri Nets implementations based on the rete algorithm [BB01]. But the most important applications are production systems like OPS5 [X-T88, For81], Clips [CR03], JEOPS [dFFR00], Jess [FH03] and JRules [S.A04]. There are also many specialized production systems, like parallel, distributed,multi-agent and real-time production systems [LG89, Lop87, FL91, Ish94b]. But, despite of all this work around production systems and the rete algorithm, to the best of our knowledge there has been just one proposition for a formal definition of the rete algorithm given by Fages [FL92], but no one for production systems as a whole, giving rise to lots of ambiguities and incompatibilities between the...