Числа Фибоначчи - ошибка глобального стека - PullRequest
Новая
       41

Числа Фибоначчи - ошибка глобального стека

1 голос
/ 25 мая 2019

Рассмотрим эту простую программу Prolog: 

nat(0).
nat(s(X)) :- nat(X).
plus(X, 0, X) :- nat(X).
plus(X, s(Y), s(Z)) :- nat(X), nat(Y), nat(Z), plus(X, Y, Z).
fib(0, 0).
fib(s(0), s(0)).
fib(s(s(K)), Z) :- fib(s(K), Y), fib(K, X), plus(X, Y, Z).

Я уже протестировал plus и похоже, что она работает.Посмотрим, будет ли fib работать нормально ... 

?- fib(0, 0).
true.

?- fib(s(0), s(0)).
true ;
false.

?- fib(s(s(0)), s(0)).
true ;
false.

?- fib(s(s(s(0))), s(s(0))).
true ;
ERROR: Out of global stack

Все работает великолепно, пока я не хочу распечатать 3-е число, которое оказывается 2!

Я понимаю, чтосимуляция арифметики Пеано таким способом далеко не эффективна, а также то, что используемый здесь экспоненциальный алгоритм является неоптимальным, тем не менее я отказываюсь верить, что проблемы с производительностью возникают раньше, когда я вычисляю только третье число.Поэтому моя программа наверняка зацикливается, и поэтому она ошибочна.

... почему она зацикливается?и что нужно, чтобы он прекратил цикл?

1 Ответ

1 голос
/ 25 мая 2019

Короткий ответ : он зацикливается, потому что plus(0, s(0), X). произведет true, а затем зациклится.

Если мы посмотрим на traceмы видим: 

[trace]  ?- fib(s(s(s(0))), s(s(0))).
   Call: (8) fib(s(s(s(0))), s(s(0))) ? creep
   Call: (9) fib(s(s(0)), _902) ? creep
   Call: (10) fib(s(0), _906) ? creep
   Exit: (10) fib(s(0), s(0)) ? creep
   Call: (10) fib(0, _910) ? creep
   Exit: (10) fib(0, 0) ? creep
   <b>Call: (10) plus(0, s(0), _912) ? creep</b>
   ...
   Exit: (9) plus(s(0), s(0), s(s(0))) ? creep
   Exit: (8) fib(s(s(s(0))), s(s(0))) ? creep
true .

Но интерпретатор возвращается к этому предикату и стремится найти больше решений.Это связано с тем, что ваш nat(Z) каждый раз обнаруживает следующее значение, а затем интерпретатор вызывает plus(X, Y, Z), чтобы проверить, соответствует ли это значение, но каждый раз, когда оно терпит неудачу.

Мы можем видеть, чтокогда мы отследим plus(0, s(0), X): 

[trace]  ?- plus(0, s(0), X).
   Call: (8) plus(0, s(0), _676) ? creep
   Call: (9) nat(0) ? creep
   Exit: (9) nat(0) ? creep
   Call: (9) nat(0) ? creep
   Exit: (9) nat(0) ? creep
   Call: (9) nat(_884) ? creep
   Exit: (9) nat(0) ? creep
   Call: (9) plus(0, 0, 0) ? creep
   Call: (10) nat(0) ? creep
   Exit: (10) nat(0) ? creep
   Exit: (9) plus(0, 0, 0) ? creep
   Exit: (8) plus(0, s(0), s(0)) ? creep
X = s(0) ;
   Redo: (9) plus(0, 0, 0) ? creep
   Fail: (9) plus(0, 0, 0) ? creep
   Redo: (9) nat(_884) ? creep
   Call: (10) nat(_888) ? creep
   Exit: (10) nat(0) ? creep
   Exit: (9) nat(s(0)) ? creep
   Call: (9) plus(0, 0, s(0)) ? creep
   <b>Fail: (9) plus(0, 0, s(0)) ? creep</b>
   Redo: (10) nat(_888) ? creep

Конечно, ни один из ответов, предложенных nat(Z), не будет выполнен, как только plus(0, s(0), X) будет успешным.

Однако нет причины звонить nat(Z) в любом случае, поскольку в конечном итоге рекурсивный вызов попадет в базовый регистр, который будет проверять nat(X), поэтому мы можем реализовать его следующим образом: 

plus(X, 0, X) :- nat(X).
plus(X, s(Y), s(Z)) :- <b>plus(X, Y, Z)</b>.

Как правило, более эффективно использовать различные шаблоны в первый параметр: 

plus(<b>0</b>, X, X) :- nat(X).
plus(<b>s(X)</b>, Y, s(Z)) :- <b>plus(X, Y, Z)</b>.
...