Introduction à la programmation fonctionnelle

Cours 1

kn@lri.fr
http://www.lri.fr/~kn

Attributions

Ce cours reprend de nombreux éléments du cours de Sylvain Conchon (resp. IPF jusqu'en 2020)

La page de l'an dernier : https://www.lri.fr/~conchon/IPF/

Autres ressources :

Apprendre à Programmer avec OCaml (Conchon, Filliâtre, ed. Eyrolles)

Un mot sur l'organisation

Le cours est tous les jeudi, les TP les jeudi (après le cours) et vendredi matin.

TP noté : 40%, examen : 60%

Sous réserve de modifications suite à la crise sanitaire …

Langages de programmation

Définitions

Un langage est un système de communication structuré. Il permet d'exprimer une pensée et de communiquer au moyen d'un système de signes (vocaux, gestuel, graphiques, …) doté d'une sémantique, et le plus souvent d'une syntaxe.

Un langage de programmation est un système de communication structuré. Il permet d'exprimer un algorithme de façon à ce qu'il soit réalisable par un ordinateur. Il est doté d'une sémantique, et d'une syntaxe.

Syntaxe et sémantique

La syntaxe est l'ensemble des règles de bonne formation du langage.

Exemple avec du code OCaml:

1 + 4 (* est syntaxiquement correct *) 1 / 'Bonjour' (* est syntaxiquement correct *) 1 + (* est syntaxiquement incorrect *)

La sémantique est l'ensemble des règles qui donne le sens des programmes bien formés

1 + 4 (* est sémantiquement correct *) 1 / "Bonjour" (* est sémantiquement incorrect *)

Quels langages de programmation ?


La tour de Babel, Pieter Brueghel l'Ancien, 156

Quels sont les caractéristiques des langages de programmation ?

Est-ce une bonne chose ?

Oui !

Sur le cycle de Licence, au moins 5 langages

Le langage OCaml

Caractéristiques du langage

Le langage supporte différents paradigmes : fonctionnel, impératif, orienté objet.

Dans ce cours, on n'utiliser que le fragment fonctionnel

Un premier programme

On considère le fichier salut.ml

let limit = 40;; (* On définit une variable globale *) Printf.printf "Quel est votre age ?\n";; (* On affiche un message *) let age = read_int ();; (* On lit un entier sur l'entrée standard *) let msg = if age >= limit then (* On teste la valeur *) "vieux" else "toi" ;; Printf.printf "Salut, %s!\n" msg;;

On peut compiler ce programme dans un terminal :

$ ocamlc -o salut.exe salut.ml $ ./salut.exe Quel est votre age ? 38 Salut, toi ! $

Qu'y a t'il dans ce programme ?

Le programme est compilé (comme Java ou C++)

Comment programmer avec OCaml ?

On privilégie pour les TPs un mode minimal

  1. Ouvrir un terminal
  2. Créer et se placer dans un répertoire pour le TP (par exemple IPF/TP1)
  3. Lancer un éditeur de texte sur un fichier OCaml : $ emacs exo1.ml & $
  4. Éditer le code, sauver le fichier
  5. Tester le programme : $ ocamlc -o exo1.exe exo1.ml $ ./exo1.exe

En mode distanciel on va tenter d'utiliser un environnement en ligne fournissant un éditeur et un shell.

La boucle d'interaction

Le langage OCaml possède aussi un mode interactif qui permet d'évaluer des instructions, comme un shell.

Il suffit de lancer la commande rlwrap ocaml sans argument.

$ rlwrap ocaml OCaml version 4.10.0 # 1 + 1 ;; - : int = 2 # 3 * 10 ;; - : int = 30 # let x = 42 ;; val x : int = 42 # x + 10 ;; 52 #

On peut quiter avec CTRL-d

Compilation vs. mode intéractif

Le mode intéractif attend des expressions OCaml et les exécute au fur et à mesure.
Il peut être utilisé pour tester des petits morceaux de programmes.

Compilation

Programmation fonctionnelle

C'est un paradigme de programmation dans lequel :

C'est une façon de programmer particulièrement concise, puissante et qui peut être efficace. Elle vient compléter les autres styles de programmation : impératifs et orienté objet.

Programmation fonctionnelle en OCaml

Pourquoi faire de la programmation fonctionnelle en OCaml ?

TOUS les langages de programmation modernes supportent le paradigme fonctionnel :

Mais :

Au début …

Les premiers TPs vont peut être paraître aride :

Ils deviendront plus sexy au fur et à mesure qu'on avencera dans le langage (programmation système, graphique, …)

Types simples

Les entiers (int)

En OCaml, les entiers ont une taille fixe : 63bits sur une architecture 64bits ou 31bits sur une architecture 32bits (un bit est reservé dans chaque entier en plus du bit de signe) :

# 1 ;; - : int = 1 # -149 ;; - : int = -149 # 1234567891011 ;; - : int = 1234567891011

Opération sur les entiers

Symbole Description
+ addition
- soustraction
* multiplication
/ division entière
mod modulo

# 1 - 9 ;; - : int = -8 # 3 * 4 ;; - : int = 12 # 5 / 3 ;; - : int = 1 # 10 mod 2 ;; - : int = 2 # 4 + 3.5 ;; Error: This expression has type float but an expression was expected of type int

Erreur de type ?

En OCaml, les expressions ont un type et un seul. C'est aussi valable pour les fonctions et les opérateurs. + est l'addition entre entiers.

À l'inverse d'autres langages il n'y a pas de conversion implicite entre types, il faut utiliser des conversion explicites.

Appels de fonctions

En OCaml, on appelle une fonction en donnant simplement son nom, suivi des arguments sans parenthèses :

f 1 2 3 ;; (* on appelle la fonction f sur 3 arguments *) g 4 ;; (* on appelle la fonction g sur un seul argument *) g (2 + 2) ;; (* on appelle la fonction g sur 1 seul argument *)

Cette notation étrange sera justifié dans le prochain cours

Les nombres à virgule (float)

En OCaml, les « nombres à virgule » ont une précision limitée. On les représente en utilisant la notation scientifique :

# 1.5 ;; - : float = 1.5 # -12.3423e13 ;; - : float = -123423000000000.0 # 1.5555555555555555555555555 - : float = 1.5555555555555558

Remarque : -12.3423e13 = -12.3423 × 1013 = -123423000000000.0

Attention : En OCaml, comme dans de nombreux langages, calculer avec des nombres à virgule (nombres flottants) peut provoquer des erreurs d'arrondi.

OCaml (comme C, C++, Java, Python, Javascript, …) utilise le standard IEEE-754 pour les flottants. C'est aussi celui implémenté en matériel par les processeurs et les cartes graphiques.

Opérations sur les flottants

Symbole Description
+. addition
-. soustraction
*. multiplication
/. division
** puissance
float i conversion int→float
float_of_int i conversion int→float
int_of_float f conversion float→int
sqrt f racine carrée
sin f sinus
cos f cosinus
tan f tangeante
log f logarithme (naturel)
log10 f logarithme (base 10)

Opérations sur les nombres flottants

# 1.5 +. 1.5 ;; - : float = 3. # 3.141592653589793 *. 2.0 ;; - : float = 6.28318530717958623 # 10.5 /. 3.0 ;; - : float = 3.5 # 1.2 +. 1.2 +. 1.2 ;; - : float = 3.59999999999999964 # 4.5 ** 100.0 ;; 2.09532491703986339e+65 # 1.0 /. 0.0 ;; - : float = infinity

Chaînes de caractères (string)

On représente les « textes » par des chaînes de caractères.
# "Bonjour, ça va bien ?" - : string = "Bonjour, ça va bien ?"

On ne montre que quelques opérations sur les chaînes de caractères :

Symbole Description
^ concaténation
String.length s longueur

Entrées/sorties

On se contentera d'entrées et sorties simples :

Dans un second temps, on verra comment lire et écrire des fichiers.

Printf.printf

La fonction Printf.printf est similaire à la fonction C du même nom. C'est une fonction variadique (nombre arbitraire d'arugments)

Le premier argument doit être une chaîne de format qui indique combien d'arguemnts lire ensuite et comment les afficher.
Dans cette chaîne les séquences suivantes sont spéciales :

Exemple :

Printf.printf "Un entier: %d, une chaîne: \"%s\", un flottant: %f\n" 42 "foo" 3.14;; Un entier: 42, une chaîne: "foo", un flottant: 3.14

Quel type pour la fonction Printf.printf ?

Si on exécute la fonction Printf.printf dans le terminal quel est le type du résultat ?

# Printf.printf "1+1 = %d\n" 2 ;; 1+1 = 2 - : unit = () #

Le résultat est du type unit. Ce type contient une seule valeur spéciale notée ().

Il est utilisé par les fonctions qui ne renvoient pas de résultats (affichage par exemple) ou qui ne prennent aucun argument.

On peut le voir comme un équivalent de void en Java.

Lecture au clavier

Plusieurs fonctions permettent de lire des données saisies au clavier :

Ces fonctions prennent () en argument

Arguments d'un programme

Dans les langages comme C ou Java, il y a une fonction principale main

Cette dernière reçoit en argument un tableau contenant les arguments passés au programme sur la ligne de commande.

Dans les langages sans fonction principale comme OCaml (mais aussi Python ou Javascript), les arguments sont stockés dans un tableau global. En OCaml se tableau est dans la variable globale. Sys.argv.

On peut accéder aux éléments d'un tableau avec la notation t.(i).
Exemple :

if Array.length Sys.argv >= 1 then Printf.printf "Le premier argument est %s\n" Sys.argv.(1) ;;

Le tableau contient toujours au moins une case, le nom du programme dans lequel on est (dans Sys.argv.(0))

Expressions

Structures d'un programme

Un programme OCaml est consituté d'une suite d'éléments, terminés par ;;. Ces éléments peuvent être :

Il n'y a pas de point d'entrée, un programme est exécuté dans l'ordre du fichier.

En OCaml il n'y a pas de notion de « d'instruction », il n'y a que des expressions.

if/then/else

Un test if/then/else est une expression dont l'évaluation renvoie la valeur de l'expression dans la branche then ou else

Les deux expressions de chaque branche doivent avoir le même type

Ainsi, on peut écrire :

1 + (if x > 42 then 3 else 4)

Cette expression renvoie 4 si x est plus grand que 42 et 5 sinon.
Si on compare du code C++/Java et du code OCaml

let y = if x > 42 then 4 else 5;; int y; if (x > 42) { y = 4; } else { y = 5; }

if/then/else (2)

Si la branche then est du type unit (pas de résultat), alors on peut omettre la branche else

if e > 10 then Printf.printf "e est plus grand que 10!\n"

Si on veut mettre plusieurs instructions de type Unit à la suite, on peut utiliser les mots clés begin et end et séparer les expressions par des ;.

if e > 10 then begin Printf.printf "e est plus grand que 10!\n"; Printf.printf "Si si je vous jure !\n"; Printf.printf "Il est vraiment plus grand!\n" (* pas de ; ici *) end

begin et end jouent le même rôle que { et } en Java.

Les booléens

L'algèbre de Boole (George Boole, 1847) est une branche de l'algèbre dans laquelle on ne considère que deux valeurs : true et false.
Les opérations sur ces valeurs sont la négation (not), le « ou logique » (||) et le « et logique » (&&).

On peut manipuler ces objets en OCaml, comme on le fait avec des entiers, des nombres à virgule ou des chaînes de caractères.

# true ;; - : bool = true # false ;; - : bool = false # not true ;; - : bool = false # true || false ;; - : bool = true # true && false ;; - : bool = false

Les comparaisons

Les booléens servent à exprimer le résultat d'un test. Un cas particulier de test sont les comparaisons. Les opérateurs de comparaisons en OCaml sont :

Symbole Description
= égal
<> différent
< inférieur
> supérieur
<= inférieur ou égal
>= supérieur ou égal

Attention : dans les premiers cours on ne comparera que des nombres. Les comparaisons d'autres types (chaînes de caractères par exemple) seront expliquée plus tard. Les comparaisons == et != existent aussi, mais on les verra plus tard.

Les comparaisons (exemples)

Le résultat d'une comparaison est toujours un booléens (True ou False) :

# 2 = 1 + 1 ;; - : bool = true # 3 <= 10 ;; - : bool = true # let x = 4;; val x : int = 4 x > 3 && x < 8;; - : bool = true # x <> 4 ;; - : bool = false

Définition de variables

Une variable est un moyen de donner un nom au résultat d'un calcul.
En OCaml, une variable est une suite de caractères qui commence par une lettre minuscule ou un « _ » et contient des lettres, des chiffres ou des « _ ».
On définit une variable avec le mot clé « let ».

# let x = 2 ;; val x : int = 2 # let y = 3 ;; val y : int = 3 # let z = x + y;; val z : int = 5

Définition de variables locales

On peut définir des variables locales à une expression avec les mots clés let … in

# let x = 2 in x + x;; - : int = 4 # let y = 3 ;; val y : int = 3 # let z = 4 in z + y;; - : int = 7 # x + y;; Error: Unbound value x

L'expression let x = e1 in e2 permet de définir la variable x uniquement le temps du calcul de e2. Elle prend tout son sens lorsqu'on la combine à d'autres expressions comme le if/then/else.

Définition de variables locales (exemple)

On peut comparer les deux codes OCaml et Java :
let norm = if z > 10 then let x2 = x *. x in let y2 = y *. y in sqrt (x2 +. y2) else -1.0 ;; double norm; if (z > 10) { double x2 = x * x; double y2 = y * y; norm = Math.sqrt (x2 + y2); } else { norm = -1.0; }
Dans les deux cas, les variables x2 et y2 ne sont plus visibles en dehors du bloc then.

Fonctions

Définitions de fonctions

En OCaml, on définit une fonction avec le mot clé let

let carre n = n * n ;; let aire_triangle base hauteur = base *. hauteur * 0.5 ;; let a = aire_triangle 5.0 14.5 ;;

La syntaxe générale d'une fonction est :

let f x1 … xn = e

e est l'expression dont la valeur est renvoyée.
⇒ il n'y a pas de mot-clé return en OCaml.
Bien sûr, un fonction peut avoir un corps complexe avec des let … in, des if/then/else

Exemple : formattage d'une heure

On veut écrire une fonction qui prend en argument un nombre de secondes et renvoie une chaîne de caractères au format : xj xh xmin xs

let format_time t = let j = string_of_int (t / (24 * 3600)) in let t = t mod (24 * 3600) in let h = string_of_int (t / 3600) in let t = t mod 3600 in let m = string_of_int (t / 60) in let s = string_of_int (t mod 60) in j ^ "j " ^ h ^ "h " ^ m ^ "m " ^ s ^ "s" ;; let s = format_time 145999;; Printf.printf "%s\n" s ;; (* affiche 1j 16h 33m 19s *)

Fonctions récursives

On n'a pas vu comment faire des boucles. Hors la répetition de code est un pilier important de la programmation (et sa raison d'être initiale).

On peut contourner l'absence de boucles en écrivant des fonctions récursives. Une fonction récursive est une fonction qui s'appelle elle même.
Commençons par l'exemple standard de la factorielle, écrit en OCaml :

let rec fact n = if n <= 1 then 1 else n * fact (n-1) ;; Printf.printf "fact 10 = %d\n" (fact 10) ;; (* Affiche 3628800 *)

On introduit des fonctions récursives avec le mot clé let rec

Écritures de fonctions récursives

Lorsqu'on écrit une fonction récursive, on distingue TOUJOURS au deux types de cas

Lorsque l'on fait un appel récursif, l'argument doit toujours « se rapprocher » du cas de base.

let rec fact n = if n <= 1 then (* cas de base *) 1 else (* cas récursif *) n * fact (n-1) (* on se rappelle sur n-1, donc on arrivera à 1 ou 0 à un moment *) ;;

Pour les premiers cours, les fonctions récursives seront toujours

Écriture de fonctions récursives (2)

On donne un autre exemple, la fonction fizzbuzz (utilisée comme « échauffement » dans beaucoup d'interviews techniques)

let rec fizzbuzz_aux i n = if i <= n then (* cas récursif *) let i3 = i mod 3 = 0 in let i5 = i mod 5 = 0 in begin if i3 && i5 then Printf.printf "FizzBuzz\n" else if i3 then Printf.printf "Fizz\n" else if i5 then Printf.printf "Buzz\n"; fizzbuzz_aux (i+1) n (* on se rappelle sur (i+1) → n *) end ;; let fizzbuzz n = fizzbuzz_aux 1 n ;;

Écritures de fonctions récursives (2)

Dans un premier temps, les fonctions récursives auront toujours la forme (pseudo-code) :

let rec f n … = if test sur n then cas de base else cas récursif, appel sur f (n±e)