Pulp, un environnement d'exécution multivitaminé

Super ! Est-ce le moment d'ouvrir un dépôt git ?

@AlphaZeta, à la fin de ton opération, la pile vaut [42].

TS := TS + TS1 veut dire "je POP TS, je POP TS1, j'additionne les deux et je PUSH le résultat".

Toutes les opérations (à part LET et STORE qui ont un pendant LET_POP et STORE_POP) font des POP. C'est le principe d'une calculette polonaise : les expressions sont réduites de cette façon.

@mehdidou: why not, si j'ai un peu de temps dans la journée.

Toutes les opérations (à part LET et STORE qui ont un pendant LET_POP et STORE_POP) font des POP. C'est le principe d'une calculette polonaise : les expressions sont réduites de cette façon.

En fait vu qu'on a une instruction DUP_TOP, cette distinction particulière n'est même pas utile (en temps normal ça permet de faire des optimisations de bytecode, mais il est de toute façon trop tôt pour y penser), donc je viens d'uniformiser. LET et STORE se comportent maintenant comme tout le monde en pop-ant les valeurs qu'ils utilisent de la stack, et les opcodes LET_POP et STORE_POP disparaissent.

À moins que j’aie de la merde dans les yeux, il n’a jamais été question d’environnement dans ce que tu as décrit jusqu’à présent, et pourtant, cela apparaît dans ces instructions comme si cela allait de soi. Alors, de quoi s’agit-il ? Comment c’est censé marcher ? Etc.

Je crois que c'est la première éventualité.

Damned ! Je n’avais pas relu le sujet avant la première définition du bytecode…

Juste une remarque dans le nom des instructions. Quand on parle de machine à pile en général, la terminologie c'est POP PUSH, or là, si j'ai bien compris tu utilises plutôt POP STORE. C'est voulu ?

STORE assigne le haut-de-pile à un identifiant et le pop, ça fait pas la même chose que POP, qui se contente juste de l'enlever.

On pourrait mettre PUSH à la place de LOAD_CONST. Mais pas à la place de LOAD tout court qui est une opération plus coûteuse AMHA.

Ok, mais ce que je voulais dire c'est que les noms d'instructions sont étranges du coup… Car on peut voir le LOAD_CONST comme un PUSH et NEW_ENV comme un PUSH_ENV.

Edit : grilled

P.S.

Aussi pourquoi ne pas avoir dans une première version un jeu d'instructions minimale, et voir ensuite pour rajouter plus d'instructions comme LET_POP, ROT2 (qui doit se recoder à partir des opérations binaires) etc… ?

Bonjour,

Je vous suis depuis un petit moment sur ces ateliers mini-langages, et je crois que vous m'avez convaincu d'une chose avec ce topic: mieux vaut commencer par la VM que de s'embourber avec le parsing. En tout cas c'est sur le parsing que je me suis déjà cassé les dents plusieurs fois, et du coup j'ai bien envie de partir sur une VM en premier, pour mon prochain essai de mini-langage.

Par contre j'ai plusieurs questions :

Question n°1: A quoi ça sert d'avoir des tables de constantes et de symboles ? Quel avantage cela nous procure par rapport à encoder directement les données dans le bytecode ?

Par exemple, si on suppose que l'opcode LOAD CONST = 0xA0, pourquoi ne pas faire directement ceci pour charger la valeur 200 :
A0 00 00 00 C8
Au lieu de
A0 01, en supposant que la constante 00 00 00 C8 se trouve dans le slot 01 de la table des constantes ?

Est-ce que l'intérêt est uniquement de gagner de la place au cas où on utilise beaucoup de constantes / plusieurs fois la même constante, ou est-ce que ça cache autre chose de plus intéressant ? Ou bien c'est juste « parce que CPython fait comme ça » ?

Pour la table des symboles, quel est son intérêt si on admet que notre mini-langage possède maintenant un type string, et des instructions du type
LOAD CONST "Hello"
STORE "myvar"
équivalent à une expression myvar = "Hello"; évidemment

Là encore ce ne serait qu'une question de place ?

Question n°2: je pige plus ou moins le truc avec les environnements qu'on va empiler et dépiler quand on entre/sort d'une fonction; l'environnement stockera en gros les variables locales. Mais alors comment ça va marcher pour les closures ? Chaque function va avoir un environnement privé qui n'est pas remis à zéro à chaque nouvel appel ? Comment cet environnement privé va être capturé ? IL va donc falloir que chaque environnement possède une référence vers son environnement parent (au cas où les closures s'empilent) ?

Question n°3: Je vois dans votre liste d'instructions l'opcode ROT_2, qui sert à intervertir les deux éléments au sommet de la pile. A priori ça me semble effectivement assez utile. Par contre à quoi va servir ROT_3 qui permute les trois premiers éléments de la pile ? JE n'arrive pas à imaginer d'utilité concrète.

Question n°4, plus générale: pourquoi avoir choisi une VM à pile plutôt qu'une VM à registres ? Est-ce que c'est beaucoup plus simple à implémenter ? Ma première intuition me répond oui, mais je ne n'en suis pas certain, y-a-til d'autres critères qui ont mené à ce choix ?

@Saroupille : j'ai codé celles dont j'anticipe qu'elles serviront. Sinon pour les noms, si tu veux, ça ne coûte rien à changer pour l'instant.

Simplement pour moi un push est censé prendre un argument, donc je suis mal à l'aise à l'idée d'un PUSH_ENV sans argument.

@Quentin : l'intérêt c'est de garantir que les arguments prennent une place fixe dans le bytecode, et également d'éviter les duplications (si tu crées une variable c'est pour la réutiliser plus tard, autant stocker son nom une seule fois dans le code object). Idem pour les constantes (le nom est peut-être mal choisi, on devrait sûrement parler de valeurs statiques) qui ne seront pas toujours gratuites comme un i64 à désérialiser : si la valeur à manipuler est une fonction imbriquée par exemple… C'est utile aussi parce que la plage d'adresses pour l'instruction pointer est limitée par la taille du bytecode. Et il faut voir enfin que l'on va vouloir faire des jumps dans le code : dans ce cas, avoir une taille prédictible en fonction de la seule nature des opcodes n'est pas du luxe.

