\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage[left=1cm,right=1cm,top=1cm,bottom=1.5cm]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows}
\tikzset{
c/.style={draw,circle,minimum width=8mm,ball color=white},
d/.style={->,>=stealth',very thick},
g/.style={-o, very thick}
}

\author{Alain Busser}
\title{Combinateurs en flow programming}
\begin{document}
\renewcommand{\labelitemi}{\tikz{\node[circle, ball color=black!15] at (0,0) {};}}
\maketitle
\section{Introduction}
Dans le $\lambda$-calcul, il n'y a que des fonctions. Un combinateur est une fonction spéciale qui combine des fonctions.


\subsection{I}
Le plus simple des combinateurs est celui qui ne fait rien~: on lui envoie une fonction et il renvoie la même fonction~:

\begin{center}
\begin{tikzpicture}
\node (a) at (0,2) {$f$};
\node (b) at (0,0) {$f$};
\draw[d] (a) to (b);
\end{tikzpicture}
\end{center}

Les autres combinateurs que l'on verra combinent plusieurs (en général, 2) fonctions.

\subsection{K et 0}

Les plus simples des combinateurs qui combinent deux fonctions sont ceux qui en oublient une des deux et transmettent l'autre telle quelle. Il y en a donc 2.

\subsubsection{K}

K (qui est la valeur logique \textit{true}) est le combinateur qui oublie la fonction $g$~:

\begin{center}
\begin{tikzpicture}
\node (f) at (0,2) {$f$};
\node (g) at (1,2) {$g$};
\node (c) at (0.5,0) {$f$};
\draw[d] (f) to (c);
%\draw[d] (g) to (1,1);
\end{tikzpicture}
\end{center}
 
K est la première lettre du mot $\mathfrak{Konstant}$ parce que si on considère $g$ comme une variable, la valeur $f$ renvoyée par le combinateur est indépendante de cette variable (donc constante).

\subsubsection{0}

Le combinateur 0 (qui correspond à la valeur logique \textit{false}) oublie par contre la première fonction $f$~:

\begin{center}
\begin{tikzpicture}
\node (f) at (0,2) {$f$};
\node (g) at (1,2) {$g$};
\node (c) at (0.5,0) {$f$};
\draw[d] (g) to (c);
%\draw[d] (g) to (1,1);
\end{tikzpicture}
\end{center}
 
Le combinateur est noté 0 parce que dans les numéraux de Church (voir plus bas) il représente le nombre 0.

\section{Application et composition}

\subsection{Le combinateur $\lambda$}

Le combinateur le plus important pour la suite (parce qu'il permet de construire les autres combinateurs) est l'application~: on lui donne deux fonctions $f$ et $g$ et il applique $f$ à $g$ pour renvoyer $f(g)$~:

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (c) at (0,0) {$\lambda$};
\node (d) at (0,-2) {$f(g)$};
\draw[d] (g) to (c);
\draw[g] (f) to (c);
\draw[d] (c) to (d);
\end{tikzpicture}
\end{center}

Dans la suite, on notera par une flèche \tikz{\draw[g] (0,0) to (1,0);} la fonction que l'on applique et par une flèche \tikz{\draw[d] (0,0) to (1,0);} la fonction à qui on applique une autre fonction.

Dans les numéraux de Church, le combinateur $\lambda$ représente

\begin{itemize}
\item Le nombre 1,
\item l'exponentiation.
\end{itemize}

D'où le choix de la lettre grecque $\lambda$ pour le nommer~: cette lettre ressemble à la fois au chapeau utilisé par certaines calculatrices pour désigner l'exponentiation, et au chiffre 1.

\subsection{Composition}

Il ne faut pas confondre l'application de $f$ à $g$ vue ci-dessus, avec la composée de $f$ et $g$ qui est $f\circ g$~: celle-ci est la fonction qui, à $h$, associe $f(g(h))$~:

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node (h) at (3,2) {$h$};
\node[c] (c) at (1,-2) {$\lambda$};
\node[c] (d) at (2,0) {$\lambda$};
\node (x) at (1,-4) {$f(g(h))$};
\draw[d] (h) to (d);
\draw[g] (g) to (d);
\draw[d] (d) to (c);
\draw[g] (f) to (c);
\draw[d] (c) to (x);
\end{tikzpicture}
\end{center}

\subsection{Le combinateur M}

Le combinateur M que Smullyan appelle «~mockingbird~» s'obtient facilement à l'aide du combinateur d'application~:

\begin{center}
\begin{tikzpicture}
\node (f) at (0,3) {$f$};
\node[c] (c) at (0,0) {$\lambda$};
\node (d) at (0,-2) {$f(f)$};
\draw[d] (f) -- (0,2) to [bend left] (c);
\draw[g] (f) -- (0,2) [bend right] to (c);
\draw[d] (c) to (d);
\end{tikzpicture}
\end{center}

\section{Combinateurs décrits par Smullyan}

\subsection{Combinateurs L, W, B, D et E}

\subsubsection{Combinateur L}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node[c] (c) at (0,0) {$\lambda$};
\node[c] (d) at (-1,-1) {$\lambda$};
\node (x) at (-1,-3) {$f(g(g))$};
\draw[d] (g) -- (0,2) to [bend left] (c);
\draw[g] (g) -- (0,2) [bend right] to (c);
\draw[d] (c) to (d);
\draw[g,bend right=15] (f) to (d);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Combinateur W}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node[c] (c) at (0,-1) {$\lambda$};
\node[c] (d) at (-1,0) {$\lambda$};
\node (x) at (0,-3) {$f(g)(g)$};
\draw[d] (g) -- (0,2) to (d);
\draw[d] (g) -- (0,2) [bend left] to (c);
\draw[g] (d) to (c);
\draw[g] (f) to (d);
\draw[d] (c) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Combinateur B}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (0,-1) {$\lambda$};
\node[c] (d) at (1,1) {$\lambda$};
\node (x) at (0,-3) {$f(g(h))$};
\draw[d] (h) to (d);
\draw[g] (g) to (d);
\draw[d] (d) to (c);
\draw[g] (f) to (c);
\draw[d] (c) to (x);
\end{tikzpicture}
\end{center}

On reconnaît la composition des fonctions $f\circ g$.

\subsubsection{Combinateur D}

On obtient D en appliquant B à lui-même~:

\begin{center}
\begin{tikzpicture}
\node (a) at (-3,4) {$a$};
\node (b) at (-1,4) {$b$};
\node (c) at (1,4) {$c$};
\node (d) at (3,4) {$d$};
\node[c] (m) at (-2,2) {$\lambda$};
\node[c] (n) at (2,2) {$\lambda$};
\node[c] (o) at (0,0) {$\lambda$};
\node (x) at (0,-2) {$a(b)(c(d))$};
\draw[g] (a) to (m);
\draw[d] (b) to (m);
\draw[g] (c) to (n);
\draw[d] (d) to (n);
\draw[g] (m) to (o);
\draw[d] (n) to (o);
\draw[d] (o) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Combinateur E}

\begin{center}
\begin{tikzpicture}
\node (a) at (-3,4) {$a$};
\node (b) at (-1,4) {$b$};
\node (c) at (1,4) {$c$};
\node (d) at (3,4) {$d$};
\node[c] (m) at (0,2) {$\lambda$};
\node[c] (n) at (1,0) {$\lambda$};
\node[c] (o) at (0,-2) {$\lambda$};
\node (x) at (0,-4) {$a((b(c)(d)))$};
\draw[g] (b) to (m);
\draw[d] (c) to (m);
\draw[g] (m) to (n);
\draw[d] (d) to (n);
\draw[g] (a) to (o);
\draw[d] (n) to (o);
\draw[d] (o) to (x);
\end{tikzpicture}
\end{center}

\subsection{Les combinateurs de permutation}

\subsubsection{Le combinateur C}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (0,1) {$\lambda$};
\node[c] (d) at (1,-1) {$\lambda$};
\node (x) at (1,-3) {$f(h)(g)$};
\draw[d] (h) to (c);
\draw[g] (c) to (d);
\draw[d,bend left] (g) to (d);
\draw[g] (f) to (c);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

