Type dependencies for logic programs using ACI-unification

This paper presents a new notion of typing for logic programs which generalizes the notion of directional types. The generation of type dependencies for a logic program is fully automatic with respect to a given domain of types. The analysis method is based on a novel combination of program abstraction and ACI-unification which is shown to be correct and optimal. Type dependencies are obtained by abstracting programs, replacing concrete terms by their types, and evaluating the meaning of the abstract programs using a standard semantics for logic programs enhanced by ACI-unification. This approach is generic and can be used with any standard semantics. The method is both theoretically clean and easy to implement using general purpose tools. The proposed domain of types is condensing which means that analyses can be carried out in both top-down or bottom-up frameworks with no loss of precision for goal-independent analyses. The proposed method has been fully implemented within a bottom-up approach and the experimental results are promising.

Authors

• Michael Codish Ben Gurion University of the Negev
• Vitaly Lagoon

Keywords

• ACI unification
• Type analysis
• Logic programs