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

article

Open access

Static inference of modes and data dependencies in logic programs

Editor: Susan L. Graham Author:

Saumya K. DebrayAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 11, Issue 3

Pages 418 - 450

https://doi.org/10.1145/65979.65983

Published: 01 July 1989 Publication History

Abstract

Mode and data dependency analyses find many applications in the generation of efficient executable code for logic programs. For example, mode information can be used to generate specialized unification instructions where permissible, to detect determinacy and functionality of programs, generate index structures more intelligently, reduce the amount of runtime tests in systems that support goal suspension, and in the integration of logic and functional languages. Data dependency information can be used for various source-level optimizing transformations, to improve backtracking behavior and to parallelize logic programs. This paper describes and proves correct an algorithm for the static inference of modes and data dependencies in a program. The algorithm is shown to be quite efficient for programs commonly encountered in practice.

References

[1]

BRUYNOOGHE, M., DEMOEN, B., CALLEBAUT, A., AND JANSSENS, C. Abstract interpretation: Towards the global optimization of Prolog programs. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San Francisco, Sept. 1987). IEEE, New York, 1987.

[2]

CHANG, J., DESPAIN, A. M., AND DEGROOT, D. AND-parallelism of logic programs based on a static data dependency analysis. In Digest of Papers, Compcon 85 (Feb. 1985). IEEE, New York, 1985.

[3]

CHANG, J., AND DESPAIN, A.M. Semi-intelligent backtracking of Prolog based on static data dependency analysis. In Proceedings of the 1985 Symposium on Logic Programming (Boston, July 1985). IEEE, New York, 1985, pp. 10-21.

[4]

COUSOT, P., AND COUSOT, R. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the Fourth Annual ACM Symposium on Principles of Programming Languages (1977). ACM, New York, 1977, pp. 238-252.

[5]

DEBRAY, S. K. Synthesizing control strategies for AND-parallel logic programs. Tech. Rep. 87-12, Dept. of Computer Science, Univ. of Arizona, Tucson, May 1987.

[6]

DEBRAY, S. K., AND WARREN, D. S. Automatic mode inference for logic programs, J. Logic Program. 5, 3 (Sept. 1988), 207-229.

[7]

DEBRA~, S.K. Unfold/fold transformations and loo~, optimization of logic programs. In Proceedings of the ACM SIGPLAN 1988 Conference on P 'ogramming Language Design and Implementation (Atlanta, Ga., June 1988). ACM, New York, 1988, 297-307. SIGPLAN Not. 23, 7.

[8]

DEBRAY, S. $., AND MISHRA, P. Denotational and operational semantics for Prolog. J. Logic Program. 5, I (Mar. 1988), 61-91.

[9]

DEBRAY, S. $., AND WARREN, D.S. Functional computations in logic programs. ACM Trans. Program. Lang. Syst. This issue, pp. 418-450.

[10]

DEERAY, S.K. Flow analysis of dynamic logic programs. J. Logic Program. 1989. To appear. (Preliminary version in Proceedings of the Fourth IEEI~ Symposium on Logic Programming (San Francisco, Sept. 1987)).

[11]

DERANSART, P., AND MAEUSZYNSKI, J. Relating logic programs and attribute grammars. J. Logic Program. 2, 2 (July 1985), 119-156.

[12]

DIETRICH, S.W. Extension tables: Memo relations in logic programming. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San ?rancisco, Sept. 1987). IEEE, New York, 1987, pp. 264-272.

[13]

JANSSENS, G., AND BRUYNOOGHE, M. An instance o ~ abstract interpretation integrating type and mode inferencing. In Proceedings of the Fifth International Conference on Logic Programming (Seattle, Wash., Aug. 1988). MIT Press, Cambridge, Mass., 1988, pp. 669-683.

[14]

JONES, N. D., AND MYCROFT, A. Stepwise development of operational and denotational semantics for PROLOG. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 289-298.

[15]

MANNILA, H., AND UKKONEN, E. Flow analysis of Prolog programs. In Proceedings of the Fourth IEEE Symposium on Logic Programming (San ?rancisco, Sept. 1987). IEEE, New York, 1987.

[16]

MELLISH, C. S. The automatic generation of mode declarations for Prolog programs. DAI Research Paper 163, Dept. of Artificial Intelligence, Univ. of Edinburgh, Aug. 1981.

[17]

MELL!SH, C.S. Some global optimizations for a Prolog compiler. J. Logic Program. 2, I (Apr. 1985), 43-66.

[18]

MELLISH, C. S. Abstract interpretation of Prolog ~rograms. In Proceedings of the Third International Logic Programming Conference (London, July 1986). LNCS 225, Springer, New York, 1986.

[19]

NAISH, L. Negation and Control in Prolog. LNCS 238, Springer, New York, 1986.

[20]

PLAISTED, D. The occur-check problem in Prolog. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 272-280.

[21]

REDD~, U.S. Transformation of logic programs into fimctional programs. In Proceedings of the 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984). IEEE, New York, 1984, pp. 187-196.

[22]

SONDERGAARD, H. An application of abstract interp :etation of logic programs: Occur check reduction. In Proceedings ESOP '86 (Saarbrucken, Mar 1986).

[23]

Sicstus Prolog User's Manual. Swedish Institute of Co mputer Science, Sweden, Sept. 1987.

[24]

TAMAKI, H., ANO SATO, T. OLD-resolution with tabulation. In Proceedings of the Third International Conference on Logic Programming (Londcn, July 1986). LNCS 225, Springer, New York, 1986.

