Bialgebra views: a way for polytypic programming to cohabit with data abstraction

ABSTRACT

Polytypic programming and data abstraction are important concepts in designing functional programs, but they do not fit well together. Polytypic programming currently depends on making public a free data type representation, while data abstraction depends on hiding the representation. This paper proposes the bialgebra views mechanism as a means of reconciling this conflict. Bialgebra views enable the specification of type structure according to interfaces, not representations, thus combining the genericity of polytypic programming with the information hiding of data abstraction, and narrowing the gap between generic programming in the functional and object-oriented paradigms.

REFERENCES

• 1: 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
• 2: Michael Barr , Charles Wells, Category theory for computing science, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: Maarten M. Fokkinga. Law and Order in Algorithmics. PhD thesis, Universiteit Twente, The Netherlands, 1992.
• 4: Jeremy Gibbons. Patterns in datatype-generic programming. In Declarative Programming in the Context of Object-Oriented Languages, 2003.
• 5: Jeremy Gibbons and Bruno C. d. S. Oliveira. The essence of the Iterator pattern. In Mathematically-Structured Functional Programming, 2006.
• 6: Ralf Hinze. Polytypic values possess polykinded types. Science of Computer Programming, 43(2-3), 2002.
• 7: Ralf Hinze and Johan Jeuring. Generic Haskell: Practice and Theory. In Generic Programming - Advanced Lectures, volume 2793 of LNCS. Springer, 2003.
• 8: Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez. Generic views on data types. In Mathematics of Program Construction, 2006.
• 9: Patrik Jansson. Functional Polytypic Programming. PhD thesis, Chalmers University of Technology, 2000.
• 10: C. B. Jay , G. Bellè , E. Moggi, Functorial ML, Journal of Functional Programming, v.8 n.6, p.573-619, November 1998 [doi>10.1017/S0956796898003128]
• 11: Johan Jeuring , Patrik Jansson, Polytypic Programming, Advanced Functional Programming, Second International School-Tutorial Text, p.68-114, August 26-30, 1996
• 12: Wolfram Kahl and Jan Scheffczyk. Named instances for Haskell type classes. In Haskell Workshop, 2001.
• 13: 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
• 14: 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
• 15: Ralf Lämmel, Eelco Visser, and Joost Visser. The essence of strategic programming. Tutorial, 2002.
• 16: Barbara Liskov, Abstraction and specification in program development, MIT Press, Cambridge, MA, 1986
• 17: Andres Löh. Exploring Generic Haskell. PhD thesis, Utrecht University, 2004.
• 18: Erik Meijer , Maarten M. Fokkinga , Ross Paterson, Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, p.124-144, August 26-30, 1991
• 19: John C. Mitchell, Foundations of programming languages, MIT Press, Cambridge, MA, 1996
• 20: 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]
• 21: Gustav Munkby , Andreas Priesnitz , Sibylle Schupp , Marcin Zalewski, Scrap++: scrap your boilerplate in C++, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159871]
• 22: David Musser and Atul Saini. STL Tutorial and Reference Guide. Addison-Wesley, 1996.
• 23: Pablo Nogueira, Context-parametric polykinded types, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159868]
• 24: Pablo Nogueira. When is an abstract data type a functor? In Trends in Functional Programming, volume 7. Intellect, 2006.
• 25: Chris Okasaki, Purely functional data structures, Cambridge University Press, New York, NY, 1998
• 26: Chris Okasaki. An overview of Edison. In Haskell Workshop, 2000.
• 27: Pedro Palao Gostanza , Ricardo Peña , Manuel Núñez, A new look at pattern matching in abstract data types, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.110-121, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 28: P. Wadler, Views: a way for pattern matching to cohabit with data abstraction, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.307-313, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41653]
• 29: F. Warren Burton and Robert Cameron. Pattern matching with abstract data types. Journal of Functional Programming, 3(2), 1993.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.m Miscellaneous

General Terms:
Design, Languages, Theory

Keywords:
abstract types, bialgebras, polytypic programming, program generation