From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 692917FE44 for ; Tue, 5 Jul 2016 17:26:01 +0200 (CEST) IronPort-PHdr: 9a23:RoPg5RPbcJa9HqEjEWUl6mtUPXoX/o7sNwtQ0KIMzox0KPT8rarrMEGX3/hxlliBBdydsKMczbCK+PC8EUU7or+5+EgYd5JNUxJXwe43pCcHRPC/NEvgMfTxZDY7FskRHHVs/nW8LFQHUJ2mPw6anHS+4HYoFwnlMkItf6KuS9aU1Zj8h7z60qaQSj0AvCC6b7J2IUf+hiTqne5Sv7FfLL0swADCuHpCdrce72ppIVWOg0S0vZ/or9ZLuh5dsPM59sNGTb6yP+FhFeQZX3waNDUSz8TusVHmRAqL530TGkEXiQYAVwPM6RW/WpbqrgP7sPB80W+UJ5ulY6ozXGGA6KxmTA7uvxyGLTkluDX1jcd9iLNd5imsvRtj65PSYZ/QPuJ1eq7HeNQcWSxPRJACBGR6HoqgYt5XXKI6NuFCoty4/gNWoA== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=Jocelyn.Serot@univ-bpclermont.fr; spf=None smtp.mailfrom=Jocelyn.Serot@univ-bpclermont.fr; spf=None smtp.helo=postmaster@mta02.udamail.fr Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of Jocelyn.Serot@univ-bpclermont.fr) identity=pra; client-ip=193.49.117.21; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="Jocelyn.Serot@univ-bpclermont.fr"; x-sender="Jocelyn.Serot@univ-bpclermont.fr"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of Jocelyn.Serot@univ-bpclermont.fr) identity=mailfrom; client-ip=193.49.117.21; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="Jocelyn.Serot@univ-bpclermont.fr"; x-sender="Jocelyn.Serot@univ-bpclermont.fr"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mta02.udamail.fr) identity=helo; client-ip=193.49.117.21; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="Jocelyn.Serot@univ-bpclermont.fr"; x-sender="postmaster@mta02.udamail.fr"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0C3AQBu0HtXhxV1McFcgnCBFw18AbQ/hn0ihys8EAEBAQEBAQEBEQEBAQoLCQkhL4IygkhrOmuIRwEJjheNO58tAQEBI4gfCIo5gi8FmROGCYExiUWHE4VfiBmHbwIPJoInEQuBTmyIeQEBAQ X-IPAS-Result: A0C3AQBu0HtXhxV1McFcgnCBFw18AbQ/hn0ihys8EAEBAQEBAQEBEQEBAQoLCQkhL4IygkhrOmuIRwEJjheNO58tAQEBI4gfCIo5gi8FmROGCYExiUWHE4VfiBmHbwIPJoInEQuBTmyIeQEBAQ X-IronPort-AV: E=Sophos;i="5.26,580,1459807200"; d="scan'208,217";a="225685181" Received: from mta02.udamail.fr ([193.49.117.21]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 05 Jul 2016 17:26:00 +0200 Received: from mta02.udamail.fr (localhost.localdomain [127.0.0.1]) by mta02.udamail.fr (Postfix) with ESMTPS id 05B31160167 for ; Tue, 5 Jul 2016 17:26:00 +0200 (CEST) Received: from localhost (localhost.localdomain [127.0.0.1]) by mta02.udamail.fr (Postfix) with ESMTP id EC9E3160191 for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) X-Virus-Scanned: amavisd-new at mta02.udamail.fr Received: from mta02.udamail.fr ([127.0.0.1]) by localhost (mta02.udamail.fr [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id tJoFlmlVItzc for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) Received: from proxy02.udamail.fr (proxy02.udamail.fr [193.49.117.19]) by mta02.udamail.fr (Postfix) with ESMTPS id D2AC9160167 for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) Received: from localhost (localhost.localdomain [127.0.0.1]) by proxy02.udamail.fr (Postfix) with ESMTP id CFC911622F2 for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) Received: from proxy02.udamail.fr ([127.0.0.1]) by localhost (proxy02.udamail.fr [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id LFKqLDd2OtSu for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) Received: from localhost (localhost.localdomain [127.0.0.1]) by proxy02.udamail.fr (Postfix) with ESMTP id 1D7C31622F4 for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) X-Virus-Scanned: amavisd-new at proxy02.udamail.fr Received: from proxy02.udamail.fr ([127.0.0.1]) by localhost (proxy02.udamail.fr [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id Hf46tPBi5AGF for ; Tue, 5 Jul 2016 17:25:59 +0200 (CEST) Received: from [192.168.0.42] (lav63-2-88-164-92-250.fbx.proxad.net [88.164.92.250]) by proxy02.udamail.fr (Postfix) with ESMTPSA id 94DDB1622F2 for ; Tue, 5 Jul 2016 17:25:58 +0200 (CEST) From: =?iso-8859-1?Q?Jocelyn_S=E9rot?= Content-Type: multipart/alternative; boundary="Apple-Mail=_53BA7EBB-AE9A-40BE-955E-48A0D2E8C36F" Message-Id: <64440D5D-1FC8-4C53-9520-D9D3D21F8FE5@univ-bpclermont.fr> Date: Tue, 5 Jul 2016 17:25:56 +0200 To: OCaml Mailing List Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) X-Mailer: Apple Mail (2.1878.6) Subject: [Caml-list] Q: functors and "has a" inheritance --Apple-Mail=_53BA7EBB-AE9A-40BE-955E-48A0D2E8C36F Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=windows-1252 Dear all,=20 I=92m stuck with a problem related with the use of functors for implementin= g a library. The library concerns Labeled Transition Systems but i=92ll present it in a = simplified version using sets. Suppose i have a (very simplified !) Set module, which i will call Myset to= distinguish from that of the standard library : =97=97=97=97 myset.mli module type T =3D sig type elt=20 type t=20 val empty: t val add: elt -> t -> t val elems: t -> elt list val fold: (elt -> 'a -> 'a) -> t -> 'a -> 'a end module Make (E : Set.OrderedType) : T with type elt =3D E.t =97=97=97=20 =97=97=97=97 myset.ml module type T =3D sig =85 (* idem myset.mli *) end module Make (E : Set.OrderedType) =3D struct module Elt =3D E type elt =3D E.t type t =3D { elems: elt list; }=20=20 let empty =3D { elems =3D [] } let add q s =3D { elems =3D q :: s.elems } (* obviously wrong, but does = not matter here ! *) let elems s =3D s.elems let fold f s z =3D List.fold_left (fun z e -> f e z) z s.elems end =97=97=97=20 First, i add a functor for computing the product of two sets : =97=97=97=97 myset.mli (cont=92d) module Product (S1: T) (S2: T) : sig include T with type elt =3D S1.elt * S2.elt val product: S1.t -> S2.t -> t end =97=97=97=20 =97=97=97=97 myset.ml (cont=92d) module Product (S1: T) (S2: T) =3D struct module R =3D Make (struct type t =3D S1.elt * S2.elt let compare =3D compare end) include R let product s1 s2 =3D S1.fold (fun q1 z -> S2.fold (fun q2 z -> R.add (q1,q2) z) s2 z) s1 R.empty end =97=97=97=20 Here=92s a typical usage of the Myset module :=20 =97=97 ex1.ml=20 module IntSet =3D Myset.Make (struct type t =3D int let compare =3D compare= end) module StringSet =3D Myset.Make (struct type t =3D string let compare =3D c= ompare end) let s1 =3D IntSet.add 1 (IntSet.add 2 IntSet.empty) let s2 =3D StringSet.add "a" (StringSet.add "b" StringSet.empty) module IntStringSet =3D Myset.Product (IntSet) (StringSet) let s3 =3D IntStringSet.product s1 s2 =97=97 So far, so good.=20 Now suppose i want to =AB augment =BB the Myset module so that some kind of= attribute is attached to each set element. I could of course just modify t= he definition of type [t] and the related functions in the files [myset.ml]= and [myset.mli]. But suppose i want to reuse as much as possible the code = already written. My idea is define a new module - let=92s call it [myseta] = (=AB a =BB for attributes) - in which the type [t] will include a type [Mys= et.t] and the definitions of this module will make use, as much as possible= , of those defined in [Myset]. Here=92s a first proposal (excluding the Product functor for the moment) := =20 =97=97=97=97 myseta.mli module type Attr =3D sig type t end module type T =3D sig type elt=20 type attr type t=20 module S: Myset.T val empty: t val add: elt * attr -> t -> t val elems: t -> elt list val attrs: t -> (elt * attr) list val set_of: t -> S.t val fold: (elt * attr -> 'a -> 'a) -> t -> 'a -> 'a end module Make (E : Set.OrderedType) (A: Attr) : T with type elt =3D E.t and t= ype attr =3D A.t =97=97=97=20 =97=97=97=97 myseta.ml module type Attr =3D sig type t end module type T =3D sig (* idem myseta.mli *) end module Make (E : Set.OrderedType) (A : Attr) =3D struct module Elt =3D E type elt =3D E.t type attr =3D A.t module S =3D Myset.Make(E) type t =3D { elems: S.t; attrs: (elt * attr) list } let empty =3D { elems =3D S.empty; attrs =3D [] } let add (e,a) s =3D { elems =3D S.add e s.elems; attrs =3D (e,a) :: s.att= rs } let elems s =3D S.elems s.elems let attrs s =3D s.attrs let set_of s =3D s.elems let fold f s z =3D List.fold_left (fun z e -> f e z) z s.attrs end =97=97=97=20 In practice, of course the [Attr] signature will include other specificatio= ns. In a sense, this is a =AB has a =BB inheritance : whenever i build a [Myset= a] module, i actually build a [Myset] sub-module and this module is used to= implement all the set-related operations.=20 Again, so far, so good. The problem shows when i try to define the [Product] functor for the [Myset= a] module : It=92s signature is similar to that of the [Myset.Product] functor, with an= added sharing constraint for attributes (in fact, we could imagine a more = sophisticated scheme for merging attributes but cartesian product is here) : =97=97=97=97 myset.mli (cont=92d) module Product (S1: T) (S2: T) : sig include T with type elt =3D S1.elt * S2.elt and type attr =3D S1.attr * S2.attr val product: S1.t -> S2.t -> t end =97=97=97=20 Now, here=92s my current implementation =97=97=97=97 myset.ml (cont=92d) module Product (S1: T) (S2: T) =3D struct module R =3D Make (struct type t =3D S1.elt * S2.elt let compare =3D compare end) (struct type t =3D S1.attr * S2.attr let compare =3D compare end) include R module P =3D Myset.Product(S1.S)(S2.S) let product s1 s2 =3D { elems =3D P.product (S1.set_of s1) (S2.set_of s2); attrs =3D List.fold_left (fun acc (e1,a1) -> List.fold_left (fun acc (e2,a2) -> ((e1,e2),(a1,a2))::acc) acc= (S2.attrs s2)) [] (S1.attrs s1) } end =97=97=97=20 I use the [Myseta.Make] functor for building the resulting module [named R = here]. For defining the [product] function, i first use the [Myset.Product]= functor applied on the two related sub-modules [S1] and [S2] to build the = product module (named P here) and re-use the [product] function of this mod= ule to compute the [elems] component of the result. The other component is = computed directly.=20 The problem is that when i try to compile this i get this message :=20 File "myseta.ml", line 44, characters 14-53: Error: This expression has type P.t =3D Myset.Product(S1.S)(S2.S).t but an expression was expected of type S.t =3D R.S.t My intuition is that a sharing constraint is missing somewhere but i just c= annot figure out where to add it.=20 I tried to rewrite the signature of the [Myseta.Product] functor (in [myset= a.mli]) as : module Product (S1: T) (S2: T) : sig include T with type elt =3D S1.elt * S2.elt and type attr =3D S1.attr * S2.attr and type S.t =3D Myset.Product(S1.S)(S2.S).t (* added constra= int *) val product: S1.t -> S2.t -> t end but it did not change anything.. So my question is : is my diagnostic correct and, if yes, which constraint(= s) are missing and where; or, conversely, am i completely =AB misusing =BB = the functor mechanisms for implementing this kind of =AB reuse by inclusion= =BB ?=20 Any help will be grealy appreciated : i=92ve been reading and re-reading ab= out functors for the last two days but have the impression that at this ste= p, things get more and more opaque.. :-S In anycase, the source code is here : http://filez.univ-bpclermont.fr/lamue= mlqpm Jocelyn= --Apple-Mail=_53BA7EBB-AE9A-40BE-955E-48A0D2E8C36F Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=windows-1252 Dear all, 
I=92m stuck with a problem related with the use of functors fo= r implementing a library.
The library concerns Labeled Transition= Systems but i=92ll present it in a simplified version using sets.

Suppose i have a (very simplified !) Set module, which i w= ill call Myset to distinguish from that of the standard library :

=97= =97=97=97 myset.mli
module type T =3D sig
  type elt 
  type t = ;
 = val empty: t
  val add: elt -> t -> t
  val elems: t -> elt list=
  val fol= d: (elt -> 'a -> 'a) -> t -> 'a -> 'a
end

module Make (E : Set.OrderedType) := T with type elt =3D E.t
=97=97=97 

<= div>
=97=97=97= =97 myset.ml
module type T =3D sig =85 (* idem myset.ml= i *) end

module Make (E : Set.OrderedType) =3D struct=
&= nbsp; module Elt =3D E
  type elt =3D E.t
  type t =3D = { elems: elt list; }  
=   let empty =3D { elems =3D [] }
  let add q s =3D { elems =3D q :: s.elems }  (* obviously wrong= , but does not matter here ! *)
  let elems s =3D s.elems<= /font>
&n= bsp; let fold f s z =3D List.fold_left (fun z e -> f e z) z s.elems
end
=97=97=97 

First,= i add a functor for computing the product of two sets :

=97=97= =97=97 myset.mli (cont=92d)
module Product (S1: T) (S2: T) :=
sig
  include T with type elt =3D S1.elt * S2.elt
&nbs= p; val product: S1.t -> S2.t -> t
end
=
=97=97=97 = ;

=97=97=97=97 myset.ml (cont=92d)
modul= e Product
  (S1: T)
  (S2: T) =3D
struct
&nbs= p; module R =3D
    Make (struct type t =3D S1.elt * S2.elt let compare =3D = compare = end)
    include R
<= span style=3D"font-size: 11px;">    let product s1 s2 =3D<= /font>
&n= bsp;     S1.fold
<= span style=3D"font-size: 11px;">        (fun q1 z ->=
           S2.fold
<= div>    &= nbsp;        (fun q2 z -> R.add (q1,q2) z)
&nbs= p;            s2
      &n= bsp;      z)
=         s1
 =       R.empty
end
=97=97=97 
<= br>
Here=92s a typical usage of the Myset module : 

=97=97 ex1.ml 
module IntSet =3D Myset.Make (struc= t type t =3D int let compare =3D compare end)
module StringSet =3D Mys= et.Make (struct type t =3D string let compare =3D compare end)

let s1 =3D IntSet.add 1 (IntSet.add 2 IntSet.empty)
<= div>let s2 =3D Stri= ngSet.add "a" (StringSet.add "b" StringSet.empty)
<= br>
modul= e IntStringSet =3D Myset.Product (IntSet) (StringSet)

let s3= =3D IntStringSet.product s1 s2
=97=97
<= div>
So far, so good. 

Now supp= ose i want to =AB augment =BB the Myset module so that some kind = of attribute is attached to each set element. I could of course just modify= the definition of type [t] and the related functions in the files [myset.m= l] and [myset.mli]. But suppose i want to reuse as much as possible the cod= e already written. My idea is define a new module - let=92s call it [myseta= ] (=AB a =BB for attributes) - in which the type [t] will include= a type [Myset.t] and the definitions of this module will make use, as much= as possible, of those defined in [Myset].

Here=92= s a first proposal (excluding the Product functor for the moment) : 

=97=97=97=97 myseta.mli
module type Attr =3D sig t= ype t end

module type T =3D sig
  type elt 
  type attr
  type t 
  module S: Myset.T=
  val empty: t
  val add: elt * attr -> t -> t
  val elems: t -> elt list
  val attrs: t -> (el= t * attr) list
  val set_of: t -> S.t
  val fold: = (elt * attr -> 'a -> 'a) -> t -> 'a -> 'a
end

=
module Make (E : Set.OrderedType) (A: Attr) : T with type elt =3D E.t= and type attr =3D A.t
=97=97=97 
<= font face=3D"Courier">
=97= =97=97=97 myseta.ml
module type Attr =3D sig type t end

module type T =3D sig (* idem myseta.mli *) end

module Make (E : Set.OrderedType) (A : Attr) =3D struct
  mod= ule Elt =3D E
  type elt =3D E.t
  type attr =3D A.t
  module S =3D Myset.Make(E)
  type t =3D { elems: S.t; a= ttrs: (elt * attr) list }
  let empty =3D { elems =3D S.empty; at= trs =3D [] }
  let add (e,a) s =3D { elems =3D S.add e s.elems; a= ttrs =3D (e,a) :: s.attrs }
=   let elems s =3D S.elems s.elems
  let set_of s =3D s.elems
=   let fold f s z =3D List.fold_left (fun z e -> f e z) z s.attrs
end
=97=97=97 

In practice, of course the [Attr] signature will include other specificat= ions.
In a sense, this is a =AB has a =BB inheritance := whenever i build a [Myseta] module, i actually build a [Myset] sub-module = and this module is used to implement all the set-related operations. <= /div>
Again, so far, so good.
The problem shows when i try to= define the [Product] functor for the [Myseta] module :
It=92s si= gnature is similar to that of the [Myset.Product] functor, with an added sh= aring constraint for attributes (in fact, we could imagine a more sophistic= ated scheme for merging attributes but cartesian product is here) :

=97=97=97=97 myset.mli (cont=92d)
module Product (S1: T)= (S2: T) :
sig
  include T with type elt =3D S1.elt * S2.elt=
             and type attr =3D S1.= attr * S2.attr
  val product: S1.t -> S2.t -> t
=
end
=97=97=97 

Now, here=92s my c= urrent implementation

= =97=97=97=97 myset.ml (cont=92d)
module Product
  (S1: T)
  (S2: T) =3D
struc= t
  module R =3D
<= span style=3D"font-size: 11px;">    Make
=      = ; (struct type t =3D S1.elt * S2.elt let compare =3D compare end)
&nbs= p;     (struct type t =3D S1.attr * S2.attr let compare =3D compa= re end)
  include R
  module P =3D Myset.Product(S1.S)(S= 2.S)
    { elems =3D P.product (S1.set_of = s1) (S2.set_of s2);
          &nb= sp; attrs =3D<= /span>
        List.fold_left
      &= nbsp;   (fun acc (e1,a1) ->
         =    List.fold_left (fun acc (e2,a2) -> ((e1,e2),(a1,a2))::acc)&= nbsp;acc = ;(S2.attrs s2= ))
          []
        &= nbsp; (S1.attrs s1) }
end
=97=97=97 
=

I use the [Myseta.Make] functor for building the result= ing module [named R here]. For defining the [product] function, i first use= the [Myset.Product] functor applied on the two related sub-modules [S1] an= d [S2] to build the product module (named P here) and re-use the [product] = function of this module to compute the [elems] component of the result. The= other component is computed directly. 
The problem is that = when i try to compile this i get this message : 

<= div>
File "myseta.ml", line 44, characters 14-53:
E= rror: This expression has type P.t =3D Myset.Product(S1.S)(S2.S).t
       but an expression was expected of type = S.t =3D R.S.t

My intuition is tha= t a sharing constraint is missing somewhere but i just cannot figure out wh= ere to add it. 
I tried to rewrite the signature of the [Mys= eta.Product] functor (in [myseta.mli]) as :

<= font face=3D"Courier">module Product (S1: = T) (S2: T) :
sig
  include T with type elt =3D S1.elt * S2.e= lt
             and type attr =3D S= 1.attr * S2.attr
             and t= ype S.t =3D Myset.Product(S1.S)(S2.S).t  (* added constraint *)=
&= nbsp; val product: S1.t -> S2.t -> t
end

but it did not change anything..

=
So my question is : is my diagnostic correct and, if yes, which constr= aint(s) are missing and where; or, conversely, am i completely =AB mis= using =BB the functor mechanisms for implementing this kind of =AB&nbs= p;reuse by inclusion =BB ? 

Any help wil= l be grealy appreciated : i=92ve been reading and re-reading about functors= for the last two days but have the impression that at this step, things ge= t more and more opaque.. :-S

In anycase, the sourc= e code is here : http://filez.univ-bpclermont.fr/lamuemlqpm

J= ocelyn
= --Apple-Mail=_53BA7EBB-AE9A-40BE-955E-48A0D2E8C36F--