Ask for explanation -- possibly repeated

Ask for explanation -- possibly repeated

[Benoit de Boursetty]

  Hi

  My question must already have been asked, but the error I get from the
compiler does not seem to be listed in the documentation
("This kind of expression is not allowed as right-hand side of `let rec'")

  So here's the situation. I have a basic, standard structure for trees.

# type 'a classical_tree = Classical_node of 'a * 'a classical_tree list

And now I'd like to move to another tree structure (cyclic by default)
where each node or leaf points to its parent node, if there is one.

So I want to use the following type:

# type 'a tree = Node of 'a tree option * 'a * 'a tree list

which means: Node (parent node, data, sons).

I can easily create such typed values by hand:

# let rec root = Node (None, 0, [son1; son2])
  and son1 = Node (Some root, 1, [])
  and son2 = Node (Some root, 2, []);;


But I can't manage to write the translation function from the first type
to the second one in a purely applicative fashion. It is intuitive to
write:

# let translate_tree =
    let rec aux father (Classical_node (data, sons)) =
      let rec this_node = Node (father, data,
                                List.map
                                  (aux (Some this_node))
                                  sons)
      in this_node
    in aux None

but of course this doesn't work ("This kind of expression is not allowed
as right-hand side of `let rec'", as they say) and I understand why. It's
because the contents of "this_node", not yet defined, could be looked at
in function "aux". In fact this is a correct algorithm only because
argument "father" is not accessed to in function "aux".

So, is there an applicative workaround? I know how to do it with mutable
values / references, but...

Benoit de Boursetty.

Re: Ask for explanation -- possibly repeated

[Damien Doligez]

>From: Benoit de Boursetty <debourse@email.enst.fr>
>
># let translate_tree =
>    let rec aux father (Classical_node (data, sons)) =
>      let rec this_node = Node (father, data,
>                                List.map
>                                  (aux (Some this_node))
>                                  sons)
>      in this_node
>    in aux None
>
>but of course this doesn't work ("This kind of expression is not allowed
>as right-hand side of `let rec'", as they say) and I understand why. It's
>because the contents of "this_node", not yet defined, could be looked at
>in function "aux". In fact this is a correct algorithm only because
>argument "father" is not accessed to in function "aux".

That's exactly right.


>So, is there an applicative workaround? I know how to do it with mutable
>values / references, but...

I don't think you can do it with the current system.  We would need to
do some kind of compile-time analysis to make sure the code is safe
before the compiler would accept this code.  It's not clear that we
have the manpower needed to implement this kind of feature.

-- Damien

Re: Ask for explanation -- possibly repeated

[Pierre Weis]

> >From: Benoit de Boursetty <debourse@email.enst.fr>
> >
> ># let translate_tree =
> >    let rec aux father (Classical_node (data, sons)) =
> >      let rec this_node = Node (father, data,
> >                                List.map
> >                                  (aux (Some this_node))
> >                                  sons)
> >      in this_node
> >    in aux None
> 
> >So, is there an applicative workaround? I know how to do it with mutable
> >values / references, but...

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>

Pierre Weis

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

Re: Ask for explanation -- possibly repeated

[Benoit de Boursetty]

> ># let translate_tree =
> >    let rec aux father (Classical_node (data, sons)) =
> >      let rec this_node = Node (father, data,
> >                                List.map
> >                                  (aux (Some this_node))
> >                                  sons)
> >      in this_node
> >    in aux None
> > [ doesn't compile ]
> >So, is there an applicative workaround? I know how to do it with mutable
> >values / references, but...
> 
> 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?).

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... :-)

BdB.

Re: Ask for explanation -- possibly repeated

[Pierre Weis]

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