A Taxonomy of Functional Language Implementations Part II : Call-by-Name, Call-by-Need and Graph Reduction - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 1996

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

(1) , (1)
1

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.
Fichier principal
Vignette du fichier
RR-3050.pdf (339.23 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00073642 , version 1 (24-05-2006)

Identifiers

  • HAL Id : inria-00073642 , version 1

Cite

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⟩
210 View
117 Download

Share

Gmail Facebook Twitter LinkedIn More