Conception et implémentation d'un interpréteur complet pour le langage APS, un noyau de langage de programmation impératif développé progressivement en quatre versions. Le pipeline intègre un analyseur lexical et syntaxique (OCaml / ocamlyacc), un vérificateur de types (Prolog / SWI-Prolog) et un évaluateur (OCaml).
Quatre versions du langage
Chaque version étend la précédente avec de nouvelles constructions :
- APS0 — noyau fonctionnel pur : expressions entières et booléennes, fonctions lambda, récursivité, instruction
ECHO. - APS1 — traits impératifs : affectation (
SET), structures de contrôle (IF,WHILE), procédures avec passage par valeur. - APS1a — passage par référence dans les procédures, permettant des modifications directes sur les arguments sans copie.
- APS2 — tableaux : allocation dynamique (
alloc), accès indicé (nth), gestion de blocs mémoire contigus.
APS3 (exceptions et fonctions de première classe) a fait l'objet d'une ébauche du typage uniquement.
Pipeline d'exécution
Un programme .aps traverse trois étapes successives :
- Analyse lexicale et syntaxique (OCaml + ocamllex + ocamlyacc) — production d'un terme Prolog représentant l'AST. Les erreurs lexicales signalent la ligne et la colonne exactes via une règle de capture sur le lexer :
| _ as char { let pos = lexbuf.lex_curr_p in let msg = Printf.sprintf "Lexing error: unexpected character '%c' at line %d, position %d" char pos.pos_lnum (pos.pos_cnum - pos.pos_bol + 1) in raise (Failure msg) } - Typage (Prolog / SWI-Prolog) — vérification des règles de typage via
type_prog/3; le mode trace de SWI-Prolog a servi d'outil de débogage principal. - Évaluation (OCaml) — interpréteur dirigé par la syntaxe abstraite, avec gestion d'un environnement et d'une mémoire. Les résultats de tous les exemples sont exportés dans
output_evaluation.csv.
Choix d'implémentation
APS0 — environnement fonctionnel
L'environnement est un Map.Make(String) OCaml mappant les identifiants à leurs valeurs. Les fermetures (InF pour les fonctions, InFR pour les fonctions récursives) capturent l'environnement lexical à la définition, garantissant une portée correcte sans état global mutable.
APS1 / APS1a — gestion de la mémoire
Introduction d'une table de hachage memory associant des adresses entières à des valeurs. Les commandes impératives (eval_stat) modifient cet état. APS1a ajoute le passage par référence : la procédure reçoit directement l'adresse mémoire de l'argument au lieu d'une copie de sa valeur.
APS2 — tableaux et blocs mémoire
Allocation d'un bloc contigu via allocn : la fonction recherche le premier espace libre de taille n et initialise chaque cellule à zéro. Un bug critique a été identifié et corrigé lors des tests : l'affectation d'une variable scalaire écrasait par erreur la première cellule d'un tableau alloué précédemment.
(* avant correction : SET i 99 écrasait nth src 0 → résultat "99 20" au lieu de "10 20" *)
let allocn sigma n =
let rec find_space addr =
if addr + n > max_address then failwith "Memory full"
else if List.for_all
(fun i -> not (Hashtbl.mem sigma (addr + i))) (range 0 n)
then addr
else find_space (addr + 1)
in
let start_addr = find_space !next_address in
for i = 0 to n - 1 do
Hashtbl.add sigma (start_addr + i) (InZ 0)
done;
next_address := start_addr + n;
(start_addr, sigma)En séparant strictement les espaces d'adresse des scalaires et des blocs tableau, le résultat correct 10 20 est obtenu.
Tests et performances
Un script test_samples.sh exécute l'ensemble des exemples sur les quatre versions et exporte les résultats dans deux fichiers CSV (typage et évaluation). Tous les tests passent pour APS0 à APS2. Les programmes APS1a inclus dans les échantillons APS1 échouent intentionnellement au typage, validant l'incompatibilité ascendante des versions.
