Extensible programming with first-class cases

ABSTRACT

We present language mechanisms for polymorphic, extensible records and their exact dual, polymorphic sums with extensible first-class cases. These features make it possible to easily extend existing code with new cases. In fact, such extensions do not require any changes to code that adheres to a particular programming style. Using that style, individual extensions can be written independently and later be composed to form larger components. These language mechanisms provide a solution to the expression problem.We study the proposed mechanisms in the context of an implicitly typed, purely functional language PolyR. We give a type system for the language and provide rules for a 2-phase transformation: first into an explicitly typed λ-calculus with record polymorphism, and finally to efficient index-passing code. The first phase eliminates sums and cases by taking advantage of the duality with records.We implement a version of PolyR extended with imperative features and pattern matching - we call this language MLPolyR. Programs in MLPolyR require no type annotations - the implementation employs a reconstruction algorithm to infer all types. The compiler generates machine code (currently for PowerPC) and optimizes the representation of sums by eliminating closures generated by the dual construction.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: A.W. Appel and D.B. MacQueen. Standard ML of New Jersey. In M. Wirsing, editor, 3rd International Symp. on Prog. Lang. Implementation and Logic Programming, pages 1--13, New York, Aug. 1991. Springer-Verlag.
• 3: François Bourdoncle , Stephan Merz, Type checking higher-order polymorphic multi-methods, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.302-315, January 15-17, 1997, Paris, France [doi>10.1145/263699.263743]
• 4: K. Bruce. Some challenging typing issues in object-oriented languages. In Electronic notes in Theoretical Computer Science, volume 82(8), 2003.
• 5: Luca Cardelli , John C. Mitchell, Operations on records, Theoretical aspects of object-oriented programming: types, semantics, and language design, MIT Press, Cambridge, MA, 1994
• 6: Robert Bruce Findler , Matthew Flatt, Modular object-oriented programming with units and mixins, ACM SIGPLAN Notices, v.34 n.1, p.94-104, Jan. 1999
• 7: Cormac Flanagan , Amr Sabry , Bruce F. Duba , Matthias Felleisen, The essence of compiling with continuations, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.237-247, June 21-25, 1993, Albuquerque, New Mexico, United States
• 8: Matthew Raymond Flatt , Matthias Felleisen, Programming languages for reusable software components, 2000
• 9: Tim Freeman , Frank Pfenning, Refinement types for ML, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.268-277, June 24-28, 1991, Toronto, Ontario, Canada
• 10: J. Garrigue. Programming with polymorphic variants. In ACM SIGPLAN Workshop on ML, 1998.
• 11: J. Garrigue. Code reuse through polymorphic variants. In Workshop on Foundations of Software Engineering, Nov. 2000.
• 12: B.R. Gaster and M.P. Jones. A polymorphic type system for extensible records and variants. Technical Report NOTTCS-TR-96-3, Department of Computer Science, University of Nottingham, 1996.
• 13: K. Gowani and M. Blume. Writing a garbage collector for the MLPolyR compiler, July 2005. Final report on independent study project in the CSPP program.
• 14: M.P. Jones. Coherence for qualified types. Technical Report YALEU/DCS/RR-989, Yale University, New Haven, Connecticut, USA, 1993.
• 15: M.P. Jones and S.P. Jones. Lightweight extensible records for Haskell, 1999.
• 16: Shriram Krishnamurthi , Matthias Felleisen , Daniel P. Friedman, Synthesizing Object-Oriented and Functional Design to Promote Re-Use, Proceedings of the 12th European Conference on Object-Oriented Programming, p.91-113, July 20-24, 1998
• 17: X. Leroy. {caml-list} cyclic types. http://caml.inria.fr/pub/ml-archives/caml-list/,Jan. 2005.
• 18: Todd Millstein , Colin Bleckner , Craig Chambers, Modular typechecking for hierarchically extensible datatypes and functions, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.110-122, October 04-06, 2002, Pittsburgh, PA, USA
• 19: R. Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 13(3):348--375, 1978.
• 20: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 21: N. I. Adams, IV , D. H. Bartley , G. Brooks , R. K. Dybvig , D. P. Friedman , R. Halstead , C. Hanson , C. T. Haynes , E. Kohlbecker , D. Oxley , K. M. Pitman , G. J. Rozas , G. L. Steele, Jr. , G. J. Sussman , M. Wand , H. Abelson, Revised5 report on the algorithmic language scheme, ACM SIGPLAN Notices, v.33 n.9, p.26-76, Sept. 1, 1998 [doi>10.1145/290229.290234]
• 22: Martin Odersky , Philip Wadler, Pizza into Java: translating theory into practice, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.146-159, January 15-17, 1997, Paris, France [doi>10.1145/263699.263715]
• 23: Atsushi Ohori, A simple semantics for ML polymorphism, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.281-292, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99393]
• 24: Atsushi Ohori, A compilation method for ML-style polymorphic record calculi, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.154-165, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143200]
• 25: Atsushi Ohori, A polymorphic record calculus and its compilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.844-895, Nov. 1995 [doi>10.1145/218570.218572]
• 26: D. Rémy. Type inference for records in a natural extension of ML. Research Report 1431, Institut National de Recherche en Informatique et Automatisme, Rocquencourt, BP 105, 78 153 Le Chesnay Cedex, France, may 1991.
• 27: Didier Rémy , Jérôme Vouillon, Objective ML: an effective object-oriented extension to ML, Theory and Practice of Object Systems, v.4 n.1, p.27-50, 1998 [doi>10.1002/(SICI)1096-9942(1998)4:1<27::AID-TAPO3>3.0.CO;2-4]
• 28: John Reppy , Jon Riecke, Simple objects for Standard ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.171-180, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 29: M. Torgersen. The expression problem revisited: Four new solutions using generics. In M. Odersky, editor, ECOOP 2004-Object-Oriented Programming, 18th European Conference, Oslo, Norway, Proceedings, volume 3086 of LNCS, pages 123--143, New York, NY, July 2004. Springer-Verlag.
• 30: P. Wadler. The expression problem. Email to the Java Genericity mailing list, Dec. 1998.
• 31: M. Wand. Complete type inference for simple objects. In Proceedings of the IEEE Symposium on Logic in Computer Science, Ithaca, NY, June 1987.
• 32: Mitchell Wand, Type inference for record concatenation and multiple inheritance, Information and Computation, v.93 n.1, p.1-15, July 1991 [doi>10.1016/0890-5401(91)90050-C]
• 33: Matthias Zenger , Martin Odersky, Extensible algebraic datatypes with defaults, Proceedings of the sixth ACM SIGPLAN international conference on Functional programming, September 03-05, 2001, Florence, Italy
• 34: M. Zenger and M. Odersky. Independently extensible solutions to the expression problem. In The 12th International Workshop on Foundations of Object-Oriented Languages (FOOL 12), Long Beach, California, 2005. ACM.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

General Terms:
Design, Languages

Keywords:
duality, first-class cases, records, sums