Pulp, un environnement d'exécution multivitaminé

Qu'est ce que tu ne comprends pas exactement ?

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.

L'élève : Je ne comprends pas !
Le prof : Qu'est-ce que tu ne comprends pas ?
L'élève (sans le dire) : Comment est-ce qu'il veut que je lui dise ce que je ne comprends pas, j'ai rien pigé à ce qui s'est dit sur cette page, alors que je devrai.
Le prof (sans le dire) : Comment est-ce qu'il veut que je lui explique s'il ne me dit pas précisément ce qu'il n'a pas compris.

Désolé, mais même en tentant de cibler, je ne comprends vraiment pas ce que tu veux faire. Donc, très simplement, c'est quoi les entrées et sorties de ta machine virtuelle, par exemple ?

Donc si je comprends bien, si je veux faire quelque chose genre ça:

1
2

foo = 6
reponse = foo * 7

… j'aurai un bytecode qui ressemblera à ça:

1
2
3
4
5
6
7
8

LOAD_CONST (6)
STORE (foo)
POP
LOAD_SYMBOL (foo)
LOAD_CONST (7)
MUL
STORE (reponse)
POP

Donc ma table de symbole sera la suivante:

1
2
3
4
5
6
7

// 2 symboles + padding
0x02 0x00

0x03                                   // foo: 3 caractères
   0x66 0x6F 0x6F                      // f o o
0x07                                   // reponse: 7 caractères
   0x72 0x65 0x70 0x6f 0x6e 0x73 0x65  // r e p o n s e

Et donc, en imaginant qu'on a les opcodes suivants:

… on aura le segment suivant:

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

0x39 0x00          size: 57 octets
0x01               type: code
0x00 0x00 0x00     padding
0x02 0x00          2 symboles (foo et reponse)
  0x03 0x66 0x6F 0x6F 0x07 0x72
  0x65 0x70 0x6f 0x6e 0x73 0x65
0x02 0x00          2 constantes (6 et 7)
  0x01 0x06 0x00 0x00 0x00 0x00 0x00 0x00 0x00 
  0x01 0x07 0x00 0x00 0x00 0x00 0x00 0x00 0x00  
0x12 0x00          18 octets
  0xA0 0x00 0x00   LOAD_CONST 0 (6)
  0xB0 0x00 0x00   STORE 0 (foo)
  0xC0             POP
  0xA1 0x00 0x00   LOAD_SYMBOL 0 (foo)
  0xA0 0x01 0x00   LOAD_CONST 1 (7)
  0x91             MUL
  0xB0 0x01 0x00   STORE 1 (reponse)
  0xC0             POP

C'est ça ?

L'entrée de la machine, c'est un bytecode, préalablement compilé depuis un programme dans un langage quelconque : le bytecode est la cible vers laquelle les langages sont compilés.

La machine virtuelle va simplement exécuter ce bytecode.

Cela veut dire que suivant les capacités de la machine (ce qu'elle sait gérer, les opérations et abstractions qu'elle propose), le bytecode sera plus ou moins expressif et donc les langages pourront plus ou moins facilement implémenter des fonctionnalités sympa.

@AlphaZeta, le STORE est là pour modifier un symbole existant. Je préconise que la machine impose une définition séparée de la modification, avec LET pour créer le binding.

Ça nous simplifiera la vie quand on voudra gérer des closures et ce genre de joyeusetés (j'avais en tête une récente discussion avec Eusèbe à propos des défauts de conception de la gestion des portées lexicales de Python).

Sinon c'est exactement ça. (mais ton code fait 17 octets)

Je suis nouveau au monde de la compilation, mais pourquoi a-t-on besoin d'une table de symboles ?

Pourquoi on remplace pas les noms des symboles par des trucs moins lourds, comme des entiers non signés ?

J'ai piqué ce concept à Python (… évidemment…). Ça permet de debugger beaucoup plus facilement les programmes (et de désassembler totalement le bytecode également). Et de les rendre dynamiques et faire de l'introspection par la même occasion…

En gros garder le nom des choses rend la machine et les langages plus sympa à utiliser.

Ça sert à quoi le magic word, le MD5, et le timestamp dans le header ?

Il me semblait que tu expliquais ça dans ton article sur les fuites de Dropbox mais j'ai la flemme de retrouver l'article et ça serait bien que tu expliques ici aussi

Le magic permet de vérifier qu'on est en train de lire le bon format de fichier (l'utilisateur n'essaye pas d'exécuter un fichier powerpoint…).

Le timestamp permet de se servir d'un fichier pulp comme cache. Typiquement si tu compiles un module en bytecode, qu'un fichier de bytecode existe déjà pour ce module et qu'il est plus récent que le code source, pas besoin de le recompiler.

