Abstract FR:

La motivation premiere de ce travail est la realisation d'un evaluateur de programmes logiques respectant le paradigme declaratif de la programmation en logique (principalement la completude des reponses). Cet evaluateur, appele dyalog, s'appuie sur le formalisme des automates logiques a piles lpda et les techniques de programmation dynamique. Les lpda permettent la description des methodes de resolution logique (old, bottom-up ou earley) a l'aide des transitions utilisant l'unification. L'idee de la programmation dynamique consiste ensuite en une exploration systematique de l'ensemble des piles derivables a l'aide d'une strategie de parcours equitable avec tabulation des etats atteints. Pour des raisons de cout memoire, nous ne stockons en fait que des representations compactes des piles sous forme d'items qui ne conservent que l'information necessaire. Un test de subsomption elimine les items redondants et la tabulation permet de realiser du partage de calculs par reutilisation des items dans des contextes differents. Deux interpretations des piles a l'aide d'items sont etudiees. Nous donnons une formalisation rigoureuse et une generalisation des concepts utilises par le couple automates a piles/programmation dynamique. Cela nous conduit a introduire la notion d'automates a piles orientes subsomption spda qui agissent sur des ensembles de piles enrichis par un ordre refletant l'idee de sous-calculs. Ces automates etendent les automates logiques a piles. L'implantation de dyalog a mis en evidence differents problemes dont celui du cout memoire des objets tabules. Des techniques de partage de structures ont alors ete developpees pour y remedier