Transforming acyclic programs

Share/Save/Bookmark

Bossi, Annalisa and Etalle, Sandro (1994) Transforming acyclic programs. ACM Transactions on Programming Languages and Systems (TOPLAS), 16 (4). pp. 1081-1096. ISSN 0164-0925

[img]
Preview
PDF
910Kb
Abstract:An unfold/fold transformation system is a source-to-source rewriting methodology devised to improve the efficiency of a program. Any such transformation should preserve the main properties of the initial program: among them, termination. In the field of logic programming, the class of acyclic programs plays an important role in this respect, since it is closely related to the one of terminating programs. The two classes coincide when negation is not allowed in the bodies of the clauses. We prove that the Unfold/Fold transformation system defined by Tamaki and Sato preserves the acyclicity of the initial program. From this result, it follows that when the transformation is applied to an acyclic program, then the finite failure set for definite programs is preserved; in the case of normal programs, all major declarative and operational semantics are preserved as well. These results cannot be extended to the class of left-terminating programs without modifying the definition of the transformation.
Item Type:Article
Copyright:© 1994 ACM
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/55874
Official URL:http://dx.doi.org/10.1145/183432.183434
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page