Le hash est un grand classique des fichiers binaires, il permet de vérifier l'intégrité des données, et donc d'abandonner l'exécution si les segments ont été corrompus.

En vrai je l'ai mis "par habitude" : c'est pas indispensable à l'exécution mais ça ne mange pas de pain et ça pourra aider plus tard.

Vous pourriez avoir un langage contenant qu'une seule instruction

Ou même en contenant aucune

Techniquement parlant, oui, mais la galère…

Je pense que l'objectif du projet est plutôt de rester dans le classique.

Pas forcément rester dans le classique mais dans le simpliste, ce qui revient ici à la même chose.

Attention : la VM ne sera pas simpliste à terme.

Le but du jeu est de permettre de supporter des choses assez complexes comme des fonctions de premier ordre et des closures, ce qui impose une certaine expressivité. Pour le moment on commence par un code linéaire avec quelques sauts, mais ensuite il y aura des fonctions qui vont s'imbriquer, donc des stack frames… Ça va demander aussi de gérer des "objets" nativement (sans forcément supporter la POO) pour définir les différentes données natives, et également un garbage collector.

Il faut penser aussi que la VM est une cible pour des petits langages pédagogiques, donc il va également falloir qu'on implémente des outils annexes comme un débogueur pas à pas, pourquoi pas une interface un peu sexy pour profiler les programmes, en tout cas au minimum un désassembleur.

Au final je ne pense pas que la VM, à terme, soit vraiment simple ou simpliste. Dans l'idée il n'y a rien de foncièrement difficile à faire (surtout si on s'y prend progressivement et qu'on prend le temps de comprendre ce qu'on fait à chaque étape, et il y a pas mal de choses qu'on peut apprendre de VM existantes…), mais je pense que le résultat final sera respectablement complexe.

J'ai codé un truc qui lit et dump le bytecode dans un fichier en Python, pour voir comment gérer tout ça (mais je suis bien conscient que en vrai ça sert à rien de le faire en Python).

En fait le bytecode c'est juste la sérialisation de nos instructions de manière optimisée, c'est ça ? Quand la VM lira notre bytecode, elle désérialisera le fichier en une suite d'instruction ou elle interprétera directement ?

Le bytecode à terme pourra être traduit en assembleur ou c'est pas fait pour ça ?

Il y a encore pas mal de choses que je ne comprends pas…

PS: mon bytecode ne respecte pas ta spec de toute façon, c'était surtout un test pour moi, histoire de voir un peu comment ça se passe (première fois que j'utilise bytearray )

Le bytecode n'a pas vraiment besoin d'être deserialisé : tu lis un octet (l'opcode) et tu appelles le code qui reagit à cet opcode, qui peut lui même lire les deux octets suivants s'il prend un argument, il fait ensuite son boulot puis fait avancer le code pointer à l'instruction suivante, et ainsi de suite.

Sinon on peut peut-être envisager compiler le bytecode vers de l'assembleur pour faire un JIT mais pour moi c'est pas du tout (du tout du tout) la priorité.

PS : il faut voir un segment de code un peu comme un code object de python (écris une fonction puis joue avec son attribut func.__code__ dans une console). Tu verras que le bytecode (func.__code__.co_code) est intact.

PPS : tu verras aussi que les code objects de Python ont des tables qui ressemblent un peu à nos SymTable et ConstTable (mais avec des rôles légèrement différents), et qui elles, sont complètement deserialisées.

Le code n'a pas changé tu as simplement fait pointer le code object de a sur le bytecode de b.

À la base je voulais surtout dire que python garde le bytecode des fonctions intact sans plus de traitement. C'est la raison d'être du bytecode. Il est directement exécutable sans avoir besoin d'autres transformations.

Par jouer je voulais surtout dire "essayer de comprendre ses attributs, à quoi ils servent et ce qu'on peut en déduire sur le fonctionnement de la vm de Python".

Bon j'ai un peu avancé ce matin. En particulier j'ai plutôt bien entamé un module en python qui fige les opcodes et permet d'écrire un segment de code de façon feng shui (j'ai anticipé pas mal de difficultés futures que j'ai déjà rencontrées par le passé, comme par exemple le fait de devoir écrire un opcode qui réalise un jump alors qu'on ne sait pas encore vers quelle position il doit sauter).

Je devrais pouvoir le finaliser et le partager ici ce soir. Ensuite je m'attaquerai à un désassembleur. Puis un proto pour le moteur d'exécution… Et enfin je pourrai expliquer exemple à l'appui comment va marcher tout ce merdier.

Petite preview.

Les opcodes que j'ai déjà définis:

 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
29

>>> for opcode in sorted(bytecode.OPS_BY_NAME.values(), key=lambda o: o.code):
...     print('{:<15s} (0x{:02x}): {}'.format(opcode.name, opcode.code, opcode.doc))
...     
... 
NOP             (0x00): Do nothing (No OPeration)
POP             (0x01): Pop TS off of the value stack.
ROT_2           (0x02): TS, TS1 := TS1, TS
ROT_3           (0x03): TS, TS1, TS2 := TS2, TS, TS1
DUP_TOP         (0x04): Duplicates TS
LOAD_CONST      (0x0a): TS := ConstTable[ARG]
NEW_ENV         (0x20): Push a new scope onto the env.
POP_ENV         (0x21): Exit scope: pops it off of the env.
LET             (0x25): Binds SymTable[ARG] to TS in local scope.
LET_POP         (0x26): LET ARG + POP
STORE           (0x27): Lookup for a scope containing SymTable[ARG] & update the binding with TS
STORE_POP       (0x28): STORE ARG + POP
LOAD            (0x29): Lookup SymTable[ARG] in env & push
ADD             (0x30): TS := TS1 + TS
SUB             (0x31): TS := TS1 - TS
MUL             (0x32): TS := TS1 * TS
DIV             (0x33): TS := TS1 / TS
POW             (0x34): TS := TS1 ** TS
MOD             (0x35): TS := TS1 % TS
BIT_OR          (0x36): TS := TS1 | TS
BIT_AND         (0x37): TS := TS1 & TS
BIT_XOR         (0x38): TS := TS1 ^ TS
LSHIFT          (0x39): TS := TS1 << TS
RSHIFT          (0x3a): TS := TS1 >> TS
UNARY_MINUS     (0x40): TS := -TS

Un exemple de création de segment de code (un compilateur devrait tout à fait pouvoir utiliser cet objet CodeWriter) :

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

>>> from pulp import bytecode
>>> writer = bytecode.CodeWriter()
>>> writer.put(bytecode.LOAD_CONST, 40)
>>> writer.put(bytecode.LOAD_CONST, 2)
>>> writer.put(bytecode.ADD)
>>> writer.put(bytecode.LET_POP, 'foo')
>>> writer.put(bytecode.LOAD_CONST, 2)
>>> writer.put(bytecode.LOAD, 'foo')
>>> writer.put(bytecode.MUL)
>>> writer.put(bytecode.LET_POP, 'bar')
>>> writer.to_bytes()
b'\x02\x00\x03foo\x03bar\x02\x00\x01(\x00\x00\x00\x00\x00\x00\x00\x01\x02\x00\x00\x00\x00\x00\x00\x00\n\x00\x00\n\x01\x000&\x00\x00\n\x01\x00)\x00\x002&\x01\x00'
>>> writer.symbols
['foo', 'bar']
>>> writer.consts
[40, 2]
>>> writer.code
bytearray(b'\n\x00\x00\n\x01\x000&\x00\x00\n\x01\x00)\x00\x002&\x01\x00')

Un petit coup de désassemblage ?

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

>>> idx = 0
>>> bc = writer.code
>>> while idx < len(bc):
...     op = bytecode.OPS_BY_CODE[bc[idx]]
...     idx += 1
...     if not op.arg_type:   # pas d'argument
...         print(op.name)
...         continue
...     if op.arg_type == bytecode.CONST:
...         c = int.from_bytes(bc[idx:idx+2], 'little')
...         print('{:<20s}{:>5d} ({})'.format(op.name, c, writer.consts[c]))
...     if op.arg_type == bytecode.SYMBOL:
...         s = int.from_bytes(bc[idx:idx+2], 'little')
...         print('{:<20s}{:>5d} ({})'.format(op.name, s, writer.symbols[s]))
...     idx += 2
... 
LOAD_CONST              0 (40)
LOAD_CONST              1 (2)
ADD
LET_POP                 0 (foo)
LOAD_CONST              1 (2)
LOAD                    0 (foo)
MUL
LET_POP                 1 (bar)

Salut,

C'est stylé, mais y a juste un truc que j'ai pas compris dans ton bytecode: Quand tu écris TS := TS1 + TS, ça veut dire que le résultat de l'addition est poussé en tant que nouvel élément de la pile, ou bien que le dernier élément de la pile est ajouté l'élément précédent (sans pousser la pile du tout) ?

En gros si j'ai

1
2
3

LOAD_CONST 0  (40)
LOAD_CONST 1  (2)
ADD

À la fin ma pile sera [40, 2, 42] ou [40, 42] ?

Edit: en fait y'a une troisième possibilité, ça peut faire juste [42] à la fin si on considère que ADD pop TS et TS1.