Journal Chantonnons en récursion

Posté par  (site web personnel) . Licence CC By‑SA.
Étiquettes :
32
22
nov.
2012

Dernièrement, je parlais, avec une connaissance (ça me change de parler tout seul), du très célèbre Yusuf Islam. De cette conversation, l'envie de ré-écouter un peu de sa musique m'a prise à la gorge et je me suis décidé à acheter, légalement, sur iTunes (si ce lien a la couleur d'un lien déjà visité, ne bougez pas, la police arrive) , quelques un de ses grands tubes.

Au détour de la chanson "Can't keep it in", j'entends ce petit passage lyrique, qui semble sans conséquence mais qui est effectivement dramatique :

Love is my blood
Blood spin my head
And my head fall in love

En bon psychopathe de l'informatique que je suis, je n'ai pu me retenir de penser que la pile d'appel allait exploser !

Si on met ça en C, ça donnerait un code ressemblant à ça :

void love(void);
void blood(void);
void head(void);

void love(void) {
  blood();
}

void blood(void) {
  head();
}

void head(void) {
  love();
}

int main(int argc, char ** argv) {
  love();
  return 0;
}

Depuis cette chanson, je pense tous les jours à la récursion. En fait, écouter cette chanson me fait penser à la récursion, penser à la récursion me fait penser à cette chanson, penser à cette chanson me fait écouter cette chanson … aaaargh :

void think_recurs(void);
void think_cantkeepitin(void);
void listen_cantkeepitin(void);

void think_recurs(void) {
      think_cantkeepitin();
}

void think_cantkeepitin(void) {
      listen_cantkeepitin();
}

void listen_cantkeepitin(void) {
      think_recurs();
}

int main(int argc, char ** argv) {
      listen_cantkeepitin(); /* c'est la ou tout a commence */
      return 0; /* jamais */
}

Voilà, voilà … Je vous laisse à vos occupations et je vais signer le registre d'entrée que me propose ce gentil monsieur en blouse blanche.

PS: Désolé, un des effets de bords de la chanson intitulée "Can't keep it in", soit "Peux pas le contenir", c'est qu'on ne peut pas le contenir et donc on en fait un journal (après avoir forcé toutes ses connaissances à écouter dix fois la chanson).

  • # ...

    Posté par  . Évalué à 6.

    Mais… mais… mais… on n'est pas déjà Vendredi ?

  • # It's not time to make a change

    Posté par  (site web personnel) . Évalué à 4.

    Comme il le dit si bien :

    Etienne,
    It's not time to make a change,
    Just relax, take it easy.
    You're still young, that's your fault,
    There's so much you have to know.
    Find a girl, settle down,
    If you want you can marry.
    Look at me, I am old, but I'm happy.

    Celui qui a échappé à la foudre en parle volontiers

  • # "Tail call optimization"

    Posté par  . Évalué à 7.

    pile d'appel allait exploser !

    Et pourquoi? Il existe des langages sans possibilité d'écrire une boucle où la répétition ne peut être fait que par récursion, pourtant la pile d'appel n'explose pas.

    • [^] # Re: "Tail call optimization"

      Posté par  (site web personnel) . Évalué à 3.

      Il faut pour cela que la fonction soit récursive terminal, ce qui est rarement le cas sans accumulateur.

      "La première sécurité est la liberté"

      • [^] # Re: "Tail call optimization"

        Posté par  . Évalué à 5.

        Tous ses exemples sont justement récursifs terminal

        • [^] # Re: "Tail call optimization"

          Posté par  (site web personnel) . Évalué à 1.

          C'est pour ça que mon argument sur la chronologie de la chanson et de l'apparition du tail call tient mieux la route :D

          "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

        • [^] # Re: "Tail call optimization"

          Posté par  (site web personnel) . Évalué à 3.

          Et justement, sauf erreur de ma part, GCC supporte l'optimisation tail-call (ou tail-recursion).

          • [^] # Re: "Tail call optimization"

            Posté par  . Évalué à 2.

            L'optimisation de queue consiste à simplement mettre à jour les arguments de des argument dans la pile et à faire un jump sur la première instruction de la fonction au lieux de les empiler une nouvelle fois et de faire un call.
            Là, il n'y a pas une fonction, mais trois. C'est pas possible de faire tourner ça sur place (il n'y a qu'un seul sommet de pile). Sauf si gcc remarque que ce code est compilable sans récursion, ce qu'il fait (gcc 4.7 avec -O2, les fonctions a, b et c sont là pour l’empêcher « d'optimiser » le programme en "while(1);"

            head:
    subq    $8, %rsp
    xorl    %eax, %eax
    call    c
    addq    $8, %rsp
    jmp love #au lieu de faire un appel récursif. 

blood:  
    subq    $8, %rsp
    xorl    %eax, %eax
    call    b
    addq    $8, %rsp
    jmp head

love:   
    subq    $8, %rsp
    xorl    %eax, %eax
    call    a
    addq    $8, %rsp
    jmp blood

            Please do not feed the trolls

            • [^] # Re: "Tail call optimization"

              Posté par  (site web personnel) . Évalué à 2.

              Tiens c'est marrant, j'ai à peu près le même code assembleur avec SBCL (Common Lisp) :

              (defun love ()
  (blood))
(defun blood ()
  (head))
(defun head ()
  (love))

(love)


              * (disassemble 'love)
; disassembly for LOVE
; 0AB39BB2:       8B05889BB30A     MOV EAX, [#xAB39B88]       ; #<FDEFINITION object for BLOOD>
                                                              ; no-arg-parsing entry point
;       B8:       31C9             XOR ECX, ECX
;       BA:       FF7504           PUSH DWORD PTR [EBP+4]
;       BD:       FF6005           JMP DWORD PTR [EAX+5]
NIL
* (disassemble 'blood)
; disassembly for BLOOD
; 0AB529DA:       8B05B029B50A     MOV EAX, [#xAB529B0]       ; #<FDEFINITION object for HEAD>
                                                              ; no-arg-parsing entry point
;       E0:       31C9             XOR ECX, ECX
;       E2:       FF7504           PUSH DWORD PTR [EBP+4]
;       E5:       FF6005           JMP DWORD PTR [EAX+5]
NIL
* (disassemble 'head)
; disassembly for HEAD
; 0AB6990A:       8B05E098B60A     MOV EAX, [#xAB698E0]       ; #<FDEFINITION object for LOVE>
                                                              ; no-arg-parsing entry point
;       10:       31C9             XOR ECX, ECX
;       12:       FF7504           PUSH DWORD PTR [EBP+4]
;       15:       FF6005           JMP DWORD PTR [EAX+5]
NIL

              La version en Scheme ne fait pas de stack overflow non plus :

              (define (love) (blood))
(define (blood) (head))
(define (head) (love))
(love)

              • [^] # Re: "Tail call optimization"

                Posté par  . Évalué à 2.

                En Haskell c'est rigolo aussi :

                -- love.hs
love  = blood
blood = head
head  = love

main = love


                > ghc -XNoImplicitPrelude  love.hs
> ./love
love: <<loop>>

                Par contre la version suivante boucle :

                import Prelude ((>>), return)
love  =  blood
blood = head
head = return () >> love

main = love

                C'est plus « naturel » comme comportement, main étant de type IO (), l'inférence de types remonte jusqu’à head et le trouve de type IO () aussi, et donc l’évaluation de return () est stricte (love en a besoin).

                Please do not feed the trolls

            • [^] # Re: "Tail call optimization"

              Posté par  (site web personnel) . Évalué à 2.

              Pour info en OCaml :

              let rec love ()  = blood ()
and blood () = head ()
and head ()  = love ()

let _ = love ()

              Cela donne :

               00401ee0 <_camlTt__code_begin>:
  401ee0:   b8 01 00 00 00          mov    $0x1,%eax
  401ee5:   eb 19                   jmp    401f00 <_camlTt__love_1030>
  401ee7:   89 f6                   mov    %esi,%esi
  401ee9:   8d bc 27 00 00 00 00    lea    0x0(%edi,%eiz,1),%edi

 00401ef0 <_camlTt__blood_1031>:
  401ef0:   b8 01 00 00 00          mov    $0x1,%eax
  401ef5:   eb e9                   jmp    401ee0 <_camlTt__code_begin>
  401ef7:   89 f6                   mov    %esi,%esi
  401ef9:   8d bc 27 00 00 00 00    lea    0x0(%edi,%eiz,1),%edi

 00401f00 <_camlTt__love_1030>:
  401f00:   b8 01 00 00 00          mov    $0x1,%eax
  401f05:   eb e9                   jmp    401ef0 <_camlTt__blood_1031>
  401f07:   89 f6                   mov    %esi,%esi
  401f09:   8d bc 27 00 00 00 00    lea    0x0(%edi,%eiz,1),%edi

              "La première sécurité est la liberté"

      • [^] # Re: "Tail call optimization"

        Posté par  (site web personnel) . Évalué à 2.

        Que vient faire l'accumulateur ici? On s'en fiche qu'il y ait un accumulateur ou pas. Si on n'utilise pas la valeur de retour, on s'en fiche complètement !

    • [^] # Re: "Tail call optimization"

      Posté par  (site web personnel) . Évalué à 9.

      Cat Stevens a sortit ça en 1972, le "tail call optimization" date de 1977 (si je ne me trompe pas). Donc la pile d'appel explose et j'en veux pour preuve qu'il émet une sorte de "Oooaaaargh" après avoir chanté la dernière ligne de texte, certainement lié à l'explosion de la pile.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

    • [^] # Re: "Tail call optimization"

      Posté par  . Évalué à 3.

      Dans le cas présent ça donne une boucle infinie alors, pas sûr que ça soit mieux..

      • [^] # Re: "Tail call optimization"

        Posté par  . Évalué à 6.

        Bein au moins ça ne plante pas… beaucoup de programmes sont des boucles infinies

  • # récurrence transfinie.

    Posté par  . Évalué à 2.

    Moi c'est la chanson « Those were the days » qui m'a fait un effet assez bizarre.

    J'étais en pleine théorie des ordinaux, à me poser des questions d'ordinaux successeurs, d'ordinaux limites et de récurrences transfinies et en écoutant la radio, j'entends:«
    Those were the days my friend
    We thought they'd never end
    We'd sing and dance forever and a day »

    J'ai immédiatement pensé ω+1 et à chaque fois que je bossais mes ordinaux, j'entendais la chanson dans ma tête.

    • [^] # Re: récurrence transfinie.

      Posté par  . Évalué à 1.

      Ce serait intéressant de coder ça en LISP, tiens…

      • [^] # Re: récurrence transfinie.

        Posté par  (site web personnel) . Évalué à 2.

        Si je ne me méprends pas trop :

        (defun sing ()
  (print 'sing))
(defun dance ()
  (print 'dance))

(defun day (n)
  (sing)
  (dance)
  (day (1+ n)))

(day 0)

        Et ça sing et dance forever effectivement :-)

        • [^] # Re: récurrence transfinie.

          Posté par  . Évalué à 2.

          Tu te méprends.

          Ton code tourne « forever » et pas « forever and a day ».

          1+ω=ω mais ω+1>ω

          C'est l'une des joies des ordinaux. L'addition n'est pas commutative.

  • # Crash, boucle infinie, ou programme vide ?

    Posté par  (site web personnel) . Évalué à 10.

    Je copie ton premier programme dans dlfp.c et j'essaye, sans optimisation

    $ gcc  dlfp.c && ./a.out
Segmentation fault

    Crash, stack overflow… Normal: Récursion infinie, et chaque étape de la récursion prends un peu plus de mémoire sur la stack.

    Mais attends,.. toutes tes fonctions sont des Récursion_terminale ce qui fait que, avec des optimisation, le compilateur transforme les appels de fonction en simple sauts, qui ne prennent plus aucune mémoire sur la stack.

    gcc -O2 dlfp.c && ./a.out 
^C

    Avec des optimisation, le programme de crash plus et est coincé dans une boucle infinie. Je dois faire Ctrl+C pour l'arrêter.

    Mais un programme C correct ne peut pas entrer dans une boucle infinie
    La spécification du C est très claire à ce sujet.
    Un compilateur assez intelligent peut remarquer que ce programme n'a pas d'effet secondaire, et juste retourner 0.

    $ clang -O2 dlfp.c && ./a.out 
$

    Avec clang, tout le code a été optimisé et le programme ne fait plus rien et termine immédiatement.

    À lire aussi: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

    • [^] # Re: Crash, boucle infinie, ou programme vide ?

      Posté par  . Évalué à 6.

      Mais un programme C correct ne peut pas entrer dans une boucle infinie

      Le problème de l'arrêt étant indécidable, ça m'étonnerait que ça rentre dans la définition d'un code "correct".

    • [^] # Re: Crash, boucle infinie, ou programme vide ?

      Posté par  (site web personnel) . Évalué à 8.

      Mais un programme C correct ne peut pas entrer dans une boucle infinie

      Je suis septique sur ce point. Certains types de programmes doivent être une boucle infinie, comme les systèmes d'exploitation ou les daemon ou encore dans l'embarqué.

      "It was a bright cold day in April, and the clocks were striking thirteen" - Georges Orwell

      • [^] # Re: Crash, boucle infinie, ou programme vide ?

        Posté par  (site web personnel) . Évalué à 5.

        Il y a des exceptions:

        A loop that, outside of the for-init-statement in the case of a for statement,
        - makes no calls to library I/O functions, and
        - does not access or modify volatile objects, and
        - performs no synchronization operations (1.10) or atomic operations (Clause 29)
        may be assumed by the implementation to terminate. [ Note: This is intended to allow compiler transfor- mations, such as removal of empty loops, even when termination cannot be proven. — end note ]

      • [^] # Re: Crash, boucle infinie, ou programme vide ?

        Posté par  . Évalué à 1.

        Le mot important dans la phrase, c'est "correct", dans le sens "correct pour la norme C". Dans le texte original, ca doit être "well formed".

        Bref, ça n'empêche pas d'écrire et compiler les programmes auxquels tu penses. Ces programmes vont répondre au besoin (peut-être), tourner indéfiniment (sauf bug), donc fonctionner correctement du point de vue de l'utilisateur. Par contre, du point de vue de la norme, il n'est pas "bien formé", parce qu'il ne se termine pas.

      • [^] # Re: Crash, boucle infinie, ou programme vide ?

        Posté par  . Évalué à 9.

        Je suis sCeptique sur ce point

        En même temps vu ce que tu écoutes. ça m'etonnes pas que tu aies des goûts de chiotte => []

    • [^] # Re: Crash, boucle infinie, ou programme vide ?

      Posté par  . Évalué à 2. Dernière modification le 22 novembre 2012 à 17:41.

      Tout de même très étonnant, j'ai fait quelques tests :

      En -O0 : Segmentation fault
      En -O1 : Quitte sans erreur, même "$?" == 0
      En -O2 : Boucle infinie
      En -O3 : Boucle infinie

      (pas de -Ofast ni -Og sur le gcc que j'ai sous la main)

  • # Commentaire supprimé

    Posté par  . Évalué à 10.

    Ce commentaire a été supprimé par l’équipe de modération.

  • # Oups

    Posté par  (site web personnel, Mastodon) . Évalué à 6. 

     sur iTunes (si ce lien a la couleur d'un lien déjà visité, ne bougez pas, la police arrive)

    Je comprenais pas pourquoi le lien était effectivement de la couleur d'un lien visité (jusqu'à ce que je passe la souris dessus)

  • # Je en suis pas d'accord avec la traduction du programme

    Posté par  . Évalué à 2.

    Alors nous avons

    Love is my blood
    Blood spin my head
    And my head fall in love

    Ce qui donne

    void (*blood)(int);
int head;
love = blood;

void blood() {
    switch(head) {
        case (love << head) :
            head>>1;
            blood();
            break;
        case ((love + sizeof(int) )>> head) :
            head<<1;
            blood();
            break;
      }
}
int main(int argc, char ** argv) {
  blood();
  return 0;
}

    Bon c'est pas forcément mieux (en plus écrit en deux minutes donc surement avec des erreurs) mais c'est plus proche des paroles.

    • [^] # Re: Je en suis pas d'accord avec la traduction du programme

      Posté par  . Évalué à 4. Dernière modification le 23 novembre 2012 à 10:54.

      je suis d'accord pour ne pas être d'accord, pas pas d'accord avec ton accord !

      Moi, je traduit ce qu'il a écrit comme cela :

      void love(void);
void blood(void);
void head(void);

void love(void) {
  blood();
}

void blood(void) {
  head();
}

void head(void) {
  love();
}

int main(int argc, char ** argv) {
  do_something_nice();
  return 0;
}

      Ok, il y a une récursion dans le texte du programme, mais à moins d'en savoir plus sur le début (ou la fin) des paroles, pas moyen de savoir si elle est appelée et donc si cela boucle ou pas !
      S'il n'est jamais amoureux, tout ira bien pour lui.

  • # Vous êtes des malades

    Posté par  . Évalué à 7.

    et c'est ce qui me fait revenir tous les jours ici :)

    L'acacia acajou de l'académie acoustique est acquitté de ses acrobaties. Tout le reste prend "acc".

  • # Pour aller plus loin

    Posté par  . Évalué à 1.

    Je n'ai guère le temps, mais pour ceux qui voudraient persévérer dans le codage superflu et jubilatoire, il y a aussi ce grand moment culturel des années 70, qui sollicitera un peu plus la pile:

    (Les Charlots)

    Derrière chez moi, savez-vous quoi qu'y a
    Derrière chez moi, savez-vous quoi qu'y a
    Y a un bois, le plus joli des bois
    Petit bois derrière chez moi
    Et tralon la lonlère, et tralonla lonla
    Et tralon la lonlère, et tralonla lonla
    Et dans ce bois savez-vous quoi qu'y a
    Et dans ce bois savez-vous quoi qu'y a
    Y'a une godasse, la plus jolie des godasses
    La godasse dans le bois
    Petit bois derrière chez moi
    Et tralon la lonlère, et tralonla lonla
    Et tralon la lonlère, et tralonla lonla
    Et dans cette godasse, savez-vous quoi qu'y a
    Et dans cette godasse, savez-vous quoi qu'y a
    Y'a un pneu, le plus joli des peneu
    Le peneu dans la godasse
    La godasse dans le bois
    Petit bois derrière chez moi
    Et tralon la lonlère, et tralonla lonla
    Et tralon la lonlère, et tralonla lonla
    Et dans le pneu, savez-vous quoi qu'y a
    Et dans le pneu, savez-vous quoi qu'y a
    Y'a un n'almanach, le plus joli des n'almanach
    L'almanach dans le peneu
    Le peneu dans la godasse
    La godasse dans le bois
    Petit bois derrière chez moi
    Et tralon la lonlère, et tralonla lonla
    Et tralon la lonlère, et tralonla lonla
    C'est un dépôt d'ordure qu'il y a derrière chez toi
    C'est un dépôt d'ordure qu'il y a derrière chez toi
    C'est vraiment trop dur, dur, on reste pas là…

    • [^] # Re: Pour aller plus loin

      Posté par  . Évalué à 0.

      Moi c est une chanson de 2 paysans "Chere Élise" et "Chere Eugène" qu'on m'avait apprise à l'époque qui malmenait la stack.
      J'ai simplifié le style car normalement la phrase est répétée et on rajoute chere elise ou chere eugene à la fin de chaque phrase.

      Les paroles qui bouclent:

      il y a un trou dans mon seau
      mais bouche le
      avec quoi faut il le boucher
      avec de la paille
      mais la paille elle n'est pas coupée
      mais coupe la
      avec quoi faut il la couper
      avec la faux
      mais la faux elle n'est pas meulée
      mais meule là
      avec quoi faut il la meuler
      avec la meule
      mais la meule elle n'est pas mouillée
      mais mouille la
      avec quoi faut il la mouiller (pftr)
      avec de l'eau
      oui mais l'eau elle n'est pas puisée
      mais puise la
      avec quoi faut il la puiser
      avec un seau
      oui mais …. (goto line #1)

  • # La plus célèbre de toutes

    Posté par  . Évalué à 3.

    Sinon, en une ligne de bash :

    echo -e {Lundi,Mardi,Mercredi,Jeudi,Vendredi,Samedi}", des patates ;\n"

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.