[Caml-list] How to find out if a function is tail recursive?

[Caml-list] How to find out if a function is tail recursive?

[Richard Jones]

I was writing the section on tail recursion in the OCaml tutorial, and
was surprised to find out that the range function (below) isn't tail
recursive. Or at least it causes a stack overflow on a
large-but-not-unreasonable input value.

let rec range a b =
  if a > b then []
  else a :: range (a+1) b
  ;;

let list = range 1 1000000;;

Printf.printf "length = %d\n" (List.length list);;

Can you tell me why this function isn't tail recursive, and share any
useful tips on how to tell whether a function is or is not tail
recursive?

Thanks,

Rich.

-- 
Richard Jones, Red Hat Inc. (London) and Merjis Ltd. http://www.merjis.com/
http://www.annexia.org/ Freshmeat projects: http://freshmeat.net/users/rwmj
MONOLITH is an advanced framework for writing web applications in C, easier
than using Perl & Java, much faster and smaller, reusable widget-based arch,
database-backed, discussion, chat, calendaring:
http://www.annexia.org/freeware/monolith/

-------------------
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] How to find out if a function is tail recursive?

[Paul Steckler]

> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
> 
> let list = range 1 1000000;;
> 
> Printf.printf "length = %d\n" (List.length list);;
> 
> Can you tell me why this function isn't tail recursive, and 
> share any useful tips on how to tell whether a function is or 
> is not tail recursive?

The recursive call to range is not the result for its 
caller.  Instead, the result of recursive call is 
an argument to the cons (the :: operator).

-- Paul

-------------------
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] How to find out if a function is tail recursive?

[Wolfgang Müller]

On Thursday 12 June 2003 16:15, Richard Jones wrote:
> I was writing the section on tail recursion in the OCaml tutorial, and
> was surprised to find out that the range function (below) isn't tail
> recursive. Or at least it causes a stack overflow on a
> large-but-not-unreasonable input value.
>
> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
>
> let list = range 1 1000000;;
>
> Printf.printf "length = %d\n" (List.length list);;
>
> Can you tell me why this function isn't tail recursive, 

I'll try, just to get some brainy people review my code :-)

let my_range a b = 
	let rec r a b out_range=if a>b 
		then out_range 
		else r a (b-1) (b::out_range)
	in r a b [] ;;

The difference is that when your_range is at the end of recursion, it will 
give back the empty list. To this, the innermost "a" will be prepended to [], 
then the before-innermost "a" will be prepended to that, etc... The stack 
needs to memorize this "onion" of things that need to be prepended --> not 
tail recursive.

my_range will give back at the end of the recursion the finished result. 
Nothing has to be done anymore except giving back out_range, so we can give 
it back, and do not need to remember where we came from, except for the 
initial call.

> and share any
> useful tips on how to tell whether a function is or is not tail
> recursive?

If I remember right, in the Scheme R5RS standard document there is a very 
formal description of when things are tail-recursive based on Scheme syntax.

Cheers,
Wolfgang

-------------------
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] How to find out if a function is tail recursive?

[Luc Maranget]

> 
> > let rec range a b =
> >   if a > b then []
> >   else a :: range (a+1) b
> >   ;;
> > 
> > let list = range 1 1000000;;
> > 
> > Printf.printf "length = %d\n" (List.length list);;
> > 
> > Can you tell me why this function isn't tail recursive, and 
> > share any useful tips on how to tell whether a function is or 
> > is not tail recursive?
> 
> The recursive call to range is not the result for its 
> caller.  Instead, the result of recursive call is 
> an argument to the cons (the :: operator).
> 
> -- Paul

Hence, here is a tail-recursive range function.

let rec do_range a b r =
  if a > b then r
  else do_range a (b-1) (b::r) (* tail-rec call *)
  ;;

let range a b = do_range a b []
;;

--Luc

-------------------
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] How to find out if a function is tail recursive?

[Neel Krishnaswami]

Richard Jones writes:
> I was writing the section on tail recursion in the OCaml tutorial, and
> was surprised to find out that the range function (below) isn't tail
> recursive. Or at least it causes a stack overflow on a
> large-but-not-unreasonable input value.
> 
> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
> 
> let list = range 1 1000000;;
> 
> Printf.printf "length = %d\n" (List.length list);;
> 
> Can you tell me why this function isn't tail recursive, and share any
> useful tips on how to tell whether a function is or is not tail
> recursive?

