\documentclass{article}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}
% Pour les accents dans les fichiers
\usepackage[T1]{fontenc}        % Codage des fontes
\usepackage[francais]{babel}    % Pour du français
% Packages AMS très utiles
\usepackage{amssymb,amsfonts,amsthm,amsmath}

% 
\usepackage{verbatim}
\usepackage{fancyvrb}

% Package pour la fabrication d'un index
%\usepackage{makeidx}

% Pour les dessins d'automates éventuellement
% Il faut avoir télécharger gastex.sty et gastex.pro
% http://www.lsv.ens-cachan.fr/~gastin/gastex/gastex.html
%\usepackage{gastex}

\usepackage{listing}

% Pour les algorithmes éventuellement
\usepackage{algorithm,algorithmic}
\usepackage{listings}
\usepackage{color}
%\usepackage[plain]{algorithm}   
%\usepackage[noend]{algorithmic} 

\definecolor{light-gray}{gray}{0.95}

\usepackage{varwidth}

\newcommand{\cbox}[1]{
	\vspace{8pt}
	\begin{center}%
	\fcolorbox{black}{light-gray}{%
	\begin{varwidth}{\textwidth}%
	\textit{#1}%
	\end{varwidth}%
	}%
	\end{center}%
}

% Package de dessin
\usepackage{tikz}
\usetikzlibrary{snakes,arrows,shapes}

% Package pour avoir des liens hyper-texte dans les fichiers Pdf
% A mettre en dernier
% Pose parfois problème
\usepackage{ifpdf}
\ifpdf
\usepackage[pdftex, pagebackref=false, colorlinks=true, linkcolor=black, unicode]{hyperref}
\else
\usepackage[ps2pdf, pagebackref=false, colorlinks=true, linkcolor=black, unicode]{hyperref}
\fi

% Définitions d'environements pour les théorèmes, lemmes, définitions, ...
% Tous les environnements partagent la même numérotation
\theoremstyle{plain}
\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}[theoreme]{Lemme}
\newtheorem{proposition}[theoreme]{Proposition}
\newtheorem{corollaire}[theoreme]{Corollaire}
\theoremstyle{definition}
\newtheorem{definition}[theoreme]{Définition}
\theoremstyle{remark}
\newtheorem{remarque}[theoreme]{Remarque}
\newtheorem{exemple}[theoreme]{Exemple}

\title{MIMO}
\author{Fabrice Ben Hamouda}
\date{2009-2010}

\begin{document}

\lstset{backgroundcolor=\color{light-gray}}
\lstset{language=[Objective]Caml}

\algsetup{indent=2.5em}

\maketitle

\tableofcontents

\newpage

\addcontentsline{toc}{section}{Introduction}
\section*{Introduction}

Ce rapport décrit approximativement le fonctionnement de mon compilateur \textbf{mimo}. Il insiste surtout sur les points qui m'ont semblé les plus compliqués à mettre en \oe{}uvre. En plus du travail demandé, j'ai un petit peu optimisé le code assembleur (voir \ref{opt}). J'ai aussi laissé la possibilité d'appliquer partiellement un foncteur grâce à l'option \texttt{-app-partielle} (par défaut, cela est interdit comme spécifié dans le sujet).

J'ai laissé l'ensemble des fichiers de test que j'ai utilisé dans le sous-répertoire \textit{test}. Le script python \textit{test.py} permet de les exécuter de manière automatique et de comparer le résultat avec celui de ocaml (pour les tests dans les répertoires \textit{test/exec} et \textit{test/exec2}).

Le Makefile fourni appelle simplement \textit{ocamlbuild} et crée un lien symbolique ``mimo'' sur l'exécutable produit par \textit{ocamlbuild}. Il offre aussi la possibilité de compiler cette documentation (faire \textit{make doc}).

\begin{figure}[!h]

\begin{center}
\begin{tikzpicture}

\draw[->] (3,11) -- (3,10);
\draw (3,11) node[above]{file.ml};

\draw[rounded corners] (0,9) rectangle (6,10);
\draw (3,9.75) node {Analyse lexicale};
\draw (3,9.25) node {\textit{lexer.mll}};

\draw[->] (3,9) -- (3,8);
\draw (3,8.5) node[left]{tokens} node[right] {\textit{parser.mly}};

\draw[rounded corners] (0,7) rectangle (6,8);
\draw (3,7.75) node {Analyse syntaxique};
\draw (3,7.25) node {\textit{parser.mly}};

