堆栈自动修改时不应该

Question

我在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。任何帮助确定为什么原始堆栈作为函数中的参数传递并不会保持不变将非常感激！

Answer 1

这是很多需要阅读的代码。想到的主要原因是你使用了两个可变数据结构，一个在另一个内部。乳清你做Stack.copy，它不会复制里面的队列。因此，如果您修改此副本中的队列，它们也会在原始中进行修改。

这些问题正是为什么使用不可变数据结构如此愉快。

这可能太简单了，但也许会有帮助。