Исключение «Stack_overflow» в OCaml

Question

Я хотел бы спросить, если исключение: «исключение Stack_overflow» может быть вызвано бесконечный цикл, в частности, исключение происходит в следующем коде:

(*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 первой помощи: перекомпилируйте с -g и запустите с OCAMLRUNPARAM = b (cf manual), чтобы увидеть обратную трассировку.

PS Я бы предположил структурное сравнение (например, используемое Hashtbl.find), существуют ли какие-либо циклические ссылки в элементах hashtbl?

Answer 2

Стек увеличивается при входе в функцию звонящего. while петли и обратные вызовы не увеличивают стек, поэтому ошибка Stack_overflow не может возникнуть из-за цикла.

Как было предложено ygrek, циклическая структура данных может спровоцировать переполнение стека, если вы используете на нем оператор структурного сравнения =. В вашем коде вы используете =, а модуль Hashtbl использует Pervasives.compare внутренне; если ключи hashtbl являются циклическими, все операции с ключом могут выполняться в бесконечный цикл. В этом случае хорошим решением было бы использовать модульную форму Hasthbl (Hashtbl.Make), которая позволяет вам предоставлять настраиваемую функцию равенства, зависящую от цикличности.

Более распространенная причина переполнения стека заключается в том, что некоторые из функций модуля стандартной архитектуры библиотеки не являются хвостовыми рекурсивными. Если применить к достаточно большому списку с достаточно небольшим лимитом стека, они могут вызвать переполнение стека. В этом случае использование модуля Extlib или Batteries, обеспечивающего реализацию tailrec, является хорошим решением. Это не ваша проблема, однако, поскольку List.iteris хвост-рекурсивный уже.