John Fremlin's blog: Lazy operators in C++ for fun and data fetch batching

Lazy evaluation is a key feature of the Haskell language where it enables a declarative style of programming that (for better or worse) abstracts away from the details of the order of evaluation. There are some practical reasons why this is useful and it's possible to implement a subset relatively transparently in C++ too. Here, I explore the idea of using it to semi-transparently implement futures.

Nowadays with parallelism forced on programmers, we have to deal with fetching data across machine or process boundaries. These communications are expensive and ideally in one transaction as many requests and responses are batched together as possible. Suppose one is performing a computation (e.g. for a concrete example, calculating the theoretical value of a financial derivative in a particular market scenario) then depending on the type of the derivative we need to fetch various pieces of information (always we will need to fetch the currency yield curve and then whatever specific aspect the trade depends on). To handle this simple case, we need to inspect the trade to figure out which currency and payment dates it depends on, fetch the relevant rates, and then calculate its expected value.

This would naturally imply two trade dependent functions: first a scanning function for going over the trade to find what it might depend on, and a second pricing to use these data to perform the calculation. Obviously both of these functions are very similar one to another and any change to one probably has to be reflected in the other.

Enter lazy evaluation: the pricing returns, instead of a price, a calculation tree. Then a generic walker goes over the calculation tree and figures out which data are required. When they are available the calculation tree is evaluated with them and the price is obtained.

Provided we do not have a dependency of one piece of data on another (e.g. an imaginary exotic trade that pays off in the second best performing stock), then this can be implemented in natural C++ with normal operators.

Here's an example of such a simple system I cobbled together for fun, on github and locally. The lazy evaluation and tree walking is implemented.

First we create an expression depending on us providing the values of x and y:

  auto x = H(map, "x");
  auto y = H(map, "y");
  auto expr = (x + y)/2.;

Then we easily walk the expression to discover the values that need to be obtained (all this does is print them out)

 
  expr->Walk(hash_walker);

And now we provide the values,

  (*map)["x"] = 400;
  (*map)["y"] = -200;

And finally correctly print the result: 100

  std::cout << expr->Eval() << std::endl;

There are many obvious improvements in terms of optimizations of the calculation tree and its memory layout (it should calculate as much as possible with the know values and use a more complex representation to avoid so much memory traffic), and obviously many, many functions like max, min, exp and so on that need to be implemented for these types. But it's a sketch of what's possible and an example of how much you can hack into the C++ type system!