Design patterns as higher-order datatype-generic programs

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: Richard Bird, Introduction to Functional Programming, Pearson Education, 1998
• 5: Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 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: 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]
• 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: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 12: Ronald Garcia , Jaakko Jarvi , Andrew Lumsdaine , Jeremy G. Siek , Jeremiah Willcock, A comparative study of language support for generic programming, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 13: Jeremy Gibbons, Calculating functional programs, Algebraic and coalgebraic methods in the mathematics of program construction, Springer-Verlag New York, Inc., New York, NY, 2002
• 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.
• 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.
• 20: J. Gibbons and O. de Moor, editors. The Fun of Programming. Cornerstones in Computing. Palgrave, 2003. ISBN 1-4039-0772-2.
• 21: Jeremy Gibbons , Geraint Jones, The under-appreciated unfold, Proceedings of the third ACM SIGPLAN international conference on Functional programming, p.273-279, September 26-29, 1998, Baltimore, Maryland, United States
• 22: Andrew Gill , John Launchbury , Simon L. Peyton Jones, A short cut to deforestation, Proceedings of the conference on Functional programming languages and computer architecture, p.223-232, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165214]
• 23: Ralf Hinze, Polytypic Values Possess Polykinded Types, Proceedings of the 5th International Conference on Mathematics of Program Construction, p.2-27, July 03-05, 2000
• 24: Ralf Hinze, Generics for the masses, Journal of Functional Programming, v.16 n.4-5, p.451-483, July 2006 [doi>10.1017/S0956796806006022]
• 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, The Computer Journal, v.32 n.2, p.98-107, April 1989 [doi>10.1093/comjnl/32.2.98]
• 28: Graham Hutton, A tutorial on the universality and expressiveness of fold, Journal of Functional Programming, v.9 n.4, p.355-372, July 1999 [doi>10.1017/S0956796899003500]
• 29: 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]
• 30: 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]
• 31: C. Barry Jay, A semantics for shape, Science of Computer Programming, v.25 n.2-3, p.251-283, Dec. 1995
• 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, v.14 n.2-3, p.255-279, Oct. 1990 [doi>10.1016/0167-6423(90)90023-7]
• 35: C. McBride and R. Paterson. Applicative programming with effects. Journal of Functional Programming, To appear.
• 36: 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
• 37: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 38: P. Norvig. Design patterns in dynamic programming. In Object World, Boston, MA, May 1996. Tutorial slides at http://norvig.com/design-patterns/.
• 39: Bruno C. d. S. Oliveira , Jeremy Gibbons, TypeCase: a design pattern for type-indexed functions, Proceedings of the 2005 ACM SIGPLAN workshop on Haskell, p.98-109, September 30-30, 2005, Tallinn, Estonia [doi>10.1145/1088348.1088358]
• 40: Jens Palsberg , C. Barry Jay, The Essence of the Visitor Pattern, Proceedings of the 22nd International Computer Software and Applications Conference, p.9-15, August 19-21, 1998
• 41: Lawrence C. Paulson, ML for the working programmer (2nd ed.), Cambridge University Press, New York, NY, 1996
• 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: 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]
• 46: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990
• 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, Proceedings of the 5th International Conference on Software Reuse, p.371, June 02-05, 1998

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Object-oriented constructs

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages; Applicative (functional) languages; Design languages
      D.3.3 Language Constructs and Features
          Subjects: Control structures; Polymorphism; Recursion

General Terms:
Algorithms, Design, Languages, Theory

Keywords:
design patterns, folds, functional programming, generic programming, higher-order functions, unfolds