Alias calculus, change calculus and frame inference

• Change calculus allows inferring “modifies” clause automatically.
• The change calculus is based on alias calculus and covers most of a modern OO language.
• A large part of the calculus has been proved sound, mechanically, using Coq.
• Applied to an existing formally specified library, the analysis uncovered missing “modifies” clauses.

Alias analysis, which determines whether two expressions in a program may reference to the same object, has many potential applications in program construction and verification. We have developed a theory for alias analysis, the “alias calculus”, implemented its application to an object-oriented language, and integrated the result into a modern IDE. The calculus has a higher level of precision than many existing alias analysis techniques.One of the principal applications is to allow automatic change analysis, which leads to inferring “modifies” clauses, providing a significant advance towards addressing the Frame Problem. Experiments were able to infer the “modifies” clauses of an existing formally specified library. Other applications, in particular to concurrent programming, also appear possible.The article presents the calculus, the application to frame inference including experimental results, and other projected applications. The ongoing work includes building more efficient model capturing aliasing properties and soundness proof for its essential elements.