The pattern calculus
Tóm tắt
There is a significant class of operations such as mapping that are common to all data structures. The goal of generic programming is to support these operations on arbitrary data types without having to recode for each new type. The pattern calculus and combinatory type system reach this goal by representing each data structure as a combination of names and a finite set of constructors. These can be used to define generic functions by pattern-matching programs in which each pattern has a different type. Evaluation is type-free. Polymorphism is captured by quantifying over type variables that represent unknown structures. A practical type inference algorithm is provided.
Từ khóa
Tài liệu tham khảo
Abadi , M. , Cardelli , L. , Pierce , B. , and Rémy , D. 1995 . Dynamic typing in polymorphic languages . J. Funct. Programm. 5 , 1, 111 -- 130 . Abadi, M., Cardelli, L., Pierce, B., and Rémy, D. 1995. Dynamic typing in polymorphic languages. J. Funct. Programm. 5, 1, 111--130.
Backhouse , R. and Sheard , T. , Eds . 1998 . Workshop on Generic Programming: Marstrand, Sweden, 18th June , 1998 . Chalmers University of Technology. Backhouse, R. and Sheard, T., Eds. 1998. Workshop on Generic Programming: Marstrand, Sweden, 18th June, 1998. Chalmers University of Technology.
Barr M. and Wells C. 1990. Category Theory for Computing Science. International Series in Computer Science. Prentice Hall Englewood Cliffs NJ. Barr M. and Wells C. 1990. Category Theory for Computing Science. International Series in Computer Science. Prentice Hall Englewood Cliffs NJ.
Bird , R. and Meertens , L . 1998. Nested datatypes . In Proceedings of the 4th International Conference on Mathematics of Program Construction (MPC'98 , Marstrand, Sweden, 15--17 June) J. Jeuring, Ed. Lecture Notes in Computer Science , vol. 1422 . Springer-Verlag, Berlin, Germany, 52--67. Bird, R. and Meertens, L. 1998. Nested datatypes. In Proceedings of the 4th International Conference on Mathematics of Program Construction (MPC'98, Marstrand, Sweden, 15--17 June) J. Jeuring, Ed. Lecture Notes in Computer Science, vol. 1422. Springer-Verlag, Berlin, Germany, 52--67.
Caml. 1997. Objective Caml. Available online at http://pauillac.inria.fr/ocaml. Caml. 1997. Objective Caml. Available online at http://pauillac.inria.fr/ocaml.
Cockett J. and Fukushima T. 1992. About charity. Tech. rep. 92/480/18 University of Calgary Calgary Alta. Canada. Cockett J. and Fukushima T. 1992. About charity. Tech. rep. 92/480/18 University of Calgary Calgary Alta. Canada.
Forest , J. 2002 . A weak calculus with explicit operators for pattern matching and substitution. In Rewriting Techniques and Applications , 13th International Conference, RTA 2002, Copenhagen, Denmark, July 22--24, 2002, Proceedings, S. Tison, Ed. Vol. 2378 . Springer, Berlin, Germany, 174--191. Forest, J. 2002. A weak calculus with explicit operators for pattern matching and substitution. In Rewriting Techniques and Applications, 13th International Conference, RTA 2002, Copenhagen, Denmark, July 22--24, 2002, Proceedings, S. Tison, Ed. Vol. 2378. Springer, Berlin, Germany, 174--191.
Forest , J. and Kesner , D . 2003. Expression reduction systems with patterns . In 14th International Conference on Rewriting Techniques and Applications, R. Nieuwenhuis, Ed. Lecture Notes in Computer Science , vol. 2706 . Springer Verlag Berlin, Germany. Forest, J. and Kesner, D. 2003. Expression reduction systems with patterns. In 14th International Conference on Rewriting Techniques and Applications, R. Nieuwenhuis, Ed. Lecture Notes in Computer Science, vol. 2706. Springer Verlag Berlin, Germany.
Gibbons , J. and Jeuring , J. , Eds . 2003 . Generic Programming : IFIP TC2/WG2.1 Working Conference on Generic Programming July 11--12, 2002, Dagstuhl, Germany. Kluwer Academic Publishers , Dordrecht, The Netherlands. Gibbons, J. and Jeuring, J., Eds. 2003. Generic Programming: IFIP TC2/WG2.1 Working Conference on Generic Programming July 11--12, 2002, Dagstuhl, Germany. Kluwer Academic Publishers, Dordrecht, The Netherlands.
Girard J.-Y. Lafont Y. and Taylor P. 1989. Proofs and Types. Tracts in Theoretical Computer Science. Cambridge University Press Cambridge U.K. Girard J.-Y. Lafont Y. and Taylor P. 1989. Proofs and Types. Tracts in Theoretical Computer Science. Cambridge University Press Cambridge U.K.
Hammond K. and Michaelson G. E. 1999. Research Directions in Parallel Functional Programming. Springer Berlin Germany. Hammond K. and Michaelson G. E. 1999. Research Directions in Parallel Functional Programming. Springer Berlin Germany.
Haskell. 2002. Haskell. Available online at http://www.haskell.org/. Haskell. 2002. Haskell. Available online at http://www.haskell.org/.
Hindley R. and Seldin J. 1986. Introduction to Combinators and Lambda-Calculus. Cambridge University Press Cambridge U.K. Hindley R. and Seldin J. 1986. Introduction to Combinators and Lambda-Calculus. Cambridge University Press Cambridge U.K.
Hinze , R. 2000 . A new approach to generic functional programming . In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press , New York, NY, 119--132. 10.1145/325694.325709 Hinze, R. 2000. A new approach to generic functional programming. In Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York, NY, 119--132. 10.1145/325694.325709
Hinze , R. 2002 . Polytypic values possess polykinded types. Sci . Comput. Programm. 43 , 129 -- 159 . Hinze, R. 2002. Polytypic values possess polykinded types. Sci. Comput. Programm. 43, 129--159.
Jansson , P. and Jeuring , J . 1997. PolyP---a polytypic programming language extension . In Proceedings of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press , New York, NY, 470--482. 10.1145/263699.263763 Jansson, P. and Jeuring, J. 1997. PolyP---a polytypic programming language extension. In Proceedings of POPL '97: The 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM Press, New York, NY, 470--482. 10.1145/263699.263763
Jay , C. 2001 . Distinguishing data structures and functions: The constructor calculus and functorial types . In Typed Lambda Calculi and Applications: 5th International Conference TLCA 2001, Kraków, Poland, May 2001 Proceedings, S. Abramsky, Ed. Lecture Notes in Computer Science , vol. 2044 . Springer, Berlin, Germany, 217--239. Jay, C. 2001. Distinguishing data structures and functions: The constructor calculus and functorial types. In Typed Lambda Calculi and Applications: 5th International Conference TLCA 2001, Kraków, Poland, May 2001 Proceedings, S. Abramsky, Ed. Lecture Notes in Computer Science, vol. 2044. Springer, Berlin, Germany, 217--239.
Jay , C. and Cockett , J . 1994. Shapely types and shape polymorphism . In Programming Languages and Systems---ESOP '94: 5th European Symposium on Programming, Edinburgh, U.K., April 1994, Proceedings, D. Sannella, Ed. Lecture Notes in Computer Science , vol. 788 . Springer-Verlag, Berlin, Germany, 302--316. Jay, C. and Cockett, J. 1994. Shapely types and shape polymorphism. In Programming Languages and Systems---ESOP '94: 5th European Symposium on Programming, Edinburgh, U.K., April 1994, Proceedings, D. Sannella, Ed. Lecture Notes in Computer Science, vol. 788. Springer-Verlag, Berlin, Germany, 302--316.
Jeuring , J., Ed. 2000 . Proceedings: Workshop on Generic Programming (WGP 2000) : July 6, 2000, Ponte de Lima, Portugal. Publication, UU-CS- 2000-19, Utrecht University, Utrecht, The Netherlands. Jeuring, J., Ed. 2000. Proceedings: Workshop on Generic Programming (WGP 2000): July 6, 2000, Ponte de Lima, Portugal. Publication, UU-CS-2000-19, Utrecht University, Utrecht, The Netherlands.
Meijer , E. , Fokkinga , M. , and Paterson , R . 1991. Functional programming with bananas, lenses, envelopes and barbed wire . In Procceding of the 5th ACM Conference on Functional Programming and Computer Architecture, J. Hughes, Ed. Lecture Notes in Computer Science , vol. 523 . Springer Verlag, Berlin, Germany, 124--44. Meijer, E., Fokkinga, M., and Paterson, R. 1991. Functional programming with bananas, lenses, envelopes and barbed wire. In Procceding of the 5th ACM Conference on Functional Programming and Computer Architecture, J. Hughes, Ed. Lecture Notes in Computer Science, vol. 523. Springer Verlag, Berlin, Germany, 124--44.
Milner , R. 1978 . A theory of type polymorphism in programming . J. Comput. Syst. Sci. 17 , 3, 348 -- 375 . Milner, R. 1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 3, 348--375.
Milner R. and Tofte M. 1991. Commentary on Standard ML. MIT Press Cambridge MA. Milner R. and Tofte M. 1991. Commentary on Standard ML. MIT Press Cambridge MA.