A Taxonomy of Functional Language Implementations Part II : Call-by-Name, Call-by-Need and Graph Reduction

Rémi Douence 1 Pascal Fradet 1
1 Lande - Logiciel : ANalyse et DEveloppement
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : In Part I [5], we proposed an approach to formally describe and compare functional languages implementations. We focused on call-by-value and described well-known compilers for strict languages. Here, we complete our exploration of the design space of implementations by studying call-by-name, call-by-need and graph reduction. We express the whole compilation process as a succession of program transformations in a common framework. At each step, different transformations model fundamental choices or optimizations. We describe and compare the diverse alternatives for the compilation of the call-by-name strategy in both environment and graph-based models. The different options for the compilation of béta-reduction described in [5] can be applied here as well. Instead, we describe other possibilities specific to graph reduction. Call-by-need is nothing but call-by-name with redex sharing and update. We present how sharing can be expressed in our framework and we describe different update schemes. We finally classify some well-known call-by-need implementations.
Type de document :
[Research Report] RR-3050, INRIA. 1996
Liste complète des métadonnées

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

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:24:02
Dernière modification le : vendredi 16 novembre 2018 - 01:29:50
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:53:14



  • HAL Id : inria-00073642, version 1


Rémi Douence, Pascal Fradet. A Taxonomy of Functional Language Implementations Part II : Call-by-Name, Call-by-Need and Graph Reduction. [Research Report] RR-3050, INRIA. 1996. 〈inria-00073642〉



Consultations de la notice


Téléchargements de fichiers