Re: Programmation Fonctionnelle

Ce que je voulais dire, c'est que si on écrit un algorithme récursif dans un langage avec GC, et qu'on essaie d'y ajouter des malloc/free pour obtenir un algorithme en C par exemple, on se retrouve souvent à vouloir ajouter un free après un appel terminal.

Par exemple (le premier qui me vient en tête, pas forcément le meilleur) :

let rec tri_fusion liste suffixe = match liste with
| [] | [_] -> liste @ suffixe
| _ ->
 let gauche, droite = decoupe liste in
 tri_fusion gauche (tri_fusion droite suffixe)

Si tu dois insérer des malloc/free, la façon la plus naturelle est la suivante :

let rec tri_fusion liste suffixe = match liste with
| [] | [_] -> liste @ suffixe
| _ ->
 let gauche, droite = decoupe liste in
 let result = tri_fusion gauche (tri_fusion droite suffixe) in
 free_list gauche;
 result

(On libère seulement gauche car droite est un suffixe de la liste d'entrée, donc n'es pas possédée par le code appelant).

Si tu veux récupérer un appel terminal, il faut faire une transformation de 'passage de continuation' à la main dans le cas particulier du contexte mémoire: à l'appel récursif, mettre gauche dans une pile de "trucs à libérer après avoir calculé le résultat final":

let rec tri_fusion liste suffixe cadavres = match liste with
| [] | [_] ->
 List.iter free_list cadavres;
 free_list cadavres;
 liste @ suffixe
| _ ->
 let gauche, droite = decoupe liste in
 tri_fusion gauche (tri_fusion droite suffixe) (gauche :: cadavres)

Ça ne se voit pas dans les langages à GC parce que les actions de libération, qui sont bien effectuées après le retour de la fonction, ne sont pas mémorisées dans la pile d'appel mais redécouvertes a posteriori par le GC quand il parcourt l'espace mémoire; ça permet donc d'avoir plus d'appels terminaux.

(Et puis, y'a-tu vraiment des gens qui bossent sur la FP sans GC ? T'as des références récentes ? Je suis curieux...)

ATS est un excellent exemple que j'invite fortement les gens intéressés par la programmation bas niveau et statiquement sûre à regarder. Pour faire de la programmation fonctionnelle sans GC (ou au moins en pouvant décider localement de ne pas l'utiliser), il faut presque nécessairement un système de types linéaires, donc tu peux regarder plus largement dans la littérature de recherche sur les langages à types linéaires -- même si tous ne sont pas orientés contrôle bas-niveau de la mémoire.