Algorithmique et Programmation Fonctionnelle (APF) - RICM3 Cours

Algorithmique et Programmation Fonctionnelle (APF)

Algorithmique et Programmation Fonctionnelle(APF)RICM3

Cours 1 : Introduction à OCaml

Jean-François Monin, Benjamin Wack

2016 - 2017

1 / 31

Algorithmique et Programmation Fonctionnelle (APF)Présentation du cours

Qui ? Où ? Quand ?Enseignants

I Cours : Jean-François Monin & Benjamin WackI TD groupe 1 : Erwan JahierI TD groupe 2 : Jean-François MoninI TP : Erwan Jahier & Benjamin WackI (échanges ponctuels)

Horaires réguliersI COURS : Mardi 8h-9h30 PolytechI TD : Mardi 9h45-11h45I TP : Mercredi 8h Polytech 009

binômes tirés au hasard (apporter vos machines !)

Consulter ADE 2 / 31


Les moyens

Matériel

I Install Party : Linux + OCaml + Tuareg + emacsI Polys de TD et TPI Page Web (outils, planning, documents...)

http://www-verimag.imag.fr/~wack/APF

Ressources recommandées

I http://caml.inria.fr/

I Demander de l’aide aux enseignants

3 / 31

http://www-verimag.imag.fr/~wack/APF

http://caml.inria.fr/


Note APF

Note finale = 60 % Devoirs + 40% CC

Devoirs

I 1 DSI 1 Exam

CC

I 1 DMI 8 TPs (quitus global)I 1 Projet (2 TP + travail en autonomie)

4 / 31


Les rendus

TP

I Questions préliminaires à préparer avantI Compte-rendu à envoyer par mail lundi matin avant 8hI Correction : revue de code au début du TP suivant

DMÉnoncé distribué une semaine avant

ProjetTP-Projet (2 séances) à rendre à la fin du semestre

Travail non rendu à tempsCopier quelle que soit la source

}⇒ ZERO pour toutes

les personnes impliquées5 / 31


Votre travail

Rappel : volume de travail (4 ETCS = 4*24h)

I 15h AmphiI 20h TDI 18h TPI 50h Travail personnel

Travail personnel pour cette UE

I Préparation des TDs suite au coursI Exercices chaque semaine + DMI TP par groupe, préparés à l’avanceI ProjetI révisions...

6 / 31


Objectifs du cours

Savoir faire

I Utiliser le paradigme fonctionnel.I Utiliser la récursivité et les structures de données

correspondantes.I Concevoir des algorithmes efficaces et corrects.

Moyens

I Programmation fonctionnelle en Objective Caml.(Caml = Categorical Abstract Machine Language)

I TypageI Raisonnement par récurrence structurelle.I Initiation aux calculs de complexité. 7 / 31


Plan

Présentation du cours

Motivations

Expressions et types de base

Définition d’un identifiant

8 / 31

Algorithmique et Programmation Fonctionnelle (APF)Motivations

Plan


Motivations



9 / 31


Qu’est-ce qu’un programme ?

La traduction d’un algorithme dans un langage commun à l’hommeet à la machine.Qu’est-ce qu’un algorithme ?Une procédure de résolution d’un problème, suffisamentélémentaire pour être exécutée de façon automatique.

10 / 31


Qu’est-ce qu’un programme ?La traduction d’un algorithme dans un langage commun à l’hommeet à la machine.

Qu’est-ce qu’un algorithme ?Une procédure de résolution d’un problème, suffisamentélémentaire pour être exécutée de façon automatique.

10 / 31


Qu’est-ce qu’un programme ?La traduction d’un algorithme dans un langage commun à l’hommeet à la machine.Qu’est-ce qu’un algorithme ?

Une procédure de résolution d’un problème, suffisamentélémentaire pour être exécutée de façon automatique.

10 / 31


Qu’est-ce qu’un programme ?La traduction d’un algorithme dans un langage commun à l’hommeet à la machine.Qu’est-ce qu’un algorithme ?Une procédure de résolution d’un problème, suffisamentélémentaire pour être exécutée de façon automatique.

10 / 31


Différents paradigmes de programmation

1. ImpératifFortran (1954), COBOL (1960), C (1970)...

2. FonctionnelLisp (1959), Haskell (1990), Objective CAML (1996)...

3. LogiqueProlog (1972)

11 / 31

Algorithmique et Programmation Fonctionnelle (APF)MotivationsProgrammation impérative

Programmation impérative

Centrée sur la notion d’affectationx := E

I x est un emplacement mémoireI E est une expression :

sa valeur v est temporairement associée à x.

x est aussi traditionnellement appelée une variable.

12 / 31


Modèle de calcul

ÉtatDéfinit les données représentées en mémoire à un instant donné.L’état peut être très complexe, utiliser des pointeurs

Les ingrédients des algorithmes

I Une instruction indique une transition d’état.I Combinaisons d’instructions (if, boucles...)

