Existential Label Flow Inference via CFL Reachability (Extended Version). Polyvios Pratikakis, Michael Hicks, and Jeffrey S. Foster. Technical Report CS-TR-4700, Department of Computer Science, University of Maryland, July 2005.

Label flow analysis is a fundamental static analysis problem with a wide variety of applications. Previous work by Mossin developed a polynomial time subtyping-based label flow inference that supports Hindley-Milner style polymorphism with polymorphic recursion. Rehof et al have developed an efficient O(n3) inference algorithm for Mossin's system based on context-free language (CFL) reachability. In this paper, we extend these results to a system that also supports existential polymorphism, which is important for precisely describing correlations among members of a structured type, even when values of that type are part of dynamic data structures. We first develop a provably sound checking system based on polymorphically-constrained types. As usual, we restrict universal quantification to the top level of a type, but existential quantification is first class, with subtyping allowed between existentials with the same binding structure. We then develop a CFL-based inference system. Programmers specify which positions in a type are existentially quantified, and the algorithm infers the constraints bound in the type, or rejects a program if the annotations are inconsistent.

[ .pdf ]

@TECHREPORT{pratikakis05existstr,
  AUTHOR = {Polyvios Pratikakis and Michael Hicks and Jeffrey S. Foster},
  TITLE = {Existential Label Flow Inference via {CFL} Reachability (Extended Version)},
  INSTITUTION = {Department of Computer Science, University of Maryland},
  NUMBER = {CS-TR-4700},
  YEAR = 2005,
  MONTH = JUL
}

This file has been generated by bibtex2html 1.69