Le bytecode Python

Etudiants : MARZIN Simon et PERIVOLAS Baptiste
Chercheur : HYVERNAT Pierre

Introduction

Python est un langage de programmation multiparadigme (à la fois impératif, fonctionnel et orienté objet) créé en 1991. A la différence des langages compilés comme le C, le C++ ou le Rust, le python lui est un langage interprété (nous verrons la différence juste après). Il a la particularité dans son execution, de transformer le code en un code intermédiaire simplifié appelé Bytecode. Ce projet porte sur l'étude du fonctionnement d'un interpréteur python, et plus particulièrement du Bytecode.

Langage compilé VS interprété

Un langage compilé est un langage qui necessite de passer par un compilateur (un programme qui transforme un code source en un code objet) pour transformer le code de base en instructions de bas niveau proche de l'assembleur exécutable par la machine. En C par exemple, on doit compiler un programme C pour le transformer en .exe avant de pouvoir le lancer. Le compilateur analyse syntaxiquement tout le code, puis le transforme, ce qui fait que les erreurs sont détectées plus tôt. Les langages compilés ont la particularité d'être très rapides et performants, un programme déjà compilé étant très facilement exécutable. Néanmoins, celà rend le débug ainsi que les test plus complexes.
Un langage interprété a lui besoin d'un interpréteur (ou interprète) pour fonctionner. Il récupère un code source, le traîte, le transforme et l'execute directement dans une machine virtuelle. Les langages interprétés sont donc par conséquent plus lents que les langages compilés, mais il permettent une plus grande flexibilité. La plupart des interpréteurs traîtent et executent le code instruction par instruction. Or, ce n'est pas totalement le cas de l'interpréteur python.

Spécificité de Python

L'interpréteur python a un fonctionnement bien particulier. En effet, il est un hybride entre interpréteur et compilateur.
Le code source python est d'abord analysé syntaxiquement et sémantiquement en entiereté par un lexer et un parser (expliqué plus en détails plus bas), puis est compilé en code objet intermédiaire, le bytecode. Ce bytecode est ensuite executé instruction par instruction par la machine virtuelle python.
La syntaxe du bytecode est plutôt claire et s'apparente à de l'assembleur siplifié. Chaque instruction du code source python (affectation, calcul, definition de fonction ...) a sa propre représentation bien précise en bytecode.
Voici un exemple de bytecode pour l'instruction a = 10 :

Description du projet

Dans le cadre de nos recherches sur le sujet, nous avons décidé pour comprendre comment fonctionne l'interpréteur python d'en recoder une version simplifiée. Le code que nous avons réalisé prend en entrée un code source python basique, le transforme en code intermédiaire inspiré du vrai bytecode de Python3, et l'execute dans une machine virtuelle. Nous avons donc trouvé pertinnent de découper ce projet en deux parties distinctes : la partie Compilation et la partie Machine virtuelle et execution
Ce code prend en compte quelques fonctionnalités de base de python telles que :

• L'affectation de variable
• Les opérations de base
• La gestion des boucles
• La gestion des conditions
• La définition de fonctions en prenant en compte :
  • Les variables locales
  • Les variables globales
  • Les clotures (ou closures)
• La gestion d'une fonction built-in : print()

Pour ce qui est de l'aspect technique, ce projet a été entièrement développé en python, dans le paradigme de programmation orientée objet (POO).

Partie compilation

Python ne comprend pas directement le texte que nous écrivons. Avant de pouvoir exécuter un programme, l’interpréteur doit d’abord analyser le code source puis le transformer en une représentation plus simple à manipuler.

Dans notre projet, cette phase de compilation est découpée en plusieurs étapes importantes :

• Le lexer, qui transforme le texte en une suite de tokens
• Le parser, qui vérifie la structure du programme
• L’AST, qui représente le programme sous forme d’arbre
• Puis la compilation en bytecode

L’objectif de cette partie est donc de comprendre comment on transforme progressivement notre texte brut Python en instructions exécutables par notre machine virtuelle.

Lexer

La première étape de la compilation est le lexer (aussi appelé analyse lexicale). Son rôle est de transformer notre texte brut Python en une suite linéaire de petites unités appelées tokens.

Un token représente un élément important du langage. Chaque token possède généralement :

• Un type (NUMBER, PLUS, NAME, IF, etc.)
• Et parfois une valeur associée

Par exemple, l’instruction suivante :

x = 10 + 5

peut être découpée en une suite de tokens ressemblant à :

NAME(x) EQUAL(=) NUMBER(10) PLUS(+) NUMBER(5)

Dans l’interpréteur CPython, cette étape est relativement complexe et gère un très grand nombre de cas particuliers du langage Python.

Dans notre projet, nous avons choisi une approche volontairement plus simple. Nous avons utilisé des expressions régulières (regex) afin de détecter certains patterns précis dans le texte, puis de les associer au token correspondant.

Par exemple :

• Une suite de chiffres devient un token NUMBER
• Le caractère + devient un token PLUS
• Un mot valide devient un token NAME

Le lexer parcourt donc le code source caractère par caractère, détecte les motifs correspondant à nos règles, puis génère progressivement la liste de tokens qui sera ensuite utilisée par le parser.

C’est également à cette étape que l’indentation devient explicite. En Python, l’indentation a une importance syntaxique très forte puisqu’elle permet de délimiter les blocs de code (conditions, boucles, fonctions, etc.).

Le lexer détecte donc les changements d’indentation et génère des tokens spéciaux représentant l’entrée ou la sortie d’un bloc. Celà permet ensuite au parser de comprendre précisément la structure du programme.

Parser

Une fois la liste de tokens générée, elle est transmise au parser. Le rôle du parser est de vérifier que la suite de tokens respecte bien les règles de syntaxe du langage.

Le parser parcourt donc les tokens un par un et applique un ensemble de règles grammaticales. En fonction du token actuel, il sait quels types de tokens il doit retrouver ensuite.

Si la structure ne correspond pas à ce qui est attendu, le parser génère une erreur de syntaxe.

Par exemple, dans notre projet, lorsqu’il rencontre :

NAME(x) EQUAL(=)

le parser reconnaît le début d’une affectation de variable. Il sait donc qu’il doit ensuite trouver une expression valide (un nombre, une opération, un appel de fonction, etc.).

Le parser ne travaille donc plus directement sur du texte brut, mais sur les tokens produits par le lexer. Son objectif est maintenant de comprendre la structure logique du programme.

AST

L’AST (Abstract Syntax Tree, ou arbre syntaxique abstrait) est une représentation structurée et logique du programme.

Comme son nom l’indique, l’AST est un arbre : chaque élément important du programme devient un nœud relié à d’autres nœuds. En informatique, une structure arborescente est une structure de données organisée de manière hiérarchique, où chaque élément peut posséder plusieurs enfants.

Voir : structure d’arbre en informatique

Dans notre projet, la construction de l’AST se fait directement pendant le parsing. Il serait possible de séparer totalement les deux étapes, mais cela obligerait à reparcourir toute la liste de tokens, ce qui ajouterait des traitements inutiles.

Le parser analyse donc les tokens tout en construisant progressivement les nœuds de l’arbre.

Par exemple, lorsqu’il détecte :

NAME(x) EQUAL(=)

il reconnaît une affectation. On sait que la partie droite est une expression grâce au parser. Une fois l’expression analysée, il crée alors un nœud Assign contenant :

• Une cible (target) correspondant à la variable
• Et une valeur (value) correspondant à l’expression assignée

L’AST est une étape extrêmement importante dans la compilation. À ce stade, on ne manipule plus simplement une suite linéaire de tokens, mais une véritable représentation logique et structurée du programme.

Celà permet ensuite à la phase de compilation de parcourir facilement l’AST pour générer le bytecode correspondant.

Compilation

Une fois l’AST construit, on peut enfin passer à la phase de compilation en bytecode.

Le compilateur parcourt l’arbre en commençant par sa racine (le nœud Module). Ensuite, le parcours dépend du type de nœud rencontré.

Cette différence de comportement vient principalement du fait que certains nœuds représentent des statements (des instructions), tandis que d’autres représentent des expressions (elles renvoient une valeur).

Les statements correspondent à des actions qui structurent ou modifient le programme. Par exemple :

• Une affectation
• Une boucle
• Une condition
• Une définition de fonction

Ces nœuds possèdent souvent un body, c’est-à-dire une liste d’autres nœuds à parcourir récursivement.

Les expressions, elles, représentent des valeurs ou des calculs produisant un résultat.

Par exemple :

• Un nombre
• Une addition
• Un appel de fonction
• Une comparaison

Lors de la compilation, une expression génère généralement du bytecode produisant une valeur sur la pile d’exécution, alors qu’un statement modifie plutôt le déroulement du programme ou l’environnement d’exécution.

Le compilateur transforme donc progressivement chaque élément logique de l’AST en instructions bytecode.

Cependant, le résultat final n’est pas simplement une liste brute d’instructions. Dans notre projet, la compilation produit un objet que nous avons appelé un code object.

Cet objet représente un contexte d’exécution complet, très lié au fonctionnement des frames de la machine virtuelle.

Il contient notamment plusieurs informations importantes :

• La liste des instructions bytecode
• Les constantes utilisées
• Les noms de variables
• Les variables locales
• Le nom de la fonction ou du module
• Et d’autres métadonnées utiles à l’exécution

Lors de la génération du bytecode, nous évitons également de répéter inutilement certaines données.

Par exemple, lorsqu’une constante est rencontrée plusieurs fois, elle n’est stockée qu’une seule fois dans la liste des constantes du code object.

Les instructions bytecode utilisent alors un indice pointant vers cette liste.

Par exemple, pour la constante :

5

le compilateur peut produire :

LOAD_CONST 0

avec :

consts = [5]

L’argument 0 de l’instruction représente donc l’indice de la constante dans la liste consts.

Nous avons appliqué le même principe pour plusieurs autres éléments comme les noms de variables.

Cette approche permet :

• D’éviter les duplications inutiles
• De simplifier certaines opérations de la machine virtuelle
• Et de produire une représentation plus compacte du programme

Ce fonctionnement est d’ailleurs très proche de celui utilisé par CPython, qui stocke lui aussi les constantes, noms et variables dans différentes structures associées aux code objects.

À la fin de cette étape, le programme Python d’origine a donc complètement changé de forme :

• Le texte brut est devenu des tokens
• Les tokens sont devenus un AST
• Puis l’AST a été transformé en bytecode exécutable par notre machine virtuelle

Partie machine virtuelle

Comme énoncé précédemment, la machine virtuelle de l'interpréteur python prend en entrée un code objet, et l'execute.

Fonctionnement global

La machine virtuelle est basée sur une structure de pile Last In First Out (LIFO) pour les instructions. Elle utilise 2 piles différentes, qui ont chacune un rôle bien défini :

