Compositional Flexible Memory Representations for Algebraic Data Types
Thaïs Baudon, Gabriel Radanne, Laure Gonnord · HAL (Le Centre pour la Communication Scientifique Directe) · 2022
Initially present only in functional languages such as OCaml and Haskell, AlgebraicData Types have now become pervasive in mainstream languages, providing nice data abstractionsand an elegant way to express functions through pattern matching. Numerous approaches have beendesigned to compile rich pattern matching to cleverly designed, efficient decision trees. However,these approaches are specific to a choice of memory representation which must accommodategarbage collection and polymorphism.ADTs now appear in languages more liberal in their memory representation. Notably, Rust is nowintroducing more and more memory optimisations. As memory representation and compilationare interdependent, it raises the question of pattern matching compilation for highly customisedlayouts.We propose to ease the experimentation of new, custom layouts in the early stages of compilerdevelopment by providing specification tools and a complete synthesis chain to generate patternmatching compilation procedures.In this report, we present a novel way to specify compositional memory layouts, for which we automatically synthesise elementary builders and accessors, yielding a correct representation-specificcompilation algorithm. This approach is implemented in a prototype tool ribbit.