Tại sao vị từ của tôi trong Prolog Fib/2 luôn luôn nói "ra khỏi ngăn xếp cục bộ"?

Question

Tôi đã viết một biến vị ngữ fib/2 để tính toán các số Fibonacci trong Prolog. Mặc dù nó hoạt động, nó luôn luôn nói "ra khỏi ngăn xếp địa phương" và lỗi trông giống như:

?- fib(10, F). 
F = 55 ; 
ERROR: Out of local stack 

ngữ của tôi là dưới đây:

fib(0, 0). 
fib(1, 1). 
fib(N, NF) :- 
    A is N - 1, 
    B is N - 2, 
    fib(A, AF), 
    fib(B, BF), 
    NF is AF + BF. 

Bất cứ ai biết tại sao điều này là gì và làm thế nào để sửa chữa nó để nhận các nội dung sau ::

% or the search might stop immediately, without pressing space. 
?- fib2(10, F). 
F = 55 ; 
false. 

Cảm ơn bạn trước!

Answer 1

Lỗi out of local stack có nghĩa là chương trình đã sử dụng quá nhiều bộ nhớ và vượt quá không gian được phân bổ; điều này xảy ra thường xuyên khi chương trình rơi vào một vòng lặp vô hạn. Trong trường hợp của bạn, đây là dấu vết:

[trace] 2 ?- fib(2,M). 
    Call: (6) fib(2, _G671) ? creep 
^ Call: (7) _G746 is 2+ -1 ? creep 
^ Exit: (7) 1 is 2+ -1 ? creep 
^ Call: (7) _G749 is 2+ -2 ? creep 
^ Exit: (7) 0 is 2+ -2 ? creep 
    Call: (7) fib(1, _G747) ? creep 
    Exit: (7) fib(1, 1) ? creep 
    Call: (7) fib(0, _G747) ? creep 
    Exit: (7) fib(0, 0) ? creep 
^ Call: (7) _G671 is 1+0 ? creep 
^ Exit: (7) 1 is 1+0 ? creep 
    Exit: (6) fib(2, 1) ? creep 
M = 1 ; 
    Redo: (7) fib(0, _G747) ? creep 
^ Call: (8) _G752 is 0+ -1 ? creep 
^ Exit: (8) -1 is 0+ -1 ? creep 
^ Call: (8) _G755 is 0+ -2 ? creep 
^ Exit: (8) -2 is 0+ -2 ? creep 
    Call: (8) fib(-1, _G753) ? creep 
^ Call: (9) _G758 is -1+ -1 ? creep 
^ Exit: (9) -2 is -1+ -1 ? creep 
^ Call: (9) _G761 is -1+ -2 ? creep 
^ Exit: (9) -3 is -1+ -2 ? creep 
    Call: (9) fib(-2, _G759) ? creep 
^ Call: (10) _G764 is -2+ -1 ? creep 
^ Exit: (10) -3 is -2+ -1 ? creep 
... 

như bạn có thể thấy, sau khi tìm thấy rằng fibonacci thứ 2 là 1 (theo định nghĩa của bạn), bạn yêu cầu một giải pháp thứ hai; vì bạn chưa chỉ định rằng mệnh đề thứ ba chỉ có thể được sử dụng khi N> 1 prolog cố gắng tìm giải pháp thứ hai bằng cách tính toán fib (-1), fib (-2), fib (-3) v.v.

để khắc phục, bạn phải thêm N>1 hoặc quy tắc tương tự vào mệnh đề thứ ba

Answer 2

Một vấn đề bạn có thể giải quyết là việc tính toán lại giá trị của các giá trị không cần thiết. Đây là một thay đổi nhỏ cho mã của bạn để giải quyết sự thiếu hụt này:

:- dynamic db_fib/2. 

init_fib :- 
    assertz(db_fib(0, 0)), 
    assertz(db_fib(1, 1)). 

fib(N, NF) :- 
    A is N - 1, 
    B is N - 2, 
    get_fib(A, AF), 
    get_fib(B, BF), 
    NF is AF + BF. 

get_fib(A, F) :- 
    db_fib(A, F), 
    !. 

get_fib(A, F) :- 
    fib(A, F), 
    assertz(db_fib(A, F)). 

