Modelling of mutable state spaces and precisely describing how variables are manipulated in a program is a fundamental problem in compositional verification. Though we can make use of the embedded abstract syntax of a program for such analysis, this runs contrary to the shallow-embedding approach, and hampers efficient proof automation. On the other hand, lenses and prisms provide an elegant algebraic foundation for modelling state, which provide sufficient structure to provide meta-logical program analysis, but without requiring a deep embedding. Nevertheless lenses, as complex algebraic objects, cannot easily be combined, complemented, or collected in sets. In this paper we contribute an accompanying algebraic structure called the scene, which allows us to characterise the set of variables, or coordinates, in a state space. Scenes intuitively correspond to sets of lenses, but like lenses they are purely semantic algebraic objects. We demonstrate that scenes provide us with sufficient structure to characterise the lens-based meta-logical properties, like independence and equivalence. Moreover, we introduce the notion of a scene space, analogous to a vector space, which allows us to recover a set-like algebraic structure. Finally, we show how scenes allow us to characterise the free and bound variables of expressions and programs, without any need for syntax, and demonstrate their use for reasoning about programs by deriving reasoning principles for the parallel composition operator.
Relational program logics are a popular formalism for stating and proving properties that relate executions of several computations. We present Infinitary Relational Logic (IRL)—the first Hoare-style Separation Logic that allows one to state and prove relational properties of possibly infinite families of arbitrary pro...
Vladimir Gladshtein, Qi-Yuan Zhao, Yu-Xi Ling et al.· Proceedings of the ACM on Pr...· 0 citations
This work introduces DueList, an abstraction-refinement approach geared towards list reasoning, which is implemented on top of off-the-shelf SMT solvers and extends reasoning facilities of existing solvers, allowing to conclude about the (un)satisfiability of a larger range of problems, while outperforming existing sol...
Pierre Goutagny, Aymeric Fromherz, Raphaël Monat· arXiv.org· 0 citations
An evaluation engine that is algebra-generic and amenable to differentiation, together with an executable specification of the algebras it can accept is presented, both forward and backward.
This work examines the computational complexity of existing abstraction techniques based on clustering (faithful and uniform abstractions) and proposes a novel syntactic operator to achieve uniform abstractions, when possible, and explores properties needed to reach abstractions from syntactic symmetry.
Z. G. Saribatur, Markus Hecher, J. Fichte· Proceedings of the Thirty-Fi...· 1 citation
It is demonstrated that VitruviusOCL can express multi-model constraints and specify intended behavior during design space exploration prior to identifying a concrete repair action, thereby making it a valuable part of the engineering process.
Max Oesterle, Arne Lange, Nathan Hagel et al.· Proceedings of the ACM/IEEE...· 1 citation
The empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and is competitive with state-of-the-art exact inference systems for continuous programs.
Katherine Wu, Jules Jacobs, Kevin Batz et al.· Proceedings of the ACM on Pr...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.