OCaml : un Langage Fonctionnel

Alan Schmitt

11 septembre 2018

1 / 104

Informations Pratiques

▶ Équipe pédagogique▶ Alan Schmitt (cours, 1 groupe de TP)▶ Barbara Kordy (1 groupe de TP)▶ Chen Qian (1 groupe de TP)▶ Leo Henry (1 groupe de TP)

▶ 4 cours▶ 8 TP + 1 TP noté▶ pas d’examen

https://people.rennes.inria.fr/Alan.Schmitt/teaching/alan.schmitt@inria.fr

Ne pas utiliser mon adresse à l’INSA

2 / 104

Pourquoi apprendre OCaml ?

Objectifs de ce cours

▶ Comprendre des concepts fondamentaux de la programmation(fonctions, types, récursion)

▶ Apprendre à exploiter les atouts de la programmationfonctionnelle

Pourquoi ?▶ Pourquoi s’intéresser à ce style de programmation ?▶ Peut-on résoudre les mêmes problèmes qu’en C ou Java ?

4 / 104

Pourquoi s’intéresser à la programmation fonctionnelle (1)

Approche favorisant des programmes▶ corrects;▶ lisibles;▶ réutilisables ou modifiables.

Un langage de programmation est un outil pointu. Les langagesfonctionnels sont le résultat de nombreuses années de recherche.

5 / 104

Pourquoi s’intéresser à la programmation fonctionnelle (2)

Les langages fonctionnels sont proches des mathématiques. Cesont des langages de haut niveau :

▶ permettant de s’abstraire de l’architecture des machine;▶ donnant des programmes clairs et concis;▶ favorisant un développement rapide;▶ fournissant des outils pour une meilleure sûreté (types).

6 / 104

Exemple: gestion de la mémoire

Allouer une liste en C:struct list * x1 = malloc(sizeof(struct list));struct list * x2 = malloc(sizeof(struct list));if (x1 == NULL || x2 == NULL) return NULL;x1->hd = 1; x1->tl = x2; x2->hd = 2; x2->tl = NULL;return x1;

Allouer une liste en OCaml1 :: 2 :: []

7 / 104

Pourquoi s’intéresser à la programmation fonctionnelle (3)

De nombreux langages intègrent des aspects fonctionnels:▶ Java▶ Objective C▶ JavaScript▶ Swift

8 / 104

Peut-on tout programmer en OCaml?

9 / 104

On peut tout programmer en OCaml

La plupart des langages sont Turing complets.Les langages sont des outils. Un bon outil est un outil adapté auproblème.Ce qui peut être important :

▶ la rapidité pour avoir un programme correct,▶ la facilité de maintenance du programme,▶ la performance (en temps ou mémoire) du programme.

10 / 104

Influence

Haskell Scala

F# Swift

TypeScript, …

11 / 104

Influence

https://facebook.github.io/reason/

12 / 104

Grands succès

https://ocaml.org/learn/success.html

13 / 104

Mirage OShttps://mirage.io/

MirageOS is a library operating system that constructsunikernels for secure, high-performance networkapplications across a variety of cloud computing andmobile platforms. Code can be developed on a normalOS such as Linux or MacOS X, and then compiled into afully-standalone, specialised unikernel that runs under aXen or KVM hypervisor.This lets your services run more efficiently, securely andwith finer control than with a full conventional softwarestack.MirageOS uses the OCaml language, with libraries thatprovide networking, storage and concurrency support thatwork under Unix during development, but becomeoperating system drivers when being compiled forproduction deployment.

14 / 104

Apprendre OCaml

http://ocaml.org

15 / 104

Apprendre OCaml : des livres

http://caml.inria.fr/pub/distrib/books/llc.pdf

http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/

http://programmer-avec-ocaml.lri.fr/

16 / 104

Apprendre OCaml : un MOOChttps://tinyurl.com/ocamooc3

Début du cours le 17 septembre

17 / 104

Introduction

Un langage de la famille ML

fonctionnel les fonctions sont des valeurs de première classetypé inférence de types et types polymorphes

let composition f g = fun x -> f (g x)

val composition : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b =<fun>

filtrage avec déclaration de nouveaux typestype cell = T | F

let rule110 triple = match triple with| (T,T,T) | (T,F,F) | (F,F,F) -> F| _ -> T

type cell = T | Fval rule110 : cell * cell * cell -> cell = <fun>

19 / 104

Un langage fonctionnel

▶ en maths:N → Nn 7→ 2n + 3

▶ en C (nom obligatoire, instruction return):int f (int x) { return 2*x + 3; }

▶ en OCamlfun x -> 2*x + 3

Avantages :▶ tout est expression, assemblées comme des briques Lego▶ raisonnement local (pas d’effet de bord)

20 / 104

Exemple

let rec fact = fun n -> if n < 2 then 1 else n * (fact (n-1))

let res = fact 10

val fact : int -> int = <fun>val res : int = 3628800

21 / 104

Programmes

Un programme est une suite de phraseslet identifiant = expression

comme danslet rec fact = fun n -> if n < 2 then 1 else n * (fact (n-1))

let res = fact 10

Exécuter un programme, c’est exécuter toutes ses phrases dansl’ordre (pas de main)Exécuter une phrase, c’est calculer la valeur de expression, etd’associer le nom identifiant à cette valeur

22 / 104

Deux outils pour d’exécuter les programmes

InterprèteMéthode interactive pour écrire des programmes. OCaml exécutechaque phrase, et imprime le résultat de son évaluation sous laforme val identifiant : type = valeur.let rec fact = fun n -> if n < 2 then 1 else n * (fact (n-1))

let res = fact 10

val fact : int -> int = <fun>val res : int = 3628800

avantages interactif, permet d’évaluer des programmes partiels,donne les types et valeurs des phrases

inconvénients lent, utilisable que pour le développement duprogramme, OCaml doit être installé

23 / 104

Deux outils pour d’exécuter les programmes

CompilateurUn outil transformant le programme en du code machineocamlopt -o fact fact.ml./fact

avantages rapide, pas besoin d’avoir à installer OCamlinconvénients n’imprime rien, sauf si instruction spécifique

let rec fact = fun n -> if n < 2 then 1 else n * (fact (n-1))

let res = fact 10

let pr = Printf.printf "résultat : %d\n" res

ocamlopt -o fact2 fact2.ml && ./fact2

résultat : 3628800

24 / 104

Les définitions

En Caml une définition consiste à donner un nom à une valeurSyntaxelet identifiant = expression

Exemplelet x = 3 + 5

val x : int = 8

Définitions récursivesSi expression mentionne nom (fonctions récursives), on utiliselet rec nom = expression

25 / 104

Les définitions

Attention: un nom x désigne la valeur, pas l’expression

let x = 5-3 val x : int = 2

let y = 2*x val y : int = 4

let x = 1 val x : int = 1

let res = y val res : int = 4

26 / 104

Portée des noms

(* À ce niveau aucun nom n’est défini *)

let x =(* x n’est toujours pas défini *)1 + 2

(* x est maintenant défini et vaut 3 *)

let x =(* x vaut toujours 3 *)x + 1 (* le x est l’ancien qui vaut 3 *)

(* un nouveau nom x cache l’ancien, et vaut 4 *)

let rec fact =(* fact est défini, et vaudra le résultat de l’évaluation du reste *)fun n -> if n < 2 then 1 else n * (fact (n - 1))(* le fact ci-dessus est le même que celui qu’on défini *)

27 / 104

Le typage

Le typage est une technique pour détecter automatiquement uneclasse d’erreurs de programmation:let x = 1 + 2 * 3

val x : int = 7

maislet x = 1 + "toto"

Characters 12-18:let x = 1 + "toto";;

^^^^^^Error: This expression has type string

but an expression was expected of type int

28 / 104

Limites du typage▶ Correct et bien typé:

let rec fact = fun n -> if n < 2 then 1 else fact(n - 1) * n

val fact : int -> int = <fun>

▶ Incorrect et mal typé:let rec fact = fun n -> if n < 2 then 1 else fact(n - "toto") * n

Characters 54-60:let rec fact = fun n -> if n < 2 then 1 else fact(n - "toto") * n

;;^^^^^^

Error: This expression has type stringbut an expression was expected of type int

▶ Incorrect mais bien typé:let rec fact = fun n -> if n < 2 then 1 else fact(n + 1) * n

val fact : int -> int = <fun>

29 / 104

À quoi servent les types ?▶ à éviter segmentation fault

▶ les types capturent la structure de la mémoirelet x = 3 + "toto"

Characters 12-18:let x = 3 + "toto";;

^^^^^^Error: This expression has type string

but an expression was expected of type int

▶ à ne pas oublier de castype foo = A | Blet f x = match x with

| A -> 1

Characters 27-50:..........match x with| A -> 1..

Warning 8: this pattern-matching is not exhaustive.Here is an example of a value that is not matched:Btype foo = A | Bval f : foo -> int = <fun>

30 / 104

Les catégories d’expressions

let rec fact = fun n -> if n < 2 then 1 else (fact (n - 1)) * n

▶ les expressions réduites à une valeur▶ les nombres▶ les fonctions▶ …

▶ les expressions réduites à un nom▶ les appels de fonction▶ les expressions conditionnelles▶ les expressions de filtrage

31 / 104

Les valeurs élémentaires

Les valeurs élémentaires : les nombres entiers

▶ valeurs dans [−230, 230 − 1] ou [−262, 262 − 1]

▶ type int▶ opérateurs principaux :

+ - * / mod

▶ exemple :let res = 5 / 2

val res : int = 2

33 / 104

Les valeurs élémentaires : les nombres flottants

▶ valeurs : 41.5, 24e5▶ type : float▶ opérateurs principaux :

+. -. *. /. **

▶ fonctions principales :sqrt log exp sin cos asin acos tan atan

▶ exemple :let res = 5. /. 2.

val res : float = 2.5

34 / 104

Les valeurs élémentaires : les booléens

▶ les 2 valeurs :true false

▶ type : bool▶ opérateurs principaux :

not && ||

▶ Attention: && et || sont évalués de gauche à droite

35 / 104

Les valeurs élémentaires : les caractères

▶ valeurs :'3' 'a' ';'

▶ type : char▶ opérations : voir cours sur la programmation impérative et

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

36 / 104

Les valeurs élémentaires : les chaînes

▶ valeurs :"Hello World!"

▶ type : string▶ opérateurs principaux : ^ (concaténation), String.length▶ http://caml.inria.fr/pub/docs/manual-ocaml/

libref/String.html

37 / 104

Les valeurs élémentaires : l’unité

▶ unique valeur : ()▶ type : unit▶ utilisé comme type de retour des fonctions qui ne renvoient

rienlet res = print_endline

val res : string -> unit = <fun>

38 / 104

Les valeurs élémentaires : les fonctions

▶ valeur de la forme fun nom -> expression

fun x -> 3 * x + 1

- : int -> int = <fun>

▶ type argument -> résultat▶ opérateur principal, l’application (dénoté par la juxtaposition)

(fun x -> 3 * x + 1) 5

- : int = 16

Ces fonctions sont anonymes. Pour leur donner un nom, on utiliseune définition:let mafonction = fun x -> 3 * x + 1

val mafonction : int -> int = <fun>

39 / 104

Comment lire le type des fonctions ?

Le parenthésage à droite est implicite dans l’expression du type desfonctions

int -> int -> int -> int=

int -> (int -> (int -> int))

Fonction qui prend un entier en argument, qui rend une fonctionqui prend un entier en argument, qui rend une fonction de entierdans entier.

40 / 104

Fonctions : ordre supérieur

Une fonction est une valeur : elle peut être l’argument ou lerésultat d’autres fonction.Une fonctionnelle est une fonction acceptant en argument et/ourendant en résultat d’autres fonctions.

41 / 104

Fonctionnelles : exercices

Soit la fonction sin : float → float▶ définir en Caml une fonction g

g : x 7→ sin xx

▶ définir en Caml une fonctionnelle hh : f 7→ (x 7→ f(x)

x )

42 / 104

Fonctionnelles : solutions

let g = fun x -> (sin x)/.x

val g : float -> float = <fun>

let h = fun f -> (fun x -> (f x)/.x)

val h : (float -> float) -> float -> float = <fun>

let hs1 = h sin

val hs1 : float -> float = <fun>

(c’est la fonction sin(x)/x)let hs2 = fun x -> (h sin) x

val hs2 : float -> float = <fun>

(c’est évidemment la même fonction)

43 / 104

Valeurs composées : NUplets

Valeurs: (e1, e2, e3, ...)Type: (t1 * t2 * t3 * ...)

let triplet = (1, 1.2, true)

val triplet : int * float * bool = (1, 1.2, true)

let pair = fst((1,2+3),3)

val pair : int * int = (1, 5)

44 / 104

Conversions

int_of_float

- : float -> int = <fun>

float_of_int

- : int -> float = <fun>

int_of_char

- : char -> int = <fun>

