Mixin modules

ABSTRACT

Mixin modules are proposed as a new construct for module languages, allowing recursive definitions to span module boundaries. Mixin modules are proposed specifically for the Standard ML language. Several applications are described, including the resolution of cycles in module import dependency graphs, as well as functionality related to Haskell type classes and CLOS generic functions, though without any complications to the core language semantics. Mixin modules require no changes to the core ML type system, and only a very minor change to its run-time semantics. A type system and reduction semantics are provided, and the former is verified to be sound relative to the latter.

REFERENCES

• 1: Andrew Appel and David MacQueen. Standard ML of New Jersey. In Proceedings of the Symposium on Programming Language implementation and Logic Programming, volume 528 of Lecture Notes in Computer Science, pages 1-13. Springer-Verlag, 1991.
• 2: Andrew W. Appel , David B. MacQueen, Separate compilation for Standard ML, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.13-23, June 20-24, 1994, Orlando, Florida, United States
• 3: Gilad Bracha , William Cook, Mixin-based inheritance, ACM SIGPLAN Notices, v.25 n.10, p.303-311, Oct. 1990
• 4: Gilad Bracha and Gary Lindstrom. Modularity meets inheritance. In International Conference on Computer Languages, pages 282-290. IEEE, 1992.
• 5: R. M. Burstall. Design considerations for a functional programming language. In Infotech State of the Art Conference, Copenhagen, Denmark, 1977. Infotech.
• 6: R. M. Burstall , D. B. MacQueen , D. T. Sannella, HOPE: An experimental applicative language, Proceedings of the 1980 ACM conference on LISP and functional programming, p.136-143, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802799]
• 7: William R. Cook , Walter Hill , Peter S. Canning, Inheritance is not subtyping, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.125-135, December 1989, San Francisco, California, United States [doi>10.1145/96709.96721]
• 8: Dominic Duggan. Polymorphic methods with self types for ML-like languages. Technical Report CS-95-03, University of Waterloo, Department of Computer Science, 1995.
• 9: Dominic Duggan and Frederick Bent. Explaining type inference. Technical Report CS-94-14, University of Waterloo, Waterloo, Ontario, Canada, 1994. To appear in Science of Computer Programming.
• 10: Dominic Duggan and John Ophel. Kinded parametric overloading. Technical Report CS-94-35, University of Waterloo, Department of Computer Science, September 1994.
• 11: Dominic Duggan and John Ophel. On type-checking multiparameter type classes. To be submitted, 1995.
• 12: Jonathan Eifrig , Scott Smith , Valery Trifonov, Sound polymorphic type inference for objects, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.169-184, October 15-19, 1995, Austin, Texas, United States
• 13: 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]
• 14: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 15: Mark P. Jones, A system of constructor classes: overloading and implicit higher-order polymorphism, Proceedings of the conference on Functional programming languages and computer architecture, p.52-61, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165190]
• 16: Stefan Kaes, Parametric Overloading in Polymorphic Programming Languages, Proceedings of the 2nd European Symposium on Programming, p.131-144, March 21-24, 1988
• 17: S. E. Keene, A programmer's guide to object-oriented programming in Common LISP, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 18: 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]
• 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: Sheng Liang , Paul Hudak , Mark Jones, Monad transformers and modular interpreters, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.333-343, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199528]
• 21: Ole Lehrmann Madsen , Birger Mø-Pedersen , Kristen Nygaard, Object-oriented programming in the BETA programming language, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 22: John Mitchell , Sigurd Meldal , Neel Madhav, An extension of standard ML modules with subtyping and inheritance, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-278, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99620]
• 23: John C. Mitchell, Toward a typed foundation for method specialization and inheritance, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.109-124, December 1989, San Francisco, California, United States [doi>10.1145/96709.96719]
• 24: Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 25: Martin Odersky , Konstantin Läufer, Putting type annotations to work, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-67, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237729]
• 26: John Ophel. A polymorphic language with first-class modules. Australian Computer Science Communications, 17(1):422--430, February 1995.
• 27: Didier Rémy, Programming Objects with ML-ART, an Extension to ML with Abstract and Record Types, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.321-346, April 19-22, 1994
• 28: Constantinos Sourelis. Mixin modules. Master's thesis, University of Waterloo, 1995.
• 29: Guy L. Steele, Jr., Building interpreters by composing monads, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.472-492, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.178068]
• 30: Philip Wadler. Efficient compilation of pattern-matching. pages 78-103. Prentice-Hall, 1987. Chapter contributed to The implementation of Functional Programming Languages, Simon Peyton-Jones.
• 31: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 32: Andrew Wright and Matthias Felleisen. A syntactic approach to type soundness. Technical Report TR91-160, Rice University, April 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Design, Languages, Theory