Mixin' up the ML module system

ABSTRACT

ML modules provide hierarchical namespace management, as well as fine-grained control over the propagation of type information, but they do not allow modules to be broken up into mutually recursive, separately compilable components. Mixin modules facilitate recursive linking of separately compiled components, but they are not hierarchically composable and typically do not support type abstraction. We synthesize the complementary advantages of these two mechanisms in a novel module system design we call MixML.

A MixML module is like an ML structure in which some of the components are specified but not defined. In other words, it unifies the ML structure and signature languages into one. MixML seamlessly integrates hierarchical composition, translucent MLstyle data abstraction, and mixin-style recursive linking. Moreover, the design of MixML is clean and minimalist; it emphasizes how all the salient, semantically interesting features of the ML module system (as well as several proposed extensions to it) can be understood simply as stylized uses of a small set of orthogonal underlying constructs, with mixin composition playing a central role.

REFERENCES

• 1: D. Ancona, S. Fagorzi, E. Moggi, and E. Zucca. Mixin modules and computational effects. In ICALP '03.
• 2: Davide Ancona , Elena Zucca, A theory of mixin modules: basic and derived operators, Mathematical Structures in Computer Science, v.8 n.4, p.401-446, August 1998 [doi>10.1017/S0960129598002576]
• 3: Davide Ancona , Elena Zucca, A calculus of module systems, Journal of Functional Programming, v.12 n.2, p.91-132, March 2002 [doi>10.1017/S0956796801004257]
• 4: Gilad Bracha , William Cook, Mixin-based inheritance, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.303-311, September 1990, Ottawa, Canada
• 5: Gilad Bracha and Gary Lindstrom. Modularity meets inheritance. In ICCL '92.
• 6: Karl Crary , Robert Harper , Sidd Puri, What is a recursive module?, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.50-63, May 01-04, 1999, Atlanta, Georgia, United States
• 7: Derek Dreyer, A type system for recursive modules, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 8: Derek Dreyer, A type system for well-founded recursion, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-305, January 14-16, 2004, Venice, Italy
• 9: DEREK DREYER, Recursive type generativity, Journal of Functional Programming, v.17 n.4-5, p.433-471, July 2007 [doi>10.1017/S0956796807006429]
• 10: Derek Dreyer , Karl Crary , Robert Harper, A type system for higher-order modules, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.236-249, January 15-17, 2003, New Orleans, Louisiana, USA
• 11: Derek Dreyer and Andreas Rossberg. MixML (project website). http://www.mpi-sws.mpg.de/~rossberg/mixml/.
• 12: Dominic Duggan, Type-Safe linking with recursive DLLs and shared libraries, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.711-804, November 2002 [doi>10.1145/586088.586093]
• 13: Dominic Duggan and Constantinos Sourelis. Mixin modules. In ICFP '96.
• 14: Matthew Flatt , Matthias Felleisen, Units: cool modules for HOT languages, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.236-248, June 17-19, 1998, Montreal, Quebec, Canada
• 15: Robert Harper , Mark Lillibridge, A type-theoretic approach to higher-order modules with sharing, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.123-137, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.176927]
• 16: Robert Harper , Christopher Stone, A type-theoretic interpretation of standard ML, Proof, language, and interaction: essays in honour of Robin Milner, MIT Press, Cambridge, MA, 2000
• 17: Tom Hirschowitz , Xavier Leroy, Mixin modules in a call-by-value setting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.857-881, September 2005 [doi>10.1145/1086642.1086644]
• 18: Mark P. Jones, Using parameterized signatures to express modular structure, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.68-78, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237731]
• 19: Xavier Leroy, Applicative functors and fully transparent higher-order modules, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.142-153, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199476]
• 20: Xavier Leroy, Manifest types, modules, and separate compilation, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.109-122, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.176926]
• 21: Xavier Leroy, A modular module system, Journal of Functional Programming, v.10 n.3, p.269-303, May 2000 [doi>10.1017/S0956796800003683]
• 22: Xavier Leroy. A proposal for recursive modules in Objective Caml, 2003. http://caml.inria.fr/pub/papers/xleroy-recursive_modules-03.pdf.
• 23: David MacQueen, Modules for standard ML, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.198-207, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802036]
• 24: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 25: David A. Moon, Object-oriented programming with flavors, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-8, September 29-October 02, 1986, Portland, Oregon, United States
• 26: Keiko Nakata , Jacques Garrigue, Recursive modules for programming, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 27: Nathaniel Nystrom , Xin Qi , Andrew C. Myers, J&: nested intersection for scalable software composition, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 28: M. Odersky, V. Cremet, C. Röckl, and M. Zenger. A nominal theory of objects with dependent types. In ECOOP '03.
• 29: Martin Odersky , Matthias Zenger, Scalable component abstractions, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 30: Scott Owens , Matthew Flatt, From structures and functors to modules and units, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 31: Norman Ramsey , Kathleen Fisher , Paul Govereau, An expressive language of signatures, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 32: Andreas Rossberg, The missing link: dynamic components for ML, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 33: Claudio V. Russo, Recursive structures for standard ML, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types; Recursion; Modules, packages

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Theory

Keywords:
ML modules, abstract data types, hierarchical composability, mixin modules, recursive modules, type systems