…

45 / 104

Expressions

Définitions locales

let nom = expr1 in expr2

Sémantique1. on évalue expr1, qui donne val12. on évalue expr2 en ayant associé nom à val1

Exemplelet res =

let x = (11 + 10) in x + x

val res : int = 42

AttentionEn OCaml, let est utilisé à la fois pour introduire une phrase etpour introduire une définition locale

47 / 104

Définitions locales et séquentialité

Une utilisation courante des définitions locales est de choisir unordre d’évaluation.let p = (print_endline "Hello", print_endline "World")

WorldHelloval p : unit * unit = ((), ())

let p =let res1 = print_endline "Hello" inlet res2 = print_endline "World" in(res1,res2)

HelloWorldval p : unit * unit = ((), ())

48 / 104

Noms

Un nom est simplement un synonyme pour la valeur associée.L’évaluer revient à retourner cette valeur. Le type du nom est letype de la valeur.let x = 40 + 2

val x : int = 42

let res = x

val res : int = 42

49 / 104

Expressions conditionnelles (1)if expr1 then expr2 else expr3

Sémantique1. on évalue expr1, qui doit être de type booléen, en v12. selon v1, on évalue expr2 ou expr3, qui sont de même type

Exemples

let res = (if 3=4 then 2+7 else 7-7*2) + 4 val res : int = -3

let res = (if 3=4 then "foo" else 7-7*2) + 4

Characters 23-28:let res = (if 3=4 then "foo" else 7-7*2) + 4;;

^^^^^Error: This expression has type string

but an expression was expected of type int

50 / 104

Expressions conditionnelles (2)

On peut écrireif expr1 then expr2

qui est équivalent àif expr1 then expr2 else ()

=⇒ le type de expr2 doit être compatible avec unit

let res = if true then "foo"

Characters 23-28:let res = if true then "foo";;

^^^^^Error: This expression has type string

but an expression was expected of type unit

51 / 104

Le filtrage

Expressions de filtragematch expr with| motif1 -> expr1| motif2 -> expr2...| motifn -> exprn

SémantiqueOn évalue expr et sa valeur v est confrontée aux motifs.On évalue ensuite l’expression associée au premier motif quiaccepte la valeur v.Toutes les branches doivent retourner une valeur du même type.

Exemplelet res =

let b = false inmatch b with| true -> "foo"| false -> "bar"

val res : string = "bar"

53 / 104

Filtres de valeurs, filtre universel, combinaison▶ fitrage de valeur (true, "foo", 3, (), …): le motif

3

est « rigide », il accepte un seul élément, l’élément 3.▶ filtre universel (_): le motif

_

est un motif qui accepte tous les éléments▶ un filtre (m1,m2) accepte les paires (v1,v2) si m1 accepte v1

et m2 accepte v2. Par exemple,(true,_)

accepte toutes les paires dont le premier élément est true :(true,true)(true,55)(true,(4,5.67))...

54 / 104

Noms dans les motifs

Un nom dans un motif est un filtre universel qui est associe le nomà la valeur acceptée dans l’expression associéelet res =

match (1,2) with| (x,1) -> x (* ce motif n’accepte pas la valeur *)| (x,2) -> x + 10 (* valeur acceptée, x est associé à 1 *)| (_,_) -> 0

val res : int = 11

let sumpair = fun x ->match x with| (x1,x2) -> x1+x2

val sumpair : int * int -> int = <fun>

C’est une manière d’accéder aux éléments d’un nuplet

55 / 104

Noms dans les motifsAttentionlet x = 12

val x : int = 12

let egal_12 = fun n -> match n with| x -> true| _ -> false

Characters 50-51:| _ -> false;;^

Warning 11: this match case is unused.val egal_12 : 'a -> bool = <fun>

let res = egal_12 42

val res : bool = true

Un nom dans un motif n’est jamais remplacé par une valeur qui luiserait associée

56 / 104

Restrictions sur les motifs▶ une même variable ne peut apparaître qu’une seule fois par

motif: le motif doit être linéairelet diag p = match p with| (x,x) -> true| _ -> false

Characters 31-32:| (x,x) -> true

^Error: Variable x is bound several times in this matching

let diag p = match p with| (x,y) -> x=y

val diag : 'a * 'a -> bool = <fun>

▶ les valeurs acceptées par les motifs ne sont pas forcémentdisjointes

▶ le premier motif qui accepte la valeur est celui utilisé

57 / 104

Définitions et motifsLes définitions globale ou locale sont en fait de la formelet motif = expressionlet motif = expression in expression

On peut donc écrire :let (x,y) = (1+2, "foo" ^ "bar")

val x : int = 3val y : string = "foobar"

pour accéder aux éléments d’une paire;let () = print_endline "hello" (* filtrage rigide sur () *)

hello

si on sait que le résultat est ();let _ = 12

- : int = 12

si on veut ignorer le résultat.58 / 104

Fonctions et motifs

Comme pour les définitions, les fonctions sont de la formefun motif -> expression

Exemplelet sumpair = fun (x1,x2) -> x1+x2

val sumpair : int * int -> int = <fun>

59 / 104

Fonctions : combien d’arguments ?

▶ fonction à un argumentlet carre = fun x -> x*.x

val carre : float -> float = <fun>

▶ fonction à plusieurs arguments (?)let distance = fun (x,y) -> sqrt(carre(x)+.carre(y))

val distance : float * float -> float = <fun>

en fait un seul argument: un couple▶ la version à deux arguments:

let distance = fun x -> fun y -> sqrt(carre(x)+.carre(y))

val distance : float -> float -> float = <fun>

60 / 104

Syntaxe des fonctionsUne fonction à un argumentlet nom = fun x -> expr

peut s’écrirelet nom x = expr

De la même manière, une fonction attendant une pairelet sumpair = fun (x1,x2) -> x1+x2

peut s’écrirelet sumpair (x1,x2) = x1+x2

Enfin, une fonction à deux argumentslet foo = fun x -> fun y -> expr

peut s’écrirelet foo x y = expr

(et pareil pour 3, 4, … arguments)61 / 104

Application d’une fonction à plusieurs argumentsAppliquer une fonction = remplacer x par 3(fun x -> fun y -> x + y) 3

devient(fun y -> 3 + y)

C’est une nouvelle fonction. On parle alors d’application partielle.let f = fun x -> let _ = print_endline "argument 1" in

fun y -> let _ = print_endline "argument 2" inx + y

let _ = print_endline "avant"let res1 = f 3let _ = print_endline "après"let res2 = res1 4

avantargument 1aprèsargument 2val f : int -> int -> int = <fun>val res1 : int -> int = <fun>val res2 : int = 7

62 / 104

Les fonctions retardent l’exécutionÉvaluer l’expressionfun () -> print_endline "Hello"

retourne immédiatement la fonction mais ne l’exécute pas. Lafonction sera exécuté à chaque fois qu’elle sera appelée.En revanche, évaluer l’expressionprint_endline "Hello"

affiche Hello et retourne ().let foo () = print_endline "Hello"let _ = foo ()let _ = foo ()

HelloHelloval foo : unit -> unit = <fun>

let foo = print_endline "Hello"let _ = foolet _ = foo

Helloval foo : unit = () 63 / 104

Exhaustivité

Soit la définition :let trait_dir dir = match dir with| "nord" -> 0| "sud" -> 1| "est" -> 2| "ouest" -> 3

quel est le comportement de Caml ?Characters 20-94:

....................match dir with| "nord" -> 0| "sud" -> 1| "est" -> 2| "ouest" -> 3..

Warning 8: this pattern-matching is not exhaustive.Here is an example of a value that is not matched:""val trait_dir : string -> int = <fun>

64 / 104

La fonction et logique

et : bool * bool -> bool

x y et (x,y)true true truetrue false falsefalse true falsefalse false false

let et (x,y) = match (x,y) with| (true,true) -> true| (true,false) -> false| (false,true) -> false| (false,false) -> false

val et : bool * bool -> bool = <fun>

65 / 104

Exercice de filtrage (1)Imaginer une définition de la fonction et plus conciselet et (x,y) = match (x,y) with| (true,y) -> if y then true else false| (false,y) -> false

val et : bool * bool -> bool = <fun>

let et (x,y) = match (x,y) with| (true,y) -> y| (false,y) -> false

val et : bool * bool -> bool = <fun>

let et (x,y) = match x with| true -> y| false -> false

val et : bool * bool -> bool = <fun>

let et (x,y) = if x then y else false

val et : bool * bool -> bool = <fun>

66 / 104

Filtrages particuliers

▶ Combinaison de motifslet trait_caract c = match c with| 'a' | 'e' | 'i' | 'o' | 'u' | 'y' -> "voyelle"| _ -> "pas voyelle"

▶ Filtrage d’intervalle de caractèreslet f c = match c with| 'a' .. 'z' -> "lettre"| _ -> "pas lettre"

▶ Nommage de la valeur filtrée, <motif> as <nom>let maj c = match c with| ('a'..'z' as l) -> char_of_int (int_of_char l - 32)| x -> x

67 / 104

Exercice de filtrage (2)Supposons donnée une fonction:val f : int -> int * int * int = <fun>

Écrire une fonction de typeval g : int -> bool = <fun>

telle que:▶ g x = true si le triplet f x contient au moins un zéro,▶ g x = false sinon.

let g x = match f x with| (0,_,_) -> true| (_,0,_) -> true| (_,_,0) -> true| _ -> false

let g x = match f x with| (0,_,_) | (_,0,_) | (_,_,0) -> true| _ -> false

68 / 104

begin et endLes filtrages imbriqués peuvent poser problèmelet bug b g = match b with

| true ->match g with| "foo" -> 1| _ -> 0

| false -> -1

Characters 93-98:| false -> -1;;^^^^^

Error: This pattern matches values of type boolbut a pattern was expected which matches values of type string

let bug b g = match b with| true -> begin

match g with| "foo" -> 1| _ -> 0

end| false -> -1

val bug : bool -> string -> int = <fun>

69 / 104

Polymorphisme & Inférence detypes

Le polymorphisme

certaines fonctions peuvent être appliquées à des arguments dontle type n’est pas tout le temps le même : fonctions génériques oupolymorpheslet first (x,y) = x

val first : 'a * 'b -> 'a = <fun>

let _ = first (3, "foo")

- : int = 3

let _ = first (true, first)

- : bool = true

71 / 104

Variables de type

les parties génériques du type sont représentées par des variablesde type notées 'a, 'b, …

▶ first:- : 'a * 'b -> 'a = <fun>

▶ doublon:let doublon x = (x,x)

val doublon : 'a -> 'a * 'a = <fun>

▶ un changement de structurelet chg_struct ((x,y),z) = (y,(x,z))

val chg_struct : ('a * 'b) * 'c -> 'b * ('a * 'c) = <fun>

72 / 104

Exercice : polymorphisme

Définir la fonction identitéval id : 'a -> 'a = <fun>

qui renvoie son argument, et la fonction de compositionval comp : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b = <fun>

qui prend en argument une paire de fonction (f,g) et rend lafonction composéelet id x = x

let comp (f,g) = fun x -> f (g x)

oulet comp (f,g) x = f (g x)

73 / 104

Inférence de type

OCaml devine les types, et utilise cette information pour compilerle programme.let add x y = x + y

val add : int -> int -> int = <fun>

n’est pas compilé commelet addf x y = x +. y

val addf : float -> float -> float = <fun>

C’est pour cela que l’on distingue + et +..

74 / 104

Récursivité

Factorielle

▶ définition intuitive: fact n = 1 * 2 * … * n▶ définition mathématique:

fact(n) = 1 si n < 2

fact(n) = n ∗ fact(n − 1) si n ≥ 2

▶ en OCamllet rec fact n = if n < 2 then 1 else n * (fact (n-1))

val fact : int -> int = <fun>

let _ = fact 5

- : int = 120

76 / 104

Calcul de factoriellePour calculer e1 * e2, on calcul d’abord e1, puis on calcule e2,puis on multiplie les résultats

fact 55 * (fact 4)5 * (4 * (fact 3))5 * (4 * (3 * (fact 2)))5 * (4 * (3 * (2 * (fact 1))))5 * (4 * (3 * (2 * 1)))5 * (4 * (3 * 2))5 * (4 * 6)5 * 24120

Lors de l’appel récursif à fact, on doit garder de l’informationpour les calculs à faire après

77 / 104

Fonctions récursives

Une définition récursive valide comporte au moins 2 cas :▶ un ou plusieurs cas de base (où figure un élément particulier)

if n < 2 then 1

▶ un ou plusieurs cas récursifs, utilisant la fonction en cours dedéfinitionelse n * (fact (n-1))

Attention l’appel récursif doit « se rapprocher » du cas de base.Sinon: risque de boucle infinielet rec fact = fun n -> if n < 2 then 1 else n * (fact (n+1))

78 / 104

Anatomie d’une fonction récursivelet rec funrec arg =

if arg > 4 then 0 (* cas de base *)else (* cas récursif *)

(* code exécuté avant l’appel récursif *)let _ = Printf.printf "avant, arg = %d\n" arg in(* appel récursif, il faut se souvenir de arg pour après *)let res = funrec (arg + 1) in(* retour de l’appel récursif, on peut utiliser res et arg *)Printf.printf "après, arg = %d, res = %d\n" arg res;(* valeur finale retournée *)(res + 10)

let res = funrec 1

avant, arg = 1avant, arg = 2avant, arg = 3avant, arg = 4après, arg = 4, res = 0après, arg = 3, res = 10après, arg = 2, res = 20après, arg = 1, res = 30val funrec : int -> int = <fun>val res : int = 40

79 / 104

Graphiquement

Code

Avant (arg)Récursion

Après (arg)

Exécution

Avant (1)

Avant (2)

Avant (3)

Avant (4)

Après (4)

Après (3)

Après (2)

Après (1)

80 / 104

Mini guide de traduction

int power(int v, int n) {int res = 1;while (n > 0) {res = res * v;n = n - 1;

}return res;

}

let power v n =let rec aux res curn =

if curn > 0 thenlet res' = res * v inlet curn' = curn - 1 inaux res' curn'

elseres

in aux 1 n

val power : int -> int -> int = <fun>

let rec power v n =if n = 0 then 1else v * (power v (n-1))

val power : int -> int -> int = <fun>

81 / 104

Récursion terminale

Si on se souvient de trop de choses, on tombe en panne demémoirelet rec stupide n = if n <= 0 then 0 else 1 + (stupide (n-1))let res = stupide 265000

Stack overflow during evaluation (looping recursion?).

Si on retourne directement le résultat de l’appel récursif, alorsOCaml optimise et ne se souviens plus des argumentslet rec malin n acc =

if n <= 0 then acc else let acc' = acc + 1 in malin (n-1) acc'let res = malin 265000 0

val malin : int -> int -> int = <fun>val res : int = 265000

82 / 104

Domaines de récursion

▶ cas classique: la récurrence sur les entiers▶ cas de base pour 0▶ valeur en n+1 calculée avec la valeur pour n

▶ listes▶ cas de base pour la liste vide▶ valeur pour l’ajout d’un élément calculé avec la valeur pour le

reste de la liste▶ arbres, etc …

83 / 104

Exemple

U0 = 4

Un = 2Un−1 + 3n pour n > 0

let rec u x = if x = 0 then 4 else 2 * u (x-1) + 3 * xlet res = u 10

val u : int -> int = <fun>val res : int = 10204

Version avec récursion terminalelet urt x =

let rec aux acc n =if n > x then accelse let acc' = 2 * acc + 3 * n in

aux acc' (n+1)in aux 4 1

let res = urt 10

val urt : int -> int = <fun>val res : int = 10204

84 / 104

Récursivité croisée

let rec nom1 = expr1and nom2 = expr2

Les expressions expr1 et expr2 peuvent utiliser nom1 et nom2.let rec pair n = if n = 0 then true else impair (n-1)and impair n = if n = 0 then false else pair (n-1)

val pair : int -> bool = <fun>val impair : int -> bool = <fun>

85 / 104

Spécificités de Caml

Opérateurs de comparaison

= <> < > <= >=

let _ = "foo" = "foo"

- : bool = true

let _ = "foo" <> "foo"

- : bool = false

let _ = "foo" < "bar"

- : bool = false

let _ = "foo" > "foo"

- : bool = false

Attention L’opérateur « == » existe mais il ne faut pas l’utiliser.

87 / 104

Divers : les priorités en Caml (1)

L’application est notée par la simple juxtaposition de la fonction etde son argument.expr expr

Une suite d’applications est parenthésée par défaut à gauche.expr expr expr

est équivalent à(expr expr) expr

88 / 104

Divers : les priorités en Caml (2)

priorités décroissantes1. application: f x2. opérateur arithmétiques: f x + 1 est (f x) + 13. construction de n-uplets: f x + 1,2 est ((f x) + 1),24. abstraction: fun x -> f x + 1,2 est fun x -> (((f x) +

1),2)Ne pas hésiter à mettre des parenthèsesL’opérateur - est par défaut la soustraction et pas l’opposé: f -1est « f moins un ». Pour appliquer une fonction f à -1 il fautécrire f (-1).

89 / 104

Curryfication

Comparer et typer les définitions :let f (x,y) = x + 2*y

let g x y = x + 2*y

let _ = f (4,5)

- : int = 14

let _ = g 4 5

- : int = 14

90 / 104

Curryfication

▶ f doit toujours être appelée avec une paire d’entiers commeargument

▶ g peut être appelée avec un entier ou deux▶ g 4 est la fonction fun y -> 4 + 2*y

91 / 104

Application partielle

let compdbl f x = f (f x)

val compdbl : ('a -> 'a) -> 'a -> 'a = <fun>

let square x = x*x

val square : int -> int = <fun>

compdbl square 5

- : int = 625

let puiss4 = compdbl square

val puiss4 : int -> int = <fun>

92 / 104

Un exemple

Fonctionnelle d’itération

Ecrire une fonctionnelle qui correspond à la sémantique del’itération pour

▶ caractérisation à partir d’exemples de l’itération « pour »▶ établissement des lois de récurrence▶ écriture de la fonctionnelle repeter▶ constat de l’efficacité de cette fonctionnelle

94 / 104

Exemples d’itérations

1. calcul itératif de 2n

2. calcul itératif du terme de rang n de la suite▶ u0 = 3▶ un = 3 ∗ un−1 + 5

3. calcul itératif du terme de rang n de la suite de fibonacci▶ u0 = 0▶ u1 = 1▶ un = un−1 + un−2

95 / 104

La boucle classique

puiss := 1 initpour i:=1 à n faire

puiss := puiss*2 f

U := 3 initpour i:=1 à n faire

U := U*3+5 f

96 / 104

La sémantique de toute itération (1)

Similitudes:▶ utilisation d’une variable v de cumul (U , puiss)▶ initialisation de v▶ le contenu de la variable subit à chaque pas une

transformation v := f(v)▶ f(x) = x*2 pour 2n

▶ f(x) = x*3+5 pour la suite Un

97 / 104

La sémantique de toute itération (2)

Schéma général

x := x0pour i := 1 à n faire

x := f(x)

La valeur à rendre est x. Elle dépend de x0, n et f.On cherche F telle que x = F(n, f, x0)

98 / 104

La sémantique de toute itération (3)

valeur de x en fonction de x0, n et f :n = 0 x = F(0, f, x0) = x0n = 1 x = F(1, f, x0) = f(x0)n = 2 x = F(2, f, x0) = f(f(x0))

…cas général: x = F(n, f, x0) = fn(x0)

99 / 104

La loi de récurrence

F(n, f, x0) = fn(x0) = f(fn−1(x0)) = f(F(n − 1, f, x0))

F est en fait la fonctionnelle repeter▶ repeter n f x0 = x0 pour n = 0▶ repeter n f x0 = f (repeter (n-1) f x0) pour n > 0

100 / 104

La fonctionnelle repeter

let rec repeter f x0 n =if n = 0 then x0 else f (repeter f x0 (n-1))

val repeter : ('a -> 'a) -> 'a -> int -> 'a = <fun>

101 / 104

Utilisation de repeterUtiliser l’itérateur repeter pour calculer

▶ 2n

▶ le terme de rang n de la suite▶ u0 = 3▶ un = 3 ∗ un−1 + 5

let puissde2 n = repeter (fun x -> x*2) 1 n

val puissde2 : int -> int = <fun>

let suite n = repeter (fun x -> 3*x+5) 3 n

val suite : int -> int = <fun>

On peut utiliser l’application partielle pour ne pas mentionner nlet puissde2 = repeter (fun x -> x*2) 1

val puissde2 : int -> int = <fun>

let suite = repeter (fun x -> 3*x+5) 3

val suite : int -> int = <fun>

102 / 104

Fibonacci itératif

Revenons à Fibonacci

U := 0; V := 1;pour i:=2 à n faire

Y := V;V := V+U;U := Y;

let fibo n = snd (repeter (fun (x,y) -> (x+y,x)) (1,0) n)

val fibo : int -> int = <fun>

103 / 104

Cumuler les termes d’une suite

Définirsigma(n) =

n∑i=0

Ui

en organisant les calculs de façon à diminuer la complexité.

acc:=0;pour i:=0 à n faire

acc:=s+Ui

let sigma n =snd(repeter

(fun (t,acc) -> (3*t+5,acc+t))(3,0)(n+1))

val sigma : int -> int = <fun>

104 / 104