Факториальный расчет без использования рекурсии

Question

Я пытаюсь реализовать решение для факториала (n!) Без использования рекурсии, только используя ретроакцию пролога. Например:

factorial(0, 1). 
factorial(1, 1). 
factorial(2, 2). 

retroaction(X, Y) :- 
factorial(K, Y), 
not(K = X), 
fail. 

retroaction(K, Y) :- factorial(K, Y). 

С фиксированными фактами факторного, если я называю предикат обратного действия, чтобы открыть факториал 2, к примеру, я получить правильный ответ:

?- retroaction(2, X). 
X = 2. 

Решение, которое я пытаюсь реализовать:

factorial_ret(Number, _) :- 
    retractall(factorial(_, _)), 
    assertz(factorial(0,1)), 
    factorial(X, Y), 
    not(X = Number), 
    NewNumber is X + 1, 
    Factorial is Y * NewNumber, 
    retractall(factorial(_, _)), 
    assertz(factorial(NewNumber, Factorial)), 
    fail. 

factorial_ret(Number, Y) :- 
    factorial(Number, Y). 

Если я попытаюсь получить факториал числа больше 1, не работает. Кто-то имеет представление о том, почему?

Answer 1

Как отметил @lurker, вы сбиваете с толку «предикат хранения» с «предикатом определения». Вам нужно определение factorial/2, поэтому он не имеет смысла для retractall(factorial(_,_)).

Ниже я использую retract(mem(N, F)) для получения временных значений и подготовки БД для возможного обновления. Всегда должен быть только экземпляр mem/2.

% replace recursion with a failure driven loop 
:- dynamic mem/2. 
factorial(X, Y) :- 
    assert(mem(0, 1)), 
    repeat, 
    retract(mem(N, F)), 
    ( X == N % done ? 
    -> Y = F, % yes, succeed 
     !  % but be sure to avoid 'external' backtracking... 
    ; N1 is N + 1, 
     F1 is N1 * F, 
     assert(mem(N1, F1)), 
     fail % loop: 'goto repeat' 
    ). 

Обратите внимание, что все встроенные функции в ветви между repeat,...,fail не являются backtrackable (ну, за исключением отводного/1).

Обратите внимание, что такой код будет намного медленнее рекурсивного определения (и не будет работать в многопоточном SWI-Prolog).

Я думаю, что assert/retract были доступны раньше программистам Prolog, как требуется для обработки «баз знаний», а не для глобальных переменных. Несколько Прологов имеют специализированный предикат библиотеки для глобальных переменных, поскольку их законное использование: например, см. memoization.

PS: «задним числом» это термин, используемый в линейной теории устойчивости систем, я никогда не видел раньше о программировании

редактировать Может быть полезно посмотреть, как ошибка сообщает @repeat может быть решена : просто замените унификацию и разрез. Ну, нам также нужно проверить, что X - положительное целое число. С уважением, я думаю, что на самом деле это не имеет отношения к делу.

... 
    ( X == N % done ? 
    -> !,  % yes, be sure to avoid further backtracking 
     Y = F % unify with the computed factorial 
    ; N1 is N + 1, 
... 

Answer 2

У вас есть нижний регистр k в вашем предложении not.

Answer 3

Предполагая, что «обратная реакция» вы на самом деле означает "memoization", один путь об этом будет:

До тех пор, пока вы не найти факториал вам нужно, найти самый большой один до сих пор, вычислить следующий, полоскать и повторить.

Я пишу этот ответ, потому что он имеет немного менее ненужный код, чем в противном случае правильный answer by @CapelliC.

Вам нужен только один начальный факт для этого, факториал 0:

Затем вы можете использовать в repeat цикл, чтобы сделать «пока». Затем, если вы всегда добавлять новые факториалов в верхней части стопки предварительно рассчитанных факториалов и вы всегда смотреть только один раз, вы можете быть уверены, что вы найдете самый большой один до сих пор:

:- dynamic factorial/2. 
factorial(0, 1). 

factorial_memoize(N, F) :- 
    repeat, 
     ( factorial(N, F0) 
     -> !, F = F0 
     ; once(factorial(N0, F0)), 
      succ(N0, N1), 
      F1 is N1 * F0, 
      asserta(factorial(N1, F1)), 
      fail 
     ). 

Вот как программные работы:

?- listing(factorial/2). 
:- dynamic factorial/2. 

factorial(0, 1). 

true. 

?- factorial_memoize(0, F). 
F = 1. 

?- listing(factorial/2). 
:- dynamic factorial/2. 

factorial(0, 1). 

true. 

?- factorial_memoize(5, F). 
F = 120. 

?- listing(factorial/2). 
:- dynamic factorial/2. 

factorial(5, 120). 
factorial(4, 24). 
factorial(3, 6). 
factorial(2, 2). 
factorial(1, 1). 
factorial(0, 1). 

true. 

Answer 4

無! Моя совесть заставляет меня un-ask your question.

За то, что вы искать является no-no -Даже в imperative-programming -И более в Прологе.

prolog-assert, конечно, может быть очень полезным в некоторых обстоятельствах; Обычно я рассматриваю его как «оружие последней инстанции», а не как «первое оружие выбора». ИМО вероятные последствия его использования включают:

• declarative-programming оставлен позади.
• logical-purity легко теряется.
• debugging становится намного сложнее.
• code-complexity поднимается.
• performance капель.
• пахнет global-variables.

Дело в точке? Возьмите ответы by @CapelliC и by @Boris. кавычки @Boris:

Я пишу этот ответ, потому что он имеет немного меньше ненужного кода, чем иначе правильный ответ по @CapelliC.

Давайте запустим несколько запросов и положим эту оценку на тест!

?- factorialBoris(0,0). 
**LOOPS** 

?- factorialBoris(0,2). 
**LOOPS** 

?- factorialBoris(1,2). 
**LOOPS** 

?- factorialCapelliC(0,0). 
**LOOPS** 

?- factorialCapelliC(0,2). 
**LOOPS** 

нет!

Пожалуйста, не поймите меня неправильно! Я не хочу подавать работу и усилие by @CapelliC и by @Boris, два Prolog topusers on SO, в любом случае, форма или форма.

---

Итог:

Использование imperative-programming стиля при кодировании в Прологе может легко иметь неприятные последствия!

Тщательное тестирование кода с использованием prolog-assert гораздо сложнее, чем тестирование logically-pure кода и даже что может быть довольно много, поверьте!

В случае неопределенности выберите мудрый путь: просто делать то, что правильно :)

Preserve logical-purity по возможности-не торговать в ничего взамен.