Functional Programming for Dynamic and Large Data with Self-Adjusting Computation

Abstract : Combining type theory, language design, and empirical work, we present techniques for computing with large and dynamically changing datasets. Based on lambda calculus, our techniques are suitable for expressing a diverse set of algorithms on large datasets and, via self-adjusting computation, enable computations to respond automatically to changes in their data. To improve the scalability of self-adjusting computation, we present a type system for precise dependency tracking that minimizes the time and space for storing dependency metadata. The type system eliminates an important assumption of prior work that can lead to recording spurious dependencies. We present a type-directed translation algorithm that generates correct self-adjusting programs without relying on this assumption. We then show a probabilistic-chunking technique to further decrease space usage by controlling the fundamental space-time tradeoff in self-adjusting computation. We implement and evaluate these techniques, showing promising results on challenging benchmarks involving large graphs.
Type de document :
Communication dans un congrès
ICFP 2014: 19th ACM SIGPLAN International Conference on Functional Programming, Sep 2014, Gothenburg, Sweden. <10.1145/2628136.2628150>
Liste complète des métadonnées

https://hal.inria.fr/hal-01100337
Contributeur : Arthur Charguéraud <>
Soumis le : mardi 6 janvier 2015 - 11:54:46
Dernière modification le : lundi 5 octobre 2015 - 17:01:55

Identifiants

Collections

Citation

Yan Chen, Umut A. Acar, Kanat Tangwongsan. Functional Programming for Dynamic and Large Data with Self-Adjusting Computation. ICFP 2014: 19th ACM SIGPLAN International Conference on Functional Programming, Sep 2014, Gothenburg, Sweden. <10.1145/2628136.2628150>. <hal-01100337>

Partager

Métriques

Consultations de la notice

121