[swift-evolution] [Proposal] Random Unification

Mon Nov 13 19:38:44 CST 2017

On Mon, Nov 13, 2017 at 7:12 PM, Alejandro Alonso <aalonso128 at outlook.com>
wrote:

> After thinking about this for a while, I don’t agree with with an
> associated type on RandomNumberGenerator. I think a generic
> FixedWidthInteger & UnsignedInteger should be sufficient. If there were an
> associated type, and the default for Random was UInt32, then there might be
> some arguments about allowing Double to utilize the full 64 bit precision.
> We could make Random32 and Random64, but I think people will ask why there
> isn’t a Random8 or Random16 for those bit widths. The same could also be
> said that any experienced developer would know that his PRNG would be
> switched if he asked for 32 bit or 64 bit.
>

I don't understand. Of course, Double would require 64 bits of randomness.
It would obtain this by calling `next()` as many times as necessary to
obtain the requisite number of bits.

At base, any PRNG algorithm yields some fixed number of bits on each
iteration. You can certainly have a function that returns an arbitrary
number of random bits (in fact, I would recommend that such an algorithm be
a protocol extension method on RandomNumberGenerator), but it must be built
on top of a function that returns a fixed number of bits, where that number
is determined on a per-algorithm basis. Moreover--and this is
important--generating a random unsigned integer of arbitrary bit width in a
sound way is actually subtly _different_ from generating a floating-point
value of a certain bit width, and I'm not sure that one can be built on top
of the other. Compare, for example:

https://github.com/xwu/NumericAnnex/blob/c962760bf974a84ec57d8c5e94c91f06584e2453/Sources/PRNG.swift#L157
https://github.com/xwu/NumericAnnex/blob/c962760bf974a84ec57d8c5e94c91f06584e2453/Sources/PRNG.swift#L316

(These are essentially Swift versions of C++ algorithms.)

Basically, what I'm saying is that RandomNumberGenerator needs a `next()`
method that returns a fixed number of bits, and extension methods that
build on that to return T : FixedWidthInteger & UnsignedInteger of
arbitrary bit width or U : BinaryFloatingPoint of an arbitrary number of
bits of precision. Each individual RNG does not need to reimplement the
latter methods, just a method to return a `next()` value of a fixed number
of bits. You are welcome to use my implementation.

> - Alejandro
>
> On Nov 12, 2017, 9:46 PM -0600, Xiaodi Wu <xiaodi.wu at gmail.com>, wrote:
>
> On Sun, Nov 12, 2017 at 19:47 Alejandro Alonso <aalonso128 at outlook.com>
> wrote:
>
>> Sorry I’ve been gone for a while, I had to do a lot of traveling.
>>
>> 1. Initially I made this thinking that developers had the power to
>> determine their own lower bound. The current implementation uses the
>> integer’s min value as a lower bound. If it makes sense to only allow
>> unsigned integers from an RNG, then I’m perfectly fine with. I do disagree
>> when you say that it should only generate UInt32s. The current approach
>> allows, lets say mt19337 and mt19337-64, to be used within one generator.
>> So if you wanted a UInt32, mt19337 would be used, and if you asked for a
>> UInt64, mt19337-64 would be used.
>>
>
> I agree with Nate that this doesn't need to be--and is better off not
> being--generic. The two different Mersenne Twisters are properly two
> distinct PRNGs. A user sufficiently sophisticated to ask for their own PRNG
> would expect the same algorithm to be used to generate a value of any
> bitwidth, by concatenation of successively generated random bits if
> necessary.
>
> Instead, the return type should be an associated type. 32-bit PRNG
> algorithms would always return values of type UInt32 and 64-bit algorithms
> would always return values of type UInt64.
>
> 2. The Randomizable protocol isn’t always used with integers. Think
>> Date.random or Color.random. These types of values are difficult to express
>> with ranges. Randomizable solves this issue.
>>
>> 3. I’ve made the adjustment necessary for this.
>>
>> 4. So while I can see your point for this, it would break the consistency
>> with Randomizable’s random property. You could argue that we could make
>> this property a function itself, but I think most will agree that
>> Int.random is a cleaner api than Int.random().
>>
>> 5. I’ve made the adjustment necessary for this.
>>
>> 6. I actually forgot to implement the random api for the ranges where
>> Bound: BinaryFloatingPoint. While implementing this, I realized these would
>> never fail and would always return a non-optional.
>>
>
> Sure it can. 0.0..<0.0 is an empty range, just like 0..<0. Any collection
> type really should return an Optional for 'random' because collections can
> be empty.
>
> So, I decided making the other Countable ranges non-optional. (0 ..<
>> 10).random would return a non-optional, (0.0 ..< 10.0).random would return
>> a non-optional, and Array(0 ..< 10).random would return an optional. I can
>> agree that something like (0 ..< 10).random is hard to discover, so I added
>> Int.random(in: 0 ..< 10) (along with BinaryFloatingPoint).
>>
>
> This is unsatisfying (to me, at least). The proposed design should offer
> one very good way to accomplish something, not two spellings for the same
> thing.
>
> However, these are not requirements of Randomizable. I think these methods
>> would benefit more if they were extension methods:
>>
>> extension Randomizable where Self: FixedWidthInteger, Self.Stride:
>> SignedInteger {
>> public static func random(
>> in range: Countable{Closed}Range,
>> using generator: RandomNumberGenerator
>> ) -> Self {
>> return range.random(using: generator)
>> }
>> }
>>
>> extension Randomizable where Self: BinaryFloatingPointer {
>> public static func random(
>> in range: {Closed}Range,
>> using generator: RandomNumberGenerator
>> ) -> Self {
>> return range.random
>> }
>> }
>>
>> I think external types that wish to do something similar, like
>> Data.random(bytes: 128), could extend Randomizable with their own custom
>> needs. The stdlib would at this point provide all the features needed to
>> make this happen very simply for something like Data.random(bytes: 128).
>>
>> - Alejandro
>>
>> On Nov 5, 2017, 10:44 PM -0600, Nate Cook <natecook at apple.com>, wrote:
>>
>> Thanks for continuing to push this forward, Alejandro! I’m excited about
>> the potential of having access to these APIs as part of the standard
>> library. Here are a few comments on some different parts of the proposal:
>>
>> 1) For your RandomGenerator protocol, I’m not totally clear on the
>> semantics of the next(_:) and next(_:upperBound:) methods. Do they both
>> have zero as their lower bound, for example? I’m not sure it makes sense to
>> have signed integers generated directly by an RNG—perhaps T:
>> FixedWidthInteger & UnsignedInteger would be a more useful constraint.
>> (Does it even need to be generic? What if RNGs just generate UInt32s?)
>>
>> 2) Can you say more about the purpose of the Randomizable protocol? How
>> would we use that protocol in useful ways that we wouldn’t get from being
>> able to select random values from ranges (half-open and closed) of
>> FixedWidthInteger / BinaryFloatingPoint? My experience has been that a
>> full-width random value is rarely what a user needs.
>>
>> 3) I agree with Xiaodi that Random should probably be a struct with a
>> single shared instance, but I don’t think it should be internal. Hiding
>> that shared RNG would make it hard for non-stdlib additions to have the
>> same usage, as they would need to have completely separate implementations
>> for the “default” and custom RNG versions.
>>
>> 4) I would also still suggest that the simplest version of random (that
>> you use to get a value from a range or an element from a collection) should
>> be a function, not a property. Collection properties like first, last,
>> and count all represent facts that already exist about a collection, and
>> don’t change unless the collection itself changes. Choosing a random
>> element, on the other hand, is clearly going to be freshly performed on
>> each call. In addition, with the notable exception of count, we try to
>> ensure O(1) performance for properties, while random will be O(n) except
>> in random-access collections. Finally, if it is a method, we can unify the
>> two versions by providing a single method with the shared RNG as the
>> default parameter.
>>
>> 5) To match the sorted() method, shuffled() should be on Sequence
>> instead of Collection. I don’t think either shuffled() or shuffle()
>> needs to be a protocol requirement, since there isn’t really any kind of
>> customization necessary for different kinds of collections. Like the
>> sorting algorithms, both could be regular extension methods.
>>
>> 6) I don’t know whether or not a consensus has formed around the correct
>> spelling of the APIs for generating random values. From the proposal it
>> looks like the preferred ways of getting a random value in a range would be
>> to use the random property (or method) on a range or closed range:
>>
>>     (0..<10).random          // 7
>>     (0.0 ... 5.0).random     // 4.112312
>>
>> If that’s the goal, and we don’t want those values to be optional, we’ll
>> need an implementation of random for floating-point ranges and an overload
>> for fixed-width integer ranges. That said, I don’t think that style is as
>> discoverable as having static methods or initializers available on the
>> different types:
>>
>>     Int.random(in: 0..<10)
>>     Double.random(in: 0.0 ... 5.0)
>>     // or maybe
>>     Int(randomIn: 0..<10)
>>     Double(randomIn: 0.0 ... 5.0)
>>
>> (My only quibble with the initializer approach is that Bool would be
>> awkward.)
>>
>> In addition, this alternative approach could make creating random values
>> more consistent with types that don’t work well in ranges:
>>
>>     Data.random(bytes: 128)
>>     Color.random(r: 0...0, g: 0...1, b: 0...1, a: 1...1)
>>
>> ————
>>
>> Thanks again!
>> Nate
>>
>> On Nov 5, 2017, at 6:33 PM, Alejandro Alonso via swift-evolution <
>> swift-evolution at swift.org> wrote:
>>
>> https://github.com/apple/swift-evolution/pull/760 is the current API and
>> proposed solution.
>>
>> - Alejandro
>>
>> On Nov 5, 2017, 6:18 PM -0600, Xiaodi Wu <xiaodi.wu at gmail.com>, wrote:
>>
>> My comments are directed to the "more up-to-date" document that you just
>> linked to in your reply to Jon. Is that one outdated? If so, can you send a
>> link to the updated proposal and implementation for which you're soliciting
>> feedback?
>>
>>
>> On Sun, Nov 5, 2017 at 6:12 PM, Alejandro Alonso <aalonso128 at outlook.com>
>> wrote:
>>
>>> The proposal and implementation have the current updated API. The link I
>>> sent Jon was the one I brought up a few weeks ago which is outdated now.
>>> The proposal answers all of your questions. As for `.random` being a
>>> function, some would argue that it behaves in the same way as `.first` and
>>> `.last` which are properties.
>>>
>>> - Alejandro
>>>
>>> On Nov 5, 2017, 6:07 PM -0600, Xiaodi Wu <xiaodi.wu at gmail.com>, wrote:
>>>
>>> A few quick thoughts:
>>>
>>> I know that there's been some discussion that `(1...10).random` is the
>>> best spelling, but I'd like to push back on that suggestion. When I want a
>>> random number, I tend to think of the type I want first ("I want a random
>>> integer") and then a range ("I want a random integer between a and b"), not
>>> the other way around. My intuition is that `Int.random(in:)` will be more
>>> discoverable, both on that basis and because it is more similar to other
>>> languages' syntax (`Math.random` in JavaScript and `randint` in NumPy,
>>> for example). It also has the advantage that the type is explicit, which
>>> I think is particularly useful in this case because the value itself is,
>>> well, random.
>>>
>>> I would also argue that, `random` is most appropriately a method and not
>>> a property; there's no hard and fast rule for this, but the fact that the
>>> result is stochastic suggests (to me) that it's not a "property" of the
>>> range (or, for that matter, of the type).
>>>
>>> I would reiterate here my qualms about `Source` being the term used for
>>> a generator. These types are not a _source_ of entropy but rather a
>>> _consumer_ of entropy.
>>>
>>> `UnsafeRandomSource` needs to be renamed; "unsafe" has a specific
>>> meaning in Swift--that is, memory safety, and this is not it. Moreover,
>>> it's questionable whether this protocol is useful in any sense. What useful
>>> generic algorithms can one write with such a protocol?
>>>
>>> `XoroshiroRandom` cannot be seeded by any `Numeric` value; depending on
>>> the specific algorithm it needs a seed of a specific bit width. If you
>>> default the shared instance to being seeded with an `Int` then you will
>>> have to have distinct implementations for 32-bit and 64-bit platforms. This
>>> is unadvisable. On that note, your `UnsafeRandomSource` needs to have an
>>> associated type and not a generic `<T : Numeric>` for the seed.
>>>
>>> The default random number generator should be cryptographically secure;
>>> however, it's not clear to me that it should be device random.
>>>
>>> I agree with others that alternative random number generators other than
>>> the default RNG (and, if not default, possibly also the device RNG) should
>>> be accommodated by the protocol hierarchy but not necessarily supplied in
>>> the stdlib.
>>>
>>> The term `Randomizable` means something specific which is not how it's
>>> used in your proposed protocol.
>>>
>>> There's still the open question, not answered, about how requesting an
>>> instance of the hardware RNG behaves when there's insufficient or no
>>> entropy. Does it return nil, throw, trap, or wait? The proposed API does
>>> not clarify this point, although based on the method signature it cannot
>>> return nil or throw. Trapping might be acceptable but I'd be interested to
>>> hear your take as to why it is preferable.
>>>
>>>
>>> On Sun, Nov 5, 2017 at 4:43 PM, Alejandro Alonso via swift-evolution <
>>> swift-evolution at swift.org> wrote:
>>>
>>>> For the proof of concept, I had accidentally deleted that one. I have a
>>>> more up to date one which was discussed a few weeks later.
>>>> https://gist.github.com/Azoy/15f0518df38df9b722d4cb17bafea4c1
>>>>
>>>> - Alejandro
>>>>
>>>> On Nov 5, 2017, 4:37 PM -0600, Jonathan Hull <jhull at gbis.com>, wrote:
>>>>
>>>> Is there a link to the writeup?  The one in the quote 404s.
>>>>
>>>> Thanks,
>>>> Jon
>>>>
>>>> On Nov 5, 2017, at 2:10 PM, Alejandro Alonso via swift-evolution <
>>>> swift-evolution at swift.org> wrote:
>>>>
>>>> Hello once again Swift evolution community. I have taken the time to
>>>> write up the proposal for this thread, and have provided an implementation
>>>> for it as well. I hope to once again get good feedback on the overall
>>>> proposal.
>>>>
>>>> - Alejandro
>>>>
>>>> On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution <
>>>> swift-evolution at swift.org>, wrote:
>>>>
>>>> Hello swift evolution, I would like to propose a unified approach to
>>>> `random()` in Swift. I have a simple implementation here
>>>> https://gist.github.com/Azoy/5d294148c8b97d20b96ee64f434bb4f5. This
>>>> implementation is a simple wrapper over existing random functions so
>>>> existing code bases will not be affected. Also, this approach introduces a
>>>> new random feature for Linux users that give them access to upper bounds,
>>>> as well as a lower bound for both Glibc and Darwin users. This change would
>>>> be implemented within Foundation.
>>>>
>>>> I believe this simple change could have a very positive impact on new
>>>> developers learning Swift and experienced developers being able to write
>>>> single random declarations.
>>>>
>>>> I’d like to hear about your ideas on this proposal, or any
>>>> implementation changes if need be.
>>>>
>>>> - Alejando
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list
>>>> swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>>
>>>>
>>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20171113/5e97aa87/attachment.html>