Ví dụ, trong SWI Prolog, người ta có thể tính toán

?- init_fib, fib(1000,F). 

rất nhanh chóng và không có chồng xả.

?- init_fib. 
true. 

?- fib(10,A). 
A = 55. 

?- fib(100,A). 
A = 354224848179261915075. 

?- fib(1000,A). 
A = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875. 

Answer 3

Mã của bạn không phải là tail-recursive. một cấu trúc đệ quy đuôi đúng nghĩa là có thể áp dụng TRO (tối ưu đệ quy đuôi). Về cơ bản, chuyển đổi đệ quy của bạn thành lặp lại, bằng cách tái sử dụng khung ngăn xếp hiện có cho cuộc gọi đệ quy. Với TRO được áp dụng, mỗi cuộc gọi đệ quy sẽ đẩy một khung ngăn xếp mới lên ngăn xếp cuộc gọi. Bạn nên cấu trúc vị ngữ của bạn một cái gì đó như thế này (lưu ý rằng tôi đã không thực sự thử nghiệm mã này, nhưng nó nên thực hiện công việc):

% ------------------------------------------------------ 
% the public interface predicate 
% ------------------------------------------------------ 
fib(1,1).   % first element in the sequence is 1 
fib(2,1).   % second element in the sequence is 1 
fib(N,X) :-  % subsequent elements 
    N > 2 ,   % where N > 2 
    fib(1,1,3,N,X) % are computed 
    . 

% -------------------------------------- 
% the private worker predicate for N > 2 
% this predicate maintains a sliding 'window' on the fibonacci sequence 
% as it computes it 
% -------------------------------------- 
fib(V1 , V2 , N , N , X) :- % compute the element at position N 
    N > 2 ,      % ensure N > 2 
    X is V1 + V2    % value is the sum of the 2 prior elements 
    . 
fib(V1 , V2 , T , N , X) :- % on backtracking, slide the window to the right: 
    T > 2   ,    % ensure N > 2 
    T1 is T + 1 ,    % increment N 
    V3 is V1 + V2 ,    % compute the next value (V1+V2) 
    fib(V2,V3,T1,N,X)   % recurse 
    . 

Answer 4

Rất có thể thứ tự (người đầu tiên là gà hoặc trứng) rất có thể nếu nó được viết như thế này:

fib(N, NF) :- 
    A is N - 1, 
    B is N - 2, 
    fib(A, AF), 
    fib(B, BF), 
    NF is AF + BF. 
fib(1, 1). 
fib(0, 0). 

vấn đề sẽ được giải quyết.

Answer 5

Lý do tại sao chương trình của bạn không chấm dứt có thể được xem tốt nhất bằng cách xem xét chỉ là một đoạn của chương trình của bạn, được gọi là failure-slice mà có thể thu được bằng cách thêm false mục tiêu vào chương trình của bạn.

 
fib(0, 0) :- false. 
fib(1, 1) :- false. 
fib(N, NF) :- 
    A is N - 1, 
    B is N - 2, 
    fib(A, AF), false, 
    fib(B, BF), 
    NF is AF + BF. 

Tất cả tấn công qua một phần chương trình của bạn không ảnh hưởng đến việc chấm dứt.Họ có thể có các tác động khác, như khi chương trình của bạn thành công hay thất bại nhưng không có kết thúc.

Để làm cho chương trình chấm dứt nó là cần thiết để thay đổi một cái gì đó trong phần nhìn thấy được. Rõ ràng, đối số đầu tiên giảm mà không có giới hạn.

Nhưng lát thất bại cũng ngụ ý nhiều chương trình khác có hiệu quả sẽ có cùng một lát thất bại. Hãy suy nghĩ ví dụ để đưa các sự kiện cuối cùng (như đề xuất bởi @ RicardoMojica). Những sự kiện như vậy có thể bị xóa với false theo cùng một cách như vậy dẫn đến cùng một chương trình. Do đó:

Thay đổi thứ tự các mệnh đề không ảnh hưởng đến việc chấm dứt (phổ quát).

---

^{TNHH Bảo hành
Tất cả các báo cáo này chỉ áp dụng cho các chương trình đơn điệu thuần túy. các tính năng không đơn điệu không tinh khiết và tác dụng phụ tiêu diệt các đặc tính này.}