Pour comprendre un programmeIl faut étudier l’effet de toutes les instructions sur toutes les partiesde l’état dans toutes les situations atteignables.Problème : les variables sont de véritables savonettes.

13 / 31


Comprendre un programme

Pour raisonner sur un programmeIl faut étudier l’effet de toutes les instructions sur toutes les partiesde l’état dans toutes les situations atteignables.Problème : les variables sont de véritables savonettes.

Exemplex := 3

Donne x = 3x := x+1

Donne quoi ?

On peut survivreCf. matières A&G et API

14 / 31

Algorithmique et Programmation Fonctionnelle (APF)MotivationsProgrammation fonctionnelle

Programmation fonctionnelle

Centrée sur la notion d’expressionToute expression a une valeur et un type.

I Déterminés une fois pour toutes.I La valeur ne dépend pas de l’ordre d’évaluation.

Description d’un algorithme

I Un algorithme est une fonction d’un ensemble de valeurs dansun autre.

I Une fonction est souvent décrite elle-même à partir defonctions (analyse descendante).

I Utilisation intensive de la récursivitéI Manipulation aisée des données grâce au filtrage

(English : pattern-matching)15 / 31


Comprendre un programme fonctionnel

Raisonnement facilité

I On ne se préoccupe que de la valeur et du type.I Raisonnement par cas sur les différentes valeurs possibles

+ raisonnement par récurrence.I Raisonnement équationnel :

toute expression peut-être remplacée par une expression égale.

Passe plus facilement à l’échelleY compris pour des preuves formelles en présence de donnéescomplexes

16 / 31


Mythes et réalités sur la programmation fonctionnelle

Ce que l’on évite

I Pas de contrôle : chemins d’exécution indifférentsI Pas de pointeurs : pas de corruption des valeurs

Ce que l’on ne perd pas

I Efficacité : Interpréteur, compilateur → code-octet ou natifI Possibilité d’utiliser des traits impératifs (à bon escient)

Ce que l’on gagne

I Taille du code typiquement 1/10 du code C équivalentI Gestion mémoire automatique

17 / 31


Prix à payer

Effort

I Changement de perspectiveI Moins adapté à l’embarqué ou à la programmation système de

bas niveau (un peu comme Java)

Support

I Communauté très active dans le « libre »I Bibliothèques en quantité moyenne mais d’excellente qualité

18 / 31


Un « vrai » langageCaml et ses avatars développés depuis ' 25 ans, principalementdans des laboratoires d’informatique français.Applications

I Domaine de prédilection : traitement symboliqueI analyse de programmes : ASTREE (CNRS & INRIA)I aide à la démonstration : Coq (INRIA)I compilation

I Programmation système : SLAM (Microsoft)I Programmation réseau : MLdonkey (peer to peer

multiplateformes, premier client open source d’eDonkey)I Milieux scientifiques, domaine bancaire (Jane Street)...

Un exemple : est passé de Java à OCaml en cours dedéveloppement pour gagner en robustesse. 19 / 31


Caractéristiques de OCaml

Expressivité

I Typage statique avec inférence de types et polymorphismeI Types définissables et filtrageI Gestions des exceptions

Développement

I Gestion de la mémoireI Modules paramétrables (foncteur)I Compilateur natif et bytecodeI Système de classe évolué (objets)I Open source

20 / 31


Programme du Cours

1. Bases de OCaml2. Programmation et preuve par récurrence structurelle3. Analyse syntaxique4. Modularité5. Mécanismes de typage6. Lambda Calcul7. Structures et traits impératifs

21 / 31

Algorithmique et Programmation Fonctionnelle (APF)Expressions et types de base

Plan


Motivations



22 / 31


Types de base

I int 42 -12 opérateurs : + - * / modI float -3.1 0. 1.3e-4 opérateurs : +. -. *. /.I bool true false opérateurs : && || not

I et aussi char, string... cf doc. OCaml

Expression = assemblage de constantes et d’opérateursqui respecte les contraintes de type

Chaque opérateur est typé (arguments attendus et valeur calculée).

23 / 31


Types de base

I int 42 -12 opérateurs : + - * / modI float -3.1 0. 1.3e-4 opérateurs : +. -. *. /.I bool true false opérateurs : && || not

I et aussi char, string... cf doc. OCaml

Expression = assemblage de constantes et d’opérateursqui respecte les contraintes de type

Chaque opérateur est typé (arguments attendus et valeur calculée).

23 / 31


Expressions à base d’opérateurs

I 2 + 3I 2.x +. 3.I (2 + 5) * 3I 2 = 5I 2 < 5I true && falseI (2 < 5) && 2 = 5

24 / 31


Expression conditionnelle

I “if b then e1 else e2”I Pas une instruction mais une expression dont la valeur dépend

de b

Exemple : (if 5 < 9 then 21 else 3) * 2 ; ;

I (if 5 < 9 then 21 else 3) *2I (if true then 21 else 3) *2I 21*2I 42

