Scala for generic programmers

ABSTRACT

Datatype-generic programming involves parametrization by the shape of data, in the form of type constructors such as "list of". Most approaches to datatype-generic programming are developed in the lazy functional programming language Haskell. We argue that the functional object-oriented language Scala is in many ways a better setting. Not only does Scala provide equivalents of all the necessary functional programming features (such parametric polymorphism, higher-order functions, higher-kinded type operations, and type- and constructor-classes), but it also provides the most useful features of object-oriented languages (such as subtyping, overriding, traditional single inheritance, and multiple inheritance in the form of traits). We show how this combination of features benefits datatype-generic programming, using three different approaches as illustrations.

REFERENCES

• 1: Kim Bruce , Luca Cardelli , Giuseppe Castagna , Gary T. Leavens , Benjamin Pierce, On binary methods, Theory and Practice of Object Systems, v.1 n.3, p.221-242, Fall 1995
• 2: P. Buchlovsky and H. Thielecke. A type-theoretic reconstruction of the Visitor pattern. In Mathematical Foundations of Programming Semantics, 2005.
• 3: 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]
• 4: R. Cockett and T. Fukushima. About Charity. Department of Computer Science, University of Calgary, May 1992.
• 5: William R. Cook, A denotational semantics of inheritance, Brown University, Providence, RI, 1989
• 6: A. Dijkstra and S. D. Swierstra. Making implicit parameters explicit. Technical Report UU-CS-2005-032, Department of Information and Computing Sciences, Utrecht University, 2005.
• 7: J. Garrigue. Code reuse through polymorphic variants. In Workshop on Foundations of Software Engineering, Sasaguri, Japan, 2000.
• 8: Jeremy Gibbons, Design patterns as higher-order datatype-generic programs, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159863]
• 9: J. Gibbons and B. C. d. S. Oliveira. The essence of the Iterator pattern. Journal of Functional Programming, 2008.
• 10: 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]
• 11: 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]
• 12: Ralf Hinze, Generics for the masses, Journal of Functional Programming, v.16 n.4-5, p.451-483, July 2006 [doi>10.1017/S0956796806006022]
• 13: R. Hinze and J. Jeuring. Generic Haskell: Practice and theory. In LNCS 2793: Summer School on Generic Programming, Berlin, 2002.
• 14: R. Hinze and A. Löh. Generic programming, now! In LNCS 4719: Datatype-Generic Programming, 2007.
• 15: R. Hinze and S. Peyton Jones. Derivable type classes. In Haskell Workshop, 2000.
• 16: R. Hinze, A. Löh, and B. C. d. S. Oliveira. "Scrap your Boilerplate" reloaded. In Functional and Logic Programming, 2006.
• 17: W. Kahl and J. Scheffczyk. Named instances for Haskell type classes. In Haskell Workshop, 2001.
• 18: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, Proceedings of the 2003 ACM SIGPLAN international workshop on Types in languages design and implementation, January 18-18, 2003, New Orleans, Louisiana, USA
• 19: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate with class: extensible generic functions, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 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: Karl J. Lieberherr, Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns, PWS Publishing Co., Boston, MA, 1995
• 22: A. Löh. Exploring Generic Haskell. PhD thesis, Utrecht University, 2004.
• 23: Andres Löh , Ralf Hinze, Open data types and open functions, Proceedings of the 8th ACM SIGPLAN international conference on Principles and practice of declarative programming, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140352]
• 24: Conor Mcbride , Ross Paterson, Applicative programming with effects, Journal of Functional Programming, v.18 n.1, p.1-13, January 2008 [doi>10.1017/S0956796807006326]
• 25: L. Meertens. Paramorphisms. Formal Aspects of Computing, 4 (5): 413--425, 1992.
• 26: Erik Meijer , Johan Jeuring, Merging Monads and Folds for Functional Programming, Advanced Functional Programming, First International Spring School on Advanced Functional Programming Techniques-Tutorial Text, p.228-266, May 24-30, 1995
• 27: A. Moors. Code-follows-type programming in Scala. http://www.cs.kuleuven.be/~adriaan/?q=cft_intro, June 2007.
• 28: Adriaan Moors , Frank Piessens , Wouter Joosen, An object-oriented approach to datatype-generic programming, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159875]
• 29: Adriaan Moors , Frank Piessens , Martin Odersky, Generics of a higher kind, Proceedings of the 23rd ACM SIGPLAN conference on Object oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 30: M. Odersky. An Overview of the Scala programming language (second edition). Technical Report IC/2006/001, EPFL Lausanne, Switzerland, 2006\natexlaba.
• 31: M. Odersky. Poor man's type classes. http://lamp.epfl.ch/~odersky/talks/wg2.8-boston06.pdf, July 2006.
• 32: M. Odersky. Scala by example. http://scala.epfl.ch/docu/files/ScalaIntro.pdf, May 2007.
• 33: M. Odersky. The Scala language specification version 2.4. http://scala.epfl.ch/docu/files/ScalaReference.pdf, May 2007.
• 34: Martin Odersky , Konstantin Läufer, Putting type annotations to work, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.54-67, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237729]
• 35: Martin Odersky , Matthias Zenger, Scalable component abstractions, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 36: B. C. d. S. Oliveira. Genericity, Extensibility and Type-Safety in the Visitor Pattern. PhD thesis, University of Oxford, 2007.
• 37: Bruno C.d.S. Oliveira , Jeremy Gibbons, Scala for generic programmers, Proceedings of the ACM SIGPLAN workshop on Generic programming, September 20-20, 2008, Victoria, BC, Canada [doi>10.1145/1411318.1411323]
• 38: B. C. d. S. Oliveira and M. Sulzmann. Objects to unify type classes and GADTs. http://www.comlab.ox.ac.uk/people/Bruno.Oliveira/objects.pdf, Apr. 2008.
• 39: B. C. d. S. Oliveira, R. Hinze, and A. Löh. Extensible and modular generics for the masses. In Trends in Functional Programming, pages 109--138, Apr. 2006.
• 40: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Geoffrey Washburn, Simple unification-based type inference for GADTs, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 41: A. Rodriguez, J. Jeuring, P. Jansson, A. Gerdes, O. Kiselyov, and B. C. d. S. Oliveira. Comparing libraries for generic programming in Haskell. Technical Report UU-CS-2008-010, Utrecht University, 2008.
• 42: N. Schärli, S. Ducasse, O. Nierstrasz, and A. Black. Traits: Composable units of behavior. In LNCS 2743: European Conference on Object-Oriented Programming, pages 248--274, July 2003.
• 43: M. Schinz. A Scala tutorial for Java programmers. http://scala.epfl.ch/docu/files/ScalaTutorial.pdf, May 2007.
• 44: Tim Sheard , Simon Peyton Jones, Template meta-programming for Haskell, Proceedings of the 2002 ACM SIGPLAN workshop on Haskell, p.1-16, October 03, 2002, Pittsburgh, Pennsylvania [doi>10.1145/581690.581691]
• 45: P. Wadler. Monads for functional programming. In Program Design Calculi. Springer-Verlag, 1993.
• 46: P. Wadler. The expression problem. Java Genericity Mailing list, Nov. 1998. URL http://www.cse.ohio-state.edu/~gb/cis888.07g/java-genericity/20.
• 47: G. Washburn. Revisiting higher-rank impredicative polymorphism in Scala. http://existentialtype.net/2008/05/26/revisiting-higher-rank-impredicat%ive-polymorphism-in-scala/, May 2008.
• 48: Stephanie Weirich, RepLib: a library for derivable type classes, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159844]

INDEX TERMS

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

General Terms:
Languages

Keywords:
datatype-generic programming, polytypic programming, scala