Sunday, October 2, 2022

Deferred argument evaluation

Suppose our program deals with heavy entities of some type object which are uniquely identified by an integer ID. The following is a possible implementation of a function that controls ID-constrained creation of such objects:

object* retrieve_or_create(int id)
{
  static std::unordered_map<int, std::unique_ptr<object>> m;

  // see if the object is already in the map
auto [it,b] = m.emplace(id, nullptr);
// create it otherwise if(b) it->second = std::make_unique<object>(id); return it->second.get(); }

Note that the code is careful not to create a spurious object if an equivalent one already exists; but in doing so, we have introduced a potentially inconsistency in the internal map if object creation throws:

// fixed version

object* retrieve_or_create(int id)
{
  static std::unordered_map<int, std::unique_ptr<object>> m;

  // see if the object is already in the map
auto [it,b] = m.emplace(id, nullptr); // create it otherwise
if(b){ try{ it->second = std::make_unique<object>(id); } catch(...){
// we can get here when running out of memory, for instance m.erase(it); throw; } } return it->second.get(); }

This fixed version is a little cumbersome, to say the least. Starting in C++17, we can use try_emplace to rewrite retrieve_or_create as follows:

object* retrieve_or_create(int id)
{
  static std::unordered_map<int, std::unique_ptr<object>> m;

  auto [it,b] = m.try_emplace(id, std::make_unique<object>(id));
  return it->second.get();
}

But then we've introduced the problem of spurious object creation we strived to avoid. Ideally, we'd like for try_emplace to not create the object except when really needed. What we're effectively asking for is some sort of technique for deferred argument evaluation. As it happens, it is very easy to devise our own:

template<typename F>
struct deferred_call
{
  using result_type=decltype(std::declval<const F>()());
  operator result_type() const { return f(); }

  F f;
};

object* retrieve_or_create(int id)
{
  static std::unordered_map<int, std::unique_ptr<object>> m;

  auto [it,b] = m.try_emplace(
    id,
    deferred_call([&]{ return std::make_unique<object>(id); }));
  return it->second.get();
}

deferred_call is a small utlity that computes a value upon request of conversion to deferred_call::result_type. In the example, such conversion will only happen if try_emplace really needs to create a std::pair<const int, std::unique_ptr<object>>, that is, if no equivalent object was already present in the map.

In a general setting, for deferred_call to work as expected, that is, to delay producing the value until the point of actual usage, the following conditions must be met:

  1. The deferred_call object is passed to function/constructor template accepting generic, unconstrained parameters.
  2. All internal intermediate interfaces are also generic.
  3. The final function/constructor where actual usage happens asks exactly for a deferred_call::result_type value or reference.

It is the last condition that can be the most problematic:

void f(std::string);
    
// error: deferred_call not convertible to std::string
f(deferred_call([]{ return "hello"; }));

C++ rules for conversion alows just one user-defined conversion to take place at most, and here we are calling for the sequence deferred_callconst char*std::string. In this case, however, the fix is trivial:

void f(std::string);

f(deferred_call([]{ return std::string("hello"); })); 

Update Oct 4

Jessy De Lannoit proposes a variation on deferred_call that solves the problem of producing a value that is one user-defined conversion away from the target type:

template<typename F>
struct deferred_call
{
using result_type=decltype(std::declval<const F>()());
operator result_type() const { return f(); }

template<typename T>
requires (std::is_constructible_v<T, result_type>)
constexpr operator T() const { return {f()}; }

F f;
};

void f(std::string); // works ok: deferred_call converts to std::string
f(deferred_call([]{ return "hello"; }));

This version of deferred_call has an eager conversion operator producing any requested value as long  as it is constructible from deferred_call::result_type. The solution comes with a different set of problems, though:

void f(std::string);
void f(const char*); // ambiguous call to f
f(deferred_call([]{ return "hello"; }));
There is probably little more we can do without language support. One can imagine some sort of "silent" conversion operator that does not add to the cap on user-defined conversions allowed by the rules of C++:
template<typename F>
struct deferred_call
{
using result_type=decltype(std::declval<const F>()());
operator result_type() const { return f(); }

// "silent" conversion operator marked with ~explicit
// (not actual C++)
template<typename T>
requires (std::is_constructible_v<T, result_type>)
~explicit constexpr operator T() const { return {f()}; }

F f;
};

No comments:

Post a Comment