[Proposal] Random Unification

To throw an idea out into the wild: How about a protocol to define the default source fo random on a given platform, with per-platform extensions to provide default implementations?

This would allow any eventual proposal to have default arguments for functions— or to use within `var`s— without implicitly annotating one (CS)PRNG as the de-facto RNG for Swift on all platforms, as well as remove the requirement for providing a `shared` singleton on every (CS)PRNG.

I’m imagining something like this (names taken from, or inspired by, Félix’s design for consistency within this discussion, I’m not strongly attached to any of them):

protocol StandardRandomSource {
	static var generator: RandomSource { get }
}

extension StandardRandomSource {
	static var generator: RandomSource {
#if os(Linux)
		// /dev/random chosen naively
		return DeviceRandom.shared
#elseif os(macOS) || os(iOS) || os(watchOS) || os(tvOS)
		// SecCopyRandomBytes-based, also chosen naively
		return SecRandomSource()
#else
		fatalError("Standard source of randomness not provided on current platform")
#endif
	}
}

and this new protocol could be used like this (largely copied from Félix’s design):

extension Randomizable {
	public static var random: Self {
		return random(using: StandardRandomSource.generator)
	}
}

extension FixedWidthInteger: {
	public static func random(using source: RandomSource = StandardRandomSource.generator) -> Self {
		return (0 ..< Self.max).random(using: source)
	}
}

On a more meta level, introducing this protocol lets us (Swift Evolution) kick the question of “What (CS)PRNG gets implemented for a given OS as the default provider?” further down the road instead of potentially blocking discussion for a long time.

Another possible upside that I can think of is: We could let per-platform implementations of this protocol could happen outside of the Swift Evolution process. Hopefully this means it would be easier to amend or fix in the future, as new platforms are added and new best practices arise.

A downside to this idea is that we’d be adding a protocol to the stdlib that isn’t intended for people to implement, although there’s no possible harm if anyone does so.

One other idea I also explored, but ultimately decided against was having per-platform `typealias`es instead of a protocol with a default implementation. Without a way to get an instance of a random number generator, I fell back to requiring `var shared: Self` to stay in `RandomSource`, which didn’t seem as necessary.

-z

···

On Sep 25, 2017, at 9:57 PM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org> wrote:

Hello evolution,

I am very thankful for all the feedback, and I’ve been working on a design that tries to utilize everybody’s ideas. The link to what I have so far is here: https://gist.github.com/Azoy/15f0518df38df9b722d4cb17bafea4c1\. Please keep in mind this is just a design, no actual implementation as I would most likely need assistance in doing. The default source for randomness will use the OS’s unseeded CSPRNG. This current setup exposes developers to an API that lets them create their own RandomSources on the fly. I want to make the distinction that any existing or new sources of randomness that conform to UnsafeRandomSource are to be considered non cryptographically secure.

I would love to get this discussion flowing again, and I would love input on the design. A few things I came across with this design is that some may want to use ranges as an argument for the numeric types, RandomAccessCollection returning an optional when getting a random, and how to incorporate an API that allows distributions. I wanted to get input on how you feel about each of these topics as I’m indifferent about them all. I’m in no way saying this is the design we should go for, but I’m simply providing something I think we should build on or talk about.

- Alejandro

On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution <swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

First of all, I like this proposal.

For a empty RandomAccessCollection, is it cause a fatal error with calling the random methods?

···

Alejandro Alonso via swift-evolution <swift-evolution@swift.org> 於 2017年9月26日 下午12:57 寫道:

Hello evolution,

I am very thankful for all the feedback, and I’ve been working on a design that tries to utilize everybody’s ideas. The link to what I have so far is here: https://gist.github.com/Azoy/15f0518df38df9b722d4cb17bafea4c1\. Please keep in mind this is just a design, no actual implementation as I would most likely need assistance in doing. The default source for randomness will use the OS’s unseeded CSPRNG. This current setup exposes developers to an API that lets them create their own RandomSources on the fly. I want to make the distinction that any existing or new sources of randomness that conform to UnsafeRandomSource are to be considered non cryptographically secure.

I would love to get this discussion flowing again, and I would love input on the design. A few things I came across with this design is that some may want to use ranges as an argument for the numeric types, RandomAccessCollection returning an optional when getting a random, and how to incorporate an API that allows distributions. I wanted to get input on how you feel about each of these topics as I’m indifferent about them all. I’m in no way saying this is the design we should go for, but I’m simply providing something I think we should build on or talk about.

- Alejandro

On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution <swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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@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@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

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. Swift Random Unification Design · GitHub

- Alejandro

···

