Pulp, un environnement d'exécution multivitaminé

Salut, vu que les sujets "créons un petit langage" fleurissent sur ce forum, j'ai décidé de dépareiller un petit peu en proposant un projet de machine virtuelle.

Le but est de créer une machine virtuelle ainsi que le bytecode associé (et peut-être, pourquoi pas une IR), vers lequel les gens pourraient compiler leurs petits langages. Ce serait l'occasion pour nous de nous frotter à des problématiques sympathiques comme le fait de donner ou non un accès aux appels systèmes sur la machine hôte, ou bien réfléchir au multithreading en essayant de nous affranchir du GIL présent dans beaucoup de VMs, ou encore des choses plus balèses, comme de la compilation JIT.

Voici les différents dépots Git sur lesquels nous travaillons :

• https://github.com/ArnaudCalmettes/pulp

Pour l'heure, designons ensemble notre machine virtuelle. Je propose de partir simplement sur une machine à pile. En ajoutant au fur et à mesure des instructions et des notions qui nous semblent pertinentes pour l'exécution de langages divers et variés.

Comme je l'ai déjà dit, I'm in !

Faudrait d'abord que je me renseigne un peu sur les VMs.

Salut,

J'ai eu des problèmes de Wi-Fi donc j'ai posté sur l'autre sujet sans savoir que tu avais créé un sujet entretemps. Du coup je reposte ici: https://zestedesavoir.com/forums/sujet/6129/acid-le-lisp-like-de-la-communaute/?page=18#p115582.

Déjà faut "pre-parser" le code ça veut dire si je comprends bien ?

La génération de bytecode se fait après le parsing, oui

Pour ensuite le transformer en p-code que la process VM pourra exécuter

Je sais pas trop ce que c'est le P-Code, d'après Wikipédia c'est du bytecode portable donc oui

Sa m'intéresse, je vais essayer de sortir des instructions, mais faut que je me renseigne

Je suis en train d'étudier les documents de design de Parrot pour essayer de situer le boulot. Non pas que je tienne forcément à partir sur une machine à registres, mais c'est la première VM dont je trouve une documentation extensive pour essayer de nous inspirer.

Bon, essayons de partir sur des bases très simples, et on corrigera/enrichira ça quand on rencontrera des problèmes ou quand on voudra faire des trucs plus alambiqués.

Donc, pour moi ce qui me semble le plus facile à coder c'est une simple VM à pile. C'est-à-dire pas de registre, on pop et on push des valeurs sur une pile pour réaliser des opérations.

Définissons 1 type d'objet natif : les entiers (un seul type, disons i64 en interne).

Puis quelques opérations. J'appellerai TS (top of the stack) le sommet de la pile, TS1 l'élément juste en dessous, TS2 le troisième élément de la pile, etc. :

• ADD: TS := TS1 + TS
• MUL: TS := TS1 * TS
• DIV: TS := TS1 / TS
• SUB: TS := TS1 - TS
• POW: TS := TS1 ** TS

Maintenant il faut pouvoir peupler cette pile :

• CONST(n) : pousse l'entier constant n sur la pile

Voilà, nous avons une calculette polonaise.

Ajoutons des variables.

Il faut rajouter à la VM la notion d'environnement. Pour moi, vieux pythoniste, un environnement est une pile de scopes :

• La base de la pile est le scope global (un dictionnaire, tout simple)
• Lorsque l'on entre dans un scope lexical, on empile un nouveau dictionnaire
• Lorsque l'on sort du scope, on dépile un scope de l'environnement

Du coup :

• NEW_ENV : pousse un nouveau scope vide dans l'environnement,
• POP_ENV : dépile le sommet de l'environnement
• LET (s) : crée une entrée (variable) s dans le scope local (le sommet de l'environnement), dépile TS et associe cette valeur à s.
• LOAD (s) : effectue une recherche pour le symbole s dans l'environnement et place la valeur au sommet de la stack.
• STORE (s) : recherche un scope qui contient la clé s et associe TS à la clé s dans le scope qu'on a trouvé.

Ne réfléchissons pas tout de suite aux fonctions, closures, etc. on y viendra après avoir un premier code qui marche. Essayons déjà de partir sur cette base, et de voir où ça nous mène.

Accessoirement on peut peut-être s'ajouter quelques opcodes pour afficher le sommet de la stack, etc., pour nous aider au debug, mais je pense pas que ce soit nécessaire de spécifier ça tout de suite.

Qu'en pensez-vous ?

Edit : Après ça il faudra sûrement spécifier des instructions comme des sauts, pour réaliser des conditions, des boucles, etc. Donc introduire la notion de code pointer dans la VM, mais je vous propose de le garder pour la phase 2. Pour moi, tout ce qui est branchements (if/else) et boucles while, finalement, c'est pas tellement différent de rajouter des procédures, c'est-à-dire faire des sauts dans le bytecode.

Je pense que je vais écrire un premier prototype de cette machine en Python, si j'en ai le temps cet aprem'.

Le choix de Python de ma part est motivé par le fait que les specs risquent de beaucoup flotter le temps que l'on comprenne comment tout ça s'articule. Je suis persuadé qu'il y a un iceberg de difficultés que l'on va rencontrer et sur lesquelles je ne suis pas tombé la dernière fois que j'ai codé une VM pour le boulot, donc je préfère avancer avec prudence, obtenir un code qui marche, implémenter un petit toy-language dessus, puis avancer à l'étape suivante.

Je maintiens qu'à la fin (une fois qu'on aura une base exploitable pour un langage raisonnablement complexe) je voudrai réaliser une implémentation en Rust, pour des raisons évidentes de perfs, de proximité avec la machine (pouvoir utiliser des threads posix sans se taper un GIL imposé par Python), et parce que, bon dieu, je veux me mettre à Rust !

Il y a plein de trucs que je préfère laisser libre à l'implémentation. En particulier, la représentation binaire exacte de ces opcodes. Il y a moyen que ces trucs là bougent pas mal avec le temps.

PS : exemple de toy language que j'imagine avec cette VM :

1
2
3
4
5

let add_mul = |a, b, c|
    let tmp = a + b in
    tmp := tmp * c
    return tmp
end

J'aime bien l'idée du mot clé let à la caml pour définir un binding dans un scope donné, de même que d'avoir un opérateur d'affectation bien distinct :=. Mais tout ça est parfaitement secondaire et pas du tout l'objet de ce projet.

Je passe juste pour dire qu'il ne faut pas avoir peur des mots comme « machine virtuelle » ou « bytecode », ça peut rester très simple selon les choix qu'on fait. Voici un exemple de machine virtuelle avec son bytecode qui est Turing-complet malgré sa simplicité.

À noter que ça peut servir dans l'autre sens : à partir du moment où on peut implémenter un Brainfuck complet dans un langage, alors ce langage est transitivement Turing-complet lui aussi.

Après réflexion, je pense qu'il est quand même important de pouvoir spécifier un format de bytecode, en plus de la nature et du comportement des opcodes, parce que la description des données donne une indication très forte sur la façon dont la machine fonctionne et représente ses données internes.

Je suis donc en train de réfléchir à tout ça, pour vous fournir un modèle de données précis, ainsi qu'une API en Python pour parser et produire facilement des fichiers suivant cette spec.

Salut,

J'ai codé un truc dégueulasse en Python pour essayer vite fait des instructions. C'est pas une VM à proprement parler, c'est pas performant, mais on peut définir rapidement de nouvelles instructions donc c'est utile pour tester des petits trucs: https://gist.github.com/myrma/8998194d45e26ef5fe8f097358113ada

Edit: Pas de commentaire sur le code SVP, je sais que c'est pas beau, mais je dois réviser l'oral de français en même temps donc j'ai fait le truc à l'arrache

Allez, GO, premier jet d'un format de fichier.

À haut niveau, un fichier de bytecode est un binaire qui va se représenter comme suit (tout est représenté en little-endian, si chaîne de caractères il doit y avoir, elles seront encodées en utf-8 ou bien en ASCII…, sachant que si vous pouvez décoder de l'utf-8, vous gèrerez l'ASCII automatiquement) :

1
2
3

PulpFile:
   Header
   Segment*

Donc nous avons un en-tête (Header) et un ensemble de segments. L'en-tête du fichier sera formaté comme ceci :

1
2
3
4
5
6
7
8

Header:
   magic     (4 octets, la chaîne "PULP")
   major     (1 octet, version majeure de Pulp, ici: 0)
   minor     (1 octet, version mineure de Pulp, ici: 1)
   patch     (1 octet, numéro de patch, ici: 0)
   _____     (1 octet de padding)
   timestamp (4 octets, date de génération, au format timestamp Unix)
   md5       (16 octets, aggrégat md5 de la totalité du fichier, excepté le header)

Passons aux segments. Il peut y en avoir plusieurs types différents, donc on va les formater comme ceci :

1
2
3

Segment:
    SegmentHeader
    SegmentData

Le SegmentHeader sera de la même forme pour tous les segments :

1
2
3
4

SegmentHeader
    size (4 octets, longueur du segment en octets, y compris le présent `SegmentHeader`)
    type (1 octet, type de segment)
    ---- (3 octets de padding)

