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 をスタックに置き換えてみました (メインの再帰呼び出しが行われている場所)。無限ループに入る代わりに (同じスタックを変更せずに何度も渡す必要があるため)、下部にある Queue.Empty 例外によって生成される Not_Found 例外で終了します。本質的に、スタックの一番下にあるキューが空であってはならないのに、どういうわけか空になります。

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

これは、読むべきコードがたくさんあります。頭に浮かぶ主なことは、2 つの可変データ構造を使用していて、一方が他方の内部にあるということです。Stack.copy内部のキューをコピーするつもりはありません。したがって、このコピーでキューを変更すると、元のキューも変更されます。

この種の問題こそが、不変のデータ構造を使用するのが楽しい理由です。

これはおそらく単純すぎる答えですが、おそらく役立つでしょう。

于 2013-03-28T05:27:21.360 に答える