Prolog et Fibonacci


précédentsommairesuivant

IV. Utilisation des DCG.

Les DCG "Definite Clause Grammar" permettent d'écrire de façon aisée en Prolog des règles de grammaire.

IV-A. Exemple de DCG.

Regardons ces DCG pour une grammaire très simple d'expressions numériques :

Prolog
Sélectionnez
expression --> terme, suite_terme.
suite_terme --> [].
suite_terme --> [+], expression.
terme --> facteur, suite_facteur.
suite_facteur --> [].
suite_facteur --> [*], terme.
facteur --> [I], {integer(I)}.
facteur --> ['('], expression, [')'].

La première régle signifie qu'une expression est un terme suivi d'un élément appelé suite_terme.
Le deuxième et la troisième règle définissent suite_terme. suite_terme peut n'être rien (deuxième règle) ou l'enchaînement du signe + et d'une expression.
La règle facteur --> [I], {integer(I)}. indique qu'un facteur peut être un nombre et qu'un nombre est reconnu comme vérifiant le prédicat integer/1. Le code entre accolades est interprété comme du Prolog pur.
Après compilation du code comme un code Prolog, On peut tester le règles :

Console Prolog
Sélectionnez
13 ?- expression([1,+,3,*,'(',2,+,4,')'],[]).

Yes
14 ?- expression([1,-,3,*,'(',2,+,4,')'],[]).

No

La deuxième expression n'est pas reconnue puisque '-' n'est pas défini par notre grammaire.
On peut obtenir la conversion en Prolog des règles DCG par le prédicat listing/0.

Prolog
Sélectionnez
expression(A, C) :-
        terme(A, B),
        suite_terme(B, C).

terme(A, C) :-
        facteur(A, B),
        suite_facteur(B, C).

suite_terme(A, A).
suite_terme([+|A], B) :-
        expression(A, B).

facteur([A|C], B) :-
        integer(A),
        B=C.
facteur(['('|A], C) :-
        expression(A, B),
        B=[')'|C].

suite_facteur(A, A).
suite_facteur([*|A], B) :-
        terme(A, B).

On constate que Prolog ajoute automatiquement deux arguments aux prédicats et qu'on retrouve la structure d'Open Lists (prédicas suite_terme, facteur ...).
Des renseignements complémentaires sur les DCG peuvent être trouvés ici. Des renseignements sur les DCG en SWI-Prolog peuvent être trouvés ici.

IV-B. La version naïve en DCG.

La version de l'algorithme naïf peut s'écrire sous cette forme:

Prolog
Sélectionnez
fib_dcg_naif(0,0) --> [].
fib_dcg_naif(1,1) --> [].

fib_dcg_naif(X, FX) -->
	{X > 1,
	 X1 is X-1, 
	 X2 is X - 2},
	 fib_dcg_naif(X1, FX1),
	 fib_dcg_naif(X2, FX2),
	 {FX is FX1 + FX2}.

Les performances sont à la hauteur de la méthode du calcul des nombres de Fibonacci !

Console Prolog
Sélectionnez
24 ?- time(fib_dcg_naif(25, X,_,_)).
% 971,137 inferences, 10.00 CPU in 10.05 seconds (100% CPU, 97114 Lips)

X = 75025 ;

No

Le simple calcul fib_dcg_naif(30, X). fait exploser la pile d'exécution.

IV-C. Une méthode itérative de calcul des nombres de Fibonacci avec les DCG.

Les méthodes suivantes sont inspirées de cet article
La première méthode est basée sur le calcul itératif, les résultats, sous la forme de tuples fib(Nombre, Valeur), sont mémorisés dans une liste. La liste est intialisée avec les deux premières valeurs, Fibonacci(0) et Fibonacci(1).

Prolog
Sélectionnez
% Le lancement du calcul 
fib_dcg_ver1(X) :-
	fib_dcg_ver1_calc(X, [fib(1,1), fib(0,0)], _, _).
	
% ici la valeur recherchée est trouvée
fib_dcg_ver1_calc(X, [X|_]) --> [].

% Sinon on calcule la valeur suivante
% En s'assurant qu'on n'a pas dépassé la valeur recherchée
fib_dcg_ver1_calc(X, [A, B]) -->
  {gt(X, A)},
  fib_suivant_ver1(A, B, Next_Fib),
  fib_dcg_ver1_calc(X, [Next_Fib, A]).

% calcul de la valeur suivante
fib_suivant_ver1(fib(Idx1, Num1), fib(_Idx2, Num2), fib(Idx3, Num3)) -->
	[],
	{Idx3 is Idx1 + 1,
	Num3 is Num1 + Num2}.

