sondage exclusif - Page 1

[sondage=15486]

t'as oublié "j'aime pas le caml" ds ton sondage

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

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

oulà, ça a un succès fou
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 ), et peut de toute façon être remplacé facilement par un pattern-matching sans avoir à définir une fonction auxiliaire ^^

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
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 ), 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à

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

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

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

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

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

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

*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 ))
(et accessoirement les warnings devraient être activés par défaut, je comprenais pas pourquoi ça terminait pas avec "x = 0" )

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

ç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* $

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 (sur une plateforme, sizeof(int)=sizeof(long)=sizeof(machin *), et sur une autre pas du tout)

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