[swift-evolution] [Proposal] Random Unification

Sun Nov 12 21:46:35 CST 2017

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/143666cd/attachment.html>