Programmation Fonctionnelle Avancée Programmation Fonctionnelle Avancée Organisation Organisation Programmation Fonctionnelle Avancée I 12 cours, dernier cours le 4 décembre. I 12 TP. Premier : 24 septembre. Dernier : 10 décembre. Ralf Treinen I Période des examens : du 5 au 16 janvier, avec une deuxième session du 22 juin au 3 juillet. I Il y a un projet de programmation, mais pas de partiel Université Paris Diderot UFR Informatique I Contrôle de connaissances : Laboratoire Preuves, Programmes et Systèmes 1 [email protected] 30 octobre 2014 3 2 3 ∗ exam I Note 2ème session : max( c ∗ projet + 1 3 ∗ projet + 2 3 ∗ exam2, exam2) Roberto Di Cosmo et Ralf Treinen Programmation Fonctionnelle Avancée Organisation Programmation Fonctionnelle Avancée Organisation Organisation Le projet I http://www.pps.univ-paris-diderot.fr/~treinen/ teaching/pfav/ I Support : copies des transparents I Il y a des ressources en ligne (voir la page web du cours) I Il est indispensable d'assister au cours et aux TD/TP I Les TD sont assurés par Pierre Letouzey I Le sujet détaillé sera mis en ligne plus tard. I Projet complet à rendre (la date limite sera annoncée plus tard). I Soutenance pendant la période des examens en janvier. I Peut être fait en binôme, mais la notation est individuelle. Programmation Fonctionnelle Avancée Organisation Programmation Fonctionnelle Avancée Introduction Pré-requis de ce cours Objectif du cours I Ce cours est la continuation du cours Fonctionnelle PF5 - Programmation du L3. I Mais il peut être suivi par des étudiants qui ont suivi un autre John Carmack Sometimes, the elegant implementation is a function. Not a method. Not a class. Not a framework. Just a function. cours de programmation fonctionnelle en OCaml (même si niveau L1) I ... ... ou un autre langage fonctionnel (Scheme, Haskell). I Dans ce cas vous devrez éventuellement compléter vos connaissances en consultant les ressources indiquées sur la Dans ce cours, nous allons explorer ensemble page web du cours. I Dans le livre Caml avancés de la programmation fonctionnelle en utilisant le langage OCaml I plusieurs aspects Développement d'applications avec Objective I : I I Chapitre 2 : Programmation fonctionnelle I Chapitre 3 : Programmation impérative I Chapitre 7 : Compilation I Chapitre 14 : seulement Modules Simples Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Les fonctions sont des valeurs de première classe Dans les langages dits fonctionnels, les fonctions sont des entités de première classe, i.e. une fonction I peut être construite sans besoin d'être nommée : il y a des expressions dont la valeur est une fonction ; I être dénie et nommée au même moment. Il y a deux mécanismes indépendants : I des expressions fonctionnelles, I lier un identicateur à une valeur (fonctionnelle ou pas). ∗ une v a l e u r f u n c t i o n x −> ( ∗ let definir ∗ let plus ( ( f f = x et fonctionnelle nommer function court = x ;; ∗) x +2;; ∗) x −> une x fonction ;; ∗) Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Les fonctions sont des valeurs de première classe (∗ fonctions d a n s un r e c o r d ∗) type ' a f o o = { n : i n t ; f : ' a −> l e t f o o = { n = 4 2 ; f =fun x −> x } fonctionnels, les fonctions sont des entités de première classe, i.e. une fonction foo . f 33;; foo . f foo . n ; ; ' a} ;; ;; Dans les langages dits I peut être placée à l'intérieur d'une structure de données. I peut être passée en paramètre à une fonction, et retournée comme résultat d'une fonction. ∗ let fonctions ∗ let attention ( ( ( Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle ∗ fp fp = = ( ( ( dans fun x aux fun extraction ( fst fp ) ( fst fp ) ( ( snd ( fst fp ) ( snd x une −> paire . x +1) , ( parantheses −> des fun x +1 , fonctions ∗) fun x −> ∗) −> x d ' une x x ∗x ∗x ) );; );; paire ∗) 42;; fp ) fp ) 10);; 10;; ( ∗ attention aux parantheses Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Les fonctions sont des valeurs de première classe let double x = 2 ∗x ;; ∗ une f o n c t i o n a v e c l e t apply_twice_to f ( apply_twice_to ∗ arguments l e t compose ( un et f g f fun fun fonctionnel n );; ∗) fonctionnels, les fonctions sont des entités de première classe, i.e. une fonction 5;; resultat = ( f Dans les langages dits double , argument n = x fonctionnels −> f (g x );; ∗) I peut être partiellement appliquée ; I peut créée dynamiquement ; I peut être dénie localement à une fonction. compose double ( x compose double double −> x +2);; 10;; ∗) Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Exemples (fonctions4.ml) Exemples (fonctions5.ml) let mul x ( ∗ f o n c t i o n s l o c a l e a une a u t r e f o n c t i o n ∗ ) y = x∗y ; ; (∗ a p p l i c a t i o n p a r t i e l l e ∗) let d o u b l e = mul let 2;; rev let l = aux rec acc = function let scale f k = let scale fun x scale −> ( fun scale x −> −> a c c −> a u x [] = double ∗( f x +1) k in x) ;; 2 10;; | aux rev a :: r [] [1; l 2; ( a : : acc ) r in ;; 3];; Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Liaison statique Exemples (fonctions6.ml) ( ∗ n e s t une v a r i a b l e l i b r e dans f u n c t i o n x−> x ∗ n ∗ ) I en anglais : lexical scoping let multiplier_avec let f = multiplier_avec f n = function x −> 5;; 3;; I Un identicateur libre (c-à-d qui n'est pas un paramètre) dans une expression fonctionnelle garde la liaison de son occurrence let m = textuelle dans le programme. let g let m = I On parle d'une clôture (angl. : closure ) I Tous les langages de programmation modernes suivent cette g 1;; 17;; x = x + m; ; (∗ m e s t l i b r e ∗) 42;; (∗ q u e l e s t l e r e s u l t a t ? ∗) politique. let f x = x + let g y = f let f x = x + 1000;; g 10;; (f 55;; y );; x ∗n ; ; Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Des fonctions de première classe dans Java 8 ! Des fonctions de première classe dans Java 8 ! Exemple : Appeler une procédure qui prend un ltre en argument (Java < 8) : printPersons( roster, new CheckPerson() { public boolean test(Person p) { return p.getGender() == Person.Sex.MALE && p.getAge() >= 18 && p.getAge() <= 25; } } ); Exemple : Appeler une procédure qui prend un ltre en argument (Java 8) : printPersons( roster, (Person p) -> p.getGender() == Person.Sex.MALE && p.getAge() >= 18 && p.getAge() <= 25 ); En Java on est obligé de spécier le type de l'argument. http://docs.oracle.com/javase/tutorial/java/javaOO/ lambdaexpressions.html Voir : On était obligé de créer une classe anonyme. Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Programmation Fonctionnelle Avancée Introduction Programmation fonctionnelle Des fonctions de première classe dans Python ! Des fonctions de première classe dans les maths from functools import reduce reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) envoie (((1 + 2) + 3) + 4) + 5 = 15. I Alonzo Church, debut des années 1930 : Lambda Calculus. I Notation : λx .x + 1 I À l'époque utilisé pour l'étude de la fondation des mathématiques I L'utilisation des lambda en Python est restreinte dû à la distinction entre expressions et instructions. I Pas de typage en Python. I Aujourd'hui : informatique théorique I Voir le cours de Sémantique du M1 Programmation Fonctionnelle Avancée Introduction OCaml Programmation Fonctionnelle Avancée Introduction OCaml Le commencement de l'histoire... ... Core ML Hindley-Milner polymorphic types Damas-Milner type inference First-class functions Programmation Fonctionnelle Avancée Introduction OCaml Programmation Fonctionnelle Avancée Introduction OCaml Histoire d'OCaml Traits intéressants du langage Algebraic data types Pattern matching I 1973 ML Milner (tactiques de preuves pour le prouveur LCF) I 1980 Projet Formel à l'INRIA (Gérard Huet), Categorical Abstract Machine (Pierre-Louis Curien) I 1984-1990 Dénition de SML (Milner) I 1987 Caml (implémenté en Lisp) Guy Cousineau, Ascander Suarez, (avec Pierre Weis et Michel Mauny) I 1990-1991 Caml Light par Xavier Leroy (et Damien Doligez pour la gestion de la mémoire) I 1995 Caml Special Light puis 1996 OCaml (Xavier Leroy, Jérôme Vouillon, Didier Rémy, Michel Mauny) http://events.inf.ed.ac.uk/Milner2012/X_ Leroy-html5-mp4.html ! Voir I Les fonctions fournissent un mécanisme d'abstraction puissant. I Un système de type polymorphe et implicite qui capture beaucoup d'erreurs. I La dénition par cas simplie et sécurise l'implémentation I Pas de pointeurs explicites, GC ecace - programmation de très haut niveau. I Évaluation stricte et structures de données mutables. Programmation Fonctionnelle Avancée Introduction OCaml Programmation Fonctionnelle Avancée Introduction OCaml Exemples (types.ml) Exemples (cases.ml) let index = input_line let dict = [ 1 , " one " ; ( open_in " data " ) ; ; 2 , " two " ] ; ; let l | [] | x [] y :: rest x = y then :: index dict ;; Li st . assoc ( int_of_string x else index ) dict ;; destutter :: [1; 2; Programmation Fonctionnelle Avancée Introduction OCaml Exemples (append.ml) Exemples (mutable.ml) let [] | a rev_append rec l1 −> :: l1 let −> rev_append l (a :: l2 ) ; ; a .(0);; a ;; let rev l a = a .(0) < − l2 l = rev_append −> destutter 2; l2 = with l [];; = destutter Programmation Fonctionnelle Avancée Introduction OCaml match l with −> if Li st . assoc destutter rec match [|1;2;3|];; 5;; 3; (y 4];; (y :: :: rest ) rest ) ;; Programmation Fonctionnelle Avancée Introduction OCaml Programmation Fonctionnelle Avancée Introduction OCaml Inférence de types en OCaml Typage explicite en OCaml I Pas besoin de spécier les types des identicateurs on OCaml I On a le le système trouve le type le plus général. droit de spécier le type des identicateurs (en fait, des expressions quelconques). I Combine concision du code avec la sûreté du typage fort. I Syntaxe : ( <expression> : <type> ) I Java : typage fort (sûr), mais on est obligé de spécier les I Il faut que le type donné soit compatible avec le type trouvé types (lourd). par le compilateur (le même, ou plus restrictif ). I Python : typage dynamique (pendant l'exécution du code). I Il ne s'agit pas d'un mécanisme de conversion de type. Code concis et élégant, mais en perd en sûreté (erreurs apparaissent seulement pendant les tests) Programmation Fonctionnelle Avancée Introduction OCaml Programmation Fonctionnelle Avancée Introduction OCaml Exemples (explicit.ml) Traits intéressants de l'environnement de programmation un outillage avancé ( ∗ s p e c i f i e r un t y p e ∗ ) let (x : int ) = let triple 42;; x = (x , I un toplevel ou REPL (Read-Evaluate-Print Loop) x, I un compilateur bytecode (portable) x );; I un compilateur natif, très performant let triple (x : string ) = (x , let triple x = ( (x , x , x) : x, string ∗string∗string ( ∗ pas un mecanisme de c o n v e r s i o n ∗ ) let (x : float ) = 42;; I un compilateur vers JavaScript (js_of_ocaml) x );; );; I un système de module puissant I une couche objet I des gestionnaires de paquets (en particulier I ... etc. opam) Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Applications Qui utilise OCaml ? Operating systems : Citrix, Xen Les outils de gestion de Xen, l'hyperviseur qui fait fonctionner des millions de machines virtuelles dans le I l'enseignement : ici, par exemple ! I la recherche : Coq, Astree, Ocsigen, Mirage, ... I la communauté : Unison, MLDonkey, ... cloud OCaml has brought signicant productivity and eciency benets to the project. OCaml has enabled our engineers to be more productive than they would have been had they adopted any of the mainstream languages. I l'industrie : Citrix, Dassault, Esterel, Lexi, Jane Street Richard Sharp, Citrix Capital, OcamlPro, Baretta, Merjis, RedHat, ... Voyons quelques exemples concrets sont écrits en OCaml. David Scott, Richard Sharp, Thomas Gazagnaire and Anil Madhavapeddy. Using functional programming within an industrial product group : perspectives and perceptions. International Conference on Functional Programming, 2010. Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Applications Operating systems : Mirage Social networks : Mylife.com Mirage is an exokernel for constructing secure, high-performance network applications across a variety of cloud computing and mobile platforms. Code can be developed on a normal OS such as Linux or MacOS X, and then compiled into a fully-standalone, specialised microkernel that runs under the Xen hypervisor. Since Xen powers most public cloud computing infrastructure such as Amazon EC2, this lets your servers run more cheaply, securely and ner control than with a full software stack. Mirage is based around the OCaml language ... http: // www. openmirage. org Mylife.com est un agrégateur de réseaux sociaux écrit en OCaml, avec plusieurs contributeurs, dont Martin Jambon The ocaml language and its libraries oer a good balance between expressiveness and high performance, and we dont have to switch to lower-level languages when we need high performance. Martin Jambon, Mylife.com Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Applications Finance : JaneStreet Concision L'entreprise JaneStreet utilise OCaml pour son activité de trading. Voilà ce que dit Yaron Minsky dans Yaron Minsky. OCaml for the masses. Our experience with OCaml on the research side convinced us that we could build smaller, simpler, easier-to-understand systems in OCaml than we could in languages such as Java or C#. For an organization that valued readability, this was a huge win. Communications of the ACM, September 2011 Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Applications Bug detection Performance Programmers who are new to OCaml are often taken aback by the degree to which the type system catches bugs. The impression you get is that once you manage to get the typechecker to approve of your code, there are no bugs left. This isn't really true, of course ; OCaml's type system is helpless against many bugs. There is, however, a surprisingly wide swath of bugs against which the type system is eective, including many bugs that are quite hard to get at through testing. We found that OCaml's performance was on par with or better than Java's, and within spitting distance of languages such as C or C++. In addition to having a high-quality code generator, OCaml has an incremental GC (garbage collector). This means the GC can be tuned to do small chunks of work at a time, making it more suitable for soft real-time applications such as electronic trading. Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Applications Pure, mostly Static Analysis : Esterel, Absynthe, Airbus, Facebook ... Despite how functional programmers often talk about it, mutable state is a fundamental part of programming, and one that cannot and should not be done away with. Sending a network packet or writing to disk are examples of mutability. A complete commitment to immutability is a commitment to never building anything real. Esterel code generator written in OCaml. Facebook does sophisticated static analysis using OCaml over their vast PHP codebase to close security holes. Airbus, Absynthe use of Astree, written in OCaml, to prevent bugs in Airbus code. Microsoft SLAM and Static Driver Verier ... Programmation Fonctionnelle Avancée Introduction Applications Programmation Fonctionnelle Avancée Introduction Programmation Fonctionnelle Avancée Nouvelles recentes : OCamlLabs et OCamlPro Le plan preliminaire du cours I Système de modules avancé privés, interfaces, foncteurs ou modules encapsulation, types paramétrés Il y a désormais des initiatives concrètes pour assurer le support I Utilisation avancée du GADT industriel de OCaml : I OCamlPro est une entreprise de service française dédiée au support I OCamlLabs est une structure non-for-prot qui se consacre au dévéloppement d'une plateforme OCaml stable Et ils cherchent des personnes qui aiment bien programmer. I Programmation avec système de types variants polymorphes, combinateurs, DSL I Structures de données fonctionnelles ecaces zippers, les, arbres équilibrés I Analyse de coût amorti, raisonnement équationnel innies et paresseuses : ots (streams) compactes (hash-consing, memoization) Construction modulaire d'interprètes Monades et transformateurs de Monades I Structures de données I Structures de données I I I (Transformations de programmes) I (Concurrence et parallélisme) Programmation Fonctionnelle Avancée Introduction Bibliographie Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Bibliographie Pour commencer : les dénitions par cas I Xavier Leroy et al : The Objective Caml system : documentation and user's manual http://caml.inria.fr Une des caractéristiques les plus appréciées des langages de la famille ML comme OCaml est la dénition par cas : let fact rec −> −> = function | 0 Développement d'Applications avec Objective Caml | n O'Reilly, 2000 disponible en ligne est équivalent au code suivant I Emmanuel Chailloux, Pascal Manoury et Bruno Pagano : I Chris Okasaki : Purely Functional Data Structures Cambridge University Press, 1998 disponible en ligne I Markus Mottl, http://ocaml.info/home/ocaml_sources.html Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Voyons une dénition un peu moins banale : | | | f x y = match true , f a l s e _ , false , elle peut se traduire comme l e t f1 if x if else if x y = then y then 2 e l s e 1 y then 2 e l s e 3 ; ; ∗ n rec fact n=0 t h e n if ( fact (n −1));; n = 1 n else ∗ ( fact (n −1));; Jusqu'ici, on ne voit pas trop ce qu'on gagne par rapport à faire des conditionnelles en cascade. Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Une dénition par cas résume plusieurs façons de faire des tests let let 1 true _ −> −> −> x,y | f x y = | _ 2 3;; mais aussi, plus concisément 3;; , false , f1 x y = then then 2 else 1 then 2 else 3;; l e t f2 x y = i f y then 2 else i f x then 1 else 3;; x if else if 1 match x , y w i t h −> 1 t r u e −> 2 _ −> 3 ; ; true , f a l s e | let if with l e t f2 x y = i f y then 2 else i f x then 1 e l s e let let let y y t e s t s = [ true , true ; f a l s e , f a l s e ; f a l s e , true ; true , f a l s e ] ; ; test test f ;; test f1 ; ; test f2 ; ; f = L i s t . map ( f u n (x , y) −> f x y) tests ;; Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Arbres de décision Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Arbres de décision Les arbres de décision Utilité des arbres de décision Pour chaque dénition par cas dans le source OCaml, le compilateur doit produire une série de tests qui permettent de déterminer, pour toute donnée en entrée, quelle ligne de la dénition s'applique. On peut représenter cette série de tests avec un arbre de décision. Le dernier code vu donne, par exemple : Étant donné un arbre de décision associé à une dénition par cas, il est facile de I identier les dénitions incomplètes : les cas oubliés sont les branches absentes d'un noeud de décision I identier les dénitions inutiles : si une régle n'apparaît dans 2 true rule 2 aucune feuille, elle ne sera jamais utilisée false { ! true rule 1 ~ C'est précisément ce qui rend la dénition par cas si utile et populaire parmi les programmeurs ML : ce n'est 1 pas la même chose qu'une librairie de motif ajoutée au langage comme on peut en false trouver pour Scheme ou Java. rule 3 Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Arbres de décision Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Approfondissement Un très grand nombre d'arbres de décision Pointeurs pour aller plus loin La compilation des dénitions par cas ( pattern matching) a été étudiée depuis les années 1980. Question : Combien d'arbres de décisions diérents y a-t-il pour une dénition par cas à n arguments ? Exercice : écrivez tous les encodages possibles, avec des conditionnelles, pour la fonction suivante l e t f x y z = match x , y , z w i t h | _ , f a l s e , t r u e −> 1 | f a l s e , t r u e , _ −> 2 | _ , _ , f a l s e −> 3 | _ , _ , t r u e −> 4 ; ; Marianne Baudinet and David Macqueen. Tree pattern matching for ml (extended abstract). Technical report, Stanford University, 1985. Fabrice Le Fessant and Luc Maranget. Optimizing pattern-matching. In Proceedings of the 2001 International Conference on Functional Programming. ACM Press, 2001. Luc Maranget. Compiling pattern matching to good decision trees. ML'2008. Programmation Fonctionnelle Avancée Pattern Matching, ou dénitions par cas Approfondissement Quelques résultats I Marianne Baudinet et David MacQueen, 1985 : trouver le plus petit arbre de décision est un problème NP-Complet I Lefessant et Maranget, 2001 : des heuristiques ecaces pour OCaml (c'est l'algorithme implanté aujourd'hui)
© Copyright 2024 ExpyDoc
