Designing Functions for Mutually Referential Definitions

The recipe for designing functions on mutually referential data definitions generalizes that for self-referential data. Indeed, it offers only two pieces of additional advice. First, we must create several templates simultaneously, one for each data definition. Second, we must annotate templates with self-references and CROSS-REFERENCES, that is, references among different templates. Here is a more detailed explanation of the differences:

The data analysis and design:

If a problem mentions a number of different classes of information (of arbitrary size), we need a group of data definitions that are self-referential and that refer to each other. In these groups, we identify the self-references and the cross-references between two data definitions.

In the above example, we needed two interrelated definitions:

The first one concerns parents and another one for list of children. The first (unconditionally) defines a parent in terms of symbols, numbers, and a list of children, that is, it contains a cross-reference to the second definition. This second definition is a conditional definition. Its first clause is simple; its second clause references both the definition for parents and list-of-children.

Contract, Purpose, Header:

To process interrelated classes of data, we typically need as many functions as there are class definitions. Hence, we must formulate as many contracts, purpose statements, and headers in parallel as there are data definitions.

Templates:

The templates are created in parallel, following the advice concerning compound data, mixed data, and self-referential data. Finally, we must determine for each selector expression in each template whether it corresponds to a cross-reference to some definition. If so, we annotate it in the same way we annotate cross-references.

Here are the templates for our running example:

The fun-parent template is unconditional because the data definition for parents does not contain any clauses. It contains a cross-reference to the second template: to process the children field of a parent structure. By the same rules, fun-children is conditional. The second cond-clause contains one self-reference, for the rest of the list, and one cross-reference for the first item of the list, which is a parent structure.

A comparison of the data definitions and the templates shows how analogous the two are. To emphasize the similarity in self-references and cross-references, the data definitions and templates have been annotated with arrows. It is easy to see how corresponding arrows have the same origin and destination in the two pictures.

The body:

As we proceed to create the final definitions, we start with a template or a cond-clause that does not contain self-references to the template and cross-references to other templates. The results are typically easy to formulate for such templates or cond-clauses.

The rest of this step proceeds as before. When we deal with other clauses or functions, we remind ourselves what each expression in the template computes, assuming that all functions already work as specified in the contracts. Then we decide how to combine these pieces of data into a final answer. As we do that, we must not forget the guidelines concerning the composition of complex functions (sections  and ).

The figure is not yet translated into HTML. Figure: Designing groups of functions for groups of data definitions the essential steps; for others see figures  (pg. ), (pg. ), and (pg. )