AbstractThe problem of concrete type-inference for statically typed object-oriented programming languages (e.g., Java, C++) determines at each program point, those objects to which a reference may refer or a pointer may point during execution. We present a new technique called analysis-using-abstract-values which performs modular and demand driven concrete type-inference of a robust subset of Java without threads and exceptions and C++ without exceptions. Our algorithm is provably precise on programs with only single-level types2 and without dynamic dispatch, and has the worst-case complexity of O(n4 ) which is an improvement over the O(n7 ) worst-case bound achievable by applying previous approaches of [RHS95] and [LR91] to this case. For general programs, the algorithm is polynomial-time and computes a safe solution.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).