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

article

Open access

Incremental analysis of constraint logic programs

Editor: William Pugh Authors:

Manuel Hermenegildo,

Peter J. StuckeyAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 22, Issue 2

Pages 187 - 223

https://doi.org/10.1145/349214.349216

Published: 01 March 2000 Publication History

Abstract

Global analyzers traditionally read and analyze the entire program at once, in a nonincremental way. However, there are many situations which are not well suited to this simple model and which instead require reanalysis of certain parts of a program which has already been analyzed. In these cases, it appears inefficient to perform the analysis of the program again from scratch, as needs to be done with current systems. We describe how the fixed-point algorithms used in current generic analysis engines for (constraint) logic programming languages can be extended to support incremental analysis. The possible changes to a program are classified into three types: addition, deletion, and arbitrary change. For each one of these, we provide one or more algorithms for identifying the parts of the analysis that must be recomputed and for performing the actual recomputation. The potential benefits and drawbacks of these algorithms are discussed. Finally, we present some experimental results obtained with an implementation of the algorithms in the PLAI generic abstract interpretation framework. The results show significant benefits when using the proposed incremental analysis algorithms.

References

[1]

ARMSTRONG, T., MARRIOTT, K., SCHACHTE, P., AND G H. SONDERGAARD. 1994. Boolean functions for dependency analysis: Algebraic properties and efficient representation. In Static Analysis Symposium, SAS'9~. Number 864 in LNCS. Springer-Verlag, Namur, Belgium, 266-280.

[2]

