Abstract interpretation for constraint handling rules

Tom Schrijvers; Peter J. Stuckey; Gregory J. Duck

Abstract interpretation for constraint handling rules

Tom Schrijvers
, Peter J. Stuckey
, Gregory J. Duck

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

Program analysis is essential for the optimized compilation of Constraint Handling Rules (CHRs) as well as the inference of behavioral properties such as confluence and termination. Up to now all program analyses for CHRs have been developed in an ad hoc fashion. In this work we bring the general program analysis methodology of abstract interpretation to CHRs: we formulate an abstract interpretation framework over the call-based operational semantics of CHRs. The abstract interpretation framework is non-obvious since it needs to handle the highly non-deterministic execution of CHRs. The use of the framework is illustrated with two instantiations: the CHR-specific late storage analysis and the more generally known groundness analysis. In addition, we discuss optimizations based on these analyses and present experimental results.

Original language	English
Title of host publication	PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming
Pages	218-229
Number of pages	12
Publication status	Published - 1 Dec 2005
Externally published	Yes
Event	ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2005 - Lisbon, Portugal Duration: 11 Jul 2005 → 13 Jul 2005 Conference number: 7th

Publication series

Name	PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming
Volume	2005

Conference

Conference	ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2005
Abbreviated title	PPDP'05
Country/Territory	Portugal
City	Lisbon
Period	11/07/05 → 13/07/05

Keywords

Abstract interpretation
Constraint Handling Rules

Cite this

@inproceedings{4dc809083ca8414ea53cfc7e6a142ceb,

title = "Abstract interpretation for constraint handling rules",

abstract = "Program analysis is essential for the optimized compilation of Constraint Handling Rules (CHRs) as well as the inference of behavioral properties such as confluence and termination. Up to now all program analyses for CHRs have been developed in an ad hoc fashion. In this work we bring the general program analysis methodology of abstract interpretation to CHRs: we formulate an abstract interpretation framework over the call-based operational semantics of CHRs. The abstract interpretation framework is non-obvious since it needs to handle the highly non-deterministic execution of CHRs. The use of the framework is illustrated with two instantiations: the CHR-specific late storage analysis and the more generally known groundness analysis. In addition, we discuss optimizations based on these analyses and present experimental results.",

keywords = "Abstract interpretation, Constraint Handling Rules",

author = "Tom Schrijvers and Stuckey, \{Peter J.\} and Duck, \{Gregory J.\}",

year = "2005",

month = dec,

day = "1",

language = "English",

isbn = "1595930906",

series = "PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming",

pages = "218--229",

booktitle = "PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming",

note = "ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2005, PPDP'05 ; Conference date: 11-07-2005 Through 13-07-2005",

}

Schrijvers, T, Stuckey, PJ & Duck, GJ 2005, Abstract interpretation for constraint handling rules. in PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, vol. 2005, pp. 218-229, ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2005, Lisbon, Portugal, 11/07/05.

Abstract interpretation for constraint handling rules. / Schrijvers, Tom; Stuckey, Peter J.; Duck, Gregory J.
PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. 2005. p. 218-229 (PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Abstract interpretation for constraint handling rules

AU - Schrijvers, Tom

AU - Stuckey, Peter J.

AU - Duck, Gregory J.

N1 - Conference code: 7th

PY - 2005/12/1

Y1 - 2005/12/1

N2 - Program analysis is essential for the optimized compilation of Constraint Handling Rules (CHRs) as well as the inference of behavioral properties such as confluence and termination. Up to now all program analyses for CHRs have been developed in an ad hoc fashion. In this work we bring the general program analysis methodology of abstract interpretation to CHRs: we formulate an abstract interpretation framework over the call-based operational semantics of CHRs. The abstract interpretation framework is non-obvious since it needs to handle the highly non-deterministic execution of CHRs. The use of the framework is illustrated with two instantiations: the CHR-specific late storage analysis and the more generally known groundness analysis. In addition, we discuss optimizations based on these analyses and present experimental results.

AB - Program analysis is essential for the optimized compilation of Constraint Handling Rules (CHRs) as well as the inference of behavioral properties such as confluence and termination. Up to now all program analyses for CHRs have been developed in an ad hoc fashion. In this work we bring the general program analysis methodology of abstract interpretation to CHRs: we formulate an abstract interpretation framework over the call-based operational semantics of CHRs. The abstract interpretation framework is non-obvious since it needs to handle the highly non-deterministic execution of CHRs. The use of the framework is illustrated with two instantiations: the CHR-specific late storage analysis and the more generally known groundness analysis. In addition, we discuss optimizations based on these analyses and present experimental results.

KW - Abstract interpretation

KW - Constraint Handling Rules

UR - https://www.scopus.com/pages/publications/33746032976

M3 - Conference Paper

AN - SCOPUS:33746032976

SN - 1595930906

SN - 9781595930903

T3 - PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming

SP - 218

EP - 229

BT - PPDP'05 - Proceedings of the Seventh ACM SIGPLAN Conference on Principles and Practice of Declarative Programming

T2 - ACM SIGPLAN Conference on Principles and Practice of Declarative Programming 2005

Y2 - 11 July 2005 through 13 July 2005

ER -

Abstract interpretation for constraint handling rules

Abstract

Publication series

Conference

Keywords

Other files and links

Cite this