**Next message:**Norman Ramsey: "OCaml and tail recursion"**Previous message:**Damien Doligez: "Re: Finalisation in 2.02"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

From: Pierre Weis <Pierre.Weis@inria.fr>

Message-Id: <199912131621.RAA23536@pauillac.inria.fr>

Subject: Re: Ask for explanation -- possibly repeated

To: Benoit.de-Boursetty@polytechnique.org

Date: Mon, 13 Dec 1999 17:21:41 +0100 (MET)

In-Reply-To: <Pine.GSO.4.02.9912130055340.26575-100000@young.enst.fr> from "Benoit de Boursetty" at Dec 13, 99 01:25:14 am

*> > As usual: hide the side effect into the lazy side of the language that
*

*> > is usually considered as pure and applicative, add a bit of
*

*> > eta-expansion if your language does not know lazy evaluation properly,
*

*> > and you get a simple workaround:
*

*> >
*

*> > let translate_tree t =
*

*> > let rec aux father (Classical_node (data, sons)) =
*

*> > let rec this_node = lazy (Node (father, data,
*

*> > List.map
*

*> > (aux (Some (Lazy.force this_node)))
*

*> > sons))
*

*> > in Lazy.force this_node
*

*> > in aux None t;;
*

*> > val translate_tree : 'a classical_tree -> 'a tree = <fun>
*

*>
*

*> Erm... "eta-expansion" is not that usual to me but... well, with all my
*

*> respect, your solution doesn't seem to work.
*

*> (unless it works with version 2.04, I'm still using O'CaML 2.02)
*

*>
*

*> # let essai = Classical_node ("Father", [Classical_node ("Son", [])]);;
*

*> val essai : string classical_tree =
*

*> Classical_node ("Father", [Classical_node ("Son", [])])
*

*>
*

*> # translate_tree essai;;
*

*> Stack overflow during evaluation (looping recursion?).
*

Oups! Never forget that this is the usual result with (uncautious)

lazy evaluation :) (That's why it is so difficult).

So, the evaluation was not lazy enough, since the ``this_node'' value

was needed to compute the list of its sons.

Let me have a second try with a true lazy father field:

type 'a tree = Node of ('a tree Lazy.t) option * 'a * 'a tree list

;;

let translate_tree t =

let rec aux father (Classical_node (data, sons)) =

let rec this_node = lazy (Node (father, data,

List.map

(aux (Some this_node))

sons))

in Lazy.force this_node

in aux None t;;

Now we get:

# translate_tree essai;;

- : string tree = ...

Evidently this is not completely satisfactory, since the list of sons

are not computed in a lazy maner (this list should be a lazy

list). Hence the program is still too eager (not lazy enough), since

consider the following ``classical'' tree with recursive sharing:

# let rec bug =

Classical_node

(1, [Classical_node (2,[bug]); Classical_node (3, [bug; bug])]);;

val bug : int classical_tree =

...

# translate_tree bug;;

Stack overflow during evaluation (looping recursion?).

*> Ah ha. So are mutable values a must even outside the Lazy module? Or does
*

*> your eta-expansion (I don't even know what it means) need a lift... :-)
*

Here the eta-expansion is just a technical way to say that any

functional value f is equal to the expression

(function x -> f x).

Eta-expansion is used in the example to get a fully polymorphic

definition of the translate_tree function: we write

function x -> body x, instead of body, to expose to the typechecker

the fact that we are defining a function. Hence, we write the

(polymorphic) definition

let translate_tree t =

...

in aux None t;;

instead of the monomorphic equivalent version you originally proposed

let translate_tree =

...

in aux No

(More information about this in the FAQ of the language

http://pauillac.inria.fr/caml/FAQ/)

*> Ah ha. So are mutable values a must even outside the Lazy module? Or does
*

Evidently. So is also lazy evaluation, the appropriateness of those

features depends on the problem you're trying to solve! For instance, if

you can figure out a way to solve the ``translate_tree bug'' example using

lazy evaluation, you certainly will not try to make it with mutable

values handled by hand: presumably you would say that lazy evaluation

is a must, at least inside this kind of program!

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

**Next message:**Norman Ramsey: "OCaml and tail recursion"**Previous message:**Damien Doligez: "Re: Finalisation in 2.02"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b29
: Sun Jan 02 2000 - 11:58:29 MET
*