Composition of Loop Modules in the Structural Blanks Approach to Programming with Recurrences: A Task of Synthesis of Nested Loops

Article type: Research Article

Authors: Čyras, Vytautas

Affiliations: Department of Software Engineering, Faculty of Mathematics and Informatics, Vilnius University, Naugarduko 24, LT-03225 Vilnius, Lithuania, e-mail: vytautas.cyras@maf.vu.lt

Abstract: The paper presents, first, the Structural Blanks (SB) approach, then a method to compose loop programs. SB is an approach for expressing computations based on recurrence relations and focuses on data dependencies in loops. The paper presents language constructs and semantics for expressing programs that have complex data dependency patterns. These constructs are expressed using structural “blanks” for computations based on recurrence relations. In SB the recurrence structure and the functional part of a recurrence relation may be described separately. Therefore declarative representation of data dependencies is examined. SB aims at supporting the transformational development and reuse of program modules. The approach deals with two aspects: pragmatics and semantics. In the paper we aim at: (1) developing a theory and language for functional and structural modules, (2) an algorithm for composition of structural modules. The approach is illustrated by toy problems: the Fibonacci function, heat flow, etc. Hence the reuse and verification are viewed as those of, e.g., stacks, queues, bubble sort, etc.

Keywords: recurrence, decomposition of computation, program composition, polymorphism, data dependency graph, loop program synthesis

Journal: Informatica, vol. 18, no. 1, pp. 37-54, 2007