miracle de la récursion

Gabriel Dos Reis

16/12/2003 à 01:47

"Alain Naigeon" writes:

| "Gabriel Dos Reis" a écrit dans le message
| news:
| > Loïc Joly writes:
| >
| > | wrote:
| > |
| > | <Mode chipotage>
| > | > Pourquoi pas simplement : une fonction F() est dite récursive si elle
| > | > contient un appel à elle-même, que cet appel soit direct ou indirect.
| > |
| > | La fonction suivante est-elle récursive ?
| > |
| > | void f()
| > | {
| > | if (false)
| > | {
| > | f();
| > | }
| > | }
| >
| > Oui.
|
| Euh... c'est juste syntaxique, la récursivité ?

et surtout lexicale.

Plus généralement, est-ce que

extern bool some_test();

void f() { if (some_test()) f(); }

est un appel récursif ?

La réponse, comme celle donnée avant est oui.

| Je trouve l'exemple astucieux et intéressant, mais c'est

ça dépend, je trouve que l'exemple montre peu de familiarité avec la
récursivité et la théorie des langages ;-)

| peut-être une question sur ce que doit ou peut être
| une optimisation...
| Dans un tel cas où tu peux prouver que les circonstances
| d'un deuxième appel sont l'ensemble vide, tu maintiens
| ton oui ?

Si, lexicalement, il y a appel à f(), alors il y a récursivité, même
si dynamiquement cet appel n'a pas lieu.

Pour comprendre ce qui se passe, il faut bien se placer dans un cadre
un peu plus général -- je devrais peut être juste donner un lien sur
Caml ou quelque chose de ce genre (ils doivent l'expliquer quelque
part).

Une entité est récursive si sa définition contient une référence à
elle-même. Ainsi

struct list {
int data;
list* link;
};

est récursif (via le pointeur), ou le f() de Loic.

void* p = &p;

ou

unsigned char c = c;

sont des défintions récursives.

const int x = 4;
void g()
{
enum { x = x } ; // non récursif
}

Le point est qu'il suffit que l'entité soit *lexicalement* référencée
dans sa propre définition. Ce n'est nullement du chipotage.

Considére un langage où un nom ne peut être utilisé que si un binding
(i.e. une association entre ce nom et l'entité qu'il désigne) a été
préalablement établi. Ce qui semble relever du bon sens : si j'utilise
un nom quelque part, je sais exactement ce qu'il désigne et je peux
donner la valeur de ce qu'il désigne.

Eh bin, dans un tel langage il n'est pas possible de définir une
fonction comme

let f x = if (true) true else f(x - 1);

La raison est toute simple : la validité d'une expression est
lexicale.

dans

if (true) true else f(x - 1);

on ne sait pas ce que désigne « f » -- puisqu'on ne lui a pas encore
établi de binding. Note bien qu'ici la seule présence (lexicale) de f fout
tout en l'air.

Pour arriver à faire de la recursivité, il faut un opérateur de point
fixe[1]. Par exemple, « rec » est l'opérateur de point fixe pour les
fonctions dans (O)Caml.

let rec f x = if (true) true else f(x - 1);

C++ par exemple, a beaucoup des opérateurs de point fix pour beaucoup
de choses, saus les enumérations et les cas où une classe doit être
complète.

[1] un opérateur de point fixe Fix est un opérateur qui satisfait
l'équation

Fix(f) = f(Fix(f)) pour tout f.

-- Gaby

"Alain Naigeon" <anaigeon@free.fr> writes:

| "Gabriel Dos Reis" <gdr@integrable-solutions.net> a écrit dans le message
| news: m3r7z5bywm.fsf@uniton.integrable-solutions.net...
| > Loïc Joly <loic.actarus.joly@wanadoo.fr> writes:
| >
| > | kanze@gabi-soft.fr wrote:
| > |
| > | <Mode chipotage>
| > | > Pourquoi pas simplement : une fonction F() est dite récursive si elle
| > | > contient un appel à elle-même, que cet appel soit direct ou indirect.
| > |
| > | La fonction suivante est-elle récursive ?
| > |
| > | void f()
| > | {
| > | if (false)
| > | {
| > | f();
| > | }
| > | }
| >
| > Oui.
|
| Euh... c'est juste syntaxique, la récursivité ?

et surtout lexicale.

Plus généralement, est-ce que

extern bool some_test();

void f() { if (some_test()) f(); }

est un appel récursif ?

La réponse, comme celle donnée avant est oui.

| Je trouve l'exemple astucieux et intéressant, mais c'est

ça dépend, je trouve que l'exemple montre peu de familiarité avec la
récursivité et la théorie des langages ;-)

| peut-être une question sur ce que doit ou peut être
| une optimisation...
| Dans un tel cas où tu peux prouver que les circonstances
| d'un deuxième appel sont l'ensemble vide, tu maintiens
| ton oui ?

Si, lexicalement, il y a appel à f(), alors il y a récursivité, même
si dynamiquement cet appel n'a pas lieu.

Pour comprendre ce qui se passe, il faut bien se placer dans un cadre
un peu plus général -- je devrais peut être juste donner un lien sur
Caml ou quelque chose de ce genre (ils doivent l'expliquer quelque
part).

Une entité est récursive si sa définition contient une référence à
elle-même. Ainsi

struct list {
int data;
list* link;
};

est récursif (via le pointeur), ou le f() de Loic.

void* p = &p;

ou

unsigned char c = c;

sont des défintions récursives.

const int x = 4;
void g()
{
enum { x = x } ; // non récursif
}

Le point est qu'il suffit que l'entité soit *lexicalement* référencée
dans sa propre définition. Ce n'est nullement du chipotage.

Considére un langage où un nom ne peut être utilisé que si un binding
(i.e. une association entre ce nom et l'entité qu'il désigne) a été
préalablement établi. Ce qui semble relever du bon sens : si j'utilise
un nom quelque part, je sais exactement ce qu'il désigne et je peux
donner la valeur de ce qu'il désigne.

Eh bin, dans un tel langage il n'est pas possible de définir une
fonction comme

let f x = if (true) true else f(x - 1);

La raison est toute simple : la validité d'une expression est
lexicale.

dans

if (true) true else f(x - 1);

on ne sait pas ce que désigne « f » -- puisqu'on ne lui a pas encore
établi de binding. Note bien qu'ici la seule présence (lexicale) de f fout
tout en l'air.

Pour arriver à faire de la recursivité, il faut un opérateur de point
fixe[1]. Par exemple, « rec » est l'opérateur de point fixe pour les
fonctions dans (O)Caml.

let rec f x = if (true) true else f(x - 1);

C++ par exemple, a beaucoup des opérateurs de point fix pour beaucoup
de choses, saus les enumérations et les cas où une classe doit être
complète.

[1] un opérateur de point fixe Fix est un opérateur qui satisfait
l'équation

Fix(f) = f(Fix(f)) pour tout f.

-- Gaby

Vous avez filtré cet utilisateur ! Consultez son message

"Alain Naigeon" writes:

| "Gabriel Dos Reis" a écrit dans le message
| news:
| > Loïc Joly writes:
| >
| > | wrote:
| > |
| > | <Mode chipotage>
| > | > Pourquoi pas simplement : une fonction F() est dite récursive si elle
| > | > contient un appel à elle-même, que cet appel soit direct ou indirect.
| > |
| > | La fonction suivante est-elle récursive ?
| > |
| > | void f()
| > | {
| > | if (false)
| > | {
| > | f();
| > | }
| > | }
| >
| > Oui.
|
| Euh... c'est juste syntaxique, la récursivité ?

et surtout lexicale.

Plus généralement, est-ce que

extern bool some_test();

void f() { if (some_test()) f(); }

est un appel récursif ?

La réponse, comme celle donnée avant est oui.

| Je trouve l'exemple astucieux et intéressant, mais c'est

ça dépend, je trouve que l'exemple montre peu de familiarité avec la
récursivité et la théorie des langages ;-)

