[Caml-list] tail call optimization

[Caml-list] tail call optimization

[Dustin Sallings]

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

	So, I have these other two functions:

let operate_on_file f fn =
     let ch = open_in fn in
     try
         let rv = f ch in
         close_in ch;
         rv
     with x ->
         close_in ch;
         raise x
;;

let fold_file_lines f init_value fn =
     operate_on_file (fold_lines f init_value) fn
;;

	I now want to count the lines in a file:

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?).

	Am I doing something wrong?

--
SPY                      My girlfriend asked me which one I like better.
pub  1024/3CAE01D5 1994/11/03 Dustin Sallings <dustin@spy.net>
|    Key fingerprint =  87 02 57 08 02 D0 DA D6  C8 0F 3E 65 51 98 D8 BE
L_______________________ I hope the answer won't upset her. ____________

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

Re: [Caml-list] tail call optimization

[Dustin Sallings]

On Nov 18, 2003, at 21:40, Aleksey Nogin wrote:

> On 18.11.2003 21:24, Dustin Sallings wrote:
>
>>     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;
>
> My guess is that because the recursive call is inside the "try", the 
> function is not really tail recursive.
>
> May be the following will work:
>
> let rec fold_lines f init_value ch =
>    match
>       try
>          Some (f (input_line ch) init_value)
>       with End_of_file -> None
>    with
>       Some v -> fold_lines f v ch
>     | None -> init_value

	Well, this does work, but I don't really like it.  How expensive is 
the match?  It seems to me that the try call shouldn't be relevant 
since the return value comes from the bottom of it.

--
SPY                      My girlfriend asked me which one I like better.
pub  1024/3CAE01D5 1994/11/03 Dustin Sallings <dustin@spy.net>
|    Key fingerprint =  87 02 57 08 02 D0 DA D6  C8 0F 3E 65 51 98 D8 BE
L_______________________ I hope the answer won't upset her. ____________

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

Re: [Caml-list] tail call optimization

[Brian Hurt]

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

Re: [Caml-list] tail call optimization

[Dustin Sallings]

On Nov 18, 2003, at 22:50, Brian Hurt wrote:

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

	I guess I don't understand the point of clause a.  The try block 
doesn't seem like it should prevent the optimization.

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

	Yes, this file was my test for tail recursion.  :)

--
SPY                      My girlfriend asked me which one I like better.
pub  1024/3CAE01D5 1994/11/03 Dustin Sallings <dustin@spy.net>
|    Key fingerprint =  87 02 57 08 02 D0 DA D6  C8 0F 3E 65 51 98 D8 BE
L_______________________ I hope the answer won't upset her. ____________

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

Re: [Caml-list] tail call optimization

[Frederic van der Plancke]

Dustin Sallings wrote:
> 
> On Nov 18, 2003, at 22:50, Brian Hurt wrote:
> 
> > 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)
> > ;;
> 
>         I guess I don't understand the point of clause a.  The try block
> doesn't seem like it should prevent the optimization.

Any work your function has to do before the called function returns
prevents tail-call optimisation. Unsetting a "try" exception handler is work
that has to be done at the level of the corresponding "with".

Frédéric

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

Re: [Caml-list] tail call optimization

[Brian Hurt]

On Tue, 18 Nov 2003, Dustin Sallings wrote:

> 
> On Nov 18, 2003, at 22:50, Brian Hurt wrote:
> 
> > 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
> 
> 	I guess I don't understand the point of clause a.  The try block 
> doesn't seem like it should prevent the optimization.

What would happen if f just happened to throw an End_of_file exception?  
Not to mention the fact that it's tricky for the compiler to determine 
that the call to fold_lines can't throw an End_of_file.  So the compiler 
just assumes that both might, and thus has to keep the try/catch block, 
and the context (stack frame) of the function, alive until both are 
complete.

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

Re: [Caml-list] tail call optimization

[Dustin Sallings]

On Nov 19, 2003, at 9:22, Brian Hurt wrote:

> What would happen if f just happened to throw an End_of_file exception?
> Not to mention the fact that it's tricky for the compiler to determine
> that the call to fold_lines can't throw an End_of_file.  So the 
> compiler
> just assumes that both might, and thus has to keep the try/catch block,
> and the context (stack frame) of the function, alive until both are
> complete.

	Ooh, this is the key, the compiler doesn't know that that exception 
can't be thrown.  This goes back to exception handling thread from 
earlier, I think.  If the compiler knew the exception wouldn't be 
thrown, then the tail call optimization would be possible.

	Anyway, I think this clears up my confusion, thanks.

-- 
Dustin Sallings

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