(** Un interpréteur BF (partie 1) *)
(** Nous allons développer un interpréteur BF (https://fr.wikipedia.org/wiki/Brainfuck).
Référez-vous à la page Wikipédia pour avoir une introduction complète au langage.
Dans cette première partie, nous allons ignorer les instructions `[` et `]`.
Dans les grandes lignes : en BF, on manipule des cases mémoires avec les instructions suivantes :
| Instruction | Action |
|-------------|------------------------------------------------------------------------------|
| `>` | Avance d'une case mémoire |
| `<` | Recule d'une case mémoire |
| `+` | Incrémente la valeur de case mémoire courante |
| `-` | Décrémente la valeur de case mémoire courante |
| `,` | Lit un caractère de l'utilisateur et le stocke dans la case mémoire courante |
| `.` | Affiche le caractère contenu dans la case mémoire courante | *)
(** Fonctions utiles
----------------
Comme nous allons manipuler des caractères. On importe donc deux fonctions qui
nous seront utiles : `Char.chr` et `Char.code`
On peut regarder leur types:
# Char.chr;;
- : int -> char = <fun>
# Char.code;;
- : char -> int = <fun>
`Char.chr` nous donne un caractère depuis sa valeur numérique, et
`Char.code` fait l'opération inverse. *)
(** État de la machine
------------------
Notre interpréteur va manipuler un « état » qui représente l'état de la machine
à tout moment de l'éxécution du programme. Cet état est un ensemble de case
mémoire, ainsi qu'une case mémoire courante. Il y a plusieurs façon de
représenter cet état. On pourrait par exemple le représenter par une liste et un
indice dans cette liste. L'état avec une mémoire vide (tout à zéro) et l'indice
qui pointe vers la seconde case mémoire serait donc :
mémoire : [0, 0, 0, 0, 0, 0, ...]
indice : ^
Mais on sait qu'indexer une liste de façon arbitraire (c'est-à-dire, accéder au
*n*ième élément d'une liste) n'est pas efficace (cela requiert *n* opérations).
On va plutôt représenter l'état par deux listes : les cases mémoires situées
*avant* la case courante, et les cases mémoires restantes. Ainsi, notre mémoire
précédente serait ainsi représentée de la façon suivante :
mémoire : [0], [0, 0, 0, 0, 0, ...]
On représente donc notre état par un type contenant deux
éléments. Chaque élément de ce n-uplet est une liste de case mémoire,
c'est-à-dire une liste de `char`, car chaque case mémoire représente un octet. *)
type state = {
before : char list;
after : char list;
}
(** Notez qu'on définit un *alias* de type, afin de clarifier nos déclarations de
type dans notre programme. Ce n'est pas obligatoire, mais préférable.
On défini ensuite, arbitrairement, une limite à notre mémoire dans `memorySize`. *)
let memory_size : int = 256
(** On peut ensuite définir l'état initial de la machine. C'est un état où la
mémoire est initialisée à 0, et où nous nous situons à la première case
mémoire. On se situe au premier élément, donc `before` est vide. Le reste de
la mémoire est initialisé à 0. On utilise la fonction `List.init` pour
initialiser une liste. `List.init` prend une taille pour la liste, et une
fonction qui est appelée avec l'indice de chaque élément, et qui renvoie la
valeur pour cet élément. On initialise tout à 0. *)
let initial_state : state = {
before = [];
after = List.init memory_size (fun _ -> Char.chr 0);
}
(** Se déplacer dans la mémoire
---------------------------
Définissons quelques fonctions pour manipuler nos états. Tout d'abord, on
veut pouvoir se déplacer de droite à gauche dans la mémoire. On définit
donc des fonctions qui "modifient" un étant, dans le sens où elles prennent
un état, et retournent l'état après modification. Il n'y a pas d'"effet de
bord". On doit aussi supporter le cas où on se déplace trop loin dans la
mémoire et on en sort. Dans ces cas, on lèvera l'exception suivante. *)
exception OutsideMemory
let move_right (state : state) : state = match state.after with
| [] -> raise OutsideMemory
| cell :: after -> { before = cell :: state.before; after = after }
(** Notez qu'on stocke les cases mémoires située avant le pointeur courant *à l'envers*.
Ainsi, si on veut représenter la mémoire suivante :
mémoire : [1, 2, 3, 4, 5]
indice : ^
Elle sera représentée par :
{ before = [2, 1]; after = [3, 4, 5] }
Pourquoi ? Car se déplacer dans notre mémoire ne requiert qu'une seule
opération : pour se déplacer à droite, on prend la valeur courante (`3`) et on
l'ajoute en devant les valeurs précédentes (`[2, 1]` devient `[3, 2, 1]`). Cela
est fait en une seule opération. Si on avait pas inversé la liste des valeurs
précédentes, il aurait fallu ajouter `3` tout au bout de cette liste, et pour
cela on aurait du traverser la liste dans son entièreté, ce qui est moins
efficace.
On peut se déplacer vers la gauche également : *)
let move_left (state : state) : state = match state.before with
| [] -> raise OutsideMemory
| cell :: before -> { before = before; after = cell :: state.after }
(** On peut désormais se déplacer dans notre mémoire :
move_left (move_right (move_right initial_state)) *)
(** Lire et modifier la mémoire
---------------------------
On va aussi vouloir lire et écrire dans la case mémoire courante :
- lire nous donne la valeur d'une case mémoire, donc un `char`
- écrire *change* la valeur d'une case, et nous donne un nouvel état *)
let read_cell (state : state) : char = match state.after with
| [] -> raise OutsideMemory
| cell :: _ -> cell
let write_cell (new_cell : char) (state : state) : state = match state.after with
| [] -> raise OutsideMemory
| _ :: after -> { state with after = new_cell :: after }
(** Et incrémenter et décrémenter la case mémoire courante, qui sont toutes deux des
opérations changeant la mémoire : *)
let increment_cell (state : state) : state =
write_cell (Char.chr (Char.code (read_cell state) + 1)) state
let decrement_cell (state : state) : state =
write_cell (Char.chr (Char.code (read_cell state) - 1)) state
(** Notez bien que quand on parle de *changer* la mémoire, on retourne une nouvelle
valeur de la mémoire, mais on ne modifie d'état : on ne touche pas à la mémoire
initiale, elle est **immutable**. *)
(** Commandes
---------
Une commande BF est un des caractères `<`, `>`, `+`, `-`, `,`, `.`, `[`, ou
`]`. On va introduire des types pour représenter ces commandes, plutôt que
de les représenter par un caractère.
On va faire la distinction entre trois types de commandes :
- Les commandes agissant sur la mémoire uniquement (`memory_command`): `<`, `>`, `+`, `-`
- Les commandes faisant des entrées-sorties (`io_command`): `.` et `,`
- Les commandes agissant sur le flot de contrôle du programme (`control_command`): `[` et `]`
On peut ensuite définir comment évaluer chaque type de commande. *)
(** Commandes mémoires
------------------
Une commande mémoire change simplement l'état actuel de notre programme : notre
fonction d'évaluation prend donc une commande à évaluer, l'état dans lequel
l'évaluer, et nous donne un nouvel état après avoir évalué la commande. *)
type memory_command =
| MoveLeft (* caractère '<' *)
| MoveRight (* caractère '>' *)
| Increment (* caractère '+' *)
| Decrement (* caractère '-' *)
let eval_emory_command (command : memory_command) (state : state) : state = match command with
| MoveLeft -> move_left state
| MoveRight -> move_right state
| Increment -> increment_cell state
| Decrement -> decrement_cell state
(** Nous pouvons maintenant nous déplacer et modifier notre mémoire :
# read_cell (eval_memory_command Increment (eval_memory_command MoveRight initial_state))
'\001'
(Le caractère `\001` est le caractère qui a pour valeur numérique 1) *)
(** Commandes entrées-sorties
-------------------------
Il nous faut maintenant gérer les commandes qui lisent l'entrée utilisateur
et qui affichent quelque chose. Ce n'est pas quelque chose qu'on peut
décrire mathématiquement, et on doit donc avoir recours à des fonctions non
mathématiques. OCaml n'étant pas un langage fonctionnel pur, on a accès à
des fonctions telles que `print_char` qui permettent d'afficher un caractère
au terminal. *)
type io_command =
| Write (* caractère '.' *)
| Read (* caractère ',' *)
(* Pour évaluer `.`, on récupére la valeur courante, on l'affiche, et on
retourne l'état non modifié. Pour évaluer `,`, on lit un caractère de la
console, on écrit ce caractère dans notre mémoire, et on retourne cette
nouvelle mémoire. *)
let eval_io_command (command : io_command) (state : state) : state = match command with
| Write ->
print_char (read_cell state);
state
| Read ->
let c = input_char stdin in
write_cell c state
(** Commandes de saut
-----------------
Les commandes de saut (`[` et `]`) nous requièrent de modifier le *pointeur
d'instruction* de notre machine. Mais ce n'est pas quelque chose qu'on a la
possibilité de faire avec notre représentation des états ! Il va donc
falloir revoir la façon de représenter les états, ce que nous ferons dans la
partie 2. *)
