Martelli A. Program development through successive transformations: an application to list Processing. In: 3rd International Symposium on Programming (Paris, 28-30 March 1978). Proceedings, pp. 381 - 394. DUNOD informatique, 1978. |

Abstract (English) |
The paper applies a program transformation technique to the derivation of an algorithm, proposed by Robson, for copying cyclic structures using bounded workspace and linear time. This technique allows a clear understanding of the process through which the final program is obtained, since every transformation takes into account only one aspect of the problem. The initial version of the program is a simple recursive program which copies abstract structures, i.e. structures whose nodes have auxiliary fields. This program is based on the idea of visiting twice, in different orders, the spanning tree of the structure. Then a mapping is defined between abstract and real structures; using this mapping it is possible to transform the above program into an equivalent recursive program which copies real structures. Finally the recursive program is transformed into an equivalent iterative program which embeds the stack in the structure, thus achieving the goal of using no extra workspace. An outline of the correctness proof of these transformations is given. | |

Subject |

1) Download Document PDF |

Open access Restricted Private