[swift-evolution] [Proposal] Random Unification

Brent Royal-Gordon brent at architechies.com
Sat Sep 9 07:08:42 CDT 2017


> On Sep 8, 2017, at 2:46 PM, Jacob Williams via swift-evolution <swift-evolution at swift.org> wrote:
> 
> What if we did it with something like this:
> 
> protocol RandomGenerator {
> 	associated type T: Numeric // Since numeric types are the only kinds where we could get a random number?
> 	func uniform() -> T
> 	// Other random type functions...
> }
> 
> Although if we didn’t constrain T to Numeric then collections could also conform to it, although I’m not sure that collections would want to directly conform to this. There may need to be a separate protocol for types with Numeric indexes?
> 
> I’m no pro and really haven’t thought about this too deeply. Mostly just spitballing/brainstorming.

I think I would simply say:

	/// Conforming types generate an infinite sequence of random bits through their `next()` method.
	/// They may be generated from a repeatable seed or from a source of true entropy.
	protocol Randomizer: class, IteratorProtocol, Sequence where Element == UInt, Iterator == Self {
		/// Generates and returns the next `UInt.bitWidth` bits of random data.
		func next() -> UInt
	}

And have this extension on it:

	extension Randomizer {
		/// Permits the use of a Randomizer as a plain old iterator.
		func next() -> UInt? {
			return Optional.some(next())
		}
		
		/// Returns a number in the range 0 ... maximum.
		/// (This is inclusive to allow `maximum` to be `UInt.max`.)
		func next(through maximum: UInt) -> UInt {
			…
		}
	}

We should also provide a singleton `StrongRandomizer`:

	/// A source of cryptographically secure random data.
	/// 
	/// `StrongRandomizer` typically uses the strongest random data source provided by  
	/// the platform that is suitable for relatively frequent use. It may use a hardware RNG 
	/// directly, or it may use a PRNG seeded by a good entropy source.
	/// 
	/// `StrongRandomizer` is inherently a singleton.
	/// It can be used on multiple threads, and on some platforms it may block while its 
	/// shared state is locked.
	class StrongRandomizer: Randomizer {
		static let shared = StrongRandomizer()
		
		func next() -> UInt {
			…
		}
	}

Finally, we can add extensions to `RandomAccessCollection`:

	extension RandomAccessCollection {
		func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Element? {
			guard !isEmpty else { return nil }
			let offset = IndexDistance(randomizer.next(through: UInt(count) - 1))
			return self[index(startIndex, offsetBy: offset)]
		}
	}

And ranges over `BinaryFloatingPoint`:

	extension Range where Bound: BinaryFloatingPoint {
		func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Bound? {
			…
		}
	}
	extension ClosedRange where Bound: BinaryFloatingPoint {
		func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Bound {
			…
		}
	}

A couple of notes:

• Fundamentally, a randomizer is an infinite sequence of random-ish bits. I say "random-ish" because you may be generating a repeatable pseudo-random sequence from a seed. But in any case, I think it's best to envision this as a special case of an iterator—hence the `IteratorProtocol` conformance.

• Randomizer is class-constrained because we want to encourage providing a defaulted parameter for the randomizer, and `inout` parameters can't be defaulted.

• `UInt` is intentionally inconvenient. You should not usually use a randomizer directly—you should pass it to one of our methods, which know how to handle it correctly. Making it awkward discourages direct use of the randomizer.

• `next(through:)` is provided simply to discourage incorrect modulo-ing.

• `StrongRandomizer` is provided as a slow but safe default. I don't think we should ship any other RNGs; people who want them can import them from modules, which provides at least a bit of evidence that they know what they're doing. (Actually, I could see adding a second RNG that's even stronger, and is specifically intended to be used infrequently to generate seeds or important cryptographic keys.)

-- 
Brent Royal-Gordon
Architechies

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170909/e456c389/attachment.html>


More information about the swift-evolution mailing list