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 difference 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 éxecutable 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 detecté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 executable. 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 dirrectement 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 interpreteurs 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ète et compilateur.
Le code source python est d'abord analysé syntaxiquement et cé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 instructions 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

Lexer

...

Parser et AST

...

compilation

...

Partie machine virtuelle

Comme énoncé précédemment, la macine virtuelle de l'interprèteur python prend en entrée du bytecode, 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, et leur applique l'opération entrée en paramètres :
  • 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 superieur (>)
  • LE (Lower Equal) --> Inférieur ou égal (<=)
  • GE (Greater Equal) --> Supperieur 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 fonctionalité que nous avons pu 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 <it>Just in time</it>. 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, Interpreteur, Bytecode)