Efficient Strategies and Implementation Models for Functional Languages.
Stratégies Efficaces et Modèles d'Implantation pour les Langages Fonctionnels.
Résumé
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.
Dans les langages fonctionnels, l'efficacité dépend crucialement du choix de la stratégie d'évaluation et d'un modèle d'implantation adapté. Nous développons d'abord un λ-calcul avec substitutions explicites qui évite les problèmes habituels liés à la substitution et à l'α-conversion, dans lequel on peut définir les stratégies usuelles, mais aussi des stratégies avec un meilleur partage de calcul. Ensuite, nous développons un modèle d'implantation efficace pour ce calcul. Pour cela, nous proposons une représentation innnovante des variables libres, d'abord dans le cadre très général de la récriture d'ordre supérieur, puis avec plus de détails dans notre cas particulier. Nous obtenons ainsi un λ-calcul avec substitutions explicites sans noms ni indices, dans lequel les te! rmes sont annotés avec de l'information qui indique comment les substitutions doivent être propagées, et qui constitue un modèle d'implantation efficace pour nos stratégies. Des machines abstraites sont alors définies, implantées et comparées expérimentalement aux meilleurs évaluateurs connus. Finalement, nous étudions les relations entre machines abstraites traditionnelles et réseaux d'interaction, deux modèles d'implantation courants mais très différents. Plus précisément, nous montrons comment certaines stratégies peuvent être implantées dans les réseaux d'interaction d'une façon très naturelle, rapprochant ainsi deux modèles utilisés pour l'implantation de stratégies efficaces.
Loading...