\draw[->] (3,7) -- (3,6);
\draw (3,6.5) node[left]{ast} node[right] {\textit{ast.mli}};

\draw[rounded corners] (0,5) rectangle (6,6);
\draw (3,5.75) node {Typage};
\draw (3,5.25) node {\textit{typing.ml}};

\draw[->] (3,5) -- (3,4);
\draw (3,4.5) node[left]{astT} node[right] {\textit{astT.mli}};

\draw[rounded corners] (0,3) rectangle (6,4);
\draw (3,3.75) node {Défonctorisation};
\draw (3,3.25) node {\textit{defunc.ml}};

\draw[->] (3,3) -- (3,2);
\draw (3,2.5) node[left]{astD} node[right] {\textit{astD.mli}};

\draw[rounded corners] (0,1) rectangle (6,2);
\draw (3,1.75) node {Optimisation};
\draw (3,1.25) node {\textit{opt.ml}};

\draw[->] (3,1) -- (3,0);
\draw (3,0.5) node[left]{astO} node[right] {\textit{astO.mli}};

\draw[rounded corners] (0,-1) rectangle (6,0);
\draw (3,-0.25) node {Production de l'assembleur MIPS};
\draw (3,-0.75) node {\textit{compile.ml}};

\draw[->] (3,-1) -- (3,-2);
\draw (3,-2) node[below]{file.s};

\draw[decorate,decoration={brace,raise=0.5pt,amplitude=2ex}] (8,10.5) -- (8,6.5);
\draw (9,8.5) node[right] {\ref{lexerParser}. Analyse lexicale et syntaxique};

\draw[decorate,decoration={brace,raise=0.5pt,amplitude=2ex}] (8,6.5) -- (8,4.5);
\draw (9,5.5) node[right] {\ref{typage}. Typage};

\draw[decorate,decoration={brace,raise=0.5pt,amplitude=2ex}] (8,4.5) -- (8,-1.5);
\draw (9,1.5) node[right] {\ref{prodCode}. Production de code};

\end{tikzpicture}
\end{center}

\caption{Organisation des sources}
\end{figure}

\section{Analyse lexicale et syntaxique}\label{lexerParser}

L'analyse lexicale et syntaxique est réalisée grâce aux outils \texttt{ocamllex} et \texttt{menhir}.

Il y a une légère différence avec OCAML : le parser (conformément à la syntaxe donnée dans le sujet) considère correct plusieurs points d'exclamation consécutifs (!) comme dans l'exemple suivant :
\begin{lstlisting}
let a:int = !!(ref (ref 1))
\end{lstlisting}
Alors qu'en OCAML, il est nécessaire d'écrire :
\begin{lstlisting}
let a:int = !(!(ref (ref 1)))
\end{lstlisting}

Les priorités du \textit{if then} par rapport au \textit{if then else} sont celles de Caml.

Le parser produit un AST (arbre de syntaxe abstraite) qui contient les informations de localisation des expressions et des autres éléments (voir fichier \textit{ast.mli}). Ces informations seront utilisés uniquement par \textit{typing.ml} et ne seront pas présentes dans les AST suivants (car après le typage, il n'y a - normalement - plus d'erreurs possibles).

Dans les AST après analyse syntaxique et après typage (\textit{Ast} et \textit{AstT}), les \textit{path} sont des listes de chaînes. Dans les AST après défonctorisation et après optimisation (\textit{AstD} et \textit{AstO}), ce sont de simples \textit{string} (obtenus par concaténation des éléments de la liste en ajoutant de ``.'').

\section{Typage}\label{typage}

Le typage est sûrement la partie la plus compliquée du projet. Il prend en entrée l'AST provenant de \textit{parser.mly} et retourne (si le programme est bien typé) un autre AST (AstT dans \textit{astT.mli}) où :
\begin{itemize}
\item toutes les informations de localisation ont disparu.
\item toutes les informations de type (en particulier les signatures) ont disparu : seul reste un booléen qui indique si les arguments des fonctions (lors des déclarations et des applications) sont de type \textit{unit} ou non (utile dans la phase d'optimisation).
\item le mot clé \textit{open} a disparu.
\item les appels de la fonction \textit{ref} (quand elle n'a pas été redéfinie évidemment) sont remplacés par un constructeur spécial : \textit{Ref}.
\item tous les noms de variable et de module (y compris les arguments de foncteur mais pas les variables ou modules à l'intérieur d'un argument de foncteur) sont rendus uniques par l'ajout d'un suffixe \textit{\_i} (où \textit{i} est un nombre différent pour toutes les variables).
\item de plus tous les noms de variable (y compris ceux définis par un \textit{let}) sont transformés en \textit{path} absolu (c'est-à-dire partant du \textit{toplevel}).
\end{itemize}

Pour indiquer qu'un module est un argument d'un foncteur, on ajoute \textit{!args} à son \textit{path} : par exemple si \textit{B} est un argument du foncteur \textit{A} (qui est au toplevel), alors le \textit{path} de \textit{B} est : \textit{A.!args.B}.

Ainsi après typage, le code Caml suivant :
\begin{lstlisting}
let b:int=5

module D = struct
  let c:int=4
end

module A(B : sig val c : int end) = struct
  module B = struct
    let a:int = B.c
    let c:unit = ()
  end
  let a:unit = B.c
end

module F = A(D)

module E = struct
  let a:int=b
  let c:unit=F.a
end
\end{lstlisting}
est transformé en l'Ast suivant :
\begin{verbatim}
  [AstT.Let (["b_1"], [], AstT.Cst (Ast.Int 5));
  
   AstT.Module (["D_2"], [],
    AstT.Struct [AstT.Let (["D_2"; "c_3"], [], AstT.Cst (Ast.Int 4))]);
    
   AstT.Module (["A_4"], [["A_4"; "!args"; "B_5"]],
    AstT.Struct
     [AstT.Module (["A_4"; "B_6"], [],
       AstT.Struct
        [AstT.Let (["A_4"; "B_6"; "a_7"], [],
          AstT.Var ["A_4"; "!args"; "B_5"; "c"]);
         AstT.Let (["A_4"; "B_6"; "c_8"], [], AstT.Cst Ast.Unit)]);
      AstT.Let (["A_4"; "a_9"], [], AstT.Var ["A_4"; "B_6"; "c_8"])]);
      
   AstT.Module (["F_10"], [], AstT.Functor (["A_4"], [["D_2"]]));
   
   AstT.Module (["E_11"], [],
    AstT.Struct
     [AstT.Let (["E_11"; "a_12"], [], AstT.Var ["b_1"]);
      AstT.Let (["E_11"; "c_13"], [], AstT.Var ["F_10"; "a_9"])])]
\end{verbatim}

L'environnement de typage est défini ainsi :
\begin{lstlisting}
(* -- Fichier astT.mli -- *)

(* Type des expressions *)
type typ = 
  | Tvar of tvar (* pour les elts ([]) non encore typees *)
  | Tint
  | Tbool
  | Tunit
  | Tlist of typ
  | Tref of typ
and tvar={mutable t:typ option}

module Smap = Map.Make (String)
(* Environnement de typage *)
type type_env = (path * typ2) Smap.t
(* Type des signatures *)
and typ2 =
  | Tval of (typ list) (* arguments de fonction *) * typ
  | Tmod of ((string*type_env) list) (* arguments de foncteur *) * type_env
\end{lstlisting}

Plus précisément, chaque \textit{type\_env} correspond à l'environnement d'un module : c'est une \textit{Smap} qui à chaque nom fait correspondre un couple composé de :
\begin{itemize}
\item un \textit{path} unique : ce \textit{path} est un path \textbf{relatif} par rapport au module considéré, autrement dit c'est toujours une liste composé d'un seul élément (sauf dans le cas particulier d'ouverture d'un module - voir \ref{open}).
\item le type de l'élément : ou bien module (\textit{Tmod}) ou bien valeur (\textit{Tval}).
\end{itemize}

\'Etudions maintenant le typage des expressions puis celui des modules.

\subsection{Typage des expressions}


Le typage des expressions s'inspire de celui utilisé dans le TD 4 (algorithme W) sauf que l'on prend bien soin de ne rien généraliser (et que donc le code est plus simple).

J'avais essayé avant d'adopter cette solution, une méthode plus simple où les types $\alpha$ n'était ni une référence ni un champ \textit{mutable} d'un \textit{record}. La fonction de typage avait un argument supplémentaire : le type attendu. Cet argument permettait de spécialiser les types des variables locales dans la plupart des cas (le nouvel environnement était alors retourné). Il refusait bien le code suivant :
\lstinputlisting{../test/typing2/bad/list.ml}
Mais malheureusement, il existe des cas plus complexes qu'il acceptait à tort comme le code suivant :
\lstinputlisting{../test/typing2/bad/listifthen.ml}

C'est pourquoi j'ai utilisé une méthode proche de l'algorithme W, qui évite ce genre de problèmes (avec la version actuelle du compilateur, l'exemple ci-dessus est bien refusé).

\subsection{Le mot clé \textit{open}}\label{open}

D'après les règles d'inférences données, les arguments d'un foncteur ne sont utilisable que dans le foncteur lui-même (impossible d'y faire référence à l'extérieur).

En revanche les règles du mot clé \textit{open} ne sont pas définies. J'ai donc repris celles de Caml (obtenues empiriquement) : les modules et variables d'un module ouvert par \textit{open} sont uniquement utilisable à l'intérieur du module considéré.

Par exemple, le code suivant est mal typé :
\lstinputlisting{../test/typing2/bad/open3.ml}

Voici comment est traité le mot clé \textit{open} :
\begin{enumerate}
\item on ajoute l'ensemble des déclarations du module à ouvrir dans l'environnement de typage en mettant comme nom unique (première coordonnée du couple renvoyé par le \textit{Smap} de l'environnement) le \textit{path} \textbf{absolu} des variables ou modules déclarés précédé de ``!open''.
\item on type le reste du module en cours (ou du \textit{toplevel}).
\item on supprime les déclarations ajoutées précédemment et on \textbf{restaure} les précédentes. On veut en effet que le code suivant soit bien typé :
\lstinputlisting{../test/typing2/good/open2.ml}
\end{enumerate}

\subsection{Typage des modules}

Après le typage d'un module, on regarde si la signature (éventuellement précisée) est compatible et on remplace l'environnement complet du module par l'environnement limité à la signature si nécessaire grâce à la fonction \texttt{sub\_sig\_env} en particulier. Pour les foncteurs, on vérifie aussi que les signatures attendues des arguments sont des sous-signature des vrais arguments (grâce à \texttt{sub\_sig\_env}).

Le problème majeur est qu'il est impossible pour un module de s'utiliser lui-même au sens où le code suivant est mal typé :
\lstinputlisting{../test/typing2/bad/module7.ml}

Ainsi, on met bien le module dans l'environnement de typage mais avec le nom ``!'' au lieu de son vrai nom. En revanche pour que les \textit{path} de l'AST renvoyé soit correct le nom unique associé à ``!'' est le nom unique du module. L'argument \textit{mo} des différentes fonctions de typage contient une liste de ``!'' correspondant au \textit{path} du module en cours.

Quand un module cherche une variable (constructeur \textit{Var} ou \textit{App} de l'AST), il utilise la fonction \texttt{get\_var} qui permet de chercher la variable (ou fonction - et de renvoyer son \textit{path} unique et son type) dans le module courant puis dans les arguments de ce module (si c'est un foncteur) puis dans le module parent, puis dans les arguments de ce module parent (si c'est un foncteur), etc. Il faut faire attention au fait suivant : si la variable cherchée est \textit{A.a}, dès que l'on trouve un module parent qui contient le module \textit{A}, il faut s'arrêter de chercher même si \textit{a} n'est pas dans ce module.

Voici un exemple mal typé qui illustre ce propos : 
\lstinputlisting{../test/typing2/bad/module9.ml}

\vspace{1cm}

REMARQUE : j'ai utilisé les règles d'unicité suivantes:
\begin{itemize}
\item les variables et les modules doivent être uniques dans une structure et dans une signature.
\item les arguments de fonction peuvent avoir le même nom, dans ce cas seul le dernier argument compte.
\item même règle pour les arguments de foncteur.
\item dans un match, les deux variables apparaissant doivent avoir un nom différent.
\end{itemize}

\section{Production de code}\label{prodCode}

La production de code s'effectue en 3 étapes : défonctorisation, optimisation, production d'assembleur

\subsection{Défonctorisation}

La défonctorisation supprime l'ensemble des foncteurs et des modules. Pour cela à chaque fois que le programme trouve un module (ou un foncteur), il le met dans une \textit{Hashtbl} globale : \textit{modules}. De plus si c'est un module sans argument (pas un foncteur, il rajoute ses déclarations (\textit{let}) à la suite de l'AST en cours de création.

Dès qu'il est nécessaire d'appliquer un foncteur à un module, le programme effectue les deux opérations suivantes :
\begin{itemize}
\item il remplace tous les \textit{path} faisant intervenir les arguments formels du foncteur (qui ont reçu un argument effectif - il est en effet possible\footnote{Comme précisé en introduction, l'application partielle de foncteur est autorisée si le flag \texttt{-app-partielle} est ajouté à la ligne de commande.} d'appliquer partiellement un foncteur et dans ce cas-là il reste des arguments formels sans arguments effectifs) par l'argument effectif correspondant. Les arguments formels sont repérables grâce aux \textit{!args} ajoutés dans leur \textit{path} (voir section \ref{typage}).
\item ensuite il change le \textit{path} du foncteur en le \textit{path} du nouveau module.
\end{itemize}

\subsection{Optimisation}\label{opt}

Durant cette phase sont effectuées les opérations suivantes :
\begin{itemize}
\item suppression des `` ' '' (prime) des noms\footnote{En effet \textit{spim} ne supporte pas les primes dans ses labels} (transformation en ``\_''). Comme les noms ont été rendus uniques par un suffixe numérique, ce n'est pas grave.
\item transformation des opérations binaires booléennes paresseuses \&\& et || en des tests \textit{if}.
\item détecte les appels récursifs terminaux et remplace le constructeur \textit{Ast} par le constructeur \textit{AstT} quand l'appel est récursif terminal. La détection des appels récursifs terminaux s'effectue grâce à un argument supplémentaire \textit{func} qui contient la chaîne vide quand les appels ne pourront être terminaux et sinon, il contient le nom de la fonction courante.
\item supprime les arguments \textit{unit} des fonctions et les remplace par des opérations séparées par des points virgules. Cela peut changer l'ordre d'évaluation des arguments mais cela est accepté par la sémantique de Caml.
\item effectue une légère sélection d'instructions et simplifie certaines expressions arithmétiques.
\end{itemize}

\subsection{Production de l'assembleur}

La production de l'assembleur est très proche de celle de \textit{arithc} (TD 2) : les variables locales sont stockées dans une \textit{Smap} \textit{env} tandis que les variables globales sont indiquées par une \textit{Hashtbl} \textit{genv}.

\vspace{5mm}

Les variables sont représentées ainsi :
\begin{itemize}
\item les entiers sont représentés sur 32 bits.
\item les constantes \texttt{false} et \texttt{[]} sont représentés par l'entier 0 ; la constante \texttt{true} est représentée par l'entier 1.
\item la constante \texttt{()} est représenté par n'importe quel entier (différence avec les conventions proposées dans le sujet).
\item une liste non vide est représentée par un pointeur alloué sur le tas pointant sur deux entiers 32 bits : la valeur de l'élément courant (pointeur) et le pointeur sur la suite de la liste (pointeur + 4).
\end{itemize}

\vspace{5mm}

Tous les arguments des fonctions sont passés sur la pile. Voici les conventions des registres :
\begin{itemize}
\item \texttt{V0} contient les résultats intermédiaires des expressions arithmétiques ou booléennes ainsi que la valeur de retour des fonctions.
\item \texttt{V1} est un registre temporaire.
\item \texttt{S0} contient la valeur du registre \texttt{RA} (avant l'exécution du programme).
\item \texttt{A0} est utilisé uniquement pour les appels \texttt{syscall}.
\item \texttt{FP} est le pointeur de \textit{frame} (pointe sur le premier argument de la fonction).
\item \texttt{SP} est le pointeur de pile
\end{itemize}

\vspace{5mm}

Voici le contenu de la pile juste avant l'appel de la fonction (à gauche), juste avant l'exécution de son contenu (label : ``funT\_nom de la fonction'') (au milieu) et juste avant le retour :

\vspace{5mm}

\begin{figure}[h!]
\begin{center}
\begin{tikzpicture}[scale=0.9]

\begin{scope}
	\draw (2,9.5) node {$\vdots$};
	
	\draw (0,8) rectangle (4,9);
	\draw (2,8.5) node {argument 1};
	
	\draw (0,7) rectangle (4,8);
	\draw (2,7.5) node {argument 2};
	
	\draw (0,6) rectangle (4,7);
	\draw (2,6.5) node {$\vdots$};
	
	\draw (0,5) rectangle (4,6);
	\draw (2,5.5) node {argument $n$};
	
	\draw[<-] (4.1,5.5) -- (4.6,5.5);
	\draw (4.6,5.5) node[right] {\texttt{SP}};
	
	\draw (0,4) rectangle (4,5);
	\draw (2,4.5) node {};
	
	\draw (0,3) rectangle (4,4);
	\draw (2,3.5) node {};
	
	\draw (0,2) rectangle (4,3);
	\draw (2,2.5) node {};
	
	\draw (0,1) rectangle (4,2);
	\draw (2,1.5) node {};
	
	\draw (0,0) rectangle (4,1);
	\draw (2,0.5) node {};
	
	\draw (0,-1) rectangle (4,0);
	\draw (2,-0.5) node {};
	
	\draw (2,-1.5) node {$\vdots$};
	
	\draw (2,-2.5) node {avant appel};
\end{scope}

\begin{scope}[xshift=6cm]
	\draw (2,9.5) node {$\vdots$};
	
	\draw (0,8) rectangle (4,9);
	\draw (2,8.5) node {argument 1};
	
	\draw[<-] (4.1,8.5) -- (4.6,8.5);
	\draw (4.6,8.5) node[right] {\texttt{FP}};
	
	\draw (0,7) rectangle (4,8);
	\draw (2,7.5) node {argument 2};
	
	\draw (0,6) rectangle (4,7);
	\draw (2,6.5) node {$\vdots$};
	
	\draw (0,5) rectangle (4,6);
	\draw (2,5.5) node {argument $n$};
	
	\draw (0,4) rectangle (4,5);
	\draw (2,4.5) node {précédent \texttt{FP}};
	
	\draw (0,3) rectangle (4,4);
	\draw (2,3.5) node {précédent \texttt{RA}};
	
	\draw (0,2) rectangle (4,3);
	\draw (2,2.5) node {variable locale 1};
	
	\draw (0,1) rectangle (4,2);
	\draw (2,1.5) node {variable locale 2};
	
	\draw (0,0) rectangle (4,1);
	\draw (2,0.5) node {$\vdots$};
	
	\draw (0,-1) rectangle (4,0);
	\draw (2,-0.5) node {variable locale $n'$};
	
	\draw[<-] (4.1,-0.5) -- (4.6,-0.5);
	\draw (4.6,-0.5) node[right] {\texttt{SP}};
	
	\draw (2,-1.5) node {$\vdots$};
	
	\draw (2, -2.5) node {avant exécution du corps};
\end{scope}

\begin{scope}[xshift=12cm]
	\draw (2,9.5) node {$\vdots$};

	\draw[<-] (4.1,9.5) -- (4.6,9.5);
	\draw (4.6,9.5) node[right] {\texttt{SP}};

	\draw (0,8) rectangle (4,9);
	\draw (2,8.5) node {argument 1};
	
	\draw (0,7) rectangle (4,8);
	\draw (2,7.5) node {argument 2};
	
	\draw (0,6) rectangle (4,7);
	\draw (2,6.5) node {$\vdots$};
	
	\draw (0,5) rectangle (4,6);
	\draw (2,5.5) node {argument $n$};
	
	\draw (0,4) rectangle (4,5);
	\draw (2,4.5) node {précédent \texttt{FP}};
	
	\draw (0,3) rectangle (4,4);
	\draw (2,3.5) node {précédent \texttt{RA}};
	
	\draw (0,2) rectangle (4,3);
	\draw (2,2.5) node {variable locale 1};
	
	\draw (0,1) rectangle (4,2);
	\draw (2,1.5) node {variable locale 2};
	
	\draw (0,0) rectangle (4,1);
	\draw (2,0.5) node {$\vdots$};
	
	\draw (0,-1) rectangle (4,0);
	\draw (2,-0.5) node {variable locale $n'$};
	
	\draw (2,-1.5) node {$\vdots$};
	
	\draw (2,-2.5) node {avant retour};
\end{scope}

\end{tikzpicture}
\end{center}
\caption{Conventions d'appels - état de la pile}
\end{figure}

Lors des appels récursifs terminaux, on se contente de faire un \textit{jump} (instruction \textit{j}) au label ``funT\_nom de la fonction'' et on arrive tout de suite dans l'état de la pile du milieu. Il y a juste à ne pas oublier de changer les arguments. C'est d'ailleurs la raison pour laquelle je traite uniquement le cas des appels récursif terminaux et pas des appels terminaux en général (car le tableau d'activation peut alors changer).


\end{document}