SE-0202: Random Unification

Ben_Cohen · March 23, 2018, 7:57pm

Hello Swift Community,

The review of SE-0202: Random Unification begins now and runs through April 3, 2018.

Reviews are an important part of the Swift evolution process. All reviews should be made in this thread on the Swift forums or, if you would like to keep your feedback private, directly in email to me as the review manager.

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

More information about the Swift evolution process is available on the Swift Evolution website.

As always, thank you for participating in Swift Evolution.

Ben Cohen
Review Manager

tkrajacic · March 23, 2018, 9:18pm

+1 Looks pretty good and simple to use.

pvieito · March 23, 2018, 9:37pm

+1. Extremely positive on the proposal and implementation.

Sure it is.

Yes.

Any common language. I agree with the proposal that when the random source is not available the process should be aborted. Swift should have a safe random implementation and the cases where the random source is not available would be extremely rare.

Reading the proposal.

Nevin · March 23, 2018, 9:47pm

There is a lot to cover here (the pre-proposal discussion thread has well over 200 posts!)

First, the text of the proposal itself could use a little work. One example is where the main protocol RandomNumberGenerator is described:

public protocol RandomNumberGenerator {
  // This determines the functionality for producing a random number.
  // Required to implement by all rngs.
  func next() -> UInt64
}

// These sets of functions are not required and are provided by the stdlib by default
extension RandomNumberGenerator {
  // This function provides generators a way of generating other unsigned integer types
  public func next<T : FixedWidthInteger & UnsignedInteger>() -> T

  // This function provides generators a mechanism for uniformly generating a number from 0 to upperBound
  // Developers can extend this function themselves and create different behaviors for different distributions
  public func next<T : FixedWidthInteger & UnsignedInteger>(upperBound: T) -> T
}

It is not clear whether conforming types are intended to be able to provide their own implementations for the two next<T>() methods described in the extension. As written, they are *not* able to, but the comments seem to imply that they should be.

• • •

One major decision in the proposal is to make the default random number generator cryptographically secure. I think we should explore the possibility of providing both a secure generator and a fast generator in the standard library.

• • •

It is not immediately clear how non-uniform distributions fit with the proposal. The normal distribution in particular is used quite frequently, and I would hope that a gaussian generator could be a “drop-in replacement”, at least for floating-point value.

In fact, we should consider including in the standard library some way to generate normally-distributed values, with the ability to specify a generator (eg. “fast” or “secure”) as well as a mean and standard deviation (with default values).

• • •

The proposed syntax for generating a random integer or float less than some upper bound is rather verbose:

Int.random(in: 0..<n)
Double.random(in: 0..<x)

I would like to see a free function along the lines of:

func random<T: FixedWidthInteger>(_ upperBound: T) -> T
  where: /*insert constraints here*/
{
  return T.random(in: 0..<upperBound)
}

And the same thing for BinaryFloatingPoint, so that you can write, eg:

random(n)

and have it do the correct thing. Note that I am *not* asking for the zero-argument version which leads people into the modulo-bias morass, nor for a type-converting version. This function takes one argument (and perhaps an optional generator) and returns a value of the same type as its argument.

Similarly, a free function that takes a range would be nice, and might even supplant the random(n) version entirely:

random(0...15)

My main point here is that repeating type information is unnecessary, inelegant, and non-Swifty. Putting the base implementation in static functions is great for encapsulation, and I support that decision. However, the lack of a free function makes use-sites needlessly verbose.

Having a free function with a simple, well-known name makes it easy to reach for the right tool. And if we introduce a protocol (eg. Randomizable) for types with static func random(…), then that free function could be a single simple trampoline.

Letan · March 23, 2018, 9:51pm

I agree mostly with the proposed solution. My only peeve is the inclusion of the static methods.

The only benefit (if you can call it that) is an implicit unwrap.

(0...<100).random()! == Int.random(in: 0..<100)

IMO not having to force unwrap does not carry its weight against polluting the namespaces of quite a few types.

Letan · March 23, 2018, 9:52pm

What's wrong with (0...15).random()?

danielpunkass · March 23, 2018, 9:58pm

I learned about this proposal in a Slack, where before even looking at the proposal, I suggsted I should be able to .random() on whatever numeric type. Looks like this is the proposal for That. I'm all for it!

Jens · March 23, 2018, 10:04pm

What is your evaluation of the proposal?

Overall, I expected (at least the beginnings of) a more full blown generic random number library along the lines of the one in the C++ standard library, which Dave Abrahams suggested should be looked at for inspiration in the original discussion thread. Assuming it's OK to quote that post here:

