Some questions about the module system...

Some questions about the module system...

[Francisco J. Valverde]

Hello mailing list,

here are some questions I would like to pose the system implementors
concerning the module system in O'Caml. The mail is quite lengthy, and I
apologise in case somebody else has asked the same... (I have been unable to
look up the question in the mailing archives).

1) is there any reason (unclear semantics, scope-holing, etc.) why the O'Caml
module system won't allow an "include <signature>" feature? I keep bumping
into it when I try to write module hyerarchies (or adapt ML code from texts ;) ).
What I am asking about is a nice "feature" for doing:

module type ELEMENT =
  sig
     type t
     val format : t -> unit
  end;;

module type ORDER =
sig
   include ELEMENT
   val leq : t -> t -> bool
end;;

module type DOMAIN =
sig
   include ORDER
   val bottom: t
end;;

(...and so on and so forth), instead of writing "all that code again".

b) My second question concerns module coercion by means of module signatures.
Sharing constraints between module types is really necessary for code
abstraction, but I found "value aliasing" really useful as well (I don't
know the exact term for the feature so I will describe it).

Suppose you have this priority queue functor requesting an ORDER on values of
the type shown above:

module MakePQueue = (struct ... end: (O: ORDER) -> PQUEUE);;

and a module implementing NODEs in a graph with data about the distance from
the node to a "root" and an accumulated value describing another distance
measure:

module NODE =
sig
  type node ={ depth: int; dist: int; ...}
  ..
end;;

Now, I would like to implement 2 different searching strategies namely
DepthFirst and heuristic search ( "A" strategy someone would say), for
which I need to consider two different orders (take my word for it):

value less_depth: node -> node -> bool	(* depthFirst order *)
value less_dist: node -> node -> bool	(* A* search order *)

How could I view NODE as these two different orders so that MakePQueue doesn't
complain? Answer: *alias* any of the orders to the order defined in ORDER:

(* this won't work in O'Caml 1.01 *)
module DepthFirstPQueue =
  MakePQueue (Node: NODE with t = node (* and val leq = less_depth *));;

module BestFirstPQueue =
  MakePQueue (Node: NODE with t = node (* and val leq = less_dist *));;

Unless I got it wrong all you can do for now is write TWO module signatures, say
NODE1 and NODE2, in which you define the required order with the adequate name,
that is to say "leq". *You* have to keep consistency between the rest of the primitives
on your own, and this is really... burdensome!

My feeling is that implementing this amounts to *rewriting* "leq" as
"less_dist", but this is merely a sintactic procedure and I am not sure
how would the semantics be affected: are modules just "environments" as
in ML, or do we have a more comvoluted semantica which rules out  this
behaviour?

I would like any comments about this, or other (more imaginative) ways
around these *burdensome* ways of writing code...

Francisco J. Valverde-Albacete
'Area de Tecnolog'ia Electr'onica
Dept. de Ingenier'ia (Area de Teconolog'ia Electr'onica)
Univ. Carlos III de Madrid
ESPAÑA (Spain)

Re: Some questions about the module system...

[Wolfgang Lux]

Hello

[This is the correct version of the mail I posted 5 minutes ago. It
just had hit the send key to early on that post :-)]

> 
> Hello mailing list,
> 
> here are some questions I would like to pose the system implementors
> concerning the module system in O'Caml. The mail is quite lengthy, and I
> apologise in case somebody else has asked the same... (I have been unable t=
> o
> look up the question in the mailing archives).
> 
> 1) is there any reason (unclear semantics, scope-holing, etc.) why the O'Ca=
> ml
> module system won't allow an "include <signature>" feature? I keep bumping
> into it when I try to write module hyerarchies (or adapt ML code from texts=
>  ;) ).
> [Sample deleted]

Interesting question. In Caml Special Light 1.15 this feature was
working. So why isn't it included in O'Caml?

