Re: [Caml-list] tail call optimization

[Brian Hurt <bhurt@spnz.org>]

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