miracle de la récursion

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> wrote
in message news:<3fdccdee$0$22306$626a54ce@news.free.fr>...

"James Kanze" <kanze@alex.gabi-soft.fr> a écrit > "Pierre Maurette"
<mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

|> "Christophe" <chrschneider@free.fr> a écrit
|> [...]
|> > J'imagine que c'est le compilateur qui, voyant que la fonction
|> > est récursive, va totalement modifier le code de manière à
|> > renvoyer non pas un nombre, mais une somme de nombre. En fait
|> > c'est le compilateur qui va faire un gros travail dès qu'il
|> > reconnait une fonction récursive. Je me trompe ?

|> Oui, je le crains.

Je ne crois pas. La plupart des compilateurs C++ que je connais
traitent un appel récursif exactement comme n'importe autre appel de
fonction.

C'est exactement ce que j'ai écrit : Christophe demande s'il se trompe
en pensant que le compilateur "voyant que la fonction est
récursive...etc.". Je lui réponds que oui, je pense qu'il se trompe
("crains" est un euphémisme).

En effet. Je cherchais une négation, et je me suis arrêté au mot « oui ».

S'il se trompe, c'est donc que le compilateur ne fait pas ce qu'il
pense. Et je précise que :

"La récursivité n'existe pas dans le langage. Une fonction est dite
récursive si elle s'appelle elle-même. C'est tout."

C'est qui m'a gené. Je ne suis pas sûr ce que tu entends par « existe
dans le langage », mais les normes C et C++ exigent que les fonctions
soient récursives. À l'encontre du Fortran ou Cobol, par exemple (au
moins dans leurs versions traditionnelles -- ça fait des décénnies que
je ne les ai pas régardés).

Je ne suis pas sûr ce que tu essaies à dire. Le C et le C++
garantissent que les appels récursifs (directs ou indirects)
fonctionnent, dans la mesure qu'on n'épuise pas les ressources
système (pile). Je ne sais pas ce que tu veux de plus -- Lisp (un
langage récursif par excellence) n'en dit pas plus.

Pas vu cette garantie dans les normes C99 et C++98, en tous cas aucune
allusion à la pile sur ce sujet.

Les normes précisent les effets, non les moyens. En C++, §5.2.2/9 :
« Recursive calls are permitted, except to the function named main. »

C'est implicite aussi dans la définition de « Automatic storage
duration », §3.7.2.

Je vais essayer d'expliquer, mais je n'ai jamais fait d'études
d'informatique, donc le vocabulaire est peut-être approximatif. Une
fonction F() est dite récursive si elle contient un appel récursif
direct ou indirect. Un appel récursif est un appel de fonction F1()
qui conduit la fonction F() à être appelée avant que F1() ne retourne.
F1() peut être F(), c'est alors de la récursivité directe.

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.

En cherchant sur le mot lui-même, il est simplement dit que l'appel
récursif est autorisé pour l'ensemble des fonctions, sauf main() pour
laquelle il est justement refusé à la compilation.

[norme C++]
5.2.2 Function call
...
9 Recursive calls are permitted, except to the function named main ...:

[norme C]
6.5.2.2 Function calls
Constraints
...
11 Recursive function calls shall be permitted, both directly and
indirectly through any chain of other functions.

