Optimizing compilation of CLP(R)

Andrew D Kelly, Kim Marriott, Andrew Macdonald, Peter J. Stuckey, Roland Yap

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programing languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

Original languageEnglish
Pages (from-to)1223-1250
Number of pages28
JournalACM Transactions on Programming Languages and Systems
Volume20
Issue number6
DOIs
Publication statusPublished - 1 Nov 1998

Cite this

Kelly, Andrew D ; Marriott, Kim ; Macdonald, Andrew ; Stuckey, Peter J. ; Yap, Roland. / Optimizing compilation of CLP(R). In: ACM Transactions on Programming Languages and Systems. 1998 ; Vol. 20, No. 6. pp. 1223-1250.
@article{28f51fe25ad247458bdc90bb3acc840f,
title = "Optimizing compilation of CLP(R)",
abstract = "Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programing languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.",
author = "Kelly, {Andrew D} and Kim Marriott and Andrew Macdonald and Stuckey, {Peter J.} and Roland Yap",
year = "1998",
month = "11",
day = "1",
doi = "10.1145/295656.295661",
language = "English",
volume = "20",
pages = "1223--1250",
journal = "ACM Transactions on Programming Languages and Systems",
issn = "0164-0925",
publisher = "Association for Computing Machinery (ACM)",
number = "6",

}

Optimizing compilation of CLP(R). / Kelly, Andrew D; Marriott, Kim; Macdonald, Andrew; Stuckey, Peter J.; Yap, Roland.

In: ACM Transactions on Programming Languages and Systems, Vol. 20, No. 6, 01.11.1998, p. 1223-1250.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Optimizing compilation of CLP(R)

AU - Kelly, Andrew D

AU - Marriott, Kim

AU - Macdonald, Andrew

AU - Stuckey, Peter J.

AU - Yap, Roland

PY - 1998/11/1

Y1 - 1998/11/1

N2 - Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programing languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

AB - Constraint Logic Programming (CLP) languages extend logic programming by allowing the use of constraints from different domains such as real numbers or Boolean functions. They have proved to be ideal for expressing problems that require interactive mathematical modeling and complex combinatorial optimization problems. However, CLP languages have mainly been considered as research systems, useful for rapid prototyping, but not really competitive with more conventional programing languages where efficiency is a more important consideration. One promising approach to improving the performance of CLP systems is the use of powerful program optimizations to reduce the cost of constraint solving. We extend work in this area by describing a new optimizing compiler for the CLP language CLP(R). The compiler implements six powerful optimizations: reordering of constraints, bypass of the constraint solver, splitting and dead-code elimination, removal of redundant constraints, removal of redundant variables, and specialization of constraints which cannot fail. Each program optimization is designed to remove the overhead of constraint solving when possible and keep the number of constraints in the store as small as possible. We systematically evaluate the effectiveness of each optimization in isolation and in combination. Our empirical evaluation of the compiler verifies that optimizing compilation can be made efficient enough to allow compilation of real-world programs and that it is worth performing such compilation because it gives significant time and space performance improvements.

UR - http://www.scopus.com/inward/record.url?scp=0032256524&partnerID=8YFLogxK

U2 - 10.1145/295656.295661

DO - 10.1145/295656.295661

M3 - Article

VL - 20

SP - 1223

EP - 1250

JO - ACM Transactions on Programming Languages and Systems

JF - ACM Transactions on Programming Languages and Systems

SN - 0164-0925

IS - 6

ER -