0

我在 OCaml 中实现了一个 Prolog 解释器。我遇到的问题在于主要功能。我实际上是在尝试将我的解释器堆栈存储在函数调用中，并修改此堆栈的副本，​​然后将其传递给来自此特定函数调用的递归调用。当该递归调用报告失败时，该原始函数调用应使用我保持未修改的原始堆栈并进行不同的递归调用（以实现回溯）。

现在，问题来了。当我的意图只是修改临时堆栈时，堆栈和临时堆栈（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。任何帮助确定为什么作为函数中的参数传递的原始堆栈不会保持不变，我们将不胜感激！

4

1 回答 1

5

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

这类问题正是使用不可变数据结构如此令人愉快的原因。

这可能是一个太简单的答案，但也许会有所帮助。

于 2013-03-28T05:27:21.360 回答