Dans les booléens de Church, le combinateur C représente la négation.

\subsubsection{Le combinateur T}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (c) at (0,0) {$\lambda$};
\node (d) at (0,-2) {$g(f)$};
\draw[g, bend right] (g) to (c.north west);
\draw[d, bend left] (f) to (c.north east);
\draw[d] (c) to (d);
\end{tikzpicture}
\end{center}

T est l'initiale de \emph{transposition}.

\subsubsection{Le combinateur R}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (0,1) {$\lambda$};
\node[c] (d) at (1,-1) {$\lambda$};
\node (x) at (1,-3) {$g(h)(f)$};
\draw[d] (h) to (c);
\draw[g,bend right] (g) to (c);
\draw[d,bend left=45] (f) to (d.north east);
\draw[g] (c) to (d);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

R est la première lettre de \emph{rotation}.

\subsubsection{Le combinateur F}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (1,1) {$\lambda$};
\node[c] (d) at (0,-1) {$\lambda$};
\node (x) at (0,-3) {$h(g)(f)$};
\draw[g, bend right] (h) to (c.north west);
\draw[d, bend left] (g) to (c.north east);
\draw[g,bend right] (c.south) to (d.north west);
\draw[d, bend left] (f) to (d.north east);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le combinateur V}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (-1,0) {$\lambda$};
\node[c] (d) at (0,-1) {$\lambda$};
\node (x) at (0,-3) {$h(f)(g)$};
\draw[g, bend right] (h) to (c.north west);
\draw[d, bend left] (f) to (c.north east);
\draw[g] (c) to (d);
\draw[d, bend left] (g) to (d.north east);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Combinateur G}

\begin{center}
\begin{tikzpicture}
\node (a) at (-3,4) {$a$};
\node (b) at (-1,4) {$b$};
\node (c) at (1,4) {$c$};
\node (d) at (3,4) {$d$};
\node[c] (m) at (-1,2) {$\lambda$};
\node[c] (n) at (1,2) {$\lambda$};
\node[c] (o) at (0,0) {$\lambda$};
\node (x) at (0,-2) {$a(d)(b(c))$};
\draw[g] (a) to (m);
\draw[d] (d) to (m);
\draw[g] (b) to (n);
\draw[d,bend left] (c) to (n);
\draw[g] (m) to (o);
\draw[d] (n) to (o);
\draw[d] (o) to (x);
\end{tikzpicture}
\end{center}

\section{Combinateurs S, K et I}

\subsubsection{Le combinateur S}

S est l'initiale de \emph{substitution}. Avec K et I, c'est l'un des premiers combinateurs cités par Curry.

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (m) at (-1,1) {$\lambda$};
\node[c] (n) at (1,1) {$\lambda$};
\node[c] (o) at (0,-1) {$\lambda$};
\node (x) at (0,-3) {$f(g)(f(h))$};
\draw[g] (f) -- (-2,2) to (m);
\draw[d] (g) to (m);
\draw[g] (f) -- (-2,2) to[bend left] (n);
\draw[d] (h) to (n);
\draw[g] (m) to (o);
\draw[d] (n) to (o);
\draw[d] (o) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le combinateur J}

Ce combinateur est de Rosser.

\begin{center}
\begin{tikzpicture}
\node (a) at (-3,4) {$a$};
\node (b) at (-1,4) {$b$};
\node (c) at (1,4) {$c$};
\node (d) at (3,4) {$d$};
\node[c] (m) at (-1,2) {$\lambda$};
\node[c] (n) at (1,2) {$\lambda$};
\node[c] (o) at (2,1) {$\lambda$};
\node[c] (p) at (0,0) {$\lambda$};
\node (x) at (0,-2) {$a(b)(a(d)(c))$};
\draw[g] (a) -- (-3,3) to (m);
\draw[d] (d) -- (3,3) to[bend right] (m);
\draw[g] (a) -- (-3,3) to[bend left] (n);
\draw[d] (d) -- (3,3) to (n);
\draw[g] (n) to (o);
\draw[d,bend left] (c) to (o.north east);
\draw[g] (m) to (p);
\draw[d] (o) to (p);
\draw[d] (p) to (x);
\end{tikzpicture}
\end{center}

\section{Combinateurs de point fixe}

\subsection{Combinateur utiles pour Y}

\subsubsection{Le combinateur Q}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (1,1) {$\lambda$};
\node[c] (d) at (-0,-1) {$\lambda$};
\node (x) at (0,-3) {$g(f(h))$};
\draw[g] (f) to (c);
\draw[d] (h) to (c);
\draw[g,bend right] (g) to (d);
\draw[d] (c) to (d);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le combinateur O}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,4) {$f$};
\node (g) at (1,4) {$g$};
\node[c] (c) at (0,2) {$\lambda$};
\node[c] (d) at (-1,1) {$\lambda$};
\node (x) at (-1,-1) {$g(f(g))$};
\draw[g] (f) to (c);
\draw[d] (g) -- (1,3) to (c);
\draw[g] (g) -- (1,3) to[bend right=45] (d.north west);
\draw[d] (c) to (d);
\draw[d] (d) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Combinateur U}

Ce combinateur est de Turing.

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,4) {$f$};
\node (g) at (1,4) {$g$};
\node[c] (m) at (-1,1) {$\lambda$};
\node[c] (n) at (0,0) {$\lambda$};
\node[c] (o) at (-2,-2) {$\lambda$};
\node (x) at (-2,-4) {$g(f(f)(g))$};
\draw[g] (f) -- (-1,3) to[bend right] (m);
\draw[d] (f) -- (-1,3) to[bend left] (m);
\draw[g] (m) to (n);
\draw[d] (g) -- (1,3) to[bend left] (n);
\draw[d] (n.south) to (o);
\draw[g] (g) --(1,3) to[bend right=45] (o.north west);
\draw[d] (o) to (x);
\end{tikzpicture}
\end{center}

\subsection{Combinateur de point fixe (Turing 1937)}

\subsubsection{Version abrégée}

\begin{center}
\begin{tikzpicture}
\node[c] (a) at (0,2) {U};
\node[c] (b) at (0,0) {$\lambda$};
\node (x) at (0,-1) {};
\draw[g] (a) -- (0,1) to[bend right] (b);
\draw[d] (a) -- (0,1) to[bend left] (b);
\draw[d] (b) to (x);
\end{tikzpicture}
\end{center}




\subsubsection{Le combinateur}

\begin{center}
\begin{tikzpicture}
\node (a) at (-2,10) {$a$};
\node (b) at (0,10) {$b$};
\node (c) at (2,10) {$c$};
\node[c] (l1) at (-2,8) {$\lambda$};
\node[c] (l2) at (3,7) {$\lambda$};
\node[c] (l3) at (-1,6) {$\lambda$};
\node[c] (l4) at (4,5) {$\lambda$};
\node[c] (l5) at (-1,4) {$\lambda$};
\node[c] (l6) at (4,3) {$\lambda$};
\node[c] (l7) at (-1,2) {$\lambda$};
\node[c] (l8) at (2,1) {$\lambda$};
\node (x) at (2,0) {};
\draw[g] (a) -- (-2,9) to[bend right] (l1);
\draw[d] (a) -- (-2,9) to[bend left] (l1);
\draw[g] (l1) to (l3);
\draw[d] (b) -- (0,7) to[bend left] (l3);
\draw[g] (b) -- (0,8) to[bend right=60] (l5.north west);
\draw[d,bend left] (l3) to (l5);
\draw[g] (a) -- (-2,9) -- (3,9) -- (3,8) to[bend right] (l2);
\draw[d] (a) -- (-2,9) -- (3,9) -- (3,8)  to[bend left] (l2);
\draw[g] (l2) to (l4);
\draw[d] (b) -- (0,9.5) -- (4,9.5) to[bend left=60] (l4);
\draw[g] (c) -- (2,3) -- (-1,3) to[bend right=60] (l7.north west);
\draw[g] (b) -- (0,7) to (l6);
\draw[d,bend left] (l4) to (l6);
\draw[d,bend left] (l5) to (l7);
\draw[g] (l7) to (l8);
\draw[d] (l6) to (l8);
\draw[d] (l8) to (x);
\end{tikzpicture}
\end{center}

