強迫變量重新分配（Prolog）

Question

作業是取兩個變量，一個介於0和10,000之間的數字以及1和這個數字之間有多少個圓形素數。

我無法通過遞歸傳回變量（回溯是它被稱爲，我想。）我得到正確的數字，我很確定我有概念下來，我遇到的問題是（？！），它當我嘗試重新分配變量拋出一個錯誤

下面是代碼：

circPrimeCompare(Below, NumCirc):- 
    RealNum is 0, 
    circPrimeCompare(1, Below, RealNum, []), 
    print('R: '), 
    print(RealNum), 
    nl, 
    (NumCirc =:= RealNum). 

circPrimeCompare(_, 0, _, _).  
circPrimeCompare(N, 1, _, _):- prime(N), print('aaa'). 
circPrimeCompare(X, Below, RealNum, L):- 
    (prime(X), X<Below -> 
     print(X), 
     nl, 
     numDigits(X, Y), 
     rotate(X, Y, N2), 
     ( prime(N2) 
      -> RealNum2 is RealNum + 1 
      ; RealNum2 is RealNum 
      ), 
     X2 is X + 1, 
     ( not(circPrimeCompare(X2, Below, RealNum2, L)) 
      -> RealNum = RealNum2, print(RealNum), nl 
      ; RealNum = RealNum2, print(RealNum), nl 
      ), 
     print('RealNum2: '), 
     print(RealNum), 
     nl 
    ; 
    (X<Below -> 
     X2 is X + 1, 
     RealNumPass is RealNum, 
     ( not(circPrimeCompare(X2, Below, RealNumPass, L)) 
      -> RealNum = RealNumPass, print(RealNum), nl 
      ; RealNum = RealNumPass, print(RealNum), nl 
      ), 
     print('RealNum: '), 
     print(RealNum), 
     nl 
     ) 
    ). 

這裏是跟蹤：

Fail: (26) circPrimeCompare(10, 10, 4, []) ? creep 
^ Exit: (25) not(user:circPrimeCompare(10, 10, 4, [])) ? creep 
    Call: (25) 4=4 ? creep 
    Exit: (25) 4=4 ? creep 
... 
    Exit: (24) circPrimeCompare(9, 10, 4, []) ? creep 
^ Fail: (23) not(user:circPrimeCompare(9, 10, 4, [])) ? creep 
    Call: (23) 4=4 ? creep 
    Exit: (23) 4=4 ? creep 
... 
    Exit: (22) circPrimeCompare(8, 10, 4, []) ? creep 
^ Fail: (21) not(user:circPrimeCompare(8, 10, 4, [])) ? creep 
    **Call: (21) 3=4 ? creep 
    Fail: (21) 3=4 ? creep** 
    Redo: (21) numDigits(7, _G589) ? creep 

加粗的PA rt是什麼在扔我。我真的不明白爲什麼這樣做。是否因爲變量本質上只是一個用途？任何想法如何解決它？

（。是的，我意識到這是真的，真的很可怕的代碼，我從來沒有這個任務之前寫的序言中的任何東西）

Answer 1

你沒有用「Prolog」的方式思考問題。特別是試圖「重新分配」一個變量不是Prolog的方式。變量綁定在滿足目標和子目標的方式上，而不是重新賦值，我們經常安排代碼攜帶一個「累加器」變量，只是在計算的最後階段將其值傳遞給另一個「最終」變量。

回溯和遞歸是不同的事情。當目標（或子目標）失敗時會發生回溯，並且Prolog「引擎」試圖以不同的方式來實現該目標。如果我們用完了不同的規則等來達到目標​​，那麼它就會失敗。 （這可能導致Prolog的發動機原路返回到前一個子目標，並儘量滿足是以不同的方式。）

遞歸是當一個謂語本身來定義，也就是說，如果調用謂詞可引起同樣的謂詞再次作爲子目標被調用。

要在Prolog中完成許多任務，我們必須用遞歸而不是迭代來考慮它們，這在程序語言中是很自然的。這就是我們訴諸「累加器」變量的原因，這些變量在不習慣的眼睛中顯示爲謂詞中額外且可能不必要的參數。

但是，一旦你看到這個想法在行動中，你可能會得到一些滿意的方式來以新的方式應用這個概念。

讓我們把一個模型問題加在給定列表中的數字上。天真的辦法是寫：

sum(List,Sum). 

其中List是號碼清單和Sum應該是我們的輸出，保存數值的規定金額在列表中。

的基本思想是很自然的，你考慮Head和列表的Tail，如果列表（還）沒有空，要「重新分配」 Sum = Sum + Head，然後進行遞歸應對Tail（直到列表是空的，我們有我們想要的Sum）。

但是這在Prolog中沒有意義，因爲您不能像過程語言允許的那樣更改Sum的值。這是一個累加器參數被添加到我們的謂詞中並執行相同的工作，但是以一種Prolog喜歡的方式。

sumAux([ ],Sum,Sum). 
sumAux([H|T],Accum,Sum) :- 
    NewAccum is Accum + H, 
    sumAux(T,NewAccum,Sum). 

sum(List,Sum) :- sumAux(List,0,Sum). 