> 
> b) My second question concerns module coercion by means of module signature=
> s.
> Sharing constraints between module types is really necessary for code
> abstraction, but I found "value aliasing" really useful as well (I don't
> know the exact term for the feature so I will describe it).
> 
> Suppose you have this priority queue functor requesting an ORDER on values =
> of
> the type shown above:
> 
> module MakePQueue =3D (struct ... end: (O: ORDER) -> PQUEUE);;
> 
> and a module implementing NODEs in a graph with data about the distance fro=
> m
> the node to a "root" and an accumulated value describing another distance
> measure:
> 
> module NODE =3D
> sig
>   type node =3D{ depth: int; dist: int; ...}
>   ..
> end;;
> 
> Now, I would like to implement 2 different searching strategies namely
> DepthFirst and heuristic search ( "A" strategy someone would say), for
> which I need to consider two different orders (take my word for it):
> 
> value less_depth: node -> node -> bool=09(* depthFirst order *)
> value less_dist: node -> node -> bool=09(* A* search order *)
> 
> How could I view NODE as these two different orders so that MakePQueue does=
> n't
> complain? Answer: *alias* any of the orders to the order defined in ORDER:
> 
> (* this won't work in O'Caml 1.01 *)
> module DepthFirstPQueue =3D
>   MakePQueue (Node: NODE with t =3D node (* and val leq =3D less_depth *));=
> ;
> 
> module BestFirstPQueue =3D
>   MakePQueue (Node: NODE with t =3D node (* and val leq =3D less_dist *));;
> 
> Unless I got it wrong all you can do for now is write TWO module signatures=
> , say
> NODE1 and NODE2, in which you define the required order with the adequate n=
> ame,
> that is to say "leq". *You* have to keep consistency between the rest of th=
> e primitives
> on your own, and this is really... burdensome!
> 
You don't need to write any new signature for this case, but you
simply can use a functor for achieving this name aliasing by rewriting
your code as follows:

module MakePQueue(O: ORDER)(Leq: sig val leq : O.t -> O.t -> bool end): PQUEUE ->
  struct
    ...
  end
  
and then you can apply this functor as follows:

module DepthFirstPQueue =
  MakePQueue(Node : NODE with t = node)(struct let leq = Node.less_depth end)

module BestFirstPQueue =
  MakePQueue(Node : NODE with t = node)(struct let leq = Node.less_dist end)

You might even write down a functor to convert your NODE module
together with its ordering function into an ORDER module:

module OrderOfNode(Node : NODE)(Leq : sig value leq : O.t -> O.t -> bool end) : ORDER =
  struct
    type t = Node.node
    let format = Node.format
    let leq = Leq.leq
  end

and then use your original definition of MakePQueue as follows:

module DepthFirstPQueue =
  MakePQueue(OrderOfNode(Node)(struct let leq = Node.less_depth end))
module BestFirstPQueue =
  MakePQueue(OrderOfNode(Node)(struct let leq = Node.less_dist end))


Regards
Wolfgang

----
Wolfgang Lux
WZH Heidelberg, IBM Germany             Internet: lux@heidelbg.ibm.com
+49-6221-59-4546                        VNET:     LUX at HEIDELBG
+49-6221-59-3500 (fax)	                EARN:     LUX at DHDIBMIP

Re: Some questions about the module system...

[Xavier Leroy]

> 1) is there any reason (unclear semantics, scope-holing, etc.) why the O'Caml
> module system won't allow an "include <signature>" feature?

Actually, "include <signature>" is available in O'Caml as it was in
Caml Special Light. It was a last-minute addition that never got
documented, but since it causes no harm and seems to be useful, I'll
keep it and document it for the next release.

> b) My second question concerns module coercion by means of module signatures.
> Sharing constraints between module types is really necessary for code
> abstraction, but I found "value aliasing" really useful as well (I don't
> know the exact term for the feature so I will describe it).

