Lazy and memoized evaluation of callables

• Download lazy_evaluation.zip - 9.4 KB

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:

1. 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. 
2. 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.
3. 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"


// Standalone function
int costly_function(int arg)
{
    // Suppose a very costly function whose final output is "result".
    // After a very complicated computation:

    int result=2*arg;

    return result;
}


int main()
{
    // Lazy evaluator from a standalone function.
    // (In this example, arguments are provided in constructor).
    lazy_evaluator<int(int)> func1(costly_function, 2);

    // We can copy and move the prior object as much
    // as we want all along our code.

    // Eventually, we'll need to evaluate our costly function somewhere:
    std::cout << "func1(2) = " << func1.value() << std::endl;

    // Once evaluated, the result is stored in the very object so
    // further calls to value() have no overhead:
    std::cout << "func1(2) = " << func1.value() << std::endl;

    // We can reset our evaluator simply by providing new arguments:
    func1.set_args(3);

    // As before, no operations are executed until we reclaim the result:
    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"


// Ordinary member function
class costly_function_om
{
    double a_;

public:

    explicit costly_function_om(double a) :
    a_(a)
    {}

    double func(int arg1, double arg2)
    {
        // Suppose a very costly function whose final output is "result".
        // After a very complicated computation:

        double result=2.0*arg1+arg2+a_;

        return result;
    }
};


int main()
{
    // Lazy evaluator from an ordinary member function.
    // (In this example, arguments are not provided in constructor,
    // but you can include them if you will).
    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"


// Standalone function
int costly_function(int arg)
{
    // Suppose a very costly function whose final output is "result".
    // After a very complicated computation:

    int result=2*arg;

    return result;
}


int main()
{
    // Memoized lazy evaluator from a standalone function.
    // (In this example, arguments are provided in constructor).
    memoized_lazy_evaluator<int(int)> func1("costly_function", costly_function, 2);

    // We can copy and move the prior object as much
    // as we want all along our code.

    // Eventually, we'll need to evaluate our costly function somewhere:
    std::cout << "costly_function(2) = " << func1.value() << std::endl;

    // Once evaluated, the result is stored in a static repository so
    // further calls to value() have no overhead:
    std::cout << "costly_function(2) = " << func1.value() << std::endl;

    // We can reset our evaluator simply by providing new arguments:
    func1.set_args(3);

    // As before, no operations are executed until we reclaim the result:
    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 from an anonymous function.
    // (In this example, arguments are not provided in constructor,
    // but you can include them if you will).
    memoized_lazy_evaluator<double(int)> func5(
        "costly_lambda",
        [](int arg) -> double {return 2.0*arg;}    // Very costly lambda function.
        );

    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"


// Ordinary member function
class costly_function_om
{
    double a_;

public:

    explicit costly_function_om(double a) :
    a_(a)
    {}

    double func(int arg1, double arg2)
    {
        // Suppose a very costly function whose final output is "result".
        // After a very complicated computation:

        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:

1. Generic lazy evaluation in C++
2. Generic Memoization Infrastructure

From stackoverflow.com:

1. How do I expand a tuple into variadic template function's arguments
2. Iterate over tuple