[Caml-list] Forward references

[Caml-list] Forward references

[brogoff]

Hi,
    I was browsing the mailing list archives when I reread the article 

	http://caml.inria.fr/archives/199902/msg00020.html

where it was mentioned that there was once some kind of experimental forward 
declaration feature in an earlier Caml. This was used to get full polymorphic 
recursion in the language (it served as a mandatory type constraint) and it 
was also discussed as a way to get some cross module recursion without the 
ugly "ref to function" hack mentioned in the manual. 

    I'm curious as to whether types could also be forward declared, or deferred, 
as well, and if this forward ref machinery could deal with the problem of 
instantiating a functor which is in a recursive relationship with a type, as in  
the following faux-Caml

forward type composite = { data : string ; children : CompositeSet.t }
and cmp x y = Pervasives.compare x.data y.data  
and module CompositeSet = Set.Make(module type t = composite let compare = cmp end)

    This is a lighter approach than the one involving MoscowML recursive 
modules, since there is no extra module wrapper, but can probably be transformed 
into the mosml style mechanically. Is there some showstopper that prevents this 
(admittedly half baked) approach from being feasible? 

    I'd really like to see some solution to the above mentioned problems in 
OCaml sooner rather than later.  

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

Re: [Caml-list] Forward references

[brogoff]

Hi Tom,
    You're certainy right, but let me explain my half baked thoughts. 

    A little more than a year ago Claudio Russo said that his recursive 
module approach in Moscow ML could solve the problem I posed (I'm certainly not 
the first to pose it!) of having a recursion between a type def and a 
functor instantiation. It was syntactically rather heavy (you had to wrap the 
type and functor instantiation in separate modules and tie the knot using 
the recursive modules. That was great, and I thought this problem would soon be 
solved. A related problem which could probably not be solved the same way 
without giving up separate compilation (I think?) is the simple "functions 
which are recursive across module boundaries" issue which is mentioned in the 
manual. The old message I cited mentioned that this forward mechanism could 
be used to solve this problem. I was imagining that a syntactic transformation 
could map this use of forward to the Moscow ML style recursive modules. 

I remember reading in your paper that you found the Moscow ML approach 
unsatisfactory for various reasons, but I don't remember what they were. 
Separate compilation is not the issue since it isn't there for the functor 
instantiation problem, and for the other problem I assume forwarding is OK. 

I also realize that the mixin approach you are working on is more general, 
and adds incremental programmning capabilities to the module system. Your 
messages to the list indicate that there are still quite a few open problems 
to solve, and I was hoping for quick relief from immediate problems, focused 
solely on the cross module recursive functions and the use of existing, non 
polymorphic libraries with functorial interfaces. OCaml + Mixins is probably 
quite a few years away.

-- Brian

> Hi Brian, 
> 
> in your example, the current structure of types would not allow
> to express how Set.Make uses its arguments.
> Nothing ensures you that the body of Set.Make does not make use 
> of cmp.
> 
> It is in fact exactly the same problem for the right-hand sizes 
> of let rec, as in
> 
> let rec f x y = compare (x, y) (y, x) 
> and     u = A.g f 1 2 
> 
> One could imagine a type system telling you whether A.g inspects 
> the value of its arguments or not (in fact Xavier and I did imagine 
> such a type system, article is on our web pages).
> But without this, A.g could apply f, which would make the computation 
> go wrong.
> 
> This said, even in the context of a type system where those dependency
> problems are solved, it is not trivial that types do not cause new
> problems.  We don't think so but are not sure. I tried to formalize
> this idea and implemented an early prototype type-checker for caml
> with mixin modules, which used this idea. My conclusion was that the
> theory was in to early stage for a prototype to be really significant.
> 
>  >     I'm curious as to whether types could also be forward declared, or deferred, 
>  > as well, and if this forward ref machinery could deal with the problem of 
>  > instantiating a functor which is in a recursive relationship with a type, as in  
>  > the following faux-Caml
>  > 
>  > forward type composite = { data : string ; children : CompositeSet.t }
>  > and cmp x y = Pervasives.compare x.data y.data  
>  > and module CompositeSet = Set.Make(struct type t = composite let compare = cmp end)
>  > 
>  >     This is a lighter approach than the one involving MoscowML recursive 
>  > modules, since there is no extra module wrapper, but can probably be transformed 
>  > into the mosml style mechanically. Is there some showstopper that prevents this 
>  > (admittedly half baked) approach from being feasible? 
>  > 
>  >     I'd really like to see some solution to the above mentioned problems in 
>  > OCaml sooner rather than later.  
>  > 
>  > -- 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
>  > 
> -------------------
> 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
> 

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

[Caml-list] Forward references

[Tom Hirschowitz]

Hi Brian, 

in your example, the current structure of types would not allow
to express how Set.Make uses its arguments.
Nothing ensures you that the body of Set.Make does not make use 
of cmp.

It is in fact exactly the same problem for the right-hand sizes 
of let rec, as in

let rec f x y = compare (x, y) (y, x) 
and     u = A.g f 1 2 

One could imagine a type system telling you whether A.g inspects 
the value of its arguments or not (in fact Xavier and I did imagine 
such a type system, article is on our web pages).
But without this, A.g could apply f, which would make the computation 
go wrong.

This said, even in the context of a type system where those dependency
problems are solved, it is not trivial that types do not cause new
problems.  We don't think so but are not sure. I tried to formalize
this idea and implemented an early prototype type-checker for caml
with mixin modules, which used this idea. My conclusion was that the
theory was in to early stage for a prototype to be really significant.

 >     I'm curious as to whether types could also be forward declared, or deferred, 
 > as well, and if this forward ref machinery could deal with the problem of 
 > instantiating a functor which is in a recursive relationship with a type, as in  
 > the following faux-Caml
 > 
 > forward type composite = { data : string ; children : CompositeSet.t }
 > and cmp x y = Pervasives.compare x.data y.data  
 > and module CompositeSet = Set.Make(struct type t = composite let compare = cmp end)
 > 
 >     This is a lighter approach than the one involving MoscowML recursive 
 > modules, since there is no extra module wrapper, but can probably be transformed 
 > into the mosml style mechanically. Is there some showstopper that prevents this 
 > (admittedly half baked) approach from being feasible? 
 > 
 >     I'd really like to see some solution to the above mentioned problems in 
 > OCaml sooner rather than later.  
 > 
 > -- 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
 > 
-------------------
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