Boltzmann samplers for random generation of lambda terms
type: Dataset
description: 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.
issued: 2026-05-05T12:53:43.786332
language: en
modified: 2026-05-05T12:53:43.786339
contact point: Organization
  fn: CCSD
keyword: boltzmann-sampler
keyword: combinatorics
keyword: functional-programming
keyword: infoeu-reposemanticspreprint
keyword: infoinfo-dscomputer-science-csdata-structures-and-algorithms-csds
keyword: infoinfo-locomputer-science-cslogic-in-computer-science-cslo
keyword: infoinfo-plcomputer-science-csprogramming-languages-cspl
keyword: lambda-calculus
keyword: preprints-working-papers-
keyword: random-generator
keyword: test
keyword: theory-of-computationrandomness-geometry-and-discrete-structures-generating-random-combinatorial
landing page: https://ens-lyon.hal.science/ensl-00979074

Boltzmann samplers for random generation of lambda terms
type: Distribution
format: HTML
issued: 2026-05-05T12:53:43.793032
modified: 2026-05-05T12:53:43.771648
access URL: https://ens-lyon.hal.science/ensl-00979074

test_moissonnage_selune
type: Agent