堆栈会自动修改它何时不应该

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,它不会复制里面的队列.因此,如果您修改此副本中的队列,它们也将在原始副本中进行修改.

这些问题正是为什么使用不可变数据结构这么令人愉快的原因.

这可能是一个简单的答案,但也许它会有所帮助.