Re: Ask for explanation  possibly repeated
 Pierre Weis
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  19991213 (16:42) 
From:  Pierre Weis <Pierre.Weis@i...> 
Subject:  Re: Ask for explanation  possibly repeated 
> > 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 > > etaexpansion 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... "etaexpansion" 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 etaexpansion (I don't even know what it means) need a lift... :) Here the etaexpansion is just a technical way to say that any functional value f is equal to the expression (function x > f x). Etaexpansion 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/