James Cheney
Ralf Hinze
ABSTRACT
The recent years have seen a number of proposals for extending statically typed languages by dynamics or generics. Most proposals --- if not all --- require significant extensions to the underlying language. In this paper we show that this need not be the case. We propose a particularly lightweight extension that supports both dynamics and generics. Furthermore, the two features are smoothly integrated: dynamic values, for instance, can be passed to generic functions. Our proposal makes do with a standard Hindley-Milner type system augmented by existential types. Building upon these ideas we have implemented a small library that is readily usable both with Hugs and with the Glasgow Haskell compiler.
- Martín Abadi, Luca Cardelli, Benjamin Pierce, and Didier Rémy. Dynamic typing in polymorphic languages. Journal of Functional Programming, 5(1):111-130, January 1995.]]Google Scholar
Cross Ref
- Martín Abadi, Luca Cardelli, Benjamin Pierce, and Gordon Plotkin. Dynamic typing in a statically typed language. ACM Transactions on Programming Languages and Systems, 13(2):237-268, April 1991.]] Google ScholarDigital Library
- Artem Alimarine and Rinus Plasmeijer. A generic programming extension for Clean. In Th. Arts and M. Mohnen, editors, Proceedings of the 13th International workshop on the Implementation of Functional Languages, IFL '01, pages 257-278, Älvsjö, Sweden, September 2001.]] Google ScholarDigital Library
- Arthur I. Baars and S. Doaitse Swierstra. Typing dynamic typing. In Simon Peyton Jones, editor, Proceedings of the 2002 International Conference on Functional Programming, Pittsburgh, PA, USA, October 4-6, 2002. ACM Press, October 2002. To appear.]] Google ScholarDigital Library
- Roland Backhouse, Patrik Jansson, Johan Jeuring, and Lambert Meertens. Generic Programming --- An Introduction. In S. Doaitse Swierstra, Pedro R. Henriques, and Jose N. Oliveira, editors, 3rd International Summer School on Advanced Functional Programming, Braga, Portugal, volume 1608 of Lecture Notes in Computer Science, pages 28-115. Springer-Verlag, Berlin, 1999.]]Google Scholar
- Richard Bird and Lambert Meertens. Nested datatypes. In J. Jeuring, editor, Fourth International Conference on Mathematics of Program Construction, MPC '98, Marstrand, Sweden, volume 1422 of Lecture Notes in Computer Science, pages 52-67. Springer-Verlag, June 1998.]] Google ScholarDigital Library
- Dæv Clarke, Ralf Hinze, Johan Jeuring, Andres Löh, and Jan de Wit. The Generic Haskell user's guide. Technical Report UU-CS-2001-26, Universiteit Utrecht, November 2001.]]Google Scholar
- Karl Crary and Stephanie Weirich. Flexible type analysis. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP '99), Paris, France, volume (34)9 of ACM SIGPLAN Notices, pages 233-248. ACM Press, September 1999.]] Google ScholarDigital Library
- Karl Crary, Stephanie Weirich, and Greg Morrisett. Intensional polymorphism in type-erasure semantics. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP '98), Baltimore, MD, volume (34)1 of ACM SIGPLAN Notices, pages 301-312. ACM Press, January 1999.]] Google ScholarDigital Library
- Rowan Davies and Frank Pfenning. A modal analysis of staged computation. Journal of the ACM, 48(3):555-604, May 2001.]] Google ScholarDigital Library
- Cordelia V. Hall, Kevin Hammond, Simon L. Peyton Jones, and Philip L. Wadler. Type classes in Haskell. ACM Transactions on Programming Languages and Systems, 18(2):109-138, March 1996.]] Google ScholarDigital Library
- Michael Hanus. Horn clause programs with polymorphic types: semantics and resolution. Theoretical Computer Science, 89(1):63-106, October 1991.]] Google ScholarDigital Library
- Robert Harper and Mark Lillibridge. A type-theoretic approach to higher-order modules with sharing. In Conference Record of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '94), Portland, Oregon, pages 123-137, New York, NY, January 1994. ACM.]] Google ScholarDigital Library
- Robert Harper and Greg Morrisett. Compiling polymorphism using intensional type analysis. In Conference record of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '95), San Francisco, California, pages 130-141. ACM Press, 1995.]] Google ScholarDigital Library
- Ralf Hinze. Memo functions, polytypically! In Johan Jeuring, editor, Proceedings of the 2nd Workshop on Generic Programming, Ponte de Lima, Portugal, pages 17-32, July 2000. The proceedings appeared as a technical report of Universiteit Utrecht, UU-CS-2000-19.]]Google Scholar
- Ralf Hinze. A new approach to generic functional programming. In Thomas W. Reps, editor, Proceedings of the 27th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '00), Boston, Massachusetts, January 19-21, pages 119-132, January 2000.]] Google ScholarDigital Library
- Ralf Hinze. Polytypic values possess polykinded types. Science of Computer Programming, 2002. To appear.]]Google ScholarCross Ref
- Ralf Hinze and Simon Peyton Jones. Derivable type classes. In Graham Hutton, editor, Proceedings of the 2000 ACM SIGPLAN Haskell Workshop, volume 41.1 of Electronic Notes in Theoretical Computer Science. Elsevier Science, August 2001. The preliminary proceedings appeared as a University of Nottingham technical report.]]Google Scholar
- Patrik Jansson and Johan Jeuring. PolyP---a polytypic programming language extension. In Conference Record of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '97), Paris, France, pages 470-482. ACM Press, January 1997.]] Google ScholarDigital Library
- Xavier Leroy. Manifest types, modules, and separate compilation. In Conference Record of the 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '94), Portland, Oregon, pages 109-122, New York, NY, January 1994. ACM.]] Google ScholarDigital Library
- Xavier Leroy and Michel Mauny. Dynamics in ML. Journal of Functional Programming, 3(4):431-463, 1993.]]Google ScholarCross Ref
- Yasuhiko Minamide, Greg Morrisett, and Robert Harper. Typed closure conversion. In Conference Record of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '96), pages 271-283, St. Petersburg Beach, Florida, January 1996.]] Google ScholarDigital Library
- Simon Peyton Jones and John Hughes, editors. Haskell 98 --- A Non-strict, Purely Functional Language, February 1999. Available from http://www.haskell.org/definition/.]]Google Scholar
- Simon Peyton Jones, Andrew Tolmach, and Tony Hoare. Playing by the rules: Rewriting as an optimization technique in GHC. In Ralf Hinze, editor, Proceedings of the 2001 ACM SIGPLAN Haskell Workshop (HW '2001), 2nd September 2001, Firenze, Italy, Electronic Notes in Theoretical Computer Science, Vol. 59, pages 203-233, September 2001. The preliminary proceedings appeared as a Universiteit Utrecht technical report, UU-CS-2001-62.]]Google Scholar
- Benjamin C. Pierce. Types and programming languages. MIT Press, Cambridge, Mass., 2002.]] Google ScholarDigital Library
- Marco Pil. Dynamic types and type dependent functions. In Kevin Hammond, Antony J. T. Davie, and Chris Clack, editors, Implementation of Functional Languages, 10th International Workshop, IFL '98, London, UK, September 9-11, Selected Papers, volume 1595 of Lecture Notes in Computer Science, pages 169-185. Springer, 1999.]] Google ScholarDigital Library
- Mark Shields, Tim Sheard, and Simon Peyton Jones. Dynamic typing as staged type inference. In The 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '98), pages 289-302, New York, January 1998. ACM.]] Google ScholarDigital Library
- Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM '97), volume (32)12 of ACM SIGPLAN Notices, pages 203-217, New York, June 1997. ACM Press.]] Google ScholarDigital Library
- Philip Wadler. Theorems for free! In The Fourth International Conference on Functional Programming Languages and Computer Architecture (FPCA '89), London, UK, pages 347-359. Addison-Wesley Publishing Company, September 1989.]] Google ScholarDigital Library
- Philip Wadler. The Girard-Reynolds isomorphism. In N. Kobayashi and B. C. Pierce, editors, Proc. of 4th Int. Symp. on Theoretical Aspects of Computer Science, TACS 2001, Sendai, Japan, 29-31 Oct. 2001, volume 2215 of Lecture Notes in Computer Science, pages 468-491. Springer-Verlag, Berlin, 2001.]] Google Scholar
- Philip Wadler and Stephen Blott. How to make ad-hoc polymorphism less ad hoc. In Proceedings of the 16th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '89), pages 60-76, Austin, TX, USA, January 1989. ACM Press.]] Google ScholarDigital Library
- Stephanie Weirich. Type-safe cast: functional pearl. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP '00), volume (35)9 of ACM SIGPLAN Notices, pages 58-67, N.Y., September 2000. ACM Press.]] Google ScholarDigital Library
- Stephanie Weirich. Encoding intensional type analysis. In David Sands, editor, Proceedings of the 10th European Symposium on Programming, ESOP 2001, volume 2028 of Lecture Notes in Computer Science, pages 92-106, 2001.]] Google ScholarDigital Library
Index Terms
- A lightweight implementation of generics and dynamics
Recommendations
Generics for the masses
ICFP '04: Proceedings of the ninth ACM SIGPLAN international conference on Functional programmingA generic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of generic functions are the functions that can be derived in Haskell, such as show, read, and '=='. The recent years have ...
Generics for the masses
ICFP '04A generic function is a function that can be instantiated on many data types to obtain data type specific functionality. Examples of generic functions are the functions that can be derived in Haskell, such as show, read, and '=='. The recent years have ...
Lightweight, flexible object-oriented generics
PLDI '15: Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and ImplementationThe support for generic programming in modern object-oriented programming languages is awkward and lacks desirable expressive power. We introduce an expressive genericity mechanism that adds expressive power and strengthens static checking, while ...
Comments