Stack automatically modifying when it shouldn't

Question

I'm implementing a Prolog interpreter in OCaml. The problem I'm having is in the main function. I'm essentially trying to store my interpreter stack within a function call, and modify a copy of this stack that is then passed to the recursive call from this particular function call. When that recursive call reports a failure, this original function call should use the original stack that I had kept unmodified and make a different recursive call (to implement backtracking).

Now, here's the problem. The stack and the temporary stack (tempstack) both get modified, when my intention is only to modify the tempstack. I've spent hours trying to figure out the problem and I'm pretty sure this is it. Here's the main function snippet..

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

The only computation that's happening on tempstack is that new goals are being inserted into it using another function (stacknewsubgoals) (Note: the stack is a stack of queues).

I tried replacing the tempstack in the innermost try loop to stack (where the main recursive call is being made). Instead of going into an infinite loop (because the same stack should be passed unmodified again and again), it terminates with a Not_Found exception which in turn is generated by my Queue.Empty exception at the bottom. In essence, somehow the queue at the bottom of the stack becomes empty when it should most definitely not be 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)

You can clearly see here that the only thing being modified by this function is tempstack. Any help in identifying why the original stack being passed as the argument in the function doesn't remain unmodified would be sorely appreciated!

Answer 1

This is a lot of code to read through. The main thing that comes to mind is that you're using two mutable data structures, one inside the other. Whey you do Stack.copy, it's not going to copy the queues inside. So if you modify queues in this copy, they will be modified in the original as well.

These sorts of problems are exactly why it's so pleasant to use immutable data structures.

This is possibly too simple an answer, but maybe it will help.