On Nov 5, 2017, 4:37 PM -0600, Jonathan Hull <jhull@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@swift.org<mailto:swift-evolution@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@swift.org<mailto:swift-evolution@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@swift.org<mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

Hello swift evolution once again, I’ve been hard at work considering every
email and revising the proposal. I’ve made lots of changes and additions to
the proposal to discuss some problems we’ve had (T.random), and walks
through detailed design. You can see the proposal here:
[Proposal] Random Unification by Azoy · Pull Request #760 · apple/swift-evolution · GitHub .

A big issue that lots of people pointed out was `T.random %` and to remove
it completely from the API. To give a gist of why I continue to support
T.random:

1. Modulo bias misuse is only a problem to types that conform to
`BinaryInteger`. Why remove this functionality if only a portion of the
types have the ability of misuse. `Double.random % 10` is a good example of
where modulo isn’t implemented here as it produces the error, “'%' is
unavailable: Use truncatingRemainder instead”.

2. `Int.random(in: Int.min … Int.max)` doesn’t work. For developers that
actually rely on this functionality, the work around that was discussed
earlier simply doesn’t work. `Int.min … Int.max`’s count property exceeds
that of `Int`’s numerical range. A working work around would be something
along the lines of `Int(truncatingIfNeeded: Random.default.next(UInt.self))`
which creates a pain point for those developers. As the goal of this
proposal to remove pain points regarding random, this change does the
opposite.

I’m interested to hear if anymore discussion around this, or any other
issues come up.

There is no reason why `(Int.min...Int.max).random` (as I believe the
consensus suggestion was) "doesn't work." Certainly, it doesn't work if you
write only a default implementation on Collection. But `Range where Bound :
FixedWidthInteger & SignedInteger` should have its own implementation of
`random` anyway (for performance reasons, if nothing else) and there is no
impediment to a working implementation.

As to your first point: as evidenced by concrete data given by others
above, the overwhelming majority of uses of `random %` appear to be
erroneous, and of course the great majority of uses of `T.random` will be
on types that conform to `BinaryInteger`. Again, I repeat my concern that
you are naming multiple distinct things "random", which is making it
difficult to carry on this discussion. `BinaryInteger.random` is distinct
in its semantics, and this is precisely the method that is often used and
often misused. There is no reason why other things that you name "random"
shouldn't exist just because `BinaryInteger` shouldn't have a method named
`random`, and it's spurious to say "why remove this functionality if only a
portion of the types have the ability of misuse," when this _functionality_
and its misuse are specific to `BinaryInteger`.

···

On Tue, Jan 2, 2018 at 2:35 AM, Alejandro Alonso via swift-evolution < swift-evolution@swift.org> wrote:

On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution < > swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Just skimmed through the updated proposal and am weighing in with my naïve opinions:

I’m still highly skeptical of a static “T.random” API. I’ve yet to see a convincing example where it’d be useful to pick a value from the range of all possible values. The only truly useful one I’ve seen is “pick a random bool”, which could easily be done via “[true, false].random()"

I much prefer the GameplayKit API[0], which breaks the idea of randomness up in to 2 separate concepts:
A “Source” → Where the random numbers come from
A “Distribution” → Initialized with a source, it makes sure the produced numbers exhibit a specific distribution over multiple samplings. Ie, a uniform distribution vs a Gaussian distribution, or something like “I want to pick a card from a deck but bias choices towards Spades or Aces”. I’m also reminded of the anecdote of how iTunes had to modify their “playlist shuffle” algorithm to be less random[1], because the true randomness would do weird things that made it seem not random. Spotify had the same problem and solution[2].
Breaking things up like this would also make it easier to test randomness (by using a replay-able source) but that still follow the parameters of your app (that it has a bell-curve distribution of probabilities, for example)

I’d still really really really like to see how this could be done as two separate things:
A minimal implementation in the Standard Library (like, defining the base Source and Distribution protocols, with a single default implementation of each)
A proposal for a more complete “non-standard library” where the larger array of functionality would be contained. For example, IMO I don’t think the shuffling stuff needs to be in the standard library. This is also where all the cryptographically secure stuff (that your typical app developer does not need) would live.

The “random” element of a collection/range should be “func random() → Element?”, not “var random: Element?”. Property values shouldn't change between accesses. Ditto the static “Randomizable.random” property.

What do you think about actively discouraging people from using the modulo operator to create a range? It could be done by having the RNGs return a “RandomValue<T>” type, then defining a mod operator that takes a RandomValue<T> and a T (?), and then giving it a deprecation warning + fixit. Not sure if that’d be worth the type overhead, but I’m very much in favor of encouraging people towards better practices.

I’m +1 on crashing if we can’t produce a random number.

What do you think about the philosophical difference of Type.random(using:) vs Type.init(randomSource:)?

Dave

[0]: GKRandom | Apple Developer Documentation
[1]: https://www.youtube.com/watch?v=lg188Ebas9E&feature=youtu.be&t=719 <https://www.youtube.com/watch?v=lg188Ebas9E&feature=youtu.be&t=719&gt;
[2]: https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/

···

On Jan 2, 2018, at 1:35 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org> wrote:

Hello swift evolution once again, I’ve been hard at work considering every email and revising the proposal. I’ve made lots of changes and additions to the proposal to discuss some problems we’ve had (T.random), and walks through detailed design. You can see the proposal here: [Proposal] Random Unification by Azoy · Pull Request #760 · apple/swift-evolution · GitHub .

A big issue that lots of people pointed out was `T.random %` and to remove it completely from the API. To give a gist of why I continue to support T.random:

1. Modulo bias misuse is only a problem to types that conform to `BinaryInteger`. Why remove this functionality if only a portion of the types have the ability of misuse. `Double.random % 10` is a good example of where modulo isn’t implemented here as it produces the error, “'%' is unavailable: Use truncatingRemainder instead”.

2. `Int.random(in: Int.min … Int.max)` doesn’t work. For developers that actually rely on this functionality, the work around that was discussed earlier simply doesn’t work. `Int.min … Int.max`’s count property exceeds that of `Int`’s numerical range. A working work around would be something along the lines of `Int(truncatingIfNeeded: Random.default.next(UInt.self))` which creates a pain point for those developers. As the goal of this proposal to remove pain points regarding random, this change does the opposite.

I’m interested to hear if anymore discussion around this, or any other issues come up.

- Alejandro

On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution <swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

Regards,
Ben

···

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I think ClosedRange. Also there should be support for floating types.

···

On Sep 8, 2017, at 12:34 PM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com>, wrote:
It would be nice to leverage range support instead of a start and end value IMHO.

On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Huge +1 to stdlib (or even Foundation) random number generator. I’ve worked with random numbers on both Linux and macOS/iOS and have found myself annoyed with the lack of easy random number generators. It seems that implementing a pure Swift RNG would be an obviously good addition to the stdlib.

I don’t think that it would be possible to make this work for floating point numbers. Although admittedly, I know very little about Floating Point numbers. I think this is still a worthwhile addition to Swift even for just Integers alone.

···

On Sep 8, 2017, at 1:30 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

Regards,
Ben

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com <mailto:shawnce@gmail.com>>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

What if we did it with something like this:

protocol RandomGenerator {
  associated type T: Numeric // Since numeric types are the only kinds where we could get a random number?
  func uniform() -> T
  // Other random type functions...
}

I support a protocol, but not one with an associated type; those are an enormous pain in the rear to work with. They're quite probably my biggest gripe with Swift (and it's not a short list). I shouldn't have to make an entire class generic just so I can have an RNG that I'll probably want to be a private field anyway.

···

On Sep 8, 2017, at 2:46 PM, Jacob Williams via swift-evolution <swift-evolution@swift.org> wrote:

Although if we didn’t constrain T to Numeric then collections could also conform to it, although I’m not sure that collections would want to directly conform to this. There may need to be a separate protocol for types with Numeric indexes?

I’m no pro and really haven’t thought about this too deeply. Mostly just spitballing/brainstorming.

On Sep 8, 2017, at 3:03 PM, Jacob Williams via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Huge +1 to stdlib (or even Foundation) random number generator. I’ve worked with random numbers on both Linux and macOS/iOS and have found myself annoyed with the lack of easy random number generators. It seems that implementing a pure Swift RNG would be an obviously good addition to the stdlib.

I don’t think that it would be possible to make this work for floating point numbers. Although admittedly, I know very little about Floating Point numbers. I think this is still a worthwhile addition to Swift even for just Integers alone.

On Sep 8, 2017, at 1:30 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

Regards,
Ben

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com <mailto:shawnce@gmail.com>>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

What if we did it with something like this:

protocol RandomGenerator {
  associated type T: Numeric // Since numeric types are the only kinds where we could get a random number?
  func uniform() -> T
  // Other random type functions...
}

Although if we didn’t constrain T to Numeric then collections could also conform to it, although I’m not sure that collections would want to directly conform to this. There may need to be a separate protocol for types with Numeric indexes?

I’m no pro and really haven’t thought about this too deeply. Mostly just spitballing/brainstorming.

···

On Sep 8, 2017, at 3:03 PM, Jacob Williams via swift-evolution <swift-evolution@swift.org> wrote:

Huge +1 to stdlib (or even Foundation) random number generator. I’ve worked with random numbers on both Linux and macOS/iOS and have found myself annoyed with the lack of easy random number generators. It seems that implementing a pure Swift RNG would be an obviously good addition to the stdlib.

I don’t think that it would be possible to make this work for floating point numbers. Although admittedly, I know very little about Floating Point numbers. I think this is still a worthwhile addition to Swift even for just Integers alone.

On Sep 8, 2017, at 1:30 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

Regards,
Ben

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com <mailto:shawnce@gmail.com>>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

How would this design address the relatively common use case of wanting a random floating point number in the range `0…1` or `0..<1`? Floating point ranges are not countable.

···

On Sep 8, 2017, at 2:30 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Regards,
Ben

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com <mailto:shawnce@gmail.com>>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Agree on all points. Much like Swift's strings are Unicode-correct instead
of the fastest possible way of slicing and dicing sequences of ASCII
characters, Swift's default PRNG should be cryptographically secure.

···

On Fri, Sep 8, 2017 at 7:50 PM, Stephen Canon <scanon@apple.com> wrote:

On Sep 8, 2017, at 8:09 PM, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

This topic has been broached on Swift Evolution previously. It's
interesting to me that Steve Canon is so certain that CSPRNGs are the way
to go. I wasn't aware that hardware CSPRNGs have come such a long way and
are so ubiquitous as to be feasible as a basis for Swift random numbers. If
so, great.

Otherwise, if there is any way that a software, non-cryptographically
secure PRNG is going to outperform a CSPRNG, then I think it's worthwhile
to have a (carefully documented) choice between the two. I would imagine
that for many uses, such as an animation in which you need a plausible
source of noise to render a flame, whether that is cryptographically secure
or not is absolutely irrelevant but performance may be key.

Let me be precise: it is absolutely possible to outperform CSPRNGs. They
have simply become fast enough that the performance gap doesn’t matter for
most uses (let’s say amortized ten cycles per byte or less—whatever you are
going to do with the random bitstream will be much more expensive than
getting the bits was).

That said, yes, there should definitely be other options. It should be
possible for users to get reproducible results from a stdlib random
interface run-to-run, and also across platforms. That alone requires that
at least one other option for a generator be present. There may also be a
place for a very high-throughput generator like xorshiro128+.

All I’m really saying is that the *default* generator should be an
os-provided unseeded CSPRNG, and we should be very careful about
documenting any generator options.

Hi Alejandro,

I’m really happy to see someone pick this up. We had suggested some kind of random support could be a goal for addition to the standard library in Swift 4 phase 2 but didn’t manage it, so I definitely think a good proposal would be given consideration for Swift 5.

Regarding the implementation – I would suggest exploring something along the lines of an extension on RandomAccessCollection that adds a property for a random element, rather than a pair of free functions. This would have a number of benefits:

- a very common use case is picking a random entry from a collection, which this would do automatically
- it gives you a very natural way of expressing a ranged random number i.e. (0..<10).randomElement (not necessarily recommending that name btw, it’s one of various possibilities)
- since both kinds of countable ranges are collections, it sidesteps that issue :)
- it allows for multiple different integers without the need for casting i.e. in the above, if type context meant the result was a UInt16, that’s what it would be

The one downside is that you’d have to write (0..<Int.max). This might be a justification for a static property on one of the Integer protocols as shorthand for that.

The tricky part (in addition to the cross-platform aspect) is ensuring correct distribution across the possible distances. But since this is something that people might easily get wrong, that reinforces the idea of this being something that’s easy to use correctly in the std lib.

I’d also suggest proposing a shuffle implementation for RandomAccessCollection+MutableCollection at the same time (probably as a separate but linked proposal), since this is also something that is often requested, easy to get wrong, and needs a cross-platform source of random numbers.

How would this design address the relatively common use case of wanting a random floating point number in the range `0…1` or `0..<1`? Floating point ranges are not countable.

Perhaps we should special case floating point ranges. Not sure we can generalise anything in that case.

···

On 8 Sep 2017, at 23:01, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:

On Sep 8, 2017, at 2:30 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Regards,
Ben

On Sep 8, 2017, at 10:34 AM, Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Range support is something that came up, and I think it’s a great idea as well. My question now is do we support both `CountableRange` and `CountableClosedRange`?

On Sep 8, 2017, 12:08 PM -0500, Shawn Erickson <shawnce@gmail.com <mailto:shawnce@gmail.com>>, wrote:

It would be nice to leverage range support instead of a start and end value IMHO.
On Fri, Sep 8, 2017 at 9:52 AM Alejandro Alonso via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@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@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I think I would simply say:

  /// Conforming types generate an infinite sequence of random bits through their `next()` method.
  /// They may be generated from a repeatable seed or from a source of true entropy.
  protocol Randomizer: class, IteratorProtocol, Sequence where Element == UInt, Iterator == Self {
    /// Generates and returns the next `UInt.bitWidth` bits of random data.
    func next() -> UInt
  }

And have this extension on it:

  extension Randomizer {
    /// Permits the use of a Randomizer as a plain old iterator.
    func next() -> UInt? {
      return Optional.some(next())
    }
    
    /// Returns a number in the range 0 ... maximum.
    /// (This is inclusive to allow `maximum` to be `UInt.max`.)
    func next(through maximum: UInt) -> UInt {
      …
    }
  }

We should also provide a singleton `StrongRandomizer`:

  /// A source of cryptographically secure random data.
  ///
  /// `StrongRandomizer` typically uses the strongest random data source provided by
  /// the platform that is suitable for relatively frequent use. It may use a hardware RNG
  /// directly, or it may use a PRNG seeded by a good entropy source.
  ///
  /// `StrongRandomizer` is inherently a singleton.
  /// It can be used on multiple threads, and on some platforms it may block while its
  /// shared state is locked.
  class StrongRandomizer: Randomizer {
    static let shared = StrongRandomizer()
    
    func next() -> UInt {
      …
    }
  }

Finally, we can add extensions to `RandomAccessCollection`:

  extension RandomAccessCollection {
    func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Element? {
      guard !isEmpty else { return nil }
      let offset = IndexDistance(randomizer.next(through: UInt(count) - 1))
      return self[index(startIndex, offsetBy: offset)]
    }
  }

And ranges over `BinaryFloatingPoint`:

  extension Range where Bound: BinaryFloatingPoint {
    func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Bound? {
      …
    }
  }
  extension ClosedRange where Bound: BinaryFloatingPoint {
    func randomElement(with randomizer: Randomizer = StrongRandomizer.shared) -> Bound {
      …
    }
  }

A couple of notes:

• Fundamentally, a randomizer is an infinite sequence of random-ish bits. I say "random-ish" because you may be generating a repeatable pseudo-random sequence from a seed. But in any case, I think it's best to envision this as a special case of an iterator—hence the `IteratorProtocol` conformance.

• Randomizer is class-constrained because we want to encourage providing a defaulted parameter for the randomizer, and `inout` parameters can't be defaulted.

• `UInt` is intentionally inconvenient. You should not usually use a randomizer directly—you should pass it to one of our methods, which know how to handle it correctly. Making it awkward discourages direct use of the randomizer.

• `next(through:)` is provided simply to discourage incorrect modulo-ing.

