Knit&Frog: Pattern matching compilation for custom memory representations

Initially present only in functional languages such as OCaml and Haskell, Algebraic Data Types have now become pervasive in mainstream languages, providing nice data abstractions and an elegant way to express functions though pattern-matching. Numerous approaches have been designed to compile rich pattern matching to cleverly designed, ecient decision trees. However, these approaches are specic to a choice of internal memory representation which must accommodate garbage-collection and polymorphism. ADTs now appear in languages more liberal in their memory representation such as Rust. Notably, Rust is now introducing more and more optimizations of the memory layout of Algebraic Data Types. As memory representation and compilation are interdependent, it raises the question of pattern matching compilation in the presence of non-regular, potentially customized, memory layouts. In this report, we present Knit&Frog, a framework to compile pattern-matching for monomorphic ADTs, parametrized by an arbitrary memory representation. We propose a novel way to describe choices of memory representation along with a validity condition under which we prove the correctness of our compilation scheme. The approach is implemented in a prototype tool ribbit.Initialement présents dans les langages fonctionnels comme Ocaml et Haskell, les types algébriques sont maintenant de plus en plus présents dans les langages mainstream comme Rust. Ils permettent une abstraction commode des données et une façon élégante de décrire des fonctions via le fitrage de motifs (pattern-matching). Ce rapport de recherche présente Knit&Frog, un cadre formel pour décrire des représentations mémoires de types algébrique paramétré par la représentation mémoire. La correction de l'algorithme est prouvée sous une hypothèse de validité de la représentation. L'algorithme est implémenté dans l'outil ribbit. Le principal avantage de l'approche est l'indépendance de l'algorithme et de sa représentation mémoire,qui permettra à terme de décrire des représentations optimisées sans perdre de l'expressivité