The only coercions that can be performed with a signature constraint
(str : sig) are restrictions, i.e. hide components or make their type
info less precise. I doubt renaming of structure components has its
place there. But it's easy (and just as efficient) to do the coercion
yourself, e.g.:

  module Node = struct
    type node 
    let less_depth = ...
    let less_dist = ...
    ...
  end

  module DepthFirstPQueue =
    MakePQueue (struct type t = Node.node let leq = Node.less_depth end)

  module BestFirstPQueue =
    MakePQueue (struct type t = Node.node let leq = Node.less_dist end)

Regards,

- Xavier Leroy

Re: Some questions about the module system...

[Wolfgang Lux]

> [stuff deleted]
> > module MakePQueue(O: ORDER)(Leq: sig val leq : O.t -> O.t -> bool end): PQUEUE ->
> >   struct
> >     ...
> >   end
>    
> > and then you can apply this functor as follows:
> > 
> > module DepthFirstPQueue =
> >   MakePQueue(Node : NODE with t = node)(struct let leq = Node.less_depth end)
> > 
> > module BestFirstPQueue =
> >   MakePQueue(Node : NODE with t = node)(struct let leq = Node.less_dist end)
> 
> Thank you, I was so brain-fuddled with trying to work my way around the *other*
> side of the problem that I couldn't think properly. Yours is a handy solution.
> 
> However, don't you think such ad hoc procedures beat the whole purpose of
> neatness of code, separability, etc.? I remember having to pass around a 
> reference to a parsing function to do something pretty wild to the original CAML
> parser-generating construct, and this thing with the modules smacks strongly of it!
>  

Youe are right. The above solution was really an ad-hoc one. It suits
the problem as you described it, but it may well get ugly for more
complex problems. Generally I would prefer a solution along the lines
of the other solution I presented.

> > You might even write down a functor to convert your NODE module
> > together with its ordering function into an ORDER module:
> > 
> > module OrderOfNode(Node : NODE)(Leq : sig value leq : O.t -> O.t -> bool end) : ORDER =
> >   struct
> >     type t = Node.node
> >     let format = Node.format
> >     let leq = Leq.leq
> >   end
> 
> Yes, I have thought about doing this thing, for other purposes, but for this particular
> one it would mean actually discarding the rest of the ADT of the nodes, and who
> knows what you may need in a future implementation of the NODEs.
> 
> However, maybe it wasn't a bad idea after all, if you recommend it as well.

You could take this solution even further and make all information
including the above functor OrderOfNode local to your Node module, e.g.:

module type NODE =
  sig
    type node
    module type LEQ
    module DepthFirstLeq : LEQ
    module BestFirstLeq : LEQ
    module AsOrder(Leq : LEQ): ORDER
    ...
  end

module Node =
  struct
    type node = ...
    ...
    module type LEQ = sig value leq : node -> node -> bool end
    module DepthFirstLeq = struct let leq = less_depth end
    module BestFirstLeq = struct let leq = less_dist end
    module OrderOfNode(Leq : LEQ): ORDER =
      struct
        type t = node
        let format = format
	and leq = Leq.leq
      end
    ...
  end

> 
> Nevertheless, I would still like to know if someone had answers for the original
> questions,
> 
> b) what are the reasons not to allow module values aliasing to view modules under
> different signatures? Is it envisioned for the future at all?
> 

As I am no one of the designers of OCaml I can't answer the
question. But actually I must admit that I do not miss that
feature. Actually I can even live without type sharings at all. T
think type sharings are an ad-hoc feature which had to be introduced
into the SML module systems because of its limitations. But with the
presence of higher order functors in OCaml together with their
applicative semantics I have yet not found a case where it had to use
type or module. IMHO using functors instead of sharing constraints
also makes the dependencies between modules clearer.

Regards
Wolfgang

----
Wolfgang Lux
WZH Heidelberg, IBM Germany             Internet: lux@heidelbg.ibm.com
+49-6221-59-4546                        VNET:     LUX at HEIDELBG
+49-6221-59-3500 (fax)	                EARN:     LUX at DHDIBMIP