Good advice for type-directed programming aspect-oriented programming and extensible generic functions

ABSTRACT

Type-directed programming is an important idiom for software design. In type-directed programming the behavior of programs is guided by the type structure of data. It makes it possible to implement many sorts of operations, such as serialization,traversals, and queries,only once and without needing to continually revise their implementations as new data types are defined.Type-directed programming is the basis for recent research into "scrapping" tedious boilerplate code that arises in functional programming with algebraic data types. This research has primarily focused on writing type-directed functions that are closed to extension. However, Lämmel and Peyton Jones recently developed a technique for writing openly extensible type-directed functions in Haskell by making clever use of type classes. Unfortunately, this technique has a number of limitations such as the inability to write specialized cases for existential or nested data types and function types becoming too constrained to be used as first-class functions.We present an alternate approach to writing openly extensible type-directed functions by using the aspect-oriented programming features provided by the language AspectML. Our solution not only avoids the limitations present in Lämmel and Peyton Jones's technique, but also allows type-directed functions to be extended at any time with cases for types that were not even known at compiletime. This capability is critical to writing programs that make use of dynamic loading or runtime type generativity.

REFERENCES

• 1: Martín Abadi , Luca Cardelli , Benjamin Pierce , Gordon Plotkin, Dynamic typing in a statically typed language, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.237-268, April 1991 [doi>10.1145/103135.103138]
• 2: P. Achten and R. Hinze. Combining generics and dynamics. Technical Report NIII-R0206, Nijmegen Institute for Computing and Information, July 2002.
• 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: 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]
• 5: D.S. Dantas, D. Walker, G. Washburn, and S. Weirich. AspectML: A polymorphic aspect-oriented functional programmming language (extended version). ACM Trans. Programming Languages and Systems. To appear pending revisions.Draft available at http://www.cis.upenn.edu/~geoffw/research/papers/aspect-toplas.pdf
• 6: 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
• 7: R. Hinze and A. Löh. "Scrap your boilerplate" revolutions. In Proceedings of 8th Int. Conf. on Mathematics of Program Construction (MPC), 2006.
• 8: R. Hinze, A. Löh, and B.C. Oliveira. "Scrap your boilerplate" reloaded. In Proceedings of the 8th Int. Symp. on Functional and Logic Programming (FLOPS), pages 13--29, Fuji Susono,Japan,Apr.2006.
• 9: Robert Hirschfeld, AspectS - Aspect-Oriented Programming with Squeak, Revised Papers from the International Conference NetObjectDays on Objects, Components, Architectures, Services, and Applications for a Networked World, p.216-232, October 07-10, 2002
• 10: Radha Jagadeesan , Alan Jeffrey , James Riely, Typed parametric polymorphism for aspects, Science of Computer Programming, v.63 n.3, p.267-296, 15 December 2006 [doi>10.1016/j.scico.2006.02.008]
• 11: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 12: Ralf Lämmel , Simon Peyton Jones, Scrap your boilerplate: a practical design pattern for generic programming, ACM SIGPLAN Notices, v.38 n.3, March 2003
• 13: Ralf Lämmel , Simon Peyton Jones, Scrap more boilerplate: reflection, zips, and generalised casts, Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, September 19-21, 2004, Snow Bird, UT, 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: K. Läufer and M. Odersky. An extension of ML with first-class abstract types. In Proceedings of the SIGPLAN Workshop on ML and its Applications, pages 78--91,June 1992.
• 16: X. Leroy, D. Doligez, J. Garrigue, D. Rémy, and J. Vouillon. The Objective Caml System:Documentation and user's manual,2000. Available from http://caml.inria.fr
• 17: Martin Lippert, AJEER: an aspectJ-enabled eclipse runtime, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028678]
• 18: Andres Löh , Dave Clarke , Johan Jeuring, Dependency-style generic haskell, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.141-152, August 25-29, 2003, Uppsala, Sweden
• 19: Hidehiko Masuhara , Hideaki Tatsuzawa , Akinori Yonezawa, Aspectual Caml: an aspect-oriented functional language, Proceedings of the tenth ACM SIGPLAN international conference on Functional programming, September 26-28, 2005, Tallinn, Estonia
• 20: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 21: Chris Okasaki, From fast exponentiation to square matrices: an adventure in types, Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.28-35, September 27-29, 1999, Paris, France
• 22: Jens Palsberg , Cun Xiao , Karl Lieberherr, Efficient implementation of adaptive software, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.264-292, March 1995 [doi>10.1145/201059.201066]
• 23: S. Peyton Jones.Haskell 98 Language and Libraries:The Revised Report. Cambridge University Press,2003.
• 24: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Mark Shields, Practical type inference for arbitrary-rank types, Journal of Functional Programming, v.17 n.1, p.1-82, January 2007 [doi>10.1017/S0956796806006034]
• 25: Simon Peyton Jones , Dimitrios Vytiniotis , Stephanie Weirich , Geoffrey Washburn, Simple unification-based type inference for GADTs, Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming, September 16-21, 2006, Portland, Oregon, USA
• 26: G.D. Plotkin.A note on inductive generalization. In Machine Intelligence ,volume 5,pages 153--163.Edinburgh University Press, 1970.
• 27: J.C. Reynolds. Types, abstraction, and parametric polymorphism. Information processing ,pages 513--523,1983.
• 28: Linda M. Seiter , Jens Palsberg , Karl J. Lieberherr, Evolution of object behavior using context relations, ACM SIGSOFT Software Engineering Notes, v.21 n.6, p.46-57, Nov. 1996
• 29: Martin Sulzmann , Meng Wang, Modular generic programming with extensible superclasses, Proceedings of the 2006 ACM SIGPLAN workshop on Generic programming, September 16-16, 2006, Portland, Oregon, USA [doi>10.1145/1159861.1159869]
• 30: Valery Trifonov , Bratin Saha , Zhong Shao, Fully reflexive intensional type analysis, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.82-93, September 2000
• 31: Dimitrios Vytiniotis , Geoffrey Washburn , Stephanie Weirich, An open and shut typecase, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.13-24, January 10-10, 2005, Long Beach, California, USA [doi>10.1145/1040294.1040296]
• 32: David Walker , Steve Zdancewic , Jay Ligatti, A theory of aspects, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.127-139, August 25-29, 2003, Uppsala, Sweden
• 33: M. Wang,K.Chen,and S.-C.Khoo. On the pursuit of staticness and coherence. In Proceedings of the 5th Workshop on Foundations of Aspect-Oriented Languages (FOAL), Mar. 2006.
• 34: Geoffrey Washburn, Generalizing Parametricity Using Information-flow, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), p.62-71, June 26-29, 2005 [doi>10.1109/LICS.2005.20]
• 35: Stephanie Weirich, Higher-Order Intensional Type Analysis, Proceedings of the 11th European Symposium on Programming Languages and Systems, p.98-114, April 08-12, 2002
• 36: Stephanie Weirich, RepLib: a library for derivable type classes, Proceedings of the 2006 ACM SIGPLAN workshop on Haskell, September 17-17, 2006, Portland, Oregon, USA [doi>10.1145/1159842.1159844]
• 37: Stephanie Weirich, Type-safe run-time polytypic programming, Journal of Functional Programming, v.16 n.6, p.681-710, November 2006 [doi>10.1017/S0956796806005879]
• 38: S. Weirich and L. Huang. A design for type-directed Java. In V. Bono, editor,Workshop on Object-Oriented Developments (WOOD), ENTCS, Aug. 2004. 20 pages.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns; Polymorphism

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives; Type structure; Program and recursion schemes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Lambda calculus and related systems

General Terms:
Design, Languages, Theory

Keywords:
aspect-oriented programming, expression problem, generic programming, open extension, type analysis, type-directed programming