Translation of various functions from
Not all of them, but only what is needed to support the other Dex
examples. We also skip some functions that already exist in
Futhark, but under different names - we’ll keep writing
def sq (x: f64) = x * x def mean [n] (xs: [n]f64) : f64 = f64.sum xs / f64.i64 n def std [n] (xs: [n]f64) = f64.sqrt (mean (map sq xs) - sq (mean xs)) def linspace (n: i64) (start: f64) (end: f64) : [n]f64 = tabulate n (\i -> start + f64.i64 i * ((end-start)/f64.i64 n))
Some Dex programs use this sequential scan.
def scan' n x0 f = 0) <| (.loop (arr, acc) = (replicate n x0, x0) for i < n do let acc' = f i acc in (arr with [i] = acc', acc')
The random numbers defined in random-numbers.fut are based on the idea of having functions take and return random number states. Dex’s approach to random numbers is based on splitting and never returning the final state. Both work fine in Futhark. The biggest difference is that the Dex implementation uses a high-quality hash algorithm, and we use a hash function found on StackOverflow:
type Key = #Key u32 def hash (k : Key) (y: i32): Key = match k case #Key x -> let x = x ^ u32.i32 y let x = ((x >> 16) ^ x) * 0x45d9f3b let x = ((x >> 16) ^ x) * 0x45d9f3b let x = ((x >> 16) ^ x) in #Key x def newKey = hash (#Key 0) def splitKey k = (hash k 1, hash k 2) def splitKey3 k = let (a, k') = splitKey k let (b, c) = splitKey k' in (a,b,c) def many '^a (f: Key -> a) (k: Key) (i: i64) = f (hash k (i32.i64 i)) def ixkey (k: Key) (i: i64) : Key = hash k (i32.i64 i) def ixkey2 (k: Key) (i: i64) (j: i64) : Key = hash (hash k (i32.i64 i)) (i32.i64 j)def rand (k: Key) : f64 = match k case #Key x -> f64.u32 x / f64.u32 u32.highestdef randVec 'a (n: i64) (f: Key -> a) (k: Key) : [n]a = tabulate n (\i -> f (ixkey k i)) def randn (k: Key) : f64 = let (k1, k2) = splitKey k let u1 = rand k1 let u2 = rand k2 in f64.sqrt ((-2.0) * f64.log u1) * f64.cos (2.0 * f64.pi * u2) def bern (p: f64) (k: Key) = rand k < p def randnVec (n: i64) (k: Key) : [n]f64 = tabulate n (ixkey k >-> randn)
randIdx function computes a random index into an array. In
Dex, where indexes are types, this is done by passing in the size
of the array as an implicit parameter, and using type inference to
determine the right size for any given application. In Futhark,
randIdx is just an elaborate way of generating an integer up to
an explicitly given bound.
def randIdx (n: i64) (k: Key) = let unif = rand k in i64.f64 (f64.floor (unif * f64.i64 n))