Où l'on reparle de l'Art de Programmer en Perl

Un historique de toutes nos réunions

Table des matières

mercredi 11 février 2009

La voix du secrétaire (Jean)

Présents à la réunion, par ordre d'arrivée, ce qui correspond à peu près à la disposition autour de la table.

Théo,
moi,
Laurent (B),
Olivier (M),
David (L),
Charles,
Éric (glb),
et Jérôme.

Nous avons mangé de la salade de magrets, de la salade de gésiers, des saucisses de Morteau avec purée, une andouillette, et un faux-filet. Je suis parti avant que les derniers présents commandent leur dessert. Nous avons bu de la bière Orval, un pastis et de la vodka.

La réunion a eu lieu au Maldoror.

Nous avons parlé de Perl, d'Internet en quelque sorte, d'informatique et de points divers.

Perl

Olivier vient de sortir son exemplaire de De l'art de programmer en Perl de l'emballage de cellophane. Et il est venu avec à la réunion pour que Jérôme et moi le lui dédicacions.
Bien qu'il ait commencé à le lire depuis très peu, Olivier a déjà trouvé une erreur : à la page 224, un exemple de code utilise la variable $ARG, alors qu'il s'agit du premier élément du tableau des arguments, c'est-à-dire $ARGV[0]. [ J'ai vérifié dans la version originale et j'ai trouvé cette erreur au même endroit, page 219. On la trouve également dans les exemples téléchargeables (recherchez le fichier CODE/ch10/Ch10.051_Prob). ] Et que sont devenus les errata de la version française ? Hélas, ils ont disparu, ainsi que les exemples de code traduits.
Juste après la page 224 qu'Olivier a montrée, il y a la présentation du module IO::Prompt. Dans la version originale, le livre présente l'option -onechar qui fait que l'utilisateur n'a même pas besoin de taper sur <entrée> pour que le programme récupère la réponse, car dès le premier caractère tapé, le programme recommence à s'exécuter. Il est possible de contrôler les valeurs entrées avec un autre paramètre -require, pour exiger par exemple que le caractère saisi soit "a", "b", "c", "d" ou "e". Puis l'auteur montre une extension de ce mécanisme avec l'option -yn qui attend un "y" ou un "n" pour redonner la main au programme. Dans la traduction, j'ai inversé les deux options. D'abord, je montre comment le programme peut récupérer un "y" ou un "n" avec l'option -yn. Ensuite, je montre comment faire pour que le programme accepte une entrée d'un caractère, pas forcément "y" ou "n". Et enfin, je montre comment écrire l'appel à prompt pour que la réponse soit contrôlée avant la reprise du programme et pour que l'on ait ainsi "o" ou "n".
Après la traduction du livre, il y a eu la traduction des exemples de code téléchargeables. J'ai traduit les fragments de code venant de mes chapitres et je les ai (presque tous) testés. L'un d'eux (Ch10.069_Best) simulait un réseau très peu fiable. Le programme cherche à acquérir une ressource réseau. S'il n'y arrive pas, il attend un petit peu avant de recommencer. Le délai à la n^ème tentative était de fibonacci(n) microsecondes. Le problème, c'est que le réseau simulé est tellement foireux que le programme a de fortes chances d'aller jusqu'à la centième tentative avant de s'arrêter définitivement (et non pas la cinquantième comme j'ai dit en réunion). Et fibonacci(100) microsecondes, cela fait très long. En fait, Damian Conway était au courant de ce problème d'échelle. C'est pourquoi la durée d'attente est plafonnée à 5 secondes. Le script va donc durer, au maximum, 500 secondes, soit un peu moins de 9 minutes. FAUX ! Car même si les délais sont plafonnés à 5 secondes, le programme calcule quand même fibonacci(n), avec la formule récursive, sans mise en cache. Et pour calculer fibonacci(n) avec n au voisinage de 100, il faut énormément de temps. En fait, lorsque j'ai traduit cet exemple de code, j'ai complètement changé le calcul de fibonacci(n). Je n'ai même pas adopté la méthode récursive avec mise en cache. J'ai utilisé les souvenirs d'un exercice de terminale sur les suites récurrentes et j'ai codé une formule qui donne directement la valeur de fibonacci(n) sans récursion ni itération. Pour ceux qui n'ont pas peur de mathématiques niveau terminale C, voir en annexe la discussion détaillée du programme en question.
Damian Conway a diffusé plusieurs modules à l'occasion de l'écriture de Perl Best Practices. L'un d'eux, Class::Std était destiné à illustrer la programmation orientée objet avec, notamment, l'implémentation par les « objets inversés » (inside-out objects). En fait, il me semble avoir lu que Damian ne souhaitait plus maintenir son module et recommandait l'utilisation de Object::InsideOut à la place. Mais comme je ne me souviens plus où j'ai lu cela, je vous livre cette information sous toutes réserves.
Charles évoque sa tentative pour écrire un article sur CGI.pm, pour montrer comment aborder la programmation de pages web dynamiques simples. Hélas, il lui a été répondu que :
Delenda est CGI.pm
Si l'on veut un vrai site web dynamique, il vaut mieux utiliser un vrai framework qui permet de séparer la partie graphique de la partie programmation du site, de façon à pouvoir faire évoluer le style d'ensemble sans avoir besoin de changer la logique des programmes. Mais pour une approche qui utilise une seule page dynamique, pourquoi ne pas utiliser CGI.pm ?
Néanmoins, Charles s'est intéressé à un framework, à savoir Jifty. Mais pour pouvoir utiliser Jifty, comme tous ses concurrents, d'ailleurs, il faut installer une palanquée de modules.
Et Charles se pose une grave question au sujet de la page d'accueil de Jifty. Pourquoi cette image avec un poney attelé à un traineau ? David explique que c'est une référence culturelle propre à London.pm et qu'il n'en sait pas plus. Il cite également une présentation de Larry Wall à une conférence Perl, où il a dit en substance :
Et maintenant, il faut que je parle d'un poney. Je ne comprend pas pourquoi, mais on m'a demandé d'en parler.
Et il y a eu également la tentative de programmer Perl 5 sur la machine Parrot. Ce projet s'appelait Ponie, le rétroacronyme pour : Perl On a New Internal Engine.
Récemment, Jérôme est allé à Lyon pour son travail. Mais il n'a pas réussi à joindre BooK pour qu'ils puissent convenir d'une soirée impromptue des Mongueurs de Lyon.
Par un curieux retour des choses, il y avait au Maldoror deux belges à une table voisine. Lorsqu'ils ont quitté le Maldoror, ils nous ont dit quelques mots pour nous signaler qu'ils étaient actuellement sur Paris pour un stage de formation chez Red Hat, stage que Jérôme suivait aussi. C'est par Jérôme qu'ils ont eu l'adresse du Maldoror et ils espéraient le voir le soir-même. Ils ont bien aimé ce restaurant. Et ils sont partis un quart d'heure, peut-être même seulement 10 minutes avant l'arrivée de Jérôme, coincé par un problème administratif et un logiciel qui n'aide pas.

Internet

Nous n'avons pas vraiment parlé d'Internet, mais de son précurseur, le minitel. David a lu que cela fonctionnait encore. Il doit rester deux ou trois sites qui tournent, en plus du 3611, l'annuaire électronique. Ce dernier reçoit encore environ un million d'appels par mois. France Télécom avait l'intention de supprimer le minitel, mais ils ont renoncé en constatant qu'il était encore utilisé.
Et puisque nous parlions de l'annuaire électronique, la discussion a dérivé vers les numéros 118-xxx. Les gens ont été submergés par la complexité des différents tarifs proposés par les différents opérateurs. Et ils se sont tournés vers les autres solutions, comme l'annuaire sur le web. Du coup, non seulement les opérateurs sont obligés de se partager le marché, mais en plus, le marché, tous opérateurs confondus, a été divisé par deux. [ Une objection consiste à signaler que les tarifs des opérateurs de téléphones portables sont beaucoup plus complexes que ceux des numéros 118-xxx. Cette objection est réfutée en remarquant d'une part que les abonnés à la téléphonie portable se posent la question du tarif une seule fois, le jour où ils souscrivent un abonnement, alors que la question pour les numéros 118-xxx revient à chaque utilisation. D'autre part, chercher un numéro sur un annuaire, imprimé, électronique ou téléphoné, n'est pas une activité essentielle de la vie courante. Tandis que raconter ses peines de coeur à son téléphone et à tout un wagon d'usagers de la SNCF, c'est aussi fondamental que de se nourrir et de respirer. ]

Informatique

Théo a commenté le compte-rendu de janvier, notamment le passage sur la stéganographie, qui n'avait pas donné lieu à discussion mais que j'ai inclus car cela suivait naturellement un autre point. Il évoque l'exemple du message dissimulé dans une carcasse de lièvre. Théo aurait tendance à admettre qu'il s'agit bien de stéganographie, alors que je pense qu'il s'agit plutôt de camouflage. Il évoque un autre exemple qui figure dans le livre mais dont je n'ai pas parlé dans le compte-rendu, l'exemple de l'esclave sur le crâne duquel on a tatoué un message, puis que l'on a envoyé quelques jours plus tard rejoindre le destinataire, une fois que ses cheveux avaient repoussé. Et en fait, l'exemple habituel de stéganographie, c'est le fichier image sur lequel on trafique quelques bits de poids faibles à des endroits convenus pour y inscrire le message.
Une technique voisine de la stéganographie, mais qui n'apparaît pas dans le livre Casseurs de Codes, c'est le watermarking, que je traduirais par « filigrane ». Cette technique consiste à introduire des variations imperceptibles dans les différentes copies d'un film (ou d'une oeuvre d'un type quelconque), pour pouvoir analyser une copie pirate et retrouver de quelle copie légitime elle provient. C'est une technique ardue, car il faut que le filigrane reste imperceptible, y compris par quelqu'un qui déroule le film image par image (ce qui interdit d'intercaler une image subliminale), il faut que le filigrane reste même si le pirate réduit la résolution de l'image ou la cadence (nombre d'images par seconde). Il faut même que le filigrane soit repris si la copie se fait par un procédé en partie analogique, comme le spectateur qui se pointe au cinéma avec son caméscope pour filmer en douce le film pendant sa projection. Si on laisse tomber le caractère d'imperceptibilité, on peut remarquer que le marquage des films existe depuis longtemps. Ainsi, Pathé (et non Gaumont comme j'ai commencé par dire) ajoutait l'image d'un coq sur les films, pour éviter le piratage. Plus près de nous, les chaînes de télévision avaient l'habitude d'ajouter leur logo dans un coin de l'image. Parfois, les chaînes se rachetaient entre elles des reportages ou des extraits de compétitions sportives. Lorsqu'elles diffusaient des images achetées, elles marquaient bien au début « Images Canal+ » ou « Images FR3 », mais elles masquaient le logo de la chaîne d'origine.
Jérôme évoque les problèmes associés à la cryptographie, comme la PKI (infrastructure de clés publiques). Il évoque également le problème de monnaie électronique, en exposant certains critères que doit respecter un système de monnaie électronique basé sur quelque chose qui ressemble à un certificat numérique. Il faut un équilibre entre traçabilité (pour éviter que quiconque crée des certificats à la demande, l'équivalent d'imprimer de la fausse monnaie) et l'anonymat (le banquier ne doit pas savoir en quoi a consisté l'achat qui a donné lieu au transfert d'un certificat numérique monétaire, le marchand ne doit pas savoir par où est passé le certificat monétaire qu'il reçoit, et ainsi de suite).
Laurent a un nouveau téléphone portable. Il ne maîtrise pas encore toutes les fonctionnalités. Néanmoins, Laurent a déjà constaté des fêlures dans la coque de protection du téléphone. Il va essayer de la faire changer.
Laurent voudrait également changer de laptop. Il nous a demandé des conseils, mais nous n'avons pas d'avis bien défini sur le sujet.
Lorsque j'ai évoqué le module IO::Prompt ci-dessus, j'ai évoqué un souvenir plus ancien, lorsque le client chez qui j'étais en prestation installait R2 de l'éditeur allemand SAP. C'était en 1989 et c'était la version sur MVS. À l'époque, la traduction était loin d'être parfaite. Lors de l'affichage d'une page d'aide en ligne, il était courant de commencer à la lire en anglais, de poursuivre en français et de terminer en allemand. La « I18N » (internationalisation) du logiciel était encore moins évidente. Une collègue chargée de former des utilisateurs nous avait évoqué les regards ahuris qui lui avaient fait face lorsqu'elle avait dit :
Dans ce champ, vous tapez « J » pour « oui » ou « N » pour « non ».
Pour ceux qui utilisent Windows, il faut savoir que vous devez faire un peu de ménage de temps en temps. Notamment, détruire le contenu du répertoire temporaire, celui dont le nom est contenu dans la variable %TEMP%. Laurent a remarqué que lorsque ce répertoire contient un millier de fichiers, les temps de réponse du système commencent à se dégrader de façon notable. Le fait que la plupart de ces fichiers ont une taille nulle n'y change rien. C'est l'encombrement de la table du répertoire qui dégrade les performances, pas l'encombrement du disque. Cela me fait penser que je devrais faire cette manip moi aussi au travail. Je défragmente régulièrement mon disque, mais j'ai oublié qu'il fallait aussi nettoyer les répertoires temporaires.

