Towards pointer algebra
Algorithms involving pointers are difficult to write and to verify. Due to the implicit connections through paths within a pointer structure, the side effects of a pointer assignment are much harder to survey than those of an assignment to a simple variable. Second, a careless assignment may destroy the last link to a substructure which thus is lost forever. Such errors are easily made, but found only with difficulty. The paper presents an approach to improving the situation. The store, which is an implicit global parameter in procedural languages, is made into an explicit parameter. This allows passing to an applicative treatment using a suitable algebra of operations on the store. The storage state of a von Neumann machine can be viewed as a total map from addresses to certain values. A part of such a state that forms a logical unit can then be represented by a partial submap of that map. So the state can be described in a modular way as the union of the submaps for its logical subunits. Therefore we use the algebra of relations and partial maps as our tool for specifying and developing of relational overwriting which in the case of partial maps models storage updates. The properties of overwriting are proved within abstract relational algebra. In connection with the algebra of partial maps the well-known unfold/fold transformation strategy is used for the (formal) derivation of correct pointer algorithms. This is illustrated with two algorithms on singly linked lists, viz. concatenation and reversal ``in situ. The approach extends well to arbitrary pointer structures.
- Automatically replacing indices into parallel arrays with pointers to records
- Calculational derivation of pointer algorithms from tree operations
- Characterizing determinacy in Kleene algebras
- Calculating with acyclic and cyclic lists
- Combining relational calculus and the Dijkstra-Gries method for deriving relational programs
- Extended transitive separation logic
- Extended feature algebra
- Transformational construction of correct pointer algorithms
- Pure Pointer Programs with Iteration
- Towards Modular Algebraic Specifications for Pointer Programs: A Case Study
- Datatypes in Memory
- scientific article; zbMATH DE number 3902005 (Why is no real title available?)
- Pure Pointer Programs and Tree Isomorphism
- Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras
- Structured document algebra in action
- Algebraic separation logic
- Relation-algebraic verification of disjoint-set forests
- Formalization of Refinement Calculus for Reactive Systems
- Algebra of Monotonic Boolean Transformers
This page was built for publication: Towards pointer algebra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685621)