堆棧自動修改時不應該

我在OCaml中實現了一個Prolog解釋器。我遇到的問題是主要功能。我基本上試圖將我的解釋器堆棧存儲在一個函數調用中，並修改此堆棧的副本，然後將此堆棧的副本傳遞給來自此特定函數調用的遞歸調用。當遞歸調用報告失敗時，這個原始函數調用應該使用我原來保存未修改的原始堆棧並進行不同的遞歸調用（以實現回溯）。堆棧自動修改時不應該

現在，這是問題所在。當我的意圖只是修改tempstack時，堆棧和臨時堆棧（tempstack）都會被修改。我花了幾個小時試圖找出問題，我很確定這是它。這裏的主要功能片段..

let rec main stack clauselist counter substitutions variablesinquery answers = 
try 
    let currentsubgoal = Queue.top (Stack.top stack) in 
    if counter <> List.length clauselist 
    then 
     let tempstack = Stack.copy stack in 
     try 
      let unifier = mgu1 currentsubgoal (List.nth clauselist counter) in 
      let newsubgoals = 
       match List.nth clauselist counter with 
        Fact(a) -> [] 
       | Rule(Headbody(a,b)) -> b 
      in 
      let tempstack = stacknewsubgoals tempstack unifier newsubgoals in 
      let tempsubs = match substitutions with 
       S(m) -> match unifier with S(n) -> S(m @ n) in 
      try 
       main tempstack clauselist 0 tempsubs variablesinquery answers 
      with BackTrack -> main stack clauselist (counter + 1) substitutions 
               variablesinquery answers 
     with NoUnifier -> main stack clauselist (counter + 1) substitutions 
             variablesinquery answers 
     else raise BackTrack 
with Queue.Empty -> 
    let answers = buildanswer substitutions variablesinquery :: answers in 
    raise BackTrack

這是發生在tempstack唯一的計算是新的目標正在使用其他的功能（stacknewsubgoals）（注：堆棧隊列的棧）插入到它。

我試圖將最內層的try環中的tempstack替換爲堆棧（主遞歸調用正在進行）。而不是進入一個無限循環（因爲同一個棧應該一次又一次地傳遞），它終止於一個Not_Found異常，而這個異常又是由我的Queue.Empty異常在底部產生的。從本質上講，堆棧底部的隊列在不應該是空的時候會變成空的。

let stacknewsubgoals tempstack unifier newsubgoals = 
let tempq = Stack.pop tempstack in 
    let subbedq = substituteinqueue tempq unifier (Queue.create()) in 
     if (newsubgoals <> []) then 
      (Stack.push subbedq tempstack; 
      Stack.push (Queue.create()) tempstack; 
      initialize (Stack.top tempstack) (substpredicatelist newsubgoals unifier); 
      tempstack) 
     else 
      (Stack.push subbedq tempstack; 
      ignore (Queue.pop (Stack.top tempstack)); 
      tempstack)

你可以清楚地看到這裏唯一被這個函數修改爲tempstack。任何幫助確定爲什麼原始堆棧作爲函數中的參數傳遞並不會保持不變將非常感激！

來源

2013-03-28 krandiash

我重新格式化了您的問題中的第一個代碼塊，以更好地匹配通常的ocaml編碼標準。閱讀對我來說（也許還有其他很多）看起來更容易。如果您不喜歡，請隨時將更改回滾到您的版本。我也自由地刪除了多餘的包袱。我希望你不會介意這種侵入性修改你的原始條目。 – didierc 2013-03-28 22:32:19

這是很多需要閱讀的代碼。想到的主要原因是你使用了兩個可變數據結構，一個在另一個內部。乳清你做Stack.copy，它不會複製裏面的隊列。因此，如果您修改此副本中的隊列，它們也會在原始中進行修改。

這些問題正是爲什麼使用不可變數據結構如此愉快。

這可能太簡單了，但也許會有幫助。

來源

2013-03-28 05:27:21

太棒了！就是這樣！我已經完成了整個事情，它的工作原理！那謝謝啦！：d – krandiash 2013-03-31 13:42:05

堆棧自動修改時不應該

回答

相關問題