Divers

Pour revenir à la longue discussion du mois dernier sur les plans de métro, Théo me raconte qu'il a appris à connaître Paris par le métro, ayant peu de temps pour se promener en surface. Il a donc une vision plus topologique que géographique de Paris.
David nous raconte qu'il a entendu parler d'un dancing « bio » aux Pays-Bas. Dans ce dancing, la piste de danse est montée sur des vérins ou appareils du même genre. Les mouvements des danseurs actionnent ces vérins, qui du coup produisent de l'électricité. Ainsi, l'éclairage du dancing ne consomme pas de courant en provenance du secteur. Certains mettent en doute l'autonomie énergétique du dancing, estimant que la récupération de l'énergie mécanique des danseurs permettra tout au plus d'allumer deux diodes. [ Il existe un autre dancing du même genre à Londres. Et il n'y a pas que les participant à notre réunion qui doutent de la véracité de cette anecdote. ]
Jérôme nous évoque d'autres expériences de production de l'énergie, qui prennent place à la Réunion. L'une de ces expériences consiste à recueillir l'énergie des vagues pour générer de l'électricité. Une autre expérience, plus conventionnelle, consiste à utiliser l'énergie géothermique. Le problème est que l'usine doit être installée dans un site naturel très particulier qui, du coup, sera complètement dénaturé. La troisième expérience est de la TESF. Par analogie avec la TSF, j'ai deviné en quoi consistait cette expérience. Il s'agit de « Transmission d'Électricité Sans Fil ». Il reste à savoir ce qui arrivera aux oiseaux qui auraient la mauvaise idée de traverser le flux d'« électricité sans fil ».
Jérôme évoque également une route de la Réunion. C'est une route en corniche, entre Saint-Denis et la Possession, qui nécessite un travail important pour les soubassements, construits à l'aide de tétrapodes en béton. Or, à chaque cyclone, la route est endommagée par des éboulis de la falaise terre/roche volcanique qui la surplombe, et il faut la dégager, voire la reconstruire par endroits.
Les effets de la crise sur Red Hat sont difficiles à estimer, car ils résultent de deux tendances contradictoires. D'un côté, cela apportera à Red Hat des clients qui veulent migrer d'un système propriétaire vers un système libre et moins cher. D'autre part, d'autres clients de longue date risquent de se tourner vers un Linux communautaire, plutôt que de continuer à payer des prestations à Red Hat. Laquelle de ces deux tendances contradictoires prévaudra ?
Chez BPI, la boîte de David, la crise se fait sentir d'une manière très différente. L'activité de BPI consiste à faciliter le reclassement de personnes au chômage, avec des conseils et des formations. Avec la crise, l'activité de BPI bat son plein.
Et les autres entreprises ? Certaines licencient les employés par paquets de neuf. Pourquoi ce nombre ? Parce qu'à partir de 10 licenciements, il faut faire un plan social. D'autre part, si une entreprise licencie pour des motifs économiques, elle ne peut pas réembaucher une personne pour le même poste. En effet, si l'employé précédent a été licencié pour motif économique, c'est que le poste n'est pas rentable, quelle que soit la personne qui l'occupe. Mais une entreprise peut embaucher pour un autre poste. Qu'observe-t-on avec ces règles ? Certaines entreprises licencient des employés pour raison économique, puis embauchent d'autres personnes à d'autres postes. Bien que la description des postes supprimés et celle des postes créés n'ont rien à voir, les personnes qui occupent les nouveaux postes se retrouvent à faire exactement le même travail que celles dont les postes ont été supprimés. Et comme il s'agit de débutants, le salaire n'est pas le même.
Au sujet des entretiens d'embauche, nous avons évoqué le test de l'hôtesse d'accueil. Le test d'embauche ne commence pas lorsque vous entrez dans le bureau de la personne qui vous interroge et il ne se termine pas lorsque vous sortez de ce bureau. Il commence quand vous vous présentez à l'hôtesse d'accueil et il se termine lorsque vous quittez le bâtiment. Et un mois plus tôt, BooK nous avait envoyés deux liens décrivant cette pratique.
Olivier n'a presque pas parlé de Vélib' cette fois-ci. Quelqu'un d'autre a abordé le sujet et lui a demandé s'il faisait encore du farming. Hélas non, ce n'est plus possible. En effet, il y a un délai de cinq minutes entre le moment où vous déposez un vélo et le moment où vous en reprenez un autre. Cela ôte beaucoup d'intérêt à cette pratique. Peut-être que si l'abonné a deux cartes d'abonnement, il a le droit de prendre immédiatement un autre vélo ?
C'est la même chose pour les passes Navigo [ et les coupons de Carte Orange, qui ont cessé d'exister ]. Il faut attendre cinq minutes avant de pouvoir franchir de nouveau un portillon. Le but est d'empêcher les gens de partager un même passe (ou un même coupon) pour franchir le portillon. Mais le système vérifie-t-il qu'il n'y a pas deux utilisations quasi simultanées du même passe à deux extrémités opposées de Paris ?
Toujours est-il que l'on peut avoir une bonne raison pour franchir deux fois un portillon en quelques minutes. Cela m'est arrivé un soir, à la station RER de Saint-Ouen. La station est, très approximativement, orientée nord-sud. Je suis arrivé par l'entrée sud, la plus proche de mon travail. À cette entrée, il n'y a aucun guichet, juste un écran qui affiche les prochains trains. Une fois sur le quai, aucun écran n'affichait la liste des prochains trains, tous affichaient uniquement le premier train à venir, avec la liste des stations desservies. Quelques minutes après mon arrivée, les panneaux ont annoncé que ce train était supprimé. L'écran de l'entrée sud affichant la liste des prochains trains étant en dehors de la zone payante, je suis allé jusqu'à l'entrée nord. Là aussi, il fallait sortir pour pouvoir lire l'écran qui énumérait les prochains trains. Je suis sorti de la zone payante pour lire cet écran. Et j'ai pu constater qu'un autre train arriverait quelques minutes plus tard, après le passage théorique du train supprimé. Mais j'étais coincé, je n'avais pas le droit de revenir dans la zone payante avant le délai de cinq minutes, c'est-à-dire après le passage du train. Heureusement, en raison des grosses difficultés de circulation, une personne de la station Saint-Ouen a décidé d'ouvrir les portillons de sortie pour permettre aux usagers de passer sans activer leur passe ou leur coupon.
Quelles sont les informations stockées sur le passe Navigo ? Il semblerait que le passe mémorise seulement les deux derniers trajets. D'un autre côté, le site central de la RATP mémorise les informations pendant 48 heures (certains sites annoncent plutôt 24 heures). Certains participants au mauvais esprit traduisent cela en : « Le STIF s'engage à transmettre les données à la DST dans les 48 heures, puis à les purger. »
Lors de son déplacement à Lyon, Jérôme a vu l'atelier d'entretien des trains de la SNCF. Cela lui rappelle que, lorsqu'il était au service militaire, au milieu des années 90, il a eu l'occasion de discuter avec une personne bien au courant de ce qui se passe à la SNCF. Cette personne lui a raconté, entre autres, que le rythme de l'entretien des rames avait été réduit de moitié, sans réduire le rythme de la circulation. Alors forcément, ça a plus de chances de casser...
Il a été question de Battlestar Galactica. Moi, j'en étais resté aux deux films de la fin des années 70 que j'avais vus et dans lesquels Starbuck était interprêté par Dirk Benedict et dans lesquels les pilotes étaient munis d'un casque avec tout plein de petites loupiotes qui leur éclairaient le visage : très pratique pour les reconnaître à l'écran, mais cela devait bousiller leur vision nocturne. Dans la version actuelle, non seulement les loupiotes de casque ont disparu, mais en plus Starbuck est maintenant une femme. Étant donné que cela se pratique chez nous aux XXI^e siècle, un changement de sexe doit être possible également à l'époque de Galactica. Non, me dit-on, dans la nouvelle version, Starbuck est de sexe féminin et a toujours été de sexe féminin.

