Ensemble de paramètre template "désactivables" et métaprogrammation.

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonsoir

J'ai une fonction qui prend pas mal de paramètres template qui sont en fait des types de foncteur. Par exemple,
Code:

1 2 3 4 5 6 template <typename skipping_condition, typename required_condition, typename seq_iterator> std::size_t function(seq_iterator seq_begin, seq_iterator seq_end) { }
skipping_condition et required_condition sont deux foncteurs booléens prenant un ou deux paramètres (d'où mon thread de cet aprem : ici).

La fonction ci-dessus encapsule la skipping condition dans un filter_iterator et appelle la même fonction sans le paramètre template encapsulé :
Code:

1 2 3 4 5 template <typename required_condition, typename seq_iterator> std::size_t function(seq_iterator seq_begin, seq_iterator seq_end) { }
Et vu qu'il y a plus que 2 paramètres templates, ce "dépilage" de template continue encore en encapsulant chaque fois une condition dans un filter ou transform_iterator.

J'aimerais trouver un moyen qui me permette de rentre optionnel ces conditions en passant par une structure "no_skipping_condition" par exemple. L'effet serait d'ignorer ce paramètre template et de ne pas l'encapsuler dans un itérateur.

Alors évidemment on peut utiliser typeid ou d'autre RTTI. Il faut que ça soit fait à la compilation...

Ensuite j'ai un deuxième problème (en quelque sorte similaire au premier) qui a émané suite à mon premier poste.

Considérons la fonction suivante :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 template<typename skipping_condition, typename required_condition, .... > std::size_t checksum(seq_iterator seq_begin, seq_iterator seq_end, counter_type &counter) { if(function_trait<skipping_condition>::arity == 1) { checksum<required_condition, ..., seq_iterator>(boost::filter_iterator(skipping_condition, seq_begin, seq_end), boost::filter_iterator(skipping_condition, seq_end, seq_end), counter); } if(function_trait<skipping_condition>::arity == 2) { checksum<required_condition, ..., seq_iterator>(boost::filter_iterator(boost::bind(skipping_condition, boost::bind(deref<counter_type>, counter)), seq_begin, seq_end), boost::filter_iterator(boost::bind(skipping_condition, boost::bind(deref<counter_type>, counter)), seq_end, seq_end), counter); } } template<class T> T& deref( T* p ) { return *p; }
Le problème c'est que vérifier l'arité de la fonction est une vérification du runtime alors qu'il me faut vérifier tout ça au compile-time... J'ai bien regardé du côté de boost::mpl mais je ne trouve pas LA fonction qui fera mon bonheur :cry:

J'espère que j'ai été assez clair sur ce que je n'arrivais pas à faire.

Merci pour vos réponses.

27/01/2012, 20h52
Flob90

Je ne suis pas certain de bien comprendre ton problème, mais tu pourrais introduire des classes NoSkipping, NoRequired et utiliser la spécialisation (classe de trait, de politique) pour définir des comportements dépendant de ceux-ci au besoin?

Pourtant il y a bien un if_ dans mpl, par contre ca te retourne un type, il te reste à bien choisir les types pour qu'il réalise le résultat souhaité.
27/01/2012, 20h56
Trademark

Effectivement la spécialisation est la solution mais j'ai vu qu'on ne pouvait pas spécialiser partiellement des fonctions ? Je me trompe ?

Et qu'en est-il du 2ème problème ? Je viens de voir l'édit du message. Avec le if_c mais j'ai du mal à voir comment un type peut faire le boulot d'une fonction, avec des membres statiques ?
27/01/2012, 20h57
Flob90

Pour le second j'ai édité mon message précédent.

Oui tu ne peux pas spécialiser partiellement une fonction, mais tu peux le faire pour les classes de trait / de politique, et utiliser celle-ci dans ta fonction.
27/01/2012, 21h08
Flob90

Citation:

Avec le if_c mais j'ai du mal à voir comment un type peut faire le boulot d'une fonction

Tu peux aussi instancier la classe et appeler une méthode. Par contre fais attention à l'écriture de ta fonction, essaies de garder le maximum de points de variations (que tu puisses changer le comportement de ton algo sans devoir réécrire l'ensemble des tes classes).
28/01/2012, 12h51
Joel F

Citation:

Envoyé par Trademark

comment un type peut faire le boulot d'une fonction, avec des membres statiques ?

bah tu l'instancie et tu appelels son operator()()

Bonjour et merci pour tes réponses Flob90.

J'ai un peu "joué" avec tout ça cette nuit et ce matin et je suis amené à me poser plusieurs questions :

Tout d'abord, est-ce une bonne idée de passer des fonctions (foncteurs) en paramètres template. J'étais parti la dessus parce que j'en avais quand même pas mal (4 fonctions) à passer en paramètres.
Du coup, en testant, je me suis rendu compte qu'on ne peut pas passer une fonction en argument template (logique vu qu'une fonction est un pointeur me direz-vous). Donc, c'est encore un doute de plus sur le fait que peut-être il serait plus intéressant de le passer en paramètre avec instanciation préalable.
Mais par rapport à au dessus, comment faire pour encapsuler facilement une fonction dans un type ?

Vu que vous m'aviez parlé des traits, j'ai décidé de les utiliser, et plus je codais plus je trouvais ça bien. Mais bon je m'étais un peu trop cru au pays des bisounours... :triste:

J'ai fait les codes suivant :

L'appel des classes de trait doit se passer comme suit :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename skipping_condition, 
		  typename required_condition,
		  typename transform_function,
		  typename checksum_function,
		  typename size_contract, 
		  typename counter_type,
		  typename seq_iterator>
std::size_t checksum(seq_iterator seq_begin, seq_iterator seq_end, counter_type &counter)
{
  typedef condition_trait<skipping_condition, boost::filter_iterator> cond;
 
  return checksum<required_condition, 
                          transform_function,
		          checksum_function, 
			  size_contract, 
		          counter_type> (cond::begin(seq_begin, seq_end, counter), 
				                cond::end(seq_end, counter),
						counter);
}

Code:

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
struct no_arg{};
 
template <typename function, 
          typename result_type = boost::function_traits<function>::result_type,
          typename arg1_type = boost::function_traits<function>::arg1_type,
	  std::size_t arity = boost::function_traits<function>::arity>
struct arity_trait;
 
template <typename unary_function, 
          typename result_type = boost::function_traits<unary_function>::result_type,
	  typename arg1_type = boost::function_traits<unary_function>::arg1_type,
	  std::size_t arity = boost::function_traits<unary_function>::arity>
struct arity_trait<unary_function, result_type, arg1_type, 1>
{
  typedef unary_function type;
 
  template <typename bind_arg>
  static type bind_function(unary_function f, bind_arg&)
  {
    return f;
  }
};
 
template <typename binary_function, 
          typename result_type = boost::function_traits<binary_function>::result_type,
	  typename arg1_type = boost::function_traits<binary_function>::arg1_type,
	  std::size_t arity = boost::function_traits<binary_function>::arity>
struct arity_trait<binary_function, result_type, arg1_type, 2>
{
  typedef boost::function<result_type(arg1_type)> type;
 
  template <typename bind_arg>
  static type bind_function(binary_function f, bind_arg& arg)
  {
    return boost::bind(f(), boost::bind(deref<bind_arg>, arg));
  }
};
 
template <typename function, typename iterator>
struct condition_trait
{
  template <typename base_iterator, typename bind_arg>
  static iterator<function, base_iterator> begin(base_iterator b, base_iterator e, bind_arg &arg)
  {
    typedef arity_trait<function> binding;
    return iterator<binding::type, base_iterator>(binding::bind_function(function(), arg), b, e);
  }
 
  template <typename base_iterator, typename bind_arg>
  static iterator<function, base_iterator> end(base_iterator b, base_iterator e, bind_arg &arg)
  {
    typedef arity_trait<function> binding;
    return iterator<binding::type, base_iterator>(binding::bind_function(function(), arg), e, e);
  }
};
 
template <typename condition, typename iterator>
struct condition_trait<no_arg, iterator>
{
  template <typename base_iterator, typename bind_arg>
  static base_iterator& begin(base_iterator &b, base_iterator &, bind_arg&) 
  {
    return b;
  }
 
  template <typename base_iterator, typename bind_arg>
  static base_iterator& end(base_iterator &e, bind_arg&) 
  {
    return e;
  }
}

Premièrement il y a une spécialisation de condition_trait pour gérer le cas où il n'y a pas besoin de condition.
Ensuite il y a arity_trait qui permet de séparer les fonctions unaire et binaire.

Je ne sais plus comment faire, il doit surement y avoir un problème dans mon raisonnement et peut-être que j'essaye de faire des choses impossibles ou que je les simplifie trop.

En bref : :f1:.

Merci :)

28/01/2012, 13h02
Joel F

Le plus simples est de passer un foncteur, ie une classe avec un operator()() surchargé. Comme ca tu peut utilsie rle type directement sasn 345678 appels a function_traits et son appel se limite a instanceir le type puis utiliser ().
28/01/2012, 13h13
Trademark

Merci pour ta réponse Joel F.

On peut donc seulement passer des foncteurs en paramètres template. Le soucis, et le pourquoi j'ai utilisé function_traits, c'est qu'il faut savoir quand l'opérateur() prend un ou deux paramètres pour binder le deuxième paramètre si besoin.

Et si l'utilisateur n'a qu'une fonction sous la main, comment peut-il la passer facilement à ma fonction template ? Doit-il l'encapsuler tout seul dans une structure ?
28/01/2012, 15h51
Joel F

Citation:

Envoyé par Trademark

Merci pour ta réponse Joel F.

On peut donc seulement passer des foncteurs en paramètres template. Le soucis, et le pourquoi j'ai utilisé function_traits, c'est qu'il faut savoir quand l'opérateur() prend un ou deux paramètres pour binder le deuxième paramètre si besoin.

Et si l'utilisateur n'a qu'une fonction sous la main, comment peut-il la passer facilement à ma fonction template ? Doit-il l'encapsuler tout seul dans une structure ?

Non les foncteurs sont des types comme les autres, tu les passe en arguments classiquement et tu laisses le reste se faire gerer par le compilateur.

Pour le binding, il est, je pense, plus censé d'avoir une fonction qui attend explicitement une foncton avec une signature fixe et laisser les gens utiliser bind pour s'y conformer que de meta-programmer un truc bancal.
28/01/2012, 17h15
Trademark

Citation:

Envoyé par Joel F

Non les foncteurs sont des types comme les autres, tu les passe en arguments classiquement et tu laisses le reste se faire gerer par le compilateur.

Oui mais je voulais parler des pointeurs de fonction. Comment encapsuler facilement un pointeur de fonction dans un type ?

Citation:

Envoyé par Joel F

Pour le binding, il est, je pense, plus censé d'avoir une fonction qui attend explicitement une foncton avec une signature fixe et laisser les gens utiliser bind pour s'y conformer que de meta-programmer un truc bancal.

Oui je suis d'accord sur le principe, mais le problème, c'est que le binding ne peut pas s'effectuer au niveau de celui qui utilisera la fonction car le deuxième paramètre à binder n'a pas encore été instancié. Dans ce cas, il s'agit d'un counting_iterator encapsulé dans un filter_iterator. Il permet de compter le nombre de caractère rencontré mais de "skipper" par exemple de la valeur 6 à 8 selon certaines conditions pré-établie (le predicate du filter_iterator).

Et binder la fonction veut dire la passer en argument tout en étant instancié.

Je pense que ça pourrait choquer d'avoir autant de paramètre à passer, non ?
28/01/2012, 17h32
Joel F

binder, comme dans utiliser boost::bind
28/01/2012, 18h26
Flob90

Tes classes resseblent plus à des classes de politiques qu'à des classes de traits, et elles sont imbriqués alors que je pense qu'il est possible de faire sans.

En l'état actuel elle ne servent à rien, car les templates sont quelque-chose de "statique", le type de ton foncteur c'est std::function<...>, c'est avec ca que ton template est instancié, pas avec unary ou binary.

(template <typename condition, typename iterator> => template <typename iterator>)

Ton besoin d'un type qui fait quelque chose était pour utiliser mpl, tu sais exactement ce que le type doit faire, tu n'as pas besoin d'un pointeur de fonction, écrit directement ton foncteur en dur. Si il a besoin d'information qui ne seront connues qu'au moment de l'appel, alors passe les en paramètre de l'opérateur ().
29/01/2012, 09h31
3DArchi

Salut,
J'ai l'impression que tu t'enfonces dans un labyrinthe de complexité et pour lequel chaque coin te réserve de nouveaux problèmes que tu cherches à résoudre avec une nouvelle couche de complexité.

C'est typiquement le moment où il faut oublier le C++, les templates et tout le reste, prendre une feuille de papier et reposer le problème. Quel est le rôle de la fonction ? Ensuite, seulement on regarde les outils à disposition.

Deuxième écueil, à la lecture, je ne vois pas une nette séparation des différents traitements et étapes que déroule ta fonction. Ce n'est pas parce qu'on est en méta prog qu'il ne faut pas faire une distribution claire des rôles dans des unités dédiées.

J'ai du mal à voir quelle expression tu cherches vraiment à construire. Cependant la multiplicité des foncteurs et la volonté d'un traitement récursif me donne envi de suggérer un coup d’œil sur les type listes (séquences MPL ou fusion) pour généraliser un peu et éviter la fonction à 45 paramètres templates.

Mais ma première question demeure : peux tu décrire en quelques mots l'objectif de la fonction ?
29/01/2012, 15h46
Trademark
Merci pour la réponse 3DArchi, je pense aussi que ça devenait trop complexe mais grâce à vous j'ai pu prendre un peu de distance. Je ne peux pas décrire en quelques mots, mais je vais essayer d'être aussi bref que possible sans trop oublier de détails.

Je dois créer une bibliothèque générique pour la vérification et le calcul de clé de contrôle. Par exemple, les codes-barres ou les numéros de comptes ou cartes sont des séquences de caractères avec une clé de contrôle.

En généralisant, je me suis rendu compte que pour chaque numéro il fallait appliquer une suite d'action dans un ordre précis que voici :
1. "skipping_predicate" : Permet d'ignorer une valeur si celle-ci n'est pas probante pour le calcul de la clé (par exemple les tirets ou espaces dans un numéro).
2. "required_predicate" : Toutes les valeurs doivent répondre vrai à ce prédicat sinon le nombre n'est pas correct (Par exemple, un numéro de carte VISA doit commencer par '4'). (Lorsque ce prédicat renvoie faux, le traitement s'arrête et une erreur est renvoyée).
3. "conversion_function" : Certain numéro ont des lettres qui nécessitent d'être convertie en chiffre selon une formule ou une table de conversion.
4. "checksum_function" : Fonction binaire permettant d'accumuler la somme de contrôle pour chaque valeur passée en argument.
Les trois premiers points sont optionnelles. Dans un premier temps j'avais codé des classes de polices qui encapsulait plus ou moins ces 4 traitements et qui pouvait hériter entre elle pour bénéficier d'une factorisation du code. Vous pouvez éventuellement voir le fonctionnement dans la doc que j'avais écrite. Et maintenant j'ai plutôt encapsulé les deux premiers dans un filter_iterator et le 3ème dans un transform_iterator. Le dernier est passé en argument à std::accumulate.

Il faut ajouter à ça certaines contraintes :
- La séquence peut être parcourue de gauche à droite ou droite à gauche.
- Il peut avoir la clé de contrôle dans la séquence ou pas. Et la clé de contrôle à une taille ainsi qu'une position dans le nombre.
- Un numéro peut avoir une taille attendue.
C'est plus ou moins tout. Ce qui est primordial, c'est que l'utilisateur puisse facilement créer ses propres algorithmes si ils ne sont pas proposés de base dans l'API.

Ce qui est délicat c'est de connaitre la position du caractère qu'on est en train de traiter dans les prédicats et fonctions sus-cités. D'où les essais de "binding" précédent.

D'une autre part, il faut la position "réelle" du caractère (clé de contrôle comprise si on doit la calculer). Alors pour ça j'utilise un compteur implémenté sous forme d'un counting_iterator, et si la clé de contrôle n'est pas présente dans le nombre (car on veut la calculer) alors il y a un filter_iterator qui encapsule le counting_iterator avec un prédicat qui "skip" les caractères englobant la clé de contrôle.

Plus haut, je voulais binder automatiquement (et spécialiser des traits en fonction de l'arité des fonctions passées en paramètre) pour éviter que l'utilisateur n'instancie ce compteur et le bind lui-même à sa fonction.

Merci de m'avoir lu, j'ai besoin des conseils de programmeurs plus expérimentés sur ce coup :)
29/01/2012, 18h00
Flob90

Pourquoi tu fais une fonction qui fait "tout d'un coup" ? Personnelement j'aurais décomposé le problème :
- La suppresion des caractères inutiles via un système type "lexer"
- Vérification via une regex
- Transformation/Extraction via un système type "parser"
- Calcul via accumulate

Et en forcant un peu, les 3 premiers points se font avec lexer/parser (boost::spirit).

Edit: En y réfléchissant un peu, sortir boost::spirit est peut-être un peu fort (sur le fond ce ne sera qu'un boucle for de parcourt, qui se traduirait dans spirit par une règle du style *(char_[...]), l'essentiel étant dans les ...), un for_each avec un foncteur bien choisit pourrait suffir (foncteur écrit avec boost::phoenix par exemple).
30/01/2012, 18h54
Trademark

C'est clair que décomposer le problème facilite bien des choses, mais ce qui m'embête c'est que je vois pas pourquoi la généricité devrait avoir un coup aussi important. Pour moi, calculer un checksum ça se fait en O(n) (et pas O(4n)) donc en 1 passe sur le nombre.

Est-ce que du O(n) est incompatible avec un résultat fini aussi propre que ce que tu proposes ? Je n'aime pas beaucoup sacrifier la performance, bien qu'ici, vous me direz que ça n'a pas beaucoup d'importance.
30/01/2012, 21h45
Joel F

Deja O(n) == O(4n) = O(45678n) ;)

La fusion de boucle est ensuite en geenral bien faite par les compilos.
30/01/2012, 23h51
Ekleog

En plus, même sans une optimisation (pas si certaine que ça, d'ailleurs, si tu fais plusieurs fonctions non-inlines), entre une passe et 4, les deux seules différences seront le nombre d'incrémentations de la variable (=> coût ~ 0), et le nombre de cache miss, car il faut repasser sur toute la chaine (=> coût ~ 0).

Pourquoi dis-je "cout ~ 0" ?
Simplement parce que la vérification pour un code barre ou carte bancaire ou autre élément à faible longueur prendra toujours un temps si infime en soi que la moitié (au moins) du temps sera passé à calculer la checksum.

En bref, une boucle ou 4, ça ne changera pas grand chose niveau performances. (si il fallait traiter X Mio de données, je ne dirais pas, mais ...)

Et, comme le dit le voisin du dessus, O(4n) = O(n)
31/01/2012, 07h23
3DArchi

Citation:

Envoyé par Trademark

C'est clair que décomposer le problème facilite bien des choses, mais ce qui m'embête c'est que je vois pas pourquoi la généricité devrait avoir un coup aussi important.

Elle n'en a pas (forcément). L'idée est plutôt de décomposer ton problème en items simples et ensuite de les assembler (par collaboration les uns les autres, pas par copier/coller). Sans quoi, tu t'enferres dans des problèmes techniques sans nom.

Première question : quelle est l'interface de ta bibliothèque (interface en terme de 'concepts' par forcément en terme de fonctions/classes dans un premier temps) ? La réponse à cette question devrait déjà aider à voir 1/d'identifier les points de variations et 2/comment à avoir une idée sur les éléments de design (surcharge, template, classes, etc..) pour y répondre.

Voir 40 message(s) de cette discussion en une page