Article

Free access

Analyzing logic programs with dynamic scheduling

Authors:

María José García de la Banda,

Manuel HermenegildoAuthors Info & Claims

POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 240 - 253

https://doi.org/10.1145/174675.177883

Published: 01 February 1994 Publication History

Abstract

Traditional logic programming languages, such as Prolog, use a fixed left-to-right atom scheduling rule. Recent logic programming languages, however, usually provide more flexible scheduling in which computation generally proceed left-to-right but in which some calls are dynamically “delayed” until their arguments are sufficiently instantiated to allow the call to run efficiently. Such dynamic scheduling has a significant cost. We give a framework for the global analysis of logic programming languages with dynamic scheduling and show that program analysis based on this framework supports optimizations which remove much of the overhead of dynamic scheduling.

References

[1]

M. Carlsson. Freeze, Indexing, and Other Implementation Issues in the Warn. In Fourth International Conference on Logic Programming, pages 40-58. University of Melbourne, MIT Press, May 1987.

[2]

M. Carlsson. Sicstus Protog User's Manual. Po Box 1263, S-16313 Spanga, Sweden, February 1988.

[3]

M. Codish. A Provably Correct Algorithm for Sharing and Freeness Inference. In 1992 Workshop on Static Analysis WSA'92, September 1992.

[4]

M. Codish, M. Fataschi, and K. Marriott. Suspension Analysis for Concurrent Logic Programs. In K. Furukawa, editor, Proc. Eighth Int'l Conf. on Logic Programming, pages 331- 345. The MIT Press, Cambridge, Mass., 1991.

[5]

M. Codish, M. Falaschi, K. Marriott and W. Winsborough. Efficient analysis of concurrent constraint logic programs. Proc. of Twentieth Int. Coll. Automata, Languages and Programming, A. Lingus and R. Karlsson and S. Carlsson (Ed.), LNCS Springer Verlag, pages 633-644.

Digital Library

[6]

C. Codognet, P. Codognet, and M. Corsini. Abstract Interpretation for Concurrent Logic Languages. In S. Debray and M. Hermenegildo, editors, Proc. North American Con}. on Logic Programming'90, pages 215- 232. The MIT Press, Cambridge, Mass., 1990.

Digital Library

[7]

P. Cousot and R. Cousot. Abstract Interpretation: a Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. Proc. of the Fourth A CM Symposium on Principles of Programming Languages, 238-252, 1977.

Digital Library

[8]

P. Cousot and R. Cousot. Comparing the Galois Connection and Widening/Narrowing Approaches to Abstract Interpretation. Technical report, LIX, Ecole Polytechnique, France, 1991.

[9]

P. Cousot and R. Cousot. Abstract Interpretation and Application to Logic Programs. journal of Logic Programming, 13(2 and 3):103-179, July 1992.

Digital Library

[10]

g. Dehray. ~tatic Analysi~ of Parallel Logic Programs. In Fi~h Int'l Conference and Symposium on Logic Programming, Seattle,Wasinghton, August 1988. MIT Press.

[11]

S. K. Debray. Static Inference of Modes and Data Dependencies in Logic Programs. ACM Transactions on Programming Languages and Systems 11 (3), 418-450, 1989.

Digital Library

[12]

S.K. Debray. QD-Janus: A Sequential Implementation of Janus in Prolog. Technical Report, University of Arizona, 1993.

[13]

S. K. Debray and D. S. Warren. Functional Computations in Logic Programs. A CM Transactions on Programming Languages and Systems 11 (3), 451-481, 1989.

Digital Library

[14]

M. Falaschi, M. Gabbrielh, K. Marriott and C. Palamidessi. Compositional analysis for concurrent constraint programming. IEEE Symposium on Logic in Computer Science, Montreal, June 1993.

[15]

M. Garcia de la Panda and M. Hermenegildo. A Practical Application of Sharing and Freeness Inference. In 1992 Workshop on Static Analysis WSA '92, pages 118- 125, Bourdeaux, France, September 1992.

[16]

D. Gudeman, K. De Bosschere and S.K. Debray. jc: An Efficient and Portable Sequential Implementation of Janus. In Proc. of 1992 Joint International Conference and Symposium on Logic Programming, 399-413. MIT Press, November 1992.

[17]

