On the implementation of recursion in call-by-value functional languages

Abstract : Functional languages encourage the extensive use of recursive fonctions and data structures. It is therefore important that they efficiently implement recursion. In this paper, we formalize and improve a known implementation technique for recursion. The original technique was introduced by Cousineau and Mauny as the «in-place updating trick». Consider a list of mutually recursive definitions. The technique consists in allocating a dummy, uninitialized heap block for each recursive definition. The size of these blocks is guessed from the shape of each definition. Then, the right-hand sides of the definitions are computed. Recursively-defined identifiers thus refer to the corresponding dummy blocks. This leads, for each definition, to a block of the expected size. Eventually, the contents of the obtained blocks are copied to the dummy blocks, updating them in place. The only change we propose to this scheme is to update the dummy blocks as soon as possible, immediately after each definition is computed, thus making it available for further use. At the source language level, the improvement allows to extend the class of expressions allowed as right-hand sides of recursive definitions, usually restricted to syntactic functions. We formalize our technique as a translation scheme to a lambda-calculus featuring in-place updating of memory blocks, and prove the translation to be faithful.
Type de document :
[Research Report] RR-4728, INRIA. 2003
Liste complète des métadonnées

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

Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 18:59:05
Dernière modification le : samedi 17 septembre 2016 - 01:35:24
Document(s) archivé(s) le : dimanche 4 avril 2010 - 20:28:01



  • HAL Id : inria-00071858, version 1



Tom Hirschowitz, Xavier Leroy, J. B. Wells. On the implementation of recursion in call-by-value functional languages. [Research Report] RR-4728, INRIA. 2003. 〈inria-00071858〉



Consultations de
la notice


Téléchargements du document