From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA05465; Thu, 5 Jun 2003 20:01:19 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA05444 for ; Thu, 5 Jun 2003 20:01:18 +0200 (MET DST) Received: from athlon.baretta.com ([213.255.109.130]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h55I1HH24536 for ; Thu, 5 Jun 2003 20:01:17 +0200 (MET DST) Received: from baretta.com (localhost.localdomain [127.0.0.1]) by athlon.baretta.com (Postfix) with ESMTP id C2F367DB2; Thu, 5 Jun 2003 14:02:00 -0400 (EDT) Message-ID: <3EDF8598.6070804@baretta.com> Date: Thu, 05 Jun 2003 20:02:00 +0200 From: Alessandro Baretta Organization: Baretta srl -- www.baretta.com User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3.1) Gecko/20030425 X-Accept-Language: it, en MIME-Version: 1.0 To: Brian Hurt , Ocaml Subject: Re: [Caml-list] Map module References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; alessandro:01 baretta:01 caml-list:01 bug:01 cap:99 scanf:01 sscanf:01 prov:99 printf:01 alex:01 rec:01 overflow:02 tree:02 stack:02 module:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Brian Hurt wrote: > On Thu, 5 Jun 2003, Alessandro Baretta wrote: > > > Glancing at the code, it appears to be a height-balanced tree. So > operations should use only O(log N) stack frames- call it something less > than 32 stack frames for 80K elements. Which means either there is a bug > in that code, or your insert routine is not tail-recursive. > The insert routine is actually tail recursive, but somewhere else there is something which is not tail recursive. I have now tried converting my code to simple read-parse-print tail recursive functional cycle and still I get a Stack overflow. Here's the code: let read_cap s = Scanf.sscanf s "%2s %5[0-9]%[^\r\n]%[\r\n]" let rec output_table input_ch = try let line = input_line input_ch in let prov, cap = read_cap line (fun p c _ _ -> p, c) in Printf.printf "%s\t%s\n" cap prov; output_table input_ch with | End_of_file -> print_string "" | Scanf.Scan_failure (_) -> output_table input_ch *** Ok, now I'm using a "while true" cycle with exceptions. This simply cannot overflow. let output_table2 input_ch = try while true do try let line = input_line input_ch in let prov, cap = read_cap line (fun p c _ _ -> p, c) in Printf.printf "%s\t%s\n" cap prov with Scanf.Scan_failure (_) -> () done with End_of_file -> () And, yes, this does work. So what is wrong with the recursive version? Alex ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners