Introduction
Two classes are described in this article. They can wrap any callables (plain functions, functors, static member functions, ordinary member functions, etc.) and invoke them in a lazy way (exactly at the time the result is needed) and also efficiently (with or without memoization). These classes may be useful only when such callables contain very costly or time-consuming operations. Otherwise, its use might add unnecessary overhead.
Background
A function is not a lazy object. It is in fact a very diligent one. You cannot, nude as it comes, transport it (by copying or moving) along the code (do not think about low level function pointers). You usually have to #include it into your scope and just invoke it, assuming (of course) that you already have access to all its arguments in the same scope. That is the general and sound use of functions.
In order to transport a function (or any other callable as lambdas, ordinary and static member functions, etc.) in the aforementioned sense, you can wrap it in a suitable object. std::function is a good option to do this. You can wrap any callable in a std::function object and transport it whenever you want along the code.
So far so good. But we could include some useful functionalities at a low cost. For instance:
- std::function (along with its contained callable) needs access to the arguments at the time it is invoked. Sometimes arguments input and function invocation occur at different code places. It would be interesting to wrap those arguments in the same function wrapper.
- If we need the result of a evaluation twice for the same series of arguments, invoking the std::function object again would be a total waste of time and resources. It would be good if we could store the result (at least) for the last evaluation.
- For very time-consuming callables, with a subset of frequently used arguments, memoization of the results would notably improve the overall efficiency.
The lazy_evaluator<> class, introduced herein, embodies the first two improvements whereas the memoized_lazy_evaluator<> class embodies the improvements 1 and 3.
Using the code
Lazy invocation without memoization
Let's start with a simple code sample. To invoke a plain function lazily we can write:
#include <iostream>
#include "lazy_evaluator.h"
int costly_function(int arg)
{
int result=2*arg;
return result;
}
int main()
{
lazy_evaluator<int(int)> func1(costly_function, 2);
std::cout << "func1(2) = " << func1.value() << std::endl;
std::cout << "func1(2) = " << func1.value() << std::endl;
func1.set_args(3);
std::cout << "func1(3) = " << func1.value() << std::endl;
return 0;
}
Observe that lazy_evaluator<> is instantiated with the callable call signature, (int(int) in the case above).
There are no restrictions neither in the number of arguments nor in their types. In the following example, we are wrapping an ordinary member function (with the help of std::bind):
#include <functional>
#include <iostream>
#include "lazy_evaluator.h"
class costly_function_om
{
double a_;
public:
explicit costly_function_om(double a) :
a_(a)
{}
double func(int arg1, double arg2)
{
double result=2.0*arg1+arg2+a_;
return result;
}
};
int main()
{
costly_function_om instance(1);
lazy_evaluator<double(int, double)> func3(
std::bind(
&costly_function_om::func,
instance,
std::placeholders::_1,
std::placeholders::_2
)
);
func3.set_args(2, 3.0);
std::cout << "func3(2, 3.0) = " << func3.value() << std::endl;
return 0;
}
You can find more usage examples of lazy_evaluator<> in sample_le.cpp, inside the enclosed project. Other than the use of special constructions as std::bind, its use is intuitive and pretty straightforward.
Lazy invocation with memoization
Let's use memoization now. Its point is not re-evaluating twice a very time-consuming callable with the same pack of arguments. For a standalone function again, we have:
#include <iostream>
#include "memoized_lazy_evaluator.h"
int costly_function(int arg)
{
int result=2*arg;
return result;
}
int main()
{
memoized_lazy_evaluator<int(int)> func1("costly_function", costly_function, 2);
std::cout << "costly_function(2) = " << func1.value() << std::endl;
std::cout << "costly_function(2) = " << func1.value() << std::endl;
func1.set_args(3);
std::cout << "costly_function(3) = " << func1.value() << std::endl;
return 0;
}
In the example above, func1 stores every evaluation so that, given the same set of arguments, the result is retrieved from a static repository. Before going deeper in this repository structure, let's show one more example, this time applied to a lambda:
#include <iostream>
#include "memoized_lazy_evaluator.h"
int main()
{
memoized_lazy_evaluator<double(int)> func5(
"costly_lambda",
[](int arg) -> double {return 2.0*arg;} );
func5.set_args(2);
std::cout << "costly_lambda(2) = " << func5.value() << std::endl;
return 0;
}
Observe from the previous two examples that memoized_lazy_evaluator<>'s constructor always demands a string as the first argument. Such string tag is user-arbitrary but it must be biunivocally attached to a same callable. In other words: every memoized_lazy_evaluator<> object attached to (for instance) costly_function must be constructed with the same string tag (no matter what the name of such tag is). Otherwise memoization mechanism will not be efficient.
Memoization repository
In order to understand the prior constraint, it is time to show the static repository structure. This is how it is declared inside the code:
template <typename R, typename... Args>
class memoized_lazy_evaluator<R(Args...)>
{
typedef std::tuple<Args...> args_t;
typedef std::map<args_t, R> table_t;
typedef std::map<std::string, table_t> repository_t;
static repository_t repository;
};
If you prefer to see the above structure graphically:
As you can see, there is a static repository for each R(Args...) call signature so, no matter their real types, all callables accepting the same argument types and returning the same result type are memoized in the same repository. So as to distinguish one callable from any other, tags are required in memoized_lazy_evaluator<>'s constructors. As pointed above, a tag name is user-arbitrary but it would be sensible to name a tag after the associated callable. Special care must be taken with ordinary member functions. Look at this example:
#include <functional>
#include <iostream>
#include "memoized_lazy_evaluator.h"
class costly_function_om
{
double a_;
public:
explicit costly_function_om(double a) :
a_(a)
{}
double func(int arg1, double arg2)
{
double result=2.0*arg1+arg2+a_;
return result;
}
};
int main()
{
costly_function_om instance(1);
memoized_lazy_evaluator<double(int, double)> func3(
"costly_function_om::func",
std::bind(
&costly_function_om::func,
instance,
std::placeholders::_1,
std::placeholders::_2
)
);
return 0;
}
Is "costly_function_om::func" a good tag for our memoization structure? Definitely not because the callable is dependent on a_. A much more sensible choice would have been (for example): "costly_function_om::func;a_=1".
Lazy evaluators as class members
It is possible to use the types described herein as class members. lazy_evaluator<> and memoized_lazy_evaluator<> are both copy and move constructibles and copy and move assignables.
Special care must be taken when they are included as members of default constructible classes. In this case a setter must be provided in order to attach a callable before evaluation. Otherwise a std::runtime_error will be thrown upon value() invocation.
Source code
lazy_evaluator<> and memoized_lazy_evaluator<> implementation codes have been attached, along with their corresponding main sample codes.
The code has been written with Code::Blocks and compiled with MinGw gcc (v.4.8.1-4).
References
From codeproject.com:
- Generic lazy evaluation in C++
- Generic Memoization Infrastructure
From stackoverflow.com:
- How do I expand a tuple into variadic template function's arguments
- Iterate over tuple