| peut-être une question sur ce que doit ou peut être
| une optimisation...
| Dans un tel cas où tu peux prouver que les circonstances
| d'un deuxième appel sont l'ensemble vide, tu maintiens
| ton oui ?

Si, lexicalement, il y a appel à f(), alors il y a récursivité, même
si dynamiquement cet appel n'a pas lieu.

Pour comprendre ce qui se passe, il faut bien se placer dans un cadre
un peu plus général -- je devrais peut être juste donner un lien sur
Caml ou quelque chose de ce genre (ils doivent l'expliquer quelque
part).

Une entité est récursive si sa définition contient une référence à
elle-même. Ainsi

struct list {
int data;
list* link;
};

est récursif (via le pointeur), ou le f() de Loic.

void* p = &p;

ou

unsigned char c = c;

sont des défintions récursives.

const int x = 4;
void g()
{
enum { x = x } ; // non récursif
}

Le point est qu'il suffit que l'entité soit *lexicalement* référencée
dans sa propre définition. Ce n'est nullement du chipotage.

Considére un langage où un nom ne peut être utilisé que si un binding
(i.e. une association entre ce nom et l'entité qu'il désigne) a été
préalablement établi. Ce qui semble relever du bon sens : si j'utilise
un nom quelque part, je sais exactement ce qu'il désigne et je peux
donner la valeur de ce qu'il désigne.

Eh bin, dans un tel langage il n'est pas possible de définir une
fonction comme

let f x = if (true) true else f(x - 1);

La raison est toute simple : la validité d'une expression est
lexicale.

dans

if (true) true else f(x - 1);

on ne sait pas ce que désigne « f » -- puisqu'on ne lui a pas encore
établi de binding. Note bien qu'ici la seule présence (lexicale) de f fout
tout en l'air.

Pour arriver à faire de la recursivité, il faut un opérateur de point
fixe[1]. Par exemple, « rec » est l'opérateur de point fixe pour les
fonctions dans (O)Caml.

let rec f x = if (true) true else f(x - 1);

C++ par exemple, a beaucoup des opérateurs de point fix pour beaucoup
de choses, saus les enumérations et les cas où une classe doit être
complète.

[1] un opérateur de point fixe Fix est un opérateur qui satisfait
l'équation

Fix(f) = f(Fix(f)) pour tout f.

-- Gaby

kanze

16/12/2003 à 11:20

Gabriel Dos Reis wrote in message
news:...

writes:
[...]

| Quelqu'un m'a racconté aussi un essai de ce genre sur un compilateur
| C. D'après ce que j'ai compris, il y avait quelque chose qui le
| rendait moins faisable, mais j'avoue ne pas pouvoir trouver ce que
| c'était.

Je serai bien curieux de savoir quoi.

Moi aussi. C'était une article que j'ai vu je ne me souviens plus où, et
à un moment où je n'avais que le temps de le survoler rapidement. Je
sais que le problème avait quelque chose à faire avec la durée de vie
des variables (en C -- donc, pas d'histoire en ce qui concerne quand on
appelle le destructeur, etc.).

Ça m'énerve de ne pas en souvenir de plus, parce qu'actuellement, je ne
vois aucun problème, au moins dans les cas simples. Alors, ou bien, il y
a une chose que je ne vois pas (fort possible, vue depuis combien de
temps je ne fais plus de compilateur), ou bien, il s'est gouré lui-même.

S'il est vrai que traditionnellement, les compilateurs C
implémentaient rarement l'optimisation de recrusivité finale, ils
commencent maintenant à offrir cette optimisation. GCC/gcc, depuis un
bon bout de temps (depuis EGCS au moins), en offrait une. Une version
plus élaborée existe dans GCC-3.x/gcc. Une version envore plus
élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc, peu importe comment il
sera appelé).

Je suis content de l'apprendre. Il faut dire que souvent dans de tels
cas, on a un problème de la poule et de l'oeuf : les compilatateurs ne
font pas l'optimisation, parce que ce type de code est rare dans les
programmes réels (dans le langage considéré), et ce type de code est
rare, parce que les compilateurs ne l'optimisent pas bien.

