Discussion :

[jportemer]

Bonjour à tous !

Je m'excuse par avance de ce post qui risque d'être long, et plutôt technique... Elle s'adresse plutôt aux fans de la programmation fonctionnelle .

J'essaie de reproduire un simulacre de Blitz++, permettant d'effectuer des calculs vectoriels à la sauce Matlab / J.
Je pense avoir bien compris l'intérêt des template expressions permettant de regrouper les boucles for et ainsi éviter les allocations de données superflus qui plombent la RAM.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
template<typename Left, typename Op, typename Right>
struct X {
   Left leftNode_;
   Right rightNode_;
 
   X(Left t1, Right t2)
   : leftNode_(t1), rightNode_(t2)
   { }
 
   // The trick: delegate the [] operator to subexpressions, recursively
   double operator[](int i)
   {
      return Op::apply(leftNode_[i],rightNode_[i]);
   }
};
 
// Simple array class (fixed size)
struct Array {
   Array(double* data, int N)
   : data_(data), N_(N)
   { }
 
   // Assign an expression to the array
   // It is only at that time than evaluation occurs
   template<typename Left, typename Op, typename Right>
   void operator=(X<Left,Op,Right> expression)
   {
   for (int i=0; i < N_; ++i)
      data_[i] = expression[i];
   }
 
   // Access element
   double operator[](int i)
   {
      return data_[i];
   }
   double* data_;
   int N_;
};
 
// Operator +
template<typename Left>
X<Left, plus, Array> operator+(Left a, Array b)
{
return X<Left, plus, Array>(a,b);
}
 
// Tests
int main()
{
double a_data[] = { 2, 3, 5, 9 },
b_data[] = { 1, 0, 0, 1 },
c_data[] = { 3, 0, 2, 5 },
d_data[4];
Array A(a_data,4), B(b_data,4), C(c_data,4), D(d_data,4);
D = A + B + C;
for (int i=0; i < 4; ++i)
cout << D[i] << " "; // Output --> 6 3 7 15 
cout << endl;
return 0;
}

(exemple extrait du livre Techniques for Scientific C++, Todd Veldhuizen)

Je me pose maintenant la question de savoir comment introduire dans ce schéma les fonctions du second ordre, comme la réduction, qui prend une fonction et renvoie une fonction dérivée. J'ai déjà réalisé un modèle qui permettait de le faire :
Une fonction du premier ordre prend un vector (ou array) ou deux vectors et retourne un vector.
Si elle prend un vector alors elle est monadique, si elle en prend deux elle est dyadique.

Une fonction du second ordre prend une fonction du premier ordre et en renvoie une fonction du premier ordre dérivée. Cette fonction dérivée peut potentiellement prendre un argument (monadique), ou bien deux (dyadique).

"plus" est une fonction du premier ordre, la réduction une fonction du second ordre.

En C++14 (merci à jo_link_noir pour ton aide !)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
#include <array>
 
 
using namespace std;
 
 
struct Function {
    constexpr Function() noexcept {}
};
 
 
struct Function_1st_Order : Function {
    const bool neutral;
    constexpr Function_1st_Order(bool neutral) noexcept :  Function(), neutral(neutral) {}
};
 
struct Add : Function_1st_Order {
 
  constexpr Add() noexcept : Function_1st_Order(0) {};
 
  /* Monad : add(a) = a*/
  template<class T>
  auto operator()(const vector<T> & right) const {
    return right;
  }
 
  /* Dyad : add(a, b) = a + b */
  template<class T, class U>
  auto operator()(const vector<T> & right, const vector<U> & left) const {
    size_t n = right.size();
    typedef typename common_type<T, U>::type C;
    vector<C> res(n);
    for(unsigned int i=0; i<n; i++) {
       res[i] = left[i] + right[i];
    }
    return res;
  }
 
};
 
template<typename M, typename D>
struct Derived_Function_1st_Order : Function_1st_Order {
    const M m; /* Monadic use */
    const D d; /* Dyadic use */
 
    Derived_Function_1st_Order(bool neutral, M m, D d) noexcept :  Function_1st_Order(neutral), m(m), d(d) {}
    template<class T>
    auto operator()(const vector<T> & right) const {return m(right);};
 
    template<class T, class U>
    auto operator()(const vector<T> & right, const vector<U> & left) const {return d(right, left);};
};
 
 
struct Function_2nd_Order : Function {
  constexpr Function_2nd_Order() noexcept : Function() {};
};
 
struct Reduce : Function_2nd_Order {
  constexpr Reduce() noexcept : Function_2nd_Order() {}
  template<class F> // Replace function. Mandatory to avoid virtual template fonction declaration in class function, which is impossible
  constexpr auto operator()(const F & f) const {
 
    auto monad = [f](const auto & cont) {
      auto res = decltype(cont){f.neutral}; // Copy type of cont, without the flags
      size_t n = cont.size();
      for(int i=n-1; i>=0; i--) {
           auto cur = decltype(cont){cont[i]}; // Copy type of cont, without the flags
           res = f(res, cur);
      }
      return res[0];
    };
 
    auto dyad = [f]() {
        // Undefined for the moment
    };
 
    return Derived_Function_1st_Order<decltype(monad), decltype(dyad)>(0, monad, dyad);
  }
 
 
};
 
namespace {
    constexpr auto const & reduce = Reduce();
    constexpr auto const & add = Add();
}
 
int main()
{
    auto cumulate = reduce(add);
    vector<int> l = {1,2,3};
    cout << cumulate(l);
    return 0;
}

Comment traduire ça en template expression ?
Je prends le symbole / pour la réduction, qui prend son argument-fonction à gauche (syntaxe J).
Pour les classes template, j'appelle :
X un nœud d'application d'une fonction du 1^er ordre, en mode dyadique : X<Left, Function, Right>
Y un nœud d'application d'une fonction du 1^er ordre, en mode monadique : Y<Function, Right>
Z un nœud d'application d'une fonction du 2^ème ordre, en mode monadique : Z<Left, Function>
Je sais qu'un expression du type C=A+(+/)B, avec A, B et C des tableaux, pourrait être parsée ainsi :

• C= A + Z<plus, reduce>() B
• C= A + Y<Z<plus, reduce>, array>()
• C= Z<array, Y<Z<plus, reduce>, array>()

Comment effectuer l'évaluation paresseuse pour pouvoir affecter C à la dernière ligne ? Que mettre dans la classe Z ?

Auriez-vous des idées, ne serait-ce qu'un début de piste que je pourrais creuser ? Je sais que ce que je demande est plutôt compliqué, mais je n'ai trouvé aucune référence en la matière, et pour le moment je sèche lamentablement...

Merci beaucoup !

Jean

PS : En effet, en me relisant, c'est long et technique ...

[jo_link_noir]

Pour avoir du lazy, il faudrait que cumulate(l) retourne une expression lazy<M, std::vector<int>&> et faire un operateur+(T, lazy<M,V>) en conséquence.

Ce qui sera compliqué avec le DSL est la partie optimisation des calculs (réordonner, pré-calculer les sorties de reduce puis évaluer les containers).