Les opérateurs booléens sont paresseux :Dans e1 && e2 l’expression e2 n’est pas évaluée si e1 vaut falseDans e1 || e2 l’expression e2 n’est pas évaluée si e1 vaut vrai

25 / 31




de b


I (if 5 < 9 then 21 else 3) *2

I (if true then 21 else 3) *2I 21*2I 42


25 / 31




de b


I (if 5 < 9 then 21 else 3) *2I (if true then 21 else 3) *2

I 21*2I 42


25 / 31




de b


I (if 5 < 9 then 21 else 3) *2I (if true then 21 else 3) *2I 21*2

I 42


25 / 31




de b




25 / 31




de b




25 / 31

Algorithmique et Programmation Fonctionnelle (APF)Définition d’un identifiant

Plan


Motivations



26 / 31


Identifiants

Définition d’un identifiant : letlet associe un identifiant à une valeur calculée par une expression

# let x = 53 ; ;val x : int = 53

# let y = x - 11 ; ;val y : int =?

42

ExplicationsI let y = x - 11 ; ;I x est associé à la valeur 53.I donc x - 11 a la valeur de 53 - 11.I val y : int = 42

Pas d’état, pas de variables

27 / 31


Identifiants


# let x = 53 ; ;val x : int = 53

# let y = x - 11 ; ;val y : int = 42


Pas d’état, pas de variables

27 / 31


Identifiants


# let x = 53 ; ;val x : int = 53

# let y = x - 11 ; ;val y : int = 42


Pas d’état, pas de variables27 / 31


Redéfinition d’un identifiant

Un identifiant est un nom donné à une valeur.Exemple# let x = 53 ; ;val x : int = 53# let y = x - 11 ; ;val y : int = 42# let x = 2 ; ;val x : int = 2# y ; ;- : int =?

-9 ou

On peut même écrire let x = x + 1 mais on ne peut pas s’en servirpour calculer (pas de boucles !)

28 / 31



Un identifiant est un nom donné à une valeur.Exemple# let x = 53 ; ;val x : int = 53# let y = x - 11 ; ;val y : int = 42# let x = 2 ; ;val x : int = 2# y ; ;- : int =? -9 ou 42


28 / 31





28 / 31





28 / 31


Compléments sur le let

Variantes

I Avec type spécifié let (a : t) = expr ; ;I Définitions multiples let a = 1 and b = 2

Gare à la casse# let eta = 0 ; ;# let eTa = 1 ; ;# eta = eTa ; ;- : bool = false# let Eta = 2 ; ;Error : Unbound constructor Eta

OCaml est sensible à la casse et les initiales majuscules sontréservées.

29 / 31



Variantes


Gare à la casse# let eta = 0 ; ;# let eTa = 1 ; ;# eta = eTa ; ;

- : bool = false# let Eta = 2 ; ;Error : Unbound constructor Eta


29 / 31



Variantes


Gare à la casse# let eta = 0 ; ;# let eTa = 1 ; ;# eta = eTa ; ;- : bool = false

# let Eta = 2 ; ;Error : Unbound constructor Eta


29 / 31



Variantes


Gare à la casse# let eta = 0 ; ;# let eTa = 1 ; ;# eta = eTa ; ;- : bool = false# let Eta = 2 ; ;Error : Unbound constructor Eta

OCaml est sensible à la casse et les initiales majuscules sontréservées. 29 / 31


Let localLe let précédent introduit une définition globalequi lie un nom à la valeur d’une expressionlet a = expr1expr2⇒ a reste disponible

Définition localeUne expression peut elle même commencer par une définitionlocale : identifiant visible uniquement dans cette expression

let a = expr1 in expr2

⇒ expr1 écrite et évaluée une seule fois⇒ Ce a est disponible seulement dans expr2, puis est oublié

évite des collisions⇒ Nb : let a = expr1 in expr2 est une expression 30 / 31


Bibliographie

I Xavier Leroy et al. Objective Caml manual http://caml.inria.fr/pub/docs/manual-ocaml/index.html

I The book Developing Applications With Objective Caml (byEmmanuel Chailloux, Pascal Manoury and Bruno Pagano)

I Approche fonctionnelle de la programmation, Michel Mauny ,Guy Cousineau

I Pierre Weis and Xavier Leroy. Le langage Caml. Dunod, 1999.I Apprentissage de la programmation avec OCaml Catherine

Dubois & Valérie Ménissier-MorainI Philippe Nardel. Programmation fonctionnelle, générique et

objet : Une introduction avec le langage OCaml. Vuibert, 2005I Louis Gacogne. Programmation par l’exemple en Caml.

Ellipse, 2004

31 / 31

http://caml.inria.fr/pub/docs/manual-ocaml/index.html

http://caml.inria.fr/pub/docs/manual-ocaml/index.html

Documents

Algorithmique et Programmation Fonctionnelle (APF) - RICM3 Cours