• Data stack : La pile où python stocke toutes les données avec lesquelles il travaille, comme les variables, les fonctions etc... (c'est la pile utilisée par la plupart des fonctions)
• Block stack : Utilisée dans les exception, ou pour certaines fonctions.

Dans le cadre de notre projet, nous avons choisi de fonctionner avec une seule pile pour simplifier son fonctionnement, contrairement à Cpython (la machine virtuelle python) qui en utilise deux .
Notre VM (Virtual Machine) possède donc une pile nomée 'call stack' (ou pile d'execution) qui est utilisée pour à la fois stocker les données, mais également les frames des fonctions (notion qui sera expliquée plus bas).
La VM prend en entrée une liste d'instructions bytecode, d'une classe bytecode que nous avons décidé de créer. Elle execute ensuite instruction par instruction jusqu'à arriver à la fin du programme.

La classe bytecode et la classe Frame

Classe bytecode

Les objets bytecode sont une liste d'instruction. Une instruction est constituée de deux informations :

• Le nom de l'instruction
• La valeur associée à l'instruction (si il y en a une)

Ces listes d'instruction est stockée dans des Frames

Classe frame

Une frame est comme une sorte de boite contenant :

• Sa liste d'instruction de bytecode
• Ses variables locales
• Son propre stack d'appel
• Un pointeur d'instruction qui montre la position de l'instruction actuellement executée
• Et un dictionnaire contenant les potentielles variables héritées d'un frame parent (pour la gestion des closures)

Quelques instructions de base en bytecode

Chaque action que fait python a sa propre traduction en bytecode. Voici les instructions de base du bytecode executé par notre VM :

• LOAD_FAST n : Charge la variable locale positionnée à l'indice n, et la push sur la pile d'execution (call stack)
• LOAD_CONST : Push une constante sur la pile
• STORE_FAST : Dépile et stock la valeur dans une variable locale
• BINARY_OP PLUS / MINUS / STAR / SLASH / PERCENT  : Dépile les deux derniers elements de la pile, leur applique l'opération entrée en paramètres, puis empile le résultat :
  • PLUS --> Addition
  • MINUS --> Soustraction
  • STAR --> Multiplication
  • SLASH --> Division
  • PERCENT --> Modulo
• COMPARE_OP EQEQ / LT / GT / LE / GE / NOTEQ  : Opérateurs de comparaison logiques. Dépile les deux derniers elements et les compare :
  • EQEQ --> égal (==)
  • LT (Lower Than) --> Strictement inférieur (<)
  • GT (Greater Than) --> Strictement supérieur (>)
  • LE (Lower Equal) --> Inférieur ou égal (<=)
  • GE (Greater Equal) --> Supérieur ou égal (>=)
  • NOTEQ (NOT Equal) --> Différent de (!=)
• POP_JUMP_IF_FALSE n / POP_JUMP_IF_TRUE : Dépile, et effectue un saut (principe de JUMP comme en assembleur) à l'instruction à l'indice n de la liste si la valeur qu'il vient de dépiler est vraie (TRUE) ou fausse (FALSE).
• JUMP_ABSOLUTE n  : Effectue un saut à l'instruction d'indice n
• STORE_NAME name  : Dépile et crée une variable 'name' dans laquelle il stocke cette valeur
• LOAD_NAME name  : Charge ce qui est stocké au nom 'name'
• POP_TOP : Fait un POP sur la pile (c'est à dire dépile)

Ces instructions sont la base de notre machine virtuelle.

Gestion des fonctions

Fonctionnement

Dans la VM Python, les fonctions ont une mécanique bien particulière et leur execution se fait en plusieurs étapes.

À la sortie de la compilation, une fonction est considérée comme un objet contenant :

• Son bytecode
• Ses variables locales
• Et ses arguments

. Le code objet de cette fonction est stocké dans une variable de la frame actuelle et on crée la fonction pour l'executer en dépilant de la stack cet objet.
Quand une fonction est définie, une nouvelle Frame est crée avec à l'interieur :

• Le bytecode de la fonction
• Les variables de la frame actuelle
• Et sa propre stack d'éxecution

Une fois créée, elle est ajoutée en haut de la pile.
Lors de l'appel, on la dépile, on vient récuperer les arguments de la fonction, on sauvegarde l'état de la frame actuelle et on l'empile sur la 'call stack', on passe les variables globales à la fonction, et on change de frame courrante pour se placer dans la frame de la fonction ce qui entraîne un changement temporaire de liste d'instruction bytecode.
Une fois les instructions de la fonction épuisées, on dépile et pousse le résultat sur la call stack, et on se replace dans la frame d'execution de base. Voici un schéma représentant la création et l'appel des fonctions :

                                                                           [mettre un schéma]

En bytecode

Ces étapes se traduisent par une suite de plusieurs instructions bien précises :

1. Première étape : l'ajout de l'objet fonction sur la stack : STORE_NAME n (avec l'objet de la fonction au nom de n dans les variables de la frame)
2. Ensuite, on crée la frame de la fonction avec MAKE_FUNCTION
3. Puis vient l'appel avec l'instruction CALL : On sauvegarde l'état de la frame actuelle, on l'empile sur le call stack, puis on se place dans la frame de la fonction.

A partir de ce moment précis, la suite d'instruction de bytecode que l'on execute n'est plus la suite de base, mais bien celle de la fonction. Cette dernière se termine par l'instruction RETURN_VALUE.
Quand l'instruction RETURN_VALUE est atteinte, on dépile la dernière valeur, on se replace dans la frame initiale, puis on empile dans la stack initiale la valeur du return.

Gestion des boucles et des conditions

Fonctionnement

Le fonctionnement des boucles en bytecode se rapproche des boucles en assembleur x86. En effet, les boucles fonctionnent à partir de jumps. Elles vont reposer sur une comparaison (la condition de la boucle), suivi d'un jump, ou non, vers le début de la boucle. Pour une boucle for i in range(n) par exemple, on vient incrémenter la variable i et la comparer à chaque fois, jusqu'à ce qu'elle ait atteint n.
Pour ce qui est des condition, c'est exactement le même principe : on vient sauter à un endroit du code ou à un autre en fonction du résultat de la comparaison.

En bytecode :

Les instructions principales des boucles et des conditions sont JUMP_ABSOLUTE n pour pouvoir sauter où on veut (utile pour les boucles while), et POP_JUMP_IF_TRUE / POP_JUMP_IF_FALSE pour effectuer les jumps en fonction d'une comparaison.
Voici l'exemple d'une boucle simple dans le bytecode de Cpython (un petit peu complexe que notre machine virtuelle) :

Ici, on reconnait bien la logique de comparer si i est inférieur à 5, et de sauter si c'est le cas.

Gestion des closures

La gestion des closures est la dernière fonctionnalité que nous avons pu partiellement implémenter à notre interpréteur python.

Définition et explications

Une closure (ou cloture en français) est une fonction qui capture des variables de son environnement lexical (une fonction définie dans une autre fonction qui utilise des variables de cette fonction externe).
Dans l'implémentation de Cpython, les closures reposent principalement sur les principes de variables libres (freevar), et des cellules (ou cell object).
Les variables libres sont les variables utilisées mais définies dans une autre fonction, et les cellules sont des objets contenant la valeur d'une variable libre, car plusieurs fonctions peuvent se partager les mêmes variables.

Dans notre VM

Nous avons décidé, pour rendre la chose plus simple, de simplement stocker les variables libres, et les donner à la frame enfant lorsqu'une fonction est créée.

Conclusion

A travers ce projet, nous avons pu comprendre comment fonctionne Cpython, de la compilation à l'execution, le tout en recréant un interpréteur de zéro. Au delà de ça, ce projet nous a permis de savoir ce qui se passe réellement derrière les programmes python que nous utilisons tout le temps. Celà nous donne aussi une idée sur le fonctionnement dans les grandes lignes certains compilateurs, et même de pousser nos recherches sur certaines optimisations qu'ils font comme la compilation Just in time. Ce projet était donc très enrichissant, et très interessant.

Informations supplémentaires

Lien du dépot github du projet : https://github.com/Marzzzbeats/Visi201

Sources :

• Documentation python
• Wikipédia : (Python, Cpython, Compilateur, Interpréteur, Bytecode)