# Boltzmann samplers for random generation of lambda terms

Abstract : Randomly generating structured objects is important in testing and optimizing functional programs, whereas generating random $'l$-terms is more specifically needed for testing and optimizing compilers. For that a tool called QuickCheck has been proposed, but in this tool the control of the random generation is left to the programmer. Ten years ago, a method called Boltzmann samplers has been proposed to generate combinatorial structures. In this paper, we show how Boltzmann samplers can be developed to generate lambda-terms, but also other data structures like trees. These samplers rely on a critical value which parameters the main random selector and which is exhibited here with explanations on how it is computed. Haskell programs are proposed to show how samplers are actually implemented.
Keywords :
Type de document :
Pré-publication, Document de travail
2014
Domaine :
Liste complète des métadonnées

Littérature citée [27 références]

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00979074
Contributeur : Pierre Lescanne <>
Soumis le : lundi 28 avril 2014 - 12:26:15
Dernière modification le : mardi 24 avril 2018 - 13:52:30
Document(s) archivé(s) le : lundi 28 juillet 2014 - 11:31:06

### Fichiers

boltzmann.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : ensl-00979074, version 2
• ARXIV : 1404.3875

### Citation

Pierre Lescanne. Boltzmann samplers for random generation of lambda terms. 2014. 〈ensl-00979074v2〉

### Métriques

Consultations de la notice

## 150

Téléchargements de fichiers