/*---------------------------------------------------------------------------
  Copyright 2020-2021, Microsoft Research, Daan Leijen.

  This is free software; you can redistribute it and/or modify it under the
  terms of the Apache License, Version 2.0. A copy of the License can be
  found in the LICENSE file at the root of this distribution.
---------------------------------------------------------------------------*/

/* Random numbers.
*/
module std/num/randomstd/num/random

import std/num/int32std/num/int32
import std/num/int64std/num/int64
import std/num/float64std/num/float64

extern import
  js file "random-inline.js"

pubstd/num/random/random: (E, V) -> V effect randomstd/num/random/random: (E, V) -> V
  fun random-int32() : int32std/core/types/int32: V

pub fun @default-random(actionaction: () -> <random,ndet|$520> $519 : () -> <randomstd/num/random/random: (E, V) -> V,ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> <ndet|535> 534 : <ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V
  strong-randomstd/num/random/strong-random: (action : () -> <random,ndet|$520> $519) -> <ndet|$520> $519(actionaction: () -> <random,ndet|$520> $519)

// Pick random numbers from a the best strong random source in the OS.
// (e.g. like `/dev/urandom`, `arc4random` etc.). Use `srandom-is-strong` to test if the
// numbers are indeed based on a strong random source.
pub fun strong-randomstd/num/random/strong-random: forall<a,e> (action : () -> <random,ndet|e> a) -> <ndet|e> a(actionaction: () -> <random,ndet|$448> $447 : () -> <randomstd/num/random/random: (E, V) -> V,ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> <ndet|512> 511 : <ndetstd/core/types/ndet: X|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V
  withhandler: (() -> <random,ndet|$448> $447) -> <ndet|$448> $447 fun random-int32random-int32: () -> <ndet|$448> int32() srandom-int32std/num/random/srandom-int32: () -> <ndet|$448> int32()
  actionaction: () -> <random,ndet|$448> $447()

// Pseudo random number using sfc32 by Chris Doty-Humphrey.
// It is a "chaotic" pseudo random generator that uses 32-bit operations only
// (so we can be deterministic across architectures in results and performance).
// It has good statistical properties and passes PractRand and Big-crush.
// It uses a 32-bit counter to guarantee a worst-case cycle
// of 2^32. It has a 96-bit state, so the average period is 2^127.
// The chance of a cycle of less than 2^(32+max(96-k,0)) is 2^-(32+k),
// (e.g. the chance of a cycle of less than 2^48 is 2^-80).
// <https://pracrand.sourceforge.net/RNG_engines.txt>
abstract value struct sfcstd/num/random/sfc: V(xresult: -> total int32:int32std/core/types/int32: V, yresult: -> total int32:int32std/core/types/int32: V, zresult: -> total int32:int32std/core/types/int32: V, cntstd/num/random/sfc/cnt: (sfc : sfc) -> int32:int32std/core/types/int32: V)

pub value struct sfc-resultstd/num/random/sfc-result: V( rndstd/num/random/sfc-result/rnd: (sfc-result) -> int32 : int32std/core/types/int32: V, rstatestd/num/random/sfc-result/rstate: (sfc-result) -> sfc : sfcstd/num/random/sfc: V )

pub fun sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> sfc-result( sfcsfc: sfc : sfcstd/num/random/sfc: V )result: -> total sfc-result : sfc-resultstd/num/random/sfc-result: V
  match sfcsfc: sfc
    Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc(xx: int32,yy: int32,zz: int32,cntcnt: int32) ->
      val resres: int32 = xx: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 yy: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 cntcnt: int32
      Sfc-resultstd/num/random/Sfc-result: (rnd : int32, rstate : sfc) -> sfc-result( resres: int32, Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc( yy: int32 ^std/num/int32/(^): (x : int32, y : int32) -> int32 shrstd/num/int32/shr: (i : int32, shift : int) -> int32(yy: int32,9literal: int
dec = 9
hex8 = 0x09
bit8 = 0b00001001
), zz: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 shlstd/num/int32/shl: (i : int32, shift : int) -> int32(zz: int32,3literal: int
dec = 3
hex8 = 0x03
bit8 = 0b00000011
), rotlstd/num/int32/rotl: (i : int32, shift : int) -> int32(zz: int32,21literal: int
dec = 21
hex8 = 0x15
bit8 = 0b00010101
) +std/num/int32/(+): (x : int32, y : int32) -> int32 resres: int32, cntcnt: int32 +std/num/int32/(+): (x : int32, y : int32) -> int32 1literal: int
dec = 1
hex8 = 0x01
bit8 = 0b00000001
.int32std/num/int32/int32: (i : int) -> int32 )
) pub fun sfc-init32std/num/random/sfc-init32: (seed1 : int32, seed2 : int32) -> sfc( seed1seed1: int32 : int32std/core/types/int32: V, seed2seed2: int32 : int32std/core/types/int32: V )result: -> total sfc : sfcstd/num/random/sfc: V val sfc0sfc0: sfc = Sfcstd/num/random/Sfc: (x : int32, y : int32, z : int32, cnt : int32) -> sfc(0literal: int
dec = 0
hex8 = 0x00
bit8 = 0b00000000
.int32std/num/int32/int32: (i : int) -> int32, seed1seed1: int32, seed2seed2: int32, 1literal: int
dec = 1
hex8 = 0x01
bit8 = 0b00000001
.int32std/num/int32/int32: (i : int) -> int32) fold-int32std/num/int32/fold-int32: (n : int32, init : sfc, f : (int32, sfc) -> sfc) -> sfc( 12literal: int
dec = 12
hex8 = 0x0C
bit8 = 0b00001100
.int32std/num/int32/int32: (i : int) -> int32, sfc0sfc0: sfc, fnfn: (int32, s : sfc) -> sfc(_,ss: sfc){ sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> sfc-result(ss: sfc).rstatestd/num/random/sfc-result/rstate: (sfc-result) -> sfc }
) // step 12 times pub fun sfc-initstd/num/random/sfc-init: (seed : int) -> sfc( seedseed: int : intstd/core/types/int: V )result: -> total sfc : sfcstd/num/random/sfc: V sfc-init32std/num/random/sfc-init32: (seed1 : int32, seed2 : int32) -> sfc(seedseed: int.int32std/num/int32/int32: (i : int) -> int32, (seedseed: int /std/core/int/(/): (x : int, y : int) -> int 0x100000000literal: int
dec = 4294967296
hex64= 0x0000000100000000
bit64= 0b0000000000000000000000000000000100000000000000000000000000000000
).int32std/num/int32/int32: (i : int) -> int32
) // Use pseudo random numbers given some initial `seed`. At most // 64-bits of the initial seed are used. Do not use this for // cryptographic applications (use `strong-random` instead). // Uses _sfc32_ by Chris Doty-Humphrey which is a fast random // number generator with a 128-bit internal state which // passes PractRand and BigCrush. The worst case minimum cycle // is 2^^32^^, where a potential cycle of 2^^48^^ has a chance // of 2^^-80^^. pub fun pseudo-randomstd/num/random/pseudo-random: forall<a,e> (seed : int, action : () -> <random|e> a) -> e a( seedseed: int : intstd/core/types/int: V, actionaction: () -> <random|$655> $654 : () -> <randomstd/num/random/random: (E, V) -> V|std/core/types/effect-extend: (X, E) -> Eee: E> aa: V)result: -> 868 867 : ee: E aa: V var ss: local-var<$664,sfc> := sfc-initstd/num/random/sfc-init: (seed : int) -> <local<$664>|$655> sfc(seedseed: int) withhandler: (() -> <random,local<$664>|$655> $654) -> <local<$664>|$655> $654 fun random-int32random-int32: () -> <local<$664>|$655> int32() val sfcsfc: sfc-result = sfc-stepstd/num/random/sfc-step: (sfc : sfc) -> <local<$664>|$655> sfc-result(ss: sfc) ss: local-var<$664,sfc> :=std/core/types/local-set: (v : local-var<$664,sfc>, assigned : sfc) -> <local<$664>|$655> () sfcsfc: sfc-result.rstatestd/num/random/sfc-result/rstate: (sfc-result) -> <local<$664>|$655> sfc sfcsfc: sfc-result.rndstd/num/random/sfc-result/rnd: (sfc-result) -> <local<$664>|$655> int32 actionaction: () -> <random|$655> $654() // Return a random boolean pub fun random-boolstd/num/random/random-bool: () -> random bool()result: -> random bool : randomstd/num/random/random: (E, V) -> V boolstd/core/types/bool: V (random-int32std/num/random/random-int32: () -> random int32() >=std/num/int32/(>=): (x : int32, y : int32) -> random bool 0literal: int
dec = 0
hex8 = 0x00
bit8 = 0b00000000
.int32std/num/int32/int32: (i : int) -> random int32
) // Return a random integer in the range [-2^^31^^, 2^^31^^). pub fun random-intstd/num/random/random-int: () -> random int()result: -> random int : randomstd/num/random/random: (E, V) -> V intstd/core/types/int: V random-int32std/num/random/random-int32: () -> random int32().intstd/num/int32/int: (i : int32) -> random int pub fun random-int64std/num/random/random-int64: () -> random int64()result: -> random int64 : randomstd/num/random/random: (E, V) -> V int64std/core/types/int64: V int64std/num/int64/hilo32/int64: (hi : int32, lo : int32) -> random int64( random-int32std/num/random/random-int32: () -> random int32(), random-int32std/num/random/random-int32: () -> random int32()) // todo: add native random-int64? // Return a random float64 in the range [0,1) using 52-bits of randomness pub fun random-float64std/num/random/random-float64: () -> random float64()result: -> random float64 : randomstd/num/random/random: (E, V) -> V float64std/core/types/float64: V val magmag: int64 = random-int64std/num/random/random-int64: () -> random int64().shrstd/num/int64/shr: (i : int64, shift : int) -> random int64(12literal: int
dec = 12
hex8 = 0x0C
bit8 = 0b00001100
).orstd/num/int64/or: (int64, int64) -> random int64(0x3FF0_0000_0000_0000literal: int
dec = 4607182418800017408
hex64= 0x3FF0000000000000
bit64= 0b0011111111110000000000000000000000000000000000000000000000000000
.int64std/num/int64/int64: (i : int) -> random int64) (float64-from-bitsstd/num/float64/float64-from-bits: (i : int64) -> random float64(magmag: int64) -std/num/float64/(-): (x : float64, y : float64) -> random float64 1.0literal: float64
hex64= 0x1p0
) // Returns one of its arguments `x` or `y` based on a non-deterministic choice. pub fun choosestd/num/random/choose: forall<a> (x : a, y : a) -> ndet a( xx: $567: aa: V, yy: $567: aa: V)result: -> ndet 580 : ndetstd/core/types/ndet: X aa: V if srandom-boolstd/num/random/srandom-bool: () -> ndet bool() then xx: $567 else yy: $567 // Return a strong random boolean pub fun srandom-boolstd/num/random/srandom-bool: () -> ndet bool()result: -> ndet bool : ndetstd/core/types/ndet: X boolstd/core/types/bool: V (srandom-int32std/num/random/srandom-int32: () -> ndet int32() >=std/num/int32/(>=): (x : int32, y : int32) -> ndet bool 0literal: int
dec = 0
hex8 = 0x00
bit8 = 0b00000000
.int32std/num/int32/int32: (i : int) -> ndet int32
) // Return a strong random integer in the range [-2^^31^^, 2^^31^^). pub fun srandom-intstd/num/random/srandom-int: () -> ndet int()result: -> ndet int : ndetstd/core/types/ndet: X intstd/core/types/int: V srandom-int32std/num/random/srandom-int32: () -> ndet int32().intstd/num/int32/int: (i : int32) -> ndet int // Return a strong random `:int32` pub extern srandom-int32std/num/random/srandom-int32: () -> ndet int32: () -> ndetstd/core/types/ndet: X int32std/core/types/int32: V c inline "(int32_t)kk_srandom_uint32(kk_context())" js "_srandom_int32" // Return a strong random `:float64` in the range [0,1) using 52-bits of randomness pub extern srandom-float64std/num/random/srandom-float64: () -> ndet float64 : () -> ndetstd/core/types/ndet: X float64std/core/types/float64: V c "kk_srandom_double" js "_srandom_double" // Are the strong random numbers generated from a strong random source? (like /dev/urandom) pub extern srandom-is-strongstd/num/random/srandom-is-strong: () -> ndet bool: () -> ndetstd/core/types/ndet: X boolstd/core/types/bool: V c "kk_srandom_is_strong" js "_srandom_is_strong" // Return a strong random `:int32` uniformly distributed in the range [lo,hi) pub extern srandom-int32-rangestd/num/random/srandom-int32-range: (lo : int32, hi : int32) -> ndet int32(lolo: int32 : int32std/core/types/int32: V, hihi: int32 : int32std/core/types/int32: V) : ndetstd/core/types/ndet: X int32std/core/types/int32: V c "kk_srandom_range_int32" js "_srandom_range_int32" // Generate a strong random float64 uniformly distributed in the range [lo, hi) pub fun srandom-float64-rangestd/num/random/srandom-float64-range: (lo : float64, hi : float64) -> ndet float64(lolo: float64 : float64std/core/types/float64: V, hihi: float64 : float64std/core/types/float64: V)result: -> ndet float64 : ndetstd/core/types/ndet: X float64std/core/types/float64: V val lowlow: float64 = if lolo: float64 <=std/num/float64/(<=): (x : float64, y : float64) -> ndet bool hihi: float64 then lolo: float64 else hihi: float64 val highhigh: float64 = if lolo: float64 <=std/num/float64/(<=): (x : float64, y : float64) -> ndet bool hihi: float64 then hihi: float64 else lolo: float64 val xx: float64 = ((highhigh: float64 -std/num/float64/(-): (x : float64, y : float64) -> ndet float64 lowlow: float64) *std/num/float64/(*): (x : float64, y : float64) -> ndet float64 srandom-float64std/num/random/srandom-float64: () -> ndet float64()) +std/num/float64/(+): (x : float64, y : float64) -> ndet float64 lowlow: float64 if xx: float64 >=std/num/float64/(>=): (x : float64, y : float64) -> ndet bool highhigh: float64 then lowlow: float64 else xx: float64 // can happen due to rounding