Re: [Caml-list] What is an applicative functor?

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

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.

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

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

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.

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

/Andreas