## Re: "ocaml_beginners"::[] tail recursion

Expand Messages
• ... OK, let me try :-) The result of the recursive call must be the result which is returned, without passing through any processing. Note that the question is
Message 1 of 44 , May 4, 2005
On Thu, 5 May 2005, vly3 wrote:

> I am having trouble understanding tail recursion. I have read the
> posts about tail recursion in the archives, and I have used google to
> look up articles on tail recursion, and I still don't understand how
> to tell if a function is tail recursive or not, other than to try it
> in the OCaml interpreter with a large number of recursions and see if
> it runs out of stack space. Maybe a simple example would help me.
> For instance, if I define function f as follows:
>
> let rec f x = if x = 1 then (x * 2) else ( x * 2) + f (x - 1);;
>
> If I call
>
> f 100000;;
>
> The stack overflows with the message:
> Stack overflow during evaluation (looping recursion?).
>
> From that, I assume that my function f is not tail recursive. Can
> anybody rewrite that in tail recursive form, or give me an explanation
> of tail recursion simple enough for an idiot to understand?

OK, let me try :-)

The result of the recursive call must be the result which is
returned, without passing through any processing.
Note that the question is not whether the function is tail-recursive, but
whether the compiler knows it and performs the appropriate optimization:

(* detected as tail-recursive *)
let rec f () = f ()
let rec f () = if Random.int 2 = 0 then f () else f ()
let rec f x = (fun () -> f x) ()
let rec f () = g ()
and g () = f ()

(* not detected as tail-recursive *)
let rec f () = f (); ()
let rec f () = let x = f () in x
let rec f () = try f () with Exit -> ()

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr
• ... Yes. ... No but that is related because non-strict languages require purity to be deterministic. ... Yes. The result is a sequence of n closures, each
Message 44 of 44 , Jul 4, 2008
On Friday 04 July 2008 06:04:45 marlenemiller71 wrote:
> Jon Harrop wrote:
> > Actually that (eta reduction, IIRC) is a dangerous practice in impure
> > languages like OCaml because it changes when the expressions are
> > evaluated.
>
> impure?

Yes.

> do you mean eager (as opposed to lazy)?

No but that is related because non-strict languages require purity to be
deterministic.

> > In this case, eta reducing by removing the "x" arguments from both sides
> > of the definition causes the function to partially evaluate sooner,
> > yielding a closure that encapsulates "n" nested function applications. If
> > you remove
>
> # let two n = 2 * n;;
>
> # let rec iter = fun n -> fun f ->
> if (n=0) then fun x->x else compose f (iter (n-1) f);;
> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
>
> Here, if... is evaluated and iter is applied 5 times. Right?
> # iter 5 two;;
> - : int -> int = <fun>

Yes. The result is a sequence of n closures, each calling the next and the

> # let rec iter = fun n -> fun f -> fun x ->
> if (n=0) then x else iter (n-1) f (f x);;
> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
>
> Whereas here, fun x... is evaluated but not if... Right?
> # iter 5 two;;
> - : int -> int = <fun>

Exactly, yes. The result is a single closure that captured "n", "f" and will
fully apply "iter" just as soon as it gets its third and final argument.

> > all arguments that were otherwise deferring the evaluation then
> > you can even
> > change the type of the expression from polymorphic to monomorphic,
> > where the
>
> Hmm! (to do: find an example)

Very easy, just partially apply any of the built-in polymorphic HOFs:

# let f = List.map List.map;;
val f : ('_a -> '_b) list -> ('_a list -> '_b list) list = <fun>

> > non-generalized type variable (e.g. '_a) will be ossified at first
> > use or even resulting in a type error if it tries to escape a compilation
> > unit.
>
> Hmm :-(

There is a trade-off between that and purity. As Haskell has shown, purity
sucks.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
Your message has been successfully submitted and would be delivered to recipients shortly.