M. Hanus. On the Completeness of Residuation. In posium on Logic Programming, 192-206. MIT Press, November 1992.

[18]

M. Hanus. Analysis of Nonlinear Constraints in CLP(R). In Proc. of 1993 International Conference on Logic Programming, 83-99. MIT Press, June 1993.

Digital Library

[19]

M. Hermenegildo and K. Greene. ~-Prolog and its Performance: Exploiting Independent And-Parallelism. In 1990 International Conference on Logic Programming, pages 253-268. MIT Press, June 1990.

Digital Library

[20]

M. Hermenegildo, R. Warren, and S. Debray. Global Flow Analysis as a Practical Compilation Tool. Journal of Logic Programming, 3(4):349-367, August 1992.

Digital Library

[21]

T. Hickey and S. Mudambi. GlobM Compilation of Prolog. Journal of Logic Programming, 7, 193-230, 1989.

Digital Library

[22]

J. Jaffar and J.-L. Lassez. Constraint Logic Programming. In Proc. Fourteenth Ann. A CM Syrup. Principles of Programming Languages, pages 111-119, 1987.

Digital Library

[23]

N. D. Jones and A. Mycroft. Dataflow analysis of applicative programs using minimal function graphs. In Proc. Thirteenth Ann. A CM Syrup. Principles of Programming Languages, pages 296-306. St. Petersburg, Florida, 1986.

Digital Library

[24]

K. Marriott, H. Sendergaard, and P. Dart. A characterization of non-floundering logic programs. In S. K. Debray emd M. Hermenegildo, editors, Logic Programming: Proc. North American Conf. 19g0, pages 661- 680. MIT Press, 1990.

Digital Library

[25]

K. Marriott, H. SOndergaard and N. D. Jones. Deno- ~eL%;onaI abs~rac~ ~n~erpre~~~1on o~ logic programs. To appear in A CM Trans. Programming Languages and Systems.

Digital Library

[26]

C. S. Mellish. The automatic generation of mode declarations for Prolog programs. Technical Report 163, Dept. of Artificial Intelligence, University of Edinburgh, Scotland, 1981.

[27]

K. Muthukumar and M. Hermenegildo. The CDG, UDG, and MEL Methods for Automatic Compiletime Parallelization of Logic Programs for Independent And-parallelism. In 1990 International Conference on Logic Programming, pages 221-237. MIT Press, June 1990.

Digital Library

[28]

K. Muthukumar and M. Hermenegildo. Combined Determination of Sharing and Freeness of Program Variables Through Abstract Interpretation. In 1991 International Con}erence on Logic Programming, pages 49-63. MIT Press, June 1991.

[29]

K. Muthukumar and M. Hermenegildo. Compile-time Derivation of Variable Dependency Using Abstract Interpretation. Journal of Logic Programming, 13(2 and 3):315-347, July 1992.

Digital Library

[30]

L. Naish. Negation and Control in Prolog, LNCS 238, Springer-Verlag, 1985.

Digital Library

[31]

A. Taylor. LIPS on a MIPS: Results from a Prolog Compiler for a RISC. Proc. of the 7th International Conference on Logic Programming, 174-185, 1990.

Digital Library

[32]

P. Van Roy and A.M. Despain. The Benefits of Global Dataflow Analysis for an Optimizing Prolog Compiler. Proc. of the 1990 North American Con}erence on Logic Programming, 501-515, 1990.

Digital Library

[33]

R. Warren, M. Hermenegildo and S.K. Debray. On the Practicality of Global Flow Analysis of Logic Programs. Proc. of the 5th International Con}erence and Symposium on Logic Programming, 684-699, 1988.

[34]

K. Yelick and J. Zachary. Moded type systems for logic programming. In Proc. Sixteenth Annual A CM Syrup. on Principles o} Programming Languages, pages 116- 124. ACM, 1989.

Digital Library

Cited By

DOVIER AFORMISANO AGUPTA GHERMENEGILDO MPONTELLI EROCHA R(2022)Parallel Logic Programming: A SequelTheory and Practice of Logic Programming10.1017/S147106842200005922:6(905-973)Online publication date: 28-Mar-2022
https://doi.org/10.1017/S1471068422000059
Naish L(2012)Declarative diagnosis of floundering in prologProceedings of the Thirty-fifth Australasian Computer Science Conference - Volume 12210.5555/2483654.2483660(49-56)Online publication date: 30-Jan-2012
https://dl.acm.org/doi/10.5555/2483654.2483660
Genaim SKing A(2008)Inferring non-suspension conditions for logic programs with dynamic schedulingACM Transactions on Computational Logic10.1145/1352582.13525859:3(1-43)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1352582.1352585
Show More Cited By

