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
RandomSource: a source of random bits with Java’s derived draws (nextDouble,nextInt(bound),nextLong) and TLC’snextPrime. AnyFnMut(u32) -> i32is one, so the evaluator can carry a source without naming this crate.JavaRandom:java.util.Random, bit-exact.Streams: where each stream starts, underRandomMode::Tlc(TLC’s seeding) orRandomMode::Dive(replayable at any worker count).random_element,random_subset,random_set_of_subsets: the operators overdive_value::Values, drawing exactly as TLC’s Java overrides draw.
§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§
- Dive
Stream - dive’s random stream: draw
iof the stream keyed by(seed, domain, key)isSplitMix64(k + (i + 1) * γ), withka mix of the seed, domain and key. It is counter based, so drawidepends only on(seed, key, i): never on which worker evaluates it or what it evaluated before. - Java
Random 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§
- Random
Error - An error from a random operator, with TLC’s error class and message.
- Random
Mode - 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
RandomElementthrows a non-TLC exception. - RANDOM_
SET_ OF_ SUBSETS_ METHOD - The Java method TLC names when
RandomSetOfSubsetsthrows a non-TLC exception. - RANDOM_
SUBSET_ METHOD - The Java method TLC names when
RandomSubsetthrows a non-TLC exception.
Traits§
- Random
Source - 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
-seeddoes (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 setS(tlc2.module.TLC.RandomElement).- random_
set_ of_ subsets RandomSetOfSubsets(k, n, S):kpseudo-random subsets ofS, each containing each element ofSwith probabilityn / |S|, duplicates removed (tlc2.module.Randomization.RandomSetOfSubsets,SubsetValue.getRandomSetOfSubsetswithCoinTossingSubsetEnumerator). Drawsk * |S|doubles, in pick order and the normalized order ofS.- random_
subset RandomSubset(k, S):kpseudo-random elements of the finite setS, without repetition whilek <= |S|(tlc2.module.Randomization.RandomSubset, throughgetRandomSubsetof each set class). Fork > |S|the indices wrap around and the result is all ofS, as in TLC.