[Caml-list] beginner question about tail recursion

[Caml-list] beginner question about tail recursion

[Ram Bhamidipaty]

Hi I am just getting started with OCaml. My understanding is
that it is desirable to write function in a tail recursive style.

Can the OCaml system tell me if a function is tail recursive?

-Ram

-------------------
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] beginner question about tail recursion

[Matt Gushee]

On Sat, Aug 30, 2003 at 03:52:04PM -0700, Ram Bhamidipaty wrote:
> Hi I am just getting started with OCaml. My understanding is
> that it is desirable to write function in a tail recursive style.

Well, I'm just getting started with *explaining* OCaml, so don't be
surprised if I get it wrong. But here's how I understand it:

> Can the OCaml system tell me if a function is tail recursive?

I don't think so. But it's pretty easy to tell by inspecting the code,
once you get used to it.

There are two basic rules you need to keep in mind:

1. The recursive call must be the very last thing that happens in the
   function. Another way of saying this is that the function must
   directly return the result of the recursive call to itself, with 
   absolutely no modification.

2. The recursive call can't be within a 'try' block.

Unfortunately, this means that the most intuitive pattern for many
functions (which is also the pattern found in many introductory
examples) is not tail recursive.

[ The following is mostly stolen from a previous post by Brian Hurt
  --thanks, Brian ]
A common example of the problem is a function that reads from an input
channel and returns all the lines as a list. The most obvious way to
write this function is:

1  let rec readlines chnl =
2    try
3      let line = input_line chnl in
4      line :: (readlines chnl)
5    with End_of_file -> []
        
This actually breaks both of the two rules. Rule #1 is broken in line 4,
because the cons operation ('::') is applied to the result of the
recursive call. And of course it is within a 'try' block.

A tail-recursive way to write the function would be:

  let rec readlines chnl lines =
    let line, eof =
      try
        let ln = input_line chnl in
        ln, false
      with End_of_file ->
        [], true in
    if eof then lines            (* result returned unmodified *)
    else readlines chnl (line :: lines)
                                 (* 'line :: lines' is evaluated before
                                    applying 'readlines' *)

Note the use of an accumulator (the 'lines' parameter). This is
something you often need for a tail-recursive function.

** Note to OCaml documentors **
Isn't it confusing to beginners that non-tail-recursive examples are so
common in introductory documentation? I would suggest adding warnings
along the lines of

 "The above example illustrates the simplest way to write a recursive
  function; this is not the most efficient form, and should be avoided
  in performance-critical code. For more information see the discussion
  of tail recursion in Chapter XX."

-- 
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
                            Horses bear soldiers through
                                its streets.
                                
                            --Lao Tzu (Peter Merel, trans.)

-------------------
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] beginner question about tail recursion

[Remi Vanicat]

Matt Gushee <matt@gushee.net> writes:

[...]

> A tail-recursive way to write the function would be:
>
>   let rec readlines chnl lines =
>     let line, eof =
>       try
>         let ln = input_line chnl in
>         ln, false
>       with End_of_file ->
>         [], true in
>     if eof then lines            (* result returned unmodified *)
>     else readlines chnl (line :: lines)
>                                  (* 'line :: lines' is evaluated before
>                                     applying 'readlines' *)

well, this code is tail-recursive, but it is not correct (it won't
compile). This one is better :

let rec readlines chnl lines =
    let maybe_line =
      try
        let ln = input_line chnl in
        Some ln
      with End_of_file ->
        None in
    match maybe_line with
    | Some line -> readlines chnl (line :: lines)
                                 (* 'line :: lines' is evaluated before
                                    applying 'readlines' *)
    | None -> lines            (* result returned unmodified *)

by the way, the lines in the returned list will be in the reversed
order. 
[...]


-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat

-------------------
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] beginner question about tail recursion

[Matt Gushee]

On Sun, Aug 31, 2003 at 11:12:44AM +0200, Remi Vanicat wrote:
> Matt Gushee <matt@gushee.net> writes:
> 
> [...]
> 
> > A tail-recursive way to write the function would be:
> >
> >   let rec readlines chnl lines =
> >     let line, eof =
> >       try
> >         let ln = input_line chnl in
> >         ln, false
> >       with End_of_file ->
> >         [], true in
> >     if eof then lines            (* result returned unmodified *)
> >     else readlines chnl (line :: lines)
> >                                  (* 'line :: lines' is evaluated before
> >                                     applying 'readlines' *)
> 
> well, this code is tail-recursive, but it is not correct (it won't
> compile). This one is better :

Oops. You're right. Although I use this technique myself, apparently I
have never done exactly what I wrote above. Sorry.

> let rec readlines chnl lines =
>     let maybe_line =
>       try
>         let ln = input_line chnl in
>         Some ln

Oh, I like that. Thanks.

-- 
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
                            Horses bear soldiers through
                                its streets.
                                
                            --Lao Tzu (Peter Merel, trans.)

-------------------
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] beginner question about tail recursion

[skaller]

On Sun, 2003-08-31 at 16:33, Matt Gushee wrote:

> 2. The recursive call can't be within a 'try' block.

I think that is not quite the correct rule, the rule should
be that the call can't cross a try block boundary.
For example:

let g x = 
	let y = 
		try h x with _ -> []
	in g y

This example _contains_ a try block.

let f x = 
	try
		let g x = h x
		in g x
	with _ -> ...

this example is _contained in_ a try block.

Both have tail calls to g. But in this example:

1  let rec readlines chnl =
2    try
3      let line = input_line chnl in
4      line :: (readlines chnl)
5    with End_of_file -> []

the call of readlines _crosses_ a try
block boundary.


-------------------
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] beginner question about tail recursion (caml: addressed to trusted sender for this address)

[Warren Harris]

Unless you're dealing with very long lists, or very deep data structures 
(or writing library code that might be used with long lists, etc), going 
to extra work to avoid tail recursion isn't worth it. Being properly 
tail recursive allows the compiler to make an optimization that keeps 
the stack from growing for each recursive call. Usually you can recurse 
quite a few times (thousands) before overflowing your stack is ever an 
issue in practice. I'm not saying that being properly tail recursive 
isn't important, but it's usually not the first thing you need to worry 
about when learning a new language.

Warren

Ram Bhamidipaty - ramb@sonic.net wrote:

>Hi I am just getting started with OCaml. My understanding is
>that it is desirable to write function in a tail recursive style.
>
>Can the OCaml system tell me if a function is tail recursive?
>
>-Ram
>
>-------------------
>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
>
>  
>

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