[Marseille-pm] Re: [ ppm ] YAPC: ; Europe: ; 3 <2003>

[arnaud.assad at free.fr]

On Wed, Jul 30, 2003 at 10:00:51AM +0200, Michel Rodriguez wrote: 
>>On Wed, 30 Jul 2003 arnaud.assad at free.fr wrote:

>>[une excellente explication des continuations et co-routines]

>Oaouh! Je commence a comprendre les coroutines. Pour les continuations il
>va falloir que je m'accroche encore un peu (je crois comprendre le
>principe, mais je vois pas trop l'utilite).

>Ceci dit l'impression que j'ai c'est que c'est plutot utilise comme
>mechanismes de bas niveau: c'est surtout necessaire au niveau de Parrot
>pour pouvoir traiter les interruptions, faire du multi-threading et que
>sais-je encore. Ca pourra etre utilise dans Perl pour faire des modules
>hyper-ruses, mais je suis pas sur que le clamping moyen qui fait du XML 
>(au hasard ;--) aura trop a s'en servir.


Je pense aussi.  Les continuations ont un intérêt surtout
(uniquement?) pour l'implémentation.

J'avais évoqué les tail calls et la tail recursion, optimisations pouvant
être mises en oeuvre facilement et efficacement si on a des continuation.

Comme l'explication est le meilleur moyen de tester ses connaissances,
voici un petit topo (toujours orienté newbie (tricks of the wizard on
attendra un peu ;-)) sur les tail calls et la tail recursion :

Commencons par les tail calls (appels finaux ? appels finauds ? ;-)

Un "tail call" c'est quand une fonction retourne le résultat d'une
fonction.

sub toto {
	# code

	return titi();
}


traditionnellement, lors de l'appel et l'exécution d'une fonction,
pas mal de choses sont empilées sur la pile.

plus précisément lors de l'exécution d'une fonction :

On alloue de l'espace sur la pile (parametres et variables locales)
Puis (apres le traitement de traitement) on desalloue cet espace et on
positionne sur la pile la valeur retournée.


soit une nouvelle fonction tata() :

sub tata {
	# code

	return toto();
}

et

sub titi {
	return 1; # ou n'importe quelle valeur
}

lors de l'execution de tata(), la pile ressemblera à ça (au moment ou
on se trouvera dans titi() ) :

ESPACE ALLOUE POUR tata() ESPACE ALLOUE POUR toto() ESPACE ALLOUE
POUR titi()

Notez qu'a ce moment on se trouve dans titi et qu'on a PLUS besoin des
espaces alloués pour tata et toto !

quand titi se termine, on désalloue l'espace pour titi et met la valeur
de retour sur la pile (résultat de la fonction titi() )

La pile ressemble alors à ca

ESPACE ALLOUE POUR tata() ESPACE ALLOUE POUR toto() VALEUR RETOURNEE
PAR titi()


toto récupère cette valeur sur la pile, et se termine en la retournant
à son tour. La pile ressemble alors à :


ESPACE ALLOUE POUR tata() VALEUR RETOURNEE PAR toto()

tata peut alors se terminer : après avoir récupéré la valeur de toto()
sur la pile, on désalloue l'espace alloué pour tata et retourne la valeur
précédemment récupérée en la mettant sur la pile qui contient alors :


VALEUR RETOURNEE PAR tata().


Comme on l'a précisé plus haut, on voit que lors de l'exécution de
titi la pile contient beaucoup d'informations inutiles (paramètres et
variables de tata() et toto().	Ce n'est pas optimal du point de vue
de l'espace mémoire (d'autant plus que la pile a une taille limitée).
C'est d'autant plus catastrophique, que les "profondeurs d'appels"
sont importantes (comme celle obtenue par exemple par une bonne grosse
récursivité bien profonde...)

De plus vous noterez la séquence d'instructions visiblement sous-optimile
qui consiste à passer une même valeur en la lisant sur la pile et en la
reposant sur la pile, puis en la reprenant puis en la reposant...


D'ou l'idée, déjà ancienne, de remplacer le 'return quelquechose' par

1) retirer l'espace alloué pour la fonction courante 2) faire un goto
(!!!!) vers la fonction dont on retourne la valeur


Dans ce cas lors de l'exécution de tata() lors de l'exécution de titi()
la pile ressemble à :


ESPACE ALLOUE POUR titi()

quand titi() se termine on désalloue cet espace et met la valeur de
retour sur la pile qui devient

VALEUR RETOURNEE PAR titi()

et la fonction qui a appellée tata() n'a plus qu'a récupérer cette valeur
sur la pile :-)


Gain d'espace énorme, et rapidité accrue (pas de push/pop de la valeur
de retour inutile...)

A noter la tail récursion est un sous-cas plus simple du tail call


sub fact {
	my $n = shift;

	if ($n == 1) { return 1; }

	return $n * fact($n-1);
}

se transforme en quelquechose de comparable à (mais probablement mieux
écrit ;-)

sub fact {
	my $n = shift; my $res = 1;

branche:

	if ($n == 1) { return $res; }

	$res *= $n; $n = $n -1;

	goto branche;
}


Ce cas est plus simple car on connait la fonction appelante, du coup le
compilateur peut effectuer ce genre d'optimisations automatiquement.

Donc pour en revenir à l'utilité des continuation, grace aux continuations
on aura les tail calls (et donc la tail recursion) et on pourra utiliser
des formes récursives qui sont a la fois élégantes (dans leur expression)
et efficaces dans leur implémentation.


Voila.

Comme d'hab commentaires/corrections/additifs sont les bienvenus...

Arnaud.