Annexe : analyse en détail de l'exemple `Ch10.069_Best`

L'analyse de cet exemple couvre une bonne partie du programme de mathématiques de terminale C à l'époque où j'étais au lycée : probabilités, exponentielles et logarithmes, suites récurrentes, avec une allusion fugace aux nombres complexes.

Voici le code de l'exemple :

##############################################################################
##   Code fragment (Recommended) from Chapter 10 of "Perl Best Practices"   ##
##     Copyright (c) O'Reilly & Associates, 2005. All Rights Reserved.      ##
##  See: http://www.oreilly.com/pub/a/oreilly/ask_tim/2001/codepolicy.html  ##
##############################################################################


# Standard modules...
use strict;
use warnings;
use IO::Prompt;
use Carp;
use English qw( -no_match_vars );
use Data::Alias;
use Readonly;


Readonly my @CONFIG_PATHS
    => qw( dev/config dev/config/alt ~/config /usr/config );

Readonly my $REMOTE_SERVER => 'foobar@foo.bar';
Readonly my $MAX_TRIES     => 100;

Readonly my $QUIT => qr/\A q(?:uit)? \z/ixms;

sub init_from  {
    return sleep 2;
}

sub connect_to {
    my ($server, $opt_ref) = @_;
    use List::Util qw( min );
    sleep min(5,$opt_ref->{timeout}/1e6);
    return rand > 0.99 ? 'pipe' : undef;
}

