1Introduction à la programmation fonctionnelle

Introduction `a la programmation fonctionnellePhilippe Mullerseptembre 2004Philippe MullerIntroduction `a la programmation fonctionnelleIntroduction `a la programmation fonctionnelleObjectif du cours:R´efl´echir aux principes de base de la pro-grammation et de l"informatique `a traversl"apprentissage d"un langage simple maispuissant.Diff´erenceentre"programmation" (concept abstrait)"programmation sur machine" (r´ealisation particuli`ere d"unprocessus de conception).→relative ind´ependance du langage vis `a vis des probl`emes deprogrammationle choix du langagetient `a deux choses:puissance d"expression pour r´esoudre des probl`emes complexesetfacilit´e d"utilisation et d"apprentissage pour se concentrer surl"essentiel→choix de la programmation fonctionnellenPhilippe MullerIntroduction `a la programmation fonctionnelleLa programmation fonctionnelle?concept fondamental:l"abstractiontraiter une chose complexe en ladivisant en choses plus simples et en ignorant les d´etails.objets de base :la fonctionun programme est un ensemble defonctions traitant des donn´ees d"entr´eedes langagesinterpr´et´esinstructions / interpr´et´e au fur et `a mesure ->machine?= langages compil´es :instructions / pr´eparation (compilation) / executionavantage/ inconv´enients´evaluation / d´ebuggage plus soupleplus lent (mais on peut toujours compiler)Philippe MullerIntroduction `a la programmation fonctionnelleLe langage choisi : Camella programmation fonctionnelle est une famille de langage tr`esproches, dont le plus c´el`ebre est LISP d´evelopp´e au MIT.le successeur de LISP: scheme: plus l´eger, plus simple et aussipuissant, utilis´e pour l"´education ou le scriptage (ex: Gimp)mais pas de typage des donn´ees; on utilisera donc un autre langagefonctionnel typ´e:CamelPhilippe MullerIntroduction `a la programmation fonctionnelleA retenirprocessus de calcul :ˆetres abstraits mis en oeuvre dans les ordinateurs;donn´ees :ou information, objets manipul´es par les processus;programme :contrˆole ´evolution des processus;langage de programmation :traduit les processus de fa¸con symboliqueinterpr`ete :traduit les processus ´ecrit dans un langage deprogrammation.Philippe MullerIntroduction `a la programmation fonctionnelleElements de base de la programmationLe langage de programmation :permet de donner des instructions;constitue un cadre d"organisation des processus decalcul.Pour la programmation on distingue souvent deux sortes "d"objets":les donn´ees(par ex. les nombres)les proc´edures(par ex. l"addition de nombres)Philippe MullerIntroduction `a la programmation fonctionnelleElements du langagedes expressions primitives(nombres, fonctions de base)des moyens de compositionpour construire des expressions composeesd"expressions primitivesdes moyens d"abstractionpour nommer et manipuler des objetscompos´es comme un tout, comme si c"´etait une expressionprimitive.Philippe MullerIntroduction `a la programmation fonctionnelleLes expressionsl"interpr`ete Camel ´evalue des expressions> Caml Light version 0.74#1230 ;;- : int = 1230la r´eponse pr´ecise letypede la r´eponse avec sa valeur.# 10 + (3*4);;- : int = 22+, /, * sont desop´erateursd´ecrivant desproc´edures primitives, lesnombres sont desexpressions primitives.Une expression compos´ee est form´ee `a partir d"expressions (primitives ounon) et d"op´erateurs, termin´ee par;;3????expressionoperateur????+ (5?4)????expression;;Philippe MullerIntroduction `a la programmation fonctionnelleLes types de base d"expressionsles entiers(int) : les nombres entiers relatifs.les r´eels(float) : nombres d´ecimaux.1.67les bool´eens: le vrai (true) et le faux (false).les caract`eres(char) :"a" "X" "&"les chaˆınes de caract`eres(string) "bonjour"Les op´erateurs n"acceptent que certains types comme arguments.

Parexemple, + ne prend que des entiers :# "toujours" + 29 ;;Entr´ee interactive:> "toujours" + 29 ;;> ^^^^^^^^^^Cette expression est de type string,mais est utilis´ee avec le type int.Philippe MullerIntroduction `a la programmation fonctionnelleLes d´efinitionsPour manipuler des objets, n´ecessit´e de les nommer: l"op´erateurlet# let j = 20 ;;j : int = 20# 30 - j ;;- : int = 10# let k = 3* j + 27;;k : int = 87La d´efinition est le moyen de base de l"abstraction.Elle permet :de repr´esenter le r´esultat d"op´erations compos´ees;de construire des objets complexes par ´etapes?d´eveloppement et testincr´ementaldes programmes.Pour cela il faut pouvoir d´efinir desproc´edures, moyen d"abstraction pluspuissant que le nommage d"un objet, en nommant des op´erationscompos´ees `a partir de param`etres.Philippe MullerIntroduction `a la programmation fonctionnelleLes fonctionsn´ecessit´e de manipuler des fonctions, avec param`etres de diff´erentessortes, en nombre diff´erents→besoin d"abstraire les fonctionsce qui d´efinit une fonction :ses param`etres(appel´es variables enmaths) et la fa¸con dont on la calcule;Par ex. carre : x→x*xmais une fonction peut l"ˆetre de plusieurs choses: l"´energie cin´etiqueen physique,EC: m v→1/2mv2Pour d´efinir une fonction on sp´ecifie donc les param`etres et le corps:let cinetik m v = 0.5 *. m *. v *. v ;;retourne la fonctioncinetik : float -> float -> float = A l"application d"une fonction, par ex.(cinetik 75.5 25.9), lesparam`etres formels sont remplac´es par les valeurs fournies.Philippe MullerIntroduction `a la programmation fonctionnelleLes expressions conditionnellesUne expression conditionnelle permet l"´evaluation d"une expressiondiff´erenci´ee selon une condition (vrai ou fausse).

Par exemple la d´efinitionde la valeur absolue est une expression conditionnelle :|x|=xsi 0≤x-xsinonElle se traduit en Camel parlet abs x = if x >=0 then xelse -x ;;Philippe MullerIntroduction `a la programmation fonctionnelleConditionnelles (suite)On peut utiliser les op´erateurs suivants sur les conditions (bool´eens):=´egalit´e (op´erateurpolymorphe)or"ou" logique&"et" logiquenotn´egationexercice :xc then melse c);;On peut d´efinir plusieurs liaisons (´evalu´ees ind´ependamment) :let max3 a b c =let m1=(max a b)and m2=(max b c)in (max m1 m2);;si plusieurs d´efinitions successives sont n´ecessaires, il faut imbriquer:let a = 3.2/.53.5 in let b = a *. a in Philippe MullerIntroduction `a la programmation fonctionnelleLes proc´edures et les structures de bloc : nomslocauxles noms des param`etres d"une proc´edure sont locaux au corps de laproc´edure; le nom d"un param`etre de fonction est unevariable li´ee(le sens de l"expression ne change pas si on renomme le param`etre).une variable qui n"est pas li´ee est librel"ensemble des expressions pour lesquelles une liaison d´efinit un nomest appel´ela port´eede ce nom.les variables li´es d´eclar´ees comme param`etre d"une proc´edure ontpour port´ee le corps de cette proc´edure.les variables libres ont pour port´ee le corps du programme.Philippe MullerIntroduction `a la programmation fonctionnelleLes proc´edures et les structures de bloc : liaisonslocalesSur l"exemple de la racine carr´ee, le programme est compos´ee deproc´edures s´epar´ees, permettant le contrˆole de l"usage des noms.?inconv´enient : seul l"appel `aracineest utile vu de l"ext´erieur (ce quipeut ˆetre un probl`eme pour les gros programmes)?on peut enfermer les sous-proc´edures avec desliaisons locales.let racine x =let rec ameliore estimation x =(moyenne estimation (x /. estimation))and assez_bon estimation x =(abs_float ((carre estimation) -. x)) < 0.0001in let rec racine1 estimation x =if (assez_bon estimation x)then estimationelse (racine1 (ameliore estimation x) x)in racine1 1.0 x ;;Philippe MullerIntroduction `a la programmation fonctionnelleStructure de donn´ees compos´eesJusqu"ici on a vu uniquement des donn´ees primitives, des types fournispar le langage.Pour la plupart des probl`emes on a besoin de repr´esenter des donn´eesplus complexes.De mˆeme qu"`a partir de proc´edures simples on peut faire des proc´edurescompos´ees, on peutconstruiredes types.on veut faire une proc´edure qui donne le min et en mˆeme temps le maxde deux entiers.

Mais une fonction ne renvoie qu"une valeur.→on peut utiliser un type compos´e de deux valeurs: un doublet.Notation : (2,3)let minmax x y = if x < y then (x,y) else (y,x);;let minmax x y = (min x y), (max x y);;De mˆeme on peut utiliser des triplets, des n-uplets (tuples).Philippe MullerIntroduction `a la programmation fonctionnelleUtilisation des doubletsComment r´ecuperer une valeur de doublet?let zorgbl x y =let m = minmax x yin (2 * (fst m) + (snd m));;let zorgbl x y =let (m1,m2) = minmax x yin (2* m1 + m2);;Philippe MullerIntroduction `a la programmation fonctionnelleInt´erˆetregrouper des donn´ees li´ees intrins`equement dans un seul objet.Exemple : les vecteurs.Si on ´ecrit une somme de 2 vecteurs (`a deux dimensions):let som_vect x1 y1 x2 y2 = (x1+x2),(y1+y2) ;;Plus structur´e (plusabstrait):let som_vect v1 v2 = (fst v1)+(fst v2), (snd v1)+(snd v2);;Philippe MullerIntroduction `a la programmation fonctionnelleLes ListesSi on a besoin d"un nombre quelconque (et qui peut ´evoluer) de donn´eessimilaires, on ne peut se contenter de tuples (ex: dictionnaire de mots).Pour cela on peut utiliser deslistes: une liste est un ensemble de donn´eesde mˆeme type.on note une liste[ donnee1; donnee2; ; donneep ][ 2; 19; 16; 23; 20 ]La liste vide est not´ee[]On peutextrairedes ´el´ements d"une liste grˆace aux deux op´erationssuivantes,hd(head),tl(tail):hd [ 23; 45; 78 ];;retourne23tl [ 23; 45; 78 ];;retourne[ 45; 78 ]On peutconstruireune liste avec les op´erateurs suivants :23::[ 45; 67 ]retourne[ 23; 45; 67][96; 23]@[ 45; 67 ]retourne[ 96; 23; 45; 67]Philippe MullerIntroduction `a la programmation fonctionnelleLes ListesLa liste est un type r´ecursif:une liste est::→la plupart des fonctions de listes peuvent etre exprim´es de fa¸conr´ecursive.Ex: compter les ´el´ements d"une liste :let rec compter une_liste =if une_liste=[] then 0else (1 + compter (tl une_liste));;Philippe MullerIntroduction `a la programmation fonctionnelleExercices1comment acc´eder au 3e ´el´ement de[1; 2; 3; 4; 5]2comment acc´eder `a l"´el´ement 7 de[ [1; 2; 3]; [2; 7] ]3construire les listes avec:: et @1[1;2] ajout´e devant l2[1;2] ajout´e `a l1 et [3;4]3l et 1 `a la fin4une liste avec 1 ajout´e devant l1 et 3 devant l2Philippe MullerIntroduction `a