Semaine 4 – récursion terminale (tail recursion), persistance, plus de syntaxe

photo en cc-by par Jan Ramroth

, par Pierre

Récursion terminale / tail recursion (pour éviter les débordements de pile / stock overflow). Du sucre syntaxique pour la correspondance de motifs (match with, gardes de motifs, regroupement de motifs, alias). Quelques explications sur la façon dont ocaml gère la mémoire pour nous : en particulier sur la représentation mémoire des types de données immuables, comme les listes, donnant un avant-goût de la persistance et le ramassage automatique des miettes (garbage collecting).

Il est temps de donner un lien vers un bon support de cours, pour vous permettre de compléter vos notes de cours par un texte de référence.

Le support de cours de Jean-Christophe Filliâtre est un texte que vous pouvez étudier en entier par vous même en complément de mon cours. Avec l’aimable accord de son auteur voici un lien vers son cours d’initiation à la programmation fonctionnelle (choisir le pdf) https://www.lri.fr/~filliatr/m1/cours-ocaml.en.html

Certaines parties de cours de la semaine 4 ont été faites au tableau.

La mise en évidence du l’optimisation par gcc des appels récursifs terminaux en langage C, ayant partiellement échouée cellé-ci attendra de plus amples explications lors d’un prochain cours.

  1. (* 1) Nouvelles formes syntaxiques *)
  2.  
  3. (* forme favorite *)
  4. let cube = function x -> x*x*x;;
  5. (* autre forme (rappel) *)
  6. let cube x = x * x * x;;
  7. (* rappel sur let ... in ... et and *)
  8. let x = 2;;
  9. let z =
  10. let x = 4
  11. and y = x - 1
  12. in x + y
  13. ;;
  14. z;;
  15. y;;
  16.  
  17. (* let in pour une fonction "interne" *)
  18. let cube x =
  19. let carre_inner n = n * n
  20. in
  21. (carre_inner x) * x;;
  22.  
  23. cube 3;;
  24. cube;;
  25. carre_inner;;
  26.  
  27.  
  28. type parite =
  29. Impair | Pair;;
  30.  
  31. (* recursion mutuelle *)
  32. let rec
  33. choux = function
  34. | 0 -> Pair
  35. | 1 -> Impair
  36. | n -> fleur (n - 1)
  37. and
  38. fleur = function
  39. | 0 -> Impair
  40. | 1 -> Pair
  41. | n -> choux (n - 1);;
  42. choux 1;;
  43. choux 2;;
  44. fleur 451;;
  45.  
  46.  
  47. (* pattern matching match with *)
  48.  
  49. type truc = Bidule | Machin | Chose of int | Truc of int;;
  50.  
  51. Chose 4;;
  52.  
  53. let identite = function
  54. x ->
  55. (function
  56. | Chose n -> n
  57. | Truc _ -> 0
  58. | Machin -> 2
  59. | Bidule -> -1) (Chose x) ;;
  60.  
  61. (* l'expression suivante : *)
  62. (function | m1 -> e1
  63. | m2 -> e2 | ...) e;;
  64.  
  65. (* s'écrit plus simplement : *)
  66. match e with
  67. | m1 -> e1
  68. | m2 -> e2
  69. ...;;
  70.  
  71. let identite = function
  72. x -> match Chose x
  73. with
  74. | Chose n -> n
  75. | Truc _ -> 0
  76. | Machin -> 2
  77. | Bidule -> -1
  78. ;;
  79. identite 56;;
  80.  
  81. (* cube avec une valeur speciale en zero *)
  82. let zcube z = function
  83. | 0 -> z
  84. | n -> n * n * n;;
  85. zcube (-12) 0;;
  86. zcube 0 (-12);;
  87.  
  88. (* arguments dans l'autre ordre avec match *)
  89. let zcube x z = match x
  90. with
  91. | 0 -> z
  92. | n -> n * n * n;;
  93. zcube 0 (-12);;
  94. zcube (-12) 0;;
  95.  
  96. (* gardes de motifs avec when *)
  97. let abscube = function
  98. | 0 -> z
  99. | n when n < 0 -> -n * n * n
  100. | n -> n * n * n;;
  101. ;;
  102.  
  103. (* rappel du type d'exemple *)
  104. type truc = Bidule | Machin | Chose of int | Truc of int ;;
  105.  
  106. (* regroupement de cas *)
  107. let f = function
  108. | Bidule -> 1
  109. | Chose n -> n
  110. | Truc _
  111. | Machin -> e
  112. ;;
  113.  
  114. let f = function
  115. | Bidule
  116. | Machin -> 0
  117. | Chose n
  118. | Truc n -> n
  119. ;;
  120.  
  121. let f = function
  122. | Chose _ (* <- n ne passerait pas *)
  123. | Bidule
  124. | Machin -> 0
  125. | Truc n -> n
  126. ;;
  127.  
  128. let f = function
  129. | Bidule
  130. | Machin -> 0
  131. | Chose n
  132. | Truc n when n > 0 -> n
  133. | Chose n
  134. | Truc n -> 1
  135. ;;
  136.  
  137. f (Chose (-10));;
  138.  
  139. (* alias avec as *)
  140. let f = function
  141. | Bidule
  142. | Machin as b -> (b, 0)
  143. | Chose n
  144. | Truc n as b -> (b, n)
  145. ;;
  146.  
  147.  
  148. (* Bonne pratique: eviter les catch all _ *)
  149. let f = function
  150. | Chose n -> n
  151. | Truc _ -> 0
  152. | _ -> 42 (* mauvaise pratique *)
  153. ;;
  154. (* etendre le type truc ne levera pas de warning ici *)
  155. (* preferer le regroupement des cas restants au _ *)
  156.  
  157. let f = function
  158. | Chose n -> n
  159. | Truc _ -> 0
  160. | Bidule | Machin _ -> 42 (* mieux *)
  161. ;;
  162.  
  163. (* Gestion memoire *)
  164. let rec concatenation s t =
  165. match s with
  166. | [] -> t
  167. | x::xs -> x::(concatenation xs t);;
  168.  
  169. (* persistance (au tableau) *)
  170.  
  171. (* recursion terminale / Tail Recursion (au tableau) *)
  172.  
  173. (* avec une fonction de portée local *)
  174.  
  175. (* Mise sous forme recursive terminale (pas toujours possible) *)
  176.  
  177. (* la fonction longueur suivante n'est pas TR *)
  178.  
  179. let rec longueur l = match l with
  180. | [] -> 0
  181. | x::xs -> 1 + longueur xs;;
  182.  
  183. (* on peut la réecrire ainsi : *)
  184. let rec longueur_tr l acc =
  185. print_int acc;
  186. match l with
  187. | [] -> acc
  188. | x::xs -> longueur_tr xs (acc + 1);;
  189. (* cette fonction est TR *)
  190. (*Exemple de réductions successives *)
  191. longueur_tr [10;20;30] 0;;
  192. longueur_tr [20;30] 1;;
  193. longueur_tr [30] 2;;
  194. longueur_tr [] 3;;
  195. 3;;
  196.  
  197. (* internaliser cette version tail recursive *)
  198. let longueur l =
  199. let rec longueur_tr l acc
  200. = match l with
  201. | [] -> acc
  202. | x::xs ->
  203. longueur_tr xs (acc + 1)
  204. in
  205. longueur_tr l 0
  206. ;;
  207. (* ainsi on utilise simplement la fonction longueur a un argument *)
  208.  
  209. (* factorielle en version TR ? *)
  210. let factorielle n =
  211. let rec facttr n r =
  212. print_string "facttr ";
  213. match n with
  214. |0-> r
  215. |n -> facttr (n-1) (r*n)
  216. in facttr n 1;;
  217. factorielle 5;;
  218.  
  219. (* liste_aleatoire en TR *)
  220. open Random;;
  221.  
  222. let rec lia n = match n with
  223. | 0 -> []
  224. | n -> (Random.int 100000)::(lia (n - 1));;
  225. lia 300000;;
  226.  
  227. let lia n =
  228. let rec tr n l = match n with
  229. | 0 -> l
  230. | n -> tr (n - 1) ((Random.int 10000000)::l)
  231. in
  232. tr n []
  233. ;;
  234. lia 3000000;;
  235.  
  236. (* est_croissante l retourne vrai ou faux *)
  237. (* selon si la liste est croissante *)
  238. let rec est_croissante = function
  239. | [] -> true
  240. | x::[] -> true
  241. | x::y::l -> (x <= y) &amp;&amp; (est_croissante (y::l));;
  242.  
  243. est_croissante [1;2;3;4;5];;
  244. est_croissante [1;2;3;4;2;5];;
  245. (* TODO a mettre sous forme récursive terminale ... *)

Télécharger

Revenu et logement, Je livre ici quelques éléments de comparaison concernant mon niveau de vie, pour couper court à quelques idées reçues, et un condensé de nombreuses (...)
Revenu et travail d’un enseignant-chercheur, Cet article complète l'article Revenu et logement, en détaillant un peu le budget de mon ménage, mon parcours d'enseignant-chercheur en terme de (...)
Cybersyn (el systemo synco), Au café, mardi 5 avril 2011, j'ai bien vu que, mis à part Antoine Allombert, personne ne connaissait l'histoire de l'extraordinaire projet chilien (...) [jpg, jpg, png]