my @fibonacci;
sub fibonacci {
    my ($n) = @_;
    return 1 if $n < 2;
    return $fibonacci[$n] ||= fibonacci($n-1) + fibonacci($n-2);
}

my $prompt_str = '> ';

use Smart::Comments;
 

for my $possible_config ( @CONFIG_PATHS ) {  ### Initializing...  done

    init_from($possible_config);
}
 
my $connection;
TRY:
for my $try (1..$MAX_TRIES) {                ### Connecting to server...  done

    $connection = connect_to($REMOTE_SERVER, {timeout=>fibonacci($try)});
    last if $connection;
}
croak "Can't contact server ($REMOTE_SERVER)"
    if not $connection;
 
# Interactive portion of the program starts here...

while (my $cmd = prompt($prompt_str, -fail_if=>$QUIT)) {
    remote_execute($connection, $cmd) 
        or carp "Unknown command: $cmd";
}


sub remote_execute {
    my ($connection, $cmd) = @_;
    print "remotely executing via $connection: $cmd\n";
    return 1;
}

Si vous examinez le programme, vous voyez que la fonction connect_to a 99 % de chances d'échouer à chaque tentative et que le programme effectuera 100 tentatives avant d'abandonner définitivement. Quelle est la probabilité d'aller jusqu'à la centième itération et d'échouer à cette ultime tentative ? C'est 0,99¹⁰⁰. Et combien cela fait-il ? Si vous vous souvenez de vos cours de mathématiques, vous devriez savoir que lorsque n est suffisamment grand, (1 + x / n)ⁿ est proche de exp(x). La valeur 0,99¹⁰⁰ en est un cas particulier avec x =-1 et n = 100. Donc, la probabilité est voisine de 1 / e, soit plus d'une chance sur trois. Vérification :
```
$ perl -E 'say exp(-1), " ", .99**100'
0.367879441171442 0.366032341273229
```
Combien font fibonacci(100) microsecondes concrètement ? On peut en calculer un ordre de grandeur de tête. Tout d'abord, je commence par rappeler un exercice de mathématiques que j'ai eu en terminale. Il s'agissait de démontrer que si une suite vérifie la formule de récurrence
f(n + 1) = a f(n) + b f(n - 1)
et si l'équation
x² = a x + b
admet deux racines distinctes r et r' (éventuellement complexes), alors il existe deux coefficients lambda et mu tels que, pour tout entier n,
f(n) = lambda rⁿ + mu r'ⁿ
Dans le cas de la suite de Fibonacci, r est égal au nombre d'or, (1 + sqrt(5)) / 2, soit environ 1,618, tandis que r' est égal à (1 - sqrt(5)) / 2, soit -0,618 environ. Quant à lambda et mu, ils sont donnés par le système d'équation :
```
lambda   + mu    = 1 = fibonacci(0)
lambda r + mu r' = 1 = fibonacci(1)
```
Pour calculer de tête, j'arrondis les coefficients des équations en
```
    lambda +     mu = 1
1,6 lambda - 0,6 mu = 1
```
En substituant mu par 1 - lambda, on obtient :
```
2,2 lambda - 0,6 = 1
```
soit
```
lambda = 1,6 / 2,2 = 8 / 11 = 0,727272...
```
La valeur exacte, obtenue par une résolution sur papier, est :
```
lambda = (5 + sqrt(5)) / 10 = 0,7236...
```
Pour n = 100, on peut négliger le terme basé sur r' et donc calculer 8 / 11 x 1,618¹⁰⁰. Prenons une autre partie du programme de math de terminales, les logarithmes. Logarithmes décimaux en l'occurrence. On sait que log(2) vaut environ 0,3. Donc, log(16) = 1,2 et log(1,6) = 0,2. Finalement, log(1,6¹⁰⁰) est égal à 20. Donc, fibonacci(100) microsecondes font de l'ordre de 10²⁰ microsecondes, soit 10¹⁴ secondes ou si vous voulez 100 000 milliards de secondes. Et si vous préférez les moyens électroniques de calcul :
```
$ time perl -E 'say (((1 + sqrt(5)) / 2) ** 100 * (5 + sqrt(5)) / 10)'
5.73147844013819e+20
real    0m0.007s
user    0m0.003s
sys     0m0.003s
$ time perl -MMemoize -E 'sub fib{ my($n)=@_; return $n<2 ? 1 : fib($n-1)+fib($n-2) }; memoize("fib"); say fib(100)'
5.73147844013817e+20
real    0m0.032s
user    0m0.025s
sys     0m0.004s
```
soit 573 000 milliards de secondes. Si vous vous souvenez qu'un milliard de secondes équivaut à 31 ans et 7 mois, vous vous rendez compte que ça fait un bon bout de temps, rien que pour la centième tentative, laquelle est précédée par les 99 autres ! Quant aux esprits chagrins qui s'offusquent que je me sois trompé d'un facteur 5 ou 6, je leur réplique que j'ai pris log(1,6) = 0,2 pour faciliter les calculs, alors que la véritable valeur est log(1,6) = 0,20411 et que j'aurais même dû prendre log(1,618) = 0,20898. Et comme il y a une multiplication par 100, l'absence du 0,00898 se fait sentir, même si elle est légèrement compensée par l'oubli de lambda = 0,7236. Finalement, l'utilisation de time dans ces deux lignes est un peu malhonnête : lorsque Ch10.069_Best modifié par l'ajout de Memoize calcule fib(100), il a déjà calculé (et mis en cache) fib(99) et fib(98). Donc, la version avec Memoize devrait être plus rapide que la version avec le nombre d'or.
Et maintenant, pourquoi plafonner les délais ne donne-t-il pas les résultats escomptés, c'est-à-dire un délai de 500 secondes dans le pire des cas ? Comme je l'ai écrit plus haut, c'est parce que le programme calcule les nombres de Fibonacci par la méthode récursive et sans mise en cache. Calculons le nombre appels(n) d'appels récursifs nécessaires pour calculer fibonacci(n). C'est une suite récurrente définie par :
```
appels(0) = 1
appels(1) = 1
appels(n + 1) = appels(n) + appels(n - 1) + 1
```
Calculons les premiers éléments de la suite et mettons les en regard de la suite de Fibonacci.
```
n   appels(n) fibonacci(n)  2.fibonacci(n)
0        1          1            2
1        1          1            2
2        3          2            4
3        5          3            6
4        9          5           10
5       15          8           16
```
Il est assez clair que l'on a la relation
```
appels(n) = 2.fibonacci(n) - 1
```
et ensuite, il est facile de la démontrer pour tout entier n. Donc, pour calculer fibonacci(100), il faut environ 1,14.10²¹ appels récursifs. Si vous comptez une nanoseconde par appel récursif, vous pouvez calculer que cela fait encore un paquet de temps !

