Article

Design patterns as higher-order datatype-generic programs

Author:

Jeremy GibbonsAuthors Info & Claims

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

Pages 1 - 12

https://doi.org/10.1145/1159861.1159863

Published: 16 September 2006 Publication History

Abstract

Design patterns are reusable abstractions in object-oriented software. However, using current mainstream programming languages, these elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but evidence of a lack of expressivity in the languages of today. We expect that, in the languages of the future, the code parts of design patterns will be expressible as reusable library components. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. All that is needed, in addition to commonly-available features, are higher-order and datatype-generic constructs; these features are already or nearly available now. We argue the case by presenting higher-order datatype-generic programs capturing ORIGAMI, a small suite of patterns for recursive data structures.

References

[1]

A. Alexandrescu. Modern C++ Design. Addison-Wesley, 2001.

[2]

M.H. Austern. Generic Programming and the STL. Addison-Wesley, 1999.

[3]

R.C. Backhouse, P. Jansson, J. Jeuring, and L.G.L.T. Meertens. Generic programming: An introduction. In Advanced Functional Programming, volume 1608 of Lecture Notes in Computer Science, pages 28--115, 1998.

[4]

R. Bird. Introduction to Functional Programming Using Haskell. Prentice-Hall, 1998.

Digital Library

[5]

R. Bird and O. de Moor. The Algebra of Programming. Prentice-Hall, 1996.

Digital Library

[6]

R. Bird, O. de Moor, and P. Hoogendijk. Generic functional programming with types and relations. Journal of Functional Programming, 6(1):1--28, 1996.

[7]

J. Cheney and R. Hinze. A lightweight implementation of generics and dynamics. In Haskell Workshop, pages 90--104, 2002.

Digital Library

[8]

K. Claessen and J. Hughes. Specification-based testing with QuickCheck. In Gibbons and de Moor {20}, pages 17--40.

[9]

G. Dos Reis and J.Järvi. What is generic programming? In Library-Centric Software Design, 2005. OOPSLA workshop.

[10]

M.M. Fokkinga and E. Meijer. Program calculation properties of continuous algebras. Technical Report CS-R9104, CWI, Amsterdam, Jan. 1991.

[11]

E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns: Elements of Reusable Object- riented Software. Addison-Wesley, 1995.

Digital Library

[12]

R. Garcia, J. Järvi, A. Lumsdaine, J.G. Siek, and J. Willcock. A comparative study of language support for generic programming. In Object-Oriented Programming, Systems, Languages, and Applications, Oct. 2003.

Digital Library

[13]

J. Gibbons. Calculating functional programs. In R. Backhouse, R. Crole, and J. Gibbons, editors, Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, volume 2297 of Lecture Notes in Computer Science, pages 148--203. Springer-Verlag, 2002.

Digital Library

[14]

J. Gibbons. Origami programming. In Gibbons and de Moor {20}, pages 41--60.

[15]

J. Gibbons. Design patterns as higher-order datatype-generic programs. http://2005.ecoop.org/8.html, June 2005. Tutorial presented at ECOOP.

[16]

J. Gibbons. Design patterns as higher-order datatype-generic programs. http://www.oopsla.org/2005/ShowEvent.do?id=121, Oct. 2005. Tutorial presented at OOPSLA.

[17]

J. Gibbons. Datatype-generic programming. In Spring School on Datatype-Generic Programming. Springer-Verlag, 2006. To appear.

Digital Library

[18]

J. Gibbons. Design patterns as higher-order datatype-generic programs (full version). http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/#hodgp, June 2006.

[19]

J. Gibbons and B. C. d. S. Oliveira. The essence of the Iterator pattern. In T. Uustalu and C. McBride, editors, Mathematically-Structured Functional Programming, 2006.

Digital Library

[20]

J. Gibbons and O. de Moor, editors. The Fun of Programming. Cornerstones in Computing. Palgrave, 2003. ISBN 1-4039-0772-2.

[21]

J. Gibbons and G. Jones. The under-appreciated unfold. In Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming, pages 273--279, Baltimore, Maryland, Sept. 1998.

Digital Library

[22]

A. Gill, J. Launchbury, and S. Peyton Jones. A short cut to deforestation. In Functional Programming Languages and Computer Architecture, 1993.

Digital Library

[23]

R. Hinze. Polytypic values possess polykinded types. In R. C.Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction, volume 1837 of Lecture Notes in Computer Science, pages 2--27. Springer, 2000.

Digital Library

