SE-0202 Amendment Proposal: Rename Random to DefaultRandomNumberGenerator

Evolution Proposal Reviews
91

Jens, I agree with all the facts you brought up, but disagree on their interpretation. I know that performance concerns are close to your heart, so let me walk you through my understanding of the issues you raised and let’s see if we agree in the end.

In Swift Evolution we are trying to design perfect API in an imperfect language. Which means that while we are aiming for an ideal solution, we have to make compromises to accommodate the reality of Swift compiler and language as it stands today. It would be nice if we could hide all the accidental warts of the implementation behind a clean surface, but leaky abstractions do not let us achieve this utopia. I’ll attempt to come up with my own, incomplete, second amendment of SE-0202 to separate the clean interface we strive for, from the accidental details of the implementation that fall out of a drive for maximum performance. I’ll point those out separately at the end. Keep in mind that naming and usage patterns established in standard library set a strong precedent for the whole language, so we have a tough balancing act in front of us. Also note that all of what I’ll write (sans renaming) is already present in SE-0202 and it’s current implementation, whether it is readily apparent or not. Obviously, the discussion here shows that all of this subtlety lies in the eye of the beholder.

Random Unification

Main focus of this proposal is to create a unified random API, and access to secure source of randomness for all platforms. On top of this core it introduces utilities for generating random numbers and collection extensions for sampling and shuffling.

Randomness Generators

There are various techniques for generating random data, ranging from hardware generators to an ever-growing number of pseudorandom generators. They are making different trade-offs between computational difficulty and quality of the random distribution. Choosing the right kind of randomness generator depends on the application domain, there is no one-size-fits-all solution. To accommodate this we introduce:

public protocol RandomnessGenerator {
    mutating func bits() -> UInt64
}

Default Randomness Generator

The standard library will provide single, platform specific implementation of randomness generator. Platform vendors are free to choose the most appropriate solution. They should aim to provide cryptographically secure and reasonably performant implementation. Specifics of their implementation must be clearly documented (especially if they cannot meet the cryptographic security goal).

Access to a thread-safe instance of the default randomness generator is provided through the .default property on the type Random.

Custom Randomness Generators

The random API is designed to support custom randomness generator implementations. We expect that various implementations of seedable pseudorandom number generators will exist outside of standard library. To accommodate implementations based on classes as well as value types, the random API methods are declared mutable and take an inout using: argument of a type conforming to the RandomnessGenerator protocol.

Details about obtaining instances of custom generators are left intentionally unspecified, because we consider them to be out of scope for this proposal.

Type Random

To allow for implementation flexibility of the platform provided default randomness generator, its thread-safe instance is obtained from a static getter on the type Random. Because using type erasure would have prohibitive impact on performance, the precise return type is intentionally left out of this proposal, beyond the requirement that it returns a mutable and thread-safe instance of a type conforming to the RandomnessGenerator protocol.

let generator = Random.default

This also opens up a room for anchoring user extensions in a central and easily discoverable place. For example: a custom, seedable, pseudorandom number generator might provide a convenience initialization of an instance seeded from the default randomness generator as an extension on the type Random.

Applied Randomness

Randomness generators are used by higher-level APIs to turn the random bits into concrete applications. Intended usage pattern is to supply the method with randomness generator through the using: argument. When no custom randomness generator is provided, the Random.default will be used.

Other clients of RandomGenerator are expected to adopt the same pattern:

TK example from @nnnnnnnn that uses RG to build Gaussian distributions

Examples below assume an instance of custom randomness generator is available in the context:

// hypothetical generator, not provided by standard library
var customGenerator = Xoroshiro(seededWith: &Random.default)

Following, most common use cases are provided by the standard library.

Random Number Generation

Extensions methods for FixedWidthInteger and BinaryFloatingPoint for generating numbers in a given range. These implementations avoid the modulo bias commonly introduced in naive hand-rolled solutions.

