Relational Constraint: A Fast Semantic Analysis Technique

Abstract

Relational constraint is a new method for fast semantic analysis of computer programs. It starts with a fixed, finite vocabulary of binary relations; for each data type this vocabulary forms a complete lattice. Relational constraint focuses on strengthening relations in this lattice, developing the strongest correct statement it can about the relation between any two objects in its universe. The relational constraint algorithm runs in $O(n^{2})$ time. In this paper, we discuss the motivation for this research, present the algorithm in detail, and show how it fits in the formal framework of abstract interpretation.