[24]

R. Hinze. Generics for the masses. Journal of Functional Programming, 2006.

Digital Library

[25]

R. Hinze and J. Jeuring. Generic Haskell: Practice and theory. In R. Backhouse and J. Gibbons, editors, Summer School on Generic Programming, volume 2793 of Lecture Notes in Computer Science, pages 1--56. Springer-Verlag, 2003.

[26]

R. Hinze and S. Peyton Jones. Derivable type classes. In G. Hutton, editor, Haskell Workshop, volume 41.1 of Electronic Notes in Theoretical Computer Science. Elsevier Science, Aug. 2000.

[27]

J. Hughes. Why functional programming matters. Computer Journal, 32(2):98--107, Apr. 1989.

Digital Library

[28]

G. Hutton. A tutorial on the universality and expressiveness of fold. Journal of Functional Programming, 9(4):355--372, July 1999.

Digital Library

[29]

P. Jansson and J. Jeuring. PolyP -- a polytypic programming language extension. In Principles of Programming Languages, pages 470--482, 1997.

Digital Library

[30]

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

Digital Library

[31]

C. B. Jay. A semantics for shape. Science of Computer Programming, 25:251--283, 1995.

Digital Library

[32]

G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-oriented programming. In M. Akşit and S. Matsuoka, editors, European Conference on Object-Oriented Programming, volume 1241 of Lecture Notes in Computer Science, pages 220--242. Springer-Verlag, Berlin, Heidelberg, and New York, 1997.

[33]

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

[34]

G. Malcolm. Data structures and program transformation. Science of Computer Programming, 14:255--279, 1990.

Digital Library

[35]

C. McBride and R. Paterson. Applicative programming with effects. Journal of Functional Programming, To appear.

Digital Library

[36]

E. Meijer, M. Fokkinga, and R. Paterson. Functional programming with bananas, lenses, envelopes and barbed wire. In J. Hughes, editor, Functional Programming Languages and Computer Architecture, volume 523 of Lecture Notes in Computer Science, pages 124--144. Springer-Verlag, 1991.

Digital Library

[37]

R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML. MIT Press, revised edition, 1997.

Digital Library

[38]

P. Norvig. Design patterns in dynamic programming. In Object World, Boston, MA, May 1996. Tutorial slides at http://norvig.com/design-patterns/.

[39]

B. C. d. S. Oliveira and J. Gibbons. TypeCase: A design pattern for type-indexed functions. In D. Leijen, editor, Haskell Workshop, 2005.

Digital Library

[40]

J. Palsberg and C. B. Jay. The essence of the Visitor pattern. In 22nd Annual International Computer Software and Applications Conference, pages 9--15, Vienna, Austria, August 1998.

Digital Library

[41]

L. C. Paulson. ML for the Working Programmer. Cambridge University Press, second edition, 1996.

Digital Library

[42]

S. Peyton Jones. The Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.

[43]

G. T. Sullivan. Advanced programming language features for executable design patterns: Better patterns through reflection. Artificial Intelligence Laboratory Memo AIM-2002-005, Artificial Intelligence Lab, MIT, Mar. 2002.

[44]

The Programatica Team. Programatica tools for certifiable, auditable development of high-assurance systems in Haskell. In High Confidence Software and Systems Conference. National Security Agency, April 2003.

[45]

P. Wadler. Theorems for free! In Functional Programming and Computer Architecture, 1989.

Digital Library

[46]

P. Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science, 73:231--248, 1990.

Digital Library

[47]

P. Wadler. Monads for functional programming. In M. Broy, editor, Program Design Calculi: Proceedings of the Marktoberdorf Summer School, 1992.

[48]

P. Wadler. The expression problem. Posting to java-genericity mailing list, 12th Nov 1998.

[49]

P. Wadler. How to solve the reuse problem? Functional programming. In Internal Conference on Software Reuse, pages 371--372. IEEE, 1998.

Digital Library

Cited By

Crichton WSperber MHutton G(2023)Typed Design Patterns for the Functional EraProceedings of the 1st ACM SIGPLAN International Workshop on Functional Software Architecture10.1145/3609025.3609477(40-48)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609025.3609477
Flageol WMenaud ÉGuéhéneuc YBadri MMonnier S(2023)A mapping study of language features improving object-oriented design patternsInformation and Software Technology10.1016/j.infsof.2023.107222160:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.infsof.2023.107222
Spanò ACortesi A(2020)Legodroid: A Type-Driven Library for Android and LEGO Mindstorms InteroperabilitySensors10.3390/s2007192620:7(1926)Online publication date: 30-Mar-2020
https://doi.org/10.3390/s20071926
Show More Cited By

