Open data types and open functions

ABSTRACT

The problem of supporting the modular extensibility of both data and functions in one programming language at the same time is known as the expression problem. Functional languages traditionally make it easy to add new functions, but extending data (adding new data constructors) requires modifying existing code. We present a semantically and syntactically lightweight variant of open data types and open functions as a solution to the expression problem in the Haskell language. Constructors of open data types and equations of open functions may appear scattered throughout a program with several modules. The intended semantics is as follows: the program should behave as if the data types and functions were closed, defined in one place. The order of function equations is determined by best-fit pattern matching, where a specific pattern takes precedence over an unspecific one. We show that our solution is applicable to the expression problem, generic programming, and exceptions. We sketch two implementations: a direct implementation of the semantics, and a scheme based on mutually recursive modules that permits separate compilation

REFERENCES

• 1: Wadler, P.: The expression problem. Mail to the java-genericity mailing list (1998).
• 2: Craig Chambers, Object-Oriented Multi-Methods in Cecil, Proceedings of the European Conference on Object-Oriented Programming, p.33-56, June 29-July 03, 1992
• 3: 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
• 4: 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]
• 5: Ralf Hinze, Generics for the masses, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, USA
• 6: Löh, A., Jeuring, J., Clarke, D., Hinze, R., Rodriguez, A., de Wit, J.: The Generic Haskell user's guide, version 1.42 (Coral). Technical Report UU-CS-2005-004, Institute of Information and Computing Sciences, Utrecht University (2005).
• 7: James Cheney , Ralf Hinze, A lightweight implementation of generics and dynamics, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.90-104, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581698]
• 8: Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088358]
• 9: Hinze, R., Löh, A., Oliveira, B.C.: "Scrap Your Boilerplate" reloaded. In Hagiya, M., Wadler, P., eds.: Proceedings of FLOPS 2006. Lecture Notes in Computer Science, Springer (2006) Available from http://www.iai.uni-bonn.de/~loeh/SYB0.html.
• 10: Daume, H.: Haskell all-in-one. Tool homepage (2003) http://www.isi.edu/~hdaume/HAllInOne/.
• 11: Meacham, J.: Jhc. Compiler homepage (2006) http://repetae.net/john/computer/jhc/jhc.html.
• 12: Zenger, M., Odersky, M.: Independently extensible solutions to the expression problem. In: Foundations of Object-Oriented Languages (FOOL 2005). (2005).
• 13: 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
• 14: Torgersen, M.: The expression problem revisited -- four new solutions using generics. In Odersky, M., ed.: Proceedings of ECOOP 2004, Springer (2004) 123--146.
• 15: Leroy, X., Doligez, D., Garrigue, J., Rémy, D., Vouillon, J.: The Objective Caml system release 3.09 -- Documentation and user's manual. Institut National de Recherche en Informatique et en Automatique. (2004) Available from http://caml.inria.fr/pub/docs/manual-ocaml/.
• 16: Gaster, B.R., Jones, M.P.: A polymorphic type system for extensible records and variants. Technical Report NOTTCS-TR-96-3, Department of Computer Science, University of Nottingham (1996).
• 17: Leijen, D.: Extensible records with scoped labels. In: Proceedings of the 2005 Symposium on Trends in Functional Programming (TFP'05). (2005) 297--312.
• 18: Garrigue, J.: Code reuse through polymorphic variants. In: Workshop on Foundations of Software Engineering. (2000).
• 19: Nordlander, J.: A survey of O'Haskell. Web article (2001) Available from http://www.cs.chalmers.se/~nordland/ohaskell/survey.html.
• 20: Kiselyov, O., Lämmel, R.: Haskell's overlooked object system. Draft. Available from http://homepages.cwi.nl/~ralf/OOHaskell/ (2005).
• 21: Tim Sheard, Putting curry-howard to work, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.74-85, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088356]
• 22: Mitchell, N., Runciman, C.: Unfailing Haskell: a static checker for pattern matching. In: Proceedings of the 2005 Symposium on Trends in Functional Programming (TFP'05). (2005) 313--328.
• 23: Dijkstra, A., Swierstra, S.D.: Explicit implicit parameters. Technical Report UU-CS-2004-059, Institute of Information and Computing Sciences, Utrecht University (2004).
• 24: Conor McBride , James McKinna, The view from the left, Journal of Functional Programming, v.14 n.1, p.69-111, January 2004 [doi>10.1017/S0956796803004829]
• 25: Hanus, M.: Curry -- An Integrated Functional Logic Language (Version 0.8). (2003) Available from http://www.informatik.uni-kiel.de/~mh/curry/report.html.
• 26: Field, A.J., Harrison, P.G.: Functional Programming. Addison-Wesley (1988).
• 27: Mark Tullsen, First Class Patterns, Proceedings of the Second International Workshop on Practical Aspects of Declarative Languages, p.1-15, January 01, 2000
• 28: Don Stewart , Manuel M. T. Chakravarty, Dynamic applications from the ground up, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.27-38, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088352]

INDEX TERMS

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

Keywords:
Haskell, expression problem, extensible data types, extensible exceptions, extensible functions, functional programming, generic programming, mutually recursive modules