Suspension Analyses for Concurrent Logic Programs

Michael Codish, Moreno Falaschi, Kim Marriott

Research output: Contribution to journalArticleResearchpeer-review

29 Citations (Scopus)

Abstract

Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies. However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.

Original languageEnglish
Pages (from-to)649-686
Number of pages38
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Volume16
Issue number3
DOIs
Publication statusPublished - 5 Jan 1994
Externally publishedYes

Keywords

  • abstract interpretation
  • concurrent logic programming
  • program analysis

Cite this

@article{bcf3b79081ea467e9a2603382cfe792d,
title = "Suspension Analyses for Concurrent Logic Programs",
abstract = "Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies. However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.",
keywords = "abstract interpretation, concurrent logic programming, program analysis",
author = "Michael Codish and Moreno Falaschi and Kim Marriott",
year = "1994",
month = "1",
day = "5",
doi = "10.1145/177492.177656",
language = "English",
volume = "16",
pages = "649--686",
journal = "ACM Transactions on Programming Languages and Systems",
issn = "0164-0925",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

Suspension Analyses for Concurrent Logic Programs. / Codish, Michael; Falaschi, Moreno; Marriott, Kim.

In: ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 16, No. 3, 05.01.1994, p. 649-686.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Suspension Analyses for Concurrent Logic Programs

AU - Codish, Michael

AU - Falaschi, Moreno

AU - Marriott, Kim

PY - 1994/1/5

Y1 - 1994/1/5

N2 - Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies. However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.

AB - Concurrent logic languages specify reactive systems which consist of collections of communicating processes. The presence of unintended suspended computations is a common programming error which is difficult to detect using standard debugging and testing techniques. We develop a number of analyses, based on abstract interpretation, which succeed if a program is definitely suspension free. If an analysis fails, the program may, or may not, be suspension free. Examples demonstrate that the analyses are practically useful. They are conceptually simple and easy to justify because they are based directly on the transition system semantics of concurrent logic programs. A naive analysis must consider all scheduling policies. However, it is proven that for our analyses it suffices to consider only one scheduling policy, allowing for efficient implementation.

KW - abstract interpretation

KW - concurrent logic programming

KW - program analysis

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

U2 - 10.1145/177492.177656

DO - 10.1145/177492.177656

M3 - Article

VL - 16

SP - 649

EP - 686

JO - ACM Transactions on Programming Languages and Systems

JF - ACM Transactions on Programming Languages and Systems

SN - 0164-0925

IS - 3

ER -