\documentclass[10pt]{tpcaml}

% TP caml à LLG, Fin Mai
% par Gabriel Scherer

\tp{6}{Interprète\\}
% \usepackage{amsfonts}

\usepackage{listings}
\lstset{language={Caml},basicstyle=\small}

\begin{document}

  \maketitle  

\vspace{12pt}

  Un code source est (généralement) un fichier texte dans un langage
  bien défini. C'est très bien, mais souvent on n'écrit pas les codes
  sources uniquement pour les lire, mais aussi pour ``faire quelque
  chose'', ``lancer'' le programme qui lui correspond. Il y a deux
  grandes méthodes pour faire quelque chose :
  \begin{itemize}
  \item on peut utiliser un \emph{interpréteur}, un programme déjà
    lancé sur la machine qui va lire le code source qu'on lui donne et
    effectuer les calculs correspondants
  \item on peut utiliser un \emph{compilateur}, un programme qui va
    lire le code source et produire un autre programme écrit en
    \emph{langage machine}, un langage très simple que notre
    ordinateur peut alors exécuter directement
  \end{itemize}

  Il est nettement plus simple d'écrire un interpréteur, et c'est ce
  qu'on va faire ici pour un langage de programmation très simple.

\vspace{12pt}

\begin{question}
  Écrire un programme \code{valide $:$ string -> bool} qui prend une
  chaîne contenant uniquement des `(` et des `)`, et indique si elle
  est bien parenthésée. Par exemple, \code{"()"}, \code{"(())"} et \code{"(()())()"} sont
  bien parenthésées, mais pas \code{"())("}.
\end{question}

\vspace{12pt}

\section{Le langage BF}

Le BF est un langage très simple, qui a été écrit dans le but d'être
le plus simple à compiler possible. Un programme BF dispose d'une
``bande'' mémoire découpée en $N$ cases contenant chacune un entier,
et d'un ``pointeur'' placé sur l'une des cases de la bande, et qui
peut se déplacer vers les deux cases voisines. Le langage dispose de
8 instructions, représentées par 8 lettres :
\begin{itemize}
\item `>` et `<` déplacent le pointeur vers la case de droite (`>`) ou
  de gauche (`<`) de la case courante
\item `+` et `-` modifient la valeur de la case courante : `+` ajoute
  1, `-` enlève 1
\item `.` affiche la valeur de l'entier contenu dans la case courante
\item `,` lit un entier, et le stocke dans la case courante
\item `[` saute à l'instruction suivant le `]` correspondant si la
  case courante vaut $0$
\item `]` revient à l'instruction suivant le `[` correspondant si la
  case courante ne vaut pas $0$
\end{itemize}

Les crochets fonctionnent comme des parenthèses : un crochet fermant
correspond au dernier crochet ouvrant qui n'a pas déjà été refermé.

\subsection{Mises en appétit}

\begin{question}
  Étant donné une bande de départ, que font les quatre programmes suivants ?\\
  \code{\ \ \ \ ,+.} $\qquad$ \code{[-.]} $\qquad$ \code{[[-]>]} $\qquad$
  \code{[-]>,[>,]<[.<]} ?
\end{question}

\vspace{12pt}

\begin{question}
  Écrire un programme BF qui lit deux entiers naturels et affiche leur somme.
  % solution : ,>,[-<+>].
\end{question}

\vspace{12pt}

\begin{question}
  Écrire un programme BF qui lit deux entiers naturels et affiche leur produit.
  % solution : ,>,[-<[-<+<+>>]<[->+<]>>]<<<.
\end{question}

\vspace{12pt}

\subsection{Parsing}

On va maintenant essayer de \emph{parser} le langage BF : étant donné
une chaîne de caractères représentant un programme Brainfuck, on
voudrait obtenir une valeur \caml qui représente la structure du programme.

On définit pour représenter un programme BF deux types, \code{instr}
et \code{prog}, représentant respectivement une instruction brainfuck
(instruction simple ou boucle délimitée par des crochets) et un
bloc d'instructions.

\begin{lstlisting}
  type prog == instr list
  and instr =
  | Move of int      (* déplacement du pointeur *)
  | Change of int    (* modification de la case *)
  | Read | Print     (* lecture/ecriture *)
  | Loop of prog     (* boucle : [...] *)
\end{lstlisting}

Il faut que vous recopiez cette déclaration dans votre code pour
pouvoir l'utiliser ensuite. Vous pouvez remarquer que ces deux types
sont mutuellement récursifs : chacun utilise l'autre dans sa propre
définition.

\vspace{12pt}

\begin{question}
  Que fait le programme \code{,[.-].} ?\\
  Écrire la valeur de type \code{prog} correspondant.  
\end{question}

\vspace{12pt}

On cherche à écrire une fonction \code{bf\_parse $:$ string -> prog} qui
prend une chaîne et renvoie la valeur du type \code{prog}
correspondante.

Notre type étant récursif, on peut s'attendre à ce que la fonction
\code{bf\_parse} utilise de la récursivité (elle ne sera pas récursive
elle-même mais contiendra une sous-fonction récursive). Plus
précisément, la récursion dans la définiton de \code{instr} est dans
le cas \code{Loop} (les blocs délimités par des crochets), donc on
peut s'attendre à un appel récursif servant à parser l'intérieur d'une
boucle. Il faut donc que notre fonction récursive :
\begin{itemize}
\item puisse commencer à une position arbitraire (après le `[` dans le cas de l'appel récursif)
\item puisse s'arrêter avant la fin de la chaîne (au `]` correspondant dans notre cas)
\end{itemize}

On utilisera donc le squelette suivant :
\begin{lstlisting}
  exception Erreur of int;;
  
  let bf_parse str =
    let ajoute x (xs, y) = (x :: xs, y) in
    let rec parse i =
       (* votre code ici ... *)
    in
    let (prog, fin) = parse 0 in
    if fin < string_length str then raise (Erreur fin)
    else prog
\end{lstlisting}

L'exception Erreur sert à indiquer la position où se trouvent des
erreurs de syntaxe. Par exemple, le programme \code{[]][} est
incorrect à partir de la $3^e$ lettre donc renverrait l'exception
\code{Erreur 2}.

Le type de \code{parse} est \code{int -> prog * int} : il prend en
paramètre l'indice à partir duquel il doit commencer à lire dans la
chaîne \code{str}, et renvoie le bout de programme qu'il a lu, et
l'indice auquel il s'est arrêté. Pour parser toute la chaîne on le
lance au début (indice $0$) et on vérifie qu'il ne s'est pas arrêté
avant la fin (sinon c'est une erreur).

\vspace{12pt}

\begin{question}
  À votre avis ? Compléter le squelette.
\end{question}

\subsection{Évaluation}

Maintenant, vous allez devoir vous débrouiller seuls.

\vspace{12pt}

\begin{question}
  Écrire une fonction \code{bf\_eval $:$ prog -> unit} qui évalue le
  code BF donné.  Utiliser deux sous-fonctions mutuellement
  récursives, \code{eval\_prog $:$ prog -> unit} et \code{eval $:$ instr ->
    unit}.
\end{question}

\vspace{12pt}

\begin{question}
  Question libre : écrire des fonctions travaillant sur le type
  \code{prog} pour produire des représentations du même programme en
  moins d'instructions. Par exemple on peut réunir deux instructions
  \code{Move} consécutives en une seule. On pourra même envisager de
  modifier le type \code{prog}.
\end{question}

\end{document}
