15

So I was answering a question about lazy evaluation (here, my answer is overkill for that case but the idea seems interesting) and it made me think about how lazy evaluation might be done in C++. I came up with a way but I wasn't sure of all the pitfalls in this. Are there other ways of achieving lazy evaluation? how might this be done? What are the pitfalls and this and other designs?

Here is my idea:

#include <iostream>
#include <functional>
#include <memory>
#include <string>

#define LAZY(E) lazy<decltype((E))>{[&](){ return E; }}

template<class T>
class lazy {
private:
    typedef std::function<std::shared_ptr<T>()> thunk_type;
    mutable std::shared_ptr<thunk_type> thunk_ptr;
public:
    lazy(const std::function<T()>& x)
        : thunk_ptr(
            std::make_shared<thunk_type>([x](){
                return std::make_shared<T>(x());
            })) {}
    const T& operator()() const {
        std::shared_ptr<T> val = (*thunk_ptr)();
        *thunk_ptr = [val](){ return val; };
        return *val;
    }
    T& operator()() {
        std::shared_ptr<T> val = (*thunk_ptr)();
        *thunk_ptr = [val](){ return val; };
        return *val;
    }
};

void log(const lazy<std::string>& msg) {
    std::cout << msg() << std::endl;
}

int main() {
    std::string hello = "hello";
    std::string world = "world";
    auto x = LAZY((std::cout << "I was evaluated!\n", hello + ", " + world + "!"));
    log(x);
    log(x);
    log(x);
    log(x);
    return 0;
}

Some things I was concerned about in my design.

  • decltype has some strange rules. Does my usage of decltype have any gotchas? I added extra parentheses around the E in the LAZY macro to make sure that single names got treated fairly, as references just like vec[10] would. Are there other things I'm not accounting for?
  • There are lots of layers of indirection in my example. It seems like this might be avoidable.
  • Is this correctly memoizing the result so that no matter what or how many things reference the lazy value, it will only evaluate once(this one I'm pretty confident in but lazy evaluation plus tons of shared pointers might be throwing me a loop)

What are your thoughts?

3
  • Sounds a bit like you're trying to mimic std::future and std::async with std::launch::deferred
    – MFH
    May 23, 2013 at 16:14
  • Except it's not asynchronous. I'm trying to mimic D's 'lazy' keyword and add memoization as in languages like Haskell.
    – Jake
    May 23, 2013 at 17:18
  • std::lauch::deferred actually is lazy evaluated… It gets evaluated on the first thread that tries to access the future.
    – MFH
    May 23, 2013 at 19:31

5 Answers 5

12

Yes, what you have is lazy. Basically, just pass a function which computes the argument instead of the argument. After evaluation, the object is replaced by the computed value. That is basically it, and yes, implemented like that, with reference-counted pointers, it is pretty expensive.

Memoization is an old term, which often means tabling a function's result. No modern language does that (maybe PROLOG), it's extremely expensive. Full-lazyness (never computing one thing twice) is achieved in the process of lambda lifting, which is the elimination of free variables (by putting them as arguments). In fully-lazy lambda lifting, it is the maximal free expressions that are lifted (say x is free, so an ocurrence of sqrt x is replaced by a new argument, sqrtx). There is also the so-called optimal reduction.

I don't think there are other ways of doing it. Why is it a lot faster in a lazy functional language such as Haskell? Well, basically, no reference counted pointers, then there is strictness analysis (strict is the opposite of lazy), which allows the compiler to know beforehand that some things are better evaluated strictly, unboxing values which are evaluated strictly and are of known machine type... not to mention other typical functional programming language optimizations... But in essence, if you look at the implementation of a graph reduction machine, if you look at how the stack evolves, you see that basically you are passing functions on the stack instead of arguments, and that is basically it.

Now, in those machines, the node which computes the argument is overwritten with its value. So you are missing an optimization, maybe, but one which would not possible in a type-safe context.

Suppose all your "nodes" where subclasses of a master superclass, called "node" which had only a virtual function that computed the value... then it could be "overwritten" by another which would return the already computed value. That thing, with function pointers, is why they say the STG machine of Haskell is "Tagless" (the Spineless Tagless G-Machine), because they don't tag the data elements, instead they use a function pointer which either computes or returns the value.

I don't think it can be made not nearly as efficient in C++ as it is in Haskell... unless we start thinking about implementing C++ in a totally different way (could and should be done). We are used to such complex prologs and epilogs and complicated calling convention, etc... Function call is too bureaucratic in C/C++.

Now, the book to read when you feel lazy is definitely "The Implementation of Functional Programming Languages" by Simon Peyton-Jones. However, the modern implementation is described on the freely available article "Implementing functional languages on stock hardware: The Spineless Tagless G-machine" which is very nice to read about the implementation optimizations, but the other one is the one to read to understand the fundamentals.

1
  • 1
    Memoisation usually refers to multiple calls to same function with same arguments. While lazy refers to postponing of value calculation. I feel that this two terms are slighly different in origin while have similar implementations. This lazy might be used for easy implementation of singletons or for building optional functionality which used in a small part of requests etc. While your T is pretty big the overhead should be smaller. That's why C#/.Net also have lazy and I don't think that's because og their GC.
    – ony
    Oct 2, 2013 at 3:58
4
  • You may want to have thunk_type and reference to it as a separate objects. Right now copy of lazy<T> will gain nothing from evaluation of origin. But in that case you'll get additional indirect access.
  • Sometimes you may get rid of wrapping into std::function by simply using templates.
  • I'm not sure that value needs to be shared_ptr. Maybe caller should decide that.
  • You are going to produce new closures on each access.

Consider next modification:

template<typename F>
lazy(const F& x) :
  thunk_ptr([&x,&this](){
    T val = (*x)();
    thunk_ptr = [val]() { return val; };
    return val;
  })
{}

Or alternative implementation might look like:

template<typename F>
auto memo(const F &x) -> std::function<const decltype(x()) &()> {
    typedef decltype(x()) return_type;
    typedef std::function<const return_type &()> thunk_type;
    auto thunk_ptr = std::make_shared<thunk_type>();
    auto *thunk_cptr = thunk_ptr.get();

    // note that this lambda is called only from scope which holds thunk_ptr
    *thunk_ptr = [thunk_cptr, &x]() {
        auto val = std::move(x());
        auto &thunk = *thunk_cptr;
        thunk = [val]() { return val; };
        // at this moment we can't refer to catched vars
        return thunk();
    };

    return [thunk_ptr]() { return (*thunk_ptr)(); };
};
2
  • I've added other question regarding issue with alternative implementation :)
    – ony
    Oct 2, 2013 at 3:50
  • This is kind of old but I wanted to say that after many more years of experience and coming back to this question I should have picked this answer in retrospect. You now have your upvote as deserved.
    – Jake
    Feb 19, 2017 at 0:05
2

Here is another aspect of laziness which was needed for me.

// REMARK: Always use const for lazy objects. Any, even const operation coming from ValueType called over Lazy<ValueType> freezes it.
template < typename ValueType >
struct Lazy
{
    typedef ValueType              Value;
    typedef std::function<Value()> Getter;

    Lazy( const Value& value = Value() )
        : m_value( value )
    { }

    Lazy( Value&& value )
        : m_value( value )
    { }

    Lazy( Lazy& other )
        : Lazy( const_cast<const Lazy&>(other) )
    { }

    Lazy( const Lazy&  other ) = default;
    Lazy(       Lazy&& other ) = default;
    Lazy& operator = ( const Lazy&  other ) = default;
    Lazy& operator = (       Lazy&& other ) = default;


    template < typename GetterType,
               typename = typename std::enable_if<std::is_convertible<GetterType,Getter>::value>::type >
    Lazy( GetterType&& getter )
        : m_pGetter( std::make_shared<Getter>( std::move(getter) ) )
    { }

    void Freeze()
    {
        if ( m_pGetter )
        {
            m_value = (*m_pGetter)();
            m_pGetter.reset();
        }
    }

    operator Value () const
    {
        return m_pGetter ? (*m_pGetter)() : m_value;
    }

    operator Value& ()
    {
        Freeze();
        return m_value;
    }

private:
    Value                   m_value;
    std::shared_ptr<Getter> m_pGetter;
};

With usage like this:

template < typename VectorType,
           typename VectorIthValueGetter = std::function<typename VectorType::const_reference (const size_t)>
         >
static auto MakeLazyConstRange( const VectorType& vector )
    -> decltype( boost::counting_range( Lazy<size_t>(), Lazy<size_t>() ) | boost::adaptors::transformed( VectorIthValueGetter() ) )
{
    const Lazy<size_t> bb( 0 ) ;
    const Lazy<size_t> ee( [&] () -> size_t { return vector.size(); } );
    const VectorIthValueGetter tt( [&] (const size_t i) -> typename VectorType::const_reference { return vector[i]; } );
    return boost::counting_range( bb, ee ) | boost::adaptors::transformed( tt );
}

and later:

std::vector<std::string> vv;
boost::any_range<const std::string&, boost::forward_traversal_tag, const std::string&, int>
    rr = MakeLazyConstRange( vv );

vv.push_back( "AA" );
vv.push_back( "BB" ); 
vv.push_back( "CC" ); 
vv.push_back( "DD" ); 

for ( const auto& next : rr )
    std::cerr << "---- " << next << std::endl;
4
  • when this is copied no link is maintained hence the function can be called more than once which we don't want. More over what if Value isn't a default construable type? More more over we don't want a lazy value to need to call the copy constructor of the underlying value on copy; at least I find that undesirable except for trivial types like int, double, etc... An interesting idea might be to use type_traits to optimize this even more.
    – Jake
    Oct 8, 2013 at 19:45
  • 1. // the function can be called more than once which we don't want // -- If you mean the *m_pGetter function, then in my context it is intended to be called as many times as the unfrozen lazy value is accessed. 2. // we don't want a lazy value to need to call the copy constructor of the underlying value on copy // -- This wrapper is intended just to provide laziness for the given ValueType and nothing more. On copy it copies the underlying value just it would be with ValueType. This wrapper has no burden to optimize copy for heavy ValueTypes.
    – Vahagn
    Oct 9, 2013 at 6:53
  • 3. // what if Value isn't a default construable type? // -- True, this wrapper has room to be enhanced in order to handle this situation, though it can be done in an uncomplicated way.
    – Vahagn
    Oct 9, 2013 at 6:54
  • On point 1 I mean the you could have two lazy values that have not been evaluated yet and when the first
    – Jake
    Oct 10, 2013 at 0:25
0

The Boost Phoenix library implements Lazyness, among other FP's niceties but I haven't not used myself I am not sure how good it plays with C++ 11, or perhaps it made it at least partially to the 2011 standard.

http://www.boost.org/doc/libs/1_43_0/libs/spirit/phoenix/doc/html/index.html

0

In my implementation of class Lazy, I have went by a little bit other way - lambda function does not return value, it takes it as parameter. It helps to achieve some benefits:

  1. Saved time on invoking move constructor for encapsulated type (when initialize function returns result).
  2. Copy constructor and assignment operator for encapsulated type are not required (only if you want do it for Lazy type).

Also, this version should be thread safe (please correct me if I did something wrong). One requirement which is still left - default constructor.

#pragma once
#include <mutex>
#include <atomic>
#include <functional>

template <typename T>
struct Lazy
{
    using value_type = T;

    Lazy() : mInitializer(nullptr) {}

    Lazy(const std::function<void(T&)>& initializer)
        : mInitializer(std::move(initializer))
        , mInitFlag(false)
    { }

    Lazy(const Lazy& other)
        : mInitializer(other.mInitializer)
        , mInitFlag(other.mInitFlag.load())
        , mValue(other.mValue)
    { }

    Lazy(Lazy&& other)
        : mInitializer(std::move(other.mInitializer))
        , mInitFlag(other.mInitFlag.load())
        , mValue(std::move(other.mValue))
    { }

    Lazy& operator=(const std::function<void(T&)>& initializer)
    {
        mInitFlag.store(false);
        mInitializer = initializer;
        return *this;
    };

    Lazy& operator=(const Lazy& rhs)
    {
        if (this != &rhs)
        {
            std::lock_guard<std::mutex> lock(mMutex);

            mInitializer = rhs.mInitializer;
            mInitFlag = rhs.mInitFlag.load();
            if (mInitFlag) {
                mValue = rhs.mValue;
            }
        }
        return *this;
    };

    Lazy& operator=(Lazy&& rhs)
    {
        if (this != &rhs)
        {
            std::lock_guard<std::mutex> lock(mMutex);

            mInitializer = std::move(rhs.mInitializer);
            mInitFlag = rhs.mInitFlag.load();
            if (mInitFlag) {
                mValue = std::move(rhs.mValue);
            }
        }
        return *this;
    };

    inline operator T&()                { return get(); }
    inline operator const T&() const    { return get(); }

    inline T& get()             { return const_cast<T&>(_getImpl()); }
    inline const T& get() const { return _getImpl(); }

private:
    const T& _getImpl() const
    {
        if (mInitializer != nullptr && mInitFlag.load() == false)
        {
            std::lock_guard<std::mutex> lock(mMutex);
            if (mInitFlag.load() == false)
            {
                mInitializer(mValue);
                mInitFlag.store(true);
            }
        }
        return mValue;
    }

    mutable std::mutex mMutex;
    std::function<void(T&)> mInitializer;
    mutable std::atomic_bool mInitFlag;
    mutable T mValue;   // Value should be after mInitFlag due initialization order
};

Usage sample:

using ValuesList = std::vector<int>;
Lazy<ValuesList> lazyTest = [](ValuesList& val) { val.assign({1, 2, 3, 4, 5}); };
const Lazy<ValuesList> lazyTestConst = lazyTest;

ValuesList& value = lazyTest;
const ValuesList& cvalue = lazyTestConst;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.