Taking Alloy to the Movies

We present a modified semantics and an extension of the Alloy specification language. The results presented in this paper are: (a) We show how the modified semantics of Alloy allows us to avoid the higher-order quantification currently used both in the composition of operations and in specifications, keeping the language first-order. (b) We show how the extended language, which includes features from dynamic logic, enables a cleaner (with respect to previous papers) treatment of properties of executions. (c) We show that the automatic analysis currently available for Alloy specifications can be fully applied in the analysis of specifications under the new semantics. (d) We present a calculus for the extended language that is complete with respect to the extended semantics. This allows us to complement the analysis currently provided in Alloy with theorem proving. (e) Finally, we show how to use the theorem prover PVS in order to verify Alloy specifications.