Exception "STACK_OVERFLOW" in ocaml

Question

Ich wollte fragen, ob die Ausnahme: "Ausnahme STACK_OVERFLOW" eine unendliche Schleife verursacht werden könnte, insbesondere die Ausnahme in dem folgenden Code auftritt:

(*the loop "while" should stop when both stacks are empty*) 
    while (not (Stack.is_empty stackFalse))|| (not (Stack.is_empty stackTrue)) do  
    (
     if (not (Stack.is_empty stackTrue)) then 
     (
      let q1 = Stack.pop stackTrue in 
      let (_,_,ptrs) = fst (Hashtbl.find graph (fst q1)) in 
      List.iter (fun elem -> 

          let app = Hashtbl.find graph elem in 
          let (typeNode,last,ptrs') = fst app in 

          if typeNode = "Or-node" then 
          (
           Stack.push (elem,true) stackTrue; 
           Hashtbl.add labeled elem true 
          ) 
          else if last = false then               
           Hashtbl.replace graph elem ((typeNode,true,ptrs'),snd app) 
          else 
          (
           Stack.push (elem,true) stackTrue; 
           Hashtbl.add labeled elem true 
          )  ) ptrs ; 
     ); 

     if (not (Stack.is_empty stackFalse)) then    
     (
      let q2 = Stack.pop stackFalse in 
      let (_,_,ptrs1) = fst (Hashtbl.find graph (fst q2))in 

      List.iter (fun elem -> 

          let app = Hashtbl.find graph elem in 
          let (typeNode,last,ptrs') = fst app in 

          if typeNode = "And-node" then 
          (
           Stack.push (elem,false) stackFalse; 
           Hashtbl.add labeled elem false 
          )        
          else if last = false then               
           Hashtbl.replace graph elem ((typeNode,true,ptrs'),snd app) 
          else 
          (
           Stack.push (elem,false) stackFalse; 
           Hashtbl.add labeled elem false 
          ) ) ptrs1 ; 
     ); 

    ) 
    done; 

Answer 1

Standard-Erste-Hilfe: kompiliere mit -g und starte mit OCAMLRUNPARAM = b (siehe Handbuch), um Backtrace zu sehen.

PS Ich würde strukturelle Vergleiche vermuten (z. B. von Hashtbl.find verwendet), gibt es irgendwelche Zirkelverweise in Hashtbl-Elementen?

Answer 2

Der Stapel wächst, wenn Sie eine Anruferfunktion eingeben. while Schleifen und Tail-Aufrufe wachsen nicht den Stapel, so dass ein Stack_overflow Fehler kann nicht aus wie Schleife.

Wie von ygrek vorgeschlagen, kann eine zyklische Datenstruktur einen Stapelüberlauf verursachen, wenn Sie den Strukturvergleichsoperator = verwenden. Sie verwenden = in Ihrem Code und das Modul verwendet Pervasives.compare intern; Wenn die Hashtbl-Schlüssel zyklisch sind, können alle Schlüsselverwendungsoperationen in eine Endlosschleife laufen. In diesem Fall wäre es eine gute Lösung, das modularisierte Formular Hasthbl (Hashtbl.Make) zu verwenden, mit dem Sie eine benutzerdefinierte Gleichheitsfunktionalität zur Verfügung stellen können.

Eine häufigere Ursache für Stapelüberlauf ist die Tatsache, dass einige der Funktionen des List-Moduls der Standardbibliothek nicht tail-rekursiv sind. Wenn sie auf eine ausreichend große Liste mit einem kleinen Stack-Limit angewendet werden, können sie Stapelüberläufe verursachen. In diesem Fall ist die Verwendung des List Moduls von Extlib oder Batteries - das Nachrüstimplementierungen bietet - eine gute Lösung. Dies ist jedoch nicht Ihr Problem hier, wie ist tail-recursive bereits.