BCBasile Clément

Basile Clément

*This is an algorithmically generated author record based on publicly available information.

Basile Clément has a total of 6 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Translation validation of tensor compilers

    by Basile Clément

    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

    Tail Modulo Cons, OCaml, and Relational Separation Logic

    by Clément Allain, Frédéric Bour, Basile Clément, François Pottier, Gabriel Scherer

    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

    Snapshottable Stores

    by Clément Allain, Basile Clément, Alexandre Moine, Gabriel Scherer

    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

    End-to-end translation validation for the halide language

    by Basile Clément, Albert Cohen

    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.