Analyse des inférences récursives en PROLOG : système d'aide à la détection et au contrôle de boucles
Institution:
Paris 11Disciplines:
Directors:
Abstract EN:
The declarative and procedural semantic of PROLOG allows it to be in good position among the ether languages of Artificial Intelligence. However, the expressive power of this language may cause undesired effect which cannot be controlled by the programmer like loops in recursive programs. We propose here a programming environment which aims at foreseeing the behavior of a program. It is a system designed for analysis and control of recursive programs which is made up of two parts. The first part performs a static analysis of program. In this part cycles existing in the program clauses are localized. The second part consists in a dynamic evaluation of the program. Its main objective is, either to determine the class of goals for which we can ensure termination of resolution, or to present the cycle schemes which activation may lead to loops. The system may then yield informations on these potential loops. First, it points out their structure, namely the sequence of goals which composes the activated cycle. Secondly, it precise their origin: in other words is a loop caused by a bad instantiation of a goal or is it related to the semantic of the clause. Thirdly, the system informs the user about the possible consequences of loop, that 1s to say, does the loop yield a finite or infinite set of solutions. On the other hand, debugging methods fitted to the nature of the detected loops are interactively proposed to the user. A generalization method, named method of data generalization, allows to extract informations about a loop from the environment in which it is activated.
Abstract FR:
La double sémantique, déclarative et procédurale, de PROLOG lui permet de tenir une place de choix dans le domaine de l'Intelligence Artificielle. Cependant la puissance d'expression de ce langage peut entraîner des effets non désirés et incontrôlés par le programmeur dont une conséquence fréquente est le bouclage de l'interprète sur des programmes récursifs. Nous proposons un environnement adapté dont l'objectif est de prévoir le comportement d'un programme. C'est un système d'analyse et de contrôle des programmes récursifs composé de deux phases. La première correspond à une analyse statique des programmes: on construit les schémas des cycles existants sur les clauses dont l'activation provoque le bouclage de l'interprète. La seconde phase est l'évaluation dynamique des programmes: son rôle premier est d'indiquer les contextes d'appels dont on est certain que l'évaluation termine. Dans les autres cas le système présente les schémas des cycles activés sur le programme qui peuvent conduire à des boucles. Il fournit alors des renseignements précis sur ces boucles potentielles. D'une part, il indique la structure de la boucle, c'est-à-dire l'ensemble des clauses qui composent le cycle activé. D'autre part, il précise l'origine de la boucle: si elle est créée par une instantiation spécifique d'un littéral récursif ou bien si elle est liée à la sémantique des clauses. Enfin, il informe l'utilisateur des conséquences possibles de la boucle, à savoir si elle produit un ensemble fini ou infini de solutions. De plus, des méthodes de traitement adaptées à la nature des boucles détectées sont proposées interactivement à l'utilisateur. Une méthode de généralisation, appelée méthode de généralisation des données, permet d'extraire, de l'environnement dans lequel le bouclage est activé, les informations qui sont significatives pour ce bouclage.