Module L07 · Partie F · Coder comme un professionnel

C et OCaml : les deux langages de la prépa.

En MP2I/MPI, on programme en C (pour comprendre la mémoire, les pointeurs, ce que fait vraiment la machine) et en OCaml (pour la programmation fonctionnelle, les types, la récursion structurelle et les preuves). Vous connaissez déjà le C par Arduino ; ce module va plus loin et introduit OCaml. Le C et OCaml ne tournent pas dans la page : les exemples sont à compiler sur votre PC, et Python sert de miroir pour comparer.

Durée : 4 séances · Prérequis : séances 22-23 (Arduino), L03. Objectifs : compilation, types et mémoire en C, pointeurs, tableaux, chaînes, structures, allocation dynamique, listes chaînées en C ; OCaml : expressions, types, filtrage, listes, récursion, types algébriques, modules. Un même algorithme écrit dans les trois langages.

Fiche de cours · Définitions

C et OCaml : les notions à définir sans hésiter

Fiche de cours · Formules

Tables à connaître

Fiche de cours · Théorèmes et démonstrations

Démonstrations à savoir refaire

Fiche de cours · Méthodes

Méthodes et pièges

Pièges C : = au lieu de == ; sizeof(t) sur un paramètre (c’est un pointeur : 8) ; renvoyer l’adresse d’une variable locale ; char *s = "abc"; s[0] = 'x' (littéral en lecture seule) ; for (unsigned i = n − 1; i >= 0; …) boucle infinie. Pièges OCaml : = (structurel) vs == (physique) ; + pour int et +. pour float ; oublier rec ; l @ [x] en boucle (O(n²)).

Fiche de cours · Exercices corrigés

Exercices corrigés

int *cree_tableau(int n) { int t[n]; for (int i = 0; i < n; i++) t[i] = i; return t; }

01 / C : compiler

Du texte au binaire

/* bonjour.c */
#include <stdio.h>

int main(void) {
    int n = 5;
    double moyenne = 17.0 / 3;
    printf("n = %d, moyenne = %.2f\n", n, moyenne);
    for (int i = 0; i < n; i++) {
        printf("%d² = %d\n", i, i * i);
    }
    return 0;      /* 0 = tout s'est bien passé */
}

$ gcc -Wall -Wextra -O2 -o bonjour bonjour.c
$ ./bonjour
n = 5, moyenne = 5.67
0² = 0
...

01 / C : compiler

Types, tailles, débordements : ce que Python vous cache

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

int main(void) {
    printf("char %zu, int %zu, long %zu, double %zu octets\n",
           sizeof(char), sizeof(int), sizeof(long), sizeof(double));
    int x = INT_MAX;
    x = x + 1;                 /* débordement : comportement indéfini ! */
    printf("INT_MAX + 1 = %d\n", x);      /* souvent -2147483648 */
    uint8_t octet = 250;
    octet += 10;               /* non signé : modulo 256, bien défini */
    printf("250 + 10 sur 8 bits = %u\n", octet);   /* 4 */
    printf("7 / 2 = %d, -7 / 2 = %d, -7 %% 2 = %d\n", 7 / 2, -7 / 2, -7 % 2);
    printf("0.1 + 0.2 == 0.3 ? %d\n", 0.1 + 0.2 == 0.3);
    return 0;
}

02 / C : mémoire

Pointeurs : une variable qui contient une adresse

#include <stdio.h>

void echanger(int *a, int *b) {   /* reçoit des ADRESSES */
    int t = *a;                    /* *a : la valeur à l'adresse a */
    *a = *b;
    *b = t;
}

int main(void) {
    int x = 3, y = 7;
    int *p = &x;                   /* &x : l'adresse de x */
    printf("x = %d, p = %p, *p = %d\n", x, (void *)p, *p);
    *p = 10;                       /* modifie x à travers p */
    printf("x = %d\n", x);
    echanger(&x, &y);
    printf("x = %d, y = %d\n", x, y);

    int t[5] = {10, 20, 30, 40, 50};
    int *q = t;                    /* un tableau « est » l'adresse de son premier élément */
    printf("%d %d %d\n", t[2], *(q + 2), q[2]);   /* trois écritures identiques */
    return 0;
}

02 / C : mémoire

Pile et tas : où vivent les variables

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int *creer_tableau(int n) {
    int *t = malloc(n * sizeof(int));      /* sur le TAS : survit à la fonction */
    if (t == NULL) { perror("malloc"); exit(1); }
    for (int i = 0; i < n; i++) t[i] = i * i;
    return t;
}

int *creer_tableau_faux(int n) {
    int t[100];                             /* sur la PILE : détruit au return ! */
    for (int i = 0; i < n; i++) t[i] = i * i;
    return t;                               /* pointeur pendouillant : bug */
}

int main(void) {
    int *carres = creer_tableau(10);
    printf("%d\n", carres[7]);
    carres = realloc(carres, 20 * sizeof(int));   /* agrandir (comme la list Python) */
    free(carres);                                   /* obligatoire, sinon fuite */
    /* carres[0] = 1;  ← utilisation après libération : bug */

    char nom[32];
    strncpy(nom, "robot explorateur", sizeof nom - 1); nom[sizeof nom - 1] = '\0';
    printf("%s (%zu caractères)\n", nom, strlen(nom));   /* chaîne = tableau de char terminé par 0 */
    return 0;
}

02 / C : mémoire

Structures et liste chaînée en C

#include <stdio.h>
#include <stdlib.h>

typedef struct Maillon {
    double valeur;
    struct Maillon *suivant;
} Maillon;

Maillon *inserer_tete(Maillon *tete, double v) {
    Maillon *m = malloc(sizeof *m);
    m->valeur = v;          /* m->x  ≡  (*m).x */
    m->suivant = tete;
    return m;
}

double somme(const Maillon *m) {
    double s = 0;
    for (; m != NULL; m = m->suivant) s += m->valeur;
    return s;
}

void liberer(Maillon *m) {
    while (m) { Maillon *s = m->suivant; free(m); m = s; }
}

int main(void) {
    Maillon *l = NULL;
    for (int i = 1; i <= 5; i++) l = inserer_tete(l, i * 1.5);
    printf("somme = %.1f\n", somme(l));
    liberer(l);
    return 0;
}

02 / C : mémoire

Le C au niveau du matériel : bits, registres, volatile

#include <stdint.h>

/* Registre matériel : une adresse fixe où lire/écrire change l'état d'une broche (exemple STM32) */
#define GPIOA_ODR (*(volatile uint32_t *)0x40020014)

void allumer_led(void)  { GPIOA_ODR |=  (1u << 5); }   /* mettre le bit 5 à 1 */
void eteindre_led(void) { GPIOA_ODR &= ~(1u << 5); }   /* le mettre à 0 */
void basculer_led(void) { GPIOA_ODR ^=  (1u << 5); }   /* l'inverser */
int  led_allumee(void)  { return (GPIOA_ODR >> 5) & 1; }

/* Compacter des drapeaux : un octet = 8 booléens */
typedef enum { OBSTACLE = 1 << 0, BATTERIE_FAIBLE = 1 << 1, EN_MOUVEMENT = 1 << 2 } Etat;
uint8_t etat = OBSTACLE | EN_MOUVEMENT;
int bloque = (etat & OBSTACLE) && (etat & EN_MOUVEMENT);

/* Interruption : appelée par le matériel, pas par votre programme */
volatile uint32_t ticks = 0;             /* volatile : « peut changer sans que le code le fasse » */
void SysTick_Handler(void) { ticks++; }  /* toutes les millisecondes */
uint32_t millis(void) { return ticks; }

volatile interdit au compilateur de mettre la variable en cache dans un registre : sans lui, while (ticks < 100); pourrait être optimisé en boucle infinie. Ce mot-clé n’existe pas en Python parce que Python n’a pas d’optimiseur qui raisonne ainsi. Module L18 pour la suite.

