A lightweight implementation of generics and dynamics

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.

REFERENCES

• 1: 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.
• 2: Martín Abadi , Luca Cardelli , Benjamin Pierce , Gordon Plotkin, Dynamic typing in a statically typed language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.237-268, April 1991 [doi>10.1145/103135.103138]
• 3: Artem Alimarine , Marinus J. Plasmeijer, A Generic Programming Extension for Clean, Selected Papers from the 13th International Workshop on Implementation of Functional Languages, p.168-185, September 24-26, 2001
• 4: Arthur I. Baars , S. Doaitse Swierstra, Typing dynamic typing, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.157-166, October 04-06, 2002, Pittsburgh, PA, USA
• 5: 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.
• 6: Richard S. Bird , Lambert G. L. T. Meertens, Nested Datatypes, Proceedings of the Mathematics of Program Construction, p.52-67, June 15-17, 1998
• 7: 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.
• 8: Karl Crary , Stephanie Weirich, Flexible type analysis, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.233-248, September 27-29, 1999, Paris, France
• 9: Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.301-312, September 26-29, 1998, Baltimore, Maryland, United States
• 10: Rowan Davies , Frank Pfenning, A modal analysis of staged computation, Journal of the ACM (JACM), v.48 n.3, p.555-604, May 2001 [doi>10.1145/382780.382785]
• 11: Cordelia V. Hall , Kevin Hammond , Simon L. Peyton Jones , Philip L. Wadler, Type classes in Haskell, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.2, p.109-138, March 1996 [doi>10.1145/227699.227700]
• 12: Michael Hanus, Horn clause programs with polymorphic types: semantics and resolution, Theoretical Computer Science, v.89 n.1, p.63-106, Oct. 21, 1991
• 13: 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]
• 14: Robert Harper , Greg Morrisett, Compiling polymorphism using intensional type analysis, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.130-141, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199475]
• 15: 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.
• 16: Ralf Hinze, A new approach to generic functional programming, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.119-132, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325709]
• 17: Ralf Hinze. Polytypic values possess polykinded types. Science of Computer Programming, 2002. To appear.
• 18: 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.
• 19: Patrik Jansson , Johan Jeuring, PolyP—a polytypic programming language extension, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.470-482, January 15-17, 1997, Paris, France [doi>10.1145/263699.263763]
• 20: 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]
• 21: Xavier Leroy and Michel Mauny. Dynamics in ML. Journal of Functional Programming, 3(4):431-463, 1993.
• 22: Yasuhiko Minamide , Greg Morrisett , Robert Harper, Typed closure conversion, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.271-283, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237791]
• 23: Simon Peyton Jones and John Hughes, editors. Haskell 98 --- A Non-strict, Purely Functional Language, February 1999. Available from http://www.haskell.org/definition/.
• 24: 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.
• 25: Benjamin C. Pierce, Types and programming languages, MIT Press, Cambridge, MA, 2002
• 26: Marco Pil, Dynamic Types and Type Dependent Functions, Selected Papers from the 10th International Workshop on 10th International Workshop, p.169-185, September 09-11, 1998
• 27: Mark Shields , Tim Sheard , Simon Peyton Jones, Dynamic typing as staged type inference, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.289-302, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268970]
• 28: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 29: Philip Wadler, Theorems for free!, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.347-359, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99404]
• 30: Philip Wadler, The Girard-Reynolds Isomorphism, Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software, p.468-491, October 29-31, 2001
• 31: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]
• 32: Stephanie Weirich, Type-safe cast: (functional pearl), Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.58-67, September 2000
• 33: Stephanie Weirich, Encoding Intensional Type Analysis, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.92-106, April 02-06, 2001

INDEX TERMS

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

General Terms:
Languages

Keywords:
dynamic typing, generic programming, type representations