Skip to Main content Skip to Navigation
Theses

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 :
Theses
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00001952
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

Identifiers

  • HAL Id : pastel-00001952, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

441

Files downloads

217