CONSTRAINT PROPAGATION IN SOFTWARE LIBRARIES OF TRANSFORMATION SYSTEMS

Abstract
Domain modeling can be applied to collections of reusable designs and reusable software. Libraries of such collections can be used when applying a refinement by transformation technique to software construction. There already exist systems that can automatically or semi-automatically perform program transformations that constitute refinements. An important question is how to organize such libraries so that transformation tools may feasibly use them. We show that transformation of a high level program with constraints on the transformations is an NP-complete problem; however, appropriately organized libraries are tractable. Moreover, we define a property which a library of transformations can have, ensuring that any consistent high level program can be transformed into an executable form. Finally, we give approximations which reduce the complexity of transformations for libraries which do not have this property. The most important aspect of this work is that it implies certain rules should be followed in constructing libraries and the domains that are placed in them.

This publication has 0 references indexed in Scilit: