Table of Contents

Mes notes de cours en ligne: http://gasche.info/tmp/cours-ocaml-paris8-2020.org

Exercices: http://gasche.info/tmp/cours-ocaml-paris8-2020.html

Autre référence: un bon cours sur OCaml en ligne, de Maxence Guesdon, en français:

https://www.good-eris.net/formation-ocaml/

0.1 Livres sur OCaml:

  • "Real World OCaml", disponible aussi en ligne (gratuitement), plutôt centré sur la pratique, suppose plutôt qu'on sait déjà programmer dans un autre langage https://dev.realworldocaml.org/index.html
  • "OCaml from the Very Beginning", pour les débutants, très bon
  • "Apprendre à programmer avec OCaml : Algorithmes et structures de données" utilisé pour des cours à l'université
  • "Le langage Caml": très bon, plus édité, pour une très vieille version du langage (Caml Light), mais la plupart du cours reste pertinent pour OCaml

1 Cours 1: bases de OCaml (fonctions, tuples)

1.1 Exemple de programme

let rec split = function
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x1::x2::rest ->
    let (r1, r2) = split rest in
    (x1::r1, x2::r2)

let rec merge la lb =
  match la, lb with
  | [], li | li, [] -> li
  | a::ra, b::rb ->
    if a < b
    then a :: merge ra lb
    else b :: merge la rb

let rec sort = function
  | [] -> []
  | [x] -> [x]
  | li ->
    let l1, l2 = split li in
    merge (sort l1) (sort l2)

1.2 Présentation de l'outil Learn-OCaml

1.3 Définitions et fonctions.

1.3.1 Définition globale

let <nom> = <expression>
let me = "Gabriel"
let message = "Bonjour " ^ me

let bonjour name =
  "Bonjour " ^ name

let greeting2 (name1 : string) name2 : string =
  "Bonjour " ^ name1 ^ " et " ^ name2

(* quand le nom n'a pas d'importance, on veut juste le résultat: *)
let _ = 1 + 2

1.3.2 Définition locale

let <nom> = <expression> in <expression>
let x = 2

let x4 =
  let x2 = x * x in
  x2 * x2

Définition de fonction:

let <nom> <param1> <param2> ... = <expression>
let pow5 x =
  let x2 = x * x in
  x2 * x2 * x

let abs x =
  if x >= 0
  then x
  else (- x)

1.3.3 Fonctions

fun <nom> .. <nom> -> <expression>
let square = fun x -> x * x
let square_dist = fun x y -> square x + square y

let squares =
  List.map (fun x -> x * x) [1; 2; 3; 4; 5]

Remarque: les deux syntaxes suivantes sont équivalentes

let square x = x * x
let square = fun x -> x * x

Remarque avancée: les trois syntaxes suivantes sont équivalentes

let square_dist x y = square x + square y
let square_dist = fun x y -> square x + square y
let square_dist = fun x -> fun y -> square x + square y

(* et on peut écrire: *)
let square_dist_to_one = square_dist 1
let _ = square_dist_to_one 2

let _ = square_dist 1 2

1.3.4 Polymorphisme

let id x = x
let twice f x = f (f x)
let compose f g = fun x -> f (g x)

1.3.5 Types

(fun x -> x) : 'a -> 'a
(fun x -> x + 1) : int -> int
(fun x -> x > 0) : int -> bool
(fun b -> if b then 1 else (- 1)) : bool -> int
(fun x y -> x + y > 0) : int -> int -> bool
( + ) : int -> int -> int
(fun f x -> f x) : ('a -> 'b) -> 'a -> 'b

Définitions de type

type variable = string

type arith_op = int -> int -> int

type 't binop = 't -> 't -> 't
type arith_op = int binop

*

1.4 N-uplets (tuples)

let date = (2020, 09, 21)
(*
  int * int * int
*)

let next_year date =
  let (year, month, day) = date in
  (year + 1, month, day)

let next_year (year, month, day) =
  (year + 1, month, day)

let _ = next_year date

Remarque: 0-uplet noté ~unit~, expression ~()~

let pas_de_valeur = ()

let main () =
  print_endline "Hello World!"

Exercice:

val swap : ('a * 'b) -> ('b * 'a)

Exercice:

val nom : string * int -> string
val age : string * int -> int

2 Cours 2: bases de OCaml (sommes)

Une somme: le type d'une donnée qui est "soit un Truc, soit un Machin" – et on sait lequel des deux.

Très courant en pratique !

2.1 Définir un nouveau type somme

type <params> <nom> =
  | <Constructeur> of <type> * <type> * <...>
  | <Constructeur> of <type> * <type> * <...>
  <...>
type address =
  | Telephone of int * string
  | Email of string

Constructeurs sans paramètres:

type trois_elements =
  | A
  | B
  | C

2.2 Construire une expression de type somme

<Constructeur> (<expr>, <expr>, <...>)
let me = Email "gabriel.scherer@inria.fr"
let not_really_me = Telephone (33, "123456789")

2.3 Inspecter/décomposer une valeur de type somme

match <expression> with
| <Constructeur>(<nom>, <nom>, <...>) -> <expression>
| <Constructeur>(<nom>, <nom>, <...>) -> <expression>
| <...>
type address =
  | Telephone of int * string
  | Email of string

let how_to_contact address =
  match address with
  | Email mail ->
    "send an email to <" ^ mail ^ ">"
  | Telephone(country_code, number) ->
    "call 0" ^ number ^ " or "
    ^ "+" ^ string_of_int country_code ^ "-" ^ number

Exercice:

val categorie : address -> string
categorie (Email "gabriel.scherer@inria.fr") = "email"
categorie (Telephone (33, "123456789")) = "numero"

Remarque: ~if .. then .. else~ est un cas particulier de ~match~

let abs x =
  if x >= 0 then x else (- x)

let abs x =
  match x >= 0 with
  | true -> x
  | false -> (- x)

3 Cours 3: bases de OCaml (types paramétrés, filtrage, records)

3.1 Types paramétrés

type address =
  | Telephone of int * string
  | Email of string

type 'ty option =
  | None
  | Some of 'ty

let safe_div a b =
  if b = 0 then None
  else Some (a / b)

let maybe_add a (b : int option) = 
  match b with
  | None -> a
  | Some x -> a + x

Le type ~'a option~ est standard en OCaml, déjà présent dans l'environnement de base.

Exercices:

val maybe_add : int -> int option -> int

val bonjour : string option -> string
bonjour None = "Bonjour"
bonjour (Some "Alex") = "Bonjour Alex"

val apply_opt : ('a -> 'b) option -> 'a option -> 'b option

val if_opt : bool option -> 'a -> 'a -> 'a option
if_opt (Some false) "toto" "tata" = Some "tata"
if_opt (Some true) 1 37 = Some 1
if_opt None 1 37 = None

val pair_opt : 'a option -> 'b option -> ('a * 'b) option

3.2 Motifs généraux

Dans le cas général, ce qui est à gauche de la flèche dans la construction ~match~ s'appelle un "motif". Un motif "reconnaît" certaines valeurs, et permet de donner des noms à ses sous-composants.

Nous avons déjà vu d'autres exemples de motifs avec la construction ~let~:

<nom>                       let two = 1 + 1
_                           let _ = 1 + 1
(<motif>, <motif>, <...>)   let (y, m, d) = date

Les motifs peuvent être imbriqués ou mélangés:

let same_address addr1 addr2 =
  match (addr1, addr2) with
  | (Email em1, Email em2) -> em1 = em2
  | (Telephone(cc1, n1), Telephone(cc2, n2)) -> cc1 = cc2 && n1 = n2
  | _ -> false

Il est très courant de "matcher" sur un n-uplet quand on veut inspecter plusieurs choses à la fois. Dans ce cas les parenthèses ne sont pas nécessaires.

let same_address addr1 addr2 =
  match addr1, addr2 with
  | Email em1, Email em2 -> em1 = em2
  | Telephone(cc1, num1), Telephone(cc2, num2) -> cc1 = cc2 && n1 = n2
  | _ -> false

Attention! Un nom dans un motif est toujours interprété comme la déclaration d'une variable, quitte à cacher un nom existant.

Il n'y pas de test d'égalité sur les noms.

let my_email = "gabriel.scherer@inria.fr"

let is_me address =
  match address with
  | Email my_email -> true
  | Email _ -> false
  | Telephone _ -> false