\subsection{Combinateur de Curry}

\subsubsection{Version abrégée}

\begin{center}
\begin{tikzpicture}
\node[c] (f) at (-2,2) {$S$};
\node[c] (g) at (0,2) {$L$};
\node[c] (c) at (0,-1) {$\lambda$};
\node[c] (d) at (-1,0) {$\lambda$};
\node (x) at (0,-2) {};
\draw[d] (g) -- (0,1) to (d);
\draw[d] (g) -- (0,1) [bend left] to (c);
\draw[g] (d) to (c);
\draw[g] (f) to (d);
\draw[d] (c) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le combinateur Y}

\begin{center}
\begin{tikzpicture}
\node (a) at (-1,4) {$a$};
\node (b) at (1,4) {$b$};
\node[c] (l1) at (1,2) {$\lambda$};
\node[c] (l2) at (3,2) {$\lambda$};
\node[c] (l3) at (0,0) {$\lambda$};
\node[c] (l4) at (2,0) {$\lambda$};
\node[c] (l5) at (1,-1) {$\lambda$};
\node (x) at (1,-2) {};
\draw[g] (b) -- (1,3) to[bend right] (l1);
\draw[d] (b) -- (1,3) to[bend left] (l1);
\draw[g] (b) -- (1,3) -- (3,3) to[bend right] (l2);
\draw[d] (b) -- (1,3) -- (3,3) to[bend left] (l2);
\draw[g] (a) -- (-1,1) to (l3);
\draw[g] (a) -- (-1,1) -- (1,1) to (l4);
\draw[d] (l1) to (l3);
\draw[d] (l2) to (l4);
\draw[g] (l3) to (l5);
\draw[d] (l4) to (l5);
\draw[d] (l5) to (x);
\end{tikzpicture}
\end{center}



\section{Numéraux de Church}

\subsection{Nombres}

Le nombre 0 a déjà été vu~:

\begin{center}
\begin{tikzpicture}
\node (f) at (0,2) {$f$};
\node (g) at (1,2) {$g$};
\node (c) at (0.5,0) {};
\draw[d] (g) -- (1,1) to (c);
\end{tikzpicture}
\end{center}
 
\subsubsection{Le nombre 1}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (c) at (0,0) {$\lambda$};
\node (x) at (0,-1) {};
\draw[g] (f) -- (-1,1) to[bend right] (c);
\draw[d] (g) -- (1,1) to[bend left] (c);
\draw[d] (c) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le nombre 2}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (l1) at (0,0) {$\lambda$};
\node[c] (l2) at (0,-2) {$\lambda$};
\node (x) at (0,-3) {};
\draw[g] (f) -- (-1,1) to[bend right] (l1);
\draw[d] (g) -- (1,1) to[bend left] (l1);
\draw[g] (f) -- (-1,-1) to[bend right] (l2);
\draw[d] (l1) to[bend left] (l2);
\draw[d] (l2) to (x);
\end{tikzpicture}
\end{center}