/.../ I think the discussion seems way too narrow, focusing on spelling rather than on functionality and composability. I consider the “generic random number library” design to be a mostly-solved problem, in the C++ standard library (Pseudo-random number generation - cppreference.com). Whatever goes into the Swift standard library does not need to have all those features right away, but should support being extended into something having the same general shape. IMO the right design strategy is to implement and use a Swift version of C++’s facilities and only then consider proposing [perhaps a subset of] that design for standardization in Swift.

I would like the proposal to show some more of that functionality, composability and extendability.

For example, I didn't see anything in the proposal about how support for distributions other than uniform (normal, gaussian, etc.) would fit into the API.

Also, even though it might be just an implementation detail, I noticed that the implementation uses the following method for converting a random bit pattern into a floating point value in the (half open) unit range [0, 1):

let unitRandom = Self.init(
    sign: .plus,
    exponentBitPattern: (1 as Self).exponentBitPattern,
    significandBitPattern: rand
) - 1

This will produce only half of the numbers that can actually be generated from the random bit pattern, because the lowest bit in the significand will always be zero. The following method (here only for Double) does not have this problem:

init(unitRange bitPattern: UInt64) {
    let shifts = UInt64(11) // Would be eg 7 for Float, obviously it would be calculated from static properties of the type.
    self = Double(bitPattern &>> shifts) * (Double.ulpOfOne / 2)
}

You can read more about these two ways of doing this conversion here (search the page for "Generating uniform doubles in the unit interval")

Note that range conversions like these could be factored out as a set of numeric range conversion methods/initializers that would be useful on their own. In this particular case it's range conversion from the full range of UInt64 to the unit range of a floating point type, but it can also be for converting between the full range of any two fixed width integer types (which can be useful for eg doing bit depth conversion).

Is the problem being addressed significant enough to warrant a change to Swift?

Yes

Does this proposal fit well with the feel and direction of Swift?

See below.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

I'd like Swift's Random API to (at least eventually) be more like a Swifty version of C++'s random number library, and I'm not sure if the current proposal would bring us closer or further away from something like that.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Followed the original thread, quick reading of the proposal and the current implementation.

Nevin · March 23, 2018, 10:23pm

The proposal makes that Optional. Here is a direct comparison:

let x = Int.random(in: 0..<15)      // Static function

let x = (0..<15).random()!          // Collection method

let x = random(0..<15)              // Free function

BigZaphod · March 23, 2018, 10:27pm

Is there no way to seed this without implementing your own generator?

masters3d · March 23, 2018, 11:02pm

+1 for the general case.
+1 for shuffle()

-1 extensions adding .random() to collections, ranges, bool
-1 specially bool. (We had a whole proposal to add a method to bool, this seems out of place)

what does myCollection.random() suppose to do a first glance? Is is randomizing my elements? no.
random sounds mutating to me when used in a ranges like instance.
Overall I feel that it is over reaching.

On number types sounds awesome though!

I think the collection case is intriguing. I'd rather see an overload on myCollection.first(randomGenerator)
Perhaps that should be its own proposal that would include ranges but the mybool.random() needs to go.

Thanks,
Cheyo

Alejandro · March 23, 2018, 11:29pm

I agree there is a lot to cover here!

So yes, it is a little vague in the proposal about having the ability to extend these functions on RandomNumberGenerator, however yes, it is intended to be able to extend these functions, my apologies.
So many people wanted this, however many more agreed that the stdlib is not a statistics library (Brent makes a great comment about this here: [Proposal] Random Unification - #17 by Brent_Royal-Gordon). A big portion of these discussions were about how much of this API belongs in the stdlib, and from a lot of comments in that discussion was that the stdlib should provide a default and non other.
I agree this is functionality that some will look for, but again this goes back to the discussion that the stdlib is not a statistical library. I actually experimented with a distribution design and to me it felt like a reach for the stdlib. I decided against it, but made sure that it was still possible for developers to experiment on their own about how to incorporate such functionality with this API (Extending the next(upperBound:) function on generators is what comes to mind).
Your argument that

doesn't hold up with your solution either. How would this function know you want a value other than Int or Double?

The answer is that you still explicitly have to tell the compiler what type of number you want. There are a couple of ways to represent this:

let x: UInt8 = random(0 ..< 10)
let x = random(0 as UInt8 ..< 10)
let x = random(0 ..< 10) as UInt8

Either way you look at this, you'll still be forced to define the type information (Of course you don't need this for Int or Double).

Alejandro · March 23, 2018, 11:47pm

I think it's important to make the distinction here that the bool random method is a static method. That means you can't do things like myBool.random(). This doesn't make any sense since you already have a bool value! The proposed solution is Bool.random().

So the random method on ranges couldn't have been helped because we added this function to Collection (ranges that conditionally conform to RandomAccessCollection reap the rewards of Collection). Many actually advocated for such function on collections because this functionality is very commonly needed. This function matches other facilities on collections such as .min() and .max().

Andrew · March 23, 2018, 11:54pm

Looks great, pretty minimal, very extensible, but sufficient for the standard library.

One thing it does seem to be missing is support for one-sided ranges SE-0172, were they considered?

I think that may also satisfy people wanting more concise special case methods (Int.random(), Int.random(upTo:5)), but still keep some range-like syntax (Int.random(...), Int.random(...5)) to suggest you don’t need to use modulo.

stephencelis · March 24, 2018, 12:08am

You can at least use dot abbreviation.

intTakingFunction(.random(in: 0..<15))

Nevin · March 24, 2018, 12:23am

Reading over the proposal again, I think that we should not constrain ourselves to any particular sources of randomness in the implementation of the default generator.

The “Proposed Solution” section begins with a lengthy discussion of and decision regarding sources of randomness on various platforms. It is great that the author did so much research, and I am confident that good options were chosen. However, it would be a mistake to declare that we will forever-and-always use these specific sources of randomness.

Instead, the proposal should list qualities (and it does this as well) such as cryptographic security which the default generator will be guaranteed to possess.

It seems that a gaussian distribution could not actually conform to RandomNumberGenerator, but instead would use a conforming type as its underlying source of bits. So the proposal is only for the base layer of generating bits (plus some convenience APIs).

That makes sense, and perhaps it is the right approach for the standard library.

It would infer the type from context, just like any other generic function. For example:

• Perhaps you are assigning to a property of a certain type.
• Perhaps you are adding the result to a variable of a certain type.
• Perhaps you obtained the range (or its upper bound) from a function with a certain return type.

There are many situations where the random(a..<b) syntax can shine. That said, it is easy enough to add on one’s own, so it doesn’t necessarily need to go in the standard library. But I do think it is the optimal spelling for call-sites.

Zhu_Shengqi · March 24, 2018, 12:36am

I don't think we should return an optional in the collection's API. It would be nicer to return a non-optional, and the user should check if the collection is empty before call random(). This scenario is like indexing an array. The user should always call isEmpty first before accessing any element by index.

public func random<T: RandomNumberGenerator>(
+    using generator: T
+  ) -> Element? {
+    guard !isEmpty else { return nil }
+    let random = generator.next(upperBound: UInt(count))
+    let index = self.index(
+      startIndex,
+      offsetBy: numericCast(random)
+    )
+    return self[index]
+  }

masters3d · March 24, 2018, 12:58am

Got it. I think Bool.random() is a slippery slope. Why not have random for closed enums then? (Specially since now most enums would have an .allCases collection). I don't like it. Should we add myBool.shuffle()? now I am just trolling but still.

I am not not saying that it wouldn't be cool to have a way to get a random element from a non empty collection. I just do not think that this should be the proposal for this. Having the non number types gain a random method (static or not) is distracting to this proposal.

.min and .max are intrinsic "properties" of the sequence. How is a random element and intrinsic part of of the collection?

Not to mention that a collection has the word "random" when referring of its access.
If people want something random then I think they should use the subscript.
myCollection[Int.random(0, myCount)]
Anyway, I stated my point. I don't want to distract from the other good parts of the proposal.

Thanks,
Cheyo

Kristian · March 24, 2018, 1:24am

Agreed. I think that if the .random() extension on collection returns an optional, we'll see code like let rand = someNumbers.random() ?? 0 being common, which is the last thing we want people to do.

beccadax · March 24, 2018, 1:42am

I like most of this proposal, but I think we should have a free random(in:using:) function instead of having several static random(in:using:) methods on individual types, because:

The one free function can handle all integer types, all collection types, and random enum elements (through the allCases property). A one-stop shop is a good thing.
The explicit type name is redundant. The in parameter has a type, and that type pins the return type.
@Alejandro argues that this design is bad because you would have to explicitly name the type if you wanted an integer type other than Int, but I don't think that argument holds much water, because we encourage code to only use Int anyway.
The need to use ! in some circumstances is a wart, but I think it's a pretty minor wart. If we really care about it, we could make a NeverEmptyCollection protocol or something, conform ClosedRange to it, and call it a day, but I don't think that's really necessary. (Such a protocol would probably have other applications; for instance, first and last could be non-optional.)

A second overload would be needed for floating-point numbers; this is unfortunate but I don't think it's that big a deal. On the other hand, floats are the main place where we care about distributions—perhaps they should be excluded from the standard library's implementation and left to statistics packages? Such packages can still use the RandomNumberGenerator primitive to extract entropy from the system.

Other issues:

In the implementation, Random tries to override func next<T: FixedWidthInteger & UnsignedInteger>() -> T, but this is not a requirement of the protocol, so this override will not usually be used. Is this intentional?
Should RandomNumberGenerator refine IteratorProtocol? The naming of next() suggests that it should, but the proposal doesn't specify this.