Исключение "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

Стандартная первая помощь: перекомпилируйте с -g и запустите с OCAMLRUNPARAM = b (руководство по cf), чтобы увидеть обратную трассировку.

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

Answer 2

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

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

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