Skip to main content

Module random

Module random 

Source
Expand description

TLC’s randomness, bit-exact, and dive’s replayable randomness.

TLC’s random operators are unseeded unless -seed is given; its draws while expanding a state also depend on the fingerprint polynomial, and in simulation on which worker ran a trace, so -seed alone does not replay them. dive always reports the seed it used, and --seed alone replays a run exactly at any worker count; --compat=tlc reproduces TLC’s draws bit for bit. See Differences from TLC.

§Layers

§Using it from the evaluator and the checker

The checker owns the streams: it asks Streams::startup for constant definitions, ASSUMEs and Init, and Streams::state once per expanded state (TLC: fingerprint(state) ^ seed). The evaluator passes the current stream down to the operator as a &mut dyn FnMut(u32) -> i32:

use dive_stdlib::random::{random_element, RandomMode, RandomSource, Streams};
use dive_value::{Ctx, Int, Value, print::print_value};

let ctx = Ctx::tlc();
let streams = Streams::new(7, RandomMode::Tlc);
let mut stream = streams.startup();
// What dive-eval would carry in its context:
let mut bits = |n| stream.next_bits(n);
let s = Value::interval(Int::from(1i64), Int::from(1_000_000i64), ctx);
let v = random_element(&s, ctx, &mut bits)?;
// Under TLC -seed 7, `RandomElement(1..1000000)` is 730700.
assert_eq!(print_value(&v, ctx)?, "730700");

Under RandomMode::Tlc, Streams::state needs TLC’s own state fingerprint, which depends on TLC’s variable order; under RandomMode::Dive any fixed 64-bit state fingerprint gives a replayable run.

Structs§

DiveStream
dive’s random stream: draw i of the stream keyed by (seed, domain, key) is SplitMix64(k + (i + 1) * γ), with k a mix of the seed, domain and key. It is counter based, so draw i depends only on (seed, key, i): never on which worker evaluates it or what it evaluated before.
JavaRandom
java.util.Random, bit-exact: the 48-bit linear congruential generator of Knuth, TAOCP vol. 2 §3.2.1, as Java specifies it.
Streams
The run’s seed and seeding: hands out the random stream for each evaluation.

Enums§

RandomError
An error from a random operator, with TLC’s error class and message.
RandomMode
Which seeding a run uses.
Stream
A random stream: TLC’s generator or dive’s.

Constants§

RANDOM_ELEMENT_METHOD
The Java method TLC names when RandomElement throws a non-TLC exception.
RANDOM_SET_OF_SUBSETS_METHOD
The Java method TLC names when RandomSetOfSubsets throws a non-TLC exception.
RANDOM_SUBSET_METHOD
The Java method TLC names when RandomSubset throws a non-TLC exception.

Traits§

RandomSource
A source of random bits, with the derived draws TLC uses.

Functions§

fresh_seed
A fresh seed for a run without --seed, as TLC draws one without -seed (new RandomGenerator().nextLong(), seeded from the clock). dive always reports the seed it used, so the run can be replayed.
parse_seed
Parses a seed as TLC’s -seed does (Long.parseLong): an optional + or - and decimal digits, within the range of a 64-bit signed integer.
random_element
RandomElement(S): a pseudo-random element of the finite set S (tlc2.module.TLC.RandomElement).
random_set_of_subsets
RandomSetOfSubsets(k, n, S): k pseudo-random subsets of S, each containing each element of S with probability n / |S|, duplicates removed (tlc2.module.Randomization.RandomSetOfSubsets, SubsetValue.getRandomSetOfSubsets with CoinTossingSubsetEnumerator). Draws k * |S| doubles, in pick order and the normalized order of S.
random_subset
RandomSubset(k, S): k pseudo-random elements of the finite set S, without repetition while k <= |S| (tlc2.module.Randomization.RandomSubset, through getRandomSubset of each set class). For k > |S| the indices wrap around and the result is all of S, as in TLC.