Génération Automatique d'Algorithmes de Filtrage à partir de Spécifications Déclaratives : le Système GAP

F. DERROUGH

IBP-Masi 1994/Th07: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Masi / Masi research reports
313 pages - Novembre/November 1994 - French document.

PostScript : Ko /Kb

Titre / Title: Génération Automatique d'Algorithmes de Filtrage à partir de Spécifications Déclaratives : le Système GAP

Résumé : Le filtrage est un mécanisme qui permet de déterminer les règles candidates au déclenchement à chaque cycle du moteur en éliminant les règles dont au moins une condition n'est pas satisfaite. L'instanciation des règles n'est alors effectuée que sur les règles qui ont franchi l'étape de filtrage avec succès. Dans les systèmes classiques, les moyens mis en oeuvre pour réaliser le filtrage sont simples. Cela est dû principalement à la nature des conditions qui sont autorisées en prémisses de règles. En règle générale, ces conditions décrivent de manière générique les éléments de la mémoire de travail.
Nous nous sommes intéressés à la génération automatique d'algorithmes de filtrage à partir de spécifications déclaratives. Dans notre étude, nous avons considéré des conditions de règles complexes qui sont des formules de la logique des prédicats du premier ordre avec les quantificateurs existentiels et universels dans n'importe quel ordre.
Notre méthode de génération automatique des algorithmes de filtrage repose sur la différentiation ensembliste que nous avons définie en tenant compte à la fois des aspects qualitatifs et quantitatifs. La différentiation ensembliste qualitative nous permet d'éliminer les directions vers lesquelles les ensembles ne peuvent varier. Dans la génération des algorithmes de filtrage, ces informations de nature qualitative nous ont permis de conclure immédiatement dans certaines situations. La connaissance des différentielles qualitatives des ensembles nous évite également de calculer des différentielles quantitatives d'expressions ensemblistes composées qui s'avèrent vides.
Nous avons développé un prototype, le système qui se compose d'un module de génération et d'un module de réécriture. Ce dernier permet de simplifier les expressions contenues dans les algorithmes engendrés.

Abstract : Rule filtering is a mechanism which determines the rules that are potentially firable at each inference engine cycle by eliminating those having at least one non satisfied condition element. Rule instantiation is then performed on rules which have successfully crossed the rule filtering step. In classical systems, means needed for implementing rule filtering are simple. This is essentially due to condition elements allowed in the left hand sides of rules. Generally, these condition elements are generic descriptions of working memory elements.
We are interested in the automatic generation of filtering algorithms from a declarative specification. In our work, we consider complex condition elements which are first order predicate formulas with existential and universal quantifiers in any order.
Our method of automatic generation of filtering algorithms relies on set differentiation. We have studied both qualitative and quantitative aspects of set differentiation. Qualitative set differentiation allows us to eliminate directions in which sets cannot vary. In the generation of filtering algorithms, qualitative information allows us to immediately conclude in many situations. Knowing qualitative set differentials avoids us to compute quantitative differentials of composed set expressions that are in fact empty.
We have developed a prototype, the system GAP which is composed of two modules: the generation module and the rewriting module. The goal of the rewriting module is to simplify expressions contained in the generated algorithms.

Publications internes Masi 1994 / Masi research reports 1994