What are the primary theoretical difficulties with adding ML-style modules to Haskell?

Question

It is well known that Haskell-style typeclasses and ML-style modules offer different mechanisms for specifying interfaces. They are (possibly) equivalent in power, but in practice each has their own benefits and drawbacks.

Since I'm a bit of an inclusionist when it comes to language features, my question is this: What are the primary theoretical difficulties with adding ML-style modules to Haskell? I'm interested in answers along the following lines:

What existing type system features interact poorly with ML-style modules? (An example of poor interaction is GADT and functional dependencies, even though fundeps are technically equivalent to associated types!)
What things have to be given up on the compiler end in order to compile ML-style modules?
How do ML style modules interact with type inference?

Related reading:

Thanks for asking this. I *love* ML functors, it's the one thing I really miss in Haskell. — luqui, Apr 17 '11 at 17:57
Why would you want functional dependencies in a module system? As far as I can tell all functional dependencies do is control inference/implicit instantiation, which modules don't really try to do. — L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳, Mar 29 '13 at 16:44

Don Stewart · Accepted Answer · 2011-04-17T17:36:55.033

34

The main place to do the comparison is,

ML Modules and Haskell Type Classes: A Constructive Comparison. Stefan Wehr and Manuel M.T. Chakravarty. In Proceedings of The Sixth ASIAN Symposium on Programming Languages and Systems - APLAS 2008, Springer-Verlag, LNCS, 2008.
Modular Type Classes. Derek Dreyer, Robert Harper, and Manuel M. T. Chakravarty. In Proceedings of The 34th Annual ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages, ACM Press, 2007.
First class modules for Haskell, Mark Shields and Simon Peyton Jones. Submitted to the Ninth International Conference on Foundations of Object-Oriented Languages (FOOL 9), Portland, Oregon. 20 pages. Oct 2001.

I'm not actually aware of any theoretical issues -- at least, concrete proposals have been made (and implemented in prototypes) -- the Shields and PJ paper have a lot of the details. The implementation burden however, is non-trivial.

edited Apr 17 '11 at 17:36

answered Apr 17 '11 at 17:30

Don Stewart

137,316
36
365
468

3

In 2014, it's probably worth updating with a reference to [Backpack](http://plv.mpi-sws.org/backpack/) which is trying to bring something like an ML-style module system to GHC. – Lambdageek Feb 13 '14 at 01:47
1

[No HKT](http://archive.is/itQtX#selection-48019.0-48021.4) in core ML (∉MixML) for first 2 cited papers that implement typeclasses as modules. [_§7 Conclusion_](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/first_class_modules.pdf#page=12) of third cited paper concludes that _§3 Abstract Modules and Existentials_’s [existentials instead of](http://lambda-the-ultimate.org/node/5121#comment-84650) dependent sums breaks [encapsulation](http://lambda-the-ultimate.org/node/5121#comment-84486). [Discussion](http://lambda-the-ultimate.org/node/5121#comment-84248) with examples. – Shelby Moore III Feb 02 '18 at 01:58
2

@Lambdageek as of Nov 2017, the author of this question Edward Z. Yang has been [the active maintainer of Backpack](http://archive.is/https://ghc.haskell.org/trac/ghc/wiki/Backpack) since at least Aug 2017. For example, see his [blog post](http://blog.ezyang.com/2014/09/open-type-families-are-not-modular/) on anti-modularity of typeclasses when construed as an algebra. And his [blog post](http://blog.ezyang.com/2014/08/whats-a-module-system-good-for-anyway/#comment-7357) on why we need modules. Backpack is partially based on MixML, which afaik allows/has HKT in the core language. – Shelby Moore III Feb 02 '18 at 03:32

score 11 · Answer 2 · answered Apr 17 '11 at 20:30

11

I don't think there's any big theoretical problems. You'd have to make a decision about applicative functors or not. Applicative is probably more in the Haskell style. But I think any attempt at adding ML style modules to Haskell will be grotesque because the overlap between modules and classes; there will be two ways of doing many things.

answered Apr 17 '11 at 20:30

augustss

22,884
5
56
93

you don't have to add, you could replace – L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳ Mar 29 '13 at 16:42

score 8 · Answer 3 · answered Apr 18 '11 at 09:44

8

Simon PJ has argued that ML style modules have a poor power/cost ratio, that they are hard to implement. See SPJ's slides from POPL 2003 (towards the end). He also calls for a design which has a better power/cost ration but I'm unaware of any such proposal.

answered Apr 18 '11 at 09:44

svenningsson

4,009
1
24
32

The question asked for theoretical difficulties but the issues you cite are just the beliefs of one person. You might consider OCaml's delimited overloading to be a higher power/cost ratio use of modules. – J D May 03 '11 at 13:04
The slides are just SPJ's opinion, but it's a common one — also because the metatheory of ML modules is very tricky. And Derek Dreyer gives to it enough credit to react to it by presenting a different metatheory — the great "F-ing Modules" (http://www.mpi-sws.org/~dreyer/papers/f-ing/journal.pdf). After reading it, I couldn't reproduce their formal translation, but I could translate most (all?) use of SML modules to plain Fomega. – Blaisorblade Jul 02 '15 at 18:41

What are the primary theoretical difficulties with adding ML-style modules to Haskell?

3 Answers3