Cependant, c'est un peu plus dur à faire correctement pour C++ à cause
de la sémantique des destructreurs.

C'est effectivement un problème. A priori, pas insurmontable, mais quand
même loin d'être trivial.

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

Gabriel Dos Reis <gdr@integrable-solutions.net> wrote in message
news:<m365gidmct.fsf@uniton.integrable-solutions.net>...

kanze@gabi-soft.fr writes:
[...]

| Quelqu'un m'a racconté aussi un essai de ce genre sur un compilateur
| C. D'après ce que j'ai compris, il y avait quelque chose qui le
| rendait moins faisable, mais j'avoue ne pas pouvoir trouver ce que
| c'était.

Je serai bien curieux de savoir quoi.

Moi aussi. C'était une article que j'ai vu je ne me souviens plus où, et
à un moment où je n'avais que le temps de le survoler rapidement. Je
sais que le problème avait quelque chose à faire avec la durée de vie
des variables (en C -- donc, pas d'histoire en ce qui concerne quand on
appelle le destructeur, etc.).

Ça m'énerve de ne pas en souvenir de plus, parce qu'actuellement, je ne
vois aucun problème, au moins dans les cas simples. Alors, ou bien, il y
a une chose que je ne vois pas (fort possible, vue depuis combien de
temps je ne fais plus de compilateur), ou bien, il s'est gouré lui-même.

S'il est vrai que traditionnellement, les compilateurs C
implémentaient rarement l'optimisation de recrusivité finale, ils
commencent maintenant à offrir cette optimisation. GCC/gcc, depuis un
bon bout de temps (depuis EGCS au moins), en offrait une. Une version
plus élaborée existe dans GCC-3.x/gcc. Une version envore plus
élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc, peu importe comment il
sera appelé).

Je suis content de l'apprendre. Il faut dire que souvent dans de tels
cas, on a un problème de la poule et de l'oeuf : les compilatateurs ne
font pas l'optimisation, parce que ce type de code est rare dans les
programmes réels (dans le langage considéré), et ce type de code est
rare, parce que les compilateurs ne l'optimisent pas bien.

Cependant, c'est un peu plus dur à faire correctement pour C++ à cause
de la sémantique des destructreurs.

C'est effectivement un problème. A priori, pas insurmontable, mais quand
même loin d'être trivial.

--
James Kanze GABI Software mailto:kanze@gabi-soft.fr
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

Vous avez filtré cet utilisateur ! Consultez son message

Gabriel Dos Reis wrote in message
news:...

writes:
[...]

| Quelqu'un m'a racconté aussi un essai de ce genre sur un compilateur
| C. D'après ce que j'ai compris, il y avait quelque chose qui le
| rendait moins faisable, mais j'avoue ne pas pouvoir trouver ce que
| c'était.

Je serai bien curieux de savoir quoi.

Moi aussi. C'était une article que j'ai vu je ne me souviens plus où, et
à un moment où je n'avais que le temps de le survoler rapidement. Je
sais que le problème avait quelque chose à faire avec la durée de vie
des variables (en C -- donc, pas d'histoire en ce qui concerne quand on
appelle le destructeur, etc.).

Ça m'énerve de ne pas en souvenir de plus, parce qu'actuellement, je ne
vois aucun problème, au moins dans les cas simples. Alors, ou bien, il y
a une chose que je ne vois pas (fort possible, vue depuis combien de
temps je ne fais plus de compilateur), ou bien, il s'est gouré lui-même.

S'il est vrai que traditionnellement, les compilateurs C
implémentaient rarement l'optimisation de recrusivité finale, ils
commencent maintenant à offrir cette optimisation. GCC/gcc, depuis un
bon bout de temps (depuis EGCS au moins), en offrait une. Une version
plus élaborée existe dans GCC-3.x/gcc. Une version envore plus
élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc, peu importe comment il
sera appelé).