[25]

VAN ROY, P., DEMOEN, B., AND WILLEMS, Y.D. Improving the execution speed of compiled Prolog with modes, clause selection and determinism. In Proceedings of TAPSOFT 1987 (Pisa, Mar. 1987).

[26]

WARREN, D. H.D. Implementing Prolog--compiling predicate logic programs. Res. Reps. 39 and 40, Dept. of Artificial Intelligence, Univ. of Edinbu~'gh, 1977.

[27]

WARREN, R., HERMENEGILDO, M., AND DEBRAY, S. K. On the practicality of global flow analysis of logic programs. In Proceedings of the Fifth In~ ernational Conference on Logic P~'ogramming (Seattle, Wash., Aug. 1988). MIT Press, Cambridge, Mass., 1988.

Cited By

Casso IMorales JLópez-García PGiacobazzi RHermenegildo M(2019)Computing Abstract Distances in Logic ProgramsLogic-Based Program Synthesis and Transformation10.1007/978-3-030-45260-5_4(57-72)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-45260-5_4
Zhou N(2016)Programming in PicatRule Technologies. Research, Tools, and Applications10.1007/978-3-319-42019-6_1(3-18)Online publication date: 28-Jun-2016
https://doi.org/10.1007/978-3-319-42019-6_1
Rojas JGómez-Zamalloa M(2013)A Framework for Guided Test Case Generation in Constraint Logic ProgrammingLogic-Based Program Synthesis and Transformation10.1007/978-3-642-38197-3_12(176-193)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38197-3_12
Show More Cited By

Index Terms

Static inference of modes and data dependencies in logic programs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Logic
    1. Constraint and logic programming
  2. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Semantics for disjunctive logic programs
SLGAD Resolution for Inference on Logic Programs with Annotated Disjunctions
RCRA 2008 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

Logic Programs with Annotated Disjunctions (LPADs) allow to express probabilistic information in logic programming. The semantics of an LPAD is given in terms of the well-founded models of the normal logic programs obtained by selecting one disjunct ...
Logic programming as classical inference

We propose a denotational semantics for logic programming based on a classical notion of logical consequence which is apt to capture the main proposed semantics of logic programs. In other words, we show that any of those semantics can be viewed as a ...

Reviews

Reviewer: Ralph Walter Wilkerson

The static inference of data dependency and mode information (i.e., input and output arguments) in logic programs serves an essential purpose in the generation of optimized code. By combining the analysis of these dependencies, Debray develops an algorithm that uses flow analysis techniques to handle dependencies between variables. The algorithm is carefully described and full attention is given to detailed aspects of the computation. The author also gives a formal proof of its soundness and an analysis of its complexity. The method is amply illustrated through numerous examples normally encountered in logic programming situations.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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 11, Issue 3

July 1989

137 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/65979

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1989 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1989

Published in TOPLAS Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
475
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Casso IMorales JLópez-García PGiacobazzi RHermenegildo M(2019)Computing Abstract Distances in Logic ProgramsLogic-Based Program Synthesis and Transformation10.1007/978-3-030-45260-5_4(57-72)Online publication date: 8-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-45260-5_4
Zhou N(2016)Programming in PicatRule Technologies. Research, Tools, and Applications10.1007/978-3-319-42019-6_1(3-18)Online publication date: 28-Jun-2016
https://doi.org/10.1007/978-3-319-42019-6_1
Rojas JGómez-Zamalloa M(2013)A Framework for Guided Test Case Generation in Constraint Logic ProgrammingLogic-Based Program Synthesis and Transformation10.1007/978-3-642-38197-3_12(176-193)Online publication date: 2013
https://doi.org/10.1007/978-3-642-38197-3_12
Vidal G(2012)Annotation of logic programs for independent and-parallelism by partial evaluation*Theory and Practice of Logic Programming10.1017/S147106841200019112:4-5(583-600)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1017/S1471068412000191
Albert EPuebla GHermenegildo M(2008)Abstraction-Carrying Code: a Model for Mobile Code SafetyNew Generation Computing10.1007/s00354-008-0039-726:2(171-204)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1007/s00354-008-0039-7
Strzalkowski T(2007)Reversible logic grammars for natural language parsing and generationComputational Intelligence10.1111/j.1467-8640.1990.tb00131.x6:3(145-171)Online publication date: 2-Apr-2007
https://doi.org/10.1111/j.1467-8640.1990.tb00131.x
Fan STanimoto S(2007)SnapshotsProceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing10.1109/VLHCC.2007.49(73-76)Online publication date: 23-Sep-2007
https://dl.acm.org/doi/10.1109/VLHCC.2007.49
Cox P(2007)Enhancing the Programmability of Spreadsheets with Logic ProgrammingProceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing10.1109/VLHCC.2007.18(87-94)Online publication date: 23-Sep-2007
https://dl.acm.org/doi/10.1109/VLHCC.2007.18
Hermenegildo MAlbert ELópez-García PPuebla GBarahona PFelty A(2005)Abstraction carrying code and resource-awarenessProceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming10.1145/1069774.1069775(1-11)Online publication date: 11-Jul-2005
https://dl.acm.org/doi/10.1145/1069774.1069775
De La Banda MHarvey WMarriott KStuckey PDemoen B(2005)Checking modes of HAL programsTheory and Practice of Logic Programming10.1017/S14710684040023275:6(623-667)Online publication date: 1-Nov-2005
https://dl.acm.org/doi/10.1017/S1471068404002327
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