Les langages de programmation – Partie 3 : Créer un interpréteur (TinyCC inside)

J’avais annoncé initialement que j’écrirais 3 articles sur le sujet des langages de programmation, et que le troisième serait consacré au thème « Qu’est-ce que j’aimerais avoir comme langage ».
Bon, j’ai menti, il y aura finalement 4 articles, et celui-ci sera consacré à la création d’un langage de programmation interprété.

Je ne vais pas m’étendre sur la théorie de la création des compilateurs et des interpréteurs. J’avais lu un énorme bouquin sur le sujet il y a quelques années ; c’était super intéressant, mais j’avoue ne pas en avoir retenu grand chose de concret. Il faut dire que c’est assez éloigné de mes préoccupations quotidiennes.

Non, je vais plutôt vous parler… d’un moyen de contourner un peu tout ça.

Compilateurs et interpréteurs

Reprenons. Si on simplifie à l’extrême, le travail d’un compilateur c’est ça :

1. Lecture du code source.
2. Analyses diverses.
3. Construction de l’arbre de compilation.
4. Optimisation.
5. Génération du code machine et écriture du fichier exécutable.

Le boulot d’un interpréteur, c’est plutôt :

1. Lecture du code source.
2. Analyses diverses.
3. Construction de l’arbre d’interprétation.
4. Optimisations éventuelles.
5. Exécution (évaluation de l’arbre).

Dans le principe, il y a beaucoup de similitudes. D’ailleurs, toutes les explications données dans le livre dont je vous parlais plus haut étaient dans l’optique de construire un interpréteur ; alors que le livre s’intitulait Les compilateurs.

De plus en plus, les interpréteurs passent par un code machine intermédiaire, le bytecode, destiné à être exécuté par une machine virtuelle. Ce code peut parfois être stocké sur disque pour accélérer les exécutions futures, mais ce n’est pas systématique. Cela donne donc des interpréteurs qui fonctionnent ainsi :

1. Génération du bytecode
1. Lecture du code source.
2. Analyses diverses.
3. Construction de l’arbre de compilation.
4. Optimisation.
5. Génération du bytecode.
2. Exécution
1. Chargement de la machine virtuelle.
2. Exécution (évaluation du bytecode par la machine virtuelle).

Ce fonctionnement est censé être plus rapide, car le bytecode est généré spécifiquement pour la machine virtuelle ; celle-ci l’exécute comme du code natif à ses yeux, et non pas comme une évaluation pas-à-pas de l’arbre syntaxique (oh les explications foireuses ! je m’en excuse platement).

Il existe un autre type d’interpréteur, les compilateurs JIT. Leur principe est de compiler à la volée le code source en binaire natif. Le gros intérêt est que le binaire est exécuté directement par l’ordinateur, il n’a pas besoin de machine virtuelle. Pourquoi tous les interpréteurs ne sont pas des compilateurs JIT ? Parce que c’est loin d’être simple à mettre en œuvre. Les compilateurs natifs sont habituellement assez lents ; cela ne pose pas le moindre problème, car quand on compile du code C ou C++, le but est d’obtenir un programme dont l’exécution sera la plus rapide possible ; ils intègrent d’ailleurs plein d’optimisations qui ralentissent la compilation mais qui accélèrent l’exécution.

Un compilateur JIT doit donc être capable de compiler nativement dans un délai très court, afin que l’exécution d’un programme interprété ne semble pas systématiquement ralentie.

Comment créer un interpréteur ?

J’ai été amené à créer plusieurs interpréteurs. Un interpréteur Lisp minimal, un interpréteur de script compatible Bash, un évaluateur mathématique assez poussé dans un outil de génération de PDF. Et je confirme : sans être impossible, ce n’est quand même pas simple.

Et encore, il ne s’agissait que de simples interpréteurs. Pas de bytecode ni de machine virtuelle, et encore moins de compilation native. J’ai bien codé une machine virtuelle particulièrement sommaire durant mes études, mais elle émulait un ordinateur tellement simple que ça ne serait d’aucune utilité.

Par contre, j’ai suivi des cours de compilation, durant lesquels j’ai appris à utiliser Lex et Yacc, qui forment un compilateur de compilateur. Ils offrent les outils de base nécessaires à la réalisation d’un interpréteur ou d’un compilateur (analyse lexicale, analyse syntaxique) : ils permettent de lire un fichier et de le « comprendre » ; à partir de là, on peut soit exécuter du code (interprétation directe), soit construire un arbre d’exécution (pour ensuite interpréter ou compiler l’arbre).

Je dois bien avouer que je n’ai pas utilisé ces programmes une seule fois de toute ma carrière. Ils ne sont pas particulièrement simples à appréhender, mais rien de fondamentalement impossible.
La grande difficulté n’est pas spécialement d’utiliser Lex/Yacc pour extraire les lexèmes qui composent un code source. La grande difficulté, c’est de construire un arbre efficace et de le traiter correctement. C’est la différence entre un petit interpréteur rigolo et un vrai langage.

La solution ?

J’en viens enfin à ma recette miracle. Il existe un compilateur C qui présente trois caractéristiques très intéressantes :

1. Il est particulièrement rapide. Il applique forcément moins de d’optimisations sur le code qu’un compilateur comme GCC, mais n’en produit pas moins du code binaire natif très efficace.
2. Il peut compiler et exécuter à la volée. Conjugué au point précédent, cela veut dire qu’on peut s’en servir comme d’un interpréteur C. Mais, contrairement aux quelques rares interpréteurs qui utilisent une syntaxe proche du C, le code n’est pas interprété ; il est compilé nativement − très très vite − puis exécuté, et tout ça sans écrire de fichier sur le disque.
3. Il est disponible sous la forme d’une bibliothèque de fonctions, elle-même écrite en C, qui permet d’exécuter du code à la volée. Cette bibliothèque permet même de partager des symboles ; ainsi, le programme qui l’utilise pour compiler et exécuter du code à la volée pourra accéder directement aux données et aux fonctions de ce code, et inversement !

Ce compilateur, c’est TinyCC. Il est écrit par le français Fabrice Bellard, qui a aussi à son actif l’émulateur QEMU ou encore la bibliothèque FFmpeg.

Je suis en train de réaliser divers benchmarks en ce moment, pour comparer plusieurs langages de programmation. Je publierai les résultats sur ce blog quand ce sera terminé. Mais je peux déjà vous dire que, pour un code orienté objet avec de l’héritage et du polymorphisme, beaucoup d’instanciations d’objets, des parcours de tableaux et quelques calculs mathématiques, j’obtiens pour le moment les résultats suivants :

• code C compilé avec GCC : 24 ms
• code C++ compilé avec G++ : 25 ms
• code C compilé à la volée avec TinyCC : 150 ms
• code PHP : 2934 ms

Bon, en soit ça ne veut pas dire grand chose (je publierai les codes sources en même temps que l’ensemble des résultats du benchmark). Mais on se rend quand même compte que TinyCC est très efficace (pour info, la compilation avec GCC prend environ 60 ms).

L’idée que j’ai en tête, c’est que plutôt que d’écrire un interpréteur complet (travail de titan), il est certainement plus simple d’écrire un programme qui traduit une syntaxe donnée en code C, que TinyCC peut compiler et exécuter à la volée. En plus, cela offre la possibilité de compiler le code nativement.

D’une certaine manière cela veut dire que le code C devient le bytecode, le langage intermédiaire qui est utilisé pour produire le binaire final.
Je sais que ça peu sembler tordu, mais je suis très humble quant à ma capacité à générer du bytecode et à créer une machine virtuelle. Par contre, je pense pouvoir être capable de créer un traducteur qui génère du code C à partir d’un autre code source.
La vraie question, c’est de savoir si cette étape de traduction ne risque pas à elle seule de plomber les performances d’un tel interpréteur…

Faisons un test !

Allez, soyons fou, essayons d’écrire un traducteur ultra-simpliste.

Créons un langage de programmation dont la syntaxe est très simpliste. Il n’accepte que 3 types de commandes. Voici un exemple de code source (bon, ça fait un peu pompeux d’appeler ça du code source, mais on est là pour s’amuser) :

// affecte une variable
// leurs noms commencent par un dollar suivi d'une seule lettre
AFF $a = 3
// incrémente une variable
// si elle n'avait pas été affectée, elle est initialisée à 0
INC $b
// affichage conditionnel
// écrit le texte après les deux-points si la condition est vraie
IF $a <= 3 : Texte

Nous allons maintenant écrire un programme qui lit un fichier de code source (passez-moi l’expression), génère du code C dans une variable, puis utilise la bibliothèque libtcc pour compiler et exécuter ce code.

Le début du programme est facile. Quelques inclusions basiques, la définition des prototypes de deux fonctions utilitaires et la fonction principale du programme. Celle-ci alloue une zone mémoire qui contiendra le code C, puis lance la lecture du fichier source et la génération du code C, ensuite elle affiche le contenu de code C généré, et enfin elle appelle la fonction qui exécute le code C.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <libtcc.h>

// prototypes
void execute(char*);
void readfile(char*, char*);

/* fonction principale */
void main(int argc, char **argv)
{
   char result[1024];

   // lecture du fichier et génération du code C
   readfile(argv[1], result);
   // affichage du code C généré
   printf("CODE C :\n%s\n", result);
   // exécution du code C généré
   execute(result);
}

La fonction de lecture et de génération de code initialise quelques variables, ouvre le fichier contenant le code source, lit les instructions qui y sont écrites et ajoute l’équivalent en C dans une chaîne de caractères. Il y a une petite subtilité au sujet des variables : à chaque instruction, on complète un tableau pour indiquer quelles sont les variables qui sont utilisées, afin de faciliter leur déclaration en C.

/* lit le fichier et génère le code C */
void readfile(char *filename, char *result)
{
   FILE *input;
   char line[128], buf[128], msg[128], op1, cond[3];
   char code[1024], variables[128];
   int i;

   // initialisations
   result[0] = code[0] = '\0';
   strcat(result, "int wrapper() {\n");
   for (i = 0; i < 128; ++i)
      variables[i] = '\0';
   // ouverture du fichier source
   input = fopen(filename, "r");
   // lecture de toutes les lignes du fichier
   while (!feof(input) & fgets(line, 128, input))
   {
      // détection de la commande
      if (sscanf(line, "AFF $%c = %d", &op1, &i))
         sprintf(buf, "\t%c = %d;\n", op1, i);
      else if (sscanf(line, "INC $%c", &op1))
         sprintf(buf, "\t%c++;\n", op1);
      else if (sscanf(line, "IF $%c %s %d : %s", &op1, cond,
                      &i, msg))
         sprintf(buf, "\tif (%c %s %d) printf(\"%s\\n\");\n",
                 op1, cond, i, msg);
      variables[op1] = op1;
      strcat(code, buf);
   }
   fclose(input);
   // définition des variables
   for (i = 0; i < 128; ++i)
   {
      if (variables[i])
      {
         sprintf(buf, "\tint %c = 0;\n", i);
         strcat(result, buf);
      }
   }
   // ajout du code
   strcat(result, code);
   strcat(result, "\treturn 0;\n}\n");
}

Enfin, la fonction d’exécution fait compiler le code C par TinyCC, place le binaire exécutable dans une zone mémoire exploitable, puis appelle la fonction que l’on a créée préalablement.

/* exécute le code généré à la volée */
void execute(char *code)
{
   TCCState *state;
   int (*wrapper)(void);
   int size;
   void *memory;

   // création du contexte TinyCC
   state = tcc_new();
   tcc_set_output_type(state, TCC_OUTPUT_MEMORY);
   // compilation du code C
   tcc_compile_string(state, code);
   // réallocation en mémoire
   size = tcc_relocate(state, NULL);
   memory = malloc(size);
   tcc_relocate(state, memory);
   // récupération du pointeur sur la fonction
   wrapper = tcc_get_symbol(state, "wrapper");
   // libération de la mémoire allouée par TinyCC
   tcc_delete(state);
   // exécution de la fonction
   wrapper();
   // libération de la mémoire contenant le code binaire
   free(memory);
}

Pour plus d’information sur l’utilisation de libtcc, je ne peux que vous conseiller de lire un très bon article sur le Site du Zéro.

Exécution

Maintenant que nous avons notre super interpréteur, nous allons l’utiliser.

Imaginons que notre code source ressemble à ceci :

AFF $a = 3
AFF $b = 1
IF $a < 5 : ok
IF $b > 7 : ko
AFF $c = 5
INC $c
IF $c >= 6 : parfait

Quand on exécute notre interpréteur, il nous affiche la fonction C générée :

int wrapper() {
   int a = 0;
   int b = 0;
   int c = 0;
   a = 3;
   b = 1;
   if (a < 5) printf("ok\n");
   if (b > 7) printf("ko\n");
   c = 5;
   c++;
   if (c >= 6) printf("parfait\n");
   return 0;
}

Et donc, le résultat de l’exécution est donc :

ok
parfait

Super, ça marche ! Trop fort.

Par acquis de conscience, je décide de comparer avec le code PHP suivant :

<?php
   $a = 3;
   $b = 1;
   if ($a < 5)
      print("ok\n");
   if ($b > 7)
      print("ko\n");
   $c = 5;
   $c++;
   if ($c >= 6)
      print("parfait\n");
?>

Et hop, un autre benchmark inutile mais rigolo :

• PHP : 25 ms
• mon interpréteur : 2 ms

Eh oui, c’est débile, ça ne sert à rien, mais ça arrache et ça me fait marrer. Évidemment, plus on ajoutera de vraies fonctionnalités à notre interpréteur pour enrichir sa syntaxe, plus on le ralentira. Mais je pense que ça prouve quand même que mon idée de base est loin d’être idiote : Si vous voulez créer un langage de programmation, utilisez le C comme « langage pivot » ; ce sera plus rapide à mettre en œuvre et plus efficace que si vous développiez votre propre bytecode et votre propre machine virtuelle. En plus vous pourrez accéder à toutes les bibliothèques de fonction disponibles en C, ce qui est loin d’être négligeable.