Some Applications of Pointer Algebra

It is well-known that algorithms involving pointers are both difficult to write and to verify. One reason is that, due to the implict connections through paths within a pointer structure, the side effects of a pointer assignment are usually much harder to survey than those of an ordinary assignment. Second, a careless assignment may destroy the last link to a substructure which thus is lost forever. Now, not only is it easy to make such errors; it is also very hard to find them. With this paper we want to show that these difficulties can be greatly reduced by making the store, which is an implicit global parameter in procedural languages, into an explicit parameter and by passing to an applicative treatment using a suitable algebra of operations on the store.