AUG
29
2014

Lazy declarative programming in C++11

make does it, Haskell does it, spreadsheets do it, QML can do it and below I explain how to do it with C++11: declarative programming. And not just any declarative programming, but my favorite kind: lazy evaluation.

I have written a few C++ classes that wrap imperative C and C++ functions into functional expressions. A simple example illustrates the difference between the common imperative programming and declarative programming.

/**
 * This is our business logic.
 */
int sum(int a, int b) {
   return a + b;
}
/**
 * In the imperative example, c and d are just storage locations for the results.
 */
void imperative() {
    int a = 3;
    int b = 4;
    auto c = sum(a, b);
    auto d = sum(a, c);
    // correct
    std::cout << a << " + " << b << " = " << c << std::endl;
    std::cout << a << " + " << c << " = " << d << std::endl;
    a = 4;
    // error: c and d have not been updated
    std::cout << a << " + " << b << " = " << c << std::endl;
    std::cout << a << " + " << c << " = " << d << std::endl;
}
/**
 * In the lazy example, c and d are defined by the function sum()
 * and the actual values of c and d are determined when these variables
 * are accessed. Any C or C++ function can be used, but the outcome
 * should depend only on the input values.
 */
void lazy() {
    InputValue<int> a = 3;
    InputValue<int> b = 4;
    auto c = makeLazy(sum, a, b);
    auto d = makeLazy(sum, a, c);
    std::cout << a << " + " << b << " = " << c << std::endl;
    std::cout << a << " + " << c << " = " << d << std::endl;
    a = 4;
    std::cout << a << " + " << b << " = " << c << std::endl;
    std::cout << a << " + " << c << " = " << d << std::endl;
}

The function makeLazy() which turns imperative functions to functional use, relies on a new feature in C++: variadic templates. Variadic templates give C++ great flexibility in the use of functions in templates. The example above shows that the functions can be chained.
The biggest advantage of this style of programming is that the programmer does not have to worry about whether the results are up to date. Programming like this feels like writing a spreadsheet: you give the logic and the computer takes care of how and when to get the result. It is nice to see that clean lazy functional programming can be done in C++ too.

Comments

Hello! This is a very cool concept, but I think you are confusing laziness with something like Functional Reactive Programming (FRP).

Laziness means that an expression is not evaluated until the first time it is needed. However it does not mean that the expression will be recalculated when it's arguments change. For example in Haskell the program

import Control.Applicative
import Data.IORef

main = do
    a <- newIORef 3 -- Allocate a new mutable variable with value 3 and bind it to name 'a'.
    b <- newIORef 4
    -- (+) is a pure function, but we need one that can deal with IO, liftA2 (+) gives us that.
    -- After adding the numbers put the result in a new mutable variable.
    c <- (liftA2 (+)) (readIORef a) (readIORef b) >>= newIORef 
    d <- (liftA2 (+)) (readIORef a) (readIORef c) >>= newIORef
    printIt a b c
    printIt a c d
    writeIORef a 4  -- Here we assign a new value to variable a.
    printIt a b c
    printIt a c d

-- Utility function for output printing.
printIt x y s = (liftA3 format) (readIORef x) (readIORef y) (readIORef s) >>= putStrLn
  where
    format x y s = show x ++ " + " ++ show y ++ " = " ++ show s

will output

3 + 4 = 7
3 + 7 = 10
4 + 4 = 7
4 + 7 = 10

just like imperative().
Note the unusual ugliness of this code - this is because it uses actual mutable variables to closely mimic the C++ code. Laziness means just that the actual computation of variables c and d is delayed until we force it (by printing them). After that the result is cached and will not be recomputed.

Now, spreadsheets do it, Haskell can do it (with special libraries), QML does it, React.js does it, your code does it, Elm does it: Reactive programming. You are right that it is a kind of declarative programming. Some RP implementations are very flexible, as they allow values not only to depend on other values, but also to be a function of time or change based on incoming events - and the framework will take care of what to recompute and when to recompute. This paradigm is especially useful for stuff like user interfaces, eg. with React.js you do not have to update the DOM when the state of your application changes, because it will happen automatically.


By PaweĊ‚ Nowak at Sat, 08/30/2014 - 22:45

You are right. Lazyness is not the right word. Functional reactive programming is indeed more accurate.


By Jos van den Oever at Thu, 08/04/2016 - 18:33

Thanks for the post. The link to the 'a few C++ classes' seems to be broken. Can you post the files for makeLazy()?

Thanks again


By Kent at Thu, 08/04/2016 - 16:03

It's just one header file.

#ifndef MAKELAZY_H
#define MAKELAZY_H

#include <memory>
#include <set>

/**
 * @brief The ValueWatcher class.
 * Abstract type for watchers of values.
 * Watchers are called synchroneously when one of the values that they are
 * watching changes.
 */
class ValueWatcher {
public:
    /**
     * @brief Empty implementation of a virtual destructor.
     */
    virtual ~ValueWatcher() {}
    /**
     * @brief Callback for changes in a value.
     * Function that is called synchroneously by the value that is being watched
     * when that value changes.
     */
    virtual void valueChanged() = 0;
};

/**
 * @brief Class that holds the set of ValueWatchers for a value.
 */
class WatcherRegistry {
private:
    /**
     * @brief The registered instances of ValueWatcher.
     */
    std::set<std::shared_ptr<ValueWatcher>> watchers;
public:
    /**
     * @brief Register a watcher.
     * @param watcher Watcher that shall be signalled when the value changes.
     */
    void registerWatcher(std::shared_ptr<ValueWatcher>& watcher) {
        watchers.insert(watcher);
    }
    /**
     * @brief Unregister a watcher.
     * @param watcher Watcher that shall be signalled when the value changes.
     */
    void unregisterWatcher(std::shared_ptr<ValueWatcher>& watcher) {
        auto p = watchers.find(watcher);
        if (p != watchers.end()) {
            watchers.erase(p);
        }
    }
    /**
     * @brief Call valueChanged() on all the registered ValueWatchers.
     */
    void signalWatchers() {
        auto i = watchers.begin();
        while (i != watchers.end()) {
            (*i)->valueChanged();
            ++i;
        }
    }
};

/**
 * @brief Template class for a value that can be watched.
 * @tparam V Type for the value.
 */
template<typename V>
class WatchedValue {
public:
    using value_type = V;
private:
    value_type m_value;
    WatcherRegistry registry;
public:
    WatchedValue() :m_value(value_type()) {}
    WatchedValue(const value_type& v) :m_value(v) {}
    WatchedValue(value_type&& v) :m_value(std::move(v)) {}
    virtual ~WatchedValue() {}
    void set(const value_type& v) {
        if (v != m_value) {
            m_value = v;
            registry.signalWatchers();
        }
    }
    void set(value_type&& v) {
        if (v != m_value) {
            m_value = std::move(v);
            registry.signalWatchers();
        }
    }
    operator const value_type&() const {
        return m_value;
    }
    void registerWatcher(std::shared_ptr<ValueWatcher>& l) {
        registry.registerWatcher(l);
    }
    void unregisterWatcher(std::shared_ptr<ValueWatcher>& l) {
        registry.unregisterWatcher(l);
    }
};
/**
 * @brief Template class for a value that is input to lazy functions.
 * @tparam V Type for the value.
 */
template<typename V>
class InputValue {
public:
    using value_type = V;
private:
    InputValue() = delete;
    std::shared_ptr<WatchedValue<value_type>> m_value;
public:
    InputValue(const value_type& v) :m_value(new WatchedValue<value_type>(v)) {
    }
    void operator=(const value_type& v) {
        m_value->set(v);
    }
    void operator=(value_type&& v) {
        m_value->set(std::move(v));
    }
    operator const value_type& () { return *m_value; }
    void registerWatcher(std::shared_ptr<ValueWatcher>& l) {
        m_value->registerWatcher(l);
    }
    void unregisterWatcher(std::shared_ptr<ValueWatcher>& l) {
        m_value->unregisterWatcher(l);
    }
};

/**
 * Value that is the result of a function.
 * When the inputs to a function change, the OutputValue changes too.
 * An OutputValue instance can be uses as input to another OutputValue.
 */
template<typename F, typename... Args>
class OutputValue {
public:
    using value_type = typename std::result_of<F(Args...)>::type;
private:
    template<int ...>
    struct seq {
    };
    template<int N, int ...S>
    struct gens : gens<N-1, N-1, S...> {
    };
    template<int ...S>
    struct gens<0, S...>{
        using type = seq<S...>;
    };
    template<std::size_t I = 0>
    typename std::enable_if<I == sizeof...(Args), void>::type
    registerAtInputs() {
    }
    template<std::size_t I = 0>
    typename std::enable_if<I < sizeof...(Args), void>::type
    registerAtInputs() {
        std::get<I>(data()->m_args).registerWatcher(m_data);
        registerAtInputs<I + 1>();
    }
    template<std::size_t I = 0>
    typename std::enable_if<I == sizeof...(Args), void>::type
    unregisterAtInputs() {
    }
    template<std::size_t I = 0>
    typename std::enable_if<I < sizeof...(Args), void>::type
    unregisterAtInputs() {
        std::get<I>(data()->m_args).unregisterWatcher(m_data);
        unregisterAtInputs<I + 1>();
    }

    class Data : public ValueWatcher {
    private:
        template<int ...S>
        value_type callFunc(seq<S...>) {
            return m_function(std::get<S>(m_args) ...);
        }
        value_type calcValue() {
            return callFunc(typename gens<sizeof...(Args)>::type());
        }
        const F m_function;
        WatcherRegistry m_registry;
        value_type m_value;
    public:
        std::tuple<Args...> m_args;
        int m_instanceCount;
        bool m_upToDate;
        Data(F f, Args... args...) :m_function(f), m_args(args...),
            m_instanceCount(1), m_upToDate(false) {
        }
        ~Data() {
        }
        virtual void valueChanged() {
            if (m_upToDate) {
                m_upToDate = false;
                m_registry.signalWatchers();
            }
        }
        /**
         * Get the value.
         * If any of the inputs have changed, the value is recalculated.
         */
        const value_type& value() {
            if (!m_upToDate) {
                m_value = calcValue();
                m_upToDate = true;
            }
            return m_value;
        }
        void registerWatcher(std::shared_ptr<ValueWatcher>& l) {
            m_registry.registerWatcher(l);
        }
        void unregisterWatcher(std::shared_ptr<ValueWatcher>& l) {
            m_registry.unregisterWatcher(l);
        }
    };
    Data* data() {
        return static_cast<Data*>(&*m_data);
    }
    std::shared_ptr<ValueWatcher> m_data;
public:
    OutputValue(F f, Args... args...) :m_data(new Data(f, args...)) {
        registerAtInputs();
    }
    OutputValue(const OutputValue& v) :m_data(v.m_data) {
        data()->m_instanceCount += 1;
    }
    ~OutputValue() {
        data()->m_instanceCount -= 1;
        if (data()->m_instanceCount == 0) {
            unregisterAtInputs();
        }
    }
    value_type apply() {
        return data()->value();
    }
    operator value_type() {
        return data()->value();
    }
    const value_type& operator->() {
        return data()->value();
    }
    void registerWatcher(std::shared_ptr<ValueWatcher>& l) {
        data()->registerWatcher(l);
    }
    void unregisterWatcher(std::shared_ptr<ValueWatcher>& l) {
        data()->unregisterWatcher(l);
    }
};

/**
 * @brief Use an imperative function as a functional expression.
 * The result of the function should rely only on the function parameters.
 * Even if InputValues change, the result of the OutputValue returned by
 * makeLazy() is up to date.
 * @tparam F The signature of the function
 * @tparam Args The arguments into F, these may be constants or instances of
 *              InputValue.
 * @param f The function used in the functional expression.
 * @param args The arguments that go into the functional expression.
 */
template<typename F, typename... Args>
OutputValue<F, Args...>
makeLazy(F f, Args... args) {
    return OutputValue<F, Args...>(f, args...);
}

#endif // MAKELAZY_H

By Jos van den Oever at Thu, 08/04/2016 - 18:26