Skip to Main content Skip to Navigation

Stratégies Efficaces et Modèles d'Implantation pour les Langages Fonctionnels.

Abstract : In functional languages, efficiency heavily relies on the choice of an evaluation strategy and an implementation model.! We first develop a λ-calculus with explicit substitution! s which avoids the usual problems of substitution and α-conversion, where we can define the usual strategies, as well as some strategies with more sharing of computations. We then develop an efficient implementation model for this calculus. To this end, we propose an innovative representation of free variables, first in the very general setting of higher-order rewriting, then with more details in our particular case. We thus obtain a λ-calculus with explicit substitutions without names nor indices, in which terms are annotated with information about how substitutions should be propagated, which is a suitable implementation model for our strategies. Abstract machines are then defined, implemented, and experimentally compared to the best known evaluators. Finally, we study the relationship between traditional abstract machines and interaction nets, two common but very different implementation models. More precisely, we show how some strategies can be implemented in interaction nets in a very natural way, thus bridging the gap between two models used to implement efficient strategies.
Document type :
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download
Contributor : Ecole Polytechnique <>
Submitted on : Wednesday, July 28, 2010 - 2:49:38 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:26 PM
Long-term archiving on: : Tuesday, October 23, 2012 - 11:31:48 AM


  • HAL Id : pastel-00001952, version 1



François-Régis Sinot. Stratégies Efficaces et Modèles d'Implantation pour les Langages Fonctionnels.. Informatique et langage [cs.CL]. Ecole Polytechnique X, 2006. Français. ⟨pastel-00001952⟩



Record views


Files downloads