Les normes considèrent que le lecteur sait ce qu'est un appel récursif
et quelles sont les conditions minimales pour qu'il puisse être
fonctionnel (les autres conditions sont dans l'algo et le codage).

Je l'espère.

Ces conditions sont la réentrance des fonctions. Qu'est-ce ?

Chaque appel d'une fonction provoque la création d'un jeu tout neuf de
variables locales (ou automatiques, etc.). Parmi ces variables
locales, les paramètres passés à la fonction, ou des variables locales
initialisées par ces paramètres, question de vocabulaire.

Techniquement, les paramètres sont créés par la fonction appelante, à la
site de l'appel. Ils sont donc des variables temporaires de la fonction
appelante, et non de la fonction appelée. Mais ça ne change rien du
principe. De même qu'en C++, formellement, les variables locales sont
créées à l'entrée d'un bloc, et non d'une fonction. Mais là aussi, je
chipote.

Surtout, la technique que tu décris, c'est simplement la technique la
plus courante. Je me suis déjà servi d'un compilateur Pascal où le
compilateur faisait effectivement un travail supplémentaire en cas d'un
appel récursif. Le processeur en question n'avait pas d'adressage basé,
et les auteurs du compilateur ont supposé que les appels récursifs
étaient rares. Ils allouaient donc des variables statiquement, et
généraient du code pour détecter des appels récursifs et pour
sauvegarder et restaurer les anciennes valeurs le cas échéant.

Imaginons que le déroulement de la fonction soit interrompu par une
interruption (signal) ou un appel de fonction (pouvant être la
fonction elle-même).

Le programme est réentrant si au retour de cet évènement, les
variables locales sont inchangées et la fonction peut donc continuer
son travail, et ceci même si la fonction a été appelée "pendant ce
temps". Ceci couvre le cas où la fonction s'est simplement appelée
elle-même (et ainsi de suite parfois). La même fonction appelée par
plusieurs threads doit également être réentrante. Les normes
garantissent effectivement cette réentrance, mais sans faire de
référence très explicite à la récursivité.

C'est l'inverse. Les normes garantissent la récursivité, et définissent
la durée de vie des variables locales. La réentrance en découle, plus ou
moins. Plutôt moins, parce que les variables locales peuvent aussi être
statiques. Donc, par exemple, de la norme C (§7.14.1.1/5) :

If the signale occurs other than the result of calling the abort or
rais function [c-à-d, d'une façon potentiellement asynchrone], the
behavior is undefined if the signal handler refers to any object
with static storage duration other than by assigning a value to an
object declared as volatile sig_atomic_t, or the signale handler
calls any function in the standard library other than the abort
function, the _Exit function, or the signal function with the first
argument equal to the signal number corresponding to the signal that
caused the invocation of the handler. Furthermore, if such a call
to the signal function results in a SIG_ERR return, the value of
errno is indeterminate.

Malheureusement, de telles précisions manquent par ailleurs, aussi bien
dans la norme C que dans la norme C++ : est-ce que la fonction de
comparaison qu'on passe à qsort peut appeler qsort, par exemple ? Ou en
C++, est-ce qu'un operator new fourni par l'utilisateur peut appeler
memset ? ou std::cerr::operator<< ?

Les fonctions des bibliothèques standard ne sont pas (ou ne sont pas
toutes, ou ne sont pas garanties) réentrantes.
[norme C++]
1.9 Program execution
(voir paragraphes 9 & 10)

[norme C]
5.2.3 Signals and interrupts
1 Functions shall be implemented such that they may be interrupted at
any time by a signal, or may be called by a signal handler, or both,
with no alteration to earlier, but still active, invocations' control
flow (after the interruption), function return values, or objects with
automatic storage duration. All such objects shall be maintained
outside the function image (the instructions that compose the
executable representation of a function) on a per-invocation basis.

Les variables statiques ne sont bien entendu pas concernées par cette
réentrance, mais elles peuvent être utilisées pour ce qu'elles sont.

Ce n'est pas dit. Voir le passage que j'ai cité en ce qui concerne les
signaux.

En fait, techniquement, on comprend bien les raisons. Les écritures ne
sont pas toujours atomiques, et c'est tout à fait possible de générer
une représentation illégale s'il n'y a qu'une partie de l'écriture qui
s'est faite.

Une variable de ce type est par essence volatile. Enfin, j'en sais
trop rien, faudrait revoir la définition exacte de la volatilité ...

Voir ci-dessus -- tu peux écrire (mais non lire) une variable de type
sig_atomic_t volatile dans le signal. C'est tout.

Une implémentation peut donner des garanties supplémentaires. Je n'en
connais pas, par exemple, où tu ne peux pas en fait aussi lire un
sig_atomic_t. Mais ça ne va jamais très loin.

La présence d'une variable statique dans le code d'une fonction
récursive est parfois le signe d'une mauvaise compréhension, d'un
refus du concept de récursivité de la part du programmeur.

Ou d'un désir de « gerer » la récursion:-). (L'exemple type, c'est un
compteur de récursion, pour empècher d'aller trop loin.)

Quid de la pile ? Pour moi, il y a deux types de pile. Tout d'abord,
le concept d'appels emboités, la pile d'appel (la commande stack du
debugger SoftIce donne un exemple) :
main()
f1()
f2()
f3()
quand le code est dans f4().
Pour ce qui est de l'éventuelle pile physique du microprocesseur, la
représentation POURRAIT être :
bloc main()
bloc f1()
bloc f2()
bloc f3()
bloc f4()
Un bloc regroupe variables locales (dont paramètres), adresse de
retour, sauvegarde de certains registres comme EBP par exemple.

Comme tu as rémarqué, la norme ne parle pas de pile. En revanche, c'est
impossible à implémenter la recursion sans pile -- il faut donc que
l'implémentation ait une pile quelque part. Mais cette pile peut prendre
de nombreuses formes : sur la plupart des processeurs modernes, il y a
une seule pile, contigüe, gérée par le hardware, qui contient les
adresses de retour et les données locales. Mais je crois qu'il a bien
existé des architectures à deux piles, une pour les adresses de retour,
et une pour les données locales. Et j'ai déjà travaillé sur une
implémentation de C où la « pile » s'était fait des blocs chaînés,
alloués par le même mechanismes que malloc.

En revanche, l'utilisation de la récursion grauitement n'est pas un
idiome classique de C++, et le langage offre de nombreux autres
constructions comme les boucles.

Certainement. le calcul d'une factorielle par récursion est calamiteux
en termes de performances.

Avec les compilateurs C et C++ courants. Ce n'est pas obligatoirement le
cas, et ce n'est pas le cas avec les compilateurs Lisp courants. Si
j'écris quelque chose du genre :

(defun fact(n)
(cond ((<= n 0) 1)
(t (* n (fact (- n 1))))))

en Lisp, je m'attends à ce que le compilateur génère une boucle. En C++,
je ne m'y attends pas.

Et pourtant ...

J'ai une solution récursive que je trouve indispensable qui me vient à
l'esprit, c'est le parcours de l'ensemble des fichiers d'un disque. Ça
vient certaineement du fait que sous Windows, quand on parcourt un
répertoire, on ne sait pas si on va ramener un fichier ou un
répertoire. Idem pour beaucoup de structures arborescentes.

En général, la gestion de l'arborescence ne connaît pas de solution non
récursive. Au moins à une certaine niveau -- quand on invoque ftw sur
les Unix qui l'ont, on n'écrit pas d'appel récursif, et dans un projet
dans la passée, on a écrit un itérateur sur une structure sembable ;
l'itérateur, évidemment, contenait une pile (gérée à la main).

Une solution comme celle proposée ne serait pas considérée une bonne
solution C++,

Certes, mais ce que fait Christophe est certainement une façon de
faire un grand pas dans la compréhension du fonctionnement des ..
fonctions.

Tout à fait. Je ne critique pas sa valeur formative.

--
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

<kanze@gabi-soft.fr> a écrit
[...]
Nous sommes d'accord sur l'essentiel me semble-t-il.
C'est un peu comme pour les chiens et les chats.
From scratch, c'est "très pareil", un toutou et un minet : même nombre de
pattes, une queue, deux yeux avec des trous dans la peau par chance situés
juste en face des yeux, même constructeur de copie (plus bruyant pour
Grosminet que pour Droopy, mais bon...) , etc. Et pourtant, quand on parle
chien-chat, c'est toujours sur les différences que l'on focalise ;-)

Les normes précisent les effets, non les moyens. En C++, §5.2.2/9 :
« Recursive calls are permitted, except to the function named main. »
Nous citons le même passage, et pour cause : c'est la seule allusion nette à

l'appel récusif d'une fonction.
Je l'interprète peut-être un peu différemment que vous, pour moi c'est une
simple possibilité syntaxique, comme l'appel da main() est simplement refusé
à la compilation. J'ai l'impression que la norme me dit : "L'appel récursif,
je vous le permet. A vous de voir si ça va fonctionner conformément à vos
attentes". Et c'est ailleurs que l'on va trouver des éléments nous
permettant de savoir que, bien géré, ça va fonctgionner.
"permitted" n'est pas "supported" ni même "allowed". MAis effectivement, je
sodomise le diptère.

Techniquement, les paramètres sont créés par la fonction appelante, à la
site de l'appel. Ils sont donc des variables temporaires de la fonction
appelante, et non de la fonction appelée. Mais ça ne change rien du
principe. De même qu'en C++, formellement, les variables locales sont
créées à l'entrée d'un bloc, et non d'une fonction. Mais là aussi, je
chipote.
Je chipote également. Je vois les paramètres réels comme des rvalues de

l'appelant qui initialisent "juste avant l'appel" des variables locales de
la fonction. Pendant la durée de vie d'un appel de la fonction, il n'y a
aucune différence entre ses variables locales et ses paramètres.
Techniquement, le compilateur est PARFOIS très économe : il empile un
paramètre, et la fonction, sans transfert supplémentaire, le "connait" sous
un "nom" ressemblant à type ptr [ESP - n] ou type ptr [EBP - n]. J'admet que
c'est imagé, lié à un processeur, et pas obligatoire du tout, il existe de
plus plusieurs conventions d'appel.

En fait, techniquement, on comprend bien les raisons. Les écritures ne
sont pas toujours atomiques, et c'est tout à fait possible de générer
une représentation illégale s'il n'y a qu'une partie de l'écriture qui
s'est faite.

Voir ci-dessus -- tu peux écrire (mais non lire) une variable de type
sig_atomic_t volatile dans le signal. C'est tout.
Je ne connais ces notions de volatilité et d'accès concurrent que par

l'assembleur, et à l'opposée par les ressources de mon OS. Je dois dire que
l'aspect C/C++ de la chose m'effraye un peu.

Comme tu as rémarqué, la norme ne parle pas de pile. En revanche, c'est
impossible à implémenter la recursion sans pile -- il faut donc que
l'implémentation ait une pile quelque part. Mais cette pile peut prendre
de nombreuses formes : sur la plupart des processeurs modernes, il y a
une seule pile, contigüe, gérée par le hardware, qui contient les
adresses de retour et les données locales.
Le mot pile est ambiguë (pour une fois, au même titre que l'anglais stack,

qui n'est guère plus précis). Au moins trois niveaux :
* Une notion purement intellectuelle : la pile d'appel.
* Un objet algorithmique, comme dans la STL.
* La pile (pas nécesssairement unique) du processeur.
Le point commun, c'est LIFO.
Entendre parler de "pile FIFO" me hérisse la pilosité sur laquelle je suis
assis.
Le mot "pipe(line)" (et pourquoi pas tuyau ?) rentre heureusement dans les
us.

Mais je crois qu'il a bien
existé des architectures à deux piles, une pour les adresses de retour,
et une pour les données locales.
Il faudrait voir des trucs comme les PIC de Microchip, qui sont en

architecture Harvard.

en Lisp, je m'attends à ce que le compilateur génère une boucle. En C++,
je ne m'y attends pas.
Connais pas Lisp. Mon petit frère qui est prof de Math Spé et que

l'informatique fatigue (tout comme les maths!) me parle d'un truc nommé je
crois Maple, qui gère la récusivité "en tant que telle", en optimisant.

Cordialement,
Pierre

kanze@gabi-soft.fr writes:

[...]

| > Ces conditions sont la réentrance des fonctions. Qu'est-ce ?
|
| > Chaque appel d'une fonction provoque la création d'un jeu tout neuf de
| > variables locales (ou automatiques, etc.). Parmi ces variables
| > locales, les paramètres passés à la fonction, ou des variables locales
| > initialisées par ces paramètres, question de vocabulaire.
|
| Techniquement, les paramètres sont créés par la fonction appelante, à la
| site de l'appel. Ils sont donc des variables temporaires de la fonction
| appelante, et non de la fonction appelée.

En C++, les paramètres de fonction sont des variables de la fonction
appelée, initialisées et détruites dans la fonction appelante.

[...]

| en Lisp, je m'attends à ce que le compilateur génère une boucle. En C++,
| je ne m'y attends pas.

parce que les fabricants de compilateurs t'ont « éduqué » comme ça.
Maintenant, suppose que beaucoup d'utilisateurs se plaignent et font
pression sur leurs fournisseurs pour avoir des produits de meilleur
qualité...

| > Et pourtant ...
|
| > J'ai une solution récursive que je trouve indispensable qui me vient à
| > l'esprit, c'est le parcours de l'ensemble des fichiers d'un disque. Ça
| > vient certaineement du fait que sous Windows, quand on parcourt un
| > répertoire, on ne sait pas si on va ramener un fichier ou un
| > répertoire. Idem pour beaucoup de structures arborescentes.
|
| En général, la gestion de l'arborescence ne connaît pas de solution non
| récursive.

tu connais sûrement le théorème qui dit que...

-- Gaby

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> writes:

| > Les normes précisent les effets, non les moyens. En C++, §5.2.2/9 :
| > « Recursive calls are permitted, except to the function named main. »
| Nous citons le même passage, et pour cause : c'est la seule allusion nette à
| l'appel récusif d'une fonction.

Non, je ne crois pas. Regarde le passage concernant les variables
automatiques (et les paramètres sont des variables
automatiques). C'est assez explicit.

[...]

| Connais pas Lisp. Mon petit frère qui est prof de Math Spé et que
| l'informatique fatigue (tout comme les maths!) me parle d'un truc nommé je
| crois Maple, qui gère la récusivité "en tant que telle", en optimisant.

oui, m'enfin si on peut appeler Maple un langage. :-)
J'aime bien le donner en contrexemple comme qui *ne devrait pas*
arriver en informatique, mais bon, cela doit être moi :-)

Je conseillerais Scheme (plutôt que Lisp directement).
Mais de nos jours, les élèves sont embrigadés et on leur enseigne (O)Caml.

Feu !

-- Gaby

"Pierre Maurette" <mmaauurreettttttee.ppiieerrrree@@ffrreeee.ffrr> wrote
in message news:<3fdd9244$0$24031$626a54ce@news.free.fr>...

<kanze@gabi-soft.fr> a écrit
[...]
Nous sommes d'accord sur l'essentiel me semble-t-il. C'est un peu
comme pour les chiens et les chats. From scratch, c'est "très
pareil", un toutou et un minet : même nombre de pattes, une queue,
deux yeux avec des trous dans la peau par chance situés juste en face
des yeux, même constructeur de copie (plus bruyant pour Grosminet que
pour Droopy, mais bon...) , etc. Et pourtant, quand on parle
chien-chat, c'est toujours sur les différences que l'on focalise ;-)

