On Mon, Nov 13, 2017 at 7:12 PM, Alejandro Alonso <[email protected]> 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 <[email protected]>, wrote: > > On Sun, Nov 12, 2017 at 19:47 Alejandro Alonso <[email protected]> > 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 <[email protected]>, 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 < >> [email protected]> 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 <[email protected]>, 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 <[email protected]> >> 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 <[email protected]>, 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 < >>> [email protected]> 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 <[email protected]>, 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 < >>>> [email protected]> 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 < >>>> [email protected]>, 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 >>>> [email protected] >>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> >>>> >>>> >>>> _______________________________________________ >>>> swift-evolution mailing list >>>> [email protected] >>>> https://lists.swift.org/mailman/listinfo/swift-evolution >>>> >>>> >>> >> _______________________________________________ >> swift-evolution mailing list >> [email protected] >> https://lists.swift.org/mailman/listinfo/swift-evolution >> >> >>
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
