Andres Löh
Ralf Hinze
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
- Wadler, P.: The expression problem. Mail to the java-genericity mailing list (1998).]]Google Scholar
- Chambers, C.: Object-oriented multi-methods in Cecil. In: ECOOP '92: Proceedings of the European Conference on Object-Oriented Programming, Springer-Verlag (1992) 33--56.]] Google ScholarDigital Library
- Millstein, T., Bleckner, C., Chambers, C.: Modular typechecking for hierarchically extensible datatypes and functions. In: ICFP '02: Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, ACM Press (2002) 110--122.]] Google ScholarDigital Library
- Flatt, M., Krishnamurthi, S., Felleisen, M.: Classes and mixins. In: POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ACM Press (1998) 171--183.]] Google ScholarDigital Library
- Hinze, R.: Generics for the masses. In Fisher, K., ed.: Proceedings of the 2004 International Conference on Functional Programming, Snowbird, Utah, September 19--22, 2004. (2004) 236--243.]] Google ScholarDigital Library
- 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).]]Google Scholar
- Cheney, J., Hinze, R.: A lightweight implementation of generics and dynamics. In: Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, ACM Press (2002) 90--104.]] Google ScholarDigital Library
- Oliveira, B.C., Gibbons, J.: TypeCase: A design pattern for type-indexed functions. In: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, ACM Press (2005) 98--109.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- Daume, H.: Haskell all-in-one. Tool homepage (2003) http://www.isi.edu/~hdaume/HAllInOne/.]]Google Scholar
- Meacham, J.: Jhc. Compiler homepage (2006) http://repetae.net/john/computer/jhc/jhc.html.]]Google Scholar
- Zenger, M., Odersky, M.: Independently extensible solutions to the expression problem. In: Foundations of Object-Oriented Languages (FOOL 2005). (2005).]]Google Scholar
- Zenger, M., Odersky, M.: Extensible algebraic datatypes with defaults. In: Proceedings of the International Conference on Functional Programming (ICFP 2001). (2001).]] Google ScholarDigital Library
- Torgersen, M.: The expression problem revisited -- four new solutions using generics. In Odersky, M., ed.: Proceedings of ECOOP 2004, Springer (2004) 123--146.]]Google Scholar
- 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/.]]Google Scholar
- 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).]]Google Scholar
- Leijen, D.: Extensible records with scoped labels. In: Proceedings of the 2005 Symposium on Trends in Functional Programming (TFP'05). (2005) 297--312.]]Google Scholar
- Garrigue, J.: Code reuse through polymorphic variants. In: Workshop on Foundations of Software Engineering. (2000).]]Google Scholar
- Nordlander, J.: A survey of O'Haskell. Web article (2001) Available from http://www.cs.chalmers.se/~nordland/ohaskell/survey.html.]]Google Scholar
- Kiselyov, O., Lämmel, R.: Haskell's overlooked object system. Draft. Available from http://homepages.cwi.nl/~ralf/OOHaskell/ (2005).]]Google Scholar
- Sheard, T.: Putting Curry-Howard to work. In: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, ACM Press (2005) 74--85.]] Google ScholarDigital Library
- 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.]]Google Scholar
- Dijkstra, A., Swierstra, S.D.: Explicit implicit parameters. Technical Report UU-CS-2004-059, Institute of Information and Computing Sciences, Utrecht University (2004).]]Google Scholar
- McBride, C., McKinna, J.: The view from the left. Journal of Functional Programming 14(1) (2004) 69--111.]] Google ScholarDigital Library
- Hanus, M.: Curry -- An Integrated Functional Logic Language (Version 0.8). (2003) Available from http://www.informatik.uni-kiel.de/~mh/curry/report.html.]]Google Scholar
- Field, A.J., Harrison, P.G.: Functional Programming. Addison-Wesley (1988).]]Google Scholar
- Tullsen, M.: First class patterns. In Pontelli, E., Costa, V.S., eds.: Practical Aspects of Declarative Languages, Second International Workshop. Number 1753 in Lecture Notes in Computer Science, Springer (2000) 1--15.]] Google ScholarDigital Library
- Stewart, D., Chakravarty, M.M.T.: Dynamic applications from the ground up. In: Haskell '05: Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, ACM Press (2005) 27--38.]] Google ScholarDigital Library
Index Terms
- Open data types and open functions
Recommendations
Abstracting extensible data types: or, rows by any other name
We present a novel typed language for extensible data types, generalizing and abstracting existing systems of row types and row polymorphism. Extensible data types are a powerful addition to traditional functional programming languages, capturing ideas ...
Good advice for type-directed programming aspect-oriented programming and extensible generic functions
WGP '06: Proceedings of the 2006 ACM SIGPLAN workshop on Generic programmingType-directed programming is an important idiom for software design. In type-directed programming the behavior of programs is guided by the type structure of data. It makes it possible to implement many sorts of operations, such as serialization,...
Dynamic optimization for functional reactive programming using generalized algebraic data types
Proceedings of the tenth ACM SIGPLAN international conference on Functional programmingA limited form of dependent types, called Generalized Algebraic Data Types (GADTs), has recently been added to the list of Haskell extensions supported by the Glasgow Haskell Compiler. Despite not being full-fledged dependent types, GADTs still offer ...
Reviews
Hans J. Schneider
Functional languages such as Haskell make it easy to add new functions, but extending data requires modifying existing code since all constructors must be defined at the same place. On the other hand, object-oriented languages support the extension of data by defining subclasses, but new functions can be added only by changing class definitions. In section 2, the authors propose extending Haskell with open data types and open functions, the declarations of which may be spread over the whole program. The concept is illustrated by two examples in section 3: generic programming and exception handling. Section 4, the main section, is concerned with defining the semantics of the language extension. First, a core language restricted to the relevant features is translated into standard Haskell. The separate parts of the open function definitions and of the open data declarations are collected into a single module, where the order of the patterns and the order of the constructors deserve special consideration. The authors arrange the separate definitions of an open function in such a way that Haskell’s first-fit pattern matching leads to a best-fit matching. The order of constructors that are not defined in the same module is derived from the order of the import statements. The features not in the core language do not add new problems. Section 5 sketches two implementations, and the last section surveys related work in great detail. The paper is clearly written and is a valuable contribution to the stepwise development of functional programs. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments