Prolog : "crash course" (2)

Flot de contrôle

Dans les langages "classiques" (modèle fonctionnel + commandes impératives comme l'affectation des variables) un "bloc fonctionnel" est appelé et retourne quelque chose, et c'est tout. "Call" et "Exit" sont les seules activités d'interfaçage d'un bloc. Prolog est plus riche, un prédicat peut échouer : "Fail", si l'unification des formes ou des arguments des prédicats s'avère impossible.

Après l'échec, le contrôle revient à la clause précédante, sur l'arbre des traces d'exécution, le système effectue le "Redo", et essaie une solution alternative, peut-être une autre unification de variables. Nous voyons ici que le flot de contrôle dépend très fort des arguments de l'appel original. Comme il a été dit, contrairement à d'autres langages, parmi les arguments on trouvera des variables logiques, qui jouent le rôle des résultats d'appel. Mais a priori tout argument peut être instancié, ou être une variable, nulle part en prolog n'est déterminé quels arguments doivent être considérés "donnés". On peut lancer la requête : ancetre(cain,X) ou ancetre(X,cain). Et nous verrons des exemples considérablement plus "exotiques".

Listes

Des structures de données séquentielles comme des tableaux et des listes sont utilisées dans tous les langages. En Prolog leur syntaxe est : [a,b,c,d], etc. où a, b, etc. peuvent être des termes quelconques, ou des variables logiques. [] dénote la liste vide, et le pattern [X|Y] est une liste dont le premier élément, la tête vaut X, et tous les éléments restants, la queue de la liste – Y. Ainsi si on unifie [X|Y] avec [1,4,8], X sera égal à 1, et Y à [4,8].

Une liste est une structure chaînée, composée de paires champ-tête + champ-queue ; ce dernier "pointe" vers le reste de la liste. Ceci est un détail d'implémentation, mais montre qu'il est facile d'avoir deux listes qui partagent la queue.

Voici l'algorithme et le code permettant de concaténer deux listes, former [a,b,c,d] à partir de [a,b,c] et [d].

append([],L,L).
append([X|Y],L,[X|Q]):-append(Y,L,Q).
La sémantique est évidente : si la première liste est vide, on retourne la seconde. Si elle a un élément comme tête, le même élément sera la tête du résultat, suivi par la concaténation de la queue gauche et la seconde liste. Notez que la seconde liste n'est même pas regardée, c'est un spectateur dans ce programme. Voici un test tracé :
[trace] 2 ?- append([a,b,1],[z],R).
   Call: (6) append([a, b, 1], [z], _G2190) ? creep
   Call: (7) append([b, 1], [z], _G2269) ? creep
   Call: (8) append([1], [z], _G2272) ? creep
   Call: (9) append([], [z], _G2275) ? creep
   Exit: (9) append([], [z], [z]) ? creep
   Exit: (8) append([1], [z], [1, z]) ? creep
   Exit: (7) append([b, 1], [z], [b, 1, z]) ? creep
   Exit: (6) append([a, b, 1], [z], [a, b, 1, z]) ? creep
R = [a, b, 1, z].

Quelques autres algorithmes sur les listes

Nous pouvons profiter de ce prédicat, pour en construire quelques autres. Par exemple, afin de renverser une liste, on sépare la tête, on renverse la queue, et on attache la tête (mise dans une liste d'un élément) à la fin, par concaténation.
reverse([],[]).
reverse([X|Y],R):-reverse(Y,M),append(M,[X],R).

[trace] 3 ?- reverse([1,2,3],L).
   Call: (6) reverse([1, 2, 3], _G2168) ? creep
   Call: (7) reverse([2, 3], _G2250) ? creep
   Call: (8) reverse([3], _G2250) ? creep
   Call: (9) reverse([], _G2250) ? creep
   Exit: (9) reverse([], []) ? creep
   Call: (9) append([], [3], _G2254) ? creep
   Exit: (9) append([], [3], [3]) ? creep
   Exit: (8) reverse([3], [3]) ? creep
   Call: (8) append([3], [2], _G2257) ? creep
   Call: (9) append([], [2], _G2249) ? creep
   Exit: (9) append([], [2], [2]) ? creep
   Exit: (8) append([3], [2], [3, 2]) ? creep
   Exit: (7) reverse([2, 3], [3, 2]) ? creep
   Call: (7) append([3, 2], [1], _G2168) ? creep
   Call: (8) append([2], [1], _G2255) ? creep
   Call: (9) append([], [1], _G2258) ? creep
   Exit: (9) append([], [1], [1]) ? creep
   Exit: (8) append([2], [1], [2, 1]) ? creep
   Exit: (7) append([3, 2], [1], [3, 2, 1]) ? creep
   Exit: (6) reverse([1, 2, 3], [3, 2, 1]) ? creep
L = [3, 2, 1].

Cette solution n'est pas optimale, on peut trouver facilement que sa complexité asymptotique est de l'ordre de N2/2, si N est la longueur de la liste, car pour chaque élément détaché de la source, il faut parcourir la cible.

Mais un autre algorithme existe, linéaire en N, et plus économique en mémoire. Il suffit d'allouer un tampon, initialement vide, et de transférer la tête de la liste source vers la tête du tampon.

revs(L,R):-revs(L,R,[]).
revs([],R,R).
revs([X|Y],R,T):-revs(Y,R,[X|T]).

[trace] 2 ?- revs([1,2,3],S).
   Call: (6) revs([1, 2, 3], _G5298) ? creep
   Call: (7) revs([1, 2, 3], _G5298, []) ? creep
   Call: (8) revs([2, 3], _G5298, [1]) ? creep
   Call: (9) revs([3], _G5298, [2, 1]) ? creep
   Call: (10) revs([], _G5298, [3, 2, 1]) ? creep
   Exit: (10) revs([], [3, 2, 1], [3, 2, 1]) ? creep
   Exit: (9) revs([3], [3, 2, 1], [2, 1]) ? creep
   Exit: (8) revs([2, 3], [3, 2, 1], [1]) ? creep
   Exit: (7) revs([1, 2, 3], [3, 2, 1], []) ? creep
   Exit: (6) revs([1, 2, 3], [3, 2, 1]) ? creep
S = [3, 2, 1].


Voici la procédure qui trie les éléments d'une liste numérique dans l'ordre croissant, avec l'algorithme de tri par insertion (un de plus faciles à coder). L'idée est de parcourir la liste source, et d'insérer ses éléments un par un dans un tampon, initialement vide. L'insertion doit maintenir le tampon toujours trié. On le traverse depuis la tête, et si l'élément inséré est plus petit que la tête de la liste ou de son fragment suffixe, on l'isère justement là. Nous utiliserons l'opérateur d'infériorité, prédéfini en standard.

insort([],[]).
insort([X|P],R):-insort(P,M),insrt(X,M,R).
% où : 

insrt(X,[],[X]).
insrt(X,L,[X|L]):-L=[Y|_],X<Y,!.
insrt(X,[Y|M],[Y|R]):-insrt(X,M,R).
Le prédicat principal insort, qui boucle sur la liste source, effectue l'appel récursif qui trie la queue de la liste. Ceci n'est pas la meilleure stratégie, une autre, ci-dessous, peut être un peu plus efficace, mais sa complexité reste la même.
insort1(L,R):-insort1(L,R,[]).
insort1([],T,T).
insort1([X|P],R,T):-insrt(X,T,T1),insort1(P,R,T1).
Le lecteur voudra COMPRENDRE ces deux solutions, éventuellement lancer ces programmes et tracer les solutions.

Attention ! Le prédicat d'insertion contient un prédicat - opérateur prédéfini, le "cut" "!". Ceci est une procédure méta-logique (ou "non-logique"), dont la sémantique est exclusivement procédurale. Quend le contrôle exécute le cut, le système élague l'arbre décisionnel, il n'y aplus de retour vers l'arrière. Le backtrack à travers le cut échoue inconditionnellement, car il n'y a plus aucune clause qui pourrait accepter le "Redo". Ainsi notre algorithme d'insertion devient globalement déterministe.


Variantes d'appel de quelques prédicats.

Nous n'allons pas définir quoi que ce soit de nouveau, mais appeler quelques procédures avec d'autres assignations des paramètres : entrée – sortie. Par exemple, que se passe-t-il, si on lance append(X,Y,[1,2,3,4]). ?

Intuitivement, c'est la demande de trouver deux listes, telles que leur concaténation donne une liste connue, donc c'est la scission d'une liste en deux fragments. La réalisation de l'algorithme de append dans un langage classique ne pourra marcher, car on ne peut scinder une "variable non-instanciée" en tête et queue, ceci n'a aucun sens.

Mais en Prolog, si. Si on essaie d'unifier X avec [Y|P], et X est une variable logique non-instanciée, Prolog assemble une paire [Y|P] avec deux nouvelles variables non-instanciées, et c'est tout. Voici l'exécution :

[trace] 11 ?- append(X,Y,[1,2,3,4]).
   Call: (6) append(_G3045, _G3046, [1, 2, 3, 4]) ? creep
   Exit: (6) append([], [1, 2, 3, 4], [1, 2, 3, 4]) ? creep
X = [],
Y = [1, 2, 3, 4] ;
   Redo: (6) append(_G3045, _G3046, [1, 2, 3, 4]) ? creep
   Call: (7) append(_G3138, _G3046, [2, 3, 4]) ? creep
   Exit: (7) append([], [2, 3, 4], [2, 3, 4]) ? creep
   Exit: (6) append([1], [2, 3, 4], [1, 2, 3, 4]) ? creep
X = [1],
Y = [2, 3, 4] ;
   Redo: (7) append(_G3138, _G3046, [2, 3, 4]) ? creep
   Call: (8) append(_G3141, _G3046, [3, 4]) ? creep
   Exit: (8) append([], [3, 4], [3, 4]) ? creep
   Exit: (7) append([2], [3, 4], [2, 3, 4]) ? creep
   Exit: (6) append([1, 2], [3, 4], [1, 2, 3, 4]) ? creep
X = [1, 2],
Y = [3, 4] ;
   Redo: (8) append(_G3141, _G3046, [3, 4]) ? creep
   Call: (9) append(_G3144, _G3046, [4]) ? creep
   Exit: (9) append([], [4], [4]) ? creep
   Exit: (8) append([3], [4], [3, 4]) ? creep
   Exit: (7) append([2, 3], [4], [2, 3, 4]) ? creep
   Exit: (6) append([1, 2, 3], [4], [1, 2, 3, 4]) ? creep
X = [1, 2, 3],
Y = [4] ;
   Redo: (9) append(_G3144, _G3046, [4]) ? creep
   Call: (10) append(_G3147, _G3046, []) ? creep
   Exit: (10) append([], [], []) ? creep
   Exit: (9) append([4], [], [4]) ? creep
   Exit: (8) append([3, 4], [], [3, 4]) ? creep
   Exit: (7) append([2, 3, 4], [], [2, 3, 4]) ? creep
   Exit: (6) append([1, 2, 3, 4], [], [1, 2, 3, 4]) ? creep
X = [1, 2, 3, 4],
Y = [] ;
   Redo: (10) append(_G3147, _G3046, []) ? creep
   Fail: (10) append(_G3147, _G3046, []) ? creep
   Fail: (9) append(_G3144, _G3046, [4]) ? creep
   Fail: (8) append(_G3141, _G3046, [3, 4]) ? creep
   Fail: (7) append(_G3138, _G3046, [2, 3, 4]) ? creep
   Fail: (6) append(_G3045, _G3046, [1, 2, 3, 4]) ? creep
false.
On obtient toutes les solutions, comme attendu.

Voici un autre exemple, avec l'inversion de la liste. Est-ce que cela marchera, et trouvera l'inverse (ce qui est mathématiquement une involution) "à l'envers"? Le résultat est un peu pathologique...

[trace] 14 ?- revs(X,[1,2,3]).
   Call: (6) revs(_G3006, [1, 2, 3]) ? creep
   Call: (7) revs(_G3006, [1, 2, 3], []) ? creep
   Call: (8) revs(_G3082, [1, 2, 3], [_G3081]) ? creep
   Call: (9) revs(_G3088, [1, 2, 3], [_G3087, _G3081]) ? creep
   Call: (10) revs(_G3094, [1, 2, 3], [_G3093, _G3087, _G3081]) ? creep
   Exit: (10) revs([], [1, 2, 3], [1, 2, 3]) ? creep
   Exit: (9) revs([1], [1, 2, 3], [2, 3]) ? creep
   Exit: (8) revs([2, 1], [1, 2, 3], [3]) ? creep
   Exit: (7) revs([3, 2, 1], [1, 2, 3], []) ? creep
   Exit: (6) revs([3, 2, 1], [1, 2, 3]) ? creep
X = [3, 2, 1] ;
   Redo: (10) revs(_G3094, [1, 2, 3], [_G3093, _G3087, _G3081]) ? creep
   Call: (11) revs(_G3100, [1, 2, 3], [_G3099, _G3093, _G3087, _G3081]) ? creep
   Call: (12) revs(_G3106, [1, 2, 3], [_G3105, _G3099, _G3093, _G3087, _G3081]) ? creep
   Call: (13) revs(_G3112, [1, 2, 3], [_G3111, _G3105, _G3099, _G3093, _G3087, _G3081]) ? creep
   Call: (14) revs(_G3118, [1, 2, 3], [_G3117, _G3111, _G3105, _G3099, _G3093, _G3087, _G3081]) ? creep
   Call: (15) revs(_G3124, [1, 2, 3], [_G3123, _G3117, _G3111, _G3105, _G3099, _G3093, _G3087, _G3081]) ? creep
   Call: (16) revs(_G3130, [1, 2, 3], [_G3129, _G3123, _G3117, _G3111, _G3105, _G3099, _G3093, _G3087|...]) ? creep
   Call: (17) revs(_G3136, [1, 2, 3], [_G3135, _G3129, _G3123, _G3117, _G3111, _G3105, _G3099, _G3093|...]) ? creep
   Call: (18) revs(_G3142, [1, 2, 3], [_G3141, _G3135, _G3129, _G3123, _G3117, _G3111, _G3105, _G3099|...]) ? creep
   Call: (19) revs(_G3148, [1, 2, 3], [_G3147, _G3141, _G3135, _G3129, _G3123, _G3117, _G3111, _G3105|...]) ? creep
   Call: (20) revs(_G3154, [1, 2, 3], [_G3153, _G3147, _G3141, _G3135, _G3129, _G3123, _G3117, _G3111|...]) ? creep
   ...
... et le processus continue jusqu'à l'exception système, le débordement de la mémoire. Le système est "stupide", si on rejette la première (bonne !!) solution, de trois éléments, l'algorithme tente de touver (unifier) la solution avec quatre éléments, ce qui est condamné à l'échec. Ensuite 5, 6, ... on a un "trou noir".

L'exemple montre que la "réversibilité" des appels des prédicats en Prolog n'est qu'une propriété formelle liée à la façon de exécuter les requêtes, à l'universalité de l'unification, considérablement plus riche qu'une affectation des variables, mais en aucun cas ne signifie que les algorithmes eux-mêmes soient réversibles. Dans quelques cas cela marche, dans d'autres on obtient des pathologie, et encore dans d'autres, l'inversion n'a pas de sens, comment par exemple inverser le tri d'une liste?...

(Pour notre procédure du tri par insertion, le système déclenchera une exception, en essayant de vérifier l'infériorité "<" entre deux variables logiques non-instanciées.)


Suivant
Retour à l'index