03 / OCaml

OCaml : tout est expression, tout est typé

(* Dans l'interpréteur : ocaml, ou utop *)
let x = 3 + 4 ;;                    (* val x : int = 7 *)
let pi = 3.14159 ;;                 (* val pi : float *)
let aire r = pi *. r *. r ;;        (* val aire : float -> float ; *. pour les flottants *)
aire 2.0 ;;                         (* - : float = 12.56636 *)

let rec factorielle n =
  if n = 0 then 1 else n * factorielle (n - 1) ;;
(* val factorielle : int -> int *)

let max a b = if a > b then a else b ;;    (* val max : 'a -> 'a -> 'a : polymorphe ! *)
max 3 5 ;;  max "a" "b" ;;  max 2.5 1.0 ;;

(* Les fonctions sont des valeurs *)
let appliquer_deux_fois f x = f (f x) ;;   (* ('a -> 'a) -> 'a -> 'a *)
appliquer_deux_fois (fun n -> n * 3) 2 ;;  (* 18 *)
let carre = fun x -> x * x in appliquer_deux_fois carre 3 ;;  (* 81 *)

03 / OCaml

Listes et filtrage de motifs : la récursion structurelle

let l = [3; 1; 4; 1; 5] ;;          (* int list ; [] liste vide ; x :: reste *)

let rec longueur = function
  | [] -> 0
  | _ :: reste -> 1 + longueur reste ;;

let rec somme = function
  | [] -> 0
  | x :: reste -> x + somme reste ;;

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

let rec filtre p = function
  | [] -> []
  | x :: reste -> if p x then x :: filtre p reste else filtre p reste ;;

(* Récursion terminale : l'accumulateur évite de faire grossir la pile *)
let somme_term l =
  let rec aux acc = function
    | [] -> acc
    | x :: reste -> aux (acc + x) reste
  in aux 0 l ;;

(* Tri par insertion *)
let rec insere x = function
  | [] -> [x]
  | y :: reste when x <= y -> x :: y :: reste
  | y :: reste -> y :: insere x reste ;;
let rec tri = function
  | [] -> []
  | x :: reste -> insere x (tri reste) ;;
tri l ;;                             (* [1; 1; 3; 4; 5] *)
List.map (fun x -> x * x) l ;;       (* la bibliothèque standard *)

03 / OCaml

Types algébriques : décrire exactement les données

(* Type somme : une valeur est l'un des cas *)
type forme =
  | Cercle of float
  | Rectangle of float * float
  | Triangle of float * float * float ;;

let aire = function
  | Cercle r -> 3.14159 *. r *. r
  | Rectangle (l, h) -> l *. h
  | Triangle (a, b, c) ->
      let s = (a +. b +. c) /. 2. in
      sqrt (s *. (s -. a) *. (s -. b) *. (s -. c)) ;;

(* Option : la valeur peut manquer, et le type vous FORCE à traiter ce cas *)
let rec cherche cle = function
  | [] -> None
  | (k, v) :: reste -> if k = cle then Some v else cherche cle reste ;;
match cherche "b" [("a", 1); ("b", 2)] with
  | Some v -> Printf.printf "trouvé %d\n" v
  | None -> print_endline "absent" ;;

(* Arbre binaire : type récursif *)
type 'a arbre = Feuille | Noeud of 'a arbre * 'a * 'a arbre ;;
let rec inserer x = function
  | Feuille -> Noeud (Feuille, x, Feuille)
  | Noeud (g, v, d) as n ->
      if x < v then Noeud (inserer x g, v, d)
      else if x > v then Noeud (g, v, inserer x d) else n ;;
let rec infixe = function
  | Feuille -> []
  | Noeud (g, v, d) -> infixe g @ [v] @ infixe d ;;
infixe (List.fold_left (fun a x -> inserer x a) Feuille [5; 2; 8; 1; 9]) ;;
(* [1; 2; 5; 8; 9] *)

03 / OCaml

Références, tableaux et modules : OCaml n’est pas que fonctionnel

(* Mutabilité explicite quand elle est utile *)
let compteur = ref 0 ;;
incr compteur ; compteur := !compteur + 10 ;;   (* !r : lire ; r := v : écrire *)

let tri_insertion t =                (* tableau mutable, boucles impératives *)
  for i = 1 to Array.length t - 1 do
    let x = t.(i) in
    let j = ref (i - 1) in
    while !j >= 0 && t.(!j) > x do
      t.(!j + 1) <- t.(!j); decr j
    done;
    t.(!j + 1) <- x
  done ;;
let t = [| 5; 2; 9; 1 |] in tri_insertion t; t ;;   (* [|1; 2; 5; 9|] *)

(* Modules : regrouper types et fonctions derrière une signature *)
module Pile : sig
  type 'a t
  val vide : 'a t
  val empiler : 'a -> 'a t -> 'a t
  val depiler : 'a t -> ('a * 'a t) option
end = struct
  type 'a t = 'a list
  let vide = []
  let empiler x p = x :: p
  let depiler = function [] -> None | x :: r -> Some (x, r)
end ;;
(* L'utilisateur du module ne peut PAS savoir que c'est une liste : encapsulation garantie par le typeur *)
Hashtbl.create 16 ;;  Queue.create () ;;  (* la bibliothèque standard : tables de hachage, files, tas via Set/Map *)

Le programme MPI utilise les tableaux, les références et les boucles autant que la récursion : l’idée est de choisir le style adapté, en gardant la mutabilité visible dans les types (ref, array). Compiler : ocamlfind ocamlopt -package str -o prog prog.ml, ou simplement dune build dans un projet.

04 / Comparer

Un algorithme, trois langages : la dichotomie

/* C */
int dichotomie(const int *t, int n, int x) {
    int bas = 0, haut = n;           /* invariant : x ∈ t[bas..haut[ si présent */
    while (bas < haut) {
        int m = bas + (haut - bas) / 2;   /* pas (bas+haut)/2 : débordement possible ! */
        if (t[m] < x) bas = m + 1;
        else if (t[m] > x) haut = m;
        else return m;
    }
    return -1;
}

(* OCaml *)
let dichotomie t x =
  let rec aux bas haut =
    if bas >= haut then None
    else
      let m = bas + (haut - bas) / 2 in
      if t.(m) < x then aux (m + 1) haut
      else if t.(m) > x then aux bas m
      else Some m
  in aux 0 (Array.length t)

Cours

Cours 1 — Le modèle mémoire du C : ce qu’il faut avoir en tête à chaque ligne

Déclarations, à lire de l’intérieur vers l’extérieur. int *p : p est un pointeur vers int. int t[10] : tableau de 10 int. int *t[10] : tableau de 10 pointeurs vers int. int (*p)[10] : pointeur vers un tableau de 10 int. const int *p : pointeur vers un int constant (on ne modifie pas *p) ; int *const p : pointeur constant (on ne modifie pas p). char **argv : pointeur vers pointeur vers char — le tableau des arguments de la ligne de commande.

Arithmétique des pointeurs. p + 1 avance de sizeof(*p) octets, pas de 1 : c’est ce qui rend t[i] ≡ *(t + i) correct pour tout type. p2 − p1 donne un nombre d’éléments. Comparer deux pointeurs n’a de sens que dans le même tableau.

Cours

Cours 2 — Le cycle de vie d’un programme C : préprocesseur, compilation, édition de liens, exécution

$ gcc -E prog.c -o prog.i      # 1. préprocesseur : #include collés, #define substitués, #ifdef résolus
$ gcc -S prog.i -o prog.s      # 2. compilation : C → assembleur (lisez-le : c'est instructif)
$ gcc -c prog.s -o prog.o      # 3. assemblage : → code machine relogeable (fichier objet)
$ gcc prog.o util.o -lm -o prog   # 4. édition de liens : objets + bibliothèques (libm : math) → exécutable
$ ./prog ; echo $?             # 5. exécution ; code de retour de main

Un projet à plusieurs fichiers. Chaque .c est compilé séparément ; les .h déclarent ce que les autres fichiers peuvent utiliser (prototypes, struct, #define) avec une garde #ifndef CAPTEUR_H / #define CAPTEUR_H / … / #endif. make ne recompile que ce qui a changé :

# Makefile
CC = gcc
CFLAGS = -Wall -Wextra -O2 -g -std=c17
OBJ = main.o capteur.o filtre.o
robot: $(OBJ)
	$(CC) $(CFLAGS) -o $@ $(OBJ) -lm
%.o: %.c capteur.h filtre.h
	$(CC) $(CFLAGS) -c $<
clean:
	rm -f $(OBJ) robot
# (les retraits sont des TABULATIONS, pas des espaces)

Cours

Cours 3 — OCaml : évaluation, types, récursion — ce que le typeur vérifie pour vous

(* Exemple travaillé : une pile persistante et son type abstrait, avec la signature qui cache la représentation *)
module type PILE = sig
  type 'a t
  val vide : 'a t
  val empiler : 'a -> 'a t -> 'a t
  val depiler : 'a t -> ('a * 'a t) option
  val taille : 'a t -> int
end
module Pile : PILE = struct
  type 'a t = 'a list
  let vide = []
  let empiler x p = x :: p
  let depiler = function [] -> None | x :: r -> Some (x, r)
  let taille = List.length
end
let () =
  let p = Pile.(vide |> empiler 1 |> empiler 2) in     (* |> : application inversée, lisible de gauche à droite *)
  match Pile.depiler p with
  | Some (x, _) -> Printf.printf "sommet %d, taille %d\n" x (Pile.taille p)
  | None -> print_endline "vide"

TP guidé

TP 1 — Compiler, déboguer, mesurer en C (sur PC, 2 h)

• Installer. Linux : sudo apt install build-essential gdb valgrind. macOS : xcode-select --install (valgrind indisponible : utiliser -fsanitize=address). Windows : WSL2 + Ubuntu (recommandé), ou MSYS2. Vérifier : gcc --version.
• Premier programme et premier avertissement. stats.c : lit des entiers sur l’entrée standard (scanf("%d", &x) == 1) dans un tableau dynamique (doublement de capacité), affiche min, max, moyenne. Compilez avec gcc -Wall -Wextra -O2 -g -o stats stats.c ; corrigez jusqu’à zéro avertissement. Test : seq 1 100 | ./stats → moyenne 50.5.
• Provoquer et diagnostiquer trois bugs. (a) Retirez le free : valgrind --leak-check=full ./stats < nombres.txt → « definitely lost ». (b) Lisez t[n] au lieu de t[n−1] : valgrind « Invalid read of size 4 » avec la ligne exacte. (c) Déréférencez NULL : gdb ./stats, run < nombres.txt, bt (pile d’appels), print p, frame 1, list. Notez pour chaque bug : symptôme, outil, message, ligne.
• Liste chaînée en C. liste.h / liste.c (types, inserer_tete, longueur, inverser, liberer) + test_liste.c avec des assert (<assert.h>) + Makefile. make && ./test_liste && valgrind ./test_liste : « All heap blocks were freed ».
• Mesurer C vs Python. Crible d’Ératosthène jusqu’à 10⁸ en C (tableau d’octets, calloc) et en Python (bytearray) : time ./crible vs time python crible.py. Puis -O0 vs -O2 vs -O3 -march=native. Remplissez un tableau des temps.
• Lire l’assembleur. gcc -O2 -S -fverbose-asm boucle.c sur une boucle qui somme un tableau : repérez la boucle, l’instruction d’addition, et avec -O3 les instructions vectorielles (paddd, vpaddd). Vous venez de voir ce que « optimisation » veut dire.
• Livrable. Dépôt avec Makefile, tests, RESULTATS.md (tableau des bugs diagnostiqués, temps C/Python/-O).

TP guidé

TP 2 — OCaml : de l’interpréteur au projet compilé (sur PC, 2 h)

• Installer.

  bash -c "sh <(curl -fsSL https://opam.ocaml.org/install.sh)"    # opam, le gestionnaire de paquets
  opam init -y && eval $(opam env)
  opam install -y utop dune ocaml-lsp-server ounit2
  ocaml -version && utop -version

  Windows : via WSL2. Éditeur : VS Code + extension « OCaml Platform ».
• Interpréteur. Lancez utop ; tapez les exemples du cours 3 ; observez le type inféré de chaque définition ; provoquez trois erreurs de type (1 + 2.0, "a" ^ 1, un match non exhaustif) et lisez les messages : ils indiquent toujours ce qui était attendu et ce qui a été trouvé.
• Projet dune.

  dune init project robotml && cd robotml
  # bin/main.ml, lib/robotml.ml, test/test_robotml.ml ; dune-project à la racine
  dune build 2>&1 | head        # zéro erreur attendue
  dune exec robotml
  dune test

• Bibliothèque. Dans lib/ : un module Listes (longueur, map, filter, fold, inverser terminale, tri par insertion, tri fusion — sans utiliser List.) ; un module Arbre (ABR polymorphe : insérer, contient, infixe, hauteur) ; un module Expr (type algébrique, eval, dérivée, affichage). Chaque fonction : sa signature dans un .mli (dune le lit ; c’est le contrat).
• Tests. Avec OUnit2 : au moins 15 cas, dont la comparaison de votre tri à List.sort sur 100 listes aléatoires (Random.int). dune test doit être vert.
• Performance et récursion terminale. longueur naïve sur une liste de 10⁶ éléments : Stack_overflow ? Réécrivez-la avec accumulateur : plus de débordement. Mesurez avec Sys.time () le tri fusion sur 10⁶ entiers en OCaml natif (dune build --profile release) et comparez à Python sorted et à votre tri fusion Python.
• Livrable. Le projet dune (build et tests verts), les .mli commentés, RESULTATS.md avec les temps et les trois messages d’erreur de type expliqués.

Exercices

Exercices auto-corrigés — prédire ce que fait le C (simulé en Python)

Exercices

Exercices auto-corrigés — penser en OCaml (prototypé en Python, puis à écrire en OCaml)

def somme(l): return 0 if not l else l[0] + somme(l[1:])
def map(f, l): return [] if not l else [f(l[0])] + map(f, l[1:])
def filtre(p, l): return [] if not l else ([l[0]] if p(l[0]) else []) + filtre(p, l[1:])
def replier_gauche(f, acc, l): return acc if not l else replier_gauche(f, f(acc, l[0]), l[1:])
def aplatir(ll): return [] if not ll else ll[0] + aplatir(ll[1:])
def compresser(l):
    if not l: return []
    r = compresser(l[1:])
    return [(l[0], r[0][1] + 1)] + r[1:] if r and r[0][0] == l[0] else [(l[0], 1)] + r

(* OCaml *)
let rec somme = function [] -> 0 | x :: r -> x + somme r                    (* int list -> int *)
let rec map f = function [] -> [] | x :: r -> f x :: map f r                 (* ('a -> 'b) -> 'a list -> 'b list *)
let rec filtre p = function [] -> [] | x :: r -> if p x then x :: filtre p r else filtre p r
let rec fold_left f acc = function [] -> acc | x :: r -> fold_left f (f acc x) r   (* ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a *)
let rec aplatir = function [] -> [] | l :: r -> l @ aplatir r
let rec compresser = function
  | [] -> []
  | x :: r -> (match compresser r with (y, n) :: q when y = x -> (x, n + 1) :: q | q -> (x, 1) :: q)

05 / Défis

Défi ★ — Trois versions

int pgcd(int a, int b) { while (b) { int r = a % b; a = b; b = r; } return a; }

void inverser(char *s) {
    for (size_t i = 0, j = strlen(s) - 1; i < j; i++, j--) { char t = s[i]; s[i] = s[j]; s[j] = t; }
}

int est_premier(long n) {
    if (n < 2) return 0;
    if (n % 2 == 0) return n == 2;
    for (long d = 3; d * d <= n; d += 2) if (n % d == 0) return 0;
    return 1;
}

05 / Défis

Défi ★★ — Un tableau dynamique en C

typedef struct { int *donnees; size_t taille, capacite; } Vecteur;

Vecteur vec_creer(void) { return (Vecteur){ NULL, 0, 0 }; }

void vec_ajouter(Vecteur *v, int x) {
    if (v->taille == v->capacite) {
        size_t nc = v->capacite ? 2 * v->capacite : 8;
        int *nd = realloc(v->donnees, nc * sizeof *nd);
        if (!nd) { perror("realloc"); exit(1); }
        v->donnees = nd; v->capacite = nc;
    }
    v->donnees[v->taille++] = x;
}

int vec_obtenir(const Vecteur *v, size_t i) {
    if (i >= v->taille) { fprintf(stderr, "indice %zu hors limites\n", i); exit(1); }
    return v->donnees[i];
}

void vec_liberer(Vecteur *v) { free(v->donnees); *v = vec_creer(); }

05 / Défis

Défi ★★★ — Esprit prépa : un évaluateur d’expressions en OCaml

type expr = Const of float | Var of string | Add of expr * expr | Mul of expr * expr | Neg of expr

let rec eval env = function
  | Const c -> c
  | Var x -> List.assoc x env
  | Add (a, b) -> eval env a +. eval env b
  | Mul (a, b) -> eval env a *. eval env b
  | Neg a -> -. (eval env a)

let rec derive x = function
  | Const _ -> Const 0.
  | Var y -> Const (if x = y then 1. else 0.)
  | Add (a, b) -> Add (derive x a, derive x b)
  | Mul (a, b) -> Add (Mul (derive x a, b), Mul (a, derive x b))
  | Neg a -> Neg (derive x a)

(* Analyseur : les jetons sont une liste de chaînes ; chaque fonction rend (expr, reste) *)
let rec parse_expr toks =
  let t, r = parse_terme toks in boucle_add t r
and boucle_add acc = function
  | "+" :: r -> let t, r' = parse_terme r in boucle_add (Add (acc, t)) r'
  | r -> acc, r
and parse_terme toks =
  let f, r = parse_facteur toks in boucle_mul f r
and boucle_mul acc = function
  | "*" :: r -> let f, r' = parse_facteur r in boucle_mul (Mul (acc, f)) r'
  | r -> acc, r
and parse_facteur = function
  | "(" :: r -> let e, r' = parse_expr r in (match r' with ")" :: r'' -> e, r'' | _ -> failwith ") attendu")
  | "-" :: r -> let f, r' = parse_facteur r in Neg f, r'
  | tok :: r -> (match float_of_string_opt tok with Some c -> Const c, r | None -> Var tok, r)
  | [] -> failwith "expression incomplète"

Référence

Les mots à retenir

Pour continuer

Vous parlez trois langages

Module suivant : les bases de données et le web — SQL exécuté dans la page, modèle relationnel, HTTP, une API pour votre robot.

À faire chez soi

• Installer gcc (Linux : sudo apt install build-essential valgrind ; Windows : WSL ou MSYS2 ; macOS : Xcode CLT) et OCaml (opam, puis opam install utop dune).
• Faire les problèmes 1-4 de CS50 en C.
• Lire les chapitres 1-4 d’OCaml from the very beginning et réécrire tous les exercices de listes du module L03 en OCaml.
• Lire le programme officiel MP2I d’informatique : repérer ce que vous savez déjà faire.

← L06SommaireL08 : Bases de données et web →