Why are c++11 random distributions mutable?

Question

I thought that the value generated by the c++11 random distribution (uniform_int_distribution, for instance), depends only on the state of the generator which is passed to the operator(). However, for some reason there is no const specifier in the signature of operator(). What does that mean, and how should I pass the distribution as a function parameter? I thought I had to pass it as any non-mutable parameter: by const reference, but now I'm not sure.

Answer 1

I misunderstood the question at first, however, now that I understand, it's a good question. Some digging into the source of the implementation of <random> for g++ gives the following (with a few bits left out for clarity):

template<typename _IntType = int>
  class uniform_int_distribution
  {

  struct param_type
  {
    typedef uniform_int_distribution<_IntType> distribution_type;

    explicit
    param_type(_IntType __a = 0,
       _IntType __b = std::numeric_limits<_IntType>::max())
    : _M_a(__a), _M_b(__b)
    {
      _GLIBCXX_DEBUG_ASSERT(_M_a <= _M_b);
    }

     private:
    _IntType _M_a;
    _IntType _M_b;
};

public:
  /**
   * @brief Constructs a uniform distribution object.
   */
  explicit
  uniform_int_distribution(_IntType __a = 0,
           _IntType __b = std::numeric_limits<_IntType>::max())
  : _M_param(__a, __b)
  { }

  explicit
  uniform_int_distribution(const param_type& __p)
  : _M_param(__p)
  { }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)
    { return this->operator()(__urng, this->param()); }

  template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng,
       const param_type& __p);

  param_type _M_param;
};

If we squint past all the _, we can see that it has only a single member parameter, param_type _M_param, which itself is simply a nested struct holding 2 integral values - in effect, a range. operator() is only declared here, not defined. Some more digging brings us to the definition. In lieu of posting all the code here, which is pretty ugly (and rather long), it suffices to say that nothing is mutated inside this function. In fact, adding const to definition and declaration will happily compile.

The question then becomes, is this true for every other distribution? The answer is no. If we look to the implementation for std::normal_distribution, we find:

template<typename _RealType>
template<typename _UniformRandomNumberGenerator>
  typename normal_distribution<_RealType>::result_type
  normal_distribution<_RealType>::
  operator()(_UniformRandomNumberGenerator& __urng,
     const param_type& __param)
  {
result_type __ret;
__detail::_Adaptor<_UniformRandomNumberGenerator, result_type>
  __aurng(__urng);

    //Mutation!
if (_M_saved_available)
  {
    _M_saved_available = false;
    __ret = _M_saved;
  }
    //Mutation!

This is all just theorizing, but I imagine the reason it is not restricted to const is to allow implementers to mutate their implementation if required. Further, it keeps a more uniform interface - if some operator() are const and some are non-const, it all becomes a bit messy.

However, why they didn't simply make them const and let the implementers utilize mutable I'm not sure. Likely, unless someone around here was involved with this part of the standardization effort, you may not get a good answer to this.

Edit: As MattieuM pointed out, mutable and multiple threads do not play nicely together.

Just as a minorly interesting aside, std::normal_distribution generates two values at once, caching one (hence the _M_saved). The operator<< that it defines actually lets you see this value before the next call to operator():

#include <random>
#include <iostream>
#include <chrono>

std::default_random_engine eng(std::chrono::system_clock::now().time_since_epoch().count());
std::normal_distribution<> d(0, 1);

int main()
{
   auto k = d(eng);
   std::cout << k << "\n";
   std::cout << d << "\n";
   std::cout << d(eng) << "\n";
}

Here, the output format is mu sigma nextval.

Answer 2

The other answer says:

This is all just theorizing, but I imagine the reason it is not restricted to const is to allow implementers to mutate their implementation if required. Further, it keeps a more uniform interface - if some operator() are const and some are non-const, it all becomes a bit messy.

This is mostly correct, but it is even deeper than that in the context of generic programming. (As @Calimo said, this leaves the idea that const was omitted just "in case").

After thinking about this, I reached the conclusion that the problem translates on whether the following member function can be in principle const or not really depends on the actual type of _UniformRandomNumberGenerator.

template<typename _UniformRandomNumberGenerator>
result_type
operator()(_UniformRandomNumberGenerator& __urng)

At this level of (generic) specification this is not know, so it is only then that "[the specification] allows implementers to mutate [internal state] " and it does it for the sake of genericity.

So, the problem of constness is that at compile-time one should know whether _UniformRandomNumberGenerator is able to generate enough randomness (bits) for the distribution to produce a sample draw.

In the current specification that possibility is left out but it can in principle be implemented (or specified) by having two exclusive versions of the member function:

template<typename _URG, typename = std::enable_if<not has_enough_randomness_for<_URG, result_type>::value > >
result_type
operator()(_UniformRandomNumberGenerator& __urng){..statefull impl..}

template<typename _URG, typename = std::enable_if<has_enough_randomness_for<_URG, result_type>::value > >
result_type
operator()(_UniformRandomNumberGenerator& __urng) const{..stateless impl...}

Where has_enough_randomness_for is an imagined boolean metafunction that can tell if the particular implementation can be stateless.

However, there is still another obstacle, in general, whether the implementation is stateless or not depends on the runtime parameters of the distribution. But since this is runtime information then it cannot be passed as part of the type system!

As you see this opens another can of worms. constexpr parameters of the distributions could in principle detect this but I would totally understand the committee stopping here.

If you need an immutable distribution (e.g. to be "conceptually" correct) you could achieve this easily by paying a price:

1. Copying a pristine distribution each time before using it.
2. Implementing the distribution logic yourself in a stateless manner.

(1) can be very inefficient and (2) it is likely to be somewhat inefficient and extremely tricky to implement correctly.

Since (2) is almost impossible to get right in general and even if one gets it right, it will be somewhat inefficient, I am only going to show how to implement a stateless distribution that just works:

template<class Distribution>
struct immutable : Distribution{
   using Distribution::Distribution;
   using Distribution::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      auto dist_copy = static_cast<Distribution>(*this);
      return dist_copy(__urng);
   }
// template<typename _URG> result_type operator()(_URG& __urng) = delete;
};

