Compiling pattern matching to in-place modifications
| Autor: | Laure Gonnord, Gabriel Radanne, Paul Iannetta |
|---|---|
| Přispěvatelé: | École normale supérieure de Lyon (ENS de Lyon), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), CASH - Compilation and Analysis, Software and Hardware (CASH), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Conception et d'Intégration des Systèmes (LCIS), Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA), Conception et Test de SYStèmes embarqués (CTSYS ), Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Institut National de Recherche en Informatique et en Automatique (Inria), ANR-17-CE23-0004,CODAS,Ordonnancement de programmes à structures de données complexes(2017), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, École normale supérieure - Lyon (ENS Lyon) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Computer science
Programming language [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 020207 software engineering 0102 computer and information sciences 02 engineering and technology code generation computer.software_genre ADT 01 natural sciences [INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL] rewriting 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Algebraic data type compilation Polytope model Code generation Use case Pattern matching Compiler Rewriting Representation (mathematics) computer |
| Zdroj: | GPCE 2021-20th International Conference on Generative Programming: Concepts & Experiences GPCE 2021-20th International Conference on Generative Programming: Concepts & Experiences, Oct 2021, Chicago & Virtual, United States. ⟨10.1145/3486609.3487204⟩ GPCE |
| DOI: | 10.1145/3486609.3487204⟩ |
| Popis: | International audience; Algebraic data types and pattern matching are popular tools to build programs manipulating complex datastructures in a safe yet efficient manner. On top of its safety advantages, compilation techniques can turn pattern matching into highly efficient deconstruction code for immutable use cases. Conversely, high-performance datastructures and languages prefer to leverage (controlled) mutations to maximize time and memory efficiency. Algebraic data types provide a natural framework to efficiently describe \emph{in-place} transformations as rewrite rules. Such representation coul take advantage of parallelism opportunities that appear in tree-like structures. We present early steps towards a new technique to compile pattern matching as parallel in-place modifications of the underlying memory representation. Towards this goal, we combine the usual language approach which is common in pattern-matching compilation with tools from the polyhedral model, which is commonly used in high-performance code generation to output efficient C code. We present our formalism, along with a prototype implementation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|