Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-11T09:12:12.310Z Has data issue: false hasContentIssue false
  • English
  • Français

Bunched polymorphism

Published online by Cambridge University Press:  01 December 2008

MATTHEW COLLINSON ,
DAVID PYM  and
EDMUND ROBINSON
MATTHEW COLLINSON
Affiliation:
Hewlett-Packard Laboratories, Bristol, BS34 8QZ, United Kingdom Email: [email protected]
DAVID PYM
Affiliation:
Hewlett-Packard Laboratories, Bristol, BS34 8QZ, United Kingdom Email: [email protected]
EDMUND ROBINSON
Affiliation:
Queen Mary, University of London, E1 4NS, United Kingdom
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe a polymorphic, typed lambda calculus with substructural features. This calculus extends the first-order substructural lambda calculus αλ associated with bunched logic. A particular novelty of our new calculus is the substructural treatment of second-order variables. This is accomplished through the use of bunches of type variables in typing contexts. Both additive and multiplicative forms of polymorphic abstraction are then supported. The calculus has sensible proof-theoretic properties and a straightforward categorical semantics using indexed categories. We produce a model for additive polymorphism with first-order bunching based on partial equivalence relations. We consider additive and multiplicative existential quantifiers separately from the universal quantifiers.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 18 , Issue 6 , December 2008 , pp. 1091 - 1132
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abadi, M. and Plotkin, G. D. (1990) A per model of polymorphism and recursive types. In: Logic in Computer Science, LICS '90, IEEE Press 31–46.Google Scholar
Atkey, R. (2004) A λ-Calculus for Resource Separation. In: Automata, Languages and Programming: 31st International Colloquium, ICALP 2004. Springer-Verlag Lecture Notes in Computer Science 3142 158–170.CrossRefGoogle Scholar
Berdine, J. and Oxs'Hearn, P. (2006) Strong update, disposal and encapsulation in bunched typing. In: Mathematical Foundations of Programming Semantics, MFPS '06. Electronic Notes in Theoretical Computer Science 158.CrossRefGoogle Scholar
Biering, B., Birkedal, L. and Torp-Smith, N. (2007) BI-hyperdoctrines, higher-order separation logic, and abstraction. To appear in ACM Transactions on Programming Languages and Systems. (An earlier version appeared in 2005 in Proceedings of European Symposium on Programming (ESOP'05) 233–247.)CrossRefGoogle Scholar
Bierman, G. M., Pitts, A. M. and Russo, C. V. (2000) Operational Properties of Lily, a Polymorphic Linear Lambda Calculus with Recursion. In: Proceedings, Fourth International Workshop on Higher Order Operational Techniques in Semantics (HOOTS 2000). Electronic Notes in Theoretical Computer Science 41 70–88.CrossRefGoogle Scholar
Birkedal, L., Møgelberg, R. E. and Petersen, R. L. (2006) Linear Abadi & Plotkin logic. Logical Methods in Computer Science 5 (2)1–48.Google Scholar
Birkedal, L. and Yang, H. (2007) Relational parametricity and separation logic. To appear in Logical Methods in Computer Science.CrossRefGoogle Scholar
Cardelli, L. and Longo, G. (1990) A semantic basis for quest. Technical Report 55, Systems Research Center, Digital Equipment Corporation.CrossRefGoogle Scholar
Collinson, M. and Pym, D. (2006) Bunching for regions and locations. In: Mathematical Foundations of Programming Semantics, MFPS '06. Electronic Notes in Theoretical Computer Science 158 171–197.CrossRefGoogle Scholar
Collinson, M., Pym, D. and Robinson, E. (2005) On Bunched Polymorphism (Extended Abstract). In: Computer Science Logic, CSL '05. Springer-Verlag Lecture Notes in Computer Science 3634 36–50.CrossRefGoogle Scholar
Day, B. J. (1970) On closed categories of functors. In: Proceedings of the Midwest Category Seminar. Springer-Verlag Lecture Notes in Mathematics 137.CrossRefGoogle Scholar
Day, B. J. (1973) An embedding theorem for closed categories. In: Proceedings of the Sydney Category Seminar 1972/73. Springer-Verlag Lecture Notes in Mathematics 420.Google Scholar
Gabbay, M. J. and Pitts, A. M. (2002) A new approach to abstract syntax with variable binding. Formal Aspects of Computing 13 341–363.CrossRefGoogle Scholar
Girard, J.-Y. (1971) Une extension de l'interprétation de Gödel à l'analyse et son application à l'élimination des coupres dans l'analyse et la théorie des types. In: Fenstad, J. E. (ed.) Proceedings of the 2nd Scandinavian Logic Symposium, North-Holland63–92.CrossRefGoogle Scholar
Girard, J.-Y. (1972) Interprétation fonctionelle et élimination des coupures dans l'arithmétique d'ordre supérieur, Ph.D. thesis, Université Paris VII.Google Scholar
Girard, J.-Y. (1987) Linear logic. Theoretical Computer Science 50 (1)1–102.CrossRefGoogle Scholar
Girard, J-Y., Lafont, Y. and Taylor, P. (1989) Proofs and Types, Cambridge University Press.Google Scholar
Hyland, J. M. E. (1988) A small complete category. Annals of Pure and Applied Logic 40 135–165.CrossRefGoogle Scholar
Jacobs, B. (1999) Categorical Logic and Type Theory. Studies in Logic and the Foundations of Mathematics 141, Elsevier.Google Scholar
Lawvere, F. W. (1969) Adjointness in foundations. Dialectica 23 281–296.CrossRefGoogle Scholar
Mac Lane, S. (1971) Categories for the Working Mathematician, Springer. (Second edition 1998.)CrossRefGoogle Scholar
Mac Lane, S. and Moerdijk, I. (1992) Sheaves in Geometry and Logic: A First Introduction to Topos Theory, Springer.Google Scholar
MacQueen, D. B., Plotkin, G. and Sethi, R. (1986) An ideal model for recursive polymorphic types. Information and Control 71 95–130.CrossRefGoogle Scholar
Maneggia, P. (2004) Models of linear polymorphism, Ph.D. thesis, School of Computer Science, The University of Birmingham.Google Scholar
Mitchell, J. C. and Moggi, E. (1991) Kripke style models for typed lambda calculus. Ann. Pure and Appl. Logic 51 (1)99–124.CrossRefGoogle Scholar
Mitchell, J. C. and Plotkin, G. D. (1988) Abstract types have existential type. ACM Transactions on Programming Languages and Systems 10 470–502.CrossRefGoogle Scholar
O'Hearn, P. (2003) On bunched typing. Journal of Functional Programming 13 747–796.CrossRefGoogle Scholar
O'Hearn, P. and Pym, D. (1999) The logic of bunched implications. Bulletin of Symbolic Logic 5 (2)215–244.CrossRefGoogle Scholar
Oles, F. J. (1982) A Category-Theoretic Approach to the Semantics of Programming Languages, Ph.D. thesis, Syracuse University, Syracuse, U.S.A.Google Scholar
Pierce, B. C. (2002) Types and Programming Languages, M.I.T. Press.Google Scholar
Plotkin, G. D. (1993) Type theory and recursion. In: Logic in Computer Science, LICS '93, IEEE Press 374.Google Scholar
Prawitz, D. (1978) Proofs and the meaning and completeness of logical constants. In: Hintikka, J., Niiniluoto, I. and Saarinen, E. (eds.) Essays on mathematical and philosophical logic, D. Reidel 25–40.Google Scholar
Pym, D., O'Hearn, P. and Yang, H. (2004) Possible worlds and resources: The semantics of BI. Theoretical Computer Science 315 (1)257–305.CrossRefGoogle Scholar
Pym, D. J. (2002) The Semantics and Proof Theory of the Logic of Bunched Implications. Applied Logic Series 26, Kluwer Academic Publishers. (Errata at: http://www.cs.bath.ac.uk/pym/BI-monograph-errata.pdf)Google Scholar
Reynolds, J. C. (1974) Towards a theory of type structure. In: Programming Symposium. Springer-Verlag Lecture Notes in Computer Science 19 408–425.CrossRefGoogle Scholar
Reynolds, J. C. (1981) The essence of algol. In: de Bakker, J. W. and van Vliet, J. C. (eds.) Algorithmic Languages, North-Holland345–372.Google Scholar
Reynolds, J. C. (2002) Separation logic: a logic for shared mutable data structures. In: Logic in Computer Science, LICS '02, IEEE Press 55–74.Google Scholar
Seely, R. A. G. (1987) Categorical semantics for higher order polymorphic lambda calculus. Journal of Symbolic Logic 52 969–989.CrossRefGoogle Scholar
Tofte, M. (1998) A brief introduction to regions. In: International Symposium on Memory Management '88, ACM Press 186–195.CrossRefGoogle Scholar