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

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00073642
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:24:02 PM
Last modification on : Friday, November 16, 2018 - 1:29:50 AM
Long-term archiving on : Sunday, April 4, 2010 - 11:53:14 PM

Identifiers

  • HAL Id : inria-00073642, version 1

Citation

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⟩

Share

Metrics

Record views

382

Files downloads

159