More Web Proxy on the site http://driver.im/

article

Free access

Unfold/fold transformations and loop optimization of logic programs

Author:

S. K. DebrayAuthors Info & Claims

ACM SIGPLAN Notices, Volume 23, Issue 7

Pages 297 - 307

https://doi.org/10.1145/960116.54020

Published: 01 June 1988 Publication History

Abstract

Programs typically spend much of their execution time in loops. This makes the generation of efficient code for loops essential for good performance. Loop optimization of logic programming languages is complicated by the fact that such languages lack the iterative constructs of traditional languages, and instead use recursion to express loops. In this paper, we examine the application of unfold/fold transformations to three kinds of loop optimization for logic programming languages: recursion removal, loop fusion and code motion out of loops. We describe simple unfold/fold transformation sequences for these optimizations that can be automated relatively easily. In the process, we show that the properties of unification and logical variables can sometimes be used to generalize, from traditional languages, the conditions under which these optimizations may be carried out. Our experience suggests that such source-level transformations may be used as an effective tool for the optimization of logic programs.

References

[1]

A.V. Aho, R. Sethi and J. D. Ullman, Compilers - Principles, Techniques and Tools, Addison-Wesley, 1986.

Digital Library

[2]

J. Arsac and Y. Kodratoff, Some Techniques for Recursion Removal from Recursive Functions, ACM Trans. Prog. Lang. and Systems 4, 2 (Apr. 1982), 295- 322.

Digital Library

[3]

N. Azibi, E. J. Costa and Y. Kodratoff, Methode de Transformation de Programmes de Burstall-Darlington Appliquee a la Programmation Logique, Research Report No. 268, Universite de Paxis-Sud, Orsay, France, Mar. 1986.

[4]

C. B loch, Source-to-Source Transformations of Logic Programs, CS84-22, Dept. of Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, Dec. 1984.

[5]

M. Bruynooghe, The Memory Management of PROLOG Implementations, in Logic Programming, K. L. Clark and S. Tarnlund (ed.), Academic Press, London, 1982. A.P.I.C. Studies in Data Processing No. 16.

[6]

R.M. Burstall and J. Darlington, A Transformation System for Developing Recursive Programs, J. ACM 24, i (January 1977), 44-67.

Digital Library

[7]

J. Chang, A. M. Despain and D. DeGroot, AND- Parallelism of Logic Programs Based on A Static Data Dependency Analysis, in Digest of Papers, Compcon 85, IEEE Computer Society, Feb. 1985.

[8]

K. L. Clark, Negation as Failure, in Logic and Data Bases, H. Gallaire and J. Minker (ed.), Plenum Press, New York, 1978.

[9]

N. H. Cohen, Source-to-Source Improvement of Recursive Programs, Ph.D. Thesis, Harvard University, Cambridge, MA, May 1980.

[10]

S. K. Debray, Optimizing Almost-Tail-Recursive Prolog Programs, in Proc. IFIP International Conference on Functional Programming Languages and Computer Architecture, Nancy, France, Sept. 1985.

Digital Library

[11]

S. K. Debray and D. S. Warren, Detection and Optimization of Functional Computations in Prolog, in Proc. Third Int. Conf. on Logic Programming, London, July 1986. Springer-Vefiag LNCS vol. 225.

Digital Library

[12]

S. K. Debray, Static inference of Modes and Data Dependencies in Logic Programs, Tech. Rep. 87-24, Dept. of Computer Science, University of Arizona, Tucson, AZ, Aug. 1987.

[13]

M. S. Feather, A System for Assisting Program Transformation, ACM Trans. Prog. Lang. and Systems 4, 1 (Jan. 1982), 1-20.

Digital Library

[14]

T. Kanamori and K. Horiuchi, Construction of Logic Programs Based on Gneralized Unfold/Fold Rules, in Proc. 4th. international Conference on Logic Programming, Melbourne, Australia, May i987, pp. 744-768.

[15]

R.B. Kieburtz and J. Schultis, Transformations of FP Program Schemes, in Proc. 1981 Conf. Func. Prog. Langs. and Comp. Arch., ACM, Portsmouth, New Hampshire, Oct. 1981.

Digital Library

[16]

J. W. Lloyd, Foundations of Logic Programming, Springer Verlag, 1984.

Digital Library

[17]

C.S. Mellish, Some Global Optimizations for a Prolog Compiler, J. Logic Programming 2, 1 (Apr. 1985), 43- 66.

[18]

H. Nakagawa, Prolog Program Transformations and Tree Manipulation Algorithms, J. Logic Programming 2, 2 (July 1985), 77-91.

[19]

H. Seki and K. Furukawa, Notes on Transformation Techniques for Generate and Test Logic Programs, in Proc. Fourth IEEE Symposium on Logic Programming, San Fransisco, CA, Sep. 1987, pp. 215-223.

[20]

E. St.-James, Recursion is More Efficient than Iteration, in Proc. 1984 A CM Syrup. on LISP and Functional Programming, Austin, Texas, Aug. 1984.

Digital Library

[21]

