Probleme de metacompilation

"Benjamin Dauvergne" <benjamin.dauvergne@gmail.com> a écrit dans le message
de news: 1127903874.788604.131770@f14g2000cwb.googlegroups.com...

Bonjour,

Je m'essaye a l'utilisation des templates pour gerer des structures de
donnee a compile time.
J'ai decide de commencer par la base et de me creer une structure de
list a base de cons.
class Nil {};
template <class A, class B> struct Cons {
typedef A head_t;
typedef B tail_t;
const A head;
const B tail;
Cons(const A &a, const B &b) : head(a), tail(b) {}
};

Si cela représente la structure d'une liste,
pourquoi head_t et tail_t auraient un type différent ?
De plus, ils sont supposés se modifier au cours le
la vie de la liste : pourquoi sont-ils const ?

Tu peux simplifier l'écriture :

template <typename T> struct Cons {
T head;
T tail;
Cons(const T &h, const T &t) : head(h), tail(t) {}
};

Mais il est conseillé d'implémenter son
code avec un type défini, puis lorsque tout
fonctionne, le transformer en modèle.

--
-Stan

Benjamin Dauvergne wrote:

template <typename A, typename B, typename C>
struct Reverse_t<Cons<A,B>, C> {
typedef Reverse_t<B, Cons<A, C> >::type; // ligne 66
};

Quel type est défini comme étant équivalent à quel type ? Là, tel que je
le lis, Reverse_t<B, Cons<A,C> >::type est un type, et il manque ensuite
le nom du type défini par typedef.

Par ailleurs, je ne suis pas trop au fait de la métacompilation (je n'ai
jamais pratiqué). Mais il me semble qu'une bonne convention pour une «
métafonction » est de définir son résultat comme un type « result ».

Enfin, J'ai du mal à comprendre pourquoi il y a trois arguments à
Reverse_t. Moi, sauf si je n'ai rien compris, j'aurais plutôt écrit
quelque chose comme :

template <typename L>
struct Reverse_t {
typedef Cons< Reverse_t<L::tail_t>, L::head_t> > result;
};

template <typename L>
struct Reverse_t<Nil> {
typedef Nil result;
};

Cons est habituellement plutôt un opérateur fonctionnel, et devrait à
mon avis utiliser une sémantique de fonction avec un type result. Et
j'appellerais plutôt List le type liste. Mais ce n'est qu'une convention
de nommage. Il faut aussi définir ce qui se passe lorsqu'on construit
une liste avec Nil :

template <typename BA, typename BB>
struct Cons<Nil, Cons<BA,BB> > {
typedef BA head_t;
typedef BB tail_t;
};

Enfin, je ne vois pas à quoi est censé servir le constructeur de Cons.
On raisonne ici sur des types, et non pas sur des objets.

Est-qu'un eminent meta-programmeur pourrait m'indiquer la solution a
cet epineux(en tout cas pour moi;)) probleme ?

Je suis loin d'être un éminent méta-programmeur. Il se pourrait donc qu
j'aie dit des bétises. Les spécialistes auront à coeur de rectifier mes
erreurs.

--
Arnaud

"Benjamin Dauvergne" <benjamin.dauvergne@gmail.com> a écrit dans le mes sage
de news: 1127903874.788604.131770@f14g2000cwb.googlegroups.com...

Bonjour,

Je m'essaye a l'utilisation des templates pour gerer des structures de
donnee a compile time.
J'ai decide de commencer par la base et de me creer une structure de
list a base de cons.
class Nil {};
template <class A, class B> struct Cons {
typedef A head_t;
typedef B tail_t;
const A head;
const B tail;
Cons(const A &a, const B &b) : head(a), tail(b) {}
};

Si cela représente la structure d'une liste,
pourquoi head_t et tail_t auraient un type différent ?
Je souhaite une liste polymorphe comme en lisp (les elements

peuvent etre tous de type differents) mais statique, i.e une fois
declarer literalment le type total est connu.

De plus, ils sont supposés se modifier au cours le
la vie de la liste : pourquoi sont-ils const ?
La non, en fait je veux representer l'AST d'un bloc d'expression,

chaque
element de la liste serait une expression differente donc un type
different.
Et j'ai besoin d'operation comme reverse ou last_elt car je veux
reordonne
mes expressions (je travaille sur une transformation de code et je ne
connais
pas de frontend c++ potable et facilement bidouillable (g++ est affreux
meme si ca marche bien)).

Tu peux simplifier l'écriture :

template <typename T> struct Cons {
T head;
T tail;
Cons(const T &h, const T &t) : head(h), tail(t) {}
};
Non ca n'est pas ce que je veux faire.

Mais il est conseillé d'implémenter son
code avec un type défini, puis lorsque tout
fonctionne, le transformer en modèle.
Je sais tres bien ecrire le code sans template, ca n'est pas le

probleme:

List *reverse(List *l) {
return reverseRec(l, 0);
}

List *reverseRec(List *l, List *rest) {
if (l)
{
List *tail = l->tail;
l->tail = rest;
return reverse0(tail, l);
}
return rest;
}

A+

Benjamin Dauvergne wrote:

template <typename A, typename B, typename C>
struct Reverse_t<Cons<A,B>, C> {
typedef Reverse_t<B, Cons<A, C> >::type; // ligne 66
};

Quel type est défini comme étant équivalent à quel type ? Là, t el que je
le lis, Reverse_t<B, Cons<A,C> >::type est un type, et il manque ensuite
le nom du type défini par typedef.
Dsl grosse typo, le :: est de trop:

template <typename A, typename B, typename C>
struct Reverse_t<Cons<A,B>, C> {
typedef Reverse_t<B, Cons<A, C> > type; // ligne 66
};

Par ailleurs, je ne suis pas trop au fait de la métacompilation (je n'ai
jamais pratiqué). Mais il me semble qu'une bonne convention pour une «
métafonction » est de définir son résultat comme un type « resu lt ».
C'est note.

Enfin, J'ai du mal à comprendre pourquoi il y a trois arguments à
Reverse_t. Moi, sauf si je n'ai rien compris, j'aurais plutôt écrit
quelque chose comme :

template <typename L>
struct Reverse_t {
typedef Cons< Reverse_t<L::tail_t>, L::head_t> > result;
};
Parce qu'alors ce n'est plus une liste mais un arbre (les contraintes

sont assouplies quand au role de head et tail) je ne sais pas si
c'est reellement un probleme pour l'utilisation que je vais en faire,
mais ca n'etait pas mon but de generaliser mes structures.

Cons est habituellement plutôt un opérateur fonctionnel, et devrait à
mon avis utiliser une sémantique de fonction avec un type result. Et
j'appellerais plutôt List le type liste. Mais ce n'est qu'une convention
de nommage. Il faut aussi définir ce qui se passe lorsqu'on construit
une liste avec Nil :

template <typename BA, typename BB>
struct Cons<Nil, Cons<BA,BB> > {
typedef BA head_t;
typedef BB tail_t;
};

Enfin, je ne vois pas à quoi est censé servir le constructeur de Cons.
On raisonne ici sur des types, et non pas sur des objets.
Le but est de pouvoir des fonctions sur des objets donc je ne connais

pas a priori le type, les templates sont la pour m'en calculer les
types (par
exemple le type retour de ma fonctione Reverse statique), le but etant
d'obtenir un arbe d'appels type statiquement que le compilo puisse
totalement inline.

Je suis loin d'être un éminent méta-programmeur. Il se pourrait don c qu
j'aie dit des bétises. Les spécialistes auront à coeur de rectifier mes
erreurs.
Je pense que nivo meta-programmation il n'y a pas de betise mais tu

n'as pas resolu mon probleme.

A+

"Benjamin Dauvergne" <benjamin.dauvergne@gmail.com> écrivait:

Est-qu'un eminent meta-programmeur pourrait m'indiquer la solution a
cet epineux(en tout cas pour moi;)) probleme ?

Si tu nous donnais un exemple minimal *compilable* ?
--
Franck Branjonneau <fasbjx@free.fr>

Benjamin Dauvergne wrote:

...
Je pense que nivo meta-programmation il n'y a pas de betise mais tu
n'as pas resolu mon probleme.

effectivement, tu veux obtenir une liste toujours formée
suivant (a, (b)) et ne jamais avoir qqch comme ((a), b)
où l'ouverture d'une parenthèse correspond à un Cons.

donc :


1. le type bouchon

struct nil {};


2. la structure de liste :

template <class elt, class next = nil>
struct cons;

// non singleton:
template <class elt, class next> // ici next ne vaut pas nil
struct cons {
// du code
};


// singleton:
template <class elt>
struct cons <elt> {
// là du code différent car pas de next
};


en définissant ainsi le type cons (avec la valeur par défaut et
les spécialisation), tu écris de façon transparente cons<int>
quand ta liste est un singleton et ça te permet de spécialiser
le code.

pour être sûr de ne pas se retrouver avec un type mal formé, il
vaut mieux se blinder et interdire les types suivants :

template <typename a>
struct cons<nil, a>; // le bouchon ne peut pas être en tête
// et cons<nil> aussi est interdit

template <typename a, typename b, typename c>
struct cons<cons<a,b>, c>; // les cons ne peuvent être qu'en queue


2. une méta-fonction utile (ajout d'un élément dans une liste...)

template <typename list, typename new_elt>
struct push;

template <typename new_elt>
struct push < nil, new_elt > // cas particulier de la creation
// d'un singleton
{
typedef cons<new_elt> ret;
};

template <typename elt, typename next, typename new_elt>
struct push < cons<elt, next>, new_elt > // cas général
{
typedef cons<elt, typename push<next, new_elt>::ret> ret;
};


3. on peut enfin songer à reverse

template <typename list>
struct reverse;

template <typename elt>
struct reverse < cons<elt> > { // cas du singleton
typedef cons<elt> ret;
};

template <typename elt, typename next>
struct reverse < cons<elt, next> > { // cas général
typedef typename push<typename reverse<next>::ret, elt>::ret ret;
};

pour que la liste soit bien formée, on doit *pousser* le premier
élément en fin de liste


4. on vérifie expérimentalement

int main()
{
typedef cons<double, cons<float, cons<int> > > test;
reverse<test>::ret tmp;
}

avec un compilateur qui donne des alertes, on obtient un message
qui signale que tmp est inutilisé et qui précise son type :
cons<int, cons<float, cons<double, nil> > >
on est content :)

maintenant, tu n'as "plus-qu'à" modifier ce méta-code pour
gérer les valeurs de tes éléments


théo
--
http://www.lrde.epita.fr/people/theo

Merci beaucoup ;) Je pense que je viens de gagner 1 niveau en proprete
de meta-code ;-)