Loading...
Please wait, while we are loading the content...
Similar Documents
Polymorphic constraint-based type inference for objects.
| Content Provider | CiteSeerX |
|---|---|
| Author | Wang, Tiejun Smith, Scott F. |
| Abstract | Constraint-based type inference infers types with subtyping constraints. Such types can capture detailed data and control flow information about the analyzed program. In the presence of polymorphism, existing constraint-based type inference algorithms sacrifice much precision for efficiency. This paper presents both theoretical and practical results on developing precise and efficient polymorphic constraint-based type inference for object-oriented languages. We develop a novel theoretical framework for polymorphic constraint-based type inference. A concrete type inference algorithm can be obtained by instantiating the framework with a particular strategy for handling polymorphism. We define well-known algorithms such as Shivers’ nCFA and Agesen’s Cartesian Product Algorithm (CPA) as instantiations of the framework. We prove the soundness of the framework, which entails the soundness of every algorithm defined as an instantiation of the framework. Using the framework, we develop a novel algorithm, Data Polymorphic CPA (DCPA), which extends Agesen’s CPA Algorithm to achieve high precision in the presence of Data Polymorphism. We further study the construction of practical constraint-based type inference systems for realistic programming languages. We have constructed a type inference system for the full Java language. The system includes implementations of the 0CFA, CPA and DCPA algorithms, and it incorporates a number of novel implementation techniques for achieving scalability. The system is used to statically verify the correctness of Java downcasts. Benchmark results on realistic Java applications show that the DCPA algorithm has good precision and efficiency: it is significantly more accurate than existing algorithms and its efficiency is comparable to CPA. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Flow Information Realistic Java Application Realistic Programming Language Efficient Polymorphic Constraint-based Type Inference Cartesian Product Algorithm Novel Algorithm Analyzed Program Data Polymorphic Cpa Practical Result Practical Constraint-based Type Inference System Good Precision High Precision Well-known Algorithm Full Java Language Much Precision Constraint-based Type Inference Infers Type Agesen Cpa Algorithm Object-oriented Language Data Polymorphism Novel Implementation Technique Constraint-based Type Inference Type Inference System Particular Strategy Java Downcast Benchmark Result Novel Theoretical Framework Dcpa Algorithm Concrete Type Inference Algorithm Polymorphic Constraint-based Type Inference |
| Content Type | Text |
| Resource Type | Article |
