Rebuilding Algebraic Data Types from Mangled Memory Layouts - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Preprints, Working Papers, ... Year : 2024

Rebuilding Algebraic Data Types from Mangled Memory Layouts

Abstract

Now integrated in mainstream languages, Algebraic Data Types (ADTs) have established themselves as a nice way to reason about data structures and their manipulations using pattern-matching. However, their use in low-level programming remains limited despite efforts, notably from the Rust community. Recently, Baudon et al. [2023] propose to let the programmer express the precise memory layout of a given Algebraic Data Type, while still enjoying high-level programming constructs. Their compilation procedure covers efficient pattern matching, but leaves out constructors and struggles with arbitrarily mangled memory layouts. So far, the literature on ADT compilation rarely mentions constructors, which are indeed a non-issue on simple memory layouts. However, when data pieces are broken and scattered in memory, this task becomes particularly challenging. Even simple accessors might require constructing new values. This is the case for many low-level representations such as network packets, instruction sets, databases data-structures, or aggressively packed representations. In this article, we propose a unified compilation procedure for ADTs constructors and destructors (i.e., patternmatching) in the context of arbitrarily mangled memory layouts. We subsume existing compilation algorithms, and extend them to emit CFG-style programs with explicit memory allocation and full support for recursive types.
Fichier principal
Vignette du fichier
main.pdf (586.47 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Licence : CC BY - Attribution

Dates and versions

hal-04388766 , version 1 (11-01-2024)

Identifiers

  • HAL Id : hal-04388766 , version 1

Cite

Gabriel Radanne, Thaïs Baudon, Laure Gonnord. Rebuilding Algebraic Data Types from Mangled Memory Layouts. 2024. ⟨hal-04388766⟩
33 View
43 Download

Share

Gmail Facebook X LinkedIn More