Apprendre la programmation fonctionnelle avec le MOOC OCaml

Logo

Pour la deuxième année consécutive, l’université Paris Diderot, en partenariat avec la Sorbonne, INRIA, IRILL et OCamlPro, organise un MOOC d’initiation à la programmation fonctionnelle avec le langage OCaml. Les leçons débuteront le 26 septembre 2016 et se termineront le 12 décembre. Les cours seront donnés en anglais mais des sous-titres sont disponibles aussi bien en anglais qu’en français. Il est toutefois possible de s’inscrire jusqu’au 25 novembre pour les retardataires.

Sommaire

La formation

La programmation fonctionnelle attire l’intérêt d’un large spectre de développeurs, car elle permet d’écrire des programmes expressifs, concis et élégants.

La formation « Introduction à la programmation fonctionnelle avec le langage OCaml » introduit progressivement les notions centrales de la programmation fonctionnelle, à travers une série de vidéos pédagogiques complétées par un riche ensemble d’exercices que vous pouvez effectuer entièrement dans votre navigateur… Oui, cela signifie que vous pouvez commencer à apprendre la programmation fonctionnelle sans prise de tête : rien à installer, rien à configurer, l’environnement de programmation est à une portée de clic !

Au cours de la formation, vous découvrirez des mécanismes puissants pour construire et manipuler des structures de données de manière claire et efficace. Et vous verrez comment les fonctions jouent un rôle central, en tant que citoyens de première classe qui peuvent être librement utilisés à chaque endroit où un terme du langage peut apparaître (une fonction peut retourner une fonction, ou prendre une autre fonction parmi ses paramètres).

Les inscriptions sont déjà ouvertes sur la plateforme fun-mooc à l’adresse suivante : s’inscrire à la formation « Introduction à la programmation fonctionnelle avec le langage OCaml ». La formation débutera le 26 septembre 2016 et durera six semaines, et la date de clôture des inscriptions est fixée au 25 novembre : vous pouvez prendre le train en marche ! 🙂

Le temps de travail attendu est compris entre 2 et 6 heures par semaine — en fonction de votre niveau initial — ce qui comprend le temps passé à visionner les courtes séquences vidéos des leçons, dont la durée est approximativement d’une heure par semaine.

Cela peut sembler un effort significatif, mais à la fin de la formation vous aurez appris de nombreuses choses : le projet final confirmera votre bonne maîtrise de la programmation fonctionnelle et votre capacité à développer des programmes de taille moyenne avec aisance.

Des milliers d’étudiants ont suivi la première session de cette formation qui s’est terminée en janvier 2016, et la majorité d’entre eux en ont été extrêmement satisfaits.

Afin d’introduire la programmation fonctionnelle, nous avons choisi d’utiliser le langage OCaml. OCaml est un langage riche, élégant et efficace qui réconcilie la concision et la flexibilité des langages sans annotations de types (comme Python, par exemple) avec la sécurité des langages fortement et statiquement typés (comme Java, C ou C++ par exemple). Ce qui signifie que si votre programme compile alors vous n’aurez pas d’erreur de typage à l’exécution, sans avoir pour autant à annoter votre code pour cela. Le langage dispose de plus d’une communauté d’utilisateurs dynamique.

Facebook, Microsoft, JaneStreet, Bloomberg font partie des grands noms de l’industrie qui ont adopté OCaml pour développer des applications de pointe. La communauté de la recherche utilise OCaml pour écrire des outils comme l’assistant de preuve Coq, le convertisseur de programme Coccinelle, l’analyseur de code Frama-C, ou l’analyseur statique Astree. De nombreuses start-up utilisent OCaml pour décupler leur productivité et la stabilité de leur base de code.

Une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon.

La formation se déroulera en anglais, mais des sous-titres sont déjà disponibles en anglais et en français. Nous remercions à ce titre les nombreux bénévoles, avec une mention spéciale pour Jean-François Monin qui s’est occupé seul de la version française.

