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

[Lucas Dixon <lucas.dixon@gmail.com>]

> -------- Original Message --------
> Subject: Re: [Caml-list] What is an applicative functor?
> Date: Tue, 19 Apr 2011 16:04:50 +0200
> From: Andreas Rossberg <rossberg@mpi-sws.org>
> To: Lucas Dixon <ldixon@inf.ed.ac.uk>
> CC: caml-list@inria.fr
>
> On Apr 15, 2011, at 05.08 h, Lucas Dixon wrote:
>>
>> On 13/04/2011 03:23, Andreas Rossberg wrote:
>>>
>>> My experience with the early MLKit, which used this so-called "closed
>>> functor style", was that it is horrible. You need lots of functor
>>> parameters, lots of structure nesting and reexporting (the sizes of
>>> signatures can grow exponentially!),  and plenty of subtle sharing
>>> constraints.
>>
>> My feeling was that a little improvement on the syntax of signatures
>> and sharing would deal with these issues fairly easily.
>
> I think this is very much a semantic problem, but I still would be
> interested to hear what improvements you have in mind.

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

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;

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) = ...

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
Also when types are ground, if they are the same, then it shouldn't complain.
If you fix these things, signature sharing is pretty easy.

Once you do this, I think you also want to have a way to canonically
name structures in error messages. e.g. never say "S1.t is not equal
to S1.t: this was a common problem in PolyML until fairly recently."

>> In terms of growing exponentially: that sounds like a serious
>> problem; I would expect it to grow linearly on the number of
>> dependencies. Or did you mean to use exponentially informally; as in
>> gets too bug too quick?
>
> 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.

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.

>>> And when some new code you're writing does not type check,
>>> you sometimes spend considerable time figuring out whether that was a
>>> "real" error or you just forgot some type sharing somewhere.
>>
>> I ended up pushing improvements to the type-error printing which
>> helped a lot in PolyML. That combined with a finding a style that
>> works out not too hideously: I create a sub-structure, typically
>> called "Sharing" to hold just types that are relevant to a
>> particular module. I can then use sharing on this substructure to
>> share all types and save the others painful problem to remember to
>> share every type.
>
> Sure, such idioms can help, but I don't think they solve the general
> problem. The more dependencies you have (e.g. in some more top-level
> module) the more unstructured their relations become, and it is
> difficult to organize them in a useful way.

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. The main complication is name-space management. But,
like I suggest above, I think that a sensible signature language could
deal with that.

> In a way, parameterizing out all imports is a kind of manual closure
> conversion. You wouldn't want to be forced to doing that in the small,
> and I don't see why you should in the large. I feel that it also
> exposes too much of what should be considered implementation details.

I'm not sure I understand... I guess you mean you want concise syntax
that lets you say you depend on more than you really do? And then
maybe you work out the details of what you really depend on later.
Course-grained dependencies? I think functors kind of do that...
imagine a structure is an import, you specify the structures you use,
although maybe they contain much more than you really do use. You can
automatically analyse what you don't use of course...

>> yes, the concept of module for SML is really a functor and
>> dependencies are explicit.
>
> 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.

> In that spectrum, there is a place
> for both definite and indefinite references to other modules. You
> often want the the latter when you cross boundaries to other
> libraries. But the current functor mechanism is not an adequate means
> for expressing them, because it cannot be used at that level.

I still think it almost is... :-P

Maybe we need to sketch a bit more of a detailed picture of what we
want... maybe you have some examples, analogies to other languages we
can flesh out a bit more? I suspect that your idea of indefinite
references is something like (3) of my suggestions above... is that
the kind of thing you were thinking of?

... I'd like to imagine what the most beautiful way to write things
would be, and then infer the logic behind it :)

best,
lucas