let _ = is_me (Email "toto@example.com")

(* version corrigée *)
let is_me address =
  match address with
  | Email email -> email = my_email
  | Telephone _ -> false

3.3 Records

type <params> <nom> = {
  <champ>: <type>;
  <champ>: <type>;
  <...>
}

{ <champ> = <expr>; <champ> = <expr>; ... }

<expr>.<champ>

{ <champ> = <motif>; <champ> = <motif>; ... }
type point2d = {
  x: int;
  y: int;
}

let origin = { x = 0; y = 0 }

let norm2 p = p.x * p.x + p.y * p.y

4 Cours 4: récursivité (entiers, types récursifs)

4.1 Fonctions récursives sur les entiers/chaînes

let rec <nom> = ... <nom> ...
let rec pow a n =
  if n = 0 then 1
  else a * pow a (n - 1)
let rec repeat s n =
  if n = 0 then ""
  else s ^ repeat s (n - 1)
val repeat: string -> int -> string
repeat "to" 3 = "tototo"

Schéma typique pour les fonctions récursives:

  • un ou plusieurs "cas d'arrêt", où on répond immédiatement
  • un ou plusieurs "cas récursifs", où on se rappelle sur un sous-problème

Idée d'ensemble: une fonction récursive résoud un problème en le découpant en sous-problèmes plus faciles.

Récursion avec accumulateur:

let pow a n =
  let rec pow' acc n =
    if n = 0 then acc
    else pow' (acc * a) (n - 1)
  in pow' 1 n

4.2 Fonction récursive sur un type algébrique

Exercices:

type point = Point of int * int
type vecteur = Vect of int * int
let deplace (Point (x, y)) (Vect (dx, dy)) = Point (x+dx, y+dy)
type moves =
  | Done
  | Slide of vecteur * moves
  | Goto of point * moves

Goto(Point(2,3), Slide(Vect(1,-1), Done))

val count_moves : moves -> int
val end_point : point -> moves -> point 
(* val points : point -> moves -> point list *)
let rec count_moves m =
  match m with
  | Done -> 0
  | Slide (vect, rest) -> 1 + count_moves rest
  | Goto (point, rest) -> 1 + count_moves rest
let rec count_moves moves =
  match moves with
  | Done -> 0
  | Slide(vec, rest) -> 1 + count_moves rest
  | Goto(point, rest) -> 1 + count_moves rest

let rec end_point depart moves =
  match moves with 
  | Done -> depart
  | Slide(vec, rest)->
    let point = deplace depart vec in
    end_point point rest
  | Goto(point, rest) -> end_point point rest

~moves~ est en fait un cas particulier de liste:

type moves =
  | Done
  | Slide of vecteur * moves
  | Goto of point * moves

type 'a option =
  | None
  | Some of 'a

type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist

type 'a list =
  | []
  | (::) of 'a * 'a list

(* on peut écrire *)
1 :: []
1 :: (2 :: [])
1 :: (2 :: (3 :: []))  (* syntaxe courte: [1; 2; 3] *)

match li with
| [] -> ...
| a :: rest -> ...

(* on peut redéfinir `moves` ainsi: *)
type move = Slide of vecteur | Goto of point
type moves = move list

(* exercice *)
val end_point : point -> moves -> point
type 'a list =
  | []
  | (::) of 'a * 'a list

let rec length li =
  match li with
  | [] -> 0
  | a :: rest -> 1 + length rest
val length : 'a list -> int
val nth : int -> 'a list -> 'a option
  (* nth 0 [1; 2; 3] = Some 1
     nth 2 [1; 2; 3] = Some 3
     nth 4 [1; 2; 3] = None *)
val last : 'a list -> 'a option
  (* last [1; 2; 3] = Some 3 *)
let rec length li =
  match li with
  | [] -> 0 
  | a :: rest -> 1 + length rest  
let rec nth n li =
 match li with
  | [] -> None
  | a :: rest ->
    if n = 0 then Some a
    else nth (n-1) rest
let rec last li =
  match li with
  | [] -> None
  | a :: rest ->
    match rest with
    | [] -> Some a
    | _ :: _ -> last rest

let rec last li =
  match li with
  | [] -> None
  | a :: rest ->
    match last rest with
    | None -> Some a
    | Some last -> Some last