H. Tamaki and T. Sato, Unfold/Fold Transformations of Logic Programs, in Proc. 2nd. Logic Programming Conference, Uppsala, Sweden, 1984.

[22]

D.H.D. Warren, An improved Prolog implementation which optimises tail recursion, Research Paper 156, Dept. of Artificial Intelligence, University of Edinburgh, Scotland, 1980. Presented at the 1980 Logic Programming Workshop, Debrecen, Hungary.

Cited By

Francesco NSantone A(2005)Unfold/Fold transformations of concurrent processesProgramming Languages: Implementations, Logics, and Programs10.1007/3-540-61756-6_84(167-181)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61756-6_84
Gergatsoulis MKatzouraki M(2005)Unfold/fold transformations for definite clause programsProgramming Language Implementation and Logic Programming10.1007/3-540-58402-1_24(340-354)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-58402-1_24
Bruynooghe MSchreye D(2005)Some thoughts on the role of examples in program transformation and its relevance for explanation-based learningAnalogical and Inductive Inference10.1007/3-540-51734-0_52(60-77)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-51734-0_52
Show More Cited By

Index Terms

Unfold/fold transformations and loop optimization of logic programs

Recommendations

Unfold/fold transformations and loop optimization of logic programs
PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation

Programs typically spend much of their execution time in loops. This makes the generation of efficient code for loops essential for good performance. Loop optimization of logic programming languages is complicated by the fact that such languages lack ...
Beyond Tamaki-Sato Style Unfold/Fold Transformations for Normal Logic Programs
ASIAN '99: Proceedings of the 5th Asian Computing Science Conference on Advances in Computing Science

Unfold/fold transformation systems for logic programs have been extensively investigated. Existing unfold/fold transformation systems for normal logic programs allow only Tamaki-Sato style folding using clauses from a previous program in the ...
Proving properties of co-logic programs by unfold/fold transformations
LOPSTR'11: Proceedings of the 21st international conference on Logic-Based Program Synthesis and Transformation

We present a framework for unfold/fold transformation of co-logic programs, where each predicate is annotated as either inductive or coinductive, and the declarative semantics of co-logic programs is defined by an alternating fixpoint model: the least ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 23, Issue 7

Proceedings of the SIGPLAN '88 conference on Programming language design and implementation

July 1988

338 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/960116

Issue’s Table of Contents

PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation
June 1988
338 pages
ISBN:0897912691
DOI:10.1145/53990
Editor:
R. L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY

Copyright © 1988 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Published in SIGPLAN Volume 23, Issue 7

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
691
Total Downloads

Downloads (Last 12 months)132
Downloads (Last 6 weeks)17

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Francesco NSantone A(2005)Unfold/Fold transformations of concurrent processesProgramming Languages: Implementations, Logics, and Programs10.1007/3-540-61756-6_84(167-181)Online publication date: 7-Jun-2005
https://doi.org/10.1007/3-540-61756-6_84
Gergatsoulis MKatzouraki M(2005)Unfold/fold transformations for definite clause programsProgramming Language Implementation and Logic Programming10.1007/3-540-58402-1_24(340-354)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-58402-1_24
Bruynooghe MSchreye D(2005)Some thoughts on the role of examples in program transformation and its relevance for explanation-based learningAnalogical and Inductive Inference10.1007/3-540-51734-0_52(60-77)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-51734-0_52
Pettorossi AProietti M(1996)Rules and strategies for transforming functional and logic programsACM Computing Surveys10.1145/234528.23452928:2(360-414)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1145/234528.234529
Pettorossi AProietti M(1994)Transformation of logic programs: Foundations and techniquesThe Journal of Logic Programming10.1016/0743-1066(94)90028-019-20(261-320)Online publication date: May-1994
https://doi.org/10.1016/0743-1066(94)90028-0
Alexandre F(1992)A technique for transforming logic programs by fold-unfold transformationsProgramming Language Implementation and Logic Programming10.1007/3-540-55844-6_137(202-216)Online publication date: 1992
https://doi.org/10.1007/3-540-55844-6_137
Pottosin I(1991)Analysis of program optimization possibilities and further developmentTheoretical Computer Science10.1016/0304-3975(91)90296-E90:1(17-36)Online publication date: 1-Nov-1991
https://dl.acm.org/doi/10.1016/0304-3975%2891%2990296-E
De Schreye DMartens BSablon GBruynooghe M(1991)Compiling bottom-up and mixed derivations into top-down executable logic programsJournal of Automated Reasoning10.1007/BF002490187:3(337-358)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1007/BF00249018
Huntbach M(1989)Meta-interpreters and partial evaluation in ParlogFormal Aspects of Computing10.1007/BF018872051:1(193-211)Online publication date: 1-Mar-1989
https://dl.acm.org/doi/10.1007/BF01887205
SCHRIJVERS TVAN DEN BERG BRIGUZZI F(2023)Automatic Differentiation in PrologTheory and Practice of Logic Programming10.1017/S1471068423000145(1-18)Online publication date: 6-Jul-2023
https://doi.org/10.1017/S1471068423000145
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents