Introduction
Le but de ce TP est d’implémenter en OCaml un interpréteur Magistack (https://esolangs.org/wiki/MagiStack), une machine virtuelle minimale à pile. Il y a plusieurs façons de proposer une solution, mais nous allons nous concentrer sur une en particulier.
De manière générale, une machine virtuelle (VM) est un programme qui va lire et donner du sens à un ensemble d’instructions. Ces instructions sont encodées d’une certaine manière et chacune de ces instructions représente une action que la machine virtuelle doit effectuer. Dans les VM à pile, la machine virtuelle considère pour gérer ses opérations une pile sur laquelle elle pousse, enlève des valeurs…etc. Les instructions qu’une VM à pile est capable de comprendre sont donc fortement à la manipulation de la pile.
La VM que vous allez implémenter ici (ou commencer à implémenter), est une VM "jouet". Elle ne considère que très peu d’instructions. Chaque instruction est encodée sur un caractère, et un programme est une longue chaine de caractère où chacun d’eux est donc une instruction. À chaque "étape" de l’exécution d’un programme, la VM va décoder un des caractères et faire ce que le symbole indique.
Pour coder cette VM en OCaml, vous allez devoir recoder ce comportement général, à savoir : évoluer dans un programme, vers la gauche ou la droite (en fonction des actions), pour regarder quelle est l’action et effectuer l’action en question.
Représentation des concepts
Si on regarde bien, il y a très peu de concepts qui vont être manipulés par notre VM. Essayez de vous poser quelques instants pour réfléchir au problème (on en discute ensemble évidemment).
-
Quels concepts voyez-vous qui vont être indispensable à la réalisation de la VM ?
-
Parmi ces concepts, comment vais-je les représenter ? (quelle structure je peux utiliser pour les représenter)
-
Imaginez que vous avez une fonction générale
eval_program, quels vont être les paramètres que vous allez passer à la fonction ? -
Imaginez maintenant que vous avec une fonction très spécifique qui est responsable de l’exécution de votre programme. Combien de concepts pensez-vous qu’il est nécessaire de passer à cette fonction ? Que vont-ils représenter ?
-
À un instant
T, qu’est-ce qui va donner l’état de ma VM en cour d’exécution ?
Première étape de "compilation" de notre programme
Comme vous l’avez peut-être deviner, travailler directement sur notre programme sous forme de chaine de caractère n’est pas très pratique. Nous allons donc "compiler" notre programme pour nous retrouver avec une représentation qui va être plus facile à manipuler en mémoire. L’idée générale va être de considérer que notre programme sous forme de chaine de caractère va être transformé en une liste d’instructions. Pour produire cette liste à partir d’une chaine de caractère, il est plus facile de passer par une première étape qui va prendre la chaine de caractère et la "couper" en une liste de caractère. Vous pouvez vous servir de la fonction suivante pour faire ça :
let explode s = List.init (String.length s) (String.get s);;-
Proposez un type algébrique pour représenter les instructions
-
Ecrivez une fonction qui va prendre une liste de caractère et la transforme en liste d’instructions
-
Ecrivez une fonction qui prend une chaine de caractère et la transforme en liste d’instructions
Modélisation de la pile et de la VM et avancer dans un programme
Nous allons maintenant regarder comment nous pouvons modéliser le fait d’avancer dans un programme, la pile et la VM.
-
Comment peut-on représenter le fait qu’on avance dans un programme à chaque fois qu’on lit une instruction ?
-
Comment peut-on représenter la pile ?
-
Comment peut-on représenter la VM en elle-même ? A-t-on besoin d’une structure de donnée spéciale ou un ensemble de fonctions suffit ?
Comportement des instructions et de la VM
Il est possible d’associer une fonction à chacune des instructions. Regardez bien sur le site de présentation du langage (https://esolangs.org/wiki/MagiStack) quelles sont les différentes instructions et ce qu’elles font.
-
Ecrivez une fonction pour chacune de ces instructions. Faites bien attention à ce qu’elles prennent en entrée et comment elles agissent sur le système pour le modifier (donc, que prennent-elles en entrée et que produisent-elle en sortie).
-
Ecrivez une fonction spéciale pour la VM qui prend une liste d’instructions (à voir comment vous la représentez exactement, discutons en), une stack vide et qui exécute le programme.
-
Ecrivez une fonction qui prend un programme sous forme de caractère et qui l’exécute en vous servant de toutes les fonctions précédentes.
){kind=avatar}