From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p3S56g8g022664 for ; Thu, 28 Apr 2011 07:06:42 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmACACf1uE3RVdY2kGdsb2JhbACldwgUAQEBAQkJDQcUBCGIcJ8DinyCJ4UeNIheAQEDBoVwBI5aiiQ7g2s X-IronPort-AV: E=Sophos;i="4.64,278,1301868000"; d="scan'208";a="93967037" Received: from mail-bw0-f54.google.com ([209.85.214.54]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 28 Apr 2011 07:06:36 +0200 Received: by bwz12 with SMTP id 12so4095433bwz.27 for ; Wed, 27 Apr 2011 22:06:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:date:message-id:subject:from:to:cc :content-type:content-transfer-encoding; bh=+J4mLd/MD0hVJIyRORKQmKAuB9rCZRzN0NDm9zASaeA=; b=jX/VJpbg67JQ5+9gcUnBD1JqxXLh2EE9xicucrdgW52Qa0xbXW2O0+GyIlBGWewStt cSNe/JGTLIN6nueTYLxTx+jn2ikHQK3C8RybTFTtel/DigETD4xLxazGqfXtHw4mAdUi 83bDZlKcTiIupx8nfCq1mlxRXFPMA4bOhIVys= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=WevsiNDYaQSZwy5mwBi3vhSdhbKg15mrNYqYsNsK17ZhGi3KGIj0UCsD8L3QgsLfZC QyD7I8CL0pRgjOXSCZbH1NPJ4QL7WoNM0PQRjSx1oAOutishBcwib0h8U9KfFbsebGc8 walHarszRmNRk5w1nDCQikP6ccKKVjL5DHdBc= MIME-Version: 1.0 Received: by 10.204.177.11 with SMTP id bg11mr1041830bkb.9.1303967196106; Wed, 27 Apr 2011 22:06:36 -0700 (PDT) Received: by 10.204.59.129 with HTTP; Wed, 27 Apr 2011 22:06:36 -0700 (PDT) Date: Thu, 28 Apr 2011 01:06:36 -0400 Message-ID: From: Lucas Dixon To: Andreas Rossberg Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p3S56g8g022664 X-Validation-by: lucas.dixon@gmail.com Subject: [Caml-list] functors and modules (was "What is an applicative functor?") > -------- Original Message -------- > Subject: Re: [Caml-list] What is an applicative functor? > Date: Tue, 19 Apr 2011 16:04:50 +0200 > From: Andreas Rossberg > To: Lucas Dixon > 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