A function call is a tail call if it is the last thing that the
function does before returning. In this example:

 let rec range a b =
   if a > b then
      []  
   else
      a :: range (a+1) b

The two expressions '[]' and 'a :: range (a+1) b' are in tail
position. The recursive call to range is *not* in tail position,
because you need to do the 'a :: <value>' before returning.

You can identify 'tail position' as a purely syntactic criterion, and
then a 'tail call' is any function call in tail position.

With the function definition 

  let f x = <expr>

<expr> is an expression in tail position.

If you have an expression <expr> in tail position, then

If <expr> = <f> <x>, then:
 
  o neither subexpression <f> nor <x> is in tail position,
  o the call '<f> <x>' is in tail position

If <expr> = if <test>
            then <e_1>
            else <e_2>, then:

  o <test> is not in tail position
  o <e_1> and <e_2> are in tail position

If <expr> = match <m> with
            | pat -> <e_1>
            | ...
            | pat -> <e_n>, then:

  o <m> is not in tail position
  o <e_1> ... <e_n> are in tail position.

If <expr> = begin
              <e_1>;
              ...
              <e_n-1>;
              <e_n>
            end, then:

  o <e1> ... <e_n-1> are not in tail position
  o <e_n> is in tail position

If <expr> = try <body> with exn -> <handler>, then:

  o <body> is not in tail position
  o <handler> is in tail position

-- 
Neel Krishnaswami
neelk@alum.mit.edu

-------------------
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] How to find out if a function is tail recursive?

[Chris Uzdavinis]

Richard Jones <rich@annexia.org> writes:

> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
>
> let list = range 1 1000000;;
>
> Printf.printf "length = %d\n" (List.length list);;
>
> Can you tell me why this function isn't tail recursive, and share
> any useful tips on how to tell whether a function is or is not tail
> recursive?

The else clause wants to build a list using the current "a" plus
whatever the recursive invocation returns.  But it can't make its
result until the recursive call completes and returns its result, so
it must hang around for the recursive call to complete.  The 2nd call
pends waiting for the 3rd, the 3rd pends waiting for the 4th, and so
on, until they start unwinding.  Called too many times and you get the
notorious overflow.

To be tail recursive, the current function must be essentially
"finished" before it invokes itself recursively.  Usually, to
implement this you have to pass all of your state to the recursive
call, such that there is nothing left to do in the current function.
When we get to the very end of the recursion, the result is
immideately available, and no unwinding is necessary.  The result is
directly returned to the original caller.

Here is how to do it for your function, which uses an internal
function to help, and passes an accumulator (result) into the next
invocation.  Each call appends to the result when the next call is
made.  The "result" starts out empty and gets filled in one piece at
at a time by the recursive calls.

  let range a b =
    let rec range_helper aa result =
      if aa > b then result
      else range_helper (aa+1) (aa :: result)
    in
      List.rev(range_helper a [])
  ;;

Notice, the tail-recursve version builds the list backwards (because
appends go to the front), so after the internal function completes, we
reverse the list to "fix" it.

-- 
Chris

-------------------
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] How to find out if a function is tail recursive?

[Brian Hurt]

On Thu, 12 Jun 2003, Richard Jones wrote:

> I was writing the section on tail recursion in the OCaml tutorial, and
> was surprised to find out that the range function (below) isn't tail
> recursive. Or at least it causes a stack overflow on a
> large-but-not-unreasonable input value.
> 
> let rec range a b =
>   if a > b then []
>   else a :: range (a+1) b
>   ;;
> 
> let list = range 1 1000000;;
> 
> Printf.printf "length = %d\n" (List.length list);;
> 
> Can you tell me why this function isn't tail recursive, and share any
> useful tips on how to tell whether a function is or is not tail
> recursive?

A function is tail recursive if it fits both of the following criteria:

1) It returns the value returned by calling itself *unmodified*.  And
modification of the return value means the functions is not tail
recursive.  This is where your example fails- it modifies the return value
br list-prepending a new item to it.  Note that even the simpliest 
"modifications" defeat tail recursion.  For example, the following code is 
*not* tail recursive:

let rec sum x = if x > 1 then x + (sum (x-1)) else x

