Exception "Stack_overflow" in ocaml

Question

I wanted to ask if the exception :"exception Stack_overflow" could be caused an infinite loop , particularly, the exception occurs in the following code :

    ( *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;

To be more idiomatic to functional programming, you should replace your Stack with a list, and replace the while loop with a recursive call. Is there a reason why this section is programmed in an imperative style? — nlucaroni
– nlucaroni, Commented Jan 5, 2011 at 15:04
Generally no, while loops won't cause a stack overflow - there is no stack. — Niki Yoshiuchi
– Niki Yoshiuchi, Commented Jan 5, 2011 at 16:40

ygrek · Accepted Answer · 2011-01-05 15:00:17Z

10

Standard first-aid : recompile with -g and run with OCAMLRUNPARAM=b (cf manual) to see backtrace.

PS I would suspect structural comparison (e.g. used by Hashtbl.find), are there any circular references in hashtbl elements?

edited Jan 5, 2011 at 15:00

answered Jan 5, 2011 at 14:52

ygrek

6,69724 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gasche · Accepted Answer · 2011-01-05 23:52:38Z

The stack grows when you enter into a caller function. while loops and tail-calls do not grow the stack, so a Stack_overflow error cannot result from such as loop.

As ygrek suggested, a cyclic data structure may provoke a stack overflow if you use the structural comparison operator = on it. You use = in your code, and the Hashtbl module uses Pervasives.compare internally; if the hashtbl keys are cyclic, all key-using operations may run into infinite loop. In that case, a good fix would be to use the modularized form of Hasthbl (Hashtbl.Make) which allows you to provide a custom, cyclicity-aware equality function.

A more common cause for stack overflow is the fact that some of the functions of the List module of the standard library are not tail-recursive. If applied to big enough list with a small enough stack limit, they may cause stack overflows. In this case, using the List module of Extlib or Batteries -- which provides tailrec implementations -- is a good fix. This is not your problem here however, as List.iter is tail-recursive already.

KJ7LNW · Accepted Answer · 2022-03-07 01:26:17Z

0

The other answers address the programming style, which is good: if you have a huge stack and can fix it programatically, that is best.

However, if there is nothing you can do then note that ulimit -s controls the max stack size. For deep stacks in Coccinelle I was able to finish the transform with the following:

ulimit -s $((1024*1024))

Note that this specifies a 1GB stack and used about 2.4GB of RAM, but it worked!

answered Mar 7, 2022 at 1:26

KJ7LNW

1,98113 silver badges24 bronze badges

Collectives™ on Stack Overflow

Exception "Stack_overflow" in ocaml

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related