A verified framework for higher-order uncurrying optimizations

Abstract : Function uncurrying is an important optimization for the efficient execution of functional programming languages. This optimization replaces curried functions by uncur-ried, multiple-argument functions, while preserving the ability to evaluate partial applications. First-order uncurrying (where curried functions are optimized only in the static scopes of their definitions) is well understood and implemented by many compilers, but its extension to higher-order functions (where uncurrying can also be performed on parameters and results of higher-order functions) is challenging. This article develops a generic framework that expresses higher-order uncurrying optimizations as type-directed insertion of coercions, and prove its correctness. The proof uses step-indexed logical relations and was entirely mechanized using the Coq proof assistant.
Type de document :
Article dans une revue
Higher-Order and Symbolic Computation, Springer Verlag, 2009, 22 (3), 〈10.1007/s10990-010-9050-z〉
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01499915
Contributeur : Xavier Leroy <>
Soumis le : samedi 1 avril 2017 - 15:36:51
Dernière modification le : lundi 24 septembre 2018 - 11:34:03
Document(s) archivé(s) le : dimanche 2 juillet 2017 - 12:41:27

Fichier

higher-order-uncurrying.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Zaynah Dargaye, Xavier Leroy. A verified framework for higher-order uncurrying optimizations. Higher-Order and Symbolic Computation, Springer Verlag, 2009, 22 (3), 〈10.1007/s10990-010-9050-z〉. 〈hal-01499915〉

Partager

Métriques

Consultations de la notice

242

Téléchargements de fichiers

32