Finalement, la version traduite de ce programme a été

#############################################################################
##            Fragment de code (Recommandé) du chapitre 10 des             ##
##             « Règles de l'Art de la Programmation en Perl »             ##
##   Copyright © O'Reilly & Associates, 2005, 2006. Tous droits réservés   ##
##  Cf. http://www.oreilly.com/pub/a/oreilly/ask_tim/2001/codepolicy.html  ##
#############################################################################

# Modules standards
use strict;
use warnings;
use IO::Prompt;
use Carp;
use English qw( -no_match_vars );
use Data::Alias;
use Readonly;

Readonly my @CHEMINS_CONFIG
    => qw( dev/config dev/config/alt ~/config /usr/config );

Readonly my $SERVEUR_DISTANT => 'foobar@foo.bar';
Readonly my $MAX_TENTATIVES  => 100;

Readonly my $QUIT => qr/\A q(?:uit(?:ter)?)? \z/ixms;

sub init_a_partir_de  {
    return sleep 2;
}

sub connecter_a {
    my ($server, $opt_ref) = @_;
    use List::Util qw( min );
    sleep min(2, $opt_ref->{timeout}/1e6);
    return rand > 0.99 ? 'pipe' : undef;
}

Readonly my $PHI  => (1 + sqrt(5)) / 2;
Readonly my $COEF => (5 + sqrt(5)) / 10;

sub fibonacci {
    my ($n) = @_;
    return int(.5 + $COEF * $PHI ** $n);
}

my $chaine_invite = '> ';

use Smart::Comments;

for my $config_possible ( @CHEMINS_CONFIG ) {  ### Initialisation...  fini

    init_a_partir_de($config_possible);
}

my $connexion;
TENTATIVE:
for my $tentative (1..$MAX_TENTATIVES) {                ### Connexion au serveur...  fini

    $connexion = connecter_a($SERVEUR_DISTANT, {timeout=>fibonacci($tentative)});
    last if $connexion;
}
croak "Impossible de contacter le serveur ($SERVEUR_DISTANT)"
    if not $connexion;

# la partie interactive du programme commence ici

while (my $cmd = prompt($chaine_invite, -fail_if=>$QUIT)) {
    execution_distante($connexion, $cmd)
        or carp "Commande inconnue: $cmd";
}

sub execution_distante {
    my ($connexion, $cmd) = @_;
    print "Exécution distante via $connexion : $cmd\n";
    return 1;
}

Ça va nettement plus vite, n'est-ce pas ? Faut-il penser que l'auteur n'a pas testé Ch10.069_Best ? Je pense qu'en fait, il l'a testé avec $MAX_TENTATIVES initialisé à 5 ou 10, puis qu'il a passé ce nombre à 100 au moment de stocker ce script dans l'archive à télécharger. Ou bien, peut-être que le calcul récursif de la suite de Fibonacci a eu lieu sur un ordinateur quantique, in parallel, in multiple universes, in constant time.

Retour aux Mongueurs

Vérification du HTML