Search Results

Documents authored by De Roover, Coen

Document
Artifact
DOI: 10.4230/DARTS.5.2.7
Garbage-Free Abstract Interpretation Through Abstract Reference Counting (Artifact)

Authors: Noah Van Es, Quentin Stiévenart, and Coen De Roover

Published in: DARTS, Volume 5, Issue 2, Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
This artifact is a modified version of Scala-AM, an abstract interpretation framework implemented in Scala. Specifically, we extended Scala-AM with several implementations of machine abstractions that each employ a different approach to abstract garbage collection. These include traditional (tracing-based) approaches to abstract garbage collection, as well as our own novel approach using abstract reference counting. In particular, using the machine abstraction that employs abstract reference counting (with cycle detection) results in a garbage-free abstract interpreter can greatly improve both the precision and performance of the corresponding machine abstraction in the original version of the Scala-AM framework. We have set up the framework in such a way that one can easily run a variety of experiments to use, evaluate and compare these approaches to abstract garbage collection. This artifact contains documentation on how these experiments can be configured, specifically to reproduce the results presented in the companion paper.
Cite as

Noah Van Es, Quentin Stiévenart, and Coen De Roover. Garbage-Free Abstract Interpretation Through Abstract Reference Counting (Artifact). In Special Issue of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Dagstuhl Artifacts Series (DARTS), Volume 5, Issue 2, pp. 7:1-7:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{vanes_et_al:DARTS.5.2.7,
  author =	{Van Es, Noah and Sti\'{e}venart, Quentin and De Roover, Coen},
  title =	{{Garbage-Free Abstract Interpretation Through Abstract Reference Counting}},
  pages =	{7:1--7:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2019},
  volume =	{5},
  number =	{2},
  editor =	{Van Es, Noah and Sti\'{e}venart, Quentin and De Roover, Coen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.2.7},
  URN =		{urn:nbn:de:0030-drops-107843},
  doi =		{10.4230/DARTS.5.2.7},
  annote =	{Keywords: static analysis, abstract interpretation, abstract garbage collection, reference counting}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2019.10
Garbage-Free Abstract Interpretation Through Abstract Reference Counting

Authors: Noah Van Es, Quentin Stiévenart, and Coen De Roover

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)

Abstract
Abstract garbage collection is the application of garbage collection to an abstract interpreter. Existing work has shown that abstract garbage collection can improve both the interpreter’s precision and performance. Current approaches rely on heuristics to decide when to apply abstract garbage collection. Garbage will build up and impact precision and performance when the collection is applied infrequently, while too frequent applications will bring about their own performance overhead. A balance between these tradeoffs is often difficult to strike. We propose a new approach to cope with the buildup of garbage in the results of an abstract interpreter. Our approach is able to eliminate all garbage, therefore obtaining the maximum precision and performance benefits of abstract garbage collection. At the same time, our approach does not require frequent heap traversals, and therefore adds little to the interpreters’s running time. The core of our approach uses reference counting to detect and eliminate garbage as soon as it arises. However, reference counting cannot deal with cycles, and we show that cycles are much more common in an abstract interpreter than in its concrete counterpart. To alleviate this problem, our approach detects cycles and employs reference counting at the level of strongly connected components. While this technique in general works for any system that uses reference counting, we argue that it works particularly well for an abstract interpreter. In fact, we show formally that for the continuation store, where most of the cycles occur, the cycle detection technique only requires O(1) amortized operations per continuation push. We present our approach formally, and provide a proof-of-concept implementation in the Scala-AM framework. We empirically show our approach achieves both the optimal precision and significantly better performance compared to existing approaches to abstract garbage collection.
Cite as

Noah Van Es, Quentin Stiévenart, and Coen De Roover. Garbage-Free Abstract Interpretation Through Abstract Reference Counting. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 10:1-10:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vanes_et_al:LIPIcs.ECOOP.2019.10,
  author =	{Van Es, Noah and Sti\'{e}venart, Quentin and De Roover, Coen},
  title =	{{Garbage-Free Abstract Interpretation Through Abstract Reference Counting}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{10:1--10:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.10},
  URN =		{urn:nbn:de:0030-drops-108022},
  doi =		{10.4230/LIPIcs.ECOOP.2019.10},
  annote =	{Keywords: abstract interpretation, abstract garbage collection, reference counting}
}
Document
DOI: 10.4230/DARTS.3.2.11
Mailbox Abstractions for Static Analysis of Actor Programs (Artifact)

Authors: Quentin Stiévenart, Jens Nicolay, Wolfgang De Meuter, and Coen De Roover

Published in: DARTS, Volume 3, Issue 2, Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
This artifact is based on Scala-AM, a static analysis framework relying on the Abstracting Abstract Machines approach. This version of the framework is extended to support actor-based programs, written in a variant of Scheme. The sound static analysis is performed in order to verify the absence of errors in actor-based program, and to compute upper bounds on actor's mailboxes. We developed several mailbox abstractions with which the static analysis can be run, and evaluate the precision of the technique with these mailbox abstractions. This artifact contains documentation on how to use analysis and on how to reproduce the results presented in the companion paper.
Cite as

Quentin Stiévenart, Jens Nicolay, Wolfgang De Meuter, and Coen De Roover. Mailbox Abstractions for Static Analysis of Actor Programs (Artifact). In Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). Dagstuhl Artifacts Series (DARTS), Volume 3, Issue 2, pp. 11:1-11:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{stievenart_et_al:DARTS.3.2.11,
  author =	{Sti\'{e}venart, Quentin and Nicolay, Jens and De Meuter, Wolfgang and De Roover, Coen},
  title =	{{Mailbox Abstractions for Static Analysis of Actor Programs (Artifact)}},
  pages =	{11:1--11:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2017},
  volume =	{3},
  number =	{2},
  editor =	{Sti\'{e}venart, Quentin and Nicolay, Jens and De Meuter, Wolfgang and De Roover, Coen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.3.2.11},
  URN =		{urn:nbn:de:0030-drops-72920},
  doi =		{10.4230/DARTS.3.2.11},
  annote =	{Keywords: static analysis, abstraction, abstract interpretation, actors, mailbox}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2017.25
Mailbox Abstractions for Static Analysis of Actor Programs

Authors: Quentin Stiévenart, Jens Nicolay, Wolfgang De Meuter, and Coen De Roover

Published in: LIPIcs, Volume 74, 31st European Conference on Object-Oriented Programming (ECOOP 2017)

Abstract
Properties such as the absence of errors or bounds on mailbox sizes are hard to deduce statically for actor-based programs. This is because actor-based programs exhibit several sources of unboundedness, in addition to the non-determinism that is inherent to the concurrent execution of actors. We developed a static technique based on abstract interpretation to soundly reason in a finite amount of time about the possible executions of an actor-based program. We use our technique to statically verify the absence of errors in actor-based programs, and to compute upper bounds on the actors' mailboxes. Sound abstraction of these mailboxes is crucial to the precision of any such technique. We provide several mailbox abstractions and categorize them according to the extent to which they preserve message ordering and multiplicity of messages in a mailbox. We formally prove the soundness of each mailbox abstraction, and empirically evaluate their precision and performance trade-offs on a corpus of benchmark programs. The results show that our technique can statically verify the absence of errors for more benchmark programs than the state-of-the-art analysis.
Cite as

Quentin Stiévenart, Jens Nicolay, Wolfgang De Meuter, and Coen De Roover. Mailbox Abstractions for Static Analysis of Actor Programs. In 31st European Conference on Object-Oriented Programming (ECOOP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 74, pp. 25:1-25:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{stievenart_et_al:LIPIcs.ECOOP.2017.25,
  author =	{Sti\'{e}venart, Quentin and Nicolay, Jens and De Meuter, Wolfgang and De Roover, Coen},
  title =	{{Mailbox Abstractions for Static Analysis of Actor Programs}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{25:1--25:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{M\"{u}ller, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2017.25},
  URN =		{urn:nbn:de:0030-drops-72541},
  doi =		{10.4230/LIPIcs.ECOOP.2017.25},
  annote =	{Keywords: static analysis, abstraction, abstract interpretation, actors, mailbox}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact