Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-23T23:01:24.376Z Has data issue: false hasContentIssue false
  • English
  • Français

Non-parametric parametricity

Part of: JFP Research Articles

Published online by Cambridge University Press:  07 September 2011

GEORG NEIS ,
DEREK DREYER  and
ANDREAS ROSSBERG
GEORG NEIS
Affiliation:
Max Planck Institute for Software Systems (MPI-SWS), Campus E1.4, 66123 Saarbrücken, Germany (e-mails: [email protected], [email protected], [email protected])
DEREK DREYER
Affiliation:
Max Planck Institute for Software Systems (MPI-SWS), Campus E1.4, 66123 Saarbrücken, Germany (e-mails: [email protected], [email protected], [email protected])
ANDREAS ROSSBERG
Affiliation:
Max Planck Institute for Software Systems (MPI-SWS), Campus E1.4, 66123 Saarbrücken, Germany (e-mails: [email protected], [email protected], [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Type abstraction and intensional type analysis are features seemingly at odds—type abstraction is intended to guarantee parametricity and representation independence, while type analysis is inherently non-parametric. Recently, however, several researchers have proposed and implemented “dynamic type generation” as a way to reconcile these features. The idea is that, when one defines an abstract type, one should also be able to generate at runtime a fresh type name, which may be used as a dynamic representative of the abstract type for purposes of type analysis. The question remains: in a language with non-parametric polymorphism, does dynamic type generation provide us with the same kinds of abstraction guarantees that we get from parametric polymorphism?

Our goal is to provide a rigorous answer to this question. We define a step-indexed Kripke logical relation for a language with both non-parametric polymorphism (in the form of type-safe cast) and dynamic type generation. Our logical relation enables us to establish parametricity and representation independence results, even in a non-parametric setting, by attaching arbitrary relational interpretations to dynamically generated type names. In addition, we explore how programs that are provably equivalent in a more traditional parametric logical relation may be “wrapped” systematically to produce terms that are related by our non-parametric relation, and vice versa. This leads us to develop a “polarized” variant of our logical relation, which enables us to distinguish formally between positive and negative notions of parametricity.

Type
Articles
Information
Journal of Functional Programming , Volume 21 , Special Issue 4-5: Dedicated to ICFP 2009 , September 2011 , pp. 497 - 562
Copyright
Copyright © Cambridge University Press 2011

References

Abadi, M., Cardelli, L., Pierce, B. & Rémy, D. (1995) Dynamic typing in polymorphic languages. J. Funct. Program. 5 (1), 111–130.CrossRefGoogle Scholar
Ahmed, A. (2004) Semantics of Types for Mutable State. Ph.D. thesis, Princeton University.Google Scholar
Ahmed, A. (2006) Step-indexed syntactic logical relations for recursive and quantified types. In Proceedings of European Symposium on Programming (ESOP), pp. 69–83.Google Scholar
Ahmed, A. & Blume, M. (2008) Typed closure conversion preserves observational equivalence. In Proceedings of ACM SIGPLAN International Conference on Functional Programming (ICFP), pp. 157–168.CrossRefGoogle Scholar
Ahmed, A., Dreyer, D. & Rossberg, A. (2009) State-dependent representation independence. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 340–353.CrossRefGoogle Scholar
Appel, A. W. & McAllester, D. (2001) An indexed model of recursive types for foundational proof-carrying code. ACM Trans. Program. Lang. Syst. 23 (5), 657–683.CrossRefGoogle Scholar
Benton, N. & Tabareau, N. (2009) Compiling functional types to relational specifications for low level imperative code. In Proceedings of ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI), pp. 3–14.CrossRefGoogle Scholar
Birkedal, L. & Harper, R. W. (1999) Constructing interpretations of recursive types in an operational setting. Inf. Comput. 155, 3–63.CrossRefGoogle Scholar
Girard, J.-Y. (1972) Interprétation Fonctionelle et Élimination des Coupures de L'arithmétique D'ordre Supérieur. Ph.D. thesis, Université Paris VII.Google Scholar
Grossman, D., Morrisett, G. & Zdancewic, S. (2000) Syntactic type abstraction. ACM Trans. Program. Lang. Syst. 22 (6), 1037–1080.Google Scholar
Harper, R. & Mitchell, J. C. (1999) Parametricity and variants of Girard's J operator. Inf. Process. Lett. 70 (1), 1–5.CrossRefGoogle Scholar
Harper, R. & Morrisett, G. (1995) Compiling polymorphism using intensional type analysis. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 130–141.Google Scholar
Matthews, J. & Ahmed, A. (2008) Parametric polymorphism through run-time sealing, or, theorems for low, low prices! In Proceedings of European Symposium on Programming (ESOP), pp. 16–31.Google Scholar
Mitchell, J. C. (1986) Representation independence and data abstraction. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 263–276.CrossRefGoogle Scholar
Mitchell, J. C. & Plotkin, G. D. (1988) Abstract types have existential type. ACM Trans. Program. Lang. Syst. 10 (3), 470–502.CrossRefGoogle Scholar
Neis, G. (2009) Non-Parametric Parametricity. M.Phil. thesis, Universität des Saarlandes.CrossRefGoogle Scholar
Pitts, A. (2005) Typed operational reasoning. In Advanced Topics in Types and Programming Languages, Benjamin, C. P. (ed), chap. 2. MIT Press.Google Scholar
Pitts, A. & Stark, I. (1993) Observable properties of higher order functions that dynamically create local names, or: What's new? In Proceedings of International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 711, pp. 122–141.Google Scholar
Pitts, A. & Stark, I. (1998) Operational reasoning for functions with local state. In Proceedings of Higher Order Operational Techniques in Semantics (HOOTS), pp. 227–274.Google Scholar
Reynolds, J. C. (1983) Types, abstraction and parametric polymorphism. Inf. Process, Amsterdam, pp. 513–523.Google Scholar
Rossberg, A. (2003) Generativity and dynamic opacity for abstract types. In Proceedings of ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP), pp. 241–252.Google Scholar
Rossberg, A. (2007) Typed Open Programming: A Higher-Order, Typed Approach to Dynamic Modularity and Distribution. Ph.D. thesis, Universität des Saarlandes.Google Scholar
Rossberg, A. (2008) Dynamic translucency with abstraction kinds and higher-order coercions. In Proceedings of Mathematical Foundations of Programming Semantics (MFPS), pp. 313–336.CrossRefGoogle Scholar
Rossberg, A., Le Botlan, D., Tack, G., Brunklaus, T. & Smolka, G. (2004) Alice ML through the looking glass. In Proceedings of Symposium on Trends in Functional Programming (TFP), vol. 5, pp. 79–96.Google Scholar
Sewell, P. (2001) Modules, abstract types, and distributed versioning. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 236–247.CrossRefGoogle Scholar
Sewell, P., Leifer, J., Wansbrough, K., Nardelli, F. Z., Allen-Williams, M., Habouzit, P. & Vafeiadis, V. (2007) Acute: High-level programming language design for distributed computation. J. Funct. Program. 17 (4–5), 547–612.Google Scholar
Sumii, E. & Pierce, B. C. (2003) Logical relations for encryption. J. Comput. Secur. 11 (4), 521–554.CrossRefGoogle Scholar
Sumii, E. & Pierce, B. C. (2007a). A bisimulation for dynamic sealing. Theor. Comput. Sci. 375 (1–3), 161–192.CrossRefGoogle Scholar
Sumii, E. & Pierce, B. C. (2007b) A bisimulation for type abstraction and recursion. J. ACM 54 (5), 1–43.CrossRefGoogle Scholar
Vytiniotis, D., Washburn, G. & Weirich, S. (2005) An open and shut typecase. In Proceedings of ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI), pp. 13–24.Google Scholar
Wadler, P. (1989) Theorems for free! In Proceedings of Conference on Functional Programming and Computer Architecture, pp. 347–359.Google Scholar
Washburn, G. & Weirich, S. (2005) Generalizing parametricity using information flow. In Proceedings of Symposium on Logic in Computer Science, pp. 62–71.Google Scholar
Weirich, S. (2004) Type-safe cast. J. Funct. Program. 14 (6), 681–695.CrossRefGoogle Scholar
Weirich, S., Vytiniotis, D., Peyton Jones, S. & Zdancewic, S. (2011) Generative type abstraction and type-level computation. In Proceedings of ACM SIGPLAN Symposium on Principles of Programming Languages (POPL), pp. 227–240.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.