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 GAA28757; Wed, 19 Nov 2003 06:52:29 +0100 (MET)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id GAA28768 for <caml-list@pauillac.inria.fr>; Wed, 19 Nov 2003 06:52:28 +0100 (MET)
Received: from herd.plethora.net (herd.plethora.net [205.166.146.1])
	by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hAJ5qR123704
	for <caml-list@inria.fr>; Wed, 19 Nov 2003 06:52:27 +0100 (MET)
Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49])
	by herd.plethora.net (8.11.6/8.10.1) with ESMTP id hAJ5osC09888;
	Tue, 18 Nov 2003 23:50:58 -0600 (CST)
Date: Wed, 19 Nov 2003 00:50:24 -0600 (CST)
From: Brian Hurt <bhurt@spnz.org>
X-X-Sender: bhurt@localhost.localdomain
To: Dustin Sallings <dustin@spy.net>
cc: Caml Mailing List <caml-list@inria.fr>
Subject: Re: [Caml-list] tail call optimization
In-Reply-To: <94AC2632-1A50-11D8-A557-000393CB0F1E@spy.net>
Message-ID: <Pine.LNX.4.44.0311190041000.5009-100000@localhost.localdomain>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; caml-list:01 violates:01 violates:01 appending:01 snippets:01 recursion:01 overflows:01 ocaml:01 rec:01 rec:01 lib:01 nov:01 overflow:02 match:02 eof:02 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

On Tue, 18 Nov 2003, Dustin Sallings wrote:

> 
> 	I read something on the list about how a function may be tail 
> recursive, but not be compiled with tail call optimization.  What kinds 
> of things might cause this?
> 
> 	Specifically, I've got an ``iter_lines'' function I'd like to turn 
> into a ``fold_lines'' function that looks something like this (a few 
> different functions for different things):
> 
> let rec fold_lines f init_value ch =
>      try
>          let v = f (input_line ch) init_value in
>          fold_lines f v ch
>      with End_of_file -> init_value;
> ;;

This function is not tail recursive.  Basically, if the recursive call 
either a) is wrapped in a try block, or b) has it's return value modified 
in any way, the function isn't tail recursive.  Your function violates 
clause a, the following function violates clause b:

let append a b =
	match a with
		| [] -> b
		| h :: t -> h :: (append t b)
;;

Since we're appending h to the return value of the recursive call, it 
isn't tail recursive.

I recommend coding the your function like:

let rec fold_lines f init_value ch =
	let line, eof = try (input_line ch), false
			with End_of_file -> "", true
	in
	if eof then
		init_value
	else
		fold_lines f (f line init_value) ch
;;

Now that the recursive call is outside the try block, and you aren't 
modifying the return value, so all is good.
 
> dustinti:~/prog/eprojects/snippets/ocaml/lib 586% wc -l numbers
>   4769526 numbers
> # Fileutils.fold_file_lines (fun x y -> y + 1) 0 "numbers";;
> Stack overflow during evaluation (looping recursion?).

Stack overflows are a classic sign of a function you thought was tail 
recursive not being tail recursive.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
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