gt(fib(A, _FA), fib(X, _FX)) :-
	A >= X.

Les résultats sont intéressants :

Console Prolog
Sélectionnez
8 ?- time(fib_dcg_ver1(100000, _)).
% 799,994 inferences, 0.80 CPU in 1.16 seconds (69% CPU, 1003914 Lips)

IV-C-1. Amélioration de la méthode.

On peut améliorer la rapidité du code en introduisant un cut bien placé : lorsque la valeur a été trouvée, il est inutile de continuer.

Prolog
Sélectionnez
% Le lancement du calcul 
fib_dcg_ver2(X) :-
	fib_dcg_ver2_calc(X, [fib(1,1), fib(0,0)], _,_).

% version avec un cut
fib_dcg_ver2_calc(X, [X|_]) --> [], {!}.

fib_dcg_ver2(X, [A, B]) -->
  fib_suivant_ver2(X, A, B, Fib1),
  fib_dcg_ver2_calc(X, [Fib1, A]).

fib_suivant_ver2(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
  [],
  { Idx3 is Idx1 + 1,
    Num3 is Num1 + Num2 }.

Le gain est important en nombre d'inférences :

Console Prolog
Sélectionnez
10 ?- time(fib_dcg_ver2(100000, _)).
% 499,999 inferences, 0.61 CPU in 1.08 seconds (57% CPU, 820511 Lips)

IV-D. Le calcul des nombres de Fibonacci avec mémorisation des résultats.

Les méthodes précédentes n'utilisent pas toute la puissance des DCG. On peut mémoriser les résultats intermédiaires dans une liste. Attention, il n'est pas question de mémoïsation, les résultats ne sont pas réutilisés, la mémoïsation sera évoquée dans le chapitre suivant.
Au cours du calcul, les résultats seront insérés en fin de la liste des nombres en utilisant la technique des différences de listes : cette méthode permet de concaténer n'importe quelles listes en une seule inférence, alors que append/3 est en O(N) où N est la longueur de la première chaîne.

IV-D-1. Le mécanisme des différences de listes.

Une liste écrite sous la forme d'une différence des listes s'écrit de manière générale X-Y. En utilisant les possibilités des Open Lists, on peut les écrire sous la forme [X|Y]-Y. Ainsi, pour concaténer des listes écrites en différences, on utilise le mécanisme suivant :

Prolog
Sélectionnez
append_dl(X1-X2, X2-X3, X1-X3).

Observons ce qui se passe lors de la concaténation avec cet exemple :

Console Prolog
Sélectionnez
append_dl([1,2,3|T]-T, [4,5,6|U]-U, Z-U).

On constate que
X1 est unifié avec [1,2,3|T].
X2 est unifié avec T et [4,5,6|U], donc T est unifié avec [4,5,6|U] et par voie de conséquence X1 est unifié avec [1,2,3,4,5,6|U].
La concaténation s'est faite en une seule inférence !
La transformation d'une différence de listes en liste normale est très simple et se fait en temps constant, il suffit de concaténer la différence de listes avec la liste vide représentée par []-[] :

Code Prolog
Sélectionnez
dl_to_lf(DL, LF):-
	append_dl(DL, []-[], LF-[]).

IV-D-2. Le calcul des nombres de Fibonacci avec mémorisation.

Comme dans la méthode itérative, les deux derniers nombres calculés servent au calcul du suivant. Le premier des deux nombres est mémorisé au moment du calcul avant d'être "oublié" par la boucle de calcul. Remarquons que insere_successeur passe de 2 arguments dans les DCG à 4 dans les règles Prolog. Le troisième argument peut être considéré comme un argument d'entrée de la clause (il contient la liste des résultats déjà connus) et le quatrième comme un argument de sortie (il contient un résultat de plus).

Prolog
Sélectionnez
% la bonne valeur est trouvée
fib_dcg_memo(X, [X|_]) --> [].

% les deux derniers nombres calculés servent au calcul du suivant
fib_dcg_memo(X, [A, B]) -->
  fib_dcg_memo_suivant(X, A, B, Fib1),
  fib_dcg_memo_suivant(X, B, Fib1, Fib2),
  fib_dcg_memo(X, [Fib1, Fib2]).

% Calcul du nombre de Fibonacci, somme des deux précédents
% le premier est mémorisé
fib_dcg_memo_suivant(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
  insere_successeur(X, fib(Idx1, Num1)),
  { Idx3 is Idx2 + 1,
    Num3 is Num1 + Num2 }.

% insertion en fin de liste d'un nombre de Fibonacci
% On s'assure qu'on n'a pas dépassé le nombre cherché
insere_successeur(A, B, Old, New) :-
  gt(A, B),
  append_dl(Old, [B|T2] - T2, New).

gt(fib(A, _FA), fib(B, _FB)) :-
	A >= B.

append_dl(X1-X2, X2-X3, X1-X3).

Le lancement du calcul peut se faire par :

 
Sélectionnez
fib_dcg_demo(X, FX, Lst_Fibo) :-
     % fib_dcg_memo(arg1, arg2, arg3, arg4).
     % arg1 : le tuple fib(X, FX) recherché
     % arg2 : la liste contenant les deux premiers résultats connus nécessaires pour le calcul
     % arg3 : la liste des tuples résultats mémorisés. A l'initialisation elle est vide 
	 % donc initialisée à T-T car c'est une différence de listes
	 % arg4 : la liste des tuples résultats connus après le calcul
    fib_dcg_memo(fib(X, FX), [fib(0,0), fib(1,1)], T-T, Dl_Lst_Fibo),
    % conversion de la liste des tuples en liste "normale"
    dl_to_lf(Dl_Lst_Fibo, Lst_Fibo).

Exemple de calcul :

Console Prolog
Sélectionnez
?- fibo(8, FX, LstFibo).

FX = 21,
LstFibo = [fib(0, 0), fib(1, 1), fib(2, 1), fib(3, 2), fib(4, 3), fib(5, 5), fib(6, 8), fib(7, 13)] ;

No

A cause de la création de la liste des nombres de Fibonacci, la méthode ne permet pas d'aller plus loin que Fibonacci(50000). Les résultats sont honorables :

Console Prolog
Sélectionnez
?- time(fib_dcg_memo(fib(50000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 425,001 inferences, 0.64 CPU in 0.73 seconds (88% CPU, 663416 Lips)

75 ?- time(fib_dcg_memo(fib(30000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 255,001 inferences, 0.28 CPU in 0.31 seconds (91% CPU, 906670 Lips)

Les calculs sont plus rapides que pour la méthode avec les streams :

Console Prolog
Sélectionnez
?- time(fib_OpenList(30000)).
% 360,029 inferences, 0.73 CPU in 0.89 seconds (83% CPU, 490252 Lips)

IV-E. Le calcul des nombres de Fibonacci avec mémoïsation.

Dans cette partie, on utilise la méthode récursive, mais les résultats sont mémorisés pour ne pas avoir à les recalculer. La recherche du résultat dans la liste se faisant à l'aide du prédicat member/2, on ne peut pas utiliser la technique des différences de listes. Voir iciLes Open Lists.
Les couples seront donc insérés en tête de la liste des résultats déjà connus.
Les régles de grammaire sont très simples : l'obtention d'un nombre de Fibonacci s'obtient soit par la recherche dans une liste, soit par le calcul des deux nombres précédents.

Code Prolog
Sélectionnez
% premiere possibilité , on trouve le résultat dans la liste
fib_dcg_memoisation(A) -->
	fib_dcg_memoisation_recherche(A), {!}.

% seconde possibilité, on calcule le nombre
fib_dcg_memoisation(A) -->
	fib_dcg_memoisation_calcul(A).

% La recherche est le simple test member/2
fib_dcg_memoisation_recherche(A, Lst, Lst)  :-
	member(A, Lst).

% Le calcul est le calcul classique récursif.
fib_dcg_memoisation_calcul(fib(X, FX)) -->	
	{
	    X1 is X-1,
	    X2 is X-2
	},
	fib_dcg_memoisation(fib(X1, FX1)),
	fib_dcg_memoisation(fib(X2, FX2)),
	{
   	   FX is FX1 + FX2
	},
	% le résultat est mémorisé
	ajoute_fib_ver1(fib(X,FX)).


% mémorisation du nombre dans la liste
ajoute_fib_ver1(A, Old, [A | Old]).
	

fib_dcg_memoisation_lance(X, L) :-
	fib_dcg_memoisation(X, [fib(1,1), fib(0,0)], L).

Exemple de résultat :

Console Prolog
Sélectionnez
32 ?- fib_dcg_memoisation_lance(fib(7,X), L).

X = 13,
L = [fib(7, 13), fib(6, 8), fib(5, 5), fib(4, 3), fib(3, 2), fib(2, 1), fib(1, 1), fib(0, 0)] ;

No

Les performances ne sont pas extraordinaires, près de 850 000 inférences pour le calcul de Fibonacci(50 000) :

 
Sélectionnez
33 ?- time(fib_dcg_memoisation_lance(fib(50000,_), _)).
% 849,988 inferences, 0.80 CPU in 0.96 seconds (83% CPU, 1066652 Lips)

Yes

précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+