1

[sondage=15486]
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

2

t'as oublié "j'aime pas le caml" ds ton sondage tongue
avatar
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez par ici :)

3

hmm, même si on n'aime pas, il y a une bonne raison de préférer l'un des deux!
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

4

Quand on sait ce que ca fait peut-être.
Déjà tu précise pas que c'est du CAML => Obiwan Kenobi
avatar

5

oulà, ça a un succès fou tritop
de toute façon ce n'est pas le même usage, List.fold_left correspond au parcours récursif terminal, donc c'est forcément utile bcp plus souvent (surtout que ça exigerait de définir une fonction auxiliaire avec un argument supplémentaire si on voulait s'en passer), alors List.fold_right n'est pas récursif terminal (donc ça bouffe O(n) octets sur la pile tritop), et peut de toute façon être remplacé facilement par un pattern-matching sans avoir à définir une fonction auxiliaire ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

6

BookeldOr :
hmm, même si on n'aime pas, il y a une bonne raison de préférer l'un des deux!

Pollux :
oulà, ça a un succès fou tritop
de toute façon ce n'est pas le même usage, List.fold_left correspond au parcours récursif terminal, donc c'est forcément utile bcp plus souvent (surtout que ça exigerait de définir une fonction auxiliaire avec un argument supplémentaire si on voulait s'en passer), alors List.fold_right n'est pas récursif terminal (donc ça bouffe O(n) octets sur la pile tritop), et peut de toute façon être remplacé facilement par un pattern-matching sans avoir à définir une fonction auxiliaire ^^


roooh t'enlèves tout le mythe là trifouet
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

7

oui, désolé d'apporter une infime partie de la lumière de la Sagesse dans le monde ténébreux des camlistes #triclasse#

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

8

Tiens l'autre jour, je pensais que ça serait pas mal que les compilos C (en particulier gcc) donnent la liste les fonctions qu'ils réussissent à rendre recursive terminales.
(Par exemple, int main(){main();} génère un Segmentation fault en -O0 mais pas en -O2 ... (sur ma version en tous cas)).
avatar
fabetal_ > Hier, je me suis fait monter par un pote
redangel > et en chevals, ça donne quoi?
Nil> OMG I think I'm gay

9

De toute façon c'est tellement flexible, la récursivité terminale... tongue

Et puis la récursivité terminale n'est pas une propriété de la fonction, c'est une propriété de l'appel : il faudrait donc marquer l'appel spécialement pour spécifier qu'il doit être récursif terminal, par exemple tail_recursion(main,()), ou, puisqu'on ne peut appeler récursive-terminale-ment que la fonction en cours (enfin je sais pas, peut-être que certains compilos peuvent faire ça avec n'importe quelle fonction ?), tail_recursion() tout court ^^

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

10

ben un tail-call c'est juste un appel de fonction dont on renvoie directement le résultat non ? donc je ne vois pas pourquoi ça serait spécialement limité à la fonction en cours confus (en gros l'idée c'est juste que tu remplaces (en pseudo-assembleur) "call bidule; return" par juste "goto bidule" car c'est équivalent). Mais en fait je ne vois pas trop comment le compilateur pourrait avoir du mal à déterminer si un appel est un tail-call ou pas, genre en C c'est un tail-call si c'est l'argument de return, point, c'est pas vraiment compliqué si ?
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

11

sauf pour les fonctions qui renvoient void, dans ce cas-là c'est un tail-call si c'est la dernière instruction avant la fin de la fonction... (en optimisant les sauts inutiles et tout ça)
et c'est spécifié par aucune norme, sans compter que ça pourrait interférer avec les optimisations du compilo (i.e. si le compilo s'amuse à déplacer certaines instructions après l'appel, c'est foutu), et qu'en C++ avec RTTI c'est même pas la peine d'y penser si y a des objets avec un destructeur non-trivial dans la scope de l'appel ^^

Pour ce qui est de "call bidule; return" : c'est un peu plus compliqué que ça, puisqu'une fonction a souvent des choses à libérer sur la pile, donc entre le "call" et le "return". C'est vrai qu'avec une convention d'appel style "la fonction appelée dépile tous ses arguments puis retourne", ton tail call ne pose pas de problème :
bidule:
    move.w (a7)+,d0
    add.w (a7)+,d0
    rts

appelant:
    move.w (a7)+,d0
    bne return
    move.w d0,-(a7)
    move.w d0,-(a7)
    bra bidule
return
    rts

Mais avec la convention cdecl utilisée avec la majorité des compilos, ce n'est possible que si la fonction appelante reçoit plus d'arguments sur la pile que la fonction appelée, ce qu'on pourrait éventuellement forcer artificiellement (si appelant qui a 1 argument appelle bidule à 2 arguments, dire à tout le monde de considérer qu'appelant en a 2 même si on n'en utilise qu'1), mais ça casserait la compilation séparée sad Et on peut avoir des bonnes raisons d'utiliser cdecl (autres qu'historiques), notamment parce que ça doit être plus efficace pour le processeur (sinon il faut empiler *d'abord* le PC, empiler les arguments et ensuite utiliser une instruction de saut sans empilement du PC : c'est plus logique de faire saut et empilement en une seule étape).

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

12

*nils*nils* $ cat > test.c
int g(int x);
int f(int x) {return (x == 0 ? x : g(x));}
int g(int x) {return f(x - 1);}
int main() {return g(1000000000);}
*nils*nils* $ gcc -O2 test.c
*nils*nils* $ ./a.out
*nils*nils* $
Donc il le fait ^^ (par contre en -O simple il sature la mémoire en quelques secondes (mais ça segfaulte pas, enfin j'ai pas attendu qu'il sature aussi le swap hein grin))
(et accessoirement les warnings devraient être activés par défaut, je comprenais pas pourquoi ça terminait pas avec "x = 0" mur)

Sinon, pour les fonctions void, ben on pourrait les mettre en argument du return justement pour spécifier qu'on veut l'optimisation, ça serait une manière de marquer l'appel spécialement comme tu le proposais en ./9 mais sans inventer un nouveau truc ^^
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

13

ça marche aussi comme ça
*nils*nils* $ cat > test.c
int g(int x);
int f(int x) {return (x == 0 ? x : g(x));}
int main() {return (g(1000000000));}
*nils*nils* $ gcc -O2 -c test.c
*nils*nils* $ cat > test2.c
int f(int x);
int g(int x) {return f(x-1);}
*nils*nils* $ gcc -O2 -c test2.c
*nils*nils* $ gcc -O2 test.o test2.o
*nils*nils* $ ./a.out
*nils*nils* $
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

14

Ah oui comme ça ça marche, mais dans le cas que j'ai cité (taille de la liste des arguments inférieure pour l'appelant) gcc se met à faire une récursion normale... Bref si les types des arguments ne sont pas rigoureusement identiques, c'est pas terrible parce que c'est complètement platform-dependent sorry (sur une plateforme, sizeof(int)=sizeof(long)=sizeof(machin *), et sur une autre pas du tout)

« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)

15

Oui je viens de tester en ajoutant des arguments inutiles à g, et ça me rebouffe toute la mémoire, effectivement. Par contre si je m'amuse à remplacer int par void* ça optimise pareil, donc il doit bien s'appuyer sur la taille des arguments sur la pile et non sur la signature de la fonction...
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#