[Caml-list] Re: functors and modules (was "What is an applicative functor?")

[Andreas Rossberg <rossberg@mpi-sws.org>]

On Apr 28, 2011, at 07:06, Lucas Dixon wrote:
> 1. I think you want to have a reasonable language to modify signatures
> - one that has all the obvious set-stuff, e.g. remove/add etc.
> (basically following the paper on an expressive language for
> signatures).

Agreed.

> 2. the resulting signature of a Functor should be able to refer to the
> input signatures. This would allow multiple inheritance in a natural
> way:   functor S2(S1) : S1 + sig val f : S1.t -> int end;

I don't understand. Is S1 a signature or structure here? In the former  
case, how is this different from:

   functor S2(X : S1) : sig include S1 val f : X.t -> int end

In the latter case, how is it different from saying (in OCaml 3.12):

   module S2(S1 : SIG) : sig include module type of S1 val f : S1.t ->  
int end

Granted, it would be much nicer with mixin composition. ;)

> 3. implicit signature dependencies:
> let S1 : SIG1 ... in
> functor F1(S2) = ...
> functor F2(S3) = ...
> end;
> =
> functor F1(S1 and S2) = ...
> functor F2(S1 and S3) = ...

Again, I don't understand what universes your Si are in, nor what you  
mean by "implicit signature dependency" or the "and" keyword. Assuming  
the Si are module identifiers, then isn't that just a nested functor?

   functor F (S1 : SIG1) =
   struct
     functor F1 (S2 : SIG2) = ...
     functor F2 (S3 : SIG3) = ...
   end

which in this case is isomorphic to the use of currying:

     functor F1 (S1 : SIG1) (S2 : SIG2) = ...
     functor F2 (S1 : SIG1) (S3 : SIG3) = ...

All this can be done in OCaml and in several SML implementations.

> 4. sharing of structures should allow be fine-grained modification,
> and should have sensible syntax (it's not a symmetric operation, so
> don't use a symmetric syntax: use <= instead of =):
> e.g..
> sharing (S1 except S1.t) <= S2

Sharing constraints a la SML are an anachronism. You simply want  
transparent (aka manifest) module specifications. E.g. in OCaml (or  
similarly in some SML dialects):

   sig
     ...
     module S1 = S2
     ...
   end

or

   S with module S1 = S2

Not sure what you intend with the "except", though.

> Also when types are ground, if they are the same, then it shouldn't  
> complain.

Yes, don't use structure sharing in SML. Ever. It was merely a  
backwards compatibility device for SML'90 code.

>> No, I meant it literally. One common idiom with functors is to re-
>> export all parameter structures in the result, in order to have a  
>> self-
>> contained result signature (and ease sharing later on). When you
>> continue doing that up the entire dependency graph, then signatures
>> can grow exponentially (in the depth of the dependency chain).
>
> While the number of paths to the sub-structures is exponential, the
> number of actual signatures is not. If the implementation does a
> reasonable job at only storing one copy when they are shared, then I
> don't think this is a problem.

The size of a signature includes nested ones. You still have to do all  
the signature matching on the full thing, which is structural and  
involves varying instantiations, so you cannot generally "cache" it.

> I think it is a problem if people don't specify their dependencies
> correctly, and the language should make it easy. Providing
> sub-structures to hold everything is not a good idea. So in some sense
> I agree: we need the right syntax for expressing what our
> dependencies.

The alternative to nesting the full structures is just flattening out  
their relevant type members. That makes the overall signature smaller,  
and is indeed the style used in most ML functor code today. But now it  
is just the number of direct type members that grows exponentially (at  
least in the worst case), which tends to be even more annoying to  
write down (although I could imagine you often can use some idiom of  
packaging them up in a single substructure that you can then include,  
but that still is kind of unpleasant).

> I think you want a reasonable language for specifying dependencies,
> and actually I think functors, with some tweaks to the signature
> language, would be pretty good. I can't see any better than saying
> what you need and what you provide, which is essentially all that a
> functor does.

Well, there is a difference between referring to a concrete module you  
need, just by name (a definite reference) or abstracting over the  
concrete module, by giving its complete interface specification (an  
indefinite reference). I'm just saying you want both, scoping and  
functorisation, depending on whether the modules are in the same  
"package" or not. Always having to give the full signature spec is  
just way too inconvenient.

>> I guess the underlying question is what constitutes a module? I think
>> you have to distinguish modules (as individual abstractions) from
>> components/libraries/packages/whatever you like to call them. The
>> latter can consist of many modules.
>
> I don't see why they need to be separate... I think structures can be
> individual modules as well as packages.

A package is typically too large to be written in one source file. So  
you want to split it into several modules without having to functorise  
everything by everything. OTOH, you actually want to functorise the  
whole thing in the end, and that is something you cannot do with the  
language as is. (OCaml provides some extra-linguistic means to do the  
former, via the compiler's -pack option, but nothing for the latter.)

Cheers,
/Andreas