Prolog Language
Raisonnement sur les données

Remarques

Récursivité

Prolog n'a pas d'itération, mais toutes les itérations peuvent être réécrites en utilisant la récursivité. La récursivité apparaît lorsqu'un prédicat contient un objectif qui se réfère à lui-même. Lors de l'écriture de tels prédicats dans Prolog, un motif récursif standard comporte toujours au moins deux parties:

• Clause de base (non récursive) : En règle générale, la ou les règles de base représentent le ou les plus petits exemples possibles du problème que vous essayez de résoudre - une liste sans membres, ou un seul membre, ou si vous Travailler avec une structure arborescente, cela peut concerner un arbre vide, ou un arbre avec un seul nœud, etc. Il décrit de manière non récursive la base du processus récursif.

• Clause récursive (continue) : Contient toute logique requise, y compris un appel à elle-même, poursuite de la récursivité.

A titre d'exemple, nous définirons l' append/3 prédicat bien connu append/3 . Vu de manière déclarative, append(L1,L2,L3) est conservé lorsque la liste L3 est le résultat des listes L1 et L2 . Lorsque nous essayons de comprendre la signification déclarative d'un prédicat, nous essayons de décrire les solutions pour lesquelles le prédicat est présent. La difficulté réside ici dans le fait d’essayer d’éviter les détails récurrents étape par étape tout en gardant à l’esprit le comportement procédural du prédicat.

% Base case
append([],L,L).

% Recursive clause
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Le cas de base déclare de manière déclarative que "tout L ajouté à la liste vide est L", notez que ceci ne dit rien sur le fait que L soit vide - ou même une liste (rappelez-vous que dans Prolog tout se résume en termes):

?- append(X,some_term(a,b),Z).
X = [],
Z = some_term(a, b).

Pour décrire la règle récursive, bien que Prolog exécute les règles de gauche à droite, nous omettons la tête pendant une seconde et regardons d'abord le corps - en lisant la règle de droite à gauche:

    append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).

Maintenant, nous disons que si le corps contient: «en supposant que append(L1,L2,L3) est valide»

    append([X|L1],L2,[X|L3]) :-  append(L1,L2,L3). 

Alors, la tête aussi: “alors alors append([X|L1],L2,[X|L3]) ”

En anglais, cela se traduit simplement par:

En supposant que L3 est la concaténation de L1 et L2, alors [X suivi de L3] est également la concaténation de [X suivi de L1] et L2.

Dans un exemple pratique:

«En supposant que [1,2,3] est la concaténation de [1] et [2,3], alors [a, 1,2,3] est aussi la concaténation de [a, 1] et [2,3]. ”

Maintenant, regardons quelques requêtes:

C'est toujours une bonne idée de tester initialement votre prédicat avec la requête la plus générale plutôt que de lui fournir un scénario de test spécifique. Pensez-y: en raison de l'unification de Prolog, nous n'avons pas besoin de fournir de données de test, nous leur transmettons simplement des variables gratuites!

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_G1162],
L3 = [_G1162|L2] ;                          % Answer #2
L1 = [_G1162, _G1168],
L3 = [_G1162, _G1168|L2] ;                  % Answer #3
L1 = [_G1162, _G1168, _G1174],
L3 = [_G1162, _G1168, _G1174|L2] ;          % Answer #4
...

_G1162 variable libre _G1162 avec des lettres alphabétiques pour obtenir un meilleur aperçu:

?- append(L1,L2,L3).
L1 = [],
L2 = L3 ;                                   % Answer #1
L1 = [_A],
L3 = [_A|L2] ;                              % Answer #2
L1 = [_A, _B],
L3 = [_A, _B|L2] ;                          % Answer #3
L1 = [_A, _B, _C],
L3 = [_A, _B, _C|L2] ;                      % Answer #4
...

Dans la première réponse, le cas de base correspond à un motif et Prolog instancie L1 à la liste vide et L2 et L3 unifiés prouvant que L3 est la concaténation de la liste vide et L2.

A la réponse n ° 2, en revenant chronologiquement, la clause récursive entre en jeu et Prolog tente de prouver que certains éléments dans la tête de L1 concaténés avec L2 sont L3 avec ce même élément dans son en-tête de liste. Pour ce faire, une nouvelle variable libre _A est unifiée avec la tête de L1 et il est prouvé que L3 est maintenant [_A|L2] .

Un nouvel appel récursif est effectué, maintenant avec L1 = [_A] . Encore une fois, Prolog tente de prouver que certains éléments placés dans la tête de L1 , concaténés avec L2 sont L3 avec ce même élément dans sa tête. Notez que _A est déjà la tête de L1 , ce qui correspond parfaitement à la règle, alors maintenant, par récursivité, Prolog place _A devant une nouvelle variable libre et nous obtenons L1 = [_A,_B] et L3 = [_A,_B|L2]

Nous voyons clairement que le motif récursif se répète et peut facilement voir que, par exemple, le résultat de la 100ème étape de la récursivité ressemblerait à ceci:

L1 = [X1,X2,..,X99],
L3 = [X1,X2,..,X99|L2]

Note: comme c'est le cas pour un bon code Prolog, la définition récursive de append/3 nous donne non seulement la possibilité de vérifier si une liste est la concaténation de deux autres listes, mais génère toutes les réponses satisfaisant les relations ou des listes partiellement instanciées.

Accéder aux listes

Membre

member/2 a un member(?Elem, ?List) signature member(?Elem, ?List) et indique true si Elem est membre de List . Ce prédicat peut être utilisé pour accéder à des variables dans une liste, où différentes solutions sont récupérées par retour en arrière.

Exemple de requêtes:

?- member(X, [1,2,3]).
X = 1 ;
X = 2 ;
X = 3.

?- member(X,[Y]).
X = Y.

?- member(X,Y).
Y = [X|_G969] ;
Y = [_G968, X|_G972] ;
Y = [_G968, _G971, X|_G975] ;
Y = [_G968, _G971, _G974, X|_G978]
...

Correspondance de motif

Lorsque les index dont vous avez besoin sont petits, la correspondance de modèle peut être une bonne solution, par exemple:

third([_,_,X|_], X).
fourth([_,_,_,X|_], X).