Re: [Caml-list] Instruction selection in the OCaml compiler:Modulesor classes?

["Andreas Rossberg" <AndreasRossberg@web.de>]

"skaller" <skaller@users.sourceforge.net>:
>
> It seems like a module functor allows both anonymous
> signatures (structural) and also anonymous argument
> modules (structural), yet you cannot have
> anonymous functor applications: you have to bind the application to
> a module name.

Not at all. For instance, given

  module Id(X : sig type t end) = X
  module A = struct type t = int end

it is perfectly legal to write:

  module A' = Id(Id(Id(A)))

Obviosuly, the inner applications of Id are all "anonymous".

Likewise, you can say

  (3 : Id(Id(A)).t)

Also purely anonymous applications.

> C++ template applications can be anonymous, and that gives them
> a major edge over Ocaml modules.

This is not really an issue of anonymity, but rather a matter of implicit 
vs. explicit sharing. In C++, all "equivalent" applications of the same 
template are - at least semantically - implicitly shared (where "equivalent" 
is rather ill-defined when it comes to non-type template arguments). In 
OCaml, all type instantiations are shared (sharing is based on a purely 
syntactic notion of module expression equivalence that is rather weak). But 
for the value part, which might involve state, you have to be explicit about 
sharing, and thus explicit about separate instantiation. After all, it makes 
a crucial semantic difference if you copy the state, and multiple 
instantiations may be desired. C++ cannot express this directly.

(As an aside, module theorists argue that it is incoherent to share types 
across instantiations of functors that are stateful. In such cases you 
rather want so-called generative functors, which OCaml does not have. SML 
has the latter, but in turn does not offer OCaml-style "applicative" 
functors, which is just as bad. More recent type theories for modules 
incorporate both.)

> Similarly, when you're lucky
> enough to be able to use non-modular functor (a function with
> polymorphic type) it is much more convenient. For example Hashtbl
> provides both alternatives, whereas Set and Map do not (a fact
> many people complain about).

Yes, the fact that there is an overlap between functors and core-language 
polymorphism is a bit unfortunate. It is one of the advantages of 
Haskell-style type classes over ML modules that they blend seamlessly with 
polymorphism. Of course, they have other disadvantages instead, implicit 
sharing being one of them.

> *** more precisely, we probably don't want to eliminate the name
> most of the time, but we would like to be able to use a
> 'Set of int' in several modules without having to *export*
> the type in another module so it can be reused.

You can more or less do that already, as long as you introduce a suitable 
global module to host the integer type:

  module Int = struct type t = int let compare = compare end

  signature A = sig ... val foo : u -> Set.Make(Int).t -> unit ... end
  signature B = sig ... val bar : v -> w -> Set.Make(Int).t ... end

Admittedly, the type looks a bit ugly, and it would be even nicer if Int was 
in the stdlib. But that are merely a questions of library design.

Due to the "weak syntactic notion of module equivalence" I was mentioning 
earlier you have to make sure that all these type expressions really refer 
to the same Int module. This is a limitation of OCaml's module type system, 
and may be what sometimes gives the impression of "nominal" typing. The 
limitation has long been solved in theory, but a full-fledged theory has not 
made it into any concrete ML implementation yet. Moscow ML probably comes 
closest.

> This is particularly annoying when it is intractable: for
> example I have variant terms some of which contain sets
> of terms .. the recursion is easy to represent with
> lists but you can't do it with modular data structures.
> The way I do it is make sets of integers instead and
> keep a term table indexed by the integers. But this isn't
> really safe. There's probably a better way but the fact
> remains if I want the type safety I have to use lists
> or some other non-modular data structure: the modules
> actually get in the way of type safety instead of
> enhancing it. I guess the 'recursive modules' stuff will
> help fix this?

Yes, with recursive modules you should be able to express this. Something 
like:

  module rec Term : Set.OrderedType = struct type t = A | B of TermSet.t let 
compare = compare end
  and TermSet : (Set.S with type elt = Term.t) = Set.Make(Term)

or even:

  module rec Term : Set.OrderedType = struct type t = A | B of 
Set.Make(Term).t let compare = compare end

- Andreas