Je suis content de l'apprendre. Il faut dire que souvent dans de tels
cas, on a un problème de la poule et de l'oeuf : les compilatateurs ne
font pas l'optimisation, parce que ce type de code est rare dans les
programmes réels (dans le langage considéré), et ce type de code est
rare, parce que les compilateurs ne l'optimisent pas bien.

Cependant, c'est un peu plus dur à faire correctement pour C++ à cause
de la sémantique des destructreurs.

C'est effectivement un problème. A priori, pas insurmontable, mais quand
même loin d'être trivial.

--
James Kanze GABI Software mailto:
Conseils en informatique orientée objet/ http://www.gabi-soft.fr
Beratung in objektorientierter Datenverarbeitung
11 rue de Rambouillet, 78460 Chevreuse, France, +33 (0)1 30 23 45 16

Gabriel Dos Reis

16/12/2003 à 11:24

writes:

| > S'il est vrai que traditionnellement, les compilateurs C
| > implémentaient rarement l'optimisation de recrusivité finale, ils
| > commencent maintenant à offrir cette optimisation. GCC/gcc, depuis un
| > bon bout de temps (depuis EGCS au moins), en offrait une. Une version
| > plus élaborée existe dans GCC-3.x/gcc. Une version envore plus
| > élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc, peu importe comment il
| > sera appelé).
|
| Je suis content de l'apprendre. Il faut dire que souvent dans de tels
| cas, on a un problème de la poule et de l'oeuf : les compilatateurs ne
| font pas l'optimisation, parce que ce type de code est rare dans les
| programmes réels (dans le langage considéré), et ce type de code est
| rare, parce que les compilateurs ne l'optimisent pas bien.

En effet. Mais, de nos jours, les compilateurs C partagent le
middle-end et les back-end avec d'autres langages pour lesquelles ces
optimisations sont essentielles, sinon bienvenues. Aussi, il me semble
qu'il y a un mouvement de fond pour aller vers un peu plus
d'abstraction, alors même en C, on voit de plus en plus d'algorithmes
implémentés en récursif parce que
(1) c'est plus facile de prouver que l'implémentation est correcte ;
(2) des fois, c'est plus facile à maintenir.

Et aussi, il faut du temps pour les transferts de technologie -- comme
ils disent dans les département marcketing.

-- Gaby

Pierre Maurette

16/12/2003 à 11:40

"Loïc Joly" a écrit dans le message de news:
brl5u5$osq$

wrote:

<Mode chipotage>

Pourquoi pas simplement : une fonction F() est dite récursive si elle
contient un appel à elle-même, que cet appel soit direct ou indirect.

La fonction suivante est-elle récursive ?

void f()
{
if (false)
{
f();
}
}
Les diptères ont mal au cucu ....

Pierre

Michel Michaud

16/12/2003 à 22:40

Dans news:, Gabriel Dos

writes:
S'il est vrai que traditionnellement, les compilateurs C
implémentaient rarement l'optimisation de recrusivité finale, ils
commencent maintenant à offrir cette optimisation.
GCC/gcc, depuis un bon bout de temps (depuis EGCS au moins), en
offrait une. Une version plus élaborée existe dans GCC-3.x/gcc. Une
version envore plus élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc,
peu importe comment il sera appelé).

J'ose une question : est-ce vraiment important ou utile cette
optimisation ? N'y a-t-il pas des choses plus importantes qui
manquent dans gcc (ou g++) ? Il me semble que si le compilateur
peut optimiser du code ordinaire, il pourra optimiser du code
où j'aurais enlevé explicitement la récursivité (en tout ou en
partie) et obtenir un résultat meilleur que l'optimisation
complète de la récursivité qu'il aurait pu faire. J'ai peut-être
une mauvaise idée des endroits où la récursivité est utile, mais
il me semble qu'annoncer de l'optimisation de la récursivité par
le compilateur, c'est un peu prendre la chance que les gens
codent récursivement ce qui n'a pas besoin d'être récursif en
pensant faire mieux que la version non récursive...

