The visitor pattern as a reusable, generic, type-safe component

ABSTRACT

The VISITOR design pattern shows how to separate the structure of an object hierarchy from the behaviour of traversals over that hierarchy. The pattern is very flexible; this very flexibility makes it difficult to capture the pattern as anything more formal than prose, pictures and prototypes.

We show how to capture the essence of the VISITOR pattern as a reusable software library, by using advanced type system features appearing in modern object-oriented languages such as Scala. We preserve type-safety statically and modularly: no reflection or similar mechanisms are used and modules can be independently compiled. The library is generic, in two senses: not only is it parametrised by both the return type and the shape of the object hierarchy, but also it allows a number of implementation choices (internal versus external control, imperative versus functional behaviour, orthogonal aspects such as tracing and memoisation) to be specified by parameters rather than fixed in early design decisions. Finally, we propose a generalised datatype-like notation,on top of our visitor library: this provides a convenient functional decomposition style in object-oriented languages.

REFERENCES

• 1: Jonathan Aldrich. Open modules: Modular reasoning about advice. In LNCS 3586: European Conference on Object-Oriented Programming, pages 144--168, 2005.
• 2: Karine Arnout. Pattern Componentization. PhD thesis, Swiss Institute of Technology, March 2004.
• 3: Richard S. Bird , Lambert G. L. T. Meertens, Nested Datatypes, Proceedings of the Mathematics of Program Construction, p.52-67, June 15-17, 1998
• 4: Richard Bird , Oege de Moor, Algebra of programming, Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 5: Corrado Bohm and Alesssandro Berarducci. Automatic synthesis of typed lambda-programs on term algebras. Theoretical Computer Science, 39(2-3):135--153, August 1985.
• 6: Peter Buchlovsky and Hayo Thielecke. A type-theoretic reconstruction of the Visitor pattern. Electronic Notes in Theoretical Computer Science, 155, 2005. Mathematical Foundations of Programming Semantics.
• 7: Bryan Chadwick and Karl Lieberherr. Functional Adaptive Programming with DemeterF. Technical Report NU-CCIS-08-March19, Northeastern University, Boston, March 2008.
• 8: Bryan Chadwick, Therapon Skotiniotis, and Karl Lieberherr. Functional Visitors Revisited. Technical Report NU-CCIS-06-03, Northeastern University, Boston, May 2006.
• 9: Craig Chambers , Gary T. Leavens, Typechecking and modules for multimethods, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.6, p.805-843, Nov. 1995 [doi>10.1145/218570.218571]
• 10: Alonzo Church. An unsolvable problem of elementary number theory. American Journal of Mathematics, 58:345--363, 1936.
• 11: Curtis Clifton , Gary T. Leavens , Craig Chambers , Todd Millstein, MultiJava: modular open classes and symmetric multiple dispatch for Java, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.130-145, October 2000, Minneapolis, Minnesota, United States
• 12: Vincent Cremet and Philippe Altherr. Adding type constructor parameterization to Java. Journal of Object Technology, 7(5):25--65, June 2008. Special issue on ECOOP 2007 Workshop on Formal Techniques for Java-like Programs.
• 13: Antonio Cunei , Jan Vitek, PolyD: a flexible dispatching framework, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 14: Michael Ernst , Craig Kaplan , Craig Chambers, Predicate Dispatching: A Unified Theory of Dispatch, Proceedings of the 12th European Conference on Object-Oriented Programming, p.186-211, July 20-24, 1998
• 15: Rémi Forax , Etienne Duris , Gilles Roussel, Reflection-based implementation of Java extensions: the double-dispatch use-case, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066996]
• 16: 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
• 17: Jeremy Gibbons. Patterns in datatype-generic programming. In J. Striegnitz, editor, Declarative Programming in the Context of Object-Oriented Languages, Uppsala, 2003.
• 18: 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]
• 19: Jeremy Gibbons and Bruno Oliveira. The essence of the Iterator pattern. Journal of Functional Programming, 2008.
• 20: Jean-Yves Girard , Paul Taylor , Yves Lafont, Proofs and types, Cambridge University Press, New York, NY, 1989
• 21: Christian Grothoff. Walkabout revisited: The Runabout. In LNCS 2743: European Conference on Object-Oriented Programming, pages 103--125, 2003.
• 22: Stephan Gudmundson and Gregor Kiczales. Addressing practical software development issues in AspectJ with a pointcut interface. In ECOOP 2001 Workshop on Advanced Separation of Concerns, 2001.
• 23: Jan Hannemann , Gregor Kiczales, Design pattern implementation in Java and aspectJ, ACM SIGPLAN Notices, v.37 n.11, November 2002
• 24: 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]
• 25: Gregor Kiczales , Mira Mezini, Aspect-oriented programming and modular reasoning, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062482]
• 26: Gregor Kiczales, John Lamping, Anurag Menhdhekar, Chris Maeda, Cristina Lopes, Jean-Marc Loingtier, and John Irwin. Aspect-oriented programming. In Mehmet Aks 'it and Satoshi Matsuoka, editors, LNCS 1241: European Conference on Object-Oriented Programming, pages 220--242, 1997.
• 27: 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]
• 28: Doug McIlroy. Mass produced software components. In Naur and Randell (1969), pages 138--155.
• 29: Lambert Meertens. Paramorphisms. Formal Aspects of Computing, 4(5):413--425, 1992.
• 30: Erik Meijer , Graham Hutton, Bananas in space: extending fold and unfold to exponential types, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.324-333, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224225]
• 31: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 32: Bertrand Meyer , Karine Arnout, Componentization: The Visitor Example, Computer, v.39 n.7, p.23-30, July 2006 [doi>10.1109/MC.2006.227]
• 33: Donald Michie. Memo functions and machine learning. Nature, 218:19--22, 1968.
• 34: Adriaan Moors, Frank Piessens, and Martin Odersky. Towards equal rights for higher-kinded types. In 6th International Workshop on Multiparadigm Programming with Object-Oriented Languages, 2007.
• 35: Peter Naur and Brian Randell, editors. Software Engineering: Report of a Conference Sponsored by the NATO Science Committee, Garmisch, Germany, 7-11 Oct. 1968. 1969.
• 36: Peter Norvig. Design patterns in dynamic programming. In Object World 96, May 1996.
• 37: Martin Odersky. An Overview of the Scala programming language (second edition). Technical Report IC/2006/001, EPFL Lausanne, Switzerland, 2006.
• 38: Martin Odersky and Matthias Zenger. Independently extensible solutions to the expression problem. In Proceedings of Foundations of Object-Oriented Languages 12, January 2005a. http://homepages.inf.ed.ac.uk/wadler/fool.
• 39: 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
• 40: Bruno C.d.S. Oliveira. Genericity, Extensibility and Type-Safety in the Visitor Pattern. PhD thesis, University of Oxford, 2007.
• 41: Doug Orleans , Karl J. Lieberherr, DJ: Dynamic Adaptive Programming in Java, Proceedings of the Third International Conference on Metalevel Architectures and Separation of Crosscutting Concerns, p.73-80, September 25-28, 2001
• 42: 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
• 43: Michel Parigot, Recursive programming with proofs, Theoretical Computer Science, v.94 n.2, p.335-356, March 9, 1992 [doi>10.1016/0304-3975(92)90042-E]
• 44: Simon Peyton Jones, editor. Haskell 98 Language and Libraries - The Revised Report. Cambridge University Press, Cambridge, England, 2003.
• 45: Cuno Pfister , Clemens Szyperski, Why objects are not enough, Proceedings of the first component user's conference on Component-based software engineering, p.141-147, July 1998, Munich, Germany
• 46: Zdzisław Spławski , Paweł Urzyczyn, Type fixpoints: iteration vs. recursion, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.102-113, September 27-29, 1999, Paris, France
• 47: Clemens Szyperski. Independently extensible systems - software engineering potential and challenges. In 19th Australian Computer Science Conference, 1996.
• 48: Peri Tarr , Harold Ossher , William Harrison , Stanley M. Sutton, Jr., N degrees of separation: multi-dimensional separation of concerns, Proceedings of the 21st international conference on Software engineering, p.107-119, May 16-22, 1999, Los Angeles, California, United States [doi>10.1145/302405.302457]
• 49: Thomas VanDrunen and Jens Palsberg. Visitor-oriented programming. In Proceedings of FOOL-11, the 11th ACM SIGPLAN International Workshop on Foundations of Object-Oriented Languages, New York, NY, USA, January 2004. ACM Press.
• 50: Joost Visser, Visitor combination and traversal control, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.270-282, October 14-18, 2001, Tampa Bay, FL, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reusable libraries

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages; Multiparadigm languages; Applicative (functional) languages

General Terms:
Design, Languages

Keywords:
algebraic datatypes, design patterns, program extensibility, software components, traversal, visitor pattern