\subsubsection{Le nombre 3}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (l1) at (0,0) {$\lambda$};
\node[c] (l2) at (0,-2) {$\lambda$};
\node[c] (l3) at (0,-4) {$\lambda$};
\node (x) at (0,-5) {};
\draw[g] (f) -- (-1,1) to[bend right] (l1);
\draw[d] (g) -- (1,1) to[bend left] (l1);
\draw[g] (f) -- (-1,-1) to[bend right] (l2);
\draw[d] (l1) to[bend left] (l2);
\draw[g] (f) -- (-1,-3) to[bend right] (l3);
\draw[d] (l2) to[bend left] (l3);
\draw[d] (l3) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le nombre 4}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (l1) at (0,0) {$\lambda$};
\node[c] (l2) at (0,-2) {$\lambda$};
\node[c] (l3) at (0,-4) {$\lambda$};
\node[c] (l4) at (0,-6) {$\lambda$};
\node (x) at (0,-8) {};
\draw[g] (f) -- (-1,1) to[bend right] (l1);
\draw[d] (g) -- (1,1) to[bend left] (l1);
\draw[g] (f) -- (-1,-1) to[bend right] (l2);
\draw[d] (l1) to[bend left] (l2);
\draw[g] (f) -- (-1,-3) to[bend right] (l3);
\draw[d] (l2) to[bend left] (l3);
\draw[g] (f) -- (-1,-5) to[bend right] (l4);
\draw[d] (l3) to[bend left] (l4);
\draw[d] (l4) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Le nombre 5}

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$f$};
\node (g) at (1,2) {$g$};
\node[c] (l1) at (0,0) {$\lambda$};
\node[c] (l2) at (0,-2) {$\lambda$};
\node[c] (l3) at (0,-4) {$\lambda$};
\node[c] (l4) at (0,-6) {$\lambda$};
\node[c] (l5) at (0,-8) {$\lambda$};
\node (x) at (0,-10) {};
\draw[g] (f) -- (-1,1) to[bend right] (l1);
\draw[d] (g) -- (1,1) to[bend left] (l1);
\draw[g] (f) -- (-1,-1) to[bend right] (l2);
\draw[d] (l1) to[bend left] (l2);
\draw[g] (f) -- (-1,-3) to[bend right] (l3);
\draw[d] (l2) to[bend left] (l3);
\draw[g] (f) -- (-1,-5) to[bend right] (l4);
\draw[d] (l3) to[bend left] (l4);
\draw[g] (f) -- (-1,-7) to[bend right] (l5);
\draw[d] (l4) to[bend left] (l5);
\draw[d] (l5) to (x);
\end{tikzpicture}
\end{center}

\subsection{Opérations}

\subsubsection{Successeur}

\begin{center}
\begin{tikzpicture}
\node (f) at (-2,3) {$f$};
\node (g) at (0,3) {$g$};
\node (h) at (2,3) {$h$};
\node[c] (c) at (1,1) {$\lambda$};
\node[c] (d) at (0,-1) {$\lambda$};
\node[c] (e) at (-1,-3) {$\lambda$};
\node (x) at (-1,-4.5) {$f(g(f(h)))$};
\draw[g] (f) -- (-2,2) to (c.north west);
\draw[d] (h) to (c);
\draw[g,bend right] (g) to (d);
\draw[d] (c) to (d);
\draw[g] (f) -- (-2,-2) to[bend right] (e.north west);
\draw[d] (d) to (e);
\draw[d] (e) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Addition}

\begin{center}
\begin{tikzpicture}
\node (a) at (-3,6) {$a$};
\node (b) at (-1,6) {$b$};
\node (c) at (1,6) {$c$};
\node (d) at (3,6) {$d$};
\node[c] (l1) at (0,4) {$\lambda$};
\node[c] (l2) at (-2,2) {$\lambda$};
\node[c] (l3) at (2,2) {$\lambda$};
\node[c] (l4) at (0,0) {$\lambda$};
\node (x) at (0,-1) {};
\draw[g] (b) -- (-1,5) to[bend right] (l1);
\draw[d] (c) -- (1,5) to[bend left] (l1);
\draw[g] (a) -- (-3,4) to[bend right] (l2.north west);
\draw[d] (c) -- (1,5) to[bend right=60] (l2.north east);
\draw[g] (l1) to (l3);
\draw[d] (d) -- (3,4) to[bend left] (l3);
\draw[g] (l2) to (l4);
\draw[d] (l3) to (l4);
\draw[d] (l4) to (x);
\end{tikzpicture}
\end{center}

\subsubsection{Exponentiation}

La soustraction et la multiplication font usage du combinateur Y, donc sont nettement plus complexes que l'addition. Mais l'exponentiation est par contre très simple puisqu'il s'agit du combinateur d'application~:

\begin{center}
\begin{tikzpicture}
\node (f) at (-1,2) {$a$};
\node (g) at (1,2) {$b$};
\node[c] (c) at (0,0) {$\lambda$};
\node (d) at (0,-1.5) {$a^b$};
\draw[d] (g) to (c);
\draw[g] (f) to (c);
\draw[d] (c) to (d);
\end{tikzpicture}
\end{center}








\end{document}
