problèmes avec la génération de nombres de fibonacci

Question

Ci-dessous mon Nième numéro de fibonacci trouver prédicat qui est ok:

f(0,0). 
f(1,1). 
f(N,R):-P is N-1,Q is N-2,f(P,T1),f(Q,T2),R is T1+T2. 

Et je suis en train de générer des nombres de fibonacci avec le prédicat suivant:

fgen(0,0). 
fgen(1,1). 
fgen(A,B):-fgen(X,Y),A is X+1,f(A,T),B is T. 

quand je fais une recherche avec fgen(X,Y).

Il montre:

?- fgen(X,Y). 

X = 0 
Y = 0 ; 

X = 1 
Y = 1 ; 

X = 1 
Y = 1 ; 
ERROR: Out of local stack 

J'ai utilisé la commande trace et ce qui suit a donné lieu:

?- trace,fgen(X,Y). 
    Call: (9) fgen(_G281, _G282) ? creep 
    Exit: (9) fgen(0, 0) ? creep 

X = 0 
Y = 0 ; 
    Redo: (9) fgen(_G281, _G282) ? creep 
    Exit: (9) fgen(1, 1) ? creep 

X = 1 
Y = 1 ; 
    Redo: (9) fgen(_G281, _G282) ? creep 
    Call: (10) fgen(_L178, _L189) ? creep 
    Exit: (10) fgen(0, 0) ? creep 
^ Call: (10) _G281 is 0+1 ? creep 
^ Exit: (10) 1 is 0+1 ? creep 
    Call: (10) f(1, _L179) ? creep 
    Exit: (10) f(1, 1) ? creep 
^ Call: (10) _G282 is 1 ? creep 
^ Exit: (10) 1 is 1 ? creep 
    Exit: (9) fgen(1, 1) ? creep 

X = 1 
Y = 1 ; 
    Redo: (10) f(1, _L179) ? creep 
^ Call: (11) _L207 is 1-1 ? creep 
^ Exit: (11) 0 is 1-1 ? creep 
^ Call: (11) _L208 is 1-2 ? creep 
^ Exit: (11) -1 is 1-2 ? creep 
    Call: (11) f(0, _L209) ? creep 
    Exit: (11) f(0, 0) ? abort 
% Execution Aborted 

Je suis en train de trouver le bug, mais à défaut. Comment résoudre le problème?

Answer 1

Pour commencer,

fgen(A,B) :- fgen(X, Y), A is X+1, f(A, T), B is T. 

est le même que

fgen(A,B) :- fgen(X, _), A is X+1, f(A, B). 

Vous avez donc deux problèmes. Le premier est que vous générez puis jetez Y, et l'avertissement singleton devrait vous avoir alerté. Les avertissements Singleton devraient toujours être répondu en remplaçant la variable par _; S'il semble que cela transforme votre code en un non-sens, votre code est un non-sens. :)

L'autre problème est que B is T est inutile (et en utilisant is/2 ici au lieu de =/2 vous achète rien, parce qu'il n'y a pas d'arithmétique sur le côté droit).

Essayons ceci:

fgen(A, B) :- fgen(X, A), B is X + A. 

Ceci est presque fonctionne:

?- fgen(X, Y). 
X = Y, Y = 0 ; 
X = Y, Y = 1 ; 
X = Y, Y = 0 ; 
X = 1, 
Y = 2 ; 
X = Y, Y = 0 ; 
X = 2, 
Y = 3 ; 
X = Y, Y = 0 ; 
X = 3, 
Y = 5 ; 
X = Y, Y = 0 ; 
X = 5, 
Y = 8 ; 
X = Y, Y = 0 ; 
X = 8, 
Y = 13 ; 
X = Y, Y = 0 ; 
X = 13, 
Y = 21 . 

Tous ces zéros vides de sens devrait vous dire que vous n'avez pas besoin de votre premier cas de base du tout. Après tout, l'ajout de zéros ne changera rien. Si vous supprimez ce cas de base, vous obtenez le comportement que vous voulez:

?- fgen(X, Y). 
X = Y, Y = 1 ; 
X = 1, 
Y = 2 ; 
X = 2, 
Y = 3 ; 
X = 3, 
Y = 5 ; 
X = 5, 
Y = 8 ; 
X = 8, 
Y = 13 ; 
X = 13, 
Y = 21 

Answer 2

D'abord, votre f/2 est pas OK:

6 ?- f(10,X). 

X = 55 ; 
ERROR: (user://2:68): 
     Out of local stack 

Vos clauses devraient être mutuellement exclusive :

f(0,0). 
f(1,1). 
f(N,R):-N>1, 
     P is N-1,Q is N-2,f(P,T1),f(Q,T2),R is T1+T2. 

Sans le N>1 test, au redémarrage, l'objectif le plus profond f(0,T2) est réapparié avec la troisième règle, en allant unidirectionnel dans les nombres négatifs, sans jamais revenir.Maintenant, avec les clauses mutuellement exclusives, cette désadaptation est bloqué et le prédicat devient déterministe:

8 ?- f(10,X). 

X = 55 ; 

No 

Peut-être que vous avez essayé de générer toutes les valeurs possibles, mais a une erreur:

9 ?- f(A,B). 

A = 0, B = 0 ;  
A = 1, B = 1 ; 
ERROR: (user://5:147): 
     Arguments are not sufficiently instantiated 
^ Exception: (8) _G230>1 ? abort 
% Execution Aborted 

parce que le premier argument doit être un nombre entièrement instancié, à utiliser avec > et is.

Ainsi votre deuxième prédicat, fgen(A,B). Il est un peu flou, mais à en juger par l'appel f(A,T) il a l'intention pour A d'être un index, et B son numéro de Fibonacci correspondant, générant un par un la séquence de réponses (0,0) , (1,1) , (2,1), (3,2) , (4,3), (5,5) , (6,8) , .... Pour énumérer les indices, nous pouvons définir

% natural(0). 
% natural(A):- natural(B), A is B+1. 

natural(N):- znat(0,N). 
znat(N,N). 
znat(A,N):- B is A+1, znat(B,N). 

puis simplement

fgen(A,B):- natural(A), f(A,B). 

Maintenant,

12 ?- fgen(A,B). 

A = 0, B = 0 ;  
A = 1, B = 1 ;  
A = 2, B = 1 ;  
A = 3, B = 2 ;  
A = 4, B = 3 ;  
A = 5, B = 5 ;  
A = 6, B = 8 

La première version (commentée) de natural/1 crée une pile d'exécution de longueur linéaire . La deuxième version s'exécute dans l'espace de pile constante.

Bien sûr, votre f/2 est doublement récursif, donc il va épuiser la pile beaucoup plus tôt que natural jamais pu.