\appendix
\section{Annexe : autres monades avancées}

\subsection{Monade CPS (Continuation Passing Style)}

La monade CPS capture l'idée de « ce qu'on fait ensuite » — la
\textbf{continuation}. Chaque fonction reçoit un argument supplémentaire
qui représente la suite du calcul. Le type est :
\begin{lstlisting}
type ('a, 'r) cont = ('a -> 'r) -> 'r
\end{lstlisting}
Une valeur de type \texttt{('a,~'r)~cont} est une fonction qui, étant
donné une continuation \texttt{('a~->~'r)}, produit un résultat \texttt{'r}.

\subsubsection{Définition}

\begin{lstlisting}
let return x = fun k -> k x

let (>>=) m f = fun k -> m (fun x -> f x k)
\end{lstlisting}

\begin{blague}
  CPS, c'est comme un restaurant où au lieu de commander et d'attendre
  votre plat, vous donnez au chef un numéro de téléphone pour qu'il vous
  appelle quand c'est prêt. Et le chef enchaîne les plats comme des
  continuations. Le problème, c'est quand le téléphone sonne dans le
  four.
\end{blague}

\subsubsection{Exemple 1 : sortie anticipée (early return)}

On peut simuler un \texttt{return} style impératif : une continuation
qui court-circuite le reste du calcul.
\begin{lstlisting}
(* Calcul avec sortie anticipee *)
let cherche_dans_liste pred lst =
  let rec aux = function
    | [] -> None
    | x :: xs ->
      if pred x then Some x
      else aux xs
  in
  aux lst
\end{lstlisting}
Avec CPS, on peut faire mieux :
\begin{lstlisting}
(* Trouve le premier element pair et l'imprime *)
let premier_pair_cps lst =
  let ret = ref None in
  let k_finale x = !ret in
  let k_trouve x = ret := Some x; k_finale 42 in
  List.iter (fun x ->
    if x mod 2 = 0 then k_trouve x
  ) lst;
  !ret
\end{lstlisting}
Bon, ce n'est pas encore très monadique. Voici un exemple plus parlant :
la « coroutine » avec CPS.

\subsubsection{Exemple 2 : generateur (coroutine)}

Avec CPS, on peut suspendre et reprendre un calcul :
\begin{lstlisting}
type ('a, 'r) gen = ('a -> unit) -> ('a -> 'r) -> 'r

let yield x = fun return suspend -> suspend x

let rec range_gen n =
  if n <= 0 then fun return _ -> return ()
  else yield n >>= fun _ ->
       range_gen (n - 1)
\end{lstlisting}

\subsubsection{Exemple 3 : amb (choix non-déterministe avec CPS)}

L'opérateur \texttt{amb} (McCarthy) essaie toutes les valeurs possibles
via CPS. C'est une version controlée du non-déterminisme :
\begin{lstlisting}
(* amb : choisit une valeur parmi une liste *)
let amb lst = fun k_succ k_fail ->
  let rec essayer = function
    | [] -> k_fail ()
    | x :: xs -> k_succ x (fun () -> essayer xs)
  in
  essayer lst

(* Utilisation : trouver x,y,z dans [1..n] tels que x^2 + y^2 = z^2 *)
let triple_pythagoricien n =
  let range = List.init n (fun i -> i + 1) in
  amb range >>= fun x ->
  amb range >>= fun y ->
  amb range >>= fun z ->
  if x * x + y * y = z * z then return (x, y, z)
  else fail
\end{lstlisting}

\begin{blague}
  L'opérateur \texttt{amb} est le CCSD (Chef de la Choisissabilité
  Supervisée) du monde des monades : il explore toutes les
  possibilités et revient en arrière si ça foire. Comme quand vous
  essayez tous les snacks du distributeur avant d'admettre que vous
  voulez juste un Mars.
\end{blague}

\newpage
\subsection{Monade de Backpropagation (Différentiation Automatique)}

La monade de backpropagation permet de calculer automatiquement les
dérivées d'une fonction. On va présenter deux approches : la
différentiation automatique en mode \textbf{forward} (nombres duaux)
et en mode \textbf{reverse} (backpropagation).

\subsubsection{Nombres duaux (mode forward)}

Un nombre dual associe à une valeur $v$ sa dérivée $dv$ :
\begin{lstlisting}
type 'a dual = { v : 'a; d : 'a }
\end{lstlisting}

Les opérations arithmétiques propageant la dérivée via la règle de
chaîne :
\begin{lstlisting}
let add a b = { v = a.v + b.v; d = a.d + b.d }
let mul a b = { v = a.v * b.v; d = a.v * b.d + b.v * a.d }
let sin a   = { v = sin a.v;   d = cos a.v *. a.d }
\end{lstlisting}

On peut en faire une monade si on veut chaîner des calculs avec
dépendances :
\begin{lstlisting}
type 'a ad = { value : 'a; deriv : 'a; mutable tape : ('a ad * 'a ad) option }

let return x = { value = x; deriv = 0.0; tape = None }

let (>>=) m f =
  let r = f m.value in
  r.deriv <- m.deriv +. r.deriv;
  r
\end{lstlisting}
Cette présentation est simplifiée. L'implémentation réelle stocke un
graphe de calcul (Wengert list / tape).

\begin{blague}
  La différentiation automatique, c'est comme se rappeler tous les
  couloirs qu'on a empruntés dans un labyrinthe, mais à l'envers.
  Le mode forward, c'est votre GPS qui recalcule le chemin à chaque
  intersection. Le mode reverse, c'est le chauffeur Uber qui vous
  demande « par où on est passés déjà ? » à la fin du trajet.
\end{blague}

\subsubsection{Mode reverse (backpropagation) : une tape monadique}

Le mode reverse est plus efficace pour les fonctions avec beaucoup de
paramètres (réseaux de neurones). On enregistre toutes les opérations
sur une \textbf{tape}, puis on la parcourt à l'envers pour propager
les gradients.

\begin{lstlisting}
type tape =
  | Leaf of { mutable grad : float }
  | Add of node * node
  | Mul of node * node
  | Sin of node
  | Cos of node
and node = { value : float; tape : tape }

(* Construction du graphe *)
let add a b =
  let r = { value = a.value +. b.value;
            tape = Add (a, b) } in
  r

let mul a b =
  let r = { value = a.value *. b.value;
            tape = Mul (a, b) } in
  r

(* Backpropagation : derivee partielle *)
let rec grad_node n =
  match n.tape with
  | Leaf _ -> 1.0
  | Add (a, b) -> grad_node a +. grad_node b
  | Mul (a, b) ->
    grad_node a *. b.value +. a.value *. grad_node b
  | Sin a -> cos a.value *. grad_node a
  | Cos a -> -.sin a.value *. grad_node a
\end{lstlisting}

On peut encapsuler \texttt{node} dans une monade pour chaîner
naturellement :
\begin{lstlisting}
type 'a backprop = unit -> node

let return x () = { value = x; tape = Leaf { grad = 0.0 } }

let (>>=) m f () =
  let a = m () in
  (f a.value) ()
\end{lstlisting}

Exemple d'utilisation :
\begin{lstlisting}
let f x = sin (mul x x)         (* f(x) = sin(x^2) *)

let x = { value = 2.0; tape = Leaf { grad = 0.0 } }
let y = f x                     (* calcule sin(4) *)
let dy = grad_node y             (* derivee : cos(4) * 2*2 *)
\end{lstlisting}

\begin{blague}
  Avec la monade de backpropagation, vous pouvez dériver n'importe
  quelle fonction sans faire une seule ligne de calcul différentiel.
  C'est comme tricher à un examen de maths avec une calculatrice
  quantique. Vos profs de prépa vous détesteraient, mais vos réseaux
  de neurones vous adoreront.
\end{blague}

\newpage
\subsection{Mini interprète Prolog}

Le Prolog est un langage de programmation \textbf{logique} : on énonce
des faits et des règles, et le moteur cherche les solutions par
\textbf{unification} et \textbf{backtracking}. La monade Liste est
parfaite pour modéliser le backtracking !

\subsubsection{Terms et substitution}

\begin{lstlisting}
type term =
  | Var of string
  | Const of string
  | Fun of string * term list

type substitution = (string * term) list
\end{lstlisting}

\subsubsection{Unification}

L'unification trouve la substitution la plus générale qui rend deux
termes égaux :
\begin{lstlisting}
let rec unifie t1 t2 subst =
  match t1, t2 with
  | Var x, _ -> unifie_var x t2 subst
  | _, Var y -> unifie_var y t1 subst
  | Const a, Const b when a = b -> return subst
  | Fun (f, args1), Fun (g, args2) when f = g ->
    unifie_liste args1 args2 subst
  | _ -> fail
\end{lstlisting}

\subsubsection{Programme logique}

Un programme est une liste de clauses (faits ou règles) :
\begin{lstlisting}
type clause = { tete : term; corps : term list }

type programme = clause list
\end{lstlisting}

Le moteur d'inférence cherche à prouver un but en essayant toutes les
clauses :
\begin{lstlisting}
let rec prouve programme buts subst =
  match buts with
  | [] -> return subst
  | but :: reste ->
    programme >>= fun clause ->
    (* Renommer les variables de la clause *)
    let clause' = renomme clause in
    unifie but clause'.tete subst >>= fun subst' ->
    prouve programme (clause'.corps @ reste) subst'
\end{lstlisting}

\subsubsection{Exemple : généalogie}

\begin{lstlisting}
let prog = [
  (* parent(x,y) : x est parent de y *)
  fait "parent" ["jean"; "marie"];
  fait "parent" ["marie"; "paul"];
  fait "parent" ["paul"; "sophie"];
  (* grandparent(x,y) :- parent(x,z), parent(z,y) *)
  regle "grandparent" ["x"; "y"]
        [atome "parent" ["x"; "z"]; atome "parent" ["z"; "y"]];
  (* ancetre(x,y) :- parent(x,y) *)
  regle "ancetre" ["x"; "y"] [atome "parent" ["x"; "y"]];
  (* ancetre(x,y) :- parent(x,z), ancetre(z,y) *)
  regle "ancetre" ["x"; "y"]
        [atome "parent" ["x"; "z"]; atome "ancetre" ["z"; "y"]];
]

(* Requete : ancetre(jean, X) ? *)
(* Resultat : X = marie, X = paul, X = sophie *)
\end{lstlisting}

Quand on lance la requête \texttt{ancetre(jean, X)}, le moteur :
\begin{enumerate}
  \item Essaie la première règle \texttt{grandparent} : échec (les noms
    ne correspondent pas).
  \item Essaie la règle \texttt{ancetre} avec \texttt{parent(jean,z)} :
    trouve \texttt{z=marie}.
  \item Puis \texttt{ancetre(marie, X)} : récursivement, trouve
    \texttt{X=paul}, puis \texttt{X=sophie}.
  \item La monade Liste collecte toutes les solutions.
\end{enumerate}

\begin{blague}
  Prolog, c'est comme un détective privé qui explore toutes les pistes
  en même temps. La monade Liste, c'est son tableau d'enquête avec
  des fiches de toutes les couleurs. Le backtracking, c'est quand il
  réalise que le majordome avait un alibi et qu'il défait tout le
  fil rouge pour suivre la piste du jardinier.
\end{blague}

\subsubsection{Code complet du mini Prolog}

Voici le squelette complet (env. 60 lignes) :
\begin{lstlisting}
type term = Var of string | Const of string | Fun of string * term list
type substitution = (string * term) list
type clause = { tete : term; corps : term list }
type programme = clause list

(* Variables fraiches *)
let compteur = ref 0
let fraiche _ = compteur := !compteur + 1; Var ("_" ^ string_of_int !compteur)

let renomme clause =
  let rec aux = function
    | Var x -> fraiche ()
    | Const _ as t -> t
    | Fun (f, args) -> Fun (f, List.map aux args)
  in
  { tete = aux clause.tete; corps = List.map aux clause.corps }

(* Unification *)
let rec unifie t1 t2 subst = match t1, t2 with
  | Var x, _ -> (try unifie (List.assoc x subst) t2 subst
                 with Not_found -> return ((x, t2) :: subst))
  | _, Var y -> unifie t2 t1 subst
  | Const a, Const b when a = b -> return subst
  | Fun (f, a1), Fun (g, a2) when f = g ->
    (try List.fold_left2 (fun s t1 t2 ->
       s >>= fun s' -> unifie t1 t2 s') (return subst) a1 a2
     with Invalid_argument _ -> fail)
  | _ -> fail

and fail = fun _ -> []

(* Moteur d'inference *)
let rec prouve prog buts subst = match buts with
  | [] -> return subst
  | but :: reste ->
    prog >>= fun clause ->
    let clause' = renomme clause in
    unifie but clause'.tete subst >>= fun subst' ->
    prouve prog (clause'.corps @ reste) subst'

(* Fonctions auxiliaires *)
let const n = Const n
let var n = Var n
let atome nom args = Fun (nom, List.map (fun n -> Const n) args)
let fait nom args = { tete = atome nom args; corps = [] }
let regle nom args corps = { tete = atome nom args; corps }
\end{lstlisting}

\begin{blague}
  Vous venez d'écrire Prolog en 60 lignes d'OCaml. C'est environ 60
  fois moins de lignes que le manuel d'utilisation de SWI-Prolog. Et
  ça compile du premier coup (enfin, après quelques tentatives).
\end{blague}

\subsection{Aller plus loin}

Les monades présentées ici ne sont que la partie émergée de l'iceberg.
Il en existe des dizaines d'autres :
\begin{itemize}
  \item \textbf{State monad} : threader un état à travers des calculs
    (compteur, générateur d'ID, etc.).
  \item \textbf{IO monad} : gérer les entrées-sorties de manière pure
    (utilisée en Haskell).
  \item \textbf{Writer monad} : accumuler des logs ou des traces.
  \item \textbf{Reader monad} : partager un environnement de
    configuration.
  \item \textbf{Free monad} : construire des DSL (Domain Specific
    Languages) de manière modulaire.
  \item \textbf{Probability monad} : modéliser des distributions de
    probabilités (Monte Carlo, inférence bayésienne).
\end{itemize}

\begin{blague}
  On dit qu'un développeur fonctionnel qui maîtrise les monades peut
  expliquer le changement de couche à un bébé. On dit aussi qu'il peut
  être dangereusement productif et faire en une après-midi ce qu'une
  équipe de 10 développeurs Java fait en une semaine. Mais ça, c'est
  peut-être une légende urbaine.
\end{blague}

\vfill
\hrule
\vspace{2mm}
\small
Cette annexe complète le \texttt{cours\_monade.pdf}. Pour aller plus
loin : le livre \textit{Real World OCaml}, la série d'articles
\textit{You Could Have Invented Monads!} (et \textit{And Then You've
  Actually Invented Them}), et le site \texttt{https://learn-ocaml.org/}.