Principe

La résolution de buts consiste répondre à une question posée par l'utilisateur, exprimée par le compilateur sous forme de buts (en fait le compilateur ne fournit qu'une suite de termes qu'il faut alors transformer via la fonction But_Constuire en une pile de buts).
La procédure Resoudre prend en argument une pile de buts et une pile d'environnements dans laquelle les buts doivent être résolus. Elle prend en compte le premier but à effacer (sommet de la pile) et tente de l'unifier successivement à chacune des règles (non déterminisme) du paquet qui possède le même nom et le même nombre d'arguments que le sous-but. La procédure Resoudre prend en plus comme paramètre le niveau d'appel de la récursivité. Cela sert notamment à connaître les niveaux des variables que l'on empile sur la pile d'environnement.
Chaque étape de la résolution (correspondant chacune à un appel à la procédure Resoudre) est visualisée à l'aide d'un arbre dit de résolution, dans lequel chaque n ud représente un appel récursif (caractérisé par sa pile de buts et sa pile d'environnements) et les différents fils d'un n ud représentent le non déterminisme résultant des tentatives d'unification successives avec les différentes clauses candidates.

Figure: Arbre de résolution

La notion d'arbre de résolution ne doit pas être confondue avec la notion d'arbre vue précédemment qui permettait de représenter un terme. Deux exemples ont été développés (cf. figure 2.1 et figure 2.2) : ils représentent deux arbres de résolution pour deux exemples différents venant illustrer la résolution de buts.

Figure: Un nouvel arbre de résolution

Le premier exemple cherche à savoir si le mot laval est un palindrome, grâce aux règles suivantes:

• règle 1 : palindrome(*x) -> turborev(*x, nil, *x);
• règle 2 : turborev(nil, *a, *a) -> ;
• règle 3 : turborev(k(*a, *b), *c, *d) -> turborev(*b, k(*a, *c), *d);

Cet exemple sert juste à montrer l'évolution de la pile d'environnements à chaque appel récursif.
Le deuxième exemple cherche tous les chemins dans un graphe (cf. figure 2.3) partant de l'état 1. Comme cet exemple est assez long, seule un partie significative a été développée. On a les règles suivantes:

• règle 1 : arc(1, 2) -> ;
• règle 2 : arc(1, 3) -> ;
• règle 3 : arc(2, 4) -> ;
• règle 4 : arc(2, 5) -> ;
• règle 5 : arc(3, 5) -> ;
• règle 6 : arc(4, 5) -> ;
• règle 7 : arc(4, 6) -> ;
• règle 8 : arc(5, 6) -> ;
• règle 9 : chemin(*x, *y) -> arc(*x, *y);
• règle 10 : chemin(*x, *y) -> arc(*x, *z), chemin(*z, *y);

Figure 2.3: Graphe

Cet exemple permet de montrer l'évolution des niveaux des environnements et des niveaux des variables à chaque appel récursif. On convient de distinguer les environnements de même indice, c'est-à-dire les environnements résultant de l'unification successive avec les différentes clauses candidates (non déterminisme) par un exposant.