Loading ...
Sorry, an error occurred while loading the content.

Re: "ocaml_beginners"::[] tail recursion

Expand Messages
  • Martin Jambon
    ... 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
    • 0 Attachment
      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
    • Jon Harrop
      ... 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 1:54 PM
      • 0 Attachment
        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
        last calling your identity function.

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