Boltzmann samplers for random generation of lambda terms

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.

Data and Resources

Additional Info

Field Value
Source https://ens-lyon.hal.science/ensl-00979074
Author Lescanne, Pierre
Maintainer CCSD
Last Updated May 5, 2026, 12:53 (UTC)
Created May 5, 2026, 12:53 (UTC)
Identifier ensl-00979074
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire de l'Informatique du Parallélisme (LIP) ; École normale supérieure de Lyon (ENS de Lyon) ; Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL) ; Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)
creator Lescanne, Pierre
date 2014-04-28T00:00:00
harvest_object_id ab9fc206-e6f4-4a9d-80cd-ddb26a9e0b68
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-10-13T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1404.3875
set_spec type:UNDEFINED