Structures de données

Un terme d'un programme Prolog peut être vu comme un arbre dont les feuilles sont soit des constantes, soit des variables. La méthode employée ici tente de factoriser au maximum les structures de données au cours de la résolution, afin d'éviter le gaspillage de la mémoire. Ainsi, les structures de données de l'interpréteur seront dynamiques, c'est-à-dire construites et désallouées au fur et à mesure (on évite ainsi les tests de débordements), au contraire des structures de données du compilateur qui seront statiques (du moins, du point de vue de l'interpréteur). Les stuctures dynamiques sont spécifiques à l'interpréteur et au nombre de trois:

• les instances d'arbre : Les structures de données sont donc factorisées au maximum, et notamment les arbres. Or, du fait que la récursivité de la résolution, il faut pouvoir distinguer deux utilisations d'un même arbre. C'est pourquoi l'interpréteur ne travaille pas directement sur des arbres mais sur des instances d'arbres. Une instance d'arbre est simplement un pointeur sur un arbre et un niveau représentant à peu de chose près le niveau d'imbrication.
• la pile de buts : Il s'agit simplement d'une pile d'instance d'arbre. Elle est initialisée avec les instances résultant de la question posée par l'utilisateur auxquelles sont attribuées le niveau 0.
• la pile d'environnements : C'est la structure qui représente, à un instant donné, la liaison entre une instance de variable et une instance d'arbre. Une instance de variable fonctionne exactement de la même manière qu'une instance d'arbre; elle contient simplement un pointeur sur une variable et son niveau. Mais comme les instances de variables ne servent que dans un environnement, aucune structure particulière n'a été définie.

Pour plus de détails sur ces structures de données, on se reportera au sujet fourni dans lequel elles sont plus amplement expliquées (section 2.3 : représentation physique des entités). Néanmoins, comme ces structures sont exploitées dans toute la suite, elles aparaîtront très clairement au final.