let last li =
  let rec last' a li =
    match li with
    | [] -> Some a
    | b :: rest ->
      last' b rest
  in
  match li with
  | [] -> None
  | a :: rest -> last' a rest

let last li =
  let rec last' o li =
    match li with
    | [] -> o
    | b :: rest ->
      last' (Some b) rest
  in last' None li

Remarque: la structure récursive des fonctions respecte la structure récursive des types.

Concept avancé: Arbres n-aires (documents, worklist, etc.)

type ('leaf, 'node) ntree =
  | Leaf of 'leaf
  | Node of 'node * ('leaf, 'node) ntree list

let node n children = Node (n, children)

type doc = (string, string) ntree
let homepage =
  node "page" [
    node "title" [ Leaf "Home Page" ];
    node "menu" [ Leaf "foo/"; Leaf "bar/" ];
    node "body" [ Leaf "..." ];
    node "contact" [
      node "email" [ Leaf "gabriel.scherer@inria.fr" ];
      node "reddit" [ Leaf "gasche" ]
    ];
  ]

type 't worklist = ('t, unit) ntree
let task t = Leaf t
let group worklists = Node ((), worklists)

let worklist =
  let teach = group [
    task "prepare lecture";
    task "go to class";
    task "teach"
  ] in
  let code_review = group [
    task "new major allocator";
    task "statmemprof";
    task "TRMC";
  ] in
  group [ teach; code_review ]
type ('leaf, 'node) ntree =
  | Leaf of 'leaf
  | Node of 'node * ('leaf, 'node) ntree list

type 't worklist = ('t, unit) ntree
val replace
 : 't worklist -> ('t -> 't worklist) -> 't workslit
let _ =
  replace worklist (fun task ->
    if task <> "prepare lecture"
    then task
    else group ["detailed plan"; "lecture notes"]

val replace
 : ('a, 'n) ntree
 -> ('a -> ('b, 'n) ntree)
 -> ('b, 'n) ntree

5 Cours 5: récursivité (listes, ordre supérieur)

5.1 Fonctions d'ordre supérieur sur les listes

La définition des listes est une définition récursive comme les autres (standard, pas besoin de la redéfinir), avec juste une syntaxe un peu particulière pour les construteurs:

type 'a list =
  | [] (* liste vide *)
  | (::) of 'a * 'a list (* élément suivi d'une liste *)

De plus, la syntaxe `[a; b; c]` est disponible, comme une façon plus concise d'écrire `a :: (b :: (c :: []))`.

On analyse les listes par filtrage de motif:

match li with
| [] -> ... (* cas liste vide *)
| head :: rest -> (* élément suivi du reste de la liste *)

Les listes sont un type récursif, et les fonctions qui manipulent des listes seront souvent récursives. Par exemple:

let rec length li =
  match li with
  | [] -> 0
  | _ :: rest -> 1 + length rest

Exercices:

val map : ('a -> 'b) -> 'a list -> 'b list
val filter : ('a -> bool) -> 'a list -> 'a list
val fold_left : ('v -> 'a -> 'a) -> 'v -> 'a list -> 'a list
val fold_right : ('a -> 'v -> 'v) -> 'a list -> 'v -> 'v

val append : 'a list -> 'a list -> 'a list
val rev : 'a list -> 'a list
  val rev_append : 'a list -> 'a list -> 'a list
let rec map f li =
  match li with
  | [] -> []
  | head :: rest -> f head :: map f rest 

let rec map f = function
 | [] -> []
 | x :: xs -> f x :: map f xs

append [1; 2; 3] [4; 5; 6] = [1; 2; 3; 4; 5; 6]
let rec append li1 li2 =
  match li1 with
  | [] -> li2
  | p :: r -> p :: append r li2 

5.2 foldleft et foldright

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
fold_left f a [x1; x2; ...; xn] = f (... (f (f a x1) x2)) xn

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b
fold_right f [x1; x2; ...; xn] a = f x1 (f x2 (... (f xn a) ..))

Exemple: calculer la taille d'une liste

let length li = fold_left (fun acc _elem -> 1 + acc) 0 li
let length li = fold_right (fun _elem acc -> 1 + acc) li  0

Exemple: calculer la somme de tous les éléments (entiers) d'une liste:

let sum li = fold_left (fun acc e -> acc + e) 0 li

Exercice: calculer le plus grand élément d'une liste d'entiers positifs.

let list_max li = fold_left ??? 0 li

let list_max li =
  fold_left (fun acc e -> if acc > e then acc else e) 0 li

let list_max li =
  let update acc e = if acc > e then acc else e in
  fold_left update 0 li

La fonction `foldleft` applique son argument `f` d'abord au premier élément de la liste, puis à tous les éléments jusqu'au dernier.

La fonction `foldright` applique son argument `f` d'abord au dernier élément de la liste, puis à tous les éléments jusqu'au premier.

let rev li = fold_left (fun acc e -> e::acc) [] li

let stutter li =
  fold_right (fun e acc -> e :: e :: acc) li []

Exercice: écrire une fonction

val count_yes_no : ('a -> bool) -> 'a list -> int * int

let count_yes_no p li = fold_left (fun (y,n) e -> 
 if  p e then (y+1,n) else (y,n+1)) (0,0) li    

tel que si `countyesno p li` vaut `(yes, no)`, alors `yes` est le nombre d'éléments `x` de `li` tels que `p x` est vrai, et `no` est le nombre d'éléments `x` de `li` tel que `p x` est faux.

Exercice avancé: une fonction

val eval_poly : int list -> int -> int

telle que, par exemple `evalpoly [a0; a1; a2; a3] x` est égale à `a0 + a1 * x + a2 * x2 + a3 * x3`.

let eval_poly li x =
  let update (sum, p) e =
    (sum + e * p, p * x)
  in
  let (sum, _) = fold_left update (0, 1) li in
  sum

5.3 Pipelines, collections (avancé)

5.3.1 Opérateur de pipeline

let ( |> ) x f = f x

let add n = fun a -> a+n
let double = fun a -> a*2

let _ =
  2
  |> add 3
  |> double
  |> add 2

(En programmation objet, "method chaining")

Courant avec les collections:

input
|> List.map (fun n -> n + 1)
|> List.filter (fun n -> n < 10)
|> List.sort

5.3.2 Collections (avancé)

Exercices avancés:

type 'a seq = unit -> 'a node
and 'a node = Nil | Cons of 'a * 'a seq

val empty : 'a seq
val return : 'a seq
val map : ('a -> 'b) -> 'a seq -> 'b seq
val filter_map : ('a -> 'b option) -> 'a seq -> 'b seq
val concat : 'a seq -> 'a seq -> 'a seq
val concat_map : ('a -> 'b seq) -> 'a seq -> 'b seq

Remarque: utiliser ~map~ plusieurs fois (par exemple)

6 Cours 6: un peu de complexité

6.1 Exemples

Ajouter un élément à la fin d'une liste:

let add_to_end x li = append li [x]

Ajouter un élément en tête d'une liste:

let add_to_beginning x li = x :: li

Coût de calcul ?

Tester si un élément apparaît dans une liste

let rec mem x li =
match li with 
| [] -> false
| head :: rest ->
  head = x || mem x rest

Tester si une liste est incluse dans une autre:

let rec included li1 li2 =
  match li1 with
  | [] -> true
  | head :: rest -> mem head li2 && included rest li2

let rec included_sorted li1 li2 =
  match li1, li2 with
  | [], _ -> true
  | _ :: _, [] -> false
  | a1 :: r1, a2 :: r2 ->
    if a1 < a2 then false
    else if a1 = a2 then included r1 li2
    else (* a1 > a2 *) included li1 r2

  (* exercice *)
let included l1 l2 =
  included_sorted (List.sort compare li1) (List.sort compare li2)

6.2 Notion de complexité

Comment parler de la vitesse d'une fonction ?

  • Mesurer le temps ? Dépend de la machine.
  • Mesurer le nombre d'instruction ? Dépend de l'entrée.
  • Mesurer la variation du nombre d'instruction, "à la louche".

Notation O(…).

Ajouter un élément au début d'une liste: O(1) Ajouter un élément à la fin d'une liste: O(n) `reverse` naïf: O(n2) `reverse` malin: O(n)

Exemple concret: le programme qui génère la documentation du compilateur OCaml mettait 6s à assembler la page web finale. La plupart du temps était passé dans un appel à une fonction qui enlève les éléments dupliqués dans une liste, avec une implémentation en O(n2); utiliser un meilleur algorithme (basé sur un tri; O(n log n)) passe le temps de calcul à 0.4s.

6.3 Exemple de bug de complexité

let rec example n =
  if n = 0 then 1
  else
    let a = example (n - 1) in
    a + a

let rec example_slow n =
  if n = 0 then 1
  else
    example_slow (n - 1) + example_slow (n - 1)

example(0) = K' example(n) = K + example(n-1) O(n)

Complexité de exampleslow?

exampleslow(n) = 2 * exampleslow(n-1) 2 * 2 * 2 * 2 * 2 * … * K' 2n O(2n)

6.4 À retenir

La complexité, c'est la mesure de l'augmentation du temps de calcul en fonction de l'augmentation de la taille de l'entrée, sans tenir compte du facteur multiplicatif précis.

Notions importantes:

  • temps constant, O(1)
  • temps linéaire, O(n)
  • temps quadratique, O(n2)
  • temps exponentiel, O(2n)

7 Cours 7: tableaux

7.1 Motivation: accès en temps constant

let rec nth i li =
  (* exercice: aller chercher le i-ìème élément dans li *)

let li = [10; 11; 12]

let _ = nth 2 li

Les listes permettent d'ajouter un nouvel élément en temps constant, mais l'accès à un élément existant est en temps linéaire (en la position).

Les tableaux sont une structure de donnée différente: leur taille est fixée à la création (ajouter un élément demande de recréer un nouveau tableau, coût linéaire), mais l'accès à un élément se fait en temps constant.

let t = [| 10; 11; 12 |]

let _ = t.(2)

7.2 Utilisation de base

Pour créer un tableau on utilise soit un litéral `[| e1; e2; ..; en |]`, soit les fonctions

Array.make : int -> 'a -> 'a array
Array.init : int -> (int -> 'a) -> 'a array

Pour accéder à la taille d'un tableau (opération en temps constant), on utilise la fonction `Array.length`.

Array.length : 'a array -> int

Exercice: ajouter la somme des éléments d'un tableau d'entier:

let sum_all (t : int array) =
  let rec sum_from i =
    if i >= Array.length t
    then 0
    else t.(i) + sum_from (i + 1)
  in sum_from 0

let () =
  assert (sum_all [|1; 2; 3|] = 6)

Exercice: renverser un tableau (le premier élément du tableau en entrée devient le dernier élément du tableau en sortie):

let reverse t =
  (* exercice *)

let () =
  let t = reverse [|1; 2; 3|] in
  assert (t.(0) = 3)

7.3 Modification en place

Un tableau OCaml est un espace modifiable, on peut changer la valeur des éléments en temps constant.

# let t = [|10; 11; 12|];;
val t : int array = [|10; 11; 12|]
# t.(1) <- 21;;
- : unit = ()
# t;;
- : int array = [|10; 21; 12|]

Par exemple, on peut imaginer un tableau qui représente la position de voitures sur une route: None s'il n'y a pas de voiture sur un segment de la route, et (Some "foo") s'il y a une voiture nommée "foo".

let route = [|None; None; Some "toto"; None; Some "tata"; None|]

On écrit une fonction (avance : string option array -> unit) qui fait avancer chaque voiture d'un segment vers la droite; les voitures à la fin de la route quittent la route.

let avance route =
  let rec loop i =
    if i < 0 then ()
    else
      match route.(i) with
      | None -> ()
      | Some voiture ->
	if i + 1 < Array.length route then begin
	  route.(i + 1) <- Some voiture;
	end;
	route.(i) <- None
  in loop (Array.length route - 1)
let route = [|None; None; Some "toto"; None; Some "tata"; None|];;
avance route;;
route;;
avance route;;
route;;

7.4 Tableaux de tableaux

let matrice = Array.init 3 (fun i -> Array.init 3 (fun j -> (i, j)))

Exercice:

val count_true : bool array array -> int
val negate : bool array array -> unit

Exercices:

val valid : 'a array array -> int * int -> bool
val get : 'a array array -> int * int -> 'a
val set : 'a array array -> int * int -> 'a -> unit

Exercice:

let dirs = [(0, 1); (0, -1); (1, 0); (-1, 0)]

val count_true_neigbors : bool array array -> int * int -> int

val negate_neighbors : bool array array -> int * int -> unit

8 Cours avancé: Property-based testing

8.1 vérifier des propriétés par le test

Formule avec quantificateurs "pour tout": forall li. List.append li [] = li

Idée: tester la formule par génération aléatoire.

#use "topfind";;
#require "qcheck";;

let test_neutral_right =
  QCheck.Test.make
    ~name:"forall li. append li [] = li"
    QCheck.(list int)
    (fun li -> List.append li [] = li)

let _ =
  QCheck_runner.run_tests ~verbose:true
  [ test_neutral_right ]

let test_head =
  QCheck.Test.make
    ~name:"forall la lb. head (append la lb) = head la"
    QCheck.(pair (list int) (list int))
    (fun (la, lb) ->
      List.hd (List.append la lb) = List.hd la)

let _ =
  QCheck_runner.run_tests ~verbose:true [ test_head ]
let test_head =
  QCheck.Test.make
    ~name:"forall la lb. head (append la lb) = head la"
    QCheck.(pair (list int) (list int))
    (fun (la, lb) ->
      QCheck.assume (la <> []);
      (List.hd (List.append la lb) = List.hd la))

let _ =
  QCheck_runner.run_tests ~verbose:true [ test_head ]
let rec sum_naive a b =
  if a = 0 then b
  else if a > 0
  then sum_naive (a - 1) (b + 1)
  else sum_naive (a + 1) (b - 1)

let test_sum =
  QCheck.Test.make
    ~name:"(a + b)"
    QCheck.(let i = int_range (-10) 10 in pair i i)
    (fun (a, b) -> (a + b) = sum_naive a b)

let _ =
  QCheck_runner.run_tests ~verbose:true
  [ test_sum ]

8.2 property-testing et force des conditions

let rec sum li =
  match li with
  | [] -> 0
  | n :: ns -> n + sum ns

let even n = (n mod 2 = 0)

let test_sum_even =
  QCheck.Test.make
    ~name:"even lists have an even sum"
    QCheck.(list int)
    (fun li ->
       QCheck.assume (List.for_all even li);
       even (sum li))

let _ =
  QCheck_runner.run_tests ~verbose:true [ test_sum_even ]

let test_sum_even =
  QCheck.Test.make
    ~name:"even lists have an even sum"
    QCheck.(list (map (fun n -> 2*n) int))
    (fun li ->
       QCheck.assume (List.for_all even li);
       even (sum li))

let _ =
  QCheck_runner.run_tests ~verbose:true [ test_sum_even ]

Difficulté: comment "inverser" une condition de bonne formation pour obtenir un générateur qui la satisfait le plus souvent ?

On veut tester un compilateur => comment générer un programme syntaxiquement valide?

8.3 property-testing et conception d'APIs

val split : sep:string -> string -> string list

split ~sep:"," "foo,bar" = ["foo"; "bar"]

Question : que renvoyer dans les cas tordus ?

split ~sep:"" "toto"
split ~sep:"," "toto" ["toto"]
split ~sep:"," ""    []  [""]
split ~sep:"," ","   [""; ""]
split ~sep:"," ",,"  [""; ""; ""]

join ~sep (split ~sep input) = input

Question: quelles propriétés pour ~split~?

Propriété proposée par la salle:

assume (not (String.contains ~sep input));
split ~sep input = [input]

Propriété supplémentaire (trop compliquée):

forall sep input1 input2.
  assume (sep <> "");
  split ~sep (input1 ^ input2) =
  merge_splits
    (split ~sep input1)
    (split ~sep input2)

sachant que

merge_splits (li1 @ [x]) ([y] @ li2) =
  li1 @ [x ^ y] @ li2

Propriétés de sérialisation:

val foo_of_json : JSON.t -> foo
val json_of_foo : foo -> JSON.t

 forall foo.
   equal_foo foo_of_json (json_of_foo foo) foo
 forall json.
   let json_carré = json_of_foo (foo_of_json json) in
   json_carré = json_of_foo (foo_of_json json_carré)

Author: Gabriel Scherer

Created: 2020-11-04 Wed 09:17

Validate