More Web Proxy on the site http://driver.im/

research-article

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

Authors:

Pablo Nogueira,

Juan José Moreno-NavarroAuthors Info & Claims

WGP '08: Proceedings of the ACM SIGPLAN workshop on Generic programming

Pages 61 - 73

https://doi.org/10.1145/1411318.1411327

Published: 20 September 2008 Publication History

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 and Marinus Plasmeijer. A generic programming extension for Clean. In Implementation of Functional Languages, 2001.

Digital Library

[2]

Michael Barr and Charles Wells. Category Theory for Computing Science. Prentice-Hall, 1990.

Digital Library

[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.

Digital Library

[5]

Jeremy Gibbons and Bruno C. d. S. Oliveira. The essence of the Iterator pattern. In Mathematically-Structured Functional Programming, 2006.

Digital Library

[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.

Digital Library

[9]

Patrik Jansson. Functional Polytypic Programming. PhD thesis, Chalmers University of Technology, 2000.

[10]

C. B. Jay, G. Bellè, and E. Moggi. Functorial ML. Journal of Functional Programming, 8(6), 1998.

Digital Library

[11]

Johan Jeuring and Patrik Jansson. Polytypic programming. In Advanced Functional Programming, volume 1129 of LNCS. Springer, 1996.

Digital Library

[12]

Wolfram Kahl and Jan Scheffczyk. Named instances for Haskell type classes. In Haskell Workshop, 2001.

[13]

Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: A practical design pattern for generic programming. In Workshop on Types in Language Design and Implementation, 2003.

Digital Library

[14]

Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate with class: extensible generic functions. In International Conference on Functional Programming, 2005.

Digital Library

[15]

Ralf Lämmel, Eelco Visser, and Joost Visser. The essence of strategic programming. Tutorial, 2002.

[16]

Barbara Liskov and John Guttag. Abstraction and Specification in Program Development. MIT Press, 1986.

Digital Library

[17]

Andres Löh. Exploring Generic Haskell. PhD thesis, Utrecht University, 2004.

[18]

Erik Meijer, Maarten Fokkinga, and Ross Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In Functional Programming Languages and Computer Architecture, 1991.

Digital Library

[19]

John C. Mitchell. Foundations for Programming Languages. MIT Press, 1996.

Digital Library

[20]

A. Moors, F. Piessens, and W. Joosen. An object-oriented approach to datatype-generic programming. In Workshop on Generic Programming, 2006.

Digital Library

[21]

G. Munkby, A. Priesnitz, S. Schupp, and M. Zalewski. Scrap++: Scrap your boilerplate in C++. In Workshop on Generic Programming, 2006.

Digital Library

[22]

David Musser and Atul Saini. STL Tutorial and Reference Guide. Addison-Wesley, 1996.

Digital Library

[23]

Pablo Nogueira. Context-parametric polykinded types. In Workshop on Generic Programming, 2006.

Digital Library

[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, 1998.

Digital Library

[26]

Chris Okasaki. An overview of Edison. In Haskell Workshop, 2000.

[27]

Pedro Palao Gostanza, Ricardo Peña and Manuel Núñez. A new look at pattern matching in abstract data types. In International Conference on Functional Programming, 1996.

Digital Library

[28]

Philip Wadler. Views: A way for pattern matching to cohabit with data abstraction. In Principles of Programming Languages, 1987.

Digital Library

[29]

F. Warren Burton and Robert Cameron. Pattern matching with abstract data types. Journal of Functional Programming, 3(2), 1993.

Cited By

Wang MGibbons JMatsuda KHu Z(2010)Gradual refinementProceedings of the 10th international conference on Mathematics of program construction10.5555/1886619.1886643(397-425)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1886619.1886643
Wang MGibbons JMatsuda KHu Z(2010)Gradual RefinementMathematics of Program Construction10.1007/978-3-642-13321-3_22(397-425)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13321-3_22

Index Terms

Bialgebra views: a way for polytypic programming to cohabit with data abstraction
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Context-parametric polykinded types
WGP '06: Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming

Generic Haskell is a language extension of Haskell for polytypic programming. Constrained types are parametric algebraic types with at least one argument constrained by type-class membership. We explain Generic Haskell, discuss the relevance of ...
Scala for generic programmers
WGP '08: Proceedings of the ACM SIGPLAN workshop on Generic programming

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 ...
An object-oriented approach to datatype-generic programming
WGP '06: Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming

Datatype-generic programming (DGP) is the next step beyond abstracting over types using parametric polymorphism, which is often called "genericity" in object-oriented languages. However, unlike genericity, DGP has not received much attention in the OO ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WGP '08: Proceedings of the ACM SIGPLAN workshop on Generic programming

September 2008

80 pages

ISBN:9781605580609

DOI:10.1145/1411318

Program Chairs:
Ralf Hinze
University of Oxford, UK
,
Don Syme
Microsoft Research, UK

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 September 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP08

Sponsor:

ICFP08: ACM SIGPLAN International Conference on Functional Programming

September 20, 2008

BC, Victoria, Canada

Acceptance Rates

WGP '08 Paper Acceptance Rate 6 of 10 submissions, 60%;

Overall Acceptance Rate 30 of 43 submissions, 70%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
126
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang MGibbons JMatsuda KHu Z(2010)Gradual refinementProceedings of the 10th international conference on Mathematics of program construction10.5555/1886619.1886643(397-425)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.5555/1886619.1886643
Wang MGibbons JMatsuda KHu Z(2010)Gradual RefinementMathematics of Program Construction10.1007/978-3-642-13321-3_22(397-425)Online publication date: 2010
https://doi.org/10.1007/978-3-642-13321-3_22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents