Mixin modules in a call-by-value setting

ABSTRACT

The ML module system provides powerful parameterization facilities, but lacks the ability to split mutually recursive definitions across modules and provides insufficient support for incremental programming. A promising approach to solve these issues is Ancona and Zucca's mixin module calculus CMS. However, the straightforward way to adapt it to ML fails, because it allows arbitrary recursive definitions to appear at any time, which ML does not otherwise support. In this article, we enrich CMS with a refined type system that controls recursive definitions through the use of dependency graphs. We then develop and prove sound a separate compilation scheme, directed by dependency graphs, that translates mixin modules down to a call-by-value λ-calculus extended with a nonstandard let rec construct.

REFERENCES

• 1: Martin Abadi , Luca Cardelli, A Theory of Objects, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 2: Ancona, D. 1998. Modular formal frameworks for module systems. Ph.D. dissertation. Universita di Pisa, Pisa, Italy.
• 3: Davide Ancona , Elena Zucca, A Primitive Calculus for Module Systems, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.62-79, September 29-October 01, 1999
• 4: 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]
• 5: Ariola, Z. M. and Blom, S. 2002. Skew confluence and the lambda calculus with letrec. Ann. Pure Appl. Logic 117, 1--3, 95--178.
• 6: Andrew P. Black , Nathanael Schärli , Stéphane Ducasse, Applying traits to the smalltalk collection classes, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 7: Bono, V., Bugliesi, M., Dezani-Ciancaglini, M., and Liquori, L. 1999. Subtyping for extensible, incomplete objects. Fund. Info. 38, 4, 325--364.
• 8: Gérard Boudol, The recursive record semantics of objects revisited, Journal of Functional Programming, v.14 n.3, p.263-315, May 2004 [doi>10.1017/S0956796803004775]
• 9: Gilad Bracha, The programming language jigsaw: mixins, modularity and multiple inheritance, University of Utah, Salt Lake City, UT, 1992
• 10: Gilad Bracha , William Cook, Mixin-based inheritance, ACM SIGPLAN Notices, v.25 n.10, p.303-311, Oct. 1990
• 11: Luca Cardelli, Program fragments, linking, and modularization, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.266-277, January 15-17, 1997, Paris, France [doi>10.1145/263699.263735]
• 12: William R. Cook, A denotational semantics of inheritance, 1989
• 13: G. Cousineau , P.-L. Curien, The categorical abstract machine, Science of Computer Programming, v.8 n.2, p.173-202, April 1, 1987 [doi>10.1016/0167-6423(87)90020-7 ]
• 14: 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
• 15: 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
• 16: Dreyer, D. R., Crary, K., and Harper, R. 2001. Toward a practical type theory for recursive modules. Tech. Rep. CMU-CS-01-112, Carnegie Mellon University.
• 17: Dreyer, D., Harper, R., and Crary, K. 2003. A type system for well founded recursion. Tech. Rep. CMU-CS-03-163, Carnegie Mellon University.
• 18: Dominic Duggan , Constantinos Sourelis, Mixin modules, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.262-273, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 19: Robert Bruce Findler , Matthew Flatt, Modular object-oriented programming with units and mixins, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.94-104, September 26-29, 1998, Baltimore, Maryland, United States
• 20: 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
• 21: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 22: 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]
• 23: Hirschowitz, T. 2003. Modules mixins, modules et récursion étendue en appel par valeur. Ph.D. dissertation. University Paris 7.
• 24: Tom Hirschowitz , Xavier Leroy , J. B. Wells, Compilation of extended recursion in call-by-value functional languages, Proceedings of the 5th ACM SIGPLAN international conference on Principles and practice of declaritive programming, p.160-171, August 27-29, 2003, Uppsala, Sweden [doi>10.1145/888251.888267]
• 25: Hirschowitz, T., Leroy, X., and Wells, J. B. 2004. Call-by-value mixin modules: Reduction semantics, side effects, types. In Proceedings of the Programming Languages and Systems, 13th European Symposium on Programming, ESOP 2004. Lecture Notes in Computer Science, vol. 2986. Springer-Verlag, Berlin, Germany, 64--78.
• 26: 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]
• 27: Lillibridge, M. 1997. Translucent sums: A foundation for higher-order module systems. Ph.D. dissertation. School of Computer Science, Carnegie Mellon University.
• 28: 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
• 29: 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
• 30: J. B. Wells , René Vestergaard, Equational Reasoning for Linking with First-Class Primitive Modules, Proceedings of the 9th European Symposium on Programming Languages and Systems, p.412-428, April 02, 2000

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages; Applicative (functional) languages
      D.3.3 Language Constructs and Features
          Subjects: Modules, packages; Recursion; Inheritance

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Keywords:
Mixins, modules, recursion, type systems