Les normes précisent les effets, non les moyens. En C++, §5.2.2/9 :
« Recursive calls are permitted, except to the function named
main. »

Nous citons le même passage, et pour cause : c'est la seule allusion
nette à l'appel récusif d'une fonction. Je l'interprète peut-être un
peu différemment que vous, pour moi c'est une simple possibilité
syntaxique, comme l'appel da main() est simplement refusé à la
compilation. J'ai l'impression que la norme me dit : "L'appel
récursif, je vous le permet. A vous de voir si ça va fonctionner
conformément à vos attentes". Et c'est ailleurs que l'on va trouver
des éléments nous permettant de savoir que, bien géré, ça va
fonctgionner. "permitted" n'est pas "supported" ni même
"allowed". MAis effectivement, je sodomise le diptère.

« Permitted », ça veut bien dire que j'ai droit à le faire. Pour la
reste, la durée de vie des variables, etc., en définit la sémantique.

Techniquement, les paramètres sont créés par la fonction appelante,
à la site de l'appel. Ils sont donc des variables temporaires de la
fonction appelante, et non de la fonction appelée. Mais ça ne change
rien du principe. De même qu'en C++, formellement, les variables
locales sont créées à l'entrée d'un bloc, et non d'une
fonction. Mais là aussi, je chipote.