Définissons un premier type de segment, décrivant un morceau de code exécutable tout bête. Celui-ci aura pour type 0x01.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

CodeSegment:
    SymbolsTable (table de symboles utilisés dans le code)
    ConstTable   (table des constantes utilisées dans le code)
    Code         (le code, enfin !)

Code:
    size (2 octets, nombre d'opcodes)
    Opcode*

Opcode:
    code (1 octet)
    arg? (2 octets ou 0 suivant que l'opcode doive prendre un argument ou non)

SymbolsTable:
    size (2 octets, nombre de symboles dans la table)
    Symbol* (les symboles)

Symbol:
    length (1 octets, taille du symbole)
    value  (`length` octets, le nom du symbole, encodé en utf-8)

ConstTable:
    size (2 octets, nombre de constantes)
    Constant* (les constantes)

Constant:
    type (1 octet, type de la constante, 0x01 pour un entier)
    value (la constante encodée selon son type, donc 8 octets pour un entier)

Le Code consiste en une suite d'opcodes. Chaque opcode sera constitué d'un octet, suivi de son argument (si applicable, suivant l'opcode) qui tiendra sur 2 octets. Cet argument optionnel peut être :

• l'indice d'un élément dans la table des symboles (un nom de variable)
• l'indice d'un élément dans la table des constantes
• (plus tard) l'adresse d'un bout de code vers lequel on voudra sauter…

Ça veut donc dire qu'on aura :

• des opcodes d'un seul octet,
• des opcodes qui prendront 3 octets,
• au maximum 65535 éléments dans la table des constantes,
• au maximum 65535 éléments dans la table des symboles.
• au maximum 65535 opcodes dans un Code.
• des variables qui font maximum 255 octets de long (ce qui est très largement suffisant selon n'importe quelle coding-style!)

Si t'es un homme, tu nous écris un code d'exemple !

OK, alors écrivons un fichier qui réalise l'addition 1 + 2.

En bytecode :

1
2
3

LOAD_CONST  (1)
LOAD_CONST  (2)
ADD

Disons que LOAD_CONST soit le code 0xA0 et ADD l'opcode 0x90, la table des symboles contiendra 0 valeur, la table des constantes les entiers 1 et 2 (à l'indice 0 et 1). Le bytecode donnera :

1
2
3
4
5

LOAD_CONST         0xA0
(1 == const[0])    0x00 0x00
LOAD_CONST         0xA0
(2 == const[1])    0x01 0x00
ADD                0x90

La table des constantes:

1
2
3
4
5

0x02 0x00                                   (2 éléments)
0x01                                        (int)
0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00     (1)
0x01                                        (int)
0x02 0x00 0x00 0x00 0x00 0x00 0x00 0x00     (2)

Nous avons donc un fichier qui ressemblera à ceci :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

0x50 0x55 0x4c 0x50     ("PULP") 
0x00 0x01 0x00          (0.1.0)
0x00                    (...padding...)
0x57 0x6e 0xbc 0xfa     (2016-06-25 19:18:50)
0x17 0x6d 0x7d 0x7f 0xde 0x3f 0x69 0x00       (md5)
0xc8 0x7f 0x64 0x77 0x11 0xc3 0xab 0xb2

0x25 0x00               (size: 37 octets)                <--- début du segment         
0x01                    (type=code) 
0x00 0x00 0x00          (...padding...)
0x00 0x00               (table des symboles vide)
0x02 0x00               (table de 2 constantes)
  0x01 0x01 0x00 0x00 0x00 0x00 0x00 0x00 0x00 
  0x01 0x02 0x00 0x00 0x00 0x00 0x00 0x00 0x00      
0x03 0x00               (3 opcodes)
  0xA0 0x00 0x00        LOAD 0 (1)
  0xA0 0x01 0x00        LOAD 1 (2)
  0x90                  ADD

Il l'a fait !

En fait je pense que la taille du Code serait peut-être plus judicieusement exprimée en octets plutôt qu'en opcodes.

Je suis pas sûr : déjà, 2¹⁶ opcodes, ça peut s’avérer limite, mais 2¹⁶ octets, ça risque d’être limitant.

Si on part sur le principe d'une VM un peu comme celle de python, chaque fonction peut avoir son segment de code à elle. Si tout le programme devait tenir dans le segment je suis d'accord, mais si les fonctions sont comme en python des objets de premier ordre qui peuvent embarquer leur propre segment de code, pour le coup on est large.

Au risque de paraitre très con, je ne comprends vraiment pas ce que tu cherches à faire.