Index Terms

Analyzing logic programs with dynamic scheduling
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
2. Theory of computation
  1. Logic
    1. Constraint and logic programming

Recommendations

Semantics for disjunctive logic programs
Sequential Dynamic Logic

We introduce a substructural propositional calculus of Sequential Dynamic Logic that subsumes a propositional part of dynamic predicate logic, and is shown to be expressively equivalent to propositional dynamic logic. Completeness of the calculus with ...
A Dynamic Logic-Based Modal Prolog
MICAI '12: Proceedings of the 2012 11th Mexican International Conference on Artificial Intelligence

The field of modal logic programming has been developed to extend the expressiveness of logic programming. By introducing the modal operators of necessity and possibility within the language of Horn clauses, modal logic programming languages retain its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

February 1994

492 pages

ISBN:0897916360

DOI:10.1145/174675

Chairmen:
Hans-J. Boehm
Xerox PARC
,
Bernard Lang
INRIA Rocquencourt
,
Daniel Yellin
IBM Watson Research Center

Copyright © 1994 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL94

Sponsor:

POPL94: 21st ACM SIGPLAN/SIGACT Symposium on Principles of Programming Languages

January 16 - 19, 1994

Oregon, Portland, USA

Acceptance Rates

POPL '94 Paper Acceptance Rate 39 of 173 submissions, 23%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

DOVIER AFORMISANO AGUPTA GHERMENEGILDO MPONTELLI EROCHA R(2022)Parallel Logic Programming: A SequelTheory and Practice of Logic Programming10.1017/S147106842200005922:6(905-973)Online publication date: 28-Mar-2022
https://doi.org/10.1017/S1471068422000059
Naish L(2012)Declarative diagnosis of floundering in prologProceedings of the Thirty-fifth Australasian Computer Science Conference - Volume 12210.5555/2483654.2483660(49-56)Online publication date: 30-Jan-2012
https://dl.acm.org/doi/10.5555/2483654.2483660
Genaim SKing A(2008)Inferring non-suspension conditions for logic programs with dynamic schedulingACM Transactions on Computational Logic10.1145/1352582.13525859:3(1-43)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1352582.1352585
Hermenegildo MPuebla GBueno FLópez-García P(2005)Integrated program debugging, verification, and optimization using abstract interpretation (and the Ciao system preprocessor)Science of Computer Programming10.1016/j.scico.2005.02.00658:1-2(115-140)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.scico.2005.02.006
Ohno KIkawa MGoshimai MMori SNakashima HTomita S(2005)Efficient goal scheduling in a concurrent logic language using type-based dependency analysisAdvances in Computing Science — ASIAN'9710.1007/3-540-63875-X_58(268-282)Online publication date: 1-Aug-2005
https://doi.org/10.1007/3-540-63875-X_58
Boer FGabbrielli MPalamidessi C(2005)Proving correctness of Constraint Logic Programs with dynamic schedulingStatic Analysis10.1007/3-540-61739-6_35(83-97)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-61739-6_35
Banda MHermenegildo MMarriott K(2005)Independence in dynamically scheduled logic languagesAlgebraic and Logic Programming10.1007/3-540-61735-3_3(47-61)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-61735-3_3
Hanus MZartmann F(2005)Mode analysis of functional logic programsStatic Analysis10.1007/3-540-58485-4_31(26-42)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-58485-4_31
Genaim SKing A(2003)Goal-independent suspension analysis for logic programs with dynamic schedulingProceedings of the 12th European conference on Programming10.5555/1765712.1765721(84-98)Online publication date: 7-Apr-2003
https://dl.acm.org/doi/10.5555/1765712.1765721
Hermenegildo MPuebla GBueno FLópez-García P(2003)Program development using abstract interpretation (and the ciao system preprocessor)Proceedings of the 10th international conference on Static analysis10.5555/1760267.1760278(127-152)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.5555/1760267.1760278
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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 Table of Contents