Pour bénéficier pleinement de cette formation il est préférable que vous ayez déjà des connaissances de base en programmation, en particulier vous devriez savoir écrire de simples programmes dans un autre langage. Par exemple, vous devriez connaître des notions comme les variables (ou identifiants), les fonctions (ou procédures, méthodes), les structures conditionnelles, et les boucles.

Le contenu des cours

Les leçons se dérouleront sur six semaines avec une courte introduction en préambule. Chaque semaine abordera un nouveau trait du langage, et elle se conclura par une série d’exercices pour contrôler la bonne assimilation des nouvelles notions introduites. À la fin de celles-ci, chaque étudiant devra réaliser un petit projet afin d’obtenir son certificat de validation.

  1. Introduction et vue d’ensemble
  2. Types de base, définitions et fonctions
  3. Structures de données de base
  4. Structures de données plus avancées
  5. Fonctions d’ordre supérieur
  6. Exceptions, entrées/sorties et construction impérative
  7. Modules et abstraction de données

Le matériel pédagogique est diffusé sous licence CC-BY-NC-ND, tandis que les étudiants conservent la pleine propriété intellectuelle de leur code.

L’équipe pédagogique

L’équipe pédagogique est constituée de trois enseignants chercheurs de l’université Paris Diderot qui s’occupent des cours en vidéos, et de deux ingénieurs en recherche et développement chez OcamlPro qui se sont occupés des exercices et de l’environnement de développement.

Roberto Di Cosmo

Roberto Di Cosmo est professeur d’informatique à l’Université Paris Diderot, directeur de l’IRILL (Initiative de Recherche et Innovation sur le Logiciel Libre), et actuellement détaché à l’INRIA. Ses thèmes de recherche incluent la programmation fonctionnelle et parallèle, les systèmes de types, la logique, la réécriture et l’analyse statique d’une large collection de logiciels. Dans le milieu du logiciel libre, il est entre autre connu pour être à l’origine du projet Mancoosi et du projet Software Heritage présenté dans le journal Bibliothèque d’Alexandrie du logiciel libre.

Yann Regis-Gianas

Yann Régis-Gianas enseigne la science informatique à l’Université Paris Diderot. Ses recherches au laboratoire PPS (Preuves, Programmes et Systèmes) se concentrent sur la théorie et la conception des langages. Il a effectué son doctorat dans l’équipe INRIA qui développe OCaml et est maintenant dans l’équipe de développement de l’assistant de preuves Coq.

Ralf Treinen

Ralf Treinen est professeur d’informatique à l’Université Paris Diderot. La résolution par contrainte symbolique, la vérification et l’application des méthodes formelles pour l’assurance qualité des logiciels sont parmi ses thèmes de recherches actuels. Il est également membre de l’IRILL.

Benjamin Canou

Benjamin Canou est ingénieur R&D chez OCamlPro. Il a travaillé sur l’environnement des exercices, conçu l’évaluateur automatique, et écrit la plupart des exercices. Il a une solide expérience de l’enseignement d’OCaml à l’université, ainsi que des formations à OCaml pour les professionnels.

Grégoire Henry

Grégoire Henry est ingénieur R&D chez OCamlPro. Il a travaillé sur l’environnement des exercices, en particulier l’éditeur de texte avec coloration syntaxique et indentation automatique, et sur le toplevel (la boucle d’interaction). Il a également de l’expérience dans l’enseignement d’OCaml à l’Université Paris Diderot, et la formation professionnelle pour OCamlPro.

Quelques exemples de code

Pour terminer cette dépêche, rien de tel que de montrer quelques exemples de code fonctionnel en OCaml. Je montrerai la plupart du temps les résultats suite à l’utilisation de la boucle interactive (REPL).

Le traditionnel “Hello World !”

Bon, là on fait dans le classique.

(* pour appeler une fonction on écrit son nom puis
 * ses arguments séparés par des espaces *)
print_endline "Hello World !";;
Hello World !
- : unit = ()

Visitor pattern sur un arbre binaire

Cette fois on aborde une structure de données assez élémentaire : les arbres binaires dont les feuilles sont toutes de type int. Puis on définira une fonction générique de parcours de l’arbre (analogue au visitor pattern de la POO) pour effectuer différentes opérations sur celui-ci.

(* on définit le type de nos arbres binaires :
 *  soit on a une feuille avec un int
 *  soit on a un nœud avec deux sous arbres *)
type tree = 
  | Leaf of int
  | Node of tree * tree

(* ici on définit une fonction de parcours de l'arbre
 * traditionnellement appelée fold : elle prend deux 
 * fonctions f et g comme paramètres et remplace les
 * constructeurs du type par l'application d'une de ces
 * deux fonctions en parcourant récursivement l'arbre
 * de la racine jusqu'aux feuilles *)
let rec fold f g = function
  (* si on a une feuille, on applique la fonction f *)
  | Leaf n -> f n
  (* si on a un nœud, on applique recursivement fold sur
   * chaque sous-arbre, puis la fonction g aux résultats *)
  | Node (left, right) -> g (fold f g left) (fold f g right)

(* maintenant on va appliquer cette fonction générique
 * de parcours pour obtenir différentes interprétations *)

(* interprétation en tant qu'addition 
 * chaque feuille renvoie sa valeur et sur
 * un nœud on additionne les deux sous-arbres*)
let plus = fold (fun i -> i) ( + )

(* interprétation en tant que soustraction *)
let moins = fold (fun i -> i) ( - )

(* ici on calcule la profondeur de l'arbre 
 * une feuille est de profondeur nulle et par définition
 * la profondeur d'un arbre vaut la plus grande des profondeurs
 * de ses sous-arbres augmentée d'une unité *)
let depth = fold (fun i -> 0) (fun d d' -> 1 + max d d')

(* ici on définit différentes fonctions de pretty printing pour nos arbres *)
let show = fold string_of_int (fun s s' -> Printf.sprintf "(op %s %s)" s s')
let show_p = fold string_of_int (fun s s' -> Printf.sprintf "(%s + %s)" s s')
let show_m = fold string_of_int (fun s s' -> Printf.sprintf "(%s - %s)" s s');;

(* le compilateur détermine automatiquement le type de tous
 * les termes bien que l'on n'ait rien précisé *)
type tree = Leaf of int | Node of tree * tree
val fold : (int -> 'a) -> ('a -> 'a -> 'a) -> tree -> 'a = <fun>
val plus : tree -> int = <fun>
val moins : tree -> int = <fun>
val depth : tree -> int = <fun>
val show : tree -> string = <fun>
val show_p : tree -> string = <fun>
val show_m : tree -> string = <fun>

(* exemple d'utilisation *)
(* on définit un arbre *)
let x = Node (Leaf 1, Node (Leaf 2, Leaf 3));;
val x : tree = Node (Leaf 1, Node (Leaf 2, Leaf 3)) 

(* on l'affiche plus joliment *)
show x;;
- : string = "(op 1 (op 2 3))"

(* on voit l'opérateur op comme une addition *)
show_p x, plus x;;
- : string * int = ("(1 + (2 + 3))", 6)

(* la même avec la soustraction *)
show_m x, moins x;;
- : string * int = ("(1 - (2 - 3))", 2)

(* on calcule enfin sa profondeur *)
depth x;;
- : int = 2

Pour mieux se rendre compte de la concision du code, regardons ce que cela donne si l’on ne garde que l’essentiel en retirant les commentaires :

type tree = Leaf of int | Node of tree * tree

let rec fold f g = function
  | Leaf n -> f n
  | Node (left, right) -> g (fold f g left) (fold f g right)

let plus = fold (fun i -> i) ( + )
let moins = fold (fun i -> i) ( - )
let depth = fold (fun i -> 0) (fun d d' -> 1 + max d d')
let show = fold string_of_int (fun s s' -> Printf.sprintf "(op %s %s)" s s')
let show_p = fold string_of_int (fun s s' -> Printf.sprintf "(%s + %s)" s s')
let show_m = fold string_of_int (fun s s' -> Printf.sprintf "(%s - %s)" s s')

Et voilà ! 🙂

Un adverbe, c’est quoi au fait ?

Sur ce dernier exemple, je vais essayer d’illustrer ce propos : « une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon »; mais en ne l’illustrant pas vis-à-vis d’un autre langage de programmation, mais par rapport à une langue vernaculaire : le français. 🙂

Ce dernier exemple est un peu plus évolué que les précédents, et s’il ne vous paraît pas clair dès aujourd’hui, cela devrait l’être à l’issue de la formation.

Pour ce faire, je vais partir d’un motif fréquent en programmation impérative : la boucle for, afin d’implémenter un code qui doit effectuer cette tâche : « écrire 5 fois “coin< coin<” » et arriver au code OCaml suivant ecrire (5 |> fois) "coin< coin<".

(* la solution standard à la mode impératif *)
for i = 1 to 5 do print_endline "coin< coin<" done;;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<
- : unit = ()

Mais on pourrait vouloir un code plus général au cas où l’on veuille effectuer la boucle plus de 5 fois. Dans ce cas, on crée une fonction qui prend en paramètre un entier qui déterminera le nombre de fois où l’on fait la boucle.

let repete_coin_coin n =
  for i = 1 to n do print_endline "coin< coin<" done;;
(* le compilateur infère toujours seul le type de la fonction *)
val repete_coin_coin : int -> unit = <fun>

repete_coin_coin 5;;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<
- : unit = ()

Voilà qui est bien, mais on peut encore essayer de généraliser ce bout de code. Ici l’action à effectuer dans la boucle est constante dans le corps de la fonction, on pourrait en faire un paramètre. La forme générale du corps de la boucle c’est : une fonction (dans notre cas print_endline) appliquée à son paramètre (ici "coin< coin<"). Ce qui donne :

let fois n f x =
  for i = 1 to n do f x done;;
(* inférence du type général de la fonction par le compilateur *)
val fois : int -> ('a -> 'b) -> 'a -> unit = <fun>

fois 5 print_endline "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Revenons un instant à notre énoncé de départ en français : « écrire 5 fois “coin< coin<” ». Ici ce que l’on doit réitérer 5 fois, c’est « écrire “coin< coin<” ». En grammaire française, un verbe comme « écrire » qui attend un complément pour signifier son action est appelé un verbe transitif. Dans notre code c’est la fonction f qui joue le rôle du verbe, et le compilateur nous dit que son type général est 'a -> 'b, autrement dit une fonction qui attend un paramètre de type quelconque 'a (son complément) pour retourner un objet d’un type quelconque 'b (le produit de l’action). Qu’à cela ne tienne, écrivons tout cela en OCaml !

(* on définit le type général d'un verbe transitif *)
type ('a, 'b) verbe = 'a -> 'b

(* ici je vais rajouter des annotations de types sur les
 * paramètres pour bien montrer l'analogie avec le français *)
let fois n (verbe:('a, 'b) verbe) (cod:'a) =
  for i = 1 to n do verbe cod done;;
val fois : int -> ('a, 'b) verbe -> 'a -> unit = <fun>

(* l'usage reste le même qu'avant *)
fois 5 print_endline "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Maintenant dans la phrase en français les mots « 5 fois » correspondent à ce que l’on appelle un groupe adverbial. Et si l’on regarde le type général de la fonction fois (que l’on a écrit pour reproduire ce groupe adverbial du français) tel qu’inférer par le compilateur on a : int -> ('a, 'b) verbe -> 'a -> unit. Or si l’on regarde la fin de ce type : 'a -> unit on retrouve la forme d’un verbe transitif dont le COD est de type 'a et dont le produit de l’action est de type unit (c’est l’équivalent du type void dans des langages comme le C). Ainsi, au fond notre fonction fois prend un entier int, un verbe ('a, 'b) verbe et renvoie un autre verbe 'a -> unit = ('a, unit) verbe. Autrement dit le groupe adverbial « 5 fois » (ou fois 5 en OCaml) prend un verbe et renvoie un verbe (en changeant éventuellement le type du produit de l’action). Essayons d’exprimer cela en OCaml :

(* le type des verbes transitifs *)
('a, 'b) verbe = 'a -> 'b 

(* celui des adverbes qui peuvent changer le type du résultat de l'action *)
type ('a, 'b, 'c) adverbe = ('a, 'b) verbe -> ('a, 'c) verbe

(* on réécrit toujours le même code avec quelques annotations
 * pour mettre en avant le lien avec la grammaire du français *)
let fois n:('a,'b,unit) adverbe =
  fun (verbe:('a, 'b) verbe) (cod:'a) -> 
    for i = 1 to n do verbe cod done;;
val fois : int -> ('a, 'b, unit) adverbe = <fun>

(* et maintenant on définit une fonction écrire qui prendra comme
 * paramètres un adverbe et un texte à afficher sur la sortie standard *)
let ecrire (adv:('a,'b,'c) adverbe):('string, 'c) verbe =
  fun texte -> adv print_endline texte;;
val ecrire : (string, unit, 'c) adverbe -> (string, 'c) verbe = <fun>

(* on retrouve presque la morphologie du français *)
ecrire (fois 5) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

(* pour coller encore plus au français on peut utiliser 
 * l'opérateur infixe |> qui est l'équivalent du pipe du
 * shell pour placer le paramètre avant la fonction *)
ecrire (5 |> fois) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Pour ceux qui m’ont suivi jusqu’au bout, afin de montrer toujours la concision du code OCaml, le résumé de tout ce qui précède tient en quelques lignes :

let fois n verbe cod =
  for i = 1 to n do verbe cod done

let ecrire adv texte = adv print_endline texte

ecrire (5 |> fois) "coin< coin<";;
coin< coin<
coin< coin<
coin< coin<
coin< coin<
coin< coin<

Qui dit mieux ? \o/

Conclusion

La programmation fonctionnelle a la mauvaise réputation d’être un paradigme de programmation pour « intello ». J’espère avoir réussi à montrer à travers ces exemples qu’il n’en est rien. Au fond, la grammaire d’une langue c’est son système de typage, et quelque que soit la langue l’on ne précise jamais la nature grammaticale (le type) des mots que l’on écrit : pourquoi devrait-il en être autrement en programmation ? En OCaml, c’est pareil grâce au mécanisme d’inférence de types et cela sans sacrifier la sécurité du typage statique.

Lors de la dépêche sur l’espéranto, les locuteurs de cette langue l’ont défendu en arguant que sa grammaire été plus simple, plus facile à assimiler et que des expériences essayaient de montrer qu’elle facilitait l’apprentissage des autres langues étrangères ainsi que des mathématiques; et tout cela bien que ce soit une langue inventée par une seule personne. Je dirais que cela ne m’étonne guère, et il en est de même avec OCaml : sa grammaire est incomparablement plus simple que n’importe quelle grammaire d’un langage impératif ou orienté objet. Et, à n’en pas douter, lorsque l’on commence à la comprendre, celles des autres langages nous apparaissent sous un autre jour.

Pour ceux qui voudraient tenter l’aventure, que ce soit pour découvrir un nouveau paradigme ou un nouveau langage, il vous suffit de vous inscrire : c’est libre, gratuit et dispenser par des enseignants de qualité. Et pour ceux qui veulent avoir un avant-goût du contenu et de l’environnement de travail, il existe une démonstration dans laquelle on peut effectuer quelques exercices issus de la première session de la formation.

Lire les commentaires

(Source: LinuxFr.org : les dépêches)