Random Lists

As kin has support for pattern matching and sequences at its heart, it's natural to formulate a random number generator as a generator of a sequence of random numbers.

For example, this is the same linear congruent shift register as used in java.util.Random:

    type lcsr ( seed : uint64 ) : seq [ uint32 ]
        def head : uint32 => uint32 ( self.seed >> 16 )
        def tail : lcsr => lcsr ( ( self.seed * 0x0005_deec_e66d + 0x0000_0000_000b ) & 0xffff_ffff_ffff )
    

You can wrap it in an actor if you want the same behaviour as a random function with hidden state:

    type @actor random_source ( sequence : seq[uint32] )
        def next_uint32 ( self ) : uint32
            let r = self.sequence.head
            self become ( sequence = self.sequence.tail )
            => r
        
        def next_real64 ( self ) : real64 
            => real64 ( natural ( self.next_uint32() ) ) / real64 ( natural ( uint32.max ) )

But you couldn't optimise matching on the value reported by a random function like you can with a pure sequence:

        let rnd_seq = lcsr ( 0x12345 )
        
        match rnd_seq
            0x00000001 :: 0xadfc5fc8 :: 0x22222222 :: 0x33333333 :: _ =>
                out <- "match one" <- endl
            0x00000001 :: 0xadfc5fc8 :: 0x9d1a5de6 :: 0xf6b685cf :: _ =>
                out <- "match two" <- endl
            _ => 
                out <- "no match" <- endl

The cons'd patterns are compiled to combinations of calls to seq.head or seq.tail. The first two matches get combined as the first couple of terms in the pattern are the same; if seq.head or seq.tail were not pure functions, the second match case would fail as the hidden state would change.


Tim Bray describes using this technique is "a sideways dance" in Haskell. I've always found Haskell a bit too 'stiff' and like to 'feel the bits between my toes' too much for it, but compared to the amount of messing around Java has to do with atomic longs (JDK7) or synchronized methods (GNU classpath) in the implementation of the random source, and then as an Iterable<Integer> if you want a sequence of random numbers, it doesn't seem too bad. In the Java case, either the runtime has to deduce that the interlocks are not required and remove them, or it has to process them; if the code is used in more than one place you may have to have more than one machine code compiled form of the method, or fall back to conservative locking always. For a pure sequence, no interlocks are required. Wrapping a sequence in a actor ( or a lazy list in a monad in Haskell ) gives you hidden variable behaviour if you want it without polluting the code of the sequence generator with synchronisation primitives.