--
Michel Michaud
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/

Michel Michaud

16/12/2003 à 22:59

Dans news:, Gabriel Dos

writes:
Je suis content de l'apprendre. Il faut dire que souvent dans de
tels cas, on a un problème de la poule et de l'oeuf : les
compilatateurs ne font pas l'optimisation, parce que ce type de
code est rare dans les programmes réels (dans le langage
considéré), et ce type de code est rare, parce que les
compilateurs ne l'optimisent pas bien.

En effet. Mais, de nos jours, les compilateurs C partagent le
middle-end et les back-end avec d'autres langages pour lesquelles
ces optimisations sont essentielles, sinon bienvenues. Aussi, il me

Ah, c'est un bon point. Merci, je n'y avais pas pensé.

Il ne faudrait quand même pas que les utilisations de gcc pour
autre chose que le C, soit ce qui pousse l'évolution dans une
direction plutôt qu'une autre. Faire de l'optimisation plus
courante en C++, me paraît plus attrayant...

--
Michel Michaud
http://www.gdzid.com
FAQ de fr.comp.lang.c++ :
http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ/

Gabriel Dos Reis

16/12/2003 à 23:07

"Michel Michaud" writes:

| Dans news:, Gabriel Dos
| > writes:
| > S'il est vrai que traditionnellement, les compilateurs C
| > implémentaient rarement l'optimisation de recrusivité finale, ils
| > commencent maintenant à offrir cette optimisation.
| > GCC/gcc, depuis un bon bout de temps (depuis EGCS au moins), en
| > offrait une. Une version plus élaborée existe dans GCC-3.x/gcc. Une
| > version envore plus élaborée sera dans GCC-3.5/gcc (ou GCC-4.0/gcc,
| > peu importe comment il sera appelé).
|
| J'ose une question : est-ce vraiment important ou utile cette
| optimisation ? N'y a-t-il pas des choses plus importantes qui
| manquent dans gcc (ou g++) ?

Comme ?

| Il me semble que si le compilateur
| peut optimiser du code ordinaire, il pourra optimiser du code
| où j'aurais enlevé explicitement la récursivité (en tout ou en
| partie) et obtenir un résultat meilleur que l'optimisation
| complète de la récursivité qu'il aurait pu faire.

Ce raisonnement n'est pas nouveau. Mais le fait est qu'il y a ce
mouvement, donc certains pensent que c'est important -- pusque dans la
liste de ceux que je vois implémenter cela, c'est sur des contrats
spécificques.

| J'ai peut-être
| une mauvaise idée des endroits où la récursivité est utile, mais
| il me semble qu'annoncer de l'optimisation de la récursivité par
| le compilateur, c'est un peu prendre la chance que les gens
| codent récursivement ce qui n'a pas besoin d'être récursif en
| pensant faire mieux que la version non récursive...

Ou que les gens codent recursivement pour des besoins de clarté de
correction et veulent que le compilateur se débrouille pour optimiser.

À quoi sert un compilateur ?
Je ne suis pas sûr, qu'il y a ait Une Seule Réponse,

-- Gaby

Gabriel Dos Reis

16/12/2003 à 23:38

"Michel Michaud" writes:

[...]

| Il ne faudrait quand même pas que les utilisations de gcc pour
| autre chose que le C, soit ce qui pousse l'évolution dans une
| direction plutôt qu'une autre. Faire de l'optimisation plus
| courante en C++, me paraît plus attrayant...

En général, les fabriquants de compilateurs fourguent ce que demandent
leurs clients ;-p Si les utilisateurs de GCC pensent que leur
compilateur doit suporter un style de programmation et que les
développeurs de GCC ont des ressources pour le faire, pourquoi ne le
feront-ils pas ?

-- Gaby

Alain Naigeon

17/12/2003 à 01:38

"Gabriel Dos Reis" a écrit dans le message
news:

"Alain Naigeon" writes:

Merci pour ta réponse, il me faut un peu de temps pour
la digérer. Mais j'ai tout de même une question immédiate :