Question n°2 : pas encore d'actualité, mais en effet dans mon idée une closure n'est rien de plus qu'une fonction qui référence un environnement extérieur, qui peu lui-même, par construction, n'être accessible qu'à elle lors de son exécution.

Question n°3 : ces deux instructions vont servir lorsque le bytecode passera par un optimiseur pinhole, pour effectuer des opérations en tirant parti de la pile le plus judicieusement possible. Je n'ai pas de cas trivial qui me vienne immédiatement à l'esprit, mais j'ai souvenir de l'avoir déjà utilisé dans des cas qui n'avaient rien d'exotiques.

Question n°4 : oui ça me semble beaucoup plus intuitif. Non seulement à implémenter mais aussi à manipuler mentalement comme cible d'un compilateur.

PS : Un exemple simpliste pour ROT_3

1
2

foo = 42
bar[baz] = foo

Code de base :

1
2
3
4
5
6

LOAD_CONST (42)  => [42]
LET (foo)  => []
LOAD (bar)   => [bar]
LOAD (baz)   => [bar, baz]
LOAD (foo)   => [bar, baz, foo=42]  
STORE_KEY  # TS2[TS1] = TS

Un optimiseur pinhole pourrait faire ceci :

1
2
3
4
5
6
7

LOAD_CONST (42)  => [42]
DUP_TOP  => [42, 42]
LET (foo)  => [42]
LOAD (bar)  => [42, bar]
LOAD (baz)  => [42, bar, baz]
ROT_3  => [bar, baz, 42]
STORE_KEY

Sachant que DUP_TOP et ROT_3 peuvent être implémentées pour être beaucoup, beaucoup plus rapides qu'un LOAD.

J'ai créé le repo. Manifestez-vous si vous voulez le droit de commiter dessus directement, même si je préfère généralement les pull requests.

https://github.com/ArnaudCalmettes/pulp

Je suis en train d’écrire un interpréteur PULP, et j’aurais une question : lorsqu’on a plusieurs segments de code, comment décide-t-on lesquels doivent être exécutés et dans quel ordre ?

Je n'y ai pas encore réfléchi. Il faut trouver une meilleure convention pour gérer plusieurs niveaux de code. Typiquement dans Parrot ils ajoutent un segment "Directory" qui liste les autres segments. On pourrait faire comme ça et définir un segment "main" obligatoire.

Dans Python c'est un peu le même fonctionnement je pense, même si pour une fois je connais plus en détail ce qu'on font les autres que Python.

Attention, petite incohérence détectée !

Dans la spec, on a ceci.

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)

Mais dans ton code d’exemple, on a ceci.

1	0x25 0x00 (size: 37 octets) <--- début du segment

La taille n’est codée que sur 2 octets. A priori, ce serait suicidaire de garder une taille de segments sur 2 octets, donc j’ai rétabli à 4 dans mon code. Il faut donc remplacer la ligne précédente par ceci.

1	0x27 0x00 0x00 0x00 (size: 39 octets) <--- début du segment

Double post, parce que.

À l’usage, j’aurais un peu quelque chose à redire concernant les headers des différentes sections d’un segment de code. Chacun contient un champ « taille » sur 2 octets. Mais pour les deux premiers, cela compte le nombre d’entrées dans la table, alors que pour le troisième, cela compte le nombre d’octets.

Or, il s’avère que la première manière de compter rend le parsing beaucoup plus simple, tandis que la seconde rend la détection de bytecode invalide beaucoup plus simple. Du coup, même si ça fait un peu doublon, je serais partisan de mettre les deux à chaque fois.

Qu’en dites-vous ?

Tu as raison pour la taille du segment. C'est censé être sur 32 bits. Je vais corriger tout ça. Il faut que je vérifie dans mon code également.

Pour ta seconde remarque, tu veux dire mettre deux compteurs dans le segment juste avant le code (nombre d'octets, nombre d'opcodes) ? Et généraliser ça aux tables également ?

Si oui, je n'y vois aucun inconvénient.

Oui, je parle bien de ça. On aurait…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Code:
    size (2 octets, longueur en octets du code)
    count (2 octets, nombre d'opcodes)
    Opcode*

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

ConstTable:
    size (2 octets, longueur en octets de la table)
    count (2 octets, nombre de constantes)
    Constant* (les constantes)

Vendu !

J'en prends compte dans la spec que je vais versionner (ASAP… Je suis très chargé cette semaine).