Functorial polymorphism and semantic parametricity

Philip J. Scott

Diagrammes (1989)

  • Volume: 22, page 77-90
  • ISSN: 0224-3911

How to cite

top

Scott, Philip J.. "Functorial polymorphism and semantic parametricity." Diagrammes 22 (1989): 77-90. <http://eudml.org/doc/193032>.

@article{Scott1989,
author = {Scott, Philip J.},
journal = {Diagrammes},
keywords = {effective topos; Girard's system F of polymorphic lambda calculus; interpretation of variable types; quantification over types; type evaluation; multivariant functors; dinatural transformations; ends of functors; category of partial equivalence relations on the natural numbers; realizable functors},
language = {eng},
pages = {77-90},
publisher = {Université Paris 7, Unité d'enseignement et de recherche de mathématiques},
title = {Functorial polymorphism and semantic parametricity},
url = {http://eudml.org/doc/193032},
volume = {22},
year = {1989},
}

TY - JOUR
AU - Scott, Philip J.
TI - Functorial polymorphism and semantic parametricity
JO - Diagrammes
PY - 1989
PB - Université Paris 7, Unité d'enseignement et de recherche de mathématiques
VL - 22
SP - 77
EP - 90
LA - eng
KW - effective topos; Girard's system F of polymorphic lambda calculus; interpretation of variable types; quantification over types; type evaluation; multivariant functors; dinatural transformations; ends of functors; category of partial equivalence relations on the natural numbers; realizable functors
UR - http://eudml.org/doc/193032
ER -

References

top
  1. [BFSS a] Bainbridge, E.S., Freyd, P.J., Scedrov, A., Scott, P.J.Functorial polymorphism. In: Huet, G. Logical Foundations of Functional Programming, Proceedings University of Texas Programming Institute, Austin, Texas, June 1987, ed. by G. Huet, to appear. MR1047051
  2. [BFSS b] Bainbridge, E.S., Freyd, P.J., Scedrov, A., Scott, P.J.Functorial polymorphism, Theoretical Computer Science, to appear. Zbl0717.18005MR1047051
  3. Barendregt, H.P., The Lambda Calculus (Revised Edition), Studies in Logic and the Foundations of Mathematics, North-Holland, 1984. Zbl0551.03007MR774952
  4. Breazu-Tannen, V., Coquand, T[87] Extensional models for polymorphism. Proc. TAPSOFT '87 - CFLP, Pisa. Springer LNCS 250. Expanded version to appear in Theor. Comp. Science. Zbl0636.03005MR900622
  5. Carboni, A., Freyd, P., Scedrov, A. [88] A categorical approach to realizability and polymorphic types. Proc. 3rd ACM Workshop on the Mathematical Foundations of the Programming Semantics, New Orleans, April, 1987, ed. by M. Main et al., Springer LNCS 298, 1988, pp. 23-42. Zbl0651.18004MR948482
  6. [CGW] Coquand, T., Gunter, C.A., Winskel, G.Domain theoretic models for polymorphism. Information and Computation, to appear. Zbl0683.03007MR997196
  7. [DS70] Dubuc, E.J., Street, R., Dinatural transformations, Reports of the Midwest Category Seminar IV, Springer LNM Vol. 137 [ 1970], pp. 126-128. Zbl0222.18004MR274550
  8. Eilenberg, S., Kelly, G.M.A generalization of the functorial calculus, J. Algebra 3 [ 1966], pp. 366-375. Zbl0146.02501MR190204
  9. [F89] Freyd, P.J.Structural Polymorphism I, II, III (Preliminary Report) Univ. of Pennsylvania, Jan. 1989. 
  10. [FGSS] Freyd, P.J., Girard, J.Y., Scedrov, A., Scott, P.J. [88] Semantic parametricity in polymorphic lambda calculus. Proc. 3rd IEEE Symposium on Logic in Computer Science, Edinburgh, Scotland, July 1988. 
  11. [Gi 72] Girard, J.-Y.Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur. Thèse de Doctorat d'Etat, Université de Paris VII. 
  12. [Gi 86] Girard, J.-Y.The system F of variables types, fifteen years later. Theor. Comp. Science 45 [ 1986] pp. 159-192. Zbl0623.03013MR867281
  13. [Gi87] Girard, J.-Y.Le Lambda Calcul Du Second Ordre, Séminaire Bourbaki, Astérisque 152-153 ( 1987), pp. 173-185. Zbl0645.03013MR936854
  14. Hasagawa, Ryu. Parametric Polymorphism and Internal Representations of Recursive Type Definitions, Manuscript, 12 April, 1989 
  15. Hyland, J.M.E.A small complete category, Ann. Pure and Applied Logic, V. 40, ( 1988) 135-165. Zbl0659.18007MR972520
  16. Hyland, J.M.E., Robinson, E.P., Rosolini, G.The discrete objects in the Effective Topos. Preprint, 1987. Zbl0703.18002
  17. Kelly, M.Many-variable Functional Calculus I, Coherence in Categories, SLNM281, S. MacLane, ed., 1977, pp. 66-105. Zbl0243.18015
  18. [LS] Lambek, J., Scott, P.J.Introduction to higher-order categorical logic. Cambridge University Press, Studies in Advanced Mathematics 7, 1986. Zbl0596.03002MR856915
  19. [Mac] MacLane, S.Categories for the working Mathematician, Graduate Texts in Mathematics 5, Springer-Verlag, 1971. Zbl0232.18001MR1712872
  20. [R83] Reynolds, J.C.Types, abstraction, and parametric polymorphism. In: Information Processing '83, ed. by R.E.A. Mason. North-Holland, Amsterdam, pp. 513-523. 
  21. [R84] Reynolds, J.C.Polymorphism is not set-theoretic. Symposium on Semantics of Data Types, ed. by Kahn et al., Springer LNCS 173, 1984. Zbl0554.03012MR784456
  22. [RP88] Reynolds, J.C., Plotkin, G.D.On functors expressible in the polymorphic typed lambda calculus. To appear in Information and Computation. Zbl0785.03004MR1225479
  23. Robinson, E.P. [89] How Complete is PER ? Proc. 4th IEEE Symposium on Logic in Computer Science, Asilomar, Califomia, June 1989. Zbl0717.03028
  24. Seely, R.A.G. [87] Categorical semantics for higher-order polymorphic lambda calculus. J. Symbolic Logic 52 [ 1987] pp. 969-989. Zbl0642.03007MR916402
  25. Wadler, P.Theorems for Free! To appear in : 4th International Symposium on Functional Languages and Computer Architecture, London, Sept 1989. 
  26. [Y60] Yoneda, N.On Ext and exact sequences J. Fac. Sci., Tokyo Sec 1, Vol. 8, 1960, pp. 507-526. Zbl0163.26902MR225854

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.