NDLI: Resolving and exploiting the k-CFA paradox:illuminating functional vs. object-oriented program analysis

Content Provider	ACM Digital Library
Author	Might, Matthew Van Horn, David Smaragdakis, Yannis
Abstract	Low-level program analysis is a fundamental problem, taking the shape of "flow analysis" in functional languages and "points-to" analysis in imperative and object-oriented languages. Despite the similarities, the vocabulary and results in the two communities remain largely distinct, with limited cross-understanding. One of the few links is Shivers's k-CFA work, which has advanced the concept of "context-sensitive analysis" and is widely known in both communities. Recent results indicate that the relationship between the functional and object-oriented incarnations of k-CFA is not as well understood as thought. Van Horn and Mairson proved k-CFA for k ≥ 1 to be EXPTIME-complete; hence, no polynomial-time algorithm can exist. Yet, there are several polynomial-time formulations of context-sensitive points-to analyses in object-oriented languages. Thus, it seems that functional k-CFA may actually be a profoundly different analysis from object-oriented k-CFA. We resolve this paradox by showing that the exact same specification of k-CFA is polynomial-time for object-oriented languages yet exponential-time for functional ones: objects and closures are subtly different, in a way that interacts crucially with context-sensitivity and complexity. This illumination leads to an immediate payoff: by projecting the object-oriented treatment of objects onto closures, we derive a polynomial-time hierarchy of context-sensitive CFAs for functional programs.
Starting Page	305
Ending Page	315
Page Count	11
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/1809028.1806631
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	45
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	Functional Pointer analysis Static analysis Control-flow analysis K-cfa M-cfa Object-oriented
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

Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis

Resolving and exploiting the k-cfa paradox illuminating functional vs. Object-oriented program analysis.

Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis (2010)

Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis (2010)

Resolving and Exploiting the k-CFA Paradox Illuminating Functional vs. Object-Oriented Program Analysis

Control-flow analysis of dynamic languages via pointer analysis

Precise static type analysis for object oriented programs

Using static single assignment form to improve flow-insensitive pointer analysis

Semi-sparse flow-sensitive pointer analysis

Resolving and exploiting the k-CFA paradox:illuminating functional vs. object-oriented program analysis

Similar Documents

Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis

Resolving and exploiting the k-cfa paradox illuminating functional vs. Object-oriented program analysis.

Resolving and exploiting the k-CFA paradox: illuminating functional vs. object-oriented program analysis (2010)

Resolving and exploiting the k-CFA paradox: Illuminating functional vs. object-oriented program analysis (2010)

Resolving and Exploiting the k-CFA Paradox Illuminating Functional vs. Object-Oriented Program Analysis

Control-flow analysis of dynamic languages via pointer analysis

Precise static type analysis for object oriented programs

Using static single assignment form to improve flow-insensitive pointer analysis

Semi-sparse flow-sensitive pointer analysis

Resolving and exploiting the k-CFA paradox:illuminating functional vs. object-oriented program analysis