NDLI: Complexity of kernel Fun subtype checking

Content Provider	ACM Digital Library
Author	Ghelli, Giorgio
Abstract	System kernel Fun is an abstract version of the system Fun defined by Cardelli's and Wegner's seminal paper [CW85], and is strictly related to system F≤. Extensions of these two systems are currently the basis of most proposals for strong type systems for object-oriented languages.We study here the problem of subtype checking for system kernel Fun, presenting the following results. We show that the standard kernel Fun subtype checking algorithm has an exponential complexity, and generates an exponential number of different subproblems. We then present a new subtype checking algorithm which has a polynomial complexity. In the process we study how variable names can be managed by a kernel Fun subtype checker which is not based on the De Bruijn encoding, and we show how to perform kernel Fun subtype checking with a "constraint generating" technique.The algorithm we give is described by a set of type rules, which we prove to be equivalent to the standard one. This new presentation of kernel Fun type system is characterized by a "multiplicative" behaviour, and it may open the way to new presentations for system F≤ as well.
Starting Page	134
Ending Page	145
Page Count	12
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/232629.232643
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	31
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Type theory Type checking Subtyping Polymorphism
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Complexity of kernel Fun subtype checking

Subtyping, Recursion and Parametric Polymorphism in Kernel Fun (2003)

Polymorphism, subtyping, and type inference in MLsub

Subtyping recursive types in kernel fun (1999).

Parametric polymorphism and semantic subtyping:the logical connection

Subtyping recursive types in kernel fun.

Polymorphism and subtyping in interface

Abstract complexity of kernel fun.

Polymorphism and type checking in object-oriented languages

Complexity of kernel Fun subtype checking

Similar Documents

Complexity of kernel Fun subtype checking

Subtyping, Recursion and Parametric Polymorphism in Kernel Fun (2003)

Polymorphism, subtyping, and type inference in MLsub

Subtyping recursive types in kernel fun (1999).

Parametric polymorphism and semantic subtyping:the logical connection

Subtyping recursive types in kernel fun.

Polymorphism and subtyping in interface

Abstract complexity of kernel fun.

Polymorphism and type checking in object-oriented languages

Complexity of kernel Fun subtype checking