這裏，我們引入了「auxillary」謂詞sumAux/3有一個額外的參數，我們已經通過了「蓄電池」中間參數設置爲爲零，但經過List並且在謂詞來定義sum/2Sum參數。

稍微思考一下它的工作方式將會回報你的努力，很快我會希望你將以各種新穎的方式應用這種範式（例如計算循環素數）。

Answer 2

"backtracking"是概念的名稱;這意味着回到自己身上，如果這已經證明是不幸的，就會違背自己的決定。在Prolog程序中，我們制定了一些規則，用於顯示哪些子目標必須被證明，主要目標（規則的負責人）被視爲已被證明。當有幾條規則時，我們可能會嘗試第一條;如果後來證明它不能被證明，我們回溯到最新的決策點，並嘗試證明下一個規則，如果可用的話。展望未來，我們實例化我們的變量，給它們賦值。一旦確定了一個變量的值，它就不能改變，而我們仍然在向前邁進，以證明我們的目標。當我們說X=2，我們承諾這個選擇。我們現在不能說X=5，那麼我們會成爲騙子，而我們的「證明」將變得毫無價值。

的Prolog的本質是，當我們前進朝證明了我們的目標，並就什麼是什麼，我們將收集這些值轉換成什麼知道的替代，變量和它們的值之間的映射，這是各種決策不自相矛盾;當我們達到最終目標時，這組變量的值就是我們的答案。

但是，當我們失敗並且必須回溯時，我們迄今爲止所做的所有實例化都是以相反的順序撤消的。

具體來說，NumCirc =:= RealNum不是一項任務。這是一個數字比較，可能是真的或假的。如果這是真的，我們說目標NumCirc =:= RealNum成功（被證明）。如果它是假的，我們說目標失敗，因此我們回溯。

另一個關鍵概念是unification：當我們說X = Y時，我們聲稱它們都是相同的。當然4=4成功，並且失敗。

是的，序言本質上是一個set-once language（SANS回溯，這撤消分配，不改變它，再次使得可變未分配）。

Answer 3

正如已經指出的那樣，一個常見的序言習慣是使用與累加器一起播種的'助手'謂詞來完成工作。此外，它有助於將問題分解爲更小，更簡單的部分。通常你會擁有我稱之爲「公共謂詞」的東西，除了強制約束並調用一個完成所有工作的「私人」助手謂詞之外，它並沒有多大作用。通常，輔助謂詞與公共謂詞具有不同的名稱（例如foo/3而不是公共謂詞foo/2）。事情是這樣的：

% 
% count the number of circular primes below the specified 
% upper limit. 
%  
count_circular_primes(Max , Cnt) :- 
    integer(Max) , 
    Max >=  1 , 
    Max =< 10000 , 
    count_circular_primes(Max , 0 , Cnt) 
    . 

助手謂詞這裏，count_circular_primes/3使用被播種爲0。它看起來像一個累加值：

count_circular_primes(0 , Cnt , Cnt) . 
count_circular_primes(N , T , Cnt) :- 
    N > 0 , 
    is_circular_prime(N) , 
    T1 is T + 1 , 
    N1 is N - 1 , 
    count_circular_primes(N1,T1,Cnt) 
    . 

你會發現，這是所有的計數發生。剩下要做的就是確定一個特定的整數是否是一個循環的素數。簡單！

您還會注意到，結果變量Cnt與任何內容都沒有統一，直到整個遞歸操作完成。當N達到零時，累加器T與結果統一。

現在框架已經到位了，讓我們考慮一下如何確定一個整數是否是一個圓形的素數。這應該是很容易的：

1. 數字是素數？
2. 將其視爲循環緩衝區並將數字向左旋轉1位
3. 重複，直到您重新開始。

下面是我將如何做列表旋轉。回溯將產生整組列表轉：

rotate(Xs,Ys) :- 
    append(A,[B|C],Xs) , % get the prefix (A) , suffix (C) and current item (B) from Xs 
    append(C,A,D)  , % append the suffic (C) to the prefix (A) to get the leftmost bit (B) 
    append([B],D,Ys)  % append the current item (B) to the leftmost bit (D) to get the rotation 
    . 

下面是它如何工作的：append/3可以用來生成指定列表中的所有可能的前綴/後綴組合。如果我說append(Prefix,Suffix,[1,2,3,4])全套通過回溯恢復解決方案是

Prefix Suffix 
========= ========= 
[]  [1,2,3,4] 
[1]   [2,3,4] 
[1,2]   [3,4] 
[1,2,3]   [4] 
[1,2,3,4]  [] 

一旦你可以產生旋轉，findall/3可以用來獲得整個解決方案設置爲一個列表，給定一個特定的輸入。因此，鑑於上述rotate/2謂語，我可以這樣說：

[ [1,2,3,4] , [2,3,4,1] , [3,4,1,2] , [4,1,2,3] ] 

一旦你有一組旋轉的，你已經：

findall(X , rotate([1,2,3,4] , X) , Rotations). 

Rotations將列出的這份名單統一必須評估它是否代表素數。你可以做到這一點與forall/2，沿着這些線路：

forall(member(Rotation,Rotations), is_prime(Rotation)) 

事情變得有點棘手，如果你不能使用findall/3和forall/2，但這應該給你對你的方式，我想。