Relational programming laws in the tree, list, bag, set hierarchy (Q1330449)

The authors demonstrate that the basic rules and the calculational techniques used in two extensively documented program derivation methods can be expressed within a relational theory of datatypes. The two methods to which the authors refer are the so-called ``Bird-Meertens formalism'' for the construction of functional programs and the ``Dijkstra-Feijen calculus'' for the construction of imperative programs. The paper starts with a brief introduction to a relational calculus of datatypes as described in some previous paper of the authors. Then it is defined the so-called binary structures and the map, reduce and filter operators. Before the authors start with the original Boom hierarchy where laws play an important role, they first define what it means by an associative, symmetric or idempotent relation, and also define the Boom hierarchy for their system and it is shown how can be incorporated into the relational calculus. Finally, the formalism is related to the quantifier calculus.