Je chipote également. Je vois les paramètres réels comme des rvalues
de l'appelant qui initialisent "juste avant l'appel" des variables
locales de la fonction. Pendant la durée de vie d'un appel de la
fonction, il n'y a aucune différence entre ses variables locales et
ses paramètres.

Ça dépend à quel niveau on se place. Dans l'appelé, je peux m'en servir
comme des variables locales. En revanche, ils sont bien construits et
détruits dans la contexte de l'appelés ; selon les compilateurs, le code
généré pour y accéder peut être différents ou le même que pour accéder à
des variables locales. Elles sont un peu à cheval.

Techniquement, le compilateur est PARFOIS très économe : il empile un
paramètre, et la fonction, sans transfert supplémentaire, le "connait"
sous un "nom" ressemblant à type ptr [ESP - n] ou type ptr [EBP -
n]. J'admet que c'est imagé, lié à un processeur, et pas obligatoire
du tout, il existe de plus plusieurs conventions d'appel.

C'est l'image le plus courant avec les machines modernes. Sur ma
machine, les paramètres sont dans les régistres, mais le banc de
régistres « glissent », de façon que les régistres o0 à o7 de l'appelant
devient i0 à i7 de l'appelé.

Il y a en fait une petite différence, surtout quand les paramètres sont
en mémoire (et non dans des régistres) : la mémoire pour les paramètres
est allouée chez l'appelant. (Mais ça ne signifie pas grand chose --
j'ai déjà travaillé sur une implémentation où la mémoire pour les
variables locales de la fonction était allouée aussi par l'appelant.)

En fait, techniquement, on comprend bien les raisons. Les écritures
ne sont pas toujours atomiques, et c'est tout à fait possible de
générer une représentation illégale s'il n'y a qu'une partie de
l'écriture qui s'est faite.

Voir ci-dessus -- tu peux écrire (mais non lire) une variable de
type sig_atomic_t volatile dans le signal. C'est tout.

Je ne connais ces notions de volatilité et d'accès concurrent que par
l'assembleur, et à l'opposée par les ressources de mon OS. Je dois
dire que l'aspect C/C++ de la chose m'effraye un peu.

Et pourtant -- si j'écris quelque chose comme « while ( i > 0 ) ... »,
et je modifie i dans la boucle, c'est bien agréable pour les
performances que le compilateur met i dans un régistre. Sauf,
évidemment, si je m'attends à ce qu'il soit modifié dans un handler de
signal, ou si c'est un régistre d'entrées/sorties mappées à une adresse
mémoire, et que c'est quelque chose en dehors de mon programme qui va le
changer. Il faut bien quelque chose pour dire au compilateur de ne pas
optimiser dans ces cas-là.

Comme tu as rémarqué, la norme ne parle pas de pile. En revanche,
c'est impossible à implémenter la recursion sans pile -- il faut
donc que l'implémentation ait une pile quelque part. Mais cette pile
peut prendre de nombreuses formes : sur la plupart des processeurs
modernes, il y a une seule pile, contigüe, gérée par le hardware,
qui contient les adresses de retour et les données locales.

Le mot pile est ambiguë (pour une fois, au même titre que l'anglais
stack, qui n'est guère plus précis). Au moins trois niveaux :

* Une notion purement intellectuelle : la pile d'appel.
* Un objet algorithmique, comme dans la STL.
* La pile (pas nécesssairement unique) du processeur.

Le point commun, c'est LIFO. Entendre parler de "pile FIFO" me
hérisse la pilosité sur laquelle je suis assis.

Tout à fait. Toute structure de données qui permet l'accès dernière
entrée/dernière sortie est une pile.

Mais on fait bien de le préciser, parce qu'il y a bien des gens pour qui
la pile, c'est où pointe ESP. (Sauf que je n'ai pas de ESP sur ma
machine.)

Le mot "pipe(line)" (et pourquoi pas tuyau ?) rentre heureusement dans
les us.

Mais je crois qu'il a bien existé des architectures à deux piles,
une pour les adresses de retour, et une pour les données locales.

Il faudrait voir des trucs comme les PIC de Microchip, qui sont en
architecture Harvard.

Ou même certaines machines plus anciennes.

Sur un PDP-11, n'importe quel régistre pouvait servir de pointeur de
pile. (Mais c'était fort déconseillé de se servir de r7, parce qu'il
servait aussi comme compteur ordinal -- c'est la seule machine que j'ai
jamais vu où le compteur ordinal était un régistre banalisé comme les
autres.) D'après ce que j'ai entendu dire, les premières implémentations
de Forth utilisait deux piles, une pour les données, et une pour les
adresses de rétour des souprogrammes. Étant donné sa structure, la même
chose ne m étonnerait pas des interpréteurs de PostScript aujourd'hui.

en Lisp, je m'attends à ce que le compilateur génère une boucle. En
C++, je ne m'y attends pas.

Connais pas Lisp. Mon petit frère qui est prof de Math Spé et que
l'informatique fatigue (tout comme les maths!) me parle d'un truc
nommé je crois Maple, qui gère la récusivité "en tant que telle", en
optimisant.

Je n'en connais que ce qu'il me faut pour configurer mon éditeur:-).
Mais j'ai toujours entendu dire que la plupart des compilateurs Lisp
reconnaissaient bien la recursion finale, et la convertissaient en
boucle.

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.

--
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

kanze@gabi-soft.fr writes:

D'après ce que j'ai entendu dire, les premières implémentations de
Forth utilisait deux piles, une pour les données, et une pour les
adresses de rétour des souprogrammes. Étant donné sa structure, la
même chose ne m étonnerait pas des interpréteurs de PostScript
aujourd'hui.

C'est a peut pres indispensable: un programme Forth manipule la pile
explicitement et un sous-programme (un mot dans la terminologie Forth)
peut empiler ou depiler des choses. La pile de retour sert aussi a
d'autres choses comme la gestion des mots fonctionnant par paire (boucle
par exemple).

--
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

kanze@gabi-soft.fr writes:

| autres.) D'après ce que j'ai entendu dire, les premières implémentations
| de Forth utilisait deux piles, une pour les données, et une pour les
| adresses de rétour des souprogrammes. Étant donné sa structure, la même
| chose ne m étonnerait pas des interpréteurs de PostScript aujourd'hui.

PostScript n'a pas de notion d'adresse de retour de sous-programme
Par contre, tu as:
- « operand stack » (là où les opérandes sont empilés)

- « dictionary stack » (là pile de dictionnaires qui sert à faire
la recherche de noms -- pas aussi compliquée qu'en C++)

- « execution stack » (là où sont placés les objets exécutables, en
cours d'éxécution). Cett dernière pile est le pendant de la pile
de « record activation » pour les langages traditionnels comme C,
C++, ML, ...

[...]

| 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.

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é).

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

-- Gaby

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.

-- Gaby

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();
}
}

</Mode>

--
Loïc

"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é ?
Je trouve l'exemple astucieux et intéressant, mais c'est
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 ?

--

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

-- Gaby