{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T11:14:07Z","timestamp":1683026047651},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[1996,5,1]],"date-time":"1996-05-01T00:00:00Z","timestamp":830908800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[1996,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we define an extension of<jats:italic>F<\/jats:italic><jats:sub>\u2264<\/jats:sub>[CUG92] to which we add functions that dispatch on different terms according to the type they receive as argument. In other words, we enrich the explicit parametric polymorphism of<jats:italic>F<\/jats:italic><jats:sub>\u2264<\/jats:sub>by an explicit \u201cad hoc\u201d polymorphism (according the classification of [Str67]). We prove that the calculus we obtain, called<jats:italic>F<\/jats:italic><jats:sub arrange=\"stack\">\u2264<\/jats:sub><jats:sup arrange=\"stack\">&amp;<\/jats:sup>, enjoys the properties of Church-Rosser and Subject Reduction and that its proof system is coherent. We also define a significant subcalculus for which the subtyping is decidable. This extension has not only a logical interest but it is strongly motivated by the foundation of a broadly used programming style: object-oriented programming. The connections between<jats:italic>F<\/jats:italic><jats:sub arrange=\"stack\">\u2264<\/jats:sub><jats:sup arrange=\"stack\">&amp;<\/jats:sup>and object-oriented languages are widely stressed, and the modelling by<jats:italic>F<\/jats:italic><jats:sub arrange=\"stack\">\u2264<\/jats:sub><jats:sup arrange=\"stack\">&amp;<\/jats:sup>of some features of the object-oriented style is described, continuing the work of [CGL96].<\/jats:p>","DOI":"10.1007\/bf01214916","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T16:10:59Z","timestamp":1109347859000},"page":"247-293","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Integration of parametric and \u201cad hoc\u201d second order polymorphism in a calculus with subtyping"],"prefix":"10.1145","volume":"8","author":[{"given":"Giuseppe","family":"Castagna","sequence":"first","affiliation":[{"name":"Laboratoire d'Informatique de l'\u00c9cole Normale Sup\u00e9rieure, C.N.R.S., Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","unstructured":"Apple Computer Inc. Eastern Research and Technology. Dylan: an object-oriented dynamic language April 1992."},{"key":"e_1_2_1_2_2_2","unstructured":"Barendregt H.P.: The Lambda Calculus Its Syntax and Semantics . North-Holland 1984. Revised edition."},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001039"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90055-7"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0890-5401(88)90007-7","article-title":"A semantics of multiple inheritance","volume":"76","author":"Luca Cardelli","year":"1988","journal-title":"Information and Computation"},{"key":"e_1_2_1_2_6_2","volume-title":"Technical Report 92-11","author":"Castagna G.","year":"1992"},{"key":"e_1_2_1_2_7_2","unstructured":"Castagna G.: Overloading subtyping and late binding: functional foundation of object-oriented programming. PhD thesis Universit\u00e9 Paris 7 January 1994. Appeared as LIENS technical report."},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/203095.203096"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00071-4"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"crossref","unstructured":"Canning P.S. Cook W.R. Hill W.L. Mitchell J. Olthoff W.G.: F-bounded quantification for object-oriented programming. In ACM Conference on Functional Programming and Computer Architecture September 1989. Also in [GuM94].","DOI":"10.1145\/99370.99392"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"crossref","unstructured":"Curien P. L. Ghelli G.: Coherence of subsumption minimum typing and the type checking in F \u2264. Mathematical Structures in Computer Science 2(1) 1992.","DOI":"10.1017\/S0960129500001134"},{"issue":"2","key":"e_1_2_1_2_12_2","first-page":"115","article-title":"A calculus for overloaded functions with subtyping","volume":"117","author":"Castagna G.","year":"1996","journal-title":"Information and Computation"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BFb0037101","volume-title":"International Conference on Typed Lambda Calculi and Applications","author":"Castagna G.","year":"1993"},{"key":"e_1_2_1_2_14_2","unstructured":"Chambers C: Object-oriented multi-methods in Cecil. In ECOOP'92 number 615 in LNCS. Springer 1992."},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"crossref","unstructured":"Cook W.R. Hill W.L. Canning P.S.: Inheritance is not subtyping. 17th Ann. ACM Symp. on Principles of Programming Languages January 1990.","DOI":"10.1145\/96709.96721"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800000198"},{"key":"e_1_2_1_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/218570.218571"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1013"},{"key":"e_1_2_1_2_19_2","unstructured":"Compagnoni A. Pierce B.C.: Multiple inheritance via intersection types. MSCS to appear."},{"key":"e_1_2_1_2_20_2","first-page":"151","volume-title":"21 st Annual Symposium on Principles Of Programming Languages","author":"Castagna G.","year":"1994"},{"key":"e_1_2_1_2_21_2","volume-title":"22nd Annual Symposium on Principles Of Programming Languages","author":"Castagna G.","year":"1995"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/6041.6042"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-47891-4_15","volume-title":"Proc. of ECOOP '87 European Conference on Object-Oriented Programming","author":"DeMichiel L.G.","year":"1987"},{"key":"e_1_2_1_2_24_2","unstructured":"Ghelli G.: Proof Theoretic Studies about a Minimal Type System Integrating Inclusion and Parametric Polymorphism . PhD thesis Dipartimento di Informatica Universit\u00e1 di Pisa March 1990. Tech. Rep. TD-6\/90."},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"crossref","unstructured":"Ghelli G.: A static type system for message passing. In Proc. of OOPSLA '91 1991.","DOI":"10.1145\/117954.117964"},{"key":"e_1_2_1_2_26_2","unstructured":"Gunter C.A. Mitchell J.C.: Theoretical Aspects of Object-Oriented Programming: Types Semantics and Language Design . The MIT Press 1994."},{"key":"e_1_2_1_2_27_2","unstructured":"Hindley R.: The Church-Rosser property and a result of combinatory logic. Dissertation 1964. University of Newcastle-upon-Tyne."},{"key":"e_1_2_1_2_28_2","unstructured":"Howard W.A.: The formulae-as-types notion of construction. In J.R. Hindley and J.P. Seldin editors To H.B. Curry: Essays in Combinatory Logic Lambda Calculus and formalism. Academic Press 1980."},{"key":"e_1_2_1_2_29_2","doi-asserted-by":"crossref","unstructured":"Knuth D.E. Bendix P.B.: Simple word problems in universal algebras. In J. Leech editor Computational Problems in Abstract Algebra pages 263\u2013297. Pergamon Press 1970.","DOI":"10.1016\/B978-0-08-012975-4.50028-X"},{"key":"e_1_2_1_2_30_2","unstructured":"Bertrand Meyer. Object-Oriented Software Construction. Prentice-Hall International Series 1988."},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"crossref","unstructured":"Mitchell J.C. Harper R.: The essence of ML. 15th Ann. ACM Symp. on Principles of Programming Languages January 1988.","DOI":"10.1145\/73560.73563"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"publisher","DOI":"10.2307\/1968867"},{"key":"e_1_2_1_2_33_2","unstructured":"NeXT Computer Inc. NeXTStep-concepts. Chapter 3: Object-Oriented Programming and Objective-C 2.0 edition 1991."},{"key":"e_1_2_1_2_34_2","doi-asserted-by":"crossref","unstructured":"Pierce B.C.: Bounded quantification is undecidable. Information and Computation 1993. To appear. Also in [GuM94]. Preliminary version in proceedings of POPL '92.","DOI":"10.1145\/143165.143228"},{"key":"e_1_2_1_2_35_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796800001040"},{"key":"e_1_2_1_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321750"},{"key":"e_1_2_1_2_37_2","unstructured":"Strachey C.: Fundamental concepts in programming languages. Lecture notes for International Summer School in Computer Programming Copenhagen August 1967."}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01214916.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01214916\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/BF01214916","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,2]],"date-time":"2023-05-02T10:50:14Z","timestamp":1683024614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/BF01214916"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,5]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,5]]}},"alternative-id":["10.1007\/BF01214916"],"URL":"https:\/\/doi.org\/10.1007\/bf01214916","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,5]]}}}