Index Terms

Design patterns as higher-order datatype-generic programs
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures
        Polymorphism
        Recursion
      2. Language types
        Functional languages
        Object oriented languages
    2. System description languages
      1. Design languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Object oriented constructs

Recommendations

Parametric datatype-genericity
WGP '09: Proceedings of the 2009 ACM SIGPLAN workshop on Generic programming

Datatype-generic programs are programs that are parametrized by a datatype or type functor: whereas polymorphic programs abstract from the "integers" in "lists of integers",datatype-generic programs abstract from the "lists of". There are two main ...
Design patterns for functional strategic programming
RULE '02: Proceedings of the 2002 ACM SIGPLAN workshop on Rule-based programming

We believe that design patterns can be an effective means of consolidating and communicating program construction expertise for functional programming, just as they have proven to be in object-oriented programming. The emergence of combinator libraries ...
Intensional computation with higher-order functions
Abstract
Intensional computations are those that query the internal structure of their arguments. In a higher-order setting, such queries perform program analysis. This is beyond the expressive power of traditional term rewriting systems, such ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

September 2006

114 pages

ISBN:1595934928

DOI:10.1145/1159861

General Chair:
Ralf Hinze
Universität Bonn

Copyright © 2006 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: 16 September 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICFP06

Sponsor:

ICFP06: ACM SIGPLAN International Conference on Functional Programming

September 16, 2006

Oregon, Portland, USA

Acceptance Rates

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

26
Total Citations
View Citations
718
Total Downloads

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

Reflects downloads up to 24 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Crichton WSperber MHutton G(2023)Typed Design Patterns for the Functional EraProceedings of the 1st ACM SIGPLAN International Workshop on Functional Software Architecture10.1145/3609025.3609477(40-48)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609025.3609477
Flageol WMenaud ÉGuéhéneuc YBadri MMonnier S(2023)A mapping study of language features improving object-oriented design patternsInformation and Software Technology10.1016/j.infsof.2023.107222160:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.infsof.2023.107222
Spanò ACortesi A(2020)Legodroid: A Type-Driven Library for Android and LEGO Mindstorms InteroperabilitySensors10.3390/s2007192620:7(1926)Online publication date: 30-Mar-2020
https://doi.org/10.3390/s20071926
King P(2020)A history of the Groovy programming languageProceedings of the ACM on Programming Languages10.1145/33863264:HOPL(1-53)Online publication date: 12-Jun-2020
https://dl.acm.org/doi/10.1145/3386326
Spanò ACortesi AZausa G(2019)Type-Driven Cross-Programming for Android and LEGO Mindstorms InteroperabilityComputer Information Systems and Industrial Management10.1007/978-3-030-28957-7_17(191-209)Online publication date: 11-Aug-2019
https://doi.org/10.1007/978-3-030-28957-7_17
Miraldo VSerrano AEisenberg RVazou N(2018)Sums of products for mutually recursive datatypes: the appropriationist’s view on generic programmingProceedings of the 3rd ACM SIGPLAN International Workshop on Type-Driven Development10.1145/3240719.3241786(65-77)Online publication date: 27-Sep-2018
https://dl.acm.org/doi/10.1145/3240719.3241786
Karanikolas CDimitroulakos GMasselos K(2017)Early Evaluation of Implementation Alternatives of Composite Data Structures Toward MaintainabilityACM Transactions on Software Engineering and Methodology10.1145/313273126:2(1-44)Online publication date: 5-Oct-2017
https://dl.acm.org/doi/10.1145/3132731
Cai YGiarrusso POstermann K(2016)System f-omega with equirecursive types for datatype-generic programmingACM SIGPLAN Notices10.1145/2914770.283766051:1(30-43)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837660
Cai YGiarrusso POstermann KBodik RMajumdar R(2016)System f-omega with equirecursive types for datatype-generic programmingProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837660(30-43)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837660
Cruz-Filipe LGaspar GNunes I(2015)Design Patterns for Description-Logic ProgramsKnowledge Discovery, Knowledge Engineering and Knowledge Management10.1007/978-3-662-46549-3_13(199-214)Online publication date: 25-Apr-2015
https://doi.org/10.1007/978-3-662-46549-3_13
Show More Cited By

View Options

Get Access

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