BossI, A., GABBRIELI, iV{., LEVI, G., AND iV{EO, iV{. 1994. A compositional semantics for logic programs. Theoretical Computer Science 122, 1,2, 3-47.

[3]

BRUYNOOGHE, ~/{. 1991. A practical framework for the abstract interpretation of logic programs. Journal of Logic Programming 10, 91-124.

[4]

BUENO, F., CABEZA, D., CARRO, ~/{., HERMENEGILDO, ~/{., LOPEZ-GARCfA, P., AND PUEBLA, G. 1997. The Ciao Prolog system. Reference manual. The Ciao System Documentation Series-TR CLIP3/97.1, School of Computer Science, Technical University of Madrid (UPM). August.

[5]

BUENO, F., CABEZA, D., HERMENEGILDO, ~/{., AND PUEBLA, G. 1996. Global analysis of standard Prolog programs. In European Symposium on Programming. Number 1058 in LNCS. Springer- Verlag, Sweden, 108-124.

[6]

BUENO, F., GARCIA DE LA BANDA, M. G., AND HERMENEGILDO, M. 1999a. Effectiveness of abstract interpretation in automatic parallelization: A case study in logic programming. A CM Transactions on Programming Languages and Systems 21, 2 (March), 189-238.

[7]

BUENO, F., GaRCfa DE LA BANDA, M. G., HERMENEGILDO, M., AND MUTHUKUMAR, K. 1999b. Automatic compile-time parallelization of logic programs for restricted, goM-level, independent and-parallelism. Journal of Logic Programming 38, 2, 165-218.

[8]

BUENO, F., GaRCfa DE LA BANDA, M., AND HERMENEGILDO, M. 1994. Effectiveness of globM analysis in strict independence-based automatic program parallelization. In International Symposium on Logic Programming. MIT Press, Cambridge, Massachusetts, 320-336.

[9]

BURKE, M. 1990. An interval-based approach to exhaustive and incremental interprocedurM dataflow analysis. ACM Transactions on Programming Languages and Systems 12, 3, 341-395.

[10]

CARROLL, M. AND RYDER, B. 1988. Incremental data flow analysis via dominator and attribute updates. In 15th A CM Symposium on Principles of Programming Languages (POPL). ACM Press, San Diego, 274-284.

[11]

CHARLIER, B. L. AND VAN HENTENRYCK, P. 1994. Experimental evaluation of a generic abstract interpretation algorithm for Prolog. A CM Transactions on Programming Languages and Systerns 16, 1, 35-101.

[12]

CHARLIER, B. L., DEGIMBE, O., MICHAEL, L., AND VAN HENTENRYCK, P. 1993. Optimization techniques for general purpose fixpoint algorithms: Practical efficiency for the abstract interpretation of Prolog. In Workshop on Static Analysis. Springer-Verlag, 15-26.

[13]

CHARLIER, B. L., ROSSI, S., AND VAN HENTENRYCK, P. 1994. An abstract interpretation framework which accurately handles Prolog search-rule and the cut. In International Symposium on Logic Programming. MIT Press, 157-171.

[14]

CODISH, M., DEBRAY, S., AND GIACOBAZZI, R. 1993. Compositional analysis of modular logic programs. In A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages POPL'93. ACM, Charleston, South Carolina, 451-464.

[15]

CONERY, J. S. AND KIBLER, D. F. 1981. Parallel interpretation of logic programs. In Proc. of the A CM Conference on Functional Programming Languages and Computer Architecture. (1981). ACM Press, 163-170.

[16]

COOPER, K. AND KENNEDY, K. 1984. Efficient computation of flow insensitive interprocedural summary information. In A CM SIGPLAN Symposium on Compiler Construction (SIGPLAN Notices 19(6)). ACM Press, 247-258.

[17]

COUSOT, P. AND COUSOT, R. 1977. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Fourth A CM Symposium on Principles of Programming Languages. ACM Press, Los Angeles, 238-252.

[18]

COUSOT, P. AND COUSOT, R. 1979. Systematic design of program analysis frameworks. In Sixth A CM Symposium on Principles of Programming Languages. ACM Press, San Antonio, Texas, 269-282.

[19]

DEBRAY, S., Ed. 1992. Journal of Logic Programming, Special Issue: Abstract Interpretation. Vol. 13(1-2). North-Holland, Amsterdam.

[20]

DEBRAY, S. K. 1989. Static inference of modes and data dependencies in logic programs. ACM Transactions on Programming Languages and Systems 11, 3, 418-450.

[21]

ENGLEBERT, V., LE CHARLIER, B., ROLAND, D., AND VAN HENTENRYCK, P. 1993. Generic abstract interpretation algorithms for Prolog: Two optimization techniques and their experimental evaluation. Software Practice and Experience 23, 4 (Apr.), 419-459.

[22]

GARCfA DE LA BANDA, M., MARRIOTT, K., SONDERGAARD, H., AND STUCKEY, P. 1998. Differential methods in logic program analysis. Journal of Logic Programming 35, 1, 1-37.

[23]

HERMENEGILDO, M. AND GREENE, K. 1991. The ~-Prolog system: Exploiting independent andparallelism. New Generation Computing 9, 3,4, 233-257.

[24]

HERMENEGILDO, M. AND ROSSI, F. 1995. Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions. Journal of Logic Programming 22, 1, 1-45.

[25]

HERMENEGILDO, M., BUENO, F., PUEBLA, G., AND L(f)PEZ-GARCfA, P. 1999a. Program analysis, debugging and optimization using the Ciao system preprocessor. In 1999 International Conference on Logic Programming. MIT Press, Cambridge, MA, 52-66.

[26]

HERMENEGILDO, M., PUEBLA, G., AND BUENO, F. 1999b. Using global analysis, partial specifications, and an extensible assertion language for program validation and debugging. In The Logic Programming Paradigm: a 25-Year Perspective, K. R. Apt, V. Marek, M. Truszczynski, and D. S. Warren, Eds. Springer-Verlag, 161-192.

[27]

HERMENEGILDO, M., PUEBLA, C., MARRIOTT, I~., AND STUCKEY, P. 1995. Incremental analysis of logic programs. In International Conference on Logic Programming. MIT Press, 797-811.

[28]

HERMENEGILDO, M., WARREN, R., AND DEBRAY, S. I~. 1992. Global flow analysis as a practical compilation tool. Journal of Logic Programming 13, 4 (August), 349-367.

[29]

KELLY, A., MACDONALD, A., MARRIOTT, I~., SONDERGAARD, H., AND STUCKEY, P. 1998a. Optimizing compilation for CLP(~). A CM Transactions on Programming Languages and Systerns 20, 6, 1223-1250.

[30]

KELLY, A., MARRIOTT, I~., SONDERGAARD, H., AND STUCKEY, P. 1998b. A practical objectoriented analysis engine for CLP. Software: Practice and Experience 28, 2, 199-224.

[31]

KRALL, A. AND BERGER, T. 1995a. Incremental global compilation of Prolog with the Vienna abstract machine. In International Conference on Logic Programming. MIT Press, Tokyo, 333-347.

[32]

KRALL, A. AND BERGER, T. 1995b. The VAMAI--an abstract machine for incremental global dataflow analysis of Prolog. In ICLP'95 Post-Conference Workshop on Abstract Interpretation of Logic Languages, M. G. de la Banda, G. Janssens, and P. Stuckey, Eds. Science University of Tokyo, Tokyo, 80-91.

[33]

MARLOWE, T. AND RYDER, B. 1990. An efficient hybrid algorithm for incremental data flow analysis. In 17th A CM Symposium on Principles of Programming Languages (POPL). ACM Press, San Francisco, 184-196.

[34]

MARRIOTT, I~. AND STUCKEY, P. 1998. Programming with Constraints: an Introduction. MIT Press.

[35]

MARRIOTT, I~., SONDERGAARD, H., AND JONES, N. 1994. Denotational abstract interpretation of logic programs. A CM Transactions on Programming Languages and Systems 16, 3, 607-648.

[36]

MUTHUKUMAR, I~. AND HERMENEGILDO, M. 1990. Deriving a fixpoint computation algorithm for top-down abstract interpretation of logic programs. Technical Report ACT-DC-153-90, Microelectronics and Computer Technology Corporation (MCC), Austin, TX 78759. April.

[37]

MUTHUKUMAR, I~. AND HERMENEGILDO, M. 1991. Combined determination of sharing and freeness of program variables through abstract interpretation. In 1991 International Conference on Logic Programming. MIT Press, Paris, 49-63.

[38]

MUTHUKUMAR, I~. AND HERMENEGILDO, M. 1992. Compile-time derivation of variable dependency using abstract interpretation. Journal of Logic Programming 13, 2/3 (July), 315-347. Originally published as Technical Report FIM 59.1/IA/90, Computer Science Dept, Universidad Politecnica de Madrid, Spain, August 1990.

[39]

POLLOCK, L. AND SOFFA, M. 1989. An incremental version of iterative data flow analysis. IEEE Transactions on Software Engineering 15, 12, 1537-1549.

[40]

PUEBLA, G. AND HERMENEGILDO, M. 1995. Implementation of multiple specialization in logic programs. In Proc. ACM SIGPLAN Symposium on Partial Evaluation and Semantics Based Program Manipulation. ACM Press, La Jolla, California, 77-87.

[41]

PUEBLA, G. AND HERMENEGILDO, M. 1996. Optimized algorithms for the incremental analysis of logic programs. In International Static Analysis Symposium. Number 1145 in LNCS. Springer- Verlag, 270-284.

[42]

PUEBLA, G. AND HERMENEGILDO, M. 1999. Abstract multiple specialization and its application to program parallelization. J. of Logic Programming. Special Issue on Synthesis, Transformation and Analysis of Logic Programs 41, 2&3 (November), 279-316.

[43]

PUEBLA, G. AND HERMENEGILDO, M. 2000. Some issues in analysis and specialization of modular Ciao-Prolog programs. Electronic Notes in Theoretical Computer Science 30, 2 (March). Special Issue on Optimization and Implementation of Declarative Programming Languages.

[44]

PUEBLA, G., BUENO, F., AND HERMENEGILDO, M. 2000. A generic preprocessor for program validation and debugging. In Analysis and Visualization Tools for Constraint Programming, P. Deransart, M. Hermenegildo, and J. MMuszynski, Eds. Springer-Verlag. To appear.

[45]

RAMALINGAM, G. AND REPS, T. 1993. A categorized bibliography on incremental computation. In A CM SIGPLAN-SIGA CT Symposium on Principles of Programming Languages POPL '93. ACM, Charleston, South Carolina.

[46]

ROSEN, B. 1981. Linear cost is sometimes quadratic. In Eighth ACM Symposium on Principles of Programming Languages (POPL). ACM Press, Williamsburg, Virginia, 117-124.

[47]

RYDER, B. 1988. Incremental data-flow analysis algorithms. A CM Transactions on Programming Languages and Systems 10, 1, 1-50.

[48]

RYDER, B., MARLOWE, T., AND PAULL, M. 1988. Conditions for incremental iteration: Examples and counterexamples. Science of Computer Programming 11, 1, 1-15.

[49]

SANTOS-COSTA, V., WARREN, D., AND YANG, R. 1991. The Andorra-I preprocessor: Supporting full Prolog on the basic Andorra model. In 1991 International Conference on Logic Programming. MIT Press, Paris, 443-456.

[50]

TARJAN, R. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 140-160.

[51]

VAN RoY, P. AND DESPAIN, t. 1992. High-performace logic programming with the aquarius Prolog compiler. IEEE Computer Magazine 25, 1 (January), 54-68.

[52]

WINSBOROUGH, W. 1992. Multiple specialization using minimM-function graph semantics. Journal of Logic Programming 13, 2 and 3 (July), 259-290.

Cited By

Jurjo DMorales JLópez-García PHermenegildo M(2023)Proceedings 39th International Conference on Logic ProgrammingElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.385.6385(55-57)Online publication date: 12-Sep-2023
https://doi.org/10.4204/EPTCS.385.6
Jurjo DMorales JLopez-Garcia PHermenegildo M(2023)A Rule-Based Approach for Designing and Composing Abstract DomainsLogic-Based Program Synthesis and Transformation10.1007/978-3-031-45784-5_6(80-98)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45784-5_6
Sanchez-Ordaz MGarcia-Contreras IPérez VMorales JLopez-Garcia PHermenegildo M(2021)Proceedings of the 6th Workshop on Formal Integrated Development EnvironmentElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.338.13338(105-112)Online publication date: 6-Aug-2021
https://doi.org/10.4204/EPTCS.338.13
Show More Cited By

Index Terms

Incremental analysis of constraint logic programs

Recommendations

Parametric shape analysis via 3-valued logic

Shape analysis concerns the problem of determining "shape invariants" for programs that perform destructive updating on dynamically allocated storage. This article presents a parametric framework for shape analysis that can be instantiated in different ...
Pushdown control-flow analysis for free
POPL '16

Traditional control-flow analysis (CFA) for higher-order languages introduces spurious connections between callers and callees, and different invocations of a function may pollute each other's return flows. Recently, three distinct approaches have been ...
Incremental resource usage analysis
PEPM '12: Proceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation

The aim of incremental global analysis is, given a program, its analysis results and a series of changes to the program, to obtain the new analysis results as efficiently as possible and, ideally, without having to (re-)analyze fragments of code which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 22, Issue 2

March 2000

244 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/349214

Editor:
William Pugh
Univ. of Maryland, College Park

Issue’s Table of Contents

Copyright © 2000 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2000

Published in TOPLAS Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
800
Total Downloads

Downloads (Last 12 months)161
Downloads (Last 6 weeks)33

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jurjo DMorales JLópez-García PHermenegildo M(2023)Proceedings 39th International Conference on Logic ProgrammingElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.385.6385(55-57)Online publication date: 12-Sep-2023
https://doi.org/10.4204/EPTCS.385.6
Jurjo DMorales JLopez-Garcia PHermenegildo M(2023)A Rule-Based Approach for Designing and Composing Abstract DomainsLogic-Based Program Synthesis and Transformation10.1007/978-3-031-45784-5_6(80-98)Online publication date: 23-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45784-5_6
Sanchez-Ordaz MGarcia-Contreras IPérez VMorales JLopez-Garcia PHermenegildo M(2021)Proceedings of the 6th Workshop on Formal Integrated Development EnvironmentElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.338.13338(105-112)Online publication date: 6-Aug-2021
https://doi.org/10.4204/EPTCS.338.13
SANCHEZ-ORDAZ MGARCIA-CONTRERAS IPEREZ VMORALES JLOPEZ-GARCIA PHERMENEGILDO M(2021) VeriFly: On-the-fly Assertion Checking via Incrementality Theory and Practice of Logic Programming10.1017/S147106842100043021:6(768-784)Online publication date: 2-Nov-2021
https://doi.org/10.1017/S1471068421000430
DE ANGELIS EFIORAVANTI FGALLAGHER JHERMENEGILDO MPETTOROSSI APROIETTI M(2021)Analysis and Transformation of Constrained Horn Clauses for Program VerificationTheory and Practice of Logic Programming10.1017/S147106842100021122:6(974-1042)Online publication date: 15-Nov-2021
https://doi.org/10.1017/S1471068421000211
GARCIA-CONTRERAS IMORALES JHERMENEGILDO M(2021)Incremental and Modular Context-sensitive AnalysisTheory and Practice of Logic Programming10.1017/S1471068420000496(1-48)Online publication date: 19-Jan-2021
https://doi.org/10.1017/S1471068420000496
Lin DWang QMin WXu JZhang Z(2020)A Survey on Energy-Efficient Strategies in Static Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/341431517:1(1-48)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3414315
Casso IMorales JLópez-García PHermenegildo M(2020)Testing Your (Static Analysis) TruthsLogic-Based Program Synthesis and Transformation10.1007/978-3-030-68446-4_14(271-292)Online publication date: 7-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-68446-4_14
Pérez VKlemen MLópez-García PMorales JHermenegildo M(2020)Cost Analysis of Smart Contracts Via Parametric Resource AnalysisStatic Analysis10.1007/978-3-030-65474-0_2(7-31)Online publication date: 18-Nov-2020
https://dl.acm.org/doi/10.1007/978-3-030-65474-0_2
Seidl HErhard JVogler R(2020)Incremental Abstract InterpretationFrom Lambda Calculus to Cybersecurity Through Program Analysis10.1007/978-3-030-41103-9_5(132-148)Online publication date: 15-Feb-2020
https://doi.org/10.1007/978-3-030-41103-9_5
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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents