[Caml-list] Recursive modules and polymorphic recursion

[Caml-list] Recursive modules and polymorphic recursion

[brogoff]

Hi,
    I was playing with the recursive modules in the CVS snapshot and much to 
my chagrin the very first pr function of the very first pr example in Okasaki 
causes the system to barf, where barf means "Cannot safely evaluate the 
definition of the recursively-defined module RAListImpl". Is this a temporary 
limitation of the CVS version or a permanent limitation of the feature? 
I've appended the code to this email.

    You can write these pr examples from Okasaki using the nested polymorphism 
on record fields (or polymorphic methods if you like objects) so I guess it's 
time again to raise the question of when we will get a direct way to write these 
functions, say with explicit type annotations on the functions. The recursive 
module approach would be acceptable, but even if it worked here it has the 
(minor) disadvantage of requiring you to create a module where you have to 
expose functions you'd prefer to have hidden, which you can then export with 
your final signature. 

-- Brian

module rec RAListImpl :
    sig
      type 'a ra_list

      val empty   : 'a ra_list
      val is_empty : 'a ra_list -> bool
      val length  : 'a ra_list -> int
(*
      val cons    : 'a -> 'a ra_list -> 'a ra_list
      val uncons    : 'a ra_list -> 'a * 'a ra_list
      val head    : 'a ra_list -> 'a
      val tail    : 'a ra_list -> 'a ra_list
      val lookup  : int -> 'a ra_list -> 'a

      val fupdate  : ('a -> 'a) -> int -> 'a -> 'a ra_list -> 'a ra_list
      val update  : int -> 'a -> 'a ra_list -> 'a ra_list
*)
    end =
  struct
    type 'a ra_list = Nil
    | Zero of ('a * 'a) ra_list
    | One of 'a * ('a * 'a) ra_list

    let empty = Nil
    let is_empty = function Nil -> true | _ -> false

    let length = function
        Nil -> 0
      | Zero ra -> 2 * (RAListImpl.length ra)
      | One (_,ra) -> 1 + 2 * (RAListImpl.length ra)

(*
    let cons x = function
        Nil -> One (x, Nil)
      | Zero ps -> One (x, ps)
      | One (y,b) -> Zero (RAListImpl.cons (x, y) b)

    let uncons = function
        Nil -> raise Not_found
      | One (x,Nil) -> (x,Nil)
      | One (x,ps) -> (x, Zero ps)
      | Zero ps ->
          let ((x,y),ps') = RAListImpl.uncons ps in
          (x, One (y, ps'))

    let lookup i l =
      match i,l with
        (i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> x
      | (i, One (x, ps)) -> RAListImpl.lookup (pred i) (Zero ps)
      | (i, Zero ps) ->
          let (x, y) = RAListImpl.lookup (i / 2) ps
          in if i mod 2 = 0 then x else y

    let head xs = let (x, _) = RAListImpl.uncons xs in x
    let tail xs = let (_, xs') = RAListImpl.uncons xs in xs'

    let fupdate f i l =
      match i,l with
        (i, Nil) -> raise Not_found
      | (0, One (x, ps)) -> One (f x, ps)
      | (i, One (x, ps)) ->
          cons x (RAListImpl.fupdate f (i-1) (Zero ps))
      | (i, Zero ps) ->
          let f' (x, y) = if i mod 2 = 0 then (f x, y) else (x, f y) in
          Zero (RAListImpl.fupdate f' (i / 2) ps)

    let update  i y xs = RAListImpl.fupdate (fun x -> y) i xs
*)
  end

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Recursive modules and polymorphic recursion

[Xavier Leroy]

>     I was playing with the recursive modules in the CVS snapshot and
> much to my chagrin the very first pr function of the very first pr
> example in Okasaki causes the system to barf, where barf means
> "Cannot safely evaluate the definition of the recursively-defined
> module RAListImpl". Is this a temporary limitation of the CVS
> version or a permanent limitation of the feature?  I've appended the
> code to this email.

As the design document explains
(http://pauillac.inria.fr/~xleroy/publi/recursive-modules-note.pdf),
the current implementation of recursive modules is such that a definition
        module rec A : SIGA = StructA
is accepted only if all value components of SIGA are functions.  This
isn't the case in your example because of the "empty" value component.
This restriction comes from the way ill-founded recursions are
detected at run-time.

Yes, it's an unfortunate restriction, and eventually it will go away
once I figure out a suitable static analysis for well-foundedness of
recursive definitions.  But this may take a while.

The decision to integrate recursive modules in 3.07 was taken on the
grounds that imperfect recursive modules are still better than no
recursive modules at all.  Be patient: perfection takes time.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Recursive modules and polymorphic recursion

[brogoff]

On Thu, 26 Jun 2003, Xavier Leroy wrote:
> As the design document explains
> (http://pauillac.inria.fr/~xleroy/publi/recursive-modules-note.pdf),
> the current implementation of recursive modules is such that a definition
>         module rec A : SIGA = StructA
> is accepted only if all value components of SIGA are functions. 

I guess I was thrown by the fact that the similar

module rec ASet : Set.S with type elt = A.t = Set.Make(A) 
and A : (* ... etc ...*) 

is accepted, and by the fact that I rarely comprehend this kind of stuff by 
reading alone, but instead have to read/hack/ask/read/... 

> The decision to integrate recursive modules in 3.07 was taken on the
> grounds that imperfect recursive modules are still better than no
> recursive modules at all.  Be patient: perfection takes time.

Of course. I'm glad that decision was taken, and I think what's there is 
pretty good, even if imperfect. I expect that perfection would take forever, 
which will certainly exhaust anyone's patience. 

-- Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners