3 R's of optimizing constraint logic programs: Refinement, removal and reordering

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

33 Citations (Scopus)

Abstract

Central to constraint logic programming (CLP) languages is the notion of a global constraint solver which is queried to direct execution and to which constraints are monotonically added. We present a methodology for use in the compilation of CLP languages which is designed to reduce the overhead of the global constraint solver. This methodology is based on three optimizations. The first, refinement, involves adding new constraints, which in effect make information available earlier in the computation, guiding subsequent execution away from unprofitable choices. The second, removal, involves eliminating constraints from the solver when they are redundant. The last, reordering, involves moving constraint addition later and constraint removal earlier in the computation. Determining the applicability of each optimization requires sophisticated global analysis. These analyses are based on abstract interpretation and provide information about potential and definite interaction between constraints.

Original languageEnglish
Title of host publicationConference Record of the Annual ACM Symposium on Principles of Programming Languages
PublisherAssociation for Computing Machinery (ACM)
Pages334-344
Number of pages11
ISBN (Print)0897915607
Publication statusPublished - 1 Jan 1993
Externally publishedYes
EventAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 1993 - Charleston, SC, USA
Duration: 10 Jan 199313 Jan 1993
Conference number: 20th

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

Conference

ConferenceAnnual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages 1993
CityCharleston, SC, USA
Period10/01/9313/01/93

Cite this

Marriott, K., & Stuckey, P. J. (1993). 3 R's of optimizing constraint logic programs: Refinement, removal and reordering. In Conference Record of the Annual ACM Symposium on Principles of Programming Languages (pp. 334-344). (Conference Record of the Annual ACM Symposium on Principles of Programming Languages). Association for Computing Machinery (ACM).