void f()
{
if( false)
{ /*
...
*/
}

Est-ce que le langage autorise une optimisation à :
void f() { }
?

(ou à rien du tout)

D'autre part, ton exemple :

Une entité est récursive si sa définition contient une référence à
elle-même. Ainsi

struct list {
int data;
list* link;
};

est tout de même un peu différent, puisque rien n'exclut
qu'un usage effectivement récursif soit fait de cette
définition. Alors que dans le cas de if( false )..!

...
As-tu un exemple d'opérateur Fix ?
(non trivial, hein, parce que "pour tout f", bigre !)

--

Français *==> "Musique renaissance" <==* English
midi - facsimiles - ligatures - mensuration
http://anaigeon.free.fr | http://www.medieval.org/emfaq/anaigeon/
Alain Naigeon - - Strasbourg, France

Gabriel Dos Reis

17/12/2003 à 04:36

"Alain Naigeon" writes:

| "Gabriel Dos Reis" a écrit dans le message
| news:
| > "Alain Naigeon" writes:
|
| Merci pour ta réponse, il me faut un peu de temps pour
| la digérer. Mais j'ai tout de même une question immédiate :
|
| void f()
| {
| if( false)
| { /*
| ...
| */
| }
|
|
| Est-ce que le langage autorise une optimisation à :
| void f() { }
| ?

As-tu vraiment voulu dire « commentaire » dans la branche de if ?
Si, oui, alors la sémantique dynamique est équivalente effectivement à
void f() { }. Si non, je ne comprends pas ta question. Veux-tu dire
que parce qu'il y a « false », le fragment suivant

void f() { if (false) { toto; } }

où le nom « toto » n'est jamais déclaré doit être considéré valide ?

| (ou à rien du tout)
|
|
| D'autre part, ton exemple :
|
| > Une entité est récursive si sa définition contient une référence à
| > elle-même. Ainsi
| >
| > struct list {
| > int data;
| > list* link;
| > };
|
| est tout de même un peu différent, puisque rien n'exclut
| qu'un usage effectivement récursif soit fait de cette
| définition. Alors que dans le cas de if( false )..!

Là, je ne comprends pas : le nom « list » qui réfère à la classe en
train d'être définie est utilisé dans la définition même. Et rien
n'exclut qu'aucun n'objet de cette classe ne soit jamais déclaré.

| ...
| As-tu un exemple d'opérateur Fix ?
| (non trivial, hein, parce que "pour tout f", bigre !)

Cherche l'opérateur (paradoxal) Y de point fixe, par exemple.

Tout langage qui admet des définitions récursives implémente un
opérateur de point fixe. C et C++ l'implémentent, c'est pour
cela que tu peux écrire

void* p = &p;

mais le restreignent à des « classes » d'entités.
Par exemple, il n'y a pas de point fixe pour les enums, ni pour les
typedefs, ni pour les alias de namespaces. Par contre il y en a pour
les classes -- c'est pour cela que tu peux écrire des structures de
données récursives ou des choses comme

struct fixpoint {
template<class T>
fixpoint operator(T) const { return fixpoint(); }
};

int main() { fixpoint f; f(f(f)); }

-- Gaby

"Alain Naigeon" <anaigeon@free.fr> writes:

| "Gabriel Dos Reis" <gdr@integrable-solutions.net> a écrit dans le message
| news: m3y8tdr3l1.fsf@uniton.integrable-solutions.net...
| > "Alain Naigeon" <anaigeon@free.fr> writes:
|
| Merci pour ta réponse, il me faut un peu de temps pour
| la digérer. Mais j'ai tout de même une question immédiate :
|
| void f()
| {
| if( false)
| { /*
| ...
| */
| }
|
|
| Est-ce que le langage autorise une optimisation à :
| void f() { }
| ?

As-tu vraiment voulu dire « commentaire » dans la branche de if ?
Si, oui, alors la sémantique dynamique est équivalente effectivement à
void f() { }. Si non, je ne comprends pas ta question. Veux-tu dire
que parce qu'il y a « false », le fragment suivant

void f() { if (false) { toto; } }

où le nom « toto » n'est jamais déclaré doit être considéré valide ?

| (ou à rien du tout)
|
|
| D'autre part, ton exemple :
|
| > Une entité est récursive si sa définition contient une référence à
| > elle-même. Ainsi
| >
| > struct list {
| > int data;
| > list* link;
| > };
|
| est tout de même un peu différent, puisque rien n'exclut
| qu'un usage effectivement récursif soit fait de cette
| définition. Alors que dans le cas de if( false )..!

Là, je ne comprends pas : le nom « list » qui réfère à la classe en
train d'être définie est utilisé dans la définition même. Et rien
n'exclut qu'aucun n'objet de cette classe ne soit jamais déclaré.

| ...
| As-tu un exemple d'opérateur Fix ?
| (non trivial, hein, parce que "pour tout f", bigre !)

Cherche l'opérateur (paradoxal) Y de point fixe, par exemple.

Tout langage qui admet des définitions récursives implémente un
opérateur de point fixe. C et C++ l'implémentent, c'est pour
cela que tu peux écrire

void* p = &p;

mais le restreignent à des « classes » d'entités.
Par exemple, il n'y a pas de point fixe pour les enums, ni pour les
typedefs, ni pour les alias de namespaces. Par contre il y en a pour
les classes -- c'est pour cela que tu peux écrire des structures de
données récursives ou des choses comme

struct fixpoint {
template<class T>
fixpoint operator(T) const { return fixpoint(); }
};

int main() { fixpoint f; f(f(f)); }

-- Gaby

Vous avez filtré cet utilisateur ! Consultez son message

"Alain Naigeon" writes:

| "Gabriel Dos Reis" a écrit dans le message
| news:
| > "Alain Naigeon" writes:
|
| Merci pour ta réponse, il me faut un peu de temps pour
| la digérer. Mais j'ai tout de même une question immédiate :
|
| void f()
| {
| if( false)
| { /*
| ...
| */
| }
|
|
| Est-ce que le langage autorise une optimisation à :
| void f() { }
| ?

As-tu vraiment voulu dire « commentaire » dans la branche de if ?
Si, oui, alors la sémantique dynamique est équivalente effectivement à
void f() { }. Si non, je ne comprends pas ta question. Veux-tu dire
que parce qu'il y a « false », le fragment suivant

void f() { if (false) { toto; } }

où le nom « toto » n'est jamais déclaré doit être considéré valide ?

| (ou à rien du tout)
|
|
| D'autre part, ton exemple :
|
| > Une entité est récursive si sa définition contient une référence à
| > elle-même. Ainsi
| >
| > struct list {
| > int data;
| > list* link;
| > };
|
| est tout de même un peu différent, puisque rien n'exclut
| qu'un usage effectivement récursif soit fait de cette
| définition. Alors que dans le cas de if( false )..!

Là, je ne comprends pas : le nom « list » qui réfère à la classe en
train d'être définie est utilisé dans la définition même. Et rien
n'exclut qu'aucun n'objet de cette classe ne soit jamais déclaré.

| ...
| As-tu un exemple d'opérateur Fix ?
| (non trivial, hein, parce que "pour tout f", bigre !)

Cherche l'opérateur (paradoxal) Y de point fixe, par exemple.

Tout langage qui admet des définitions récursives implémente un
opérateur de point fixe. C et C++ l'implémentent, c'est pour
cela que tu peux écrire

void* p = &p;

mais le restreignent à des « classes » d'entités.
Par exemple, il n'y a pas de point fixe pour les enums, ni pour les
typedefs, ni pour les alias de namespaces. Par contre il y en a pour
les classes -- c'est pour cela que tu peux écrire des structures de
données récursives ou des choses comme

struct fixpoint {
template<class T>
fixpoint operator(T) const { return fixpoint(); }
};

int main() { fixpoint f; f(f(f)); }

-- Gaby

miracle de la récursion

10 réponses

Veuillez sélectionner un problème