Cours 2 — Syntaxe et Types (OCaml)

Introduction

Rappel du cours 1 : fonctions (fun, let, let rec), récursion, tail recursion, récurseur sur ℕ, listes (::, []), recurse_list (fold_right), map, filter.

Ce cours : le mot-clé type, les types algébriques, le pattern matching exhaustif, l'AST, la compilation en bytecode.

« La programmation fonctionnelle, c'est comme la cuisine : si vous ne comprenez pas la différence entre une carotte et une carotte coupée en dés, vous allez avoir du mal à suivre la recette. Les types, c'est pareil. »

Les trois formes de fonctions (rappel)

fun x -> x * x — anonyme
let f x = x * x — nommée
let rec f n = ... f (n-1) — récursive

Exercice

Écrivez une fonction apply_twice f x qui applique f deux fois : apply_twice (fun x -> x * x) 2 = 16.

Fonctions : variations et curryfication

let add a b = a + b
let add = fun a b -> a + b
let add = fun a -> fun b -> a + b

Application partielle :

let add5 = add 5   (* val add5 : int -> int *)
(* add5 3 -> 8 *)

Pipe |> :

let ( |> ) x f = f x
let r = [1;2;3;4;5;6]
  |> List.filter (fun x -> x mod 2 = 0)
  |> List.map (fun x -> x * x)

Les types algébriques

Principe : on décrit les formes possibles d'une valeur.

Entiers de Peano :

type nat = Zero | Succ of nat

let trois = Succ (Succ (Succ Zero))

let rec to_int n = match n with
  | Zero -> 0
  | Succ n -> 1 + to_int n

Types sommes et produits

Type somme — OU logique (|) :

type couleur = Rouge | Vert | Bleu
type option = Rien | Chose of int

Type produit — ET logique :

type paire = int * string             (* anonyme *)
type point = { x : int; y : int }    (* record *)

Combinaison :

type forme = Cercle of float | Rect of float * float
type image = forme list

Les listes (version maison)

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

let rec map f l = match l with
  | Nil -> Nil
  | Cons (x, xs) -> Cons (f x, map f xs)

« Le mot Cons vient de construct, mais les étudiants disent Constantine parce que ça reste dans la tête. »

Les arbres binaires

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

let rec hauteur t = match t with
  | Leaf -> 0
  | Node (_, g, d) -> 1 + max (hauteur g) (hauteur d)

« Les arbres, c'est comme les listes, mais avec deux enfants. Quand vos parents ont un deuxième enfant, la récursion devient plus intéressante. »

AST — Votre programme devient une data structure

type expr =
  | Int of int
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

let rec eval e = match e with
  | Int n -> n
  | Add (a,b) -> eval a + eval b
  | Sub (a,b) -> eval a - eval b
  | Mul (a,b) -> eval a * eval b

Dérivation formelle

Les règles de dérivation sont des transformations d'AST :

let rec derive e = match e with
  | Int _ -> Int 0
  | Add (a,b) -> Add (derive a, derive b)
  | Mul (a,b) ->
    Add (Mul (derive a, b), Mul (a, derive b))

(a × b)' = a' × b + a × b' écrite en OCaml.

Bytecode et CPU virtuel

type instr = PUSH of int | ADD | SUB | MUL

let rec compile e = match e with
  | Int n -> [PUSH n]
  | Add (a,b) -> compile a @ compile b @ [ADD]
  | Sub (a,b) -> compile a @ compile b @ [SUB]
  | Mul (a,b) -> compile a @ compile b @ [MUL]

compile a @ compile b @ [ADD] = « calcule a, calcule b, additionne ».

Du type au processeur : Type → Pattern → Fonctions → Bytecode → CPU

📄 types_et_match.ml 📄 syntaxe_fun.ml 📄 syntaxe_let.ml 📄 syntaxe_letrec.ml 📄 bytecode.ml 📄 operateurs.ml 📄 calculatrice.ml 📖 Polycopié PDF 📽️ Slides PDF

Prochain cours

Cours 3 : les monades. On va généraliser le pattern bind/return qu'on a entrevu avec option.

🧩 Cours 2 — Syntaxe et Types