回溯太多：爲什麼這裏有「重做」？

我在Prolog中做了一個非常簡單的練習，有一些我在跟蹤中不理解。該計劃是一個「大於」（>）上表示爲接班人的整數：回溯太多：爲什麼這裏有「重做」？

greater_than(succ(_), 0). 
greater_than(succ(A), succ(B)) :- 
    greater_than(A, B).

我的問題：我不明白爲什麼請求greater_than(succ(succ(succ(0))),succ(0))在下面的跟蹤生成redo：

[trace] ?- greater_than(succ(succ(succ(0))),succ(0)). 
Call: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep 
Call: (7) greater_than(succ(succ(0)), 0) ? creep 
Exit: (7) greater_than(succ(succ(0)), 0) ? creep 
Exit: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep 
true ; 
Redo: (7) greater_than(succ(succ(0)), 0) ? creep 
Fail: (7) greater_than(succ(succ(0)), 0) ? creep 
Fail: (6) greater_than(succ(succ(succ(0))), succ(0)) ? creep 
false.

這裏爲什麼會有redo？我怎樣才能避免它（當然，沒有削減）？

順便說一句，我可以告訴大家：不，它不是某種功課......

來源

2012-08-30 Eusebius

這只是你問的一個優化，給定的編譯器可能有或沒有。 –

那麼，一般來說，我認爲優化一個人的代碼是一個合法的編程問題，即使只編寫一種編譯器（這裏是SWI）。然而，我剛剛更新了SWI，我甚至不再看到這種行爲，所以它對SWI來說真的是內部的，我想這個問題確實沒有興趣。對於噪音抱歉。 – Eusebius

我在SWI安裝上試過了你的代碼，它沒有*嘗試任何重做。它不僅是編譯器，也是它的版本。我看到你更新了它;也許這是一個非常舊的版本。 –

OK，所以這是一個給定的編譯器/版本組合可能會或可能不會有一個編譯器優化。

SWI的後續版本不存在此問題。它可能與子句索引有關。這種行爲可以在沒有建立索引的實現上看到，或者只在第一個參數上使用索引。

但顯然是"SWI-Prolog provides `just-in-time' indexing over multiple arguments"。 SWI 5.6.56手冊states表示「最多可以索引4個參數」。所以它可能索引不止一個。

來源

2012-08-30 09:30:00

感謝您的詳細信息。我確認問題似乎在版本5.10.4中解決了（但也可能在一些早期版本中）。 – Eusebius

@Eusebius *更早*。 :)它在5.4.4中工作。太。 –

有原因還有一個重做是序言不能推斷出（不檢查的話），如果通過之後的下一個條款，會有一個替代解決方案。誠然，在這種情況下，它只是一個頭統一檢查（並非總是微不足道），但它可能需要很長時間（甚至不會終止）。

現在，這正是你應該使用cut的地方：你知道額外的選擇點不會產生一個解決方案（所以你沒有改變語義 - 綠色切割）。或者（但它主要覆蓋切口語法糖），可以使用IF-THEN-ELSE：

greater_than(succ(A), B):- 
    B = succ(BI) -> 
    greater_than(A,BI) 
    ; B = 0.

並不表明仍然沒有這將與切避免額外的計算。

PS：我懷疑有人會認爲這是功課XD

來源

2012-08-30 08:53:52

不幸的是，這不是一個綠色的切割。 'greater_than（A，B）'的工作方式不同。 –

這裏沒有「額外的選擇點」：只有一種方法可以在有「重做」的子句頭上進行統一。這個程序沒有必要削減，顯然這只是SWI中的一個過渡性錯誤。 – Eusebius

這不是一個錯誤。選擇點從左到右，從上到下。 Prolog編譯器甚至不必查看在回溯之前適合的子句下的子句。如果現在SWI優化它並不意味着之前它是一個錯誤。 – m09

回溯太多：爲什麼這裏有「重做」？

回答

相關問題