• `StrongRandomizer` is provided as a slow but safe default. I don't think we should ship any other RNGs; people who want them can import them from modules, which provides at least a bit of evidence that they know what they're doing. (Actually, I could see adding a second RNG that's even stronger, and is specifically intended to be used infrequently to generate seeds or important cryptographic keys.)

···

On Sep 8, 2017, at 2:46 PM, Jacob Williams via swift-evolution <swift-evolution@swift.org> wrote:

What if we did it with something like this:

protocol RandomGenerator {
  associated type T: Numeric // Since numeric types are the only kinds where we could get a random number?
  func uniform() -> T
  // Other random type functions...
}

Although if we didn’t constrain T to Numeric then collections could also conform to it, although I’m not sure that collections would want to directly conform to this. There may need to be a separate protocol for types with Numeric indexes?

I’m no pro and really haven’t thought about this too deeply. Mostly just spitballing/brainstorming.

--
Brent Royal-Gordon
Architechies

I agree too. Anyone that need a random generator but don’t know how it works and what’s a CSPRNG is need a CSPRNG.

For other users, we still need a couple of other implementations.

···

Le 9 sept. 2017 à 03:07, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> a écrit :

On Fri, Sep 8, 2017 at 7:50 PM, Stephen Canon <scanon@apple.com <mailto:scanon@apple.com>> wrote:

On Sep 8, 2017, at 8:09 PM, Xiaodi Wu via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

This topic has been broached on Swift Evolution previously. It's interesting to me that Steve Canon is so certain that CSPRNGs are the way to go. I wasn't aware that hardware CSPRNGs have come such a long way and are so ubiquitous as to be feasible as a basis for Swift random numbers. If so, great.

Otherwise, if there is any way that a software, non-cryptographically secure PRNG is going to outperform a CSPRNG, then I think it's worthwhile to have a (carefully documented) choice between the two. I would imagine that for many uses, such as an animation in which you need a plausible source of noise to render a flame, whether that is cryptographically secure or not is absolutely irrelevant but performance may be key.

Let me be precise: it is absolutely possible to outperform CSPRNGs. They have simply become fast enough that the performance gap doesn’t matter for most uses (let’s say amortized ten cycles per byte or less—whatever you are going to do with the random bitstream will be much more expensive than getting the bits was).

That said, yes, there should definitely be other options. It should be possible for users to get reproducible results from a stdlib random interface run-to-run, and also across platforms. That alone requires that at least one other option for a generator be present. There may also be a place for a very high-throughput generator like xorshiro128+.

All I’m really saying is that the *default* generator should be an os-provided unseeded CSPRNG, and we should be very careful about documenting any generator options.

Agree on all points. Much like Swift's strings are Unicode-correct instead of the fastest possible way of slicing and dicing sequences of ASCII characters, Swift's default PRNG should be cryptographically secure.

important RNG selection is and can be expected to look for a specialized
cryptographically secure RNG. I doubt they would just use the default RNG
without first checking the documentation.

···

On Fri, Sep 8, 2017 at 8:07 PM, Xiaodi Wu via swift-evolution < swift-evolution@swift.org> wrote:

On Fri, Sep 8, 2017 at 7:50 PM, Stephen Canon <scanon@apple.com> wrote:

On Sep 8, 2017, at 8:09 PM, Xiaodi Wu via swift-evolution < >> swift-evolution@swift.org> wrote:

This topic has been broached on Swift Evolution previously. It's
interesting to me that Steve Canon is so certain that CSPRNGs are the way
to go. I wasn't aware that hardware CSPRNGs have come such a long way and
are so ubiquitous as to be feasible as a basis for Swift random numbers. If
so, great.

Otherwise, if there is any way that a software, non-cryptographically
secure PRNG is going to outperform a CSPRNG, then I think it's worthwhile
to have a (carefully documented) choice between the two. I would imagine
that for many uses, such as an animation in which you need a plausible
source of noise to render a flame, whether that is cryptographically secure
or not is absolutely irrelevant but performance may be key.

Let me be precise: it is absolutely possible to outperform CSPRNGs. They
have simply become fast enough that the performance gap doesn’t matter for
most uses (let’s say amortized ten cycles per byte or less—whatever you are
going to do with the random bitstream will be much more expensive than
getting the bits was).

That said, yes, there should definitely be other options. It should be
possible for users to get reproducible results from a stdlib random
interface run-to-run, and also across platforms. That alone requires that
at least one other option for a generator be present. There may also be a
place for a very high-throughput generator like xorshiro128+.

All I’m really saying is that the *default* generator should be an
os-provided unseeded CSPRNG, and we should be very careful about
documenting any generator options.

Agree on all points. Much like Swift's strings are Unicode-correct instead
of the fastest possible way of slicing and dicing sequences of ASCII
characters, Swift's default PRNG should be cryptographically secure.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I would argue that anyone doing cryptography probably already knows how

- I’d love to see several of the most common random kinds supported, and I agree it would be nice (but not required IMO) for the default to be cryptographically secure.

I would be very careful about choosing a "simple" solution. There is a log, sad history of languages trying to provide a "simple" random number generator and accidentally providing a powerful footgun instead. But:

- We should avoid the temptation to nuke this mosquito with a heavy handed solution designed to solve all of the world’s problems: For example, the C++ random number stuff is crazily over-general. The stdlib should aim to solve (e.g.) the top 3 most common cases, and let a more specialized external library solve the fully general problem (e.g. seed management, every distribution imaginable, etc).

That's not to say we need to have seven engines and twenty distributions like C++ does. The standard library is not a statistics package; it exists to provide basic abstractions and fundamental functionality. I don't think it should worry itself with distributions at all. I think it needs to provide:

  1. The abstraction used to plug in different random number generators (i.e. an RNG protocol of some kind).

  2. APIs on existing standard library types which perform basic randomness-related functions correctly—essentially, encapsulating Knuth. (Specifically, I think selecting a random element from a collection (which also covers generating a random integer in a range), shuffling a mutable collection, and generating a random float will do the trick.)

  3. A default RNG with a conservative design that will sometimes be too slow, but will never be insufficiently random.

If you want to pick elements with a Poisson distribution, go get a statistics framework; if you want repeatable random numbers for testing, use a seedable PRNG from XCTest or some other test tools package. These can leverage the standard library's RNG protocol to work with existing random number generators or random number consumers.

I wholeheartedly agree with that plan. The mix of protocol + simple out of the box implementation that is a good default provides both simplicity and flexibility.

PS: still wish it was the same for the Standard Library hashing mechanism.

···

On 12 Sep 2017, at 06:45, Brent Royal-Gordon via swift-evolution <swift-evolution@swift.org> wrote:

On Sep 9, 2017, at 10:31 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

--
Brent Royal-Gordon
Architechies

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

Felix and Jonathan make some good points. Some general comments:

* I think, in general, this area needs a detailed review by those who are
expert in the domain; especially if we are to assert that the design is
cryptographically secure, we need to ensure that it is actually so. In
other words, not just the algorithms that we intend to implement, but the
implementations themselves. This is not at all trivial. We will also need
to specify whether extension methods that generate certain distributions,
etc., are guaranteed secure against side channel attacks where such
implementations are known possible but more expensive.

* Without attempting to bikeshed, the use of the word “Source” is
potentially confusing; it could suggest that the conforming type is a
source of entropy when in fact it consumes entropy. In my proposed design,
the protocol is simply named “PRNG” with an emphasis on the P (i.e.
pseudorandom, not random).

* The distinction to be made here is CSPRNGs versus non-cryptographically
secure PRNGs, where CSPRNG : PRNG. “Reproducible” is not the right word.
Based on my understanding, some CSPRNGs can be “reproducible” if the seed
is known; what makes it cryptographically secure is that observing its
previous *outputs* does not provide information useful to predict future
outputs. Along those lines, it may be important to securely delete the seed
from memory as soon as possible; there is some way of doing so in C (it’s
used in the ChaCha20 reference implementation) but I don’t believe any way
of doing so in Swift.

* On the issue of consuming entropy: a glaring underlying inconvenience in
the API needs to be reckoned with. Sometimes, there simply isn’t enough
entropy to generate another random number. If cryptographic security were
not default, then it might be OK to fall back to some other method that
produces a low-quality result. However, if we are to do the secure thing,
we must decide whether the lack of entropy results in a call to a random
method to (a) return nil; (b) throw; (c) fatalError; or (d) block. There is
no way to paper over this problem; not enough entropy means you can’t get a
random number when you want it. The debate over blocking versus
non-blocking error, for example, held up the addition of getrandom() to
Glibc for some time. In my proposed design, initializing a PRNG from the
system’s secure stream of random bytes is failable; therefore, a user can
choose how to handle the lack of entropy. However, it is desirable to have
a thread-local CSPRNG that is used for calls, say, to Int.random(). It
would be unfortunate if Int.random() itself was failable; however, that
leads to an uncomfortable question: if there is insufficient entropy,
should Int.random() block or fatalError? That seems pretty terrible too.
However, one cannot simply write this off as an edge case: if this is to be
a robust part of the standard library, it must do the “right” thing.
Particularly if Swift is to be a true systems programming language and it
must accommodate the case when a system is first booted and there is very
little entropy.

* What should the default CSPRNG be? There are good arguments for using a
cryptographically secure device random. (In my proposed implementation, for
device random, I use Security.framework on Apple platforms (because
/dev/urandom is not guaranteed to be available due to the sandbox, IIUC).
On Linux platforms, I would prefer to use getrandom() and avoid using file
system APIs, but getrandom() is new and unsupported on some versions of
Ubuntu that Swift supports. This is an issue in and of itself.) Now, a
number of these facilities strictly limit or do not guarantee availability
of more than a small number of random bytes at a time; they are recommended
for seeding other PRNGs but *not* as a routine source of random numbers.
Therefore, although device random should be available to users, it probably
shouldn’t be the default for the Swift standard library as it could have
negative consequences for the system as a whole. There follows the
significant task of implementing a CSPRNG correctly and securely for the
default PRNG.

* It is well settled, based on math and precedent in other languages such
as C++ and Python, that Int.random() should return a number between Int.min
and Int.max, inclusive, and that Float.random() should return a number in
the range 0..<1 (note the exclusive upper bound). There are good
mathematical reasons for this and computational ones, and having these two
primitives as well as raw random bytes allows the implementation of other
distributions. It is, however, not trivial to implement Float.random()
correctly so as never to generate the value 1. Of course, it should be
possible for people to get a random value in a range with a syntax such as
Int.random(in: 0...4), and this is trivial to implement on top of the
primitive standard uniform distribution.

* “Coin flip” is the Bernoulli distribution with p = 0.5 (i.e. a fair coin,
vs. coins biased towards heads or tails), which can be built trivially on
top of Float.random(). (This is one reason why Float.random() returns a
value in 0..<1; otherwise, heads would be slightly more or less likely than
tails if you tried to implement the Bernoulli distribution in this way.)
Similarly, there are good algorithms to implement the normal distribution.
I agree that both are probably common enough to merit inclusion in the
standard library in addition to the uniform distribution and raw random
bytes, but also agree with Chris that probably not much more than that
needs to be standard so long as existing facilities allow people to
implement their own.

I will reply at some later point with a proposed API taking into account
these points and comments above.

···

On Tue, Sep 26, 2017 at 06:59 Jonathan Hull via swift-evolution < swift-evolution@swift.org> wrote:

Instead of “UnsafeRandomSource”, I would call it
“ReproducibleRandomSource”. I have also found that you often need to be
able to “rewind” a reproducible random source for graphics applications:

protocol ReproducibleRandomSource : RandomSource {
init(seed: UInt64)
func mark()->Int
func returnToMark(_ mark:Int) //These could use something like an index
instead of Int. My version just returns 1 the first time you call mark(), 2
the second time, etc...
}

Also, I find that there are just a few primitive types I actually need
from a random source:

• Double (full coverage of possible values)
• Double (in range of 0…1)
• UInt32

The following are also nice to have (built from the above), and commonly
used:

• Bool / CoinFlip
• Int (positive value)
• FixedWidthInteger (of various sizes. Full coverage of possible values)
• Character/String
• CGFloat

Any other type can be built from these building blocks. I have a
RandomSourceCreatable protocol which allows exactly that. Once you have
that, you can put a method on random source which allows you to create any
conforming type:

extension RandomSource {
func next<T:RandomSourceCreatable>(_ type: T.Type)->T
}

This is extremely useful to create colors, offsets, etc…

One thing we need to definitely consider are constraints which people may
want on the random value. For example, should an Int be positive? Should
it be in a certain range? I have a “constraints” parameter on my
RandomSourceCreatable protocol to handle this, and it works well, but I am
not 100% happy with the ergonomics. I also have a variant with an “in
range:” parameter that works for simple linear types like Ints and Floats.
We could do something like:

extension RandomSource {
func next<T:RandomRangeCreatable>(_ type: T.Type, in range:
ClosedRange<T>) -> T
}

Finally, don’t underestimate the usefulness of coinFlip and func oneIn(_
number:UInt)->Bool. They let you quickly branch based on a random value:

if source.oneIn(100) { //This will be true roughly 1 in 100 times
//Do something occasionally
}

Thanks,
Jon

On Sep 25, 2017, at 9:57 PM, Alejandro Alonso via swift-evolution < > swift-evolution@swift.org> wrote:

Hello evolution,

I am very thankful for all the feedback, and I’ve been working on a design
that tries to utilize everybody’s ideas. The link to what I have so far is
here: https://gist.github.com/Azoy/15f0518df38df9b722d4cb17bafea4c1\.
Please keep in mind this is just a design, no actual implementation as I
would most likely need assistance in doing. The default source for
randomness will use the OS’s unseeded CSPRNG. This current setup exposes
developers to an API that lets them create their own RandomSources on the
fly. I want to make the distinction that any existing or new sources of
randomness that conform to UnsafeRandomSource are to be considered non
cryptographically secure.

I would love to get this discussion flowing again, and I would love input
on the design. A few things I came across with this design is that some may
want to use ranges as an argument for the numeric types,
RandomAccessCollection returning an optional when getting a random, and how
to incorporate an API that allows distributions. I wanted to get input on
how you feel about each of these topics as I’m indifferent about them all.
I’m in no way saying this is the design we should go for, but I’m simply
providing something I think we should build on or talk about.

- Alejandro

On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution < > swift-evolution@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@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

+1 to this general plan!

-Chris

···

On Sep 11, 2017, at 9:43 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

On Sep 9, 2017, at 10:31 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

- I’d love to see several of the most common random kinds supported, and I agree it would be nice (but not required IMO) for the default to be cryptographically secure.

I would be very careful about choosing a "simple" solution. There is a log, sad history of languages trying to provide a "simple" random number generator and accidentally providing a powerful footgun instead. But:

- We should avoid the temptation to nuke this mosquito with a heavy handed solution designed to solve all of the world’s problems: For example, the C++ random number stuff is crazily over-general. The stdlib should aim to solve (e.g.) the top 3 most common cases, and let a more specialized external library solve the fully general problem (e.g. seed management, every distribution imaginable, etc).

That's not to say we need to have seven engines and twenty distributions like C++ does. The standard library is not a statistics package; it exists to provide basic abstractions and fundamental functionality. I don't think it should worry itself with distributions at all. I think it needs to provide:

  1. The abstraction used to plug in different random number generators (i.e. an RNG protocol of some kind).

  2. APIs on existing standard library types which perform basic randomness-related functions correctly—essentially, encapsulating Knuth. (Specifically, I think selecting a random element from a collection (which also covers generating a random integer in a range), shuffling a mutable collection, and generating a random float will do the trick.)

  3. A default RNG with a conservative design that will sometimes be too slow, but will never be insufficiently random.

If you want to pick elements with a Poisson distribution, go get a statistics framework; if you want repeatable random numbers for testing, use a seedable PRNG from XCTest or some other test tools package. These can leverage the standard library's RNG protocol to work with existing random number generators or random number consumers.