package boltzgen

BoltzGen

BoltzGen: Boltzmann sampler test generator is a tool to generate tests. Given a function signature, it generates a random set of calls to this function with randomly generated inputs. Inputs are generated using a Boltzmann sampler for unlabeled structures.

This project has the following goals:

• Generate values with as little information as possible, in most cases only requiring its type; the input by the user should be as minimal as possible

• The function to test is assumed to be pure

• The primary goal was developing an automatic grading system for functional programming exercises

On Boltzmann Samplers

You can read about Boltzmann samplers at https://en.wikipedia.org/wiki/Boltzmann_sampler. The idea is that, given rules that a structure must follow (similar to a type definition), a measure of the size of a structure (the number of bits in memory or the length of a string representing it for an OCaml value), and the average size of structures you want to generate, a Boltzmann sampler will generate structures such that structures of the same size have the same probability of being generated and the desired average size is respected.

Don't be afraid of the mathematical abstraction - Boltzmann samplers can be implemented in a tractable way.

Examples for the commandline tool

You can try it online here: https://barbot.pages.lacl.fr/boltzgen/ Or in a terminal with:

>./boltzgen "val sum: int -> int -> int" --value-only -n 10
sum 19 (-7)
sum (-20) (-19)
sum (-8) (-3)
sum (-6) (-11)
sum 2 16
sum 1 (-19)
sum (-2) (-14)
sum (-13) 4
sum (-2) 9
sum (-2) 2

In this simple example, integers have been generated.

In a more involved example featuring recursive algebraic types, we obtain the following:

>./boltzgen "type 'a tree = Empty | Node of 'a tree*'a*'a tree 
  val flatten: int list tree -> int tree" --value-only -n 10 -b 10
flatten (Node((Empty,[],Empty)))
flatten Empty
flatten (Node(((Node((Empty,[],Empty))),[0],(Node((Empty,[(-2)],Empty))))))
flatten (Node(((Node((Empty,[12],(Node((Empty,[],Empty)))))),[],Empty)))
flatten (Node((Empty,[],(Node((Empty,[(-12); 1],Empty))))))
flatten (Node(((Node(((Node((Empty,[],Empty))),[],Empty))),[],(Node((Empty,[(-17); (-10)],(Node(((Node(((Node((Empty,[],Empty))),[],(Node(((Node(((Node((Empty,[],(Node((Empty,[(-8); (-4)],Empty)))))),[(-4)],Empty))),[(-11); (-13)],(Node((Empty,[0],Empty))))))))),[],(Node((Empty,[],Empty))))))))))))
flatten (Node(((Node((Empty,[13; (-5); 0],(Node((Empty,[],Empty)))))),[],Empty)))
flatten (Node(((Node((Empty,[(-14)],Empty))),[(-19); (-12); (-10)],Empty)))
flatten (Node((Empty,[],(Node((Empty,[],(Node((Empty,[18],(Node(((Node((Empty,[(-5)],Empty))),[],Empty))))))))))))
flatten (Node((Empty,[],(Node((Empty,[],Empty))))))

If given two OCaml implementation files, the tool will check that both of them match the signature given as an argument, generate tests for the first function in the signature, and report differences in behavior between the functions in the two files.

Examples for the Library

OCaml values can be generated at runtime. Here is a minimal example:

open Boltzgen

(* Define a new type as a sum type *)
type 'a mal = F | N of 'a * 'a mal

(* Define a function consuming that type *)
let rec size = function 
  | F -> 0 
  | N (_, q) -> 1 + size q

let _ =
  Random.self_init ();
  (* Make the generator aware of the new type *)
  Runtime.eval_typedef "type 'a mal = F | N of 'a * 'a mal";
  (* Generate a value for type "int mal" *)
  let v = Runtime.rand_value ~size:100.0 "int mal" in
  let n = size v in
  Format.printf "Value: %a@. Size: %i@."
    (fun f -> Runtime.print_value f "int mal")
    v n

Standard Type Library

The following OCaml types are recognized by BoltzGen:

• int, char, float, string, unit

• 'a option

• 'a list

• 'a array

• ('a, 'e) result

Additionally, new types exist to control sampling with more constraints:

• nat: natural integer

• natp: positive natural integer

• bits: integer between 0 and max_int

• simple_string, id_string, simple_spaced_string: different kinds of strings

To Do, Caveats, and History

This tool was developed during the first COVID-19 lockdown in France to grade programming exercises in order to make them more interactive. The tool includes only what I needed for my students and was written in haste, thus many limitations remain:

• A simpler way to build new generators for base types is lacking

• No support for objects, modules, or labeled parameters for functions

• The documentation is minimal

• Ideally, samplers should be derived at compile time

This project could be used for unit testing and should be integrated into a testing framework, which will require some changes to the API. The API documentation is available at https://barbot.pages.lacl.fr/boltzgen/doc/.

Changelog

• 0.9.5: Refactoring, documentation, dot output

• 0.9.4: Added records, and now able to generate arbitrary values at runtime directly as OCaml values. Useful for testing higher-order functions.

• 0.9.3: Added recursive mutual types.

• 0.9.2: Polishing and added array support.

• 0.9.1: First public release.