Question

Le 14-12-2006, Pierre THIERRY <nowhere.man@levallois.eu.org> a écrit :

Bonjour tout le monde,

j'ai une question, qui est en fait un défi à réaliser ce qui m'a semblé
impossible en C++. Ou plutôt, difficilement possible. J'ai galéré
pendant 6 moix à essayer de tourner le truc dans tous les sens, et il
m'a semblé que ce ne serait possible qu'avec de la méta-programmation de
templates. L'utilisation d'une bibliothèque existante semblait tout à
fait possible, heureusement (la MPL). Néanmoins, quand je me suis mis à
Common Lisp, j'ai refait un essai avec ce nouveau langage, et là, en
quelques heures, j'avais un code qui marchait partiellement, et qui en
particulier implémentait ce qui m'avait semblé le plus inaccessible en
C++ :

J'ai surement pas compris où était le problème, car je vois pas
en quoi c'est difficile à faire en C++.

J'aimerais avoir un système pour créer toutes les combinaisons possibles
d'éléments piochés dans des listes,

OK, 3 boucles imbriquées.

le filtrage de ses combinaisons pour
celles qui n'ont pas de sens,

remove_if

puis le classement des combinaisons
restantes, selon 1 ou plusieurs critères.

sort

Qui plus est, je voudrais
pouvoir définir des opérations qui altèrent les listes avant leur
passage dans le système,

transform

et que la combinaison de ces opérations puisse
être gardée pour plus tard (pas forcément sérialisées, seulement en
mémoire),

Là, j'ai pas compris.

et que l'utilisateur puisse choisir ces opérations.

Exemple : j'ai trois listes {client}, {lot1, ..., lotN} et {banque1,
..., banqueN} et je veux que dans la première on ajoute une version
modifiée du client et que dans la troisième on remplace chaque banque
par une liste des offres de financement qu'elle propose. On doit
construire tous les triplets {client, lot, financement}, en virant ceux
pour lesquels on sait que la banque refuserait (le client ou le lot) ou
que le client ne peux payer (le lot). Ensuite, on veut le meilleur
triplet dans deux classements : celui où le financement fait sortir le
moins d'argent chaque mois, celui où l'investissement rapporte le plus.

Où est le problème ?

Pour donner un exemple numérique, donc testable si quelqu'un a le
courage d'aller jusqu'à implémenter son idée, on peut prendre les listes
{1 2 3} et {4 5 6 7 8 9}, avec comme opération préalable d'enlever tout
nombre supérieur à 6 de la deuxième liste, en refusant les couples dont
un seul nombre est impair, et comme classement, les couples dont la
différence est la plus petite ({3 5}=2 ou {2 4}=2) et le produit le plus
grand ({3 5}). Il faudrait ensuite pourvoir simplement redonner deux
autres listes, et que toutes les opérations soient refaites (modifier la
seconde liste si nécessaire, combiner, filtrer les couples, sortir deux
couples).

Pas vraiment le temps là ce matin, mais je vois pas de pb majeur.
J'ai peut-être raté quelque chose.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)

Pierre THIERRY wrote:

Bonjour tout le monde,

j'ai une question, qui est en fait un défi à réaliser ce qui m'a semblé
impossible en C++. Ou plutôt, difficilement possible. J'ai galéré
pendant 6 moix à essayer de tourner le truc dans tous les sens, et il
m'a semblé que ce ne serait possible qu'avec de la méta-programmation de
templates. L'utilisation d'une bibliothèque existante semblait tout à
fait possible, heureusement (la MPL). Néanmoins, quand je me suis mis à
Common Lisp, j'ai refait un essai avec ce nouveau langage, et là, en
quelques heures, j'avais un code qui marchait partiellement, et qui en
particulier implémentait ce qui m'avait semblé le plus inaccessible en
C++ :

J'aimerais avoir un système pour créer toutes les combinaisons possibles
d'éléments piochés dans des listes, le filtrage de ses combinaisons pour
celles qui n'ont pas de sens, puis le classement des combinaisons
restantes, selon 1 ou plusieurs critères. Qui plus est, je voudrais
pouvoir définir des opérations qui altèrent les listes avant leur

Tout le probleme est d'identifier a quel degre de flexibilite tu veux
avoir acces (dynamique?).

passage dans le système, et que la combinaison de ces opérations puisse
être gardée pour plus tard (pas forcément sérialisées, seulement en
mémoire), et que l'utilisateur puisse choisir ces opérations.

google Memoisation.

Exemple : j'ai trois listes {client}, {lot1, ..., lotN} et {banque1,
..., banqueN} et je veux que dans la première on ajoute une version
modifiée du client et que dans la troisième on remplace chaque banque
par une liste des offres de financement qu'elle propose. On doit
construire tous les triplets {client, lot, financement}, en virant ceux
pour lesquels on sait que la banque refuserait (le client ou le lot) ou
que le client ne peux payer (le lot). Ensuite, on veut le meilleur
triplet dans deux classements : celui où le financement fait sortir le
moins d'argent chaque mois, celui où l'investissement rapporte le plus.

Pour donner un exemple numérique, donc testable si quelqu'un a le
courage d'aller jusqu'à implémenter son idée, on peut prendre les listes
{1 2 3} et {4 5 6 7 8 9}, avec comme opération préalable d'enlever tout
nombre supérieur à 6 de la deuxième liste, en refusant les couples dont
un seul nombre est impair, et comme classement, les couples dont la
différence est la plus petite ({3 5}=2 ou {2 4}=2) et le produit le plus
grand ({3 5}). Il faudrait ensuite pourvoir simplement redonner deux
autres listes, et que toutes les opérations soient refaites (modifier la
seconde liste si nécessaire, combiner, filtrer les couples, sortir deux
couples).

Je ne sais pas si j'expose mon problème très clairement. Dans tous les
cas, je serais ravi d'entendre que c'était parfaitement faisable en C++,
parce que je ne vois pas comment, sans passer par une lib comme la MPL
(tout en étant typesafe, puisqu'on est en C++...).

Effectivement, c'est un sujet difficile pour C++ compare a d'autres
langages. Comme tu as mentionne Common Lisp, je me permets de mentionner
Haskell, qui est tres approprie pour ce genre d'exercice. C'est un
langage statiquement type qui supporte les fermetures et la composition
(comme tous les FPL), les fonctions avec arites decomposables et
l'evaluation paresseuse. Ces 4 concepts font de lui un langage de
predilection pour la construction de graphe de combinateurs (google
haskell+combinator), c'est a dire des graphes (potentiellement infini)
ou chaque noeud est une fonction (incomplete) qui filtre un flot de
donnees. L'exemple typique, c'est l'ecriture de parsers. Ton probleme
est analogue mais avec un generateur (paresseux = a la demande) des
combinaisions a partir des listes comme source de donnees au lieu d'un
fichier. Comme le domaine est apparament lie aux contrats en finance, je
peux te conseiller la lecture du papier:

http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.htm

Dans les groupes de discussion de Haskell, il est recurrent de voir des
personnes demander comment resoudre ce type de probleme en C++/Java/C#
en ayant un protoype en Haskell qui marche (et en general en qques
lignes). La reponse est rarement a la hauteur des esperances du
demandeur. Mais la comprehension des concepts cites ci-dessus t'aidera
certainement a mieux le programmer en C++ etant donne qu'a qqchose pres,
il te faut refaire a la main ce que Haskell supporte nativement. Et
effectivement MPL (et Boost de maniere plus generale) peut aider.

Je sais, c'est une reponse de normand ;-)

a+, ld.

Pierre THIERRY <nowhere.man@levallois.eu.org> writes:

Pour donner un exemple numérique, donc testable si quelqu'un a le courage
d'aller jusqu'à implémenter son idée, on peut prendre les listes {1 2 3}
et {4 5 6 7 8 9}, avec comme opération préalable d'enlever tout nombre
supérieur à 6 de la deuxième liste, en refusant les couples dont un seul
nombre est impair, et comme classement, les couples dont la différence
est la plus petite ({3 5}=2 ou {2 4}=2) et le produit le plus grand ({3
5}). Il faudrait ensuite pourvoir simplement redonner deux autres
listes, et que toutes les opérations soient refaites (modifier la seconde
liste si nécessaire, combiner, filtrer les couples, sortir deux couples).

C'est plus facile a faire en Lisp, mais pas impossible a faire en C++.
Code rapide ecrit pendant qu'un test un peu long tourne.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <ostream>

template <typename Idest, typename ISrc1, typename ISrc2>
void make_pairs(ISrc1 begin1, ISrc1 end1,
ISrc2 begin2, ISrc2 end2,
Idest dest)
{
for (ISrc1 i1 = begin1; i1 != end1; ++i1) {
for (ISrc2 i2 = begin2; i2 != end2; ++i2) {
*dest++ = std::make_pair(*i1, *i2);
}
}
}

template<typename T>
struct greater {
greater(T const& thresold) : thresold_(thresold) {}
// greater(greater const&);
// greater& operator=(greater const&);
// ~greater();

bool operator()(T const& v) {
return v > thresold_;
}
private:
T thresold_;
};

bool oneOdd(std::pair<int, int> const& p)
{
return (p.first % 2 == 1) != (p.second % 2 == 1);
}

bool better(std::pair<int, int> const& p1, std::pair<int, int> const& p2)
{
return ((p1.second - p1.first < p2.second - p2.first)
|| ((p1.second - p1.first == p2.second - p2.first)
&& (p1.second * p1.first > p2.second * p2.first)));
}

std::ostream& operator<<(std::ostream& os, std::pair<int, int> const& p)
{
return os << "(" << p.first << ", " << p.second << ")";
}

int const l1init[] = {1, 2, 3};
int const l2init[] = {4, 5, 6, 7, 8, 9};

int main()
{
std::list<int> l1(l1init, l1init+(sizeof l1init/sizeof *l1init));
std::list<int> l2(l2init, l2init+(sizeof l2init/sizeof *l2init));

// en supposant qu'il faille garder la liste de depart intacte,
// voir plus base remove si ce n'est pas le cas
std::list<int> l2filtered;
std::remove_copy_if(l2.begin(), l2.end(),
std::back_insert_iterator<std::list<int> >(l2filtered),
greater<int>(6));

std::list<std::pair<int, int> > couples;

make_pairs(l1.begin(), l1.end(),
l2filtered.begin(), l2filtered.end(),
std::back_insert_iterator<std::list<std::pair<int, int> > >(couples));

std::list<std::pair<int, int> > ::iterator
last = std::remove_if(couples.begin(), couples.end(), oneOdd);
couples.erase(last, couples.end());

couples.sort(better);

std::copy(couples.begin(), couples.end(),
std::ostream_iterator<std::pair<int, int> >(std::cout, " "));
std::cout << 'n';
}

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Marc Boyer wrote:

j'ai une question, qui est en fait un défi à réaliser ce qui m'a semblé
impossible en C++. Ou plutôt, difficilement possible. J'ai galéré
pendant 6 moix à essayer de tourner le truc dans tous les sens, et il
m'a semblé que ce ne serait possible qu'avec de la méta-programmati on de
templates. L'utilisation d'une bibliothèque existante semblait tout à
fait possible, heureusement (la MPL). Néanmoins, quand je me suis mis à
Common Lisp, j'ai refait un essai avec ce nouveau langage, et là, en
quelques heures, j'avais un code qui marchait partiellement, et qui en
particulier implémentait ce qui m'avait semblé le plus inaccessible en
C++ :

J'ai surement pas compris où était le problème, car je vois pas
en quoi c'est difficile à faire en C++.

Une partie du problème vient déjà de sa formulation : il a des
listes. S'il parlait des collections (ou des containers), à la
place des listes, ça serait plus conforme à la nomenclature
habituelle.

J'aimerais avoir un système pour créer toutes les combinaisons poss ibles
d'éléments piochés dans des listes,

OK, 3 boucles imbriquées.

D'abord ne faut-il pas définir la structures des données ?
Comment représenter une combinaison ? Et où en stocker les
résultats ? (Ce sont deux questions qui ne se posent pas en
Lisp, qui n'a qu'une seule structure de données, la liste.)

À l'encontre de Lisp, on n'aurait typiquement pas une solution
générique en C++ (au moins que le besoin s'en fait sentir par la
suite). A priori, je m'attendrais à quelque chose du genre :

struct Something
{
std::string fromSetA ;
int fromSetB ;
double fromSetC ;
} ;

sauf qu'évidemment, les noms auraient une signification dans
l'application, et (probablement) on donnerait un constructeur à
la classe. Seulement alors s'attaque-t-on aux boucles
imbriquées.

le filtrage de ses combinaisons pour
celles qui n'ont pas de sens,

remove_if

puis le classement des combinaisons
restantes, selon 1 ou plusieurs critères.

sort

Qui plus est, je voudrais
pouvoir définir des opérations qui altèrent les listes avant leur
passage dans le système,

transform

Pour certains types d'altérations. Pour d'autres, encore
remove_if. Et pour d'autres, il n'y a pas de fonction prévue --
quand j'écrivais des programmes qui travaillaient sur des
valeurs physiques (pressions, etc.), le lissage était la
transformation la plus fréquente, et il n'y a pas de fonction
prévue qui le supporte directement. (En revanche, C'est trivial
à implémenter sur une suite qui a un itérateur à accès
aléatoire, et pas trop difficile si l'itérateur est forward ou
bi-directionnel.)

et que la combinaison de ces opérations puisse
être gardée pour plus tard (pas forcément sérialisées, seulem ent en
mémoire),

Là, j'ai pas compris.

Il ne veut pas que la variable soit sur la pile. L'operator new
doit être ce qu'il cherche.

et que l'utilisateur puisse choisir ces opérations.

Et c'est là que ça se corse. Si j'ai bien compris, il veut un
interpréteur. Ou un mini langage, ou quelque chose du genre. Que
c'est à l'exécution que l'utilisateur spécifie les ensembles qui
lui intéressent, les conditions de filtrage et les
transformations à effectuer.

En Lisp, tu converis la requête utilisateur en source Lisp, et
tu l'exécutes. La même chose est possible en C++ : tu convertis
la requête en C++, tu invoques le compilateur (fonction system)
pour en faire un objet dynamique (.dll ou .so, selon le
système), et tu le charges. C'est quand même plus lourd qu'en
Lisp. (Et pas portable, parce que comment invoquer le
compilateur et comment charger un objet dynamique varie d'un
système à l'autre. Et évidemment, tu imposes que l'utilisateur
ait un compilateur installé sur son système, ce qui ne va pas de
soi.)

Exemple : j'ai trois listes {client}, {lot1, ..., lotN} et {banque1,
..., banqueN} et je veux que dans la première on ajoute une version
modifiée du client et que dans la troisième on remplace chaque banq ue
par une liste des offres de financement qu'elle propose. On doit
construire tous les triplets {client, lot, financement}, en virant ceux
pour lesquels on sait que la banque refuserait (le client ou le lot) ou
que le client ne peux payer (le lot). Ensuite, on veut le meilleur
triplet dans deux classements : celui où le financement fait sortir le
moins d'argent chaque mois, celui où l'investissement rapporte le plu s.

Où est le problème ?

En fait, ce genre de problème se résoud la plupart du temps en
SQL.

Pour donner un exemple numérique, donc testable si quelqu'un a le
courage d'aller jusqu'à implémenter son idée, on peut prendre les listes
{1 2 3} et {4 5 6 7 8 9}, avec comme opération préalable d'enlever tout
nombre supérieur à 6 de la deuxième liste, en refusant les couple s dont
un seul nombre est impair, et comme classement, les couples dont la
différence est la plus petite ({3 5}=2 ou {2 4}=2) et le produit le plus
grand ({3 5}=15). Il faudrait ensuite pourvoir simplement redonner de ux
autres listes, et que toutes les opérations soient refaites (modifier la
seconde liste si nécessaire, combiner, filtrer les couples, sortir de ux
couples).

Pas vraiment le temps là ce matin, mais je vois pas de pb majeur.
J'ai peut-être raté quelque chose.

S'il veut réelement un interpréteur, il faut l'implémenter. Rien
de compliquer, bien sûr, mais pas mal de boulot quand même.

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Le Thu, 14 Dec 2006 06:06:01 -0800, James Kanze a écrit:

Une partie du problème vient déjà de sa formulation : il a des listes.

Effectivement, l'implémentation de mon prototype déteint sur ma
formulation du problème...

D'abord ne faut-il pas définir la structures des données ? Comment
représenter une combinaison ? Et où en stocker les résultats ?

Dans l'implémentation C++, je comptais me servir de tuples pour stocker
les combinaisons. Il me semblait judicieux d'utiliser la structure la
plus légère de la STL pour stocker les tuples retenus, donc une liste
doublement chainée (simple aurait suffit, mais si mes souvenirs sont
bons, slist est une extension de la STL...).

(Ce sont deux questions qui ne se posent pas en Lisp, qui n'a qu'une
seule structure de données, la liste.)

Le LISP de 1958, peut-être. Mais j'utilise Common Lisp...

À l'encontre de Lisp, on n'aurait typiquement pas une solution
générique en C++ (au moins que le besoin s'en fait sentir par la
suite). A priori, je m'attendrais à quelque chose du genre :

struct Something
{
std::string fromSetA ;
int fromSetB ;
double fromSetC ;
} ;

La solution non générique, je sais l'écrire. En deux coups de cuiller à
pot, même. Et à ce prix-là, je ne m'emmerde pas, et j'écris trois ou
quatres boucles imbriquées et c'est torché.

Mais je me posais la question de savoir si c'est réalisable de façon
générique.

C'est là qu'on tombe sur des problèmes de type. Il faut écrire ici un
code capable de s'adapter à un nombre inconnu (éventuellement borné)
d'éléments dans les tuples qui vont être produits, de types inconnus à
l'avance.

Je voudrais pouvoir l'utiliser ainsi :

TupleFactory<Client,Lot,Financement> tf1;

aussi bien que :

TupleFactory<int,int,double,float> tf2;

et que l'utilisateur puisse choisir ces opérations.
Et c'est là que ça se corse. Si j'ai bien compris, il veut un

interpréteur. Ou un mini langage, ou quelque chose du genre. Que c'est
à l'exécution que l'utilisateur spécifie les ensembles qui lui
intéressent, les conditions de filtrage et les transformations à
effectuer.

Oui, mais cette partie-là peut être gérée par une forme de machine à
états, et ne nécessite d'interprêter qu'un langage vraiment minimaliste.
Pour des tuples à trois éléments, par exemple, les opérations pourraient
être spécifiées ainsi :

"op1,op2,op3::op4,op5"

Où les opérations "op1", "op2" et "op3" seraient appliquées au conteneur
destiné à fournir les premiers éléments des tuples et "op4" et "op5"
seraient appliqués au conteneur fournissant les troisièmes éléments des
tuples, le second étant utilisé intouché. Si les opérations peuvent
manipuler une pile de registres, on peut même « compliquer » notre
syntaxe en permettant de spécifier la pile initiale, toujours par des
chaînes de caractères qui sont mappées par l'application à des données
qu'elle manipule.

Loin de moi l'idée de constuire un interpréteur Turing-complete pour
ça... (quoique qu'une fois que je suis passé à Lisp, étant donné la
présence en standard d'une fonction eval et même de la fonction compile,
ça devenait envisageable)

En Lisp, tu converis la requête utilisateur en source Lisp, et tu
l'exécutes.

Oui, c'est possible. Pas forcément une bonne idée, mais possible.

En fait, ce genre de problème se résoud la plupart du temps en SQL.

<illumination mode="Je m'en étais pas rendu comtpe">
Tiens, c'est vrai...
</illumination>

Simplement,
Pierre
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Le Thu, 14 Dec 2006 11:56:16 +0100, Laurent Deniau a écrit:

et que la combinaison de ces opérations puisse être gardée pour plus
tard (pas forcément sérialisées, seulement en mémoire), et que
l'utilisateur puisse choisir ces opérations.
google Memoisation.

Mes opérations ne sont pas forcément référentiellement transparentes,
aussi la mémoisation n'est pas utilisable dans le cas générique.

Effectivement, c'est un sujet difficile pour C++ compare a d'autres
langages. Comme tu as mentionne Common Lisp, je me permets de
mentionner Haskell, qui est tres approprie pour ce genre d'exercice.

Il est sur le dessus de ma pile de langages à apprendre depuis quelques
temps ! ;-)

Comme le domaine est apparament lie aux contrats en finance, je peux
te conseiller la lecture du papier:

http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/contracts-icfp.htm

Ça a l'air intéressant, mais le serveur de MS ne me répond pas... J'ai
quand même pu jeter un oeil dans le cache de Google. Si quelqu'un a le
fichier PS de l'article, et qu'il peut me l'envoyer par email, je lui en
serais reconnaissant !

Dans les groupes de discussion de Haskell, il est recurrent de voir
des personnes demander comment resoudre ce type de probleme en
C++/Java/C# en ayant un protoype en Haskell qui marche (et en general
en qques lignes). La reponse est rarement a la hauteur des esperances
du demandeur.

À la limite, ça me rassurerait. Si c'est ardu à mettre au point en C++,
le fait que je n'y sois pas arrivé m'inquièterais moins...

Mais la comprehension des concepts cites ci-dessus t'aidera
certainement a mieux le programmer en C++ etant donne qu'a qqchose
pres, il te faut refaire a la main ce que Haskell supporte nativement.
[...]

Je sais, c'est une reponse de normand ;-)

Non, au contraire, ça me donne des pistes très intéressantes à étudier,
merci beaucoup. Et une raison de plus d'apprendre Haskell !

Curieusement,
Pierre
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Pierre THIERRY wrote:

Le Thu, 14 Dec 2006 06:06:01 -0800, James Kanze a écrit:

Une partie du problème vient déjà de sa formulation : il a des li stes.

Effectivement, l'implémentation de mon prototype déteint sur ma
formulation du problème...

D'abord ne faut-il pas définir la structures des données ? Comment
représenter une combinaison ? Et où en stocker les résultats ?

Dans l'implémentation C++, je comptais me servir de tuples pour stocker
les combinaisons.

Par tuples, entends-tu boost::tuples, ou quelque chose maison ?
L'implémentation de « tuple » le plus simple, c'est
std::vector. En revanche, il n'est pas forcement la plus
performante, si tu as des vector de tuple.

Il me semblait judicieux d'utiliser la structure la
plus légère de la STL pour stocker les tuples retenus, donc une liste
doublement chainée (simple aurait suffit, mais si mes souvenirs sont
bons, slist est une extension de la STL...).

Selon les opérations envisagées, vector ou deque pourrait être
nettement plus legers.

En fait, beaucoup dépend de la taille des ensembles envisagés.
On ne s'attaquera pas de la même façon pour des dizaines de
valeurs que pour des millions.

(Ce sont deux questions qui ne se posent pas en Lisp, qui n'a qu'une
seule structure de données, la liste.)

Le LISP de 1958, peut-être. Mais j'utilise Common Lisp...

Qui en a ajouté des tableaux, etc. Mais la structure dynamique
de base en Lisp, c'est bien une liste. Alors qu'en C++, on
choisit souvent autre chose.

À l'encontre de Lisp, on n'aurait typiquement pas une solution
générique en C++ (au moins que le besoin s'en fait sentir par la
suite). A priori, je m'attendrais à quelque chose du genre :

struct Something
{
std::string fromSetA ;
int fromSetB ;
double fromSetC ;
} ;

La solution non générique, je sais l'écrire. En deux coups de cuill er à
pot, même. Et à ce prix-là, je ne m'emmerde pas, et j'écris trois ou
quatres boucles imbriquées et c'est torché.

Mais je me posais la question de savoir si c'est réalisable de façon
générique.

À quel niveau ? Jusqu'au niveau des types dans les tuples ?
Générique résolue à l'exécution, ou lors de la compilation ?

C'est là qu'on tombe sur des problèmes de type. Il faut écrire ici un
code capable de s'adapter à un nombre inconnu (éventuellement borné)
d'éléments dans les tuples qui vont être produits, de types inconnu s à
l'avance.

Lors de l'exécution, s'entend.

Il y a bien boost::any pour les types, mais sans en savoir plus,
je ne sait pas s'il convient ou non ; pour les rares cas où
j'ai eu à résoudre quelque chose du genre, il aurait été prèsque
trop générique ; un simple hièrarchie d'héritage convenait
mieux.

Il y a aussi l'option d'implémenter quelque chose de non-typé,
genre les variables en AWK. Je l'ai fait dans la passée, avec un
espèce de struct avec tous les types supportés (en fait, string,
double et int), et un tableau de bits pour indiquer la validité
de chacun. Plus ou moins comme une union discriminée, sauf que
je pouvais maintenir plus d'un type à la fois.

Quant aux tuples, si le nombre d'éléments n'est pas trop enlevé,
je crois que j'irais simplement avec un std::vector, ou tu
stockes le type défini ci-dessus. (Je ne suis pas 100% sûr, mais
je crois que le nombre d'éléments dans un boost::tuple, ainsi
que les types, doivent être fixé lors de la compilation.) Sinon,
il pourrait être intéressant d'implémenter quelque chose du
genre vector, mais où chaque objet est membre d'un groupe, et
que c'est le groupe qui gère la taille (et l'allocation de la
mémoire). D'une côté, ça permettrait de s'assurer de façon
simple que tous les tuples dans un ensemble donné sont de la
même taille, et de l'autre, si les temps d'exécution dans
l'allocateur devient un problème, c'est assez facile à
optimiser.

Je voudrais pouvoir l'utiliser ainsi :

TupleFactory<Client,Lot,Financement> tf1;

aussi bien que :

TupleFactory<int,int,double,float> tf2;

Mais il faudrait savoir lequel lors de l'écriture du programme.

et que l'utilisateur puisse choisir ces opérations.
Et c'est là que ça se corse. Si j'ai bien compris, il veut un

interpréteur. Ou un mini langage, ou quelque chose du genre. Que c'est
à l'exécution que l'utilisateur spécifie les ensembles qui lui
intéressent, les conditions de filtrage et les transformations à
effectuer.

Oui, mais cette partie-là peut être gérée par une forme de machin e à
états, et ne nécessite d'interprêter qu'un langage vraiment minimal iste.
Pour des tuples à trois éléments, par exemple, les opérations pou rraient
être spécifiées ainsi :

"op1,op2,op3::op4,op5"

Où les opérations "op1", "op2" et "op3" seraient appliquées au cont eneur
destiné à fournir les premiers éléments des tuples et "op4" et "o p5"
seraient appliqués au conteneur fournissant les troisièmes élémen ts des
tuples, le second étant utilisé intouché.

Et tu offres un nombre d'opérations fixes. C'est effectivement
très simple.

Si les opérations peuvent
manipuler une pile de registres, on peut même « compliquer » notre
syntaxe en permettant de spécifier la pile initiale, toujours par des
chaînes de caractères qui sont mappées par l'application à des do nnées
qu'elle manipule.

Loin de moi l'idée de constuire un interpréteur Turing-complete pour
ça... (quoique qu'une fois que je suis passé à Lisp, étant donn é la
présence en standard d'une fonction eval et même de la fonction compi le,
ça devenait envisageable)

Même en C++, avec lex et yacc, ce n'est pas la fin du monde. Je
le fais souvent. Dans la mesure où le langage ne permet pas de
structures de boucles ou des sous-programmes, c'est ultra
simple. Mais il faut en général définir une représentation
interne, et un interprêteur pour l'exécuter, alors qu'en Lisp...
(Remarque : sans des instructions de branchage, un interprêteur
threadé est un jeu d'enfants. Un tableau de pointeurs à des
fonctions suffit pour la représentation interne.)

En Lisp, tu converis la requête utilisateur en source Lisp, et tu
l'exécutes.

Oui, c'est possible. Pas forcément une bonne idée, mais possible.

En fait, ce genre de problème se résoud la plupart du temps en SQL.

<illumination mode="Je m'en étais pas rendu comtpe">
Tiens, c'est vrai...
</illumination>

Ce que tu as décris n'est rien d'autre qu'un join, en parlance
base de données.

Maintenant, s'il s'agit de manipuler des ensembles d'une dizaine
d'éléments, mettre en jeu toute une base de données, ce n'est
peut-être pas la solution la plus légère. (Mais s'il y a une
base déjà installée sur ta machine...)

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Le Sat, 16 Dec 2006 02:22:46 -0800, James Kanze a écrit:

Dans l'implémentation C++, je comptais me servir de tuples pour
stocker les combinaisons.
Par tuples, entends-tu boost::tuples, ou quelque chose maison ?

Je pensais à Boost, pour que les tuples soient typés. Sinon, si on
abandonne la typesafety, il y std::vector<boost::any>.

Il me semblait judicieux d'utiliser la structure la plus légère de
la STL pour stocker les tuples retenus, donc une liste doublement
chainée
Selon les opérations envisagées, vector ou deque pourrait être

nettement plus legers.

Instinctivement, j'évite vector quand je vais faire une tripotée d'ajout
sans savoir à l'avance la taille... Deque, par contre, serait bien.

(Ce sont deux questions qui ne se posent pas en Lisp, qui n'a
qu'une seule structure de données, la liste.)
Le LISP de 1958, peut-être. Mais j'utilise Common Lisp...

Qui en a ajouté des tableaux, etc. Mais la structure dynamique de base

en Lisp, c'est bien une liste.

Il y un fossé entre « structure dynamique de base » et « seule
structure ».

Mais je me posais la question de savoir si c'est réalisable de façon
générique.
À quel niveau ? Jusqu'au niveau des types dans les tuples ?

Oui

Générique résolue à l'exécution, ou lors de la compilation ?

À la compilation.

C'est là qu'on tombe sur des problèmes de type. Il faut écrire ici
un code capable de s'adapter à un nombre inconnu (éventuellement
borné) d'éléments dans les tuples qui vont être produits, de types
inconnus à l'avance.
Lors de l'exécution, s'entend.

Non, à la compilation. C'est déjà assez compliqué comme ça. ;-)

Je voudrais pouvoir l'utiliser ainsi :

TupleFactory<Client,Lot,Financement> tf1;

aussi bien que :

TupleFactory<int,int,double,float> tf2;

Mais il faudrait savoir lequel lors de l'écriture du programme.

Non, justement. Je voudrais que le même code puisse être appelé avec ces
deux déclarations. C'est là que la MPL entrait en action (et que je
déclarais forfait)...

Loin de moi l'idée de constuire un interpréteur Turing-complete pour
ça...
Même en C++, avec lex et yacc, ce n'est pas la fin du monde. Je le

fais souvent. Dans la mesure où le langage ne permet pas de structures
de boucles ou des sous-programmes, c'est ultra simple.

C'est vrai que je ne suis pas un habitué de ces outils.

Maintenant, s'il s'agit de manipuler des ensembles d'une dizaine
d'éléments, mettre en jeu toute une base de données, ce n'est
peut-être pas la solution la plus légère. (Mais s'il y a une base déjà
installée sur ta machine...)

Ça se discute, puisque les infos seront de toutes façon déjà dans une
base de données. Reste que je veux pouvoir exprimer des contraintes
arbitrairement complexes. D'un autre côté, Postgresql dispose d'un
PL/scheme, je devrais y trouver mon bonheur...

Prospectivement,
Pierre
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Pierre THIERRY wrote:

Le Sat, 16 Dec 2006 02:22:46 -0800, James Kanze a écrit:

Dans l'implémentation C++, je comptais me servir de tuples pour
stocker les combinaisons.
Par tuples, entends-tu boost::tuples, ou quelque chose maison ?

Je pensais à Boost, pour que les tuples soient typés. Sinon, si on
abandonne la typesafety, il y std::vector<boost::any>.

Le problème éventuel que je vois, c'est les tuples soient trop
statiques, et any trop ouvert. Mais tout dépend de
l'application.

Il me semblait judicieux d'utiliser la structure la plus légère de
la STL pour stocker les tuples retenus, donc une liste doublement
chainée
Selon les opérations envisagées, vector ou deque pourrait être

nettement plus legers.

Instinctivement, j'évite vector quand je vais faire une tripotée d'aj out
sans savoir à l'avance la taille... Deque, par contre, serait bien.

Je ne sais pas. Mon expérience, c'est que quand tous les ajoutes
se font à la fin, et que la copie de l'objet n'est pas trop
cher, vector est souvent plus rapide que deque.

Aussi, dans ton application, tu connais la taille d'avance, ou
au moins, tu peux le connaître. Pour les tuples, à partir du
programme, et pour le join, c'est le produit des nombres
d'éléments dans chaque ensemble qui y participe.

(Ce sont deux questions qui ne se posent pas en Lisp, qui n'a
qu'une seule structure de données, la liste.)
Le LISP de 1958, peut-être. Mais j'utilise Common Lisp...

Qui en a ajouté des tableaux, etc. Mais la structure dynamique de base

en Lisp, c'est bien une liste.

Il y un fossé entre « structure dynamique de base » et « seule
structure ».

Certes. Mais dans la contexte, je pensais à l'influence du
langage sur la structure choisie. Quand on travaille en Lisp, on
pense automatiquement en termes de listes -- au moins dans le
Lisp que je connais (elisp, d'emacs, et connaître, c'est
beaucoup dire), les autres structures dynamiques sont bien moins
souples.

Mais je me posais la question de savoir si c'est réalisable de fa çon
générique.
À quel niveau ? Jusqu'au niveau des types dans les tuples ?

Oui

Générique résolue à l'exécution, ou lors de la compilation ?

À la compilation.

Dans quel cas, boost::tuple est tout à fait indiqué.

C'est là qu'on tombe sur des problèmes de type. Il faut écrire ici
un code capable de s'adapter à un nombre inconnu (éventuellement
borné) d'éléments dans les tuples qui vont être produits, de types
inconnus à l'avance.
Lors de l'exécution, s'entend.

Non, à la compilation. C'est déjà assez compliqué comme ça. ;-)

Je voudrais pouvoir l'utiliser ainsi :

TupleFactory<Client,Lot,Financement> tf1;

aussi bien que :

TupleFactory<int,int,double,float> tf2;

Mais il faudrait savoir lequel lors de l'écriture du programme.

Non, justement. Je voudrais que le même code puisse être appelé ave c ces
deux déclarations. C'est là que la MPL entrait en action (et que je
déclarais forfait)...

Par même code, tu veux dire même code source, je suppose. Parce
que quelque soit la solution adoptée, le code final qui traite
tf2 ne pourrait pas être le même que celui qui traite tf1.

Loin de moi l'idée de constuire un interpréteur Turing-complete p our
ça...
Même en C++, avec lex et yacc, ce n'est pas la fin du monde. Je le

fais souvent. Dans la mesure où le langage ne permet pas de structures
de boucles ou des sous-programmes, c'est ultra simple.

C'est vrai que je ne suis pas un habitué de ces outils.

Ce sont des outils très puissants pour des problèmes bien
délimités. Surtout yacc : c'est le marteau pilon pour écraser
une mouche pour des langages très simple, et ce n'est pas assez
puissant pour les langages aussi complexe que le C++, mais entre
les deux, il y a beaucoup de langages où il s'adopte à
merveille. (Si tu veux apprendre le yacc, et aussi quelques
idées sur des interprêteurs simples, le meilleur texte que je
connais, c'est le chapitre 8 de « The Unix Programming
Environment », de Kernighan et Pike.)

Maintenant, s'il s'agit de manipuler des ensembles d'une dizaine
d'éléments, mettre en jeu toute une base de données, ce n'est
peut-être pas la solution la plus légère. (Mais s'il y a une base déjà
installée sur ta machine...)

Ça se discute, puisque les infos seront de toutes façon déjà dans une
base de données.

Si les infos sont de toutes façon déjà dans une base, c'est que
tu as une base installée sur la machine:-).

Reste que je veux pouvoir exprimer des contraintes
arbitrairement complexes.

Je ne connais pas assez le SQL pour te conseiller ici, mais
d'après certains scripts que j'ai vu au travail, on peut bien
exprimer des contraintes extrèmement complexes.

D'un autre côté, Postgresql dispose d'un
PL/scheme, je devrais y trouver mon bonheur...

Je crois que si on connaît le SQL, on peut y faire beaucoup.
J'ai l'impression, en revanche, qu'il égale le C++ non seulement
pour sa puissance (dans un autre domaine), mais aussi pour
l'élégance et la simplicité.

--
James Kanze (Gabi Software) email: james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Le 15-12-2006, Pierre THIERRY <nowhere.man@levallois.eu.org> a écrit :

C'est là qu'on tombe sur des problèmes de type. Il faut écrire ici un
code capable de s'adapter à un nombre inconnu (éventuellement borné)
d'éléments dans les tuples qui vont être produits, de types inconnus à
l'avance.

Je voudrais pouvoir l'utiliser ainsi :

TupleFactory<Client,Lot,Financement> tf1;

aussi bien que :

TupleFactory<int,int,double,float> tf2;

As-tu regardé les 'typelists' qu'Andrei Alexandrescu présente
dans 'Modern C++ design'. Ca me semble ressembler à ce que tu
cherches à faire (mais bon, je ne suis pas assez expert pour
savoir si ça tient la route pour ton problème).

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)