louise
The Louise language: compiler, runtime, std, tooling
Clone avec HTTPS, un jeton personnel en mot de passe, ou avec SSH, une clé ajoutée dans vos paramètres.
Dernier runRéussi#88 · main · 15 min 30 s
0Étoiles
0Forks
40Issues
| 1 | /// Randomness, as an effect (ADR 0036). |
| 2 | /// |
| 3 | /// random.int(6) + 1 // a die |
| 4 | /// random.token(16) // 32 hex characters, for a session |
| 5 | /// random.shuffle([1, 2, 3]) |
| 6 | /// |
| 7 | /// Every function here reads random bytes through the `random` effect's one |
| 8 | /// operation. The runtime handles it around `main`, each test and each |
| 9 | /// actor, with the kernel's generator (`getrandom`/`/dev/urandom`): good |
| 10 | /// for tokens and salts. A test can choose the bytes instead: |
| 11 | /// |
| 12 | /// random.with_seed(7, fn() { random.int(100) }) // always the same |
| 13 | /// |
| 14 | /// A handler installed with `with_seed` (or `handle`) does not follow |
| 15 | /// `process.spawn`: a new actor always gets the system's randomness. |
| 16 | |
| 17 | import std/array.{type Array} |
| 18 | import std/bytes as raw |
| 19 | import std/float |
| 20 | import std/int as bits |
| 21 | import std/list |
| 22 | import std/prng |
| 23 | import std/ref |
| 24 | import std/string |
| 25 | import std/u64 |
| 26 | |
| 27 | /// Random bytes. |
| 28 | pub effect random |
| 29 | { |
| 30 | /// `count` random bytes; panics if `count` is negative. |
| 31 | fn bytes :: count: Int -> Bytes |
| 32 | } |
| 33 | |
| 34 | /// A uniformly random Int in `0..below` (`below` excluded); panics unless |
| 35 | /// `below` is positive. Any size: `random.int(bits.shift_left(1, 128))`. |
| 36 | pub fn int :: below: Int -> Int / <random> |
| 37 | { |
| 38 | if below < 1 |
| 39 | { |
| 40 | panic "random.int: the bound must be positive, got {below}" |
| 41 | } |
| 42 | let width = bits.bit_length (below - 1) |
| 43 | below_by_rejection below width |
| 44 | } |
| 45 | |
| 46 | /// Rejection sampling: draw `width` bits until they are below `below`, so |
| 47 | /// every value is equally likely (fewer than 2 draws on average). |
| 48 | fn below_by_rejection :: below: Int width: Int -> Int / <random> |
| 49 | { |
| 50 | if width == 0 |
| 51 | { |
| 52 | 0 |
| 53 | } |
| 54 | else |
| 55 | { |
| 56 | let v = bits.low_bits (big_endian (bytes ((width + 7) / 8))) width |
| 57 | if v < below |
| 58 | { |
| 59 | v |
| 60 | } |
| 61 | else |
| 62 | { |
| 63 | below_by_rejection below width |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | /// A uniformly random Int in `low..=high` (both included); panics if |
| 69 | /// `high < low`. |
| 70 | pub fn range :: low: Int high: Int -> Int / <random> |
| 71 | { |
| 72 | if high < low |
| 73 | { |
| 74 | panic "random.range: {high} is below {low}" |
| 75 | } |
| 76 | low + int (high - low + 1) |
| 77 | } |
| 78 | |
| 79 | /// A uniformly random Float in `[0, 1)`, from 53 random bits. |
| 80 | pub fn float :: -> Float / <random> |
| 81 | { |
| 82 | let v = bits.shift_right (big_endian (bytes 7)) 3 |
| 83 | float.from_int v / 9007199254740992.0 |
| 84 | } |
| 85 | |
| 86 | /// `xs` in a random order (Fisher–Yates: every order equally likely). |
| 87 | pub fn shuffle :: xs: List<a> -> List<a> / <random> |
| 88 | { |
| 89 | array.to_list (shuffle_from (array.from_list xs) (list.length xs - 1)) |
| 90 | } |
| 91 | |
| 92 | fn shuffle_from :: a: Array<a> i: Int -> Array<a> / <random> |
| 93 | { |
| 94 | if i < 1 |
| 95 | { |
| 96 | a |
| 97 | } |
| 98 | else |
| 99 | { |
| 100 | let j = int (i + 1) |
| 101 | match (array.get a i, array.get a j) |
| 102 | { (Some(x), Some(y)) -> |
| 103 | shuffle_from (array.set (array.set a i y) j x) (i - 1) |
| 104 | , _ -> a |
| 105 | } |
| 106 | } |
| 107 | } |
| 108 | |
| 109 | /// A random element of `xs`; `None` if it is empty. |
| 110 | pub fn choice :: xs: List<a> -> Option<a> / <random> |
| 111 | { |
| 112 | match xs |
| 113 | { [] -> None, _ -> array.get (array.from_list xs) (int (list.length xs)) } |
| 114 | } |
| 115 | |
| 116 | /// `count` random bytes as lowercase hexadecimal (`2 * count` characters), |
| 117 | /// for tokens and salts. |
| 118 | pub fn token :: count: Int -> String / <random> |
| 119 | { |
| 120 | let digits = raw.to_list (bytes count) |> list.map hex_byte |
| 121 | string.concat digits |
| 122 | } |
| 123 | |
| 124 | fn hex_byte :: b: Int -> String |
| 125 | { |
| 126 | "{hex_digit (b / 16)}{hex_digit (b % 16)}" |
| 127 | } |
| 128 | |
| 129 | fn hex_digit :: d: Int -> String |
| 130 | { |
| 131 | match d |
| 132 | { 10 -> "a" |
| 133 | , 11 -> "b" |
| 134 | , 12 -> "c" |
| 135 | , 13 -> "d" |
| 136 | , 14 -> "e" |
| 137 | , 15 -> "f" |
| 138 | , _ -> show d |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | /// The bytes as an unsigned big-endian integer. |
| 143 | fn big_endian :: b: Bytes -> Int |
| 144 | { |
| 145 | list.fold (raw.to_list b) 0 fn acc x { bits.or (bits.shift_left acc 8) x } |
| 146 | } |
| 147 | |
| 148 | /// Run `action` with random bytes from a SplitMix64 generator seeded with |
| 149 | /// `seed` (`std/prng`): the same seed gives the same values, on every |
| 150 | /// backend and every run. Each `bytes(n)` draws `ceil(n / 8)` outputs and |
| 151 | /// takes their bytes, low first. **Not for secrets**, only for tests and |
| 152 | /// simulations. |
| 153 | pub fn with_seed :: seed: Int action: fn() -> a / <random | e> -> a / <e> |
| 154 | { |
| 155 | region |
| 156 | { |
| 157 | let state = ref.new (prng.seeded seed) |
| 158 | handle |
| 159 | { |
| 160 | action () |
| 161 | } |
| 162 | with |
| 163 | { bytes count -> |
| 164 | { |
| 165 | if count < 0 |
| 166 | { |
| 167 | panic "random.bytes: negative count {count}" |
| 168 | } |
| 169 | let (out, next) = draw (ref.get state) count (raw.builder ()) |
| 170 | ref.set state next |
| 171 | out |
| 172 | } |
| 173 | } |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | /// `count` bytes from `g`, appended to `acc`; the generator after them. |
| 178 | fn draw :: g: prng.Prng count: Int acc: raw.Builder -> (Bytes, prng.Prng) |
| 179 | { |
| 180 | if count <= 0 |
| 181 | { |
| 182 | (raw.build acc, g) |
| 183 | } |
| 184 | else |
| 185 | { |
| 186 | let (x, next) = prng.next g |
| 187 | draw next (count - 8) (append_low acc x if count < 8 { count } else { 8 }) |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | /// The `n` low bytes of `x`, lowest first. |
| 192 | fn append_low :: acc: raw.Builder x: u64.U64 n: Int -> raw.Builder |
| 193 | { |
| 194 | if n == 0 |
| 195 | { |
| 196 | acc |
| 197 | } |
| 198 | else |
| 199 | { |
| 200 | let byte = u64.to_int (u64.and x (u64.from_int 255)) |
| 201 | append_low (raw.append_byte acc byte) (u64.shift_right x 8) (n - 1) |
| 202 | } |
| 203 | } |