Basile Clément
Research Subjects
Basile Clément has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Clément Allain
INRIA, Paris, France
2 shared publications - Gabriel Scherer
Inria IRIF Université Paris Cité Paris France
2 shared publications - Albert Cohen
Google, Paris, France
1 shared publication - Alexandre Moine
New York University, New York, USA
1 shared publication - François Pottier
INRIA, Paris, France
1 shared publication - Frederic Bour
Tarides, Paris, France
1 shared publication
Latest Publications
- 7 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Translation validation of tensor compilers
Validation de traduction pour compilateurs de tenseurs: Les compilateurs de tenseurs sont utilisés dans des domaines comme le traitement d'image et l'apprentissage profond pour générer du code bas niveau efficace à partir de spécification de haut niveau sur des tenseurs multi-dimensionnels. Le code généré peut présenter une structure drastiquement différente de celle de la spécification suite à l'application de transformations de boucles et de simplifications algébriques. La vérification formelle des compilateurs de tenseurs est donc une tâche ardue, qui ne peut être traitée par les techniques standard à base de bisimulations. Je propose une nouvelle méthode pour la vérification de compilateurs de tenseurs en présence de transformations algébriques et de boucles. Cette méthode s'inspire des techniques polyédriques de représentation de programmes, et s'appuie sur une association de raffinement depuis les affectations dans le code bas niveau vers les définitions de tenseurs dans la spécification fournie par le compilateur. Chaque exécution du compilateur est vérifiée par un outil de vérification indépendant implanté en OCaml, faisant donc de la méthode un validateur de traduction. Cet outil de vérification est testé sur Halide, un compilateur de tenseurs de niveau industriel.
- 7 April 2026
- Published by Agence Bibliographique de l'Enseignement Supérieur
Translation validation of tensor compilers
Validation de traduction pour compilateurs de tenseurs: Les compilateurs de tenseurs sont utilisés dans des domaines comme le traitement d'image et l'apprentissage profond pour générer du code bas niveau efficace à partir de spécification de haut niveau sur des tenseurs multi-dimensionnels. Le code généré peut présenter une structure drastiquement différente de celle de la spécification suite à l'application de transformations de boucles et de simplifications algébriques. La vérification formelle des compilateurs de tenseurs est donc une tâche ardue, qui ne peut être traitée par les techniques standard à base de bisimulations. Je propose une nouvelle méthode pour la vérification de compilateurs de tenseurs en présence de transformations algébriques et de boucles. Cette méthode s'inspire des techniques polyédriques de représentation de programmes, et s'appuie sur une association de raffinement depuis les affectations dans le code bas niveau vers les définitions de tenseurs dans la spécification fournie par le compilateur. Chaque exécution du compilateur est vérifiée par un outil de vérification indépendant implanté en OCaml, faisant donc de la méthode un validateur de traduction. Cet outil de vérification est testé sur Halide, un compilateur de tenseurs de niveau industriel.
- Open Access
- 7 January 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (POPL) , 2337-2363
Tail Modulo Cons, OCaml, and Relational Separation Logic
Common functional languages incentivize tail-recursive functions, as opposed to general recursive functions that consume stack space and may not scale to large inputs. This distinction occasionally requires writing functions in a tail-recursive style that may be more complex and slower than the natural, non-tail-recursive definition. This work describes our implementation of the tail modulo constructor (TMC) transformation in the OCaml compiler, an optimization that provides stack-efficiency for a larger class of functions — tail-recursive modulo constructors — which includes in particular the natural definition of List.map and many similar recursive data-constructing functions. We prove the correctness of this program transformation in a simplified setting — a small untyped calculus — that captures the salient aspects of the OCaml implementation. Our proof is mechanized in the Coq proof assistant, using the Iris base logic. An independent contribution of our work is an extension of the Simuliris approach to define simulation relations that support different calling conventions. To our knowledge, this is the first use of Simuliris to prove the correctness of a compiler transformation.
- 7 January 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (POPL) , 2337-2363
Open AccessTail Modulo Cons, OCaml, and Relational Separation Logic
Common functional languages incentivize tail-recursive functions, as opposed to general recursive functions that consume stack space and may not scale to large inputs. This distinction occasionally requires writing functions in a tail-recursive style that may be more complex and slower than the natural, non-tail-recursive definition. This work describes our implementation of the tail modulo constructor (TMC) transformation in the OCaml compiler, an optimization that provides stack-efficiency for a larger class of functions — tail-recursive modulo constructors — which includes in particular the natural definition of List.map and many similar recursive data-constructing functions. We prove the correctness of this program transformation in a simplified setting — a small untyped calculus — that captures the salient aspects of the OCaml implementation. Our proof is mechanized in the Coq proof assistant, using the Iris base logic. An independent contribution of our work is an extension of the Simuliris approach to define simulation relations that support different calling conventions. To our knowledge, this is the first use of Simuliris to prove the correctness of a compiler transformation.
- 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
- 29 April 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA1) , 1-30
End-to-end translation validation for the halide language
This paper considers the correctness of domain-specific compilers for tensor programming languages through the study of Halide, a popular representative. It describes a translation validation algorithm for affine Halide specifications, independently of the scheduling language. The algorithm relies on “prophetic” annotations added by the compiler to the generated array assignments. The annotations provide a refinement mapping from assignments in the generated code to the tensor definitions from the specification. Our implementation leverages an affine solver and a general SMT solver, and scales to complete Halide benchmarks.
- 29 April 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA1) , 1-30
Open AccessEnd-to-end translation validation for the halide language
This paper considers the correctness of domain-specific compilers for tensor programming languages through the study of Halide, a popular representative. It describes a translation validation algorithm for affine Halide specifications, independently of the scheduling language. The algorithm relies on “prophetic” annotations added by the compiler to the generated array assignments. The annotations provide a refinement mapping from assignments in the generated code to the tensor definitions from the specification. Our implementation leverages an affine solver and a general SMT solver, and scales to complete Halide benchmarks.