Double.random(in: 0 ... .pi, using: &customGenerator)
Float.random(in: 0 ..< 1)
Int.random(in: 0 ..< 10, using: &customGenerator)
UInt.random(in: .min ... .max) // Full width

Coin Flipping

Bool.random()
Bool.random(using: &customGenerator)

Collection Sampling

New randomElement extension method on Collection protocol returns a random element from the collection. To account for empty collection case this method returns an Optional, modeled after collection methods like .first and .last.

let dice = 1...6 
// Rolling the 🎲; returns Optional<Int>
dice.randomElement()!
dice.randomElement(using: &customGenerator)!

Shuffling

New shuffled extension method on Sequence is added that returns the elements from sequence in random order as a new Array.

let dnaFragment = "AUGAAATGAACGUAG"
// Simulate DNA mutations
dnaFragment.shuffled() // New scrambled sequence: `[Character]`
dnaFragment.shuffled(using: &customGenerator)

For a MutableCollection we’ve added a mutating method shuffle, which randomly reorders the collection elements in place.

var cardDeck = "♥️♣️♦️♠️".map { 
   suit in "A23456789🔟JQK".map {
       rank in "\(rank)\(suit)" }}
// Reorder the array elements in place
cardDeck.shuffle()
cardDeck.shuffle(using: &customGenerator)

I’ve tried to extract what I saw as the essence of the SE-0202, removing unnecessary implementation details from the proposal, so that the resulting specification leaves us more wiggle room with final implementation. At the same time I took a liberty to rename certain parts of the API to further separate concepts whose conflation leads to misuse potential @Ben_Cohen’s concerned about:

  • RandomnessGenerator (instead of RandomNumberGenerator) that vends .bits() to further separate the two concepts and steer users that need numbers towards the proper ranged API on the numeric types. I think that let i = Int(Random.default.bits() % n) is plenty of warning for anybody not seeking to intentionally abuse the API. Omitting the Numbers from the core protocol name could help steer learners towards the right place. In worst case we could still fall back to .defaultGenerator as was suggested before by @gwendal.roue.
  • I speak generically about type Random to avoid committing the implementation to specific choice between struct or enum and I leave out the concrete return type of the .default getter in case we need to adjust that due to memory ownership requirements as @Joe_Groff mentioned. Main point was to focus on its role as facade, rather then on the details of how that’s achieved in practice (we can have struct Random do double duty for minimal stdlib footprint, or have enum Random and SystemDefaultRandomnessGenerator split the duties — all just an implementation detail).

My point is that these aspects should be discussed in code review on GitHub PR, not on SE. We went too deep down the implementation rabbit hole, because SE-0202 as it stands commits to too many accidental implementation details, yet still leaves some important questions unaddressed. I didn’t go into the Detailed Design section, but if we really want to properly amend SE-0202, that part would definitely need more detailed specification of the guaranties provided by the higher-level RNG methods as most-clearly summarized by @jawbroken, which you’ve raised in that other thread:

This isn’t meant as a critique of excellent job @Alejandro did driving the original proposal forward. It’s just a symptom of how it was lifted from the implementation. It is an aspect our process, which now requires working implementation for SE proposals, we need to be more cognizant of in the future. I hope I didn’t mess up too badly in my reinterpretation and @Alejandro, @benrimmington, @lorentey and others who drove and reviewed the implementation together, would correct me if I did.

While searching online for the Xoroshiro initializer for my example, I came across the RandomKit library by Nikolai Vazquez (who was last active on SE back in Dec '15). I haven’t seen it mentioned anywhere on the pitch thread, but the final SE-0202 looks like a stripped down, minimal version of RandomKit. The similarity is remarkable, down to defining:

Int.random(in: 0 ..< 1, using: &randomGenerator)

But his version returns optional. His core protocol is named RandomGenerator and it’s also passaed as inout. I’m assuming independent invention here, showing how performance demands ultimately drive the implementation design. I think it is also worth exploring RandomKit for future directions and get the author involved in SE process again. :v: