Recherche en deux phases : quid ?

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

| Dans un thread d'octobre, il y a eu une discussion sur l'implémentation
| de la recherche en deux phases. Est-ce que c'est le fait que le
| compilateur doit faire deux passes pour analyser le code, parce que C++
| n'est pas toujours LALR(1), ou est-ce autre chose ?

Je ne comprends pas le rapport entre la recherche en deux phases et
parsing.

-- Gaby

Pierre THIERRY wrote:

Dans un thread d'octobre, il y a eu une discussion sur
l'implémentation de la recherche en deux phases. Est-ce que
c'est le fait que le compilateur doit faire deux passes pour
analyser le code, parce que C++ n'est pas toujours LALR(1), ou
est-ce autre chose ?

C'est autre chose. Formellement, il ne concerne que la recherche
des noms (name lookup), et en tout cas, ne concerne que les
templates.

Grosso modo, dans un template, les symboles utilisateurs se
divisent deux catégories, les symboles dépendants, dont la
signification dépendent des paramètres du template, et les
symboles non-dépendants, dont la signification (le name binding,
c-à-d le lien que fait le compilateur entre le symbol et sa
déclaration) ne dépend pas des paramètres du template.

La signification des symboles non-dépendants est fixé une fois
pour tout par le compilateur, quand il voit le code du template.
Si le compilateur ne peut pas trouver une déclaration qui
convient, c'est une erreur, même s'il y en a une dans la
contexte d'instantiation. La recherche de la déclaration se fait
d'une façon tout à fait normal.

L'évaluation de la signification des symboles dépendants est
différée jusqu'à l'instantiation, et la récherche de la
déclaration correspondante suit des règles un peu spéciales :
dans la contexte de la définition du template, mais en ne
considérant que les déclarations révélées par le récherche
dépendant des paramètres, et dans la contexte de
l'instantiation.

C'est le compilateur qui décide quels symboles sont dépendant,
et quels non, selon des règles assez obscures. Ce qui fait une
jolie devinette pour le programmeur.

Historiquement, la plupart des compilateurs ont commencé par
évaluer un template uniquement dans la contexte de
l'instantiation. (Taligent en était une exception, peut-être.)
Ce qui a l'avantage de la simplicité, si rien d'autre -- ça
présente certains dangers, mais au moins, on comprend ce qu'on
fait. Mais la véritable problème aujourd'hui, c'est que très peu
de compilateurs sont réelement conforme, ce qui fait qu'entre
deux compilateurs, il y a de fortes chances qu'ils implémentent
des règles différemment.

--
James Kanze GABI Software
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, 12 May 2005 06:50:22 +0200, Gabriel Dos Reis a écrit :

Je ne comprends pas le rapport entre la recherche en deux phases et
parsing.

Normal, il n'y en a visiblement aucun. Je n'ai pas trouvé ce qu'était la
recherche en deux phases, je demandais ce que c'est. Je me suis demandé
si c'était une autre formule pour analyse en deux passes...

Brièvement,
Nowhere man
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Historiquement, la plupart des compilateurs ont commencé par
évaluer un template uniquement dans la contexte de
l'instantiation. (Taligent en était une exception, peut-être.)
Ce qui a l'avantage de la simplicité, si rien d'autre -- ça
présente certains dangers, mais au moins, on comprend ce qu'on
fait. Mais la véritable problème aujourd'hui, c'est que très peu
de compilateurs sont réelement conforme, ce qui fait qu'entre
deux compilateurs, il y a de fortes chances qu'ils implémentent
des règles différemment.

Le deuxième problème étant qu'il y a beaucoup de code existant qui
ne compile plus avec le 2 phases-lookup, ce qui fait que certains
implémenteurs ne sont pas forcémenr très pressés de
l'implémenter....

Arnaud

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

| Le Thu, 12 May 2005 06:50:22 +0200, Gabriel Dos Reis a écrit :
| > Je ne comprends pas le rapport entre la recherche en deux phases et
| > parsing.
|
| Normal, il n'y en a visiblement aucun. Je n'ai pas trouvé ce qu'était la
| recherche en deux phases, je demandais ce que c'est. Je me suis demandé
| si c'était une autre formule pour analyse en deux passes...

Pour reprendre une suggestion faite récemment, peut-être était-ce la
formulation. J'ai voulu voir ce que cela donnait. Toujours en voulant
tester certaines de ces suggestions

La règle me semble l'algorithme récursif suivant :

- faire une recherche par soi-même sur le problème rencontré (sur les
moteurs de recherche, avec comme mots-clefs l'erreur rencontrée, par
exemple) ou sur le sujet abordé (sur les moteurs de recherche ou dans
les catalogues de bibliothèques, avec comme mots-clefs les noms des
concepts),
- lire attentivement les documents trouvés, et s'il reste des zones
d'ombre, poser des questions ciblées,
- si l'on ne trouve pas, ou trop peu de choses, expliquer comment on a
cherché et demander des pistes,
- avec les pistes, reprendre au début.

On peut aussi, quand on a glané des références, demander ce qu'elles
valent avant de se lancer dans ses lectures.

J'ai fait une simple recherche de « two phase name lookup » avec
Google et dans les premières réponses, j'ai

http://womble.decadentplace.org.uk/c++/template-faq.html

question 6.

-- Gaby

kanze@gabi-soft.fr writes:

[...]

| C'est le compilateur qui décide quels symboles sont dépendant,

Les règles qui définissent ce qui est dépendent ou non sont aussi
fixées et décrites dans la définition de C++.

| et quels non, selon des règles assez obscures. Ce qui fait une
| jolie devinette pour le programmeur.
|
| Historiquement, la plupart des compilateurs ont commencé par
| évaluer un template uniquement dans la contexte de
| l'instantiation. (Taligent en était une exception, peut-être.)
| Ce qui a l'avantage de la simplicité, si rien d'autre -- ça
| présente certains dangers, mais au moins, on comprend ce qu'on
| fait. Mais la véritable problème aujourd'hui, c'est que très peu
| de compilateurs sont réelement conforme, ce qui fait qu'entre

Aujourd'hui, j'ai vu très peu d'écarts.

-- Gaby

Le Thu, 12 May 2005 05:20:13 -0700, adebaene a écrit :

Le deuxième problème étant qu'il y a beaucoup de code existant qui ne
compile plus avec le 2 phases-lookup,

Quel type de code va échouer ?

Curieusemenent,
Nowhere man
--
nowhere.man@levallois.eu.org
OpenPGP 0xD9D50D8A

Pierre THIERRY wrote:

Le deuxième problème étant qu'il y a beaucoup de code existant
qui ne

compile plus avec le 2 phases-lookup,

Quel type de code va échouer ?

L'exemple type :

template< typename T >
struct S : public T
{
void f() { g() ; }
} ;

où g() est (ou doit être) une fonction de la classe de base.

S'il n'y a pas de fonction g() disponible globalement, lors de
la définition de S, il y aura une erreur à la compilation.

S'il y a une fonction g() disponible globalement, lors de la
définition de S, c'est elle qui sera appelée, plutôt que celle
de la classe de base.

Mais il y en a plein d'autres.

--
James Kanze GABI Software
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 Fri, 13 May 2005 08:33:40 -0700, kanze a écrit :

L'exemple type :

template< typename T >
struct S : public T
{
void f() { g() ; }
} ;

où g() est (ou doit être) une fonction de la classe de base.

S'il n'y a pas de fonction g() disponible globalement, lors de
la définition de S, il y aura une erreur à la compilation.

C'est censé échouer avec quels compilos ? Il me semble que ça marche
avec GCC (3.3.5).

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

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

| Le Fri, 13 May 2005 08:33:40 -0700, kanze a écrit :
| > L'exemple type :
| >
| > template< typename T >
| > struct S : public T
| > {
| > void f() { g() ; }
| > } ;
| >
| > où g() est (ou doit être) une fonction de la classe de base.
| >
| > S'il n'y a pas de fonction g() disponible globalement, lors de
| > la définition de S, il y aura une erreur à la compilation.
|
| C'est censé échouer avec quels compilos ?

qui documentent qu'ils implémentent la recherche de noms en deux phases.

| Il me semble que ça marche avec GCC (3.3.5).

mais GCC-3.x avec x < 4 n'est pas documenté implémenter la recherche
de noms en deux phases (quite the contrary). Essaie GCC-3.4.x ou GCC-4.0.x

-- Gaby