Évaluation paresseuse en C++

Coup de pouce.Lambda est très agréable, mais Boost.Proto est exactement ce que vous cherchez. Il a déjà des surcharges detous les opérateurs C++, qui par défaut remplissent leur fonction habituelle lorsque proto::eval() est appelé, mais peuvent être modifiés.

Ce que Konrad a déjà expliqué peut être mis plus loin pour supporter les invocations imbriquées des opérateurs, tous exécutés paresseusement. Dans L'exemple de Konrad, il a un objet expression qui peut stocker exactement deux arguments, pour exactement deux opérandes d'une opération. Le problème est qu'il n'exécutera que une sous-expression paresseusement, ce qui explique bien le concept dans l'évaluation paresseuse en termes simples, mais n'améliore pas considérablement les performances. L'autre exemple montre aussi comment on peut appliquez operator() pour ajouter uniquement certains éléments à l'aide de cet objet expression. Mais pour évaluer des expressions complexes arbitraires, nous avons besoin d'un mécanisme qui peut stocker la structure de cela aussi. Nous ne pouvons pas contourner les modèles pour le faire. Et le nom pour cela est expression templates. L'idée est qu'un objet d'expression modélisé peut stocker la structure d'une sous-expression arbitraire de manière récursive, comme un arbre, où les opérations sont les nœuds, et les opérandes sont les nœuds enfants. Pour un très bon explication que je viens de trouver aujourd'hui (quelques jours après avoir écrit le code ci-dessous) Voir ici.

template<typename Lhs, typename Rhs>
struct AddOp {
    Lhs const& lhs;
    Rhs const& rhs;

    AddOp(Lhs const& lhs, Rhs const& rhs):lhs(lhs), rhs(rhs) {
        // empty body
    }

    Lhs const& get_lhs() const { return lhs; }
    Rhs const& get_rhs() const { return rhs; }
};

Qui stockera toute opération d'addition, même imbriquée, comme on peut le voir par la définition suivante d'un opérateur+ pour un type de point simple:

struct Point { int x, y; };

// add expression template with point at the right
template<typename Lhs, typename Rhs> AddOp<AddOp<Lhs, Rhs>, Point> 
operator+(AddOp<Lhs, Rhs> const& lhs, Point const& p) {
    return AddOp<AddOp<Lhs, Rhs>, Point>(lhs, p);
} 

// add expression template with point at the left
template<typename Lhs, typename Rhs> AddOp< Point, AddOp<Lhs, Rhs> > 
operator+(Point const& p, AddOp<Lhs, Rhs> const& rhs) {
    return AddOp< Point, AddOp<Lhs, Rhs> >(p, rhs);
}

// add two points, yield a expression template    
AddOp< Point, Point > 
operator+(Point const& lhs, Point const& rhs) {
    return AddOp<Point, Point>(lhs, rhs);
}

Maintenant, si vous avez

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 };
p1 + (p2 + p3); // returns AddOp< Point, AddOp<Point, Point> >

Il vous suffit maintenant de surcharger operator = et d'ajouter un constructeur approprié pour le type de Point et d'accepter AddOp. Changer sa définition en:

struct Point { 
    int x, y; 

    Point(int x = 0, int y = 0):x(x), y(y) { }

    template<typename Lhs, typename Rhs>
    Point(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
    }

    template<typename Lhs, typename Rhs>
    Point& operator=(AddOp<Lhs, Rhs> const& op) {
        x = op.get_x();
        y = op.get_y();
        return *this;
    }

    int get_x() const { return x; }
    int get_y() const { return y; }
};

Et ajoutez le get_x approprié et get_y dans AddOp en tant que fonctions membres:

int get_x() const {
    return lhs.get_x() + rhs.get_x();
}

int get_y() const {
    return lhs.get_y() + rhs.get_y();
}

Notez que nous n'avons pas créé De temporaires de type Point. Il aurait pu être une grande matrice avec de nombreux champs. Mais à l'époque, le résultat est nécessaire, nous le calculons paresseusement.

Je n'ai rien à ajouter au post de Konrad, mais vous pouvez regarder Eigen pour un exemple d'évaluation paresseuse bien faite, dans une application du monde réel. C'est assez impressionnant.

Je pense à implémenter une classe de modèle, qui utilise std::function. La classe devrait plus ou moins ressembler à ceci:

template <typename Value>
class Lazy
{
public:
    Lazy(std::function<Value()> function) : _function(function), _evaluated(false) {}

    Value &operator*()  { Evaluate(); return  _value; }
    Value *operator->() { Evaluate(); return &_value; }

private:
    void Evaluate()
    {
        if (!_evaluated)
        {
            _value = _function();
            _evaluated = true;
        }
    }

    std::function<Value()> _function;
    Value _value;
    bool _evaluated;
};

Par exemple Utilisation:

class Noisy
{
public:
    Noisy(int i = 0) : _i(i)
    {
        std::cout << "Noisy(" << _i << ")"  << std::endl;
    }
    Noisy(const Noisy &that) : _i(that._i)
    {
        std::cout << "Noisy(const Noisy &)" << std::endl;
    }
    ~Noisy()
    {
        std::cout << "~Noisy(" << _i << ")" << std::endl;
    }

    void MakeNoise()
    {
        std::cout << "MakeNoise(" << _i << ")" << std::endl;
    }
private:
    int _i;
};  

int main()
{
    Lazy<Noisy> n = [] () { return Noisy(10); };

    std::cout << "about to make noise" << std::endl;

    n->MakeNoise();
    (*n).MakeNoise();
    auto &nn = *n;
    nn.MakeNoise();
}

Le code ci-Dessus devrait produire le message suivant sur la console:

Noisy(0)
about to make noise
Noisy(10)
~Noisy(10)
MakeNoise(10)
MakeNoise(10)
MakeNoise(10)
~Noisy(10)

Notez que l'impression du constructeur Noisy(10) ne sera pas appelée tant que la variable n'aura pas été accédée.

Cette classe est loin d'être parfaite, cependant. La première chose serait le constructeur par défaut de Value devra être appelée sur le membre initialisation (impression Noisy(0) dans ce cas). Nous pouvons utiliser le pointeur pour _value à la place, mais je ne suis pas sûr que cela affecterait les performances.

La réponse de Johannes fonctionne.Mais quand il s'agit de plus de parenthèses, cela ne fonctionne pas comme souhait. Ici est un exemple.

Point p1 = { 1, 2 }, p2 = { 3, 4 }, p3 = { 5, 6 }, p4 = { 7, 8 };
(p1 + p2) + (p3+p4)// it works ,but not lazy enough

Parce que les trois opérateurs surchargés + ne couvraient pas le cas

AddOp<Llhs,Lrhs>+AddOp<Rlhs,Rrhs>

Donc, le compilateur doit convertir (p1 + p2) ou(p3+p4) en Point ,ce n'est pas assez paresseux.Et quand le compilateur décide lequel convertir, il se plaint. Car aucun n'est meilleur que l'autre . Voici mon extension: ajouter encore un autre opérateur surchargé +

    template <typename LLhs, typename LRhs, typename RLhs, typename RRhs>
AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>> operator+(const AddOp<LLhs, LRhs> & leftOperandconst, const AddOp<RLhs, RRhs> & rightOperand)
{
    return  AddOp<AddOp<LLhs, LRhs>, AddOp<RLhs, RRhs>>(leftOperandconst, rightOperand);

}

Maintenant, le compilateur peut gérer le cas ci-dessus correctement, et aucune conversion implicite, volia!

C++0x est agréable et tout.... mais pour ceux d'entre nous vivant dans le présent, vous avez Boost lambda library et Boost Phoenix. Les deux avec l'intention d'apporter de grandes quantités de programmation fonctionnelle en C++.

Tout est possible.

Cela dépend exactement de ce que vous voulez dire:

class X
{
     public: static X& getObjectA()
     {
          static X instanceA;

          return instanceA;
     }
};

Nous avons ici l'effet d'une variable globale qui est paresseusement évaluée au point de première utilisation.

Comme nouvellement demandé dans la question.
Et voler Konrad Rudolph design et l'étendre.

L'objet paresseux:

template<typename O,typename T1,typename T2>
struct Lazy
{
    Lazy(T1 const& l,T2 const& r)
        :lhs(l),rhs(r) {}

    typedef typename O::Result  Result;
    operator Result() const
    {
        O   op;
        return op(lhs,rhs);
    }
    private:
        T1 const&   lhs;
        T2 const&   rhs;
};

Comment l'utiliser:

namespace M
{
    class Matrix
    {
    };
    struct MatrixAdd
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    struct MatrixSub
    {
        typedef Matrix  Result;
        Result operator()(Matrix const& lhs,Matrix const& rhs) const
        {
            Result  r;
            return r;
        }
    };
    template<typename T1,typename T2>
    Lazy<MatrixAdd,T1,T2> operator+(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixAdd,T1,T2>(lhs,rhs);
    }
    template<typename T1,typename T2>
    Lazy<MatrixSub,T1,T2> operator-(T1 const& lhs,T2 const& rhs)
    {
        return Lazy<MatrixSub,T1,T2>(lhs,rhs);
    }
}

, Comme il va être fait dans C++0x, par des expressions lambda.

En C++11 une évaluation paresseuse similaire à la réponse de hiapay peut être réalisée en utilisant std:: shared_future. Vous devez toujours encapsuler les calculs dans lambdas mais la mémorisation est prise en charge:

std::shared_future<int> a = std::async(std::launch::deferred, [](){ return 1+1; });

Voici un exemple complet:

#include <iostream>
#include <future>

#define LAZY(EXPR, ...) std::async(std::launch::deferred, [__VA_ARGS__](){ std::cout << "evaluating "#EXPR << std::endl; return EXPR; })

int main() {
    std::shared_future<int> f1 = LAZY(8);
    std::shared_future<int> f2 = LAZY(2);
    std::shared_future<int> f3 = LAZY(f1.get() * f2.get(), f1, f2);

    std::cout << "f3 = " << f3.get() << std::endl;
    std::cout << "f2 = " << f2.get() << std::endl;
    std::cout << "f1 = " << f1.get() << std::endl;
    return 0;
}

Prenons Haskell comme notre inspiration-il est paresseux au cœur. Aussi, gardons à l'esprit comment Linq en C# utilise des énumérateurs de manière monadique (urgh - voici le mot - désolé). Last not least, gardons à l'esprit, ce que les coroutines sont censées fournir aux programmeurs. À savoir le découplage des étapes de calcul (par exemple producteur consommateur) les unes des autres. Et essayons de réfléchir à la façon dont les coroutines se rapportent à l'évaluation paresseuse.

Tout ce qui précède semble être en quelque sorte concerner.

Ensuite, essayons d'extraire notre définition personnelle de ce que "paresseux" revient à.

Une interprétation est: nous voulons énoncer notre calcul de manière composable, avant de l'exécuter. Certaines de ces parties que nous utilisons pour composer notre solution complète pourraient très bien s'appuyer sur d'énormes sources de données (parfois infinies), notre calcul complet produisant également un résultat fini ou infini.

Permet d'obtenir du béton et dans du code. Nous avons besoin d'un exemple pour que! Ici, je choisis le "problème" fizzbuzz comme exemple, juste pour la raison qu'il y a une solution agréable et paresseuse.

Dans Haskell, ça ressemble à ceci:

module FizzBuzz
( fb
)
where
fb n =
    fmap merge fizzBuzzAndNumbers
    where
        fizz = cycle ["","","fizz"]
        buzz = cycle ["","","","","buzz"]
        fizzBuzz = zipWith (++) fizz buzz
        fizzBuzzAndNumbers = zip [1..n] fizzBuzz
        merge (x,s) = if length s == 0 then show x else s

La fonction Haskell cycle crée une liste infinie (paresseuse, bien sûr!) à partir d'une liste finie en répétant simplement les valeurs de la liste finie pour toujours. Dans un style de programmation avide, écrire quelque chose comme ça sonnerait la sonnette d'alarme (débordement de mémoire, boucles sans fin!). Mais ce n'est pas un paresseux de la langue. L'astuce est que les listes paresseuses ne sont pas calculées tout de suite. Peut-être jamais. Normalement seulement autant que le code suivant l'exige.

La troisième ligne du bloc where ci-dessus crée un autre paresseux!! liste, au moyen de combiner les listes infinies fizz et buzz au moyen de la recette de deux éléments simples "concaténer un élément de chaîne de l'une ou l'autre liste d'entrée en une seule chaîne". Encore une fois, si cela devait être immédiatement évalué, nous devrions attendre que notre ordinateur soit à court de ressources.

Dans la 4ème ligne, nous créons des tuples des membres d'une liste paresseuse finie [1..n] avec notre liste paresseuse infinie fizzbuzz. Le résultat est toujours paresseux.

Même dans le corps principal de notre fonction fb, Il n'y a pas besoin d'être impatient. La fonction entière renvoie une liste avec la solution, qui est elle-même-encore une fois-paresseuse. Vous pourriez aussi bien penser au résultat de fb 50 comme un calcul que vous pouvez (partiellement) évaluer plus tard. Ou combiner avec d'autres choses, conduisant à un encore plus grand (paresseux) évaluation.

Donc, pour commencer avec notre version C++ de "fizzbuzz", nous devons réfléchir à la façon de combiner des étapes partielles de notre calcul en plus gros bits de calculs, chaque dessin des données des étapes précédentes selon les besoins.

, Vous pouvez voir l'article complet dans un résumé de la mine.

Voici les idées de base derrière le code:

Empruntant à C # et Linq, nous "inventons" un type générique avec État Enumerator, qui contient
- Actuel valeur du calcul partiel
- L'état d'un calcul partiel (afin que nous puissions produire des valeurs ultérieures)
- La fonction worker, qui produit l'état suivant, la valeur suivante et un bool qui indique s'il y a plus de données ou si l'énumération est terminée.

Afin de pouvoir composer l'instance Enumerator<T,S> au moyen de la puissance du . (point) , cette classe contient également des fonctions, empruntées aux classes de type Haskell telles que Functor et Applicative.

La fonction de travail pour l'énumérateur est toujours de la forme: S -> std::tuple<bool,S,T où S est la variable de type générique représentant l'état et T est la variable de type générique représentant une valeur-le résultat d'une étape de calcul.

Tout cela est déjà visible dans les premières lignes de la définition de classe Enumerator.

template <class T, class S>
class Enumerator
{
public:
    typedef typename S State_t;
    typedef typename T Value_t;
    typedef std::function<
        std::tuple<bool, State_t, Value_t>
        (const State_t&
            )
    > Worker_t;

    Enumerator(Worker_t worker, State_t s0)
        : m_worker(worker)
        , m_state(s0)
        , m_value{}
    {
    }
    // ...
};

Donc, tout ce dont nous avons besoin pour créer une instance d'énumérateur spécifique, nous devons créer une fonction de travail, avoir l'état initial et créer un instance de Enumerator, avec ces deux arguments.

Ici, un exemple - Fonction range(first,last) crée une plage finie de valeurs. Cela correspond à une liste paresseuse dans le monde Haskell.

template <class T>
Enumerator<T, T> range(const T& first, const T& last)
{
    auto finiteRange =
        [first, last](const T& state)
    {
        T v = state;
        T s1 = (state < last) ? (state + 1) : state;
        bool active = state != s1;
        return std::make_tuple(active, s1, v);
    };
    return Enumerator<T,T>(finiteRange, first);
}

Et nous pouvons utiliser cette fonction, par exemple comme ceci: auto r1 = range(size_t{1},10); - nous nous sommes créés une liste paresseuse avec 10 éléments!

Maintenant, tout ce qui manque pour notre expérience "wow", c'est de voir comment nous pouvons composer des recenseurs. En revenant à la fonction Haskells cycle, ce qui est plutôt cool. Comment serait-il regarder dans notre monde c++? Ici, il est:

template <class T, class S>
auto
cycle
( Enumerator<T, S> values
) -> Enumerator<T, S>
{
    auto eternally =
        [values](const S& state) -> std::tuple<bool, S, T>
    {
        auto[active, s1, v] = values.step(state);
        if (active)
        {
            return std::make_tuple(active, s1, v);
        }
        else
        {
            return std::make_tuple(true, values.state(), v);
        }
    };
    return Enumerator<T, S>(eternally, values.state());
}

Il prend un énumérateur en entrée et renvoie un énumérateur. La fonction locale (lambda) eternally réinitialise simplement l'énumération d'entrée à sa valeur de départ chaque fois qu'elle est à court de valeurs et voilà-nous avons une version infinie et répétée de la liste que nous avons donnée en argument:: auto foo = cycle(range(size_t{1},3)); et nous pouvons déjà composer sans vergogne nos "calculs" paresseux.

zip est un bon exemple, montrant que nous pouvons également créer un nouvel énumérateur à partir de deux énumérateurs d'entrée. L'énumérateur résultant donne autant de valeurs que la plus petite des énumérateurs d'entrée (tuples avec 2 éléments, un pour chaque énumérateur d'entrée). J'ai implémenté zip à l'intérieur de class Enumerator lui-même. Voici à quoi cela ressemble:

// member function of class Enumerator<S,T> 
template <class T1, class S1>
auto
zip
( Enumerator<T1, S1> other
) -> Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
{
    auto worker0 = this->m_worker;
    auto worker1 = other.worker();
    auto combine =
        [worker0,worker1](std::tuple<S, S1> state) ->
        std::tuple<bool, std::tuple<S, S1>, std::tuple<T, T1> >
    {
        auto[s0, s1] = state;
        auto[active0, newS0, v0] = worker0(s0);
        auto[active1, newS1, v1] = worker1(s1);
        return std::make_tuple
            ( active0 && active1
            , std::make_tuple(newS0, newS1)
            , std::make_tuple(v0, v1)
            );
    };
    return Enumerator<std::tuple<T, T1>, std::tuple<S, S1> >
        ( combine
        , std::make_tuple(m_state, other.state())
        );
}

Veuillez noter que la "combinaison" finit également par combiner l'état des deux sources et les valeurs des deux sources.

Comme ce post est déjà TL; DR; pour beaucoup, ici le...

Résumé

Oui, l'évaluation paresseuse peut être implémentée en C++. Ici, je l'ai fait en empruntant les noms de fonctions de haskell et le paradigme des énumérateurs C# et Linq. Il pourrait y avoir des similitudes avec pythons itertools, btw. Je pense qu'ils ont suivi une approche similaire.

Mon implémentation (voir le lien gist ci - dessus) n'est qu'un prototype-pas un code de production, btw. Donc aucune garantie que ce soit de mon côté. Il sert bien comme code de démonstration pour obtenir le général idée à travers, cependant.

Et quelle serait cette réponse sans la version finale C++ de fizzbuz, hein? Ici, il est:

std::string fizzbuzz(size_t n)
{
    typedef std::vector<std::string> SVec;
    // merge (x,s) = if length s == 0 then show x else s
    auto merge =
        [](const std::tuple<size_t, std::string> & value)
        -> std::string
    {
        auto[x, s] = value;
        if (s.length() > 0) return s; 
        else return std::to_string(x);
    };

    SVec fizzes{ "","","fizz" };
    SVec buzzes{ "","","","","buzz" };

    return
    range(size_t{ 1 }, n)
    .zip
        ( cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
          .zipWith
            ( std::function(concatStrings)
            , cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
            )
        )
    .map<std::string>(merge)
    .statefulFold<std::ostringstream&>
    (
        [](std::ostringstream& oss, const std::string& s) 
        {
            if (0 == oss.tellp())
            {
                oss << s;
            }
            else
            {
                oss << "," << s;
            }
        }
        , std::ostringstream()
    )
    .str();
}

Et... pour pousser le point encore plus loin - ici une variante de fizzbuzz qui renvoie une" liste infinie " à l'appelant:

typedef std::vector<std::string> SVec;
static const SVec fizzes{ "","","fizz" };
static const SVec buzzes{ "","","","","buzz" };

auto fizzbuzzInfinite() -> decltype(auto)
{
    // merge (x,s) = if length s == 0 then show x else s
    auto merge =
        [](const std::tuple<size_t, std::string> & value)
        -> std::string
    {
        auto[x, s] = value;
        if (s.length() > 0) return s;
        else return std::to_string(x);
    };

    auto result =
        range(size_t{ 1 })
        .zip
        (cycle(iterRange(fizzes.cbegin(), fizzes.cend()))
            .zipWith
            (std::function(concatStrings)
                , cycle(iterRange(buzzes.cbegin(), buzzes.cend()))
            )
        )
        .map<std::string>(merge)
        ;
    return result;
}

Cela vaut la peine de montrer, puisque vous pouvez en apprendre comment esquiver la question de savoir quel est le type de retour exact de cette fonction (car cela dépend de l'implémentation de la fonction seule, à savoir comment le code combine énumérateur).

En outre, il démontre que nous avons dû déplacer les vecteurs fizzes et buzzes en dehors de la portée de la fonction afin qu'ils soient toujours là quand finalement à l'extérieur, le mécanisme paresseux produit des valeurs. Si nous ne l'avions pas fait, le code iterRange(..) aurait stocké des itérateurs dans les vecteurs qui ont disparu depuis longtemps.

Il est assez facile de créer votre propre classe "container" qui prend un objet de fonction de génération et expose les itérateurs.