TD 2 - Interprète mini-Python

Le but de ce TD est de réaliser un interprète pour un fragment très simple de Python, appelé mini-Python ; il n'est pas nécessaire de connaître le langage Python.

Afin de vous aider à construire cet interprète, nous vous fournissons sa structure de base (sous la forme d'un ensemble de fichiers Caml et d'un Makefile) que vous pouvez récupérer ici : mini-python.tar.gz. Une fois cette archive décompressée avec tar zxvf mini-python.tar.gz, vous obtenez un répertoire mini-python/ contenant les fichiers suivants :

ast.ml	la syntaxe abstraite de mini-Python (complet)
lexer.mll	l'analyseur lexical (complet)
parser.mly	l'analyseur syntaxique (complet)
interp.ml	l'interprète (à compléter)
minipython.ml	le programme principal (complet)
Makefile	pour automatiser la compilation (complet)

Comme pour le TD 2, le code fourni compile (taper make, qui va lancer dune build) mais est incomplet. Vous devez compléter le fichier interp.ml.

L'exécutable s'applique à un fichier mini-Python portant le suffixe .py. Quand on fait make, le programme est lancé sur le fichier test.py.

Un fichier mini-Python a la structure suivante :

# zéro, une ou plusieurs définitions de fonctions au début du fichier
def fibaux(a, b, k):
    if k == 0:
        return a
    else:
        return fibaux(b, a+b, k-1)

def fib(n):
    return fibaux(0, 1, n)

# une ou plusieurs instructions à la fin du fichier
print("quelques valeurs de la suite de Fibonacci :")
for n in [0, 1, 11, 42]:
    print(fib(n))

Plus généralement, un fichier mini-Python est composé d'une liste optionnelle de déclarations de fonctions, suivie d'une liste d'instructions. Les instructions sont : l'affectation, la conditionnelle, la boucle (for), l'affichage d'une expression avec print, le renvoie d'une valeur avec return ou l'évaluation d'une expression. Les expressions entières sont : une constante (booléen, entier ou chaîne de caractères), l'accès à une variable, la construction d'une liste (avec la notation [e1, e2, ..., en]), l'accès à un élément de liste (avec la notation e[i]), l'appel d'une fonction, ou une des opérations +, -, * et //, ==, !=, <, <=, >, >=, and, or et not.

On considère également trois fonctions primitives : list(range(n)) construit la liste [0, 1, 2, ..., n-1] et len(l) renvoie la longueur de la liste l. (On utilisera uniquement list et range conjointement de cette façon.)

Question 1. Expressions arithmétiques

On ne considère pour l'instant que les expressions arithmétiques ne contenant pas de variable. Compléter la fonction expr pour interpréter ces expressions. (On ignorera pour l'instant le premier argument ctx de la fonction expr.) Tester sur le programme suivant :

print(1 + 2*3)
print((3*3 + 4*4) // 5)
print(10-3-4)

dont le résultat doit être

7
5
3

Les opérations division et modulo doivent signaler une erreur en cas de division par zéro. On utilisera pour cela la fonction error fournie dans le fichier interp.ml.

Pour tester facilement, on peut éditer le fichier test.py et lancer la commande make. Celle-ci compile l'interprète mini-Python et le lance sur le fichier test.py.

Question 2. Expressions booléennes et conditionnelles

Compléter les fonctions is_true et is_false, qui déterminent respectivement si une valeur est vraie ou fausse. En Python, la valeur None, le booléen False, l'entier 0, la chaîne vide "" et la liste vide [] sont considérées comme fausses et les autres valeurs comme vraies.

Compléter ensuite la fonction expr pour interpréter les constantes booléennes, les opérations and et or (dont on rappelle qu'elles sont paresseuses, c'est-à-dire n'évaluent la seconde opérande qui si nécessaire), l'opération not et les opérations de comparaison. En Python, la comparaison est structurelle ; on pourra utiliser directement la comparaison structurelle d'OCaml, c'est-à-dire utiliser des opérations comme < sur des valeurs de type value. (Ce n'est pas 100% compatible avec Python, mais on y remédiera plus loin.)

Compléter enfin la fonction stmt pour interpréter la conditionnelle (construction Sif).

Tester sur le programme suivant :

print(not True and 1//0==0)
print(1<2)
if False or True:
    print("ok")
else:
    print("oups")

dont le résultat doit être

False
True
ok

Question 3. Variables

Pour gérer les variables (du programme principal mais aussi les variables locales et paramètres) on va utiliser un environnement, à savoir une table de hachage passée aux fonctions expr et stmt sous la forme d'un argument ctx. Cette table associe à chaque variable sa valeur. Cette table d'association est réalisée avec le module Hashtbl d'OCaml et a donc le type:

  (string, value) Hashtbl.t

Compléter la fonction expr pour que l'on puisse accéder aux variables. C'est le cas de filtrage Eident id. Tenter d'accéder à une variable qui ne se trouve pas encore dans la table doit provoquer une erreur. De même, compléter la fonction stmt pour que l'on puisse affecter une variable. C'est le cas de filtrage Sassign (id, e1). Cette fois, la variable peut ou non se trouver dans la table. Dans le premier cas, sa valeur est modifiée.

Enfin, compléter la fonction expr pour que l'on puisse concaténer deux chaînes de caractères avec l'opération +.

Tester sur le programme suivant :

x = 41
x = x+1
print(x)
b = True and False
print(b)
s = "hello" + " world!"
print(s)

dont le résultat doit être

42
False
hello world!

Question 4. Fonctions

On va ajouter maintenant le traitement des fonctions. Ces dernières sont stockées dans la table globale ainsi déclarée :

let functions = (Hashtbl.create 17 : (string, ident list * stmt) Hashtbl.t)

À chaque nom de fonction est associée une paire constituée de la liste des paramètres de la fonction et de l'instruction qui constitue le corps de la fonction. Compléter la fonction file pour qu'elle remplisse cette table avec les fonctions contenues dans la liste dl.

Compléter ensuite les fonctions expr et stmt pour interpréter un appel de fonction. Pour un appel de la forme f(e1,...,en), à une fonction f de la forme def f(x1,...,xn): body il faut construire un nouvel environnement qui associe à chaque argument formel xi la valeur de ei. On peut alors interpréter l'instruction body (le corps de la fonction) dans ce nouvel environnement. L'instruction return sera interprétée en utilisant l'exception OCaml Return (déjà définie). Si la fonction se termine sans exécuter de return, la valeur None est renvoyée.

Tester sur le programme suivant :

def fact(n):
    if n <= 1: return 1
    return n * fact(n-1)

print(fact(10))

dont le résultat doit être

Question 5. Listes

Ajouter enfin le support des listes. Pour cela, compléter la fonction expr pour que l'on puisse concaténer deux listes avec l'opération +, pour interpréter l'appel aux primitives len (longueur d'une liste, mais aussi longueur d'une chaîne) et list(range(n)) (liste [0, 1, 2, ..., n-1]), et enfin pour interpréter les constructions [e1, e2, ..., en] et e1[e2].

Compléter ensuite la fonction stmt pour interpréter l'affectation d'un élément de liste (cas de filtrage Sset (e1, e2, e3)).

Enfin, compléter la fonction stmt pour interpréter la construction for. La construction Sfor(x,e,s) affecte la variable x successivement aux différents éléments de la liste e et exécute à chaque fois l'instruction s. L'expression e doit être évaluée une seule fois. À l'issue de la boucle for, la variable x contient la dernière valeur parcourue, le cas échéant.

Tester sur le programme donné au début du sujet. Le résultat doit être :

D'autres tests

Des tests positifs et négatifs sont fournis. Pour lancer votre interprète sur ces tests, faire make tests.

Question 6 (bonus). Comparaison structurelle

Sur des listes, la comparaison structurelle de Python n'est pas exactement la même que celle effectuée par OCaml sur nos valeurs de type value array. En effet, OCaml compare d'abord les longueurs des tableaux, puis ensuite les éléments. Du coup, OCaml déclare que [|0;1;1|] est plus grand que [|1|], alors que Python déclare que [0,1,1] est plus petit que [1] car il implémente un ordre lexicographique sur les listes.

Écrire une fonction compare_value: value -> value -> int pour comparer deux valeurs Python. Elle envoie un entier strictement négatif (resp. nul, resp. strictement positif) lorsque la première valeur est plus petite (resp. égale, resp. plus grande) que la seconde. On se servira de Python comme référence en cas de doute. Utiliser cette fonction pour rectifier ce qui avait été fait à la question 2.

Faire quelques tests par soi-même.

solution

retour à la page du cours