In such a way that immutable<D> is a replacement for D. (Another name for immutable<D> could be conceptual<D>.)

I have tested this with uniform_real_distribution for example and the immutable replacement is almost twice as slow (because it copies/modifies/discards a nominal state), but as you point out it can be used in a more "conceptual" context if that is important to your design (which I can understand).

(There is another minor unrelated advantage that is that you can use a shared immutable distribution across threads)

---

INCORRECT BUT ILLUSTRATIVE CODE FOLLOWS:

To illustrate how difficult is to do (2), I am going to make a naive specialization of immutable<std::uniform_int_distribution> that is almost correct for some uses (or very incorrect depending on who you ask.)

template<class Int>
struct immutable<std::uniform_int_distribution<Int>> : std::uniform_int_distribution<Int>{
   using std::uniform_int_distribution<Int>::uniform_int_distribution;
   using std::uniform_int_distribution<Int>::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      return __urng()%(this->b() - this->a()) + this->a(); // never do this ;) for serious stuff, it is wrong in general for very subtle reasons
   }
// template<typename _URG> result_type operator()(_URG& __urng) = delete;
};

This stateless implementation is very "efficient" but not 100% correct for arbitrary values of a and b (limits of the distribution). As you might see, for other distributions (including continuous distributions) this path is very difficult, tricky and error prone, so I don't recommend it.

---

This is mostly personal opinion: Can the situations be improved?

Yes, but only slightly.

The distributions could have two versions of operator(), one no-const (i.e. &), which is optimal (current one) and one that is const that what it can to not modify the state. However it is not clear whether they will be have to deterministically consistent (i.e. give same answers). (Even fallback to copy will not give the same results as a full fledged mutable distribution.). However, I don't think this is a viable path (agreeing with the other answer); either you use an immutable version or an immutable version but not both at the same time.

What I think can be done is to have a mutable version but a specific overload for r-value references (operator() &&). This way the mechanism of the mutable version can be used but the now "useless" step of updating (e.g. resetting) the state can be omitted because the particular instance will not be used ever again. This way one can save some operations in some cases.

This way the immutable adaptor described above can be written in this way and exploit the semantics:

template<class Distribution>
struct immutable : Distribution{
   using Distribution::Distribution;
   using Distribution::result_type;
   template<typename _URG> result_type operator()(_URG& __urng) const{
      auto dist_copy = static_cast<Distribution>(*this);
      return std::move(dist_copy)(__urng);
// or return (Distribution(*this))(__urng);
   }
};