沒有使用遞歸的因子計算

Question

我試圖實現一個階乘計算（n！）的解決方案，而不使用遞歸，只使用prolog的retroaction。例如：

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所指出的那樣，你將'存儲謂詞'與'定義謂詞'混爲一談。你需要階乘/ 2的定義，所以retractall(factorial(_,_))沒什麼意義。

下面，我用retract(mem(N, F))檢索臨時變量值和最終更新準備DB。應該始終只有一個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 /收回都有了年初早前的程序員。幾個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

你已經在你的not條款有一個小寫k。

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。

prolog-assert在某些情況下肯定會非常有用;我通常認爲它是「最後的武器」，而不是「首選武器」。 IMO使用它的可能後果包括：

• 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的編碼很容易引火燒身的時候！

的使用prolog-assert代碼的嚴格測試比測試logically-pure代碼，甚至是可以是更難了不少，相信我！

在不確定的情況下，選擇明智的道路：僅僅做到這一點是正確的:)

保留logical-purity儘可能鴕鳥政策貿易它的任何回報。