Prolog et Fibonacci


précédentsommairesuivant

III. Utilisation des "Open Lists".

III-A. Que sont les Open Lists ?

Dans une liste "normale", le dernier élément est la liste vide : exemple [1,2,3|[]].
Les Open Lists sont des listes particulières où le dernier élément n'est pas défini : exemple [1,2,3|_].
Considérons ce petit programme :

Prolog
Sélectionnez
test :-
	L = [1,2,3|_],
	(   member(1, L) -> format('1 présent dans ~w~n', [L]);format('1 absent dans ~w~n', [L])),
	(   member(3, L) -> format('3 présent dans ~w~n', [L]);format('3 absent dans ~w~n', [L])),
	(   member(5, L) -> format('5 présent dans ~w~n', [L]);format('5 absent dans ~w~n', [L])).

La sortie obtenue est :

Console Prolog
Sélectionnez
10 ?- test.
1 présent dans [1, 2, 3|_G272]
3 présent dans [1, 2, 3|_G272]
5 présent dans [1, 2, 3, 5|_G281]

On constate que lorsque l'élément est présent, la liste n'est pas modifiée, lorsqu'il est absent, il est ajouté en fin de liste. Remarquons au passage, que contrairement à ce qui se passe habituellement en Prolog, bien que la liste soit modifiée, elle est toujours unifiée avec la même variable.

III-B. Simulation d'un stream par une Open List.

Il est possible d'attacher une procédure à une Open List, on peut ainsi simuler un stream.
Le code suivant est inspiré de cette pageLes stream en Prolog. when(@Condition, :Goal) est un prédicat qui permet de geler l'exécution de :Goal tant que la condition @Condition n'est pas à true. En Prolog, le "@" en début de nom de variable signifie que l'argument n'est pas encore instancié, le ":" signifie que l'argument est un méta-argument.
Ce code permet de calculer la suite des puissances de 2, on remarquera que la création du stream est faite avant la création de l'Open List.

Prolog
Sélectionnez
% arg1 : la procédure à appliquer au stream (ici un prédicat à deux arguments)
% arg2 : l'élément d'initialisation du calcul
% arg3 : le stream 
make_stream(Pred, Head, OpenList) :-
   when(nonvar(OpenList), 
        (
          % on construit l' Open List
          OpenList = [Head|Rest],
          % on applique le prédicat de calcul
          call(Pred, Head, Next),
          % on construit récursivement l' Open List
          make_stream(Pred, Next, Rest)
        )).
        
% le prédicat de calcul des puissances
double(X, Y) :-
	Y is X * 2.

% le stream permettra de calculer la liste des puissances de 2
test :-
    % création du stream
	make_stream(double, 1, OpenList),
	OpenList = [_, _, _, _|X],
	format('Les quatre premières puissances de 2 sont ~w~n', [OpenList]),
	X = [_, _, _, _|_Y],
	format('Les huit premières puissances de 2 sont ~w~n', [OpenList]).

On obtient :

Console Prolog
Sélectionnez
12 ?- test.
Les quatre premières puissances de 2 sont [1, 2, 4, 8|_G312]
Les huit premières puissances de 2 sont [1, 2, 4, 8, 16, 32, 64, 128|_G466]

De plus amples explications sur le prédicat when/2 peuvent être trouvées iciLe prédicat when/2.
De plus amples explications sur le prédicat nonvar/1 peuvent être trouvées iciLe prédicat nonvar/1.

III-C. Le calcul des nombres de Fibonacci avec les Open Lists et les streams.

Par les streams, on obtient une liste des nombres de Fibonacci.
La construction de l'Open List se fait de manière itérative.
Le calcul des nombres est un calcul itératif semblable au calcul itératif du I-C-2.

Prolog
Sélectionnez
% Construction de l' Open List
make_OpenList(0, OpenList, OpenList):- !.

make_OpenList(N, L1,L2) :-
	N1 is N-1,
	make_OpenList(N1, [_|L1], L2).

% creation du stream de calcul
% ici le prédicat de calcul a besoin de 2 arguments en entree !
make_stream_fib(Pred, First, Second, OpenList) :- 
   when(nonvar(OpenList), 
        ( 
          OpenList = [Second |Rest], 
          call(Pred, First, Second, Next),
          make_stream_fib(Pred, Second, Next, Rest) 
        )). 

fib_OpenList(N) :-
	     make_stream_fib(fib_OpenList, 0, 1, OpenList),
	     make_OpenList(N, _, OpenList).
	     
% calcul effectif du nombre de Fibonacci.		 
fib_OpenList(X,Y,Z) :-
	Z is X + Y.

Les performances sont correctes :

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

Remarquons que la génération de l'Open List par make_OpenList prend 60 000 inférences.


précédentsommairesuivant

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