Évaluation différée en C++

Question

C++ n'a pas de support natif pour les paresseux de l'évaluation (comme Haskell n').

Je me demandais si il est possible de mettre en œuvre l'évaluation différée en C++ d'une manière raisonnable. Si oui, comment le feriez-vous?

EDIT: j'aime Konrad Rudolph réponse.

Je me demandais si il est possible de la mettre en œuvre dans un cadre plus générique de la mode, en utilisant par exemple une classe paramétrée paresseux qui travaille essentiellement pour des T le chemin matrix_add travaille pour la matrice.

Toute opération sur des T serait de retour paresseux à la place. Le seul problème est de stocker les arguments et le fonctionnement de code à l'intérieur de paresseux lui-même. Quelqu'un peut-il voir comment améliorer cela?

Answer 1

Je me demandais si il est possible de mettre en œuvre l'évaluation différée en C++ d'une manière raisonnable. Si oui, comment le feriez-vous?

Oui, c'est possible et assez souvent fait, par exemple pour les calculs matriciels. Le principal mécanisme pour faciliter ce est la surcharge d'opérateur. Prenons le cas de la matrice plus. La signature de la fonction généralement de ressembler à quelque chose comme ceci:

matrix operator +(matrix const& a, matrix const& b);

Maintenant, pour faire de cette fonction paresseux, il suffit de retourner un proxy au lieu de le résultat réel:

struct matrix_add;

matrix_add operator +(matrix const& a, matrix const& b) {
    return matrix_add(a, b);
}

Maintenant, tout ce qui doit être fait est d'écrire ce proxy:

struct matrix_add {
    matrix_add(matrix const& a, matrix const& b) : a(a), b(b) { }

    operator matrix() const {
        matrix result;
        // Do the addition.
        return result;
    }
private:
    matrix const& a, b;
};

La magie réside dans la méthode de operator matrix() qui est une conversion implicite de l'opérateur de matrix_add brut matrix. De cette façon, vous pouvez chaîner plusieurs opérations (en fournissant des surcharges de cours). L'évaluation a lieu uniquement lorsque le résultat final est attribué à un matrix de l'instance.

EDIT , j'aurais dû être plus explicite. Comme il est, le code n'a pas de sens, car bien que l'évaluation se passe tranquillement, il se produit toujours dans la même expression. En particulier, un autre ajout permettra d'évaluer le présent code, à moins que l' matrix_add de la structure est modifiée pour permettre enchaîné plus. C++0x facilite grandement cette en permettant variadic templates (c'est à dire le modèle des listes de longueur variable).

Cependant, un cas très simple où ce code aurait effectivement un réel, le bénéfice direct est le suivant:

int value = (A + B)(2, 3);

Ici, il est supposé que l' A et B sont deux dimensions des matrices et que le déréférencement est fait en Fortran notation, c'est à dire la-dessus calcule un élément de la matrice somme. Bien sûr, c'est un gaspillage d'ajouter l'ensemble des matrices. matrix_add à la rescousse:

struct matrix_add {
    // … yadda, yadda, yadda …

    int operator ()(unsigned int x, unsigned int y) {
        // Calculate *just one* element:
        return a(x, y) + b(x, y);
    }
};

D'autres exemples abondent. Je viens de me souvenir que j'ai mis en place quelque chose lié n'y a pas longtemps. En gros, j'ai dû mettre en place une chaîne de classe qui doit adhérer à un fixe, pré-défini de l'interface. Cependant, ma classe string traitées avec d'énormes chaînes de caractères qui n'étaient pas réellement stockées dans la mémoire. Généralement, l'utilisateur, le simple accès des petites chaînes de la chaîne d'origine à l'aide d'une fonction d' infix. J'ai surchargé cette fonction pour mon type de chaîne de retour d'un proxy qui s'est tenue une référence à ma chaîne, avec la désirée de début et de fin de poste. Seulement lorsque cette sous-chaîne a effectivement été utilisé fait la requête d'une API C pour récupérer cette partie de la chaîne.

Answer 2

Coup de pouce.Lambda est très agréable, mais coup de pouce.Proto est exactement ce que vous cherchez. Il a déjà des surcharges de tous C++ opérateurs, qui, par défaut, effectuer leur fonction habituelle lors de l' proto::eval() est appelé, mais peut être changé.

Answer 3

Ce que Konrad déjà expliqué peut être renforcée, afin de soutenir les appels imbriqués des opérateurs, le tout exécuté paresseusement. Dans Konrad exemple, il a une expression de l'objet qui peut stocker exactement deux arguments, pour exactement deux opérandes d'une opération. Le problème est qu'elle ne fait qu'exécuter une sous-expression paresseusement, qui explique bien le concept d'évaluation différée mettre en termes simples, mais n'améliore pas les performances sensiblement. L'autre exemple montre aussi comment on peut appliquer le operator() ajouter quelques éléments à l'aide de l'expression de l'objet. Mais à l'évaluation arbitraire des expressions complexes, nous avons besoin d'un mécanisme qui peut stocker de la structure de ce trop. Nous ne pouvons pas obtenir autour de modèles de le faire. Et le nom de c'est - expression templates. L'idée est que l'un basé sur un modèle objet d'expression peut stocker la structure de certains arbitraire sous-expression de manière récursive, comme un arbre, où les opérations sont les nœuds, et les opérandes sont les enfants des nœuds. Pour une très bonne explication je viens de trouver aujourd'hui (quelques jours après, j'ai é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 va stocker toute opération d'addition, même imbriquées les unes, comme on le voit par la définition suivante d'un opérateur+ pour un simple point de type:

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 surcharge de l'opérateur= et ajouter un constructeur approprié pour le type de Point et accepter AddOp. Changer sa définition:

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 ajouter les get_x et get_y en AddOp que les fonctions de membres:

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

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

Notez comment nous n'avons pas créé de toute temporaires de type Point. Il pourrait avoir été un grand matrice avec de nombreux champs. Mais à l'époque, le résultat est nécessaire, nous le calculons paresseusement.

Answer 4

C++0x, c'est bien joli.... mais pour ceux d'entre nous qui vivent dans le présent, vous avez Boost lambda de la bibliothèque et de Stimuler Phoenix. À la fois avec l'intention de faire de grandes quantités de la fonctionnelle de la programmation C++.