Trying to calculate sum 80000 overflows the stack.  The general pattern 
for how to fix this is to instead accumulate the modications into a 
parameter, generally called 'accu' or 'accum' or similiar.  Often times, 
the recursion is then hidden in an inner function.  So you might rewrite 
the above function like:

let sum x =
    let rec loop i accum =
        if (i > 1) then
            loop (i-1) (i + accum) (* <-- note this line! *)
        else
            i + accum
    in
    loop x 0

So now sum 80000 correctly returns 1052556352.  With lists, we can only 
build lists backwards, not forwards.  So the general pattern is to build 
the list backwards, then reverse it at the last moment.  So you're example 
might be written like:
    let range a b =
        let rec loop i accum =
            if i > b then accum
            else loop (i + 1) (i :: accum)
        in
        List.rev (loop a [])

Note, we can put the list reversal either outside of the loop, or inside
of the loop just before we exit, like:

    let range a b =
        let rec loop i accum =
            if i > b then (List.rev accum)
            else loop (i + 1) (i :: accum)
        in
        loop a []

There's really not any difference between the two.  

2) The recursive call is not within a try/with block.

So, let's consider the "classic" problem- reading all the lines of a file 
into a list of strings.  The naive solution to this is:

let rec read_file chan =
    try
        let line = input_line chan in
        line :: (read_file chan)
    with
        End_of_file -> []

The line that reads "line :: (read_file chan)" is not tail recursive- 
we're modifying our return value (by prepending the current line onto it).  
This violates condition #1.  So we apply the normal pattern to it, and get 
try #2:

let read_file chan =
    let rec loop accum =
        try
            let line = input_line chan in
            loop (line :: accum)
        with
            End_of_file -> List.rev accum
    in
    loop []

So now we're not modifying the return value.  Instead of prepending the 
new list element to the return value, we're prepending it to the 
accumulator.  So we're no longer violating condition #1.  But we're still 
violating condition #2- the recursion is still within a try/with block.

The try/with block really only needs to surround the input_line call- but 
it also governs wether we exit the recursion or not.  So my normal pattern 
for solving this is to set a boolean variable as to wether we have data or 
not.  So the code now looks like:

let read_file chan =
    let rec loop accum =
        let line, eof = 
            try
                (input_line chan), false
            with
                End_of_file -> "", true
        in
        if eof then
            loop (line :: accum); (* <-- note, recursion now outside *)
        else
            List.rev accum
    in
    loop []

Now the recursive call is outside the try/with block.  *And*, as we're not 
modifying the return value at all, we're now tail recursive.

I'm probably missing more constraints, but it's pre-caffiene.  I'll look 
at this again later.

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] How to find out if a function is tail recursive?

[John Max Skaller]

> Hence, here is a tail-recursive range function.
> 
> let rec do_range a b r =
>   if a > b then r
>   else do_range a (b-1) (b::r) (* tail-rec call *)
>   ;;

There's a curious 'trick' with tail recursion,
to make the result an argument. That's weird,
but it works. You  pass the result down to the
end as an argument, and it gets returned only
then. For example to count a list:

	let rec count lst acc =
	match lst with
	| [] -> acc
	| h::t -> count t (acc+1)

instead of writing:

	let rec count lst =
	match lst with
	| [] -> 0
	| h :: t -> 1 + count t

which isn't tail recursive.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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] How to find out if a function is tail recursive?

[John Max Skaller]

John Max Skaller wrote:

 
>     let rec count lst =
>     match lst with
>     | [] -> 0
>     | h :: t -> 1 + count t
> 
> which isn't tail recursive.


BTW: to see the last line spoils the tail

recursion, rewrite it in functional notation:

	| h ::t -> add(1, count(t))

and you can now see that 'add' is the tail call,
not count.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


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

[Caml-list] This is so nice ..

[John Max Skaller]

I can hardly believe this works.
I copied this trick from Jacque's code

http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/mixev3.04.ml.txt

Thanks! This is really great stuff.
I feel like a dill: its exactly the same
as the parameterised class trick I already
knew about.
------------------------------------------

type 'a s1 = [`A | `B of 'a]
type  'a s2 = ['a s1 | `C]

type ss1 = 'a s1 as 'a
type ss2 = 'a s2 as 'a

let rec reduce : ss2 -> ss1 = function
     | `A -> `A
     | `B z -> `B (reduce z)
     | `C -> raise Not_found
;;

reduce (`B `C);;

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


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