Interprète Datalog

Le code pour démarrer se trouve ici

Étape 1 - les substitutions

Pour cette partie vous allez éditer le fichier Datalog/src/substitution.rs. Chaque question représente typiquement 3-4 lignes de code, pas plus de 8!

Une substitution est représentée par une HashMap qui à une variable associe un terme.

Question 1.1

Complétez la fonction Substitution::apply_to_term (laissez les commentaires, c'est toujours utile...)

Question 1.2

Exécutez le test test_apply_to_term. Il teste uniquement que $c \sigma = c$. Complétez le test test_apply_to_term en vous inspirant des commentaires au début de la fonction Substitution::apply_to_term.

Question 1.3

Lisez le fichier atom.rs, puis complétez la fonction Substitution::apply_to_atom, et testez votre fonction.

Question 1.4

Lisez le fichier clause.rs, et comprenez les définitions. Complétez les fonctions Substitution::apply_to_clause_item, et Substitution::apply_to_clause, et testez vos fonctions.

Question 1.5

Lisez le fichier request.rs, et ignorez pour le moment l'entier associé à une coupure. Complétez les fonctions Substitution::apply_to_request_item, et Substitution::apply_to_request, et testez vos fonctions.

Question 1.6

Relisez le cours pour vérifier que vous avez bien compris comment est définie la composition $\sigma_1;\sigma_2$ des substitutions $\sigma_1$ et $\sigma_2$. Complétez la fonction Substitution::compose et testez votre fonction avec les tests fournis test_compose1, test_compose2, et test_compose3.

Étape 2 - unification

Question 2.1

Relisez l'algorithme de calcul d'un unificateur le plus général (most general unifier, MGU) vu en cours. Complétez la fonction mgu du fichier Datalog/src/unification.rs et testez-là à l'aide des trois tests fournis dans ce fichier. Comptez entre 20 et 30 lignes à écrire.

Question 2.2

Rendez-vous maintenant dans le fichier Datalog/src/search.rs. Lisez rapidement la fonction rename qui vous est donnée, et relisez la partie du cours où on explique pourquoi il faudra renommer les variables des clauses avant de chercher à réécrire une tête de requête à l'aide d'une clause. Vous n'avez rien à écrire à cette question.

Question 2.3

Toujours dans Datalog/src/search.rs, complétez maintenant la fonction resolve et testez-la avec le test fourni. N'hésitez pas à écrire vos propres tests en complément. Comptez entre 10 et 20 lignes pour la fonction resolve proprement dite.

Étape 3 - exploration de l'arbre de recherche

On va maintenant s'intéresser à la façon d'explorer l'arbre de recherche. Une configuration correspond à un état d'avancement de cette exploration. À chaque étape, on a besoin de savoir:

  • quelle est la requête qu'on cherche à réécrire
  • quelle est la substitution obtenue par composition de tous les unificateurs le long de la branche de l'arbre où on se trouve
  • à partir de quelle clause du programme il faut continuer l'exploration des différentes clauses qui permettent de faire un pas de réécriture (c'est le program counter, PC)

C'est ce qui constitue une configuration (voir fichier configuration.rs).

La configuration initiale est celle où request est la requête saisie par l'utilisateur (on n'a pas encore commencé à réécrire), substitution est la substitution identité (on est à la racine de l'arbre de recherche), et PC=0 (on commence la recherche par une tentative de résolution via la première clause du programme).

Par exemple, si on a le programme suivant:

a(1).
b(1).
a(X) :- b(X).

et la requête initiale ?-a(X), la configuration initiale sera

[CONF0]
* a(1).
b(1).
a(X) :- b(X).
?- a(X).
sol = []

où on note le PC avec une étoile.

L'exploration de l'arbre de recherche se base sur la fonction search_step qui à une configuration (avec requête non vide) associe 0, 1, ou deux nouvelles configurations. Avant de lire l'exemple ci-dessous, lisez les explications en commentaire de la fonction search_step dans le fichier search.rs.

Après la résolution avec la clause étoilée dans CONF0, on obtient la configuration

[CONF1]
* a(1).
b(1).
a(X) :- b(X).
?- .
sol = [X <- 1]

et on peut renvoyer immédiatement une solution puisque la requête est vide. Mais la recherche continue avec le PC avancé

[CONF2]
a(1).
* b(1).
a(X) :- b(X).
?- a(X).
sol = []

Donc search_step(CONF0) renvoie vec![CONF1, CONF2].

Par ailleurs search_step(CONF1) n'est pas défini (si la requête est vide, on ne fait pas un pas "en avant", mais "en arrière", pour revenir à une branche qu'on n'a pas encore exploré.

Dans CONF2, la résolution avec b(1) échoue, donc search_step(CONF2) renvoie vec![CONF3], avec

[CONF3]
a(1).
b(1).
* a(X) :- b(X).
?- a(X).
sol = []

Cette fois-ci la résolution réussit et mène à la configuration

[CONF4]
* a(1).
b(1).
a(X) :- b(X).
?- b(X).
sol = [X<-X] = []

Notez que le PC est revenu à 0: on repart du début du programme pour résoudre b(X). Il faut cependant aussi garder en mémoire qu'il est théoriquement possible de trouver encore une autre façon de résoudre a(X) dans CONF3, et donc il faut aussi considérer la configuration

[CONF5]
a(1).
b(1).
a(X) :- b(X).
*
?- a(X).
sol = []

La configuration CONF5 est une configuration d'échec: on n'a pas réussi à réécrire la requête en la requête vide, et on est arrivé à la fin du programme. En résumé, on aura donc

  • search_step(CONF3) = vec![CONF4,CONF5]
  • search_step(CONF5) = vec![]

Question 3.1

Complétez la fonction search_step de Datalog/src/search.rs et testez votre solution avec le test fourni. Écrivez aussi vos propres tests (par exemple reprenez l'exemple ci-dessus).

Question 3.2

On va maintenant utiliser la fonction search_step en conjonction avec une pile (stack) de configurations dans la fonction search_next_solution: de manière répétée, on prend la configuration en haut de pile, on lui applique search_step, et si search_step renvoie une ou deux configurations, on les empile au-dessus des autres configuration (sinon on aura juste dépilé la configuration en haut de pile). On s'arrête quand on dépile une configuration contenant une requête vide: à ce moment-là, on a trouvé une solution et on la renvoie. La pile, passée par adresse et modifiée par la fonction search_next_step, nous permettra éventuellement de poursuivre la recherche pour trouver une nouvelle solution.

Complétez la fonction search_next_solution (entre 5 et 10 lignes, "facile").