Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 1:24:02 PM
Last modification on : Tuesday, June 15, 2021 - 4:26:33 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:53:14 PM


  • 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⟩



Record views


Files downloads