Alexandre Moine
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Alexandre Moine has a total of 12 co-authors. Here are the top co-authors by number of shared publications:
- Sam Westrick
New York University, New York, USA
4 shared publications - François Pottier
INRIA, Paris, France
3 shared publications - Arthur Charguéraud
Inria, Strasbourg, France
2 shared publications - Joseph Tassarotti
New York University, New York, USA
2 shared publications - Stephanie Balzer
Carnegie Mellon University, Pittsburgh, USA
2 shared publications - Alex Xu
Carnegie Mellon University, Pittsburgh, USA
1 shared publication
Latest Publications
- Open Access
- 17 August 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (ICFP) , 174-203
A Separation Logic for Parallel Time Complexity with Work and Span Credits
We present Parcas, a concurrent separation logic for verifying the parallel time complexity of fork-join programs. In order to abstract from the specifics of the machine, time complexity for parallel programs is given in terms of two metrics: the work, measuring the total number of operations, and the span, measuring the longest chain of sequential dependencies. Together, these two metrics determine the running time on any number of processors. For proving bounds on the work and span, Parcas is equipped with work credits and span credits, logical devices that represent permissions to incur costs. Work credits are a straightforward adaptation of time credits, a standard tool for bounding time complexity of sequential programs, and can be split additively between parallel tasks. Span credits, however, require a fundamentally different treatment. Indeed, the span of the parallel composition of two tasks is the maximum of the span of the two tasks. To account for this, we propose a rule for duplicating span credits at fork points, with each copy tagged by a logical task identifier that restricts which task may spend them. A transfer rule allows unused span credits to be forwarded across sequential compositions to subsequent tasks. The logic is expressive enough to give modular, higher-order specifications for common parallel primitives such as a parallel for loop and a tabulate function. We demonstrate Parcas on several case studies, including parallel prefix sums, parallel merge sort, and a variant of Treiber’s lock-free stack that mixes concurrency with parallelism. All the presented results are mechanized in the Rocq prover using the Iris separation logic framework.
- 17 August 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (ICFP) , 174-203
Open AccessA Separation Logic for Parallel Time Complexity with Work and Span Credits
We present Parcas, a concurrent separation logic for verifying the parallel time complexity of fork-join programs. In order to abstract from the specifics of the machine, time complexity for parallel programs is given in terms of two metrics: the work, measuring the total number of operations, and the span, measuring the longest chain of sequential dependencies. Together, these two metrics determine the running time on any number of processors. For proving bounds on the work and span, Parcas is equipped with work credits and span credits, logical devices that represent permissions to incur costs. Work credits are a straightforward adaptation of time credits, a standard tool for bounding time complexity of sequential programs, and can be split additively between parallel tasks. Span credits, however, require a fundamentally different treatment. Indeed, the span of the parallel composition of two tasks is the maximum of the span of the two tasks. To account for this, we propose a rule for duplicating span credits at fork points, with each copy tagged by a logical task identifier that restricts which task may spend them. A transfer rule allows unused span credits to be forwarded across sequential compositions to subsequent tasks. The logic is expressive enough to give modular, higher-order specifications for common parallel primitives such as a parallel for loop and a tabulate function. We demonstrate Parcas on several case studies, including parallel prefix sums, parallel merge sort, and a variant of Treiber’s lock-free stack that mixes concurrency with parallelism. All the presented results are mechanized in the Rocq prover using the Iris separation logic framework.
- 8 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Formal verification of heap space bounds under garbage collection : a space tale from the stars
Vérification formelle de bornes en espace de tas en présence d'un glaneur de cellules : un conte spatial venu des étoiles: Cette thèse aborde le problème du raisonnement formel sur l'utilisation de l'espace de tas (heap space) des programmes concurrents en présence d'un glaneur de cellules (garbage collector). Alors qu'il est facile d'identifier où l'espace est consommé, c'est-à-dire les points d'allocations, la présence d'un glaneur de cellules rend délicat de déterminer où l'espace est libéré, les points de désallocations étant implicites. En effet, le glaneur de cellules peut s'exécuter à n'importe quel moment pour désallouer des blocs mémoires inaccessibles, c'est-à-dire les blocs qui ne sont pas transitivement accessibles depuis les adresses racines (roots) du code restant à exécuter. Une question centrale à cette thèse est donc: comment raisonner sur l'inaccessibilité ? Pour répondre à cette question, nous proposons IrisFit, une nouvelle logique de séparation construite au-dessus du cadre logique Iris. IrisFit garde trace de l'accessibilité des blocs mémoire en équipant chaque adresse d'une assertion pointed-by-heap et d'une assertion pointed-by-thread, enregistrant respectivement quel bloc mémoire accessible pointe vers cette adresse et quel fil (thread) considère cette adresse comme une racine. De plus, IrisFit exploite la notion de crédits-espace, un outil purement logique qui garde trace de la quantité d'espace libre disponible. Des crédits-espace sont consommés par les allocations et peuvent être récupérés en prouvant qu'un bloc mémoire est inaccessible. Au cours de cette thèse, nous avons identifié une difficulté fondamentale dans l'analyse de la complexité en espace de tas au pire cas des programmes concurrents en présence d'un glaneur de cellules. En effet, si l'exécution du glaneur de cellules et la réduction des fils peuvent s'entrelacer de manière arbitraire, alors il existe des scénarios indésirables dans lesquels une racine retenue par un fil endormi empêche la désallocation d'une quantité de mémoire possiblement grande. Pour remédier à ce problème, nous proposons deux nouvelles constructions: les sections protégées, dans lesquelles le glaneur de cellules n'a pas le droit de s'exécuter, et les points de polling, des instructions qui bloquent le fil courant si un autre fil requiert l'exécution du glaneur de cellules. Les sections protégées peuvent être exploitées par le programmeur pour éliminer les scénarios indésirables décrits ci-dessus, permettant ainsi d'obtenir une meilleure complexité en espace de tas au pire cas. Les points de polling, quant à eux, peuvent être insérés par le compilateur pour garantir qu'aucun fil n'attend indéfiniment que le glaneur de cellules s'exécute. Nous étendons IrisFit pour permettre de raisonner sur les sections protégées. Nous prouvons qu'IrisFit offre une garantie de sûreté (les programmes vérifiés ne peuvent pas produire une erreur et n'excèdent pas une borne donnée en espace de tas) et une garantie de vivacité (il existe une stratégie d'insertion des points de polling dans les programmes vérifiés garantissant que chaque requête d'allocation sera satisfaite après un nombre de pas borné). Nous illustrons l'utilisation d'IrisFit avec plusieurs études de cas. En particulier, nous vérifions des structures de données concurrentes et non-bloquantes standards comme la pile de Treiber et la file de Michael et Scott. Nous montrons qu'en augmentant le code de ces structures avec des sections protégées, nous obtenons des implémentations qui garantissent la complexité en espace de tas intuitivement attendue. De plus, nous prouvons correcte une implémentation des fermetures, des structures de données concrètes allouées sur le tas implémentant le concept abstrait de fonction de première classe. Les techniques de raisonnement que nous développons dans cette thèse sont destinées à s'appliquer à des langages répandus comme OCaml et Java. IrisFit ainsi que tous les résultats présentés sont formalisés dans l'assistant de preuve Coq.
- 8 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Formal verification of heap space bounds under garbage collection : a space tale from the stars
Vérification formelle de bornes en espace de tas en présence d'un glaneur de cellules : un conte spatial venu des étoiles: Cette thèse aborde le problème du raisonnement formel sur l'utilisation de l'espace de tas (heap space) des programmes concurrents en présence d'un glaneur de cellules (garbage collector). Alors qu'il est facile d'identifier où l'espace est consommé, c'est-à-dire les points d'allocations, la présence d'un glaneur de cellules rend délicat de déterminer où l'espace est libéré, les points de désallocations étant implicites. En effet, le glaneur de cellules peut s'exécuter à n'importe quel moment pour désallouer des blocs mémoires inaccessibles, c'est-à-dire les blocs qui ne sont pas transitivement accessibles depuis les adresses racines (roots) du code restant à exécuter. Une question centrale à cette thèse est donc: comment raisonner sur l'inaccessibilité ? Pour répondre à cette question, nous proposons IrisFit, une nouvelle logique de séparation construite au-dessus du cadre logique Iris. IrisFit garde trace de l'accessibilité des blocs mémoire en équipant chaque adresse d'une assertion pointed-by-heap et d'une assertion pointed-by-thread, enregistrant respectivement quel bloc mémoire accessible pointe vers cette adresse et quel fil (thread) considère cette adresse comme une racine. De plus, IrisFit exploite la notion de crédits-espace, un outil purement logique qui garde trace de la quantité d'espace libre disponible. Des crédits-espace sont consommés par les allocations et peuvent être récupérés en prouvant qu'un bloc mémoire est inaccessible. Au cours de cette thèse, nous avons identifié une difficulté fondamentale dans l'analyse de la complexité en espace de tas au pire cas des programmes concurrents en présence d'un glaneur de cellules. En effet, si l'exécution du glaneur de cellules et la réduction des fils peuvent s'entrelacer de manière arbitraire, alors il existe des scénarios indésirables dans lesquels une racine retenue par un fil endormi empêche la désallocation d'une quantité de mémoire possiblement grande. Pour remédier à ce problème, nous proposons deux nouvelles constructions: les sections protégées, dans lesquelles le glaneur de cellules n'a pas le droit de s'exécuter, et les points de polling, des instructions qui bloquent le fil courant si un autre fil requiert l'exécution du glaneur de cellules. Les sections protégées peuvent être exploitées par le programmeur pour éliminer les scénarios indésirables décrits ci-dessus, permettant ainsi d'obtenir une meilleure complexité en espace de tas au pire cas. Les points de polling, quant à eux, peuvent être insérés par le compilateur pour garantir qu'aucun fil n'attend indéfiniment que le glaneur de cellules s'exécute. Nous étendons IrisFit pour permettre de raisonner sur les sections protégées. Nous prouvons qu'IrisFit offre une garantie de sûreté (les programmes vérifiés ne peuvent pas produire une erreur et n'excèdent pas une borne donnée en espace de tas) et une garantie de vivacité (il existe une stratégie d'insertion des points de polling dans les programmes vérifiés garantissant que chaque requête d'allocation sera satisfaite après un nombre de pas borné). Nous illustrons l'utilisation d'IrisFit avec plusieurs études de cas. En particulier, nous vérifions des structures de données concurrentes et non-bloquantes standards comme la pile de Treiber et la file de Michael et Scott. Nous montrons qu'en augmentant le code de ces structures avec des sections protégées, nous obtenons des implémentations qui garantissent la complexité en espace de tas intuitivement attendue. De plus, nous prouvons correcte une implémentation des fermetures, des structures de données concrètes allouées sur le tas implémentant le concept abstrait de fonction de première classe. Les techniques de raisonnement que nous développons dans cette thèse sont destinées à s'appliquer à des langages répandus comme OCaml et Java. IrisFit ainsi que tous les résultats présentés sont formalisés dans l'assistant de preuve Coq.
- Open Access
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 354-383
TypeDis: A Type System for Disentanglement
Disentanglement is a runtime property of parallel programs guaranteeing that parallel tasks remain oblivious to each other's allocations. As demonstrated in the MaPLe compiler and run-time system, disentanglement can be exploited for fast automatic memory management, especially task-local garbage collection with no synchronization between parallel tasks. However, as a low-level property, disentanglement can be difficult to reason about for programmers. The only means of statically verifying disentanglement so far has been DisLog, an Iris-fueled variant of separation logic, mechanized in the Rocq proof assistant. DisLog is a fully-featured program logic, allowing for proof of functional correctness as well as verification of disentanglement. Yet its employment requires significant expertise and per-program proof effort. This paper explores the route of automatic verification via a type system, ensuring that any well-typed program is disentangled and lifting the burden of carrying out manual proofs from the programmer. It contributes TypeDis, a type system inspired by region types, where each type is annotated with a timestamp, identifying the task that allocated it. TypeDis supports iso-recursive types as well as polymorphism over both types and timestamps. Crucially, timestamps are allowed to change during type-checking, at join points as well as via a form of subtyping, dubbed subtiming. The paper illustrates TypeDis and its features on a range of examples. The soundness of TypeDis and the examples are mechanized in the Rocq proof assistant, using an improved version of DisLog, dubbed DisLog2.
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 354-383
Open AccessTypeDis: A Type System for Disentanglement
Disentanglement is a runtime property of parallel programs guaranteeing that parallel tasks remain oblivious to each other's allocations. As demonstrated in the MaPLe compiler and run-time system, disentanglement can be exploited for fast automatic memory management, especially task-local garbage collection with no synchronization between parallel tasks. However, as a low-level property, disentanglement can be difficult to reason about for programmers. The only means of statically verifying disentanglement so far has been DisLog, an Iris-fueled variant of separation logic, mechanized in the Rocq proof assistant. DisLog is a fully-featured program logic, allowing for proof of functional correctness as well as verification of disentanglement. Yet its employment requires significant expertise and per-program proof effort. This paper explores the route of automatic verification via a type system, ensuring that any well-typed program is disentangled and lifting the burden of carrying out manual proofs from the programmer. It contributes TypeDis, a type system inspired by region types, where each type is annotated with a timestamp, identifying the task that allocated it. TypeDis supports iso-recursive types as well as polymorphism over both types and timestamps. Crucially, timestamps are allowed to change during type-checking, at join points as well as via a form of subtyping, dubbed subtiming. The paper illustrates TypeDis and its features on a range of examples. The soundness of TypeDis and the examples are mechanized in the Rocq proof assistant, using an improved version of DisLog, dubbed DisLog2.
- Open Access
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 748-776
All for One and One for All: Program Logics for Exploiting Internal Determinism in Parallel Programs
Nondeterminism makes parallel programs challenging to write and reason about. To avoid these challenges, researchers have developed techniques for internally deterministic parallel programming, in which the steps of a parallel computation proceed in a deterministic way. Internal determinism is useful because it lets a programmer reason about a program as if it executed in a sequential order. However, no verification framework exists to exploit this property and simplify formal reasoning about internally deterministic programs. To capture the essence of why internally deterministic programs should be easier to reason about, this paper defines a property called schedule-independent safety. A program satisfies schedule-independent safety, if, to show that the program is safe across all orderings, it suffices to show that one terminating execution of the program is safe. We then present a separation logic called Musketeer for proving that a program satisfies schedule-independent safety. Once a parallel program has been shown to satisfy schedule-independent safety, we can verify it with a new logic called Angelic, which allows one to dynamically select and verify just one sequential ordering of the program. Using Musketeer, we prove the soundness of MiniDet, an affine type system for enforcing internal determinism. MiniDet supports several core algorithmic primitives for internally deterministic programming that have been identified in the research literature, including a deterministic version of a concurrent hash set. Because any syntactically well-typed MiniDet program satisfies schedule-independent safety, we can apply Angelic to verify such programs. All results in this paper have been verified in Rocq using the Iris separation logic framework.
- 8 January 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (POPL) , 748-776
Open AccessAll for One and One for All: Program Logics for Exploiting Internal Determinism in Parallel Programs
Nondeterminism makes parallel programs challenging to write and reason about. To avoid these challenges, researchers have developed techniques for internally deterministic parallel programming, in which the steps of a parallel computation proceed in a deterministic way. Internal determinism is useful because it lets a programmer reason about a program as if it executed in a sequential order. However, no verification framework exists to exploit this property and simplify formal reasoning about internally deterministic programs. To capture the essence of why internally deterministic programs should be easier to reason about, this paper defines a property called schedule-independent safety. A program satisfies schedule-independent safety, if, to show that the program is safe across all orderings, it suffices to show that one terminating execution of the program is safe. We then present a separation logic called Musketeer for proving that a program satisfies schedule-independent safety. Once a parallel program has been shown to satisfy schedule-independent safety, we can verify it with a new logic called Angelic, which allows one to dynamically select and verify just one sequential ordering of the program. Using Musketeer, we prove the soundness of MiniDet, an affine type system for enforcing internal determinism. MiniDet supports several core algorithmic primitives for internally deterministic programming that have been identified in the research literature, including a deterministic version of a concurrent hash set. Because any syntactically well-typed MiniDet program satisfies schedule-independent safety, we can apply Angelic to verify such programs. All results in this paper have been verified in Rocq using the Iris separation logic framework.
- Open Access
- 31 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 47 (1) , 1-71
Will It Fit? Verifying Heap Space Bounds of Concurrent Programs under Garbage Collection
We present IrisFit, a Separation Logic with space credits for reasoning about heap space in a concurrent call-by-value language equipped with tracing garbage collection and shared mutable state. We point out a fundamental difficulty in the analysis of the worst-case heap space complexity of concurrent programs in the presence of tracing garbage collection: If garbage collection phases and program steps can be arbitrarily interleaved, then there exist undesirable scenarios where a root held by a sleeping thread prevents a possibly large amount of memory from being freed. To remedy this problem and eliminate such undesirable scenarios, we propose several language features, namely possibly-blocking memory allocation, polling points, and protected sections. Polling points are meant to be automatically inserted by the compiler; protected sections are delimited by the programmer and represent regions where no polling points must be inserted. The heart of our contribution is IrisFit, a novel program logic that can establish worst-case heap space complexity bounds and whose reasoning rules can take advantage of the presence of protected sections. IrisFit is formalized inside the Coq proof assistant, on top of the Iris Separation Logic framework. We prove that IrisFit offers both a safety guarantee—programs cannot crash and cannot exceed a heap space limit—and a liveness guarantee—provided enough polling points have been inserted, every memory allocation request is satisfied in bounded time. We illustrate the use of IrisFit via several case studies, including a version of Treiber’s stack whose worst-case behavior relies on the presence of protected sections.
- 31 March 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 47 (1) , 1-71
Open AccessWill It Fit? Verifying Heap Space Bounds of Concurrent Programs under Garbage Collection
We present IrisFit, a Separation Logic with space credits for reasoning about heap space in a concurrent call-by-value language equipped with tracing garbage collection and shared mutable state. We point out a fundamental difficulty in the analysis of the worst-case heap space complexity of concurrent programs in the presence of tracing garbage collection: If garbage collection phases and program steps can be arbitrarily interleaved, then there exist undesirable scenarios where a root held by a sleeping thread prevents a possibly large amount of memory from being freed. To remedy this problem and eliminate such undesirable scenarios, we propose several language features, namely possibly-blocking memory allocation, polling points, and protected sections. Polling points are meant to be automatically inserted by the compiler; protected sections are delimited by the programmer and represent regions where no polling points must be inserted. The heart of our contribution is IrisFit, a novel program logic that can establish worst-case heap space complexity bounds and whose reasoning rules can take advantage of the presence of protected sections. IrisFit is formalized inside the Coq proof assistant, on top of the Iris Separation Logic framework. We prove that IrisFit offers both a safety guarantee—programs cannot crash and cannot exceed a heap space limit—and a liveness guarantee—provided enough polling points have been inserted, every memory allocation request is satisfied in bounded time. We illustrate the use of IrisFit via several case studies, including a version of Treiber’s stack whose worst-case behavior relies on the presence of protected sections.
- Open Access
- 15 August 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (ICFP) , 338-369
Snapshottable Stores
We say that an imperative data structure is snapshottable or supports snapshots if we can efficiently capture its current state, and restore a previously captured state to become the current state again. This is useful, for example, to implement backtracking search processes that update the data structure during search. Inspired by a data structure proposed in 1978 by Baker, we present a snapshottable store, a bag of mutable references that supports snapshots. Instead of capturing and restoring an array, we can capture an arbitrary set of references (of any type) and restore all of them at once. This snapshottable store can be used as a building block to support snapshots for arbitrary data structures, by simply replacing all mutable references in the data structure by our store references. We present use-cases of a snapshottable store when implementing type-checkers and automated theorem provers. Our implementation is designed to provide a very low overhead over normal references, in the common case where the capture/restore operations are infrequent. Read and write in store references are essentially as fast as in plain references in most situations, thanks to a key optimisation we call record elision. In comparison, the common approach of replacing references by integer indices into a persistent map incurs a logarithmic overhead on reads and writes, and sophisticated algorithms typically impose much larger constant factors. The implementation, which is inspired by Baker’s and the OCaml implementation of persistent arrays by Conchon and Filliâtre, is both fairly short and very hard to understand: it relies on shared mutable state in subtle ways. We provide a mechanized proof of correctness of its core using the Iris framework for the Coq proof assistant.
- 15 August 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (ICFP) , 338-369
Open AccessSnapshottable Stores
We say that an imperative data structure is snapshottable or supports snapshots if we can efficiently capture its current state, and restore a previously captured state to become the current state again. This is useful, for example, to implement backtracking search processes that update the data structure during search. Inspired by a data structure proposed in 1978 by Baker, we present a snapshottable store, a bag of mutable references that supports snapshots. Instead of capturing and restoring an array, we can capture an arbitrary set of references (of any type) and restore all of them at once. This snapshottable store can be used as a building block to support snapshots for arbitrary data structures, by simply replacing all mutable references in the data structure by our store references. We present use-cases of a snapshottable store when implementing type-checkers and automated theorem provers. Our implementation is designed to provide a very low overhead over normal references, in the common case where the capture/restore operations are infrequent. Read and write in store references are essentially as fast as in plain references in most situations, thanks to a key optimisation we call record elision. In comparison, the common approach of replacing references by integer indices into a persistent map incurs a logarithmic overhead on reads and writes, and sophisticated algorithms typically impose much larger constant factors. The implementation, which is inspired by Baker’s and the OCaml implementation of persistent arrays by Conchon and Filliâtre, is both fairly short and very hard to understand: it relies on shared mutable state in subtle ways. We provide a mechanized proof of correctness of its core using the Iris framework for the Coq proof assistant.
- Open Access
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 302-331
DisLog: A Separation Logic for Disentanglement
Disentanglement is a run-time property of parallel programs that facilitates task-local reasoning about the memory footprint of parallel tasks. In particular, it ensures that a task does not access any memory locations allocated by another concurrently executing task. Disentanglement can be exploited, for example, to implement a high-performance parallel memory manager, such as in the MPL (MaPLe) compiler for Parallel ML. Prior research on disentanglement has focused on the design of optimizations, either trusting the programmer to provide a disentangled program or relying on runtime instrumentation for detecting and managing entanglement. This paper provides the first static approach to verify that a program is disentangled: it contributes DisLog, a concurrent separation logic for disentanglement. DisLog enriches concurrent separation logic with the notions necessary for reasoning about the fork-join structure of parallel programs, allowing the verification that memory accesses are effectively disentangled. A large class of programs, including race-free programs, exhibit memory access patterns that are disentangled "by construction". To reason about these patterns, the paper distills from DisLog an almost standard concurrent separation logic, called DisLog+. In this high-level logic, no specific reasoning about memory accesses is needed: functional correctness proofs entail disentanglement. The paper illustrates the use of DisLog and DisLog+ on a range of case studies, including two different implementations of parallel deduplication via concurrent hashing. All our results are mechanized in the Coq proof assistant using Iris.
- 2 January 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 8 (POPL) , 302-331
Open AccessDisLog: A Separation Logic for Disentanglement
Disentanglement is a run-time property of parallel programs that facilitates task-local reasoning about the memory footprint of parallel tasks. In particular, it ensures that a task does not access any memory locations allocated by another concurrently executing task. Disentanglement can be exploited, for example, to implement a high-performance parallel memory manager, such as in the MPL (MaPLe) compiler for Parallel ML. Prior research on disentanglement has focused on the design of optimizations, either trusting the programmer to provide a disentangled program or relying on runtime instrumentation for detecting and managing entanglement. This paper provides the first static approach to verify that a program is disentangled: it contributes DisLog, a concurrent separation logic for disentanglement. DisLog enriches concurrent separation logic with the notions necessary for reasoning about the fork-join structure of parallel programs, allowing the verification that memory accesses are effectively disentangled. A large class of programs, including race-free programs, exhibit memory access patterns that are disentangled "by construction". To reason about these patterns, the paper distills from DisLog an almost standard concurrent separation logic, called DisLog+. In this high-level logic, no specific reasoning about memory accesses is needed: functional correctness proofs entail disentanglement. The paper illustrates the use of DisLog and DisLog+ on a range of case studies, including two different implementations of parallel deduplication via concurrent hashing. All our results are mechanized in the Coq proof assistant using Iris.
- Open Access
- 9 January 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (POPL) , 718-747
A High-Level Separation Logic for Heap Space under Garbage Collection
We present a Separation Logic with space credits for reasoning about heap space in a sequential call-by-value lambda-calculus equipped with garbage collection and mutable state. A key challenge is to design sound, modular, lightweight mechanisms for establishing the unreachability of a block. Prior work in this area uses pointed-by assertions to keep track of the predecessors of every block, but is carried out in the setting of an assembly-like programming language. We take up the challenge in the setting of a high-level language, where a key problem is to identify and reason about the memory locations that the garbage collector considers as roots. For this purpose, we propose novel "stackable" assertions, which keep track of the existence of stack-to-heap pointers without explicitly recording their origin. Furthermore, we explain how to reason about closures -- concrete heap-allocated data structures that implement the abstract concept of a first-class function. We demonstrate the expressiveness and tractability of our program logic via a range of examples, including recursive functions on linked lists, objects implemented using closures and mutable internal state, recursive functions in continuation-passing style, and three stack implementations that exhibit different space bounds. These last three examples illustrate reasoning about the reachability of the items stored in a container as well as amortized reasoning about space. All of our results are proved in Coq on top of Iris.
- 9 January 2023
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 7 (POPL) , 718-747
Open AccessA High-Level Separation Logic for Heap Space under Garbage Collection
We present a Separation Logic with space credits for reasoning about heap space in a sequential call-by-value lambda-calculus equipped with garbage collection and mutable state. A key challenge is to design sound, modular, lightweight mechanisms for establishing the unreachability of a block. Prior work in this area uses pointed-by assertions to keep track of the predecessors of every block, but is carried out in the setting of an assembly-like programming language. We take up the challenge in the setting of a high-level language, where a key problem is to identify and reason about the memory locations that the garbage collector considers as roots. For this purpose, we propose novel "stackable" assertions, which keep track of the existence of stack-to-heap pointers without explicitly recording their origin. Furthermore, we explain how to reason about closures -- concrete heap-allocated data structures that implement the abstract concept of a first-class function. We demonstrate the expressiveness and tractability of our program logic via a range of examples, including recursive functions on linked lists, objects implemented using closures and mutable internal state, recursive functions in continuation-passing style, and three stack implementations that exhibit different space bounds. These last three examples illustrate reasoning about the reachability of the items stored in a container as well as amortized reasoning about space. All of our results are proved in Coq on top of Iris.
- Open Access
- 1 January 2023
- Published by OpenEdition in VertigO
- Vol. 23-2
Jalons pour une géographie de la traduction : Mieux comprendre le territoire du lac de Buyo
A travers cet article, nous proposons une démarche d’analyse pour la conduite d’un diagnostic territorial autour de problématiques liées à l’environnement en lien avec la gestion du lac de Buyo en Côte d’Ivoire. Partant du principe que les diagnostics territoriaux mis en place ne permettent pas de dégager des enjeux partagés par l’ensemble des actants, il s’agit de s’interroger sur la formalisation de nouveaux outils capable de soutenir le dialogue entre des inter/actants hétérogènes. A partir d’une étude de cas que nous prenons pour fil conducteur dans notre analyse, nous exposons une nouvelle approche théorique et opérationnelle en appui sur le paradigme de la complexité appliqué au concept de territoire ainsi que sur la démarche de sociologie de la traduction visant à partir d’un trouble établi, à créer les conditions du partage de regards et d’actions. La démarche permet de suggérer une géographie de la traduction par le biais d’une matrice qui articule cinq sous-systèmes constitutifs du système territoire et quatre étapes de la sociologie de la traduction. La mise en place d’une synthèse cartographique permet d’exprimer les enjeux croisés découlant de l’analyse des jeux d’actants mise en oeuvre. L’ingéniosité hétérogène qui se traduit par la mise en place d’une « focale nette » du territoire est capable de stimuler la coopération faisant ainsi une ouverture vers la gouvernance. L’ensemble se présente comme un outil d’interprétation du trouble et des interactions sous-jacentes, qu’un chef de projet peut mobiliser à l’aune des diagnostics à mettre en œuvre pour animer un travail collectif dans une dimension prospective.
- 1 January 2023
- Published by OpenEdition in VertigO
- Vol. 23-2
Open AccessJalons pour une géographie de la traduction : Mieux comprendre le territoire du lac de Buyo
A travers cet article, nous proposons une démarche d’analyse pour la conduite d’un diagnostic territorial autour de problématiques liées à l’environnement en lien avec la gestion du lac de Buyo en Côte d’Ivoire. Partant du principe que les diagnostics territoriaux mis en place ne permettent pas de dégager des enjeux partagés par l’ensemble des actants, il s’agit de s’interroger sur la formalisation de nouveaux outils capable de soutenir le dialogue entre des inter/actants hétérogènes. A partir d’une étude de cas que nous prenons pour fil conducteur dans notre analyse, nous exposons une nouvelle approche théorique et opérationnelle en appui sur le paradigme de la complexité appliqué au concept de territoire ainsi que sur la démarche de sociologie de la traduction visant à partir d’un trouble établi, à créer les conditions du partage de regards et d’actions. La démarche permet de suggérer une géographie de la traduction par le biais d’une matrice qui articule cinq sous-systèmes constitutifs du système territoire et quatre étapes de la sociologie de la traduction. La mise en place d’une synthèse cartographique permet d’exprimer les enjeux croisés découlant de l’analyse des jeux d’actants mise en oeuvre. L’ingéniosité hétérogène qui se traduit par la mise en place d’une « focale nette » du territoire est capable de stimuler la coopération faisant ainsi une ouverture vers la gouvernance. L’ensemble se présente comme un outil d’interprétation du trouble et des interactions sous-jacentes, qu’un chef de projet peut mobiliser à l’aune des diagnostics à mettre en œuvre pour animer un travail collectif dans une dimension prospective.
- Open Access
- 11 January 2022
- Published by Association for Computing Machinery (ACM)
- p. 82-99
Specification and verification of a transient stack
A transient data structure is a package of an ephemeral data structure, a persistent data structure, and fast conversions between them. We describe the specification and proof of a transient stack and its iterators. This data structure is a scaled-down version of the general-purpose transient sequence data structure implemented in the OCaml library Sek. Internally, it relies on fixed-capacity arrays, or chunks, which can be shared between several ephemeral and persistent stacks. Dynamic tests are used to determine whether a chunk can be updated in place or must be copied: a chunk can be updated if it is uniquely owned or if the update is monotonic. Using CFML, which implements Separation Logic with Time Credits inside Coq, we verify the functional correctness and the amortized time complexity of this data structure. Our verification effort covers iterators, which involve direct pointers to internal chunks. The specification of iterators describes what the operations on iterators do, how much they cost, and under what circumstances an iterator is invalidated.
- 11 January 2022
- Published by Association for Computing Machinery (ACM)
- p. 82-99
Open AccessSpecification and verification of a transient stack
A transient data structure is a package of an ephemeral data structure, a persistent data structure, and fast conversions between them. We describe the specification and proof of a transient stack and its iterators. This data structure is a scaled-down version of the general-purpose transient sequence data structure implemented in the OCaml library Sek. Internally, it relies on fixed-capacity arrays, or chunks, which can be shared between several ephemeral and persistent stacks. Dynamic tests are used to determine whether a chunk can be updated in place or must be copied: a chunk can be updated if it is uniquely owned or if the update is monotonic. Using CFML, which implements Separation Logic with Time Credits inside Coq, we verify the functional correctness and the amortized time complexity of this data structure. Our verification effort covers iterators, which involve direct pointers to internal chunks. The specification of iterators describes what the operations on iterators do, how much they cost, and under what circumstances an iterator is invalidated.