Pulp, un environnement d'exécution multivitaminé

QuentinC : je ne suis pas sûr de comprendre ce que tu veux dire, mais la difficulté avec les fermetures, ce n'est pas de gérer des fonctions imbriquées (ça c'est très facile), mais de gérer le fait qu'une fonction capture l'environnement courant quand elle est définie.

Tu te doutes bien que j’ai déjà lu cette page.

La question que je pose, c’est de savoir s’il est vraiment utile de généraliser ce fonctionnement assez particulier (et lourd) à toutes les fonctions sans exception. Je veux dire, on peut écrire un OS entier sans jamais faire appel à une seule fermeture, alors pourquoi remplacer un système simple (un saut à une adresse, en conservant en mémoire le point d’appel) par un système compliqué, et ce de manière systématique ? C’est de ça que je veux qu’on essaye de me convaincre.

Que c’est une très mauvaise idée.

L’intérêt d’une fonction, c’est de pouvoir être appelée depuis plusieurs endroits, donc n’avoir qu’une seule fonction parente serait un contresens. Et du coup, on n’aurait pas qu’une seule fonction ayant NULL comme fonction parente : la quasi-totalité des fonctions seraient dans ce cas.

https://fr.m.wikipedia.org/wiki/Fermeture_(informatique)

Ça se voit certes moins dans un langage comme haskell où on cache la mutabilité sous le tapis, mais dans un langage comme OCaml, c'est très répandu comme pattern (l'exemple typique, c'est générer des id entiers uniques).

Après, gérer les fermetures ou pas, c'est un choix à faire. C'est incontestablement plus compliqué, mais ça permet d'écrire des choses rigolotes. Si vous voulez faire une bonne cible pour un langage fonctionnel, c'est probablement un choix à considérer sérieusement.

Tu te doutes bien que j’ai déjà lu cette page.

La question que je pose, c’est de savoir s’il est vraiment utile de généraliser ce fonctionnement assez particulier (et lourd) à toutes les fonctions sans exception. Je veux dire, on peut écrire un OS entier sans jamais faire appel à une seule fermeture, alors pourquoi remplacer un système simple (un saut à une adresse, en conservant en mémoire le point d’appel) par un système compliqué, et ce de manière systématique ? C’est de ça que je veux qu’on essaye de me convaincre.

Rien n'empêche d'avoir les deux : pour la partie « simple », il suffit d'une instruction de saut inconditionnel tout ce qu'il y a de plus basique. Pour conserver en mémoire le point d'appel, on l'empile avant et on le dépile après : pas besoin d'instruction supplémentaire. On peut imaginer des raccourcis (à la leave/ret), mais on peut aussi partir au plus simple et considérer que c'est au compilateur du langage haut niveau de générer les instructions qui vont bien.

On peut aussi proposer (comme le présente Xavier Leroy ici) une instruction du style Closure(code) qui pousse sur la pile la paire (code, environnement courant). Les instructions Apply et Return se chargent alors de charger les codes et environnement qui vont bien.

Finalement, la différence, c'est qu'au lieu de considérer des fonctions comme « du code à exécuter », on considère des paires « code, environnement » (et de fait, les instructions précédentes correspondent un peu aux versions liftées des opérations simples).

Du coup j'ai l'impression (corrige-moi si je me trompe) que ta question est « est-ce que vraiment on a besoin que ces opérations gèrent l'environnement ? ». Mon avis est que, s'il s'agit simplement de sauter entre des code pointer, vous n'avez même pas besoin de fournir ce genre d'instruction. Du coup, si vous voulez faire une « machine virtuelle fonctionnelle », autant proposer de gérer les fermetures — et laisser le langage haut-niveau décider des fonctions qui peuvent être compilées avec des sauts simples. Vous pouvez aussi décider d'oublier le fonctionnel à votre niveau et de laisser le langage haut-niveau se débrouiller pour compiler ses fermetures lui-même. Dans tous les cas, c'est en bonus : rien n'empêche de le rajouter plus tard sans rien changer, par exemple.

J'ai l'impression qu'il parlait de « fonction parente » au sens syntaxique. Par exemple, dans le code suivant, counter est la fonction parente de c.

1
2
3
4
5
6
7

def counter():
    n = 0
    def c():
        nonlocal n
        n += 1
        return n
    return c

Mais même dans ce cas, se contenter de dire « on regarde la fonction parente pour connaître l'environnement » ne suffit pas :

1
2
3
4
5
6
7
8

>>> a = counter()
>>> b = counter()
>>> a()
1
>>> a()
2
>>> b()
1

a et b ne partagent pas le même environnement. Attention à ne pas confondre scope et environnement : le premier désigne la portée des variables, c'est une notion syntaxique (cc nohar ) qui indique quelles sont les variables définies à un endroit donné du programme. Ici, on parle de variable, pas de symbole : deux variables différentes peuvent avoir le même nom si elles ont des portées disjointes (par exemple, deux fonctions qui n'ont rien à voir peuvent utiliser deux variables locales x). L'environnement est une notion dynamique : à un certain point d'exécution, c'est une table qui associe une valeur à chaque symbole d'une variable définie à cet endroit.

Par exemple, dans l'exemple précédent, au moment où j'appelle a() et b(), les environnements sont différents (la preuve : la même instruction return n me renvoie une valeur différente). Pour autant, syntaxiquement, on ne voit aucune différence : la variable n n'est déclarée qu'à un seul endroit et sa portée couvre la fonction c qui elle-même est unique.

Du coup, si vous voulez faire une « machine virtuelle fonctionnelle », autant proposer de gérer les fermetures — et laisser le langage haut-niveau décider des fonctions qui peuvent être compilées avec des sauts simples.

C’est exactement ça que je suggère : donner la possibilité de faire des fermetures (pas forcément tout de suite tout de suite, mais à terme certainement), sans pour autant en faire le fonctionnement général. Des tas de fonctions peuvent être gérées par un simple call.

Ça me paraît être un bon plan. Un avis esthétique totalement personnel toutefois : si vous prévoyez à terme de gérer les fermetures, je vous suggère de garder call pour le futur et d'utiliser simplement une combinaison de sauts (jmp ?) et de push pour gérer les fonctions pour l'instant (au lieu de définir un call qui combine les deux).

Tel que c’est prévu, un call serait plus que des push et un saut. Il s’agirait aussi de poper certaines valeurs de la pile, de les ajouter à un nouveau scope, et de créer une nouvelle pile vide dédiée à la fonction appelée. Du coup, je pense que c’est quand même plus simple d’avoir une instruction dédiée.

Il s’agirait aussi de poper certaines valeurs de la pile, de les ajouter à un nouveau scope

J'imagine que tu parles des paramètres. Si oui, je ne pense pas que ce soit nécessaire : si une fonction haut-niveau f a pour paramètres a et b, en code-objet, ça peut simplement se traduire par POP a; POP b au début de la fonction. Ce n'est pas tellement plus cher que ce que vous pourriez obtenir en essayant de designer le call qui va bien (j'ai lu rapidement des choses qui avaient l'air un peu tordues pour les fonctions à plusieurs paramètres ?). Pour appeler une fonction, il suffit donc d'empiler le code pointer, les arguments dans l'ordre qui va bien, et de faire un jump. À la fin de la fonction appelée, deux instructions se chargent de dépiler le code pointer précédemment empilé par la fonction appelante et de jumper dessus.

et de créer une nouvelle pile vide dédiée à la fonction appelée.

Je ne comprends pas pourquoi il faudrait créer une nouvelle pile : il suffit d'empiler ce dont on a besoin sur la pile en cours, et de dépiler ensuite. C'est tout ce qu'il y a de plus classique en compilation : chaque fonction crée un « cadre de pile » qui lui est propre, c'est-à-dire empile des données dont elle a besoin. Une fois l'exécution de la fonction terminée, ces données sont dépilées et on revient à l'état de la pile avant l'appel de la fonction.

Par exemple, le code suivant :

1
2
3
4
5
6

def f(x):
    return 2 * x

def g(y):
    a = 3
    return a + f(y)

pourrait se compiler de la manière suivante ¹ :

 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
30

Segment f:
# Récupération du code pointer de retour
POP code_pointer_retour
# Récupération des paramètres
POP x
# Corps de la fonction
PUSH 2
PUSH x
ADD
# Retour : restauration de l'état avant appel
JMP code_pointer_retour

Segment g:
POP code_pointer_retour
# Récupération des paramètres
POP y
# Corps de la fonction
STORE a 3
PUSH a
## Appel de f
PUSH y
PUSH(code_pointer courant + 1)
JMP f
## f retourne ici : la valeur de retour est sur la pile
ADD
POP valeur_retour_g
# Retour : restauration de l'état avant appel
POP _a
PUSH valeur_retour_g
JMP code_pointer_retour

Est-ce que ça vaut le coup de proposer des instructions qui en regroupent deux ou trois ? Dans un premier temps, je ne pense pas : c'est préférable de travailler avec les appels explicites, d'abord parce que ça fait ça de moins à implémenter (et à maintenir !), et ensuite parce que pédagogiquement ça permet de mieux comprendre comment ça marche (à la fois pour ceux qui travaillent sur la VM et ceux qui voudraient la cibler dans leur compilateur).

J'ai l'impression qu'il parlait de « fonction parente » au sens syntaxique. Par exemple, dans le code suivant, counter est la fonction parente de c.

C'était exactement ça.

Par contre effectivement vous avez raison, ça ne suffit pas de prendre l'environnement de la fonction parente. En fait il faut intercaler l'environnement local.

J'ai du mal à exprimer mes pensées, mais je vais essayer en reprenant l'exemple :

1. Appelons P1 l'environnement parent de counter, établi à la création de la fonction. Pour faire simple on va dire qu'une fonction est définie par son code et son environnement parent, et qu'un environnement possède une référence vers un environnement parent.
2. ON fait a = counter(). A ce moment-là, on créer un nouvel environnement, appelons-le L1 (L comme local), ça devient l'environnement courant et la fonction commence à s'exécuter. A ce moment-là la pile des environnements est L1>P1.
3. On return c. Ca implique de faire une copie de l'objet fonction qui contient le même code que c, mais qui bind l'environnement local courant. Donc la variable a de a = counter() va contenir un objet fonction qui a pour environnement parent L1>P1.
4. ON fait b = counter(), la variable b va contir un objet fonction qui contient toujours le code de c mais avec l'environnement parent L2>P1 sur le même principe que les étapes 2-3.
5. ON appelle a(). ON crée un nouvel environnement local M (M parce que ça suit L, désolé, j'ai pas mieux). La pile des environnements au début de l'exécution de la fonction a doit être M1>L1>P1.
6. Les instructions de la fonction sont en gros LOAD n; PUSH 1; ADD; DUP; STORE n; RETURN. Vu que n n'existe pas dans M1, on va le chercher dans L1 (je n'aborde volontairement pas les questions de scope ici, celle de JavaScript me paraît plus logique que celle de python car on est ici obligé d'utiliser un mot-clé mystique nonlocal, mais c'est une question de goût et de ce qu'on veut donner comme sens au langage; on n'en est pas là)
7. On rappelle une deuxième fois a(). n n'existe pas dans l'environnement local M2 qu'on a créé, on va de nouveau la chercher dans L1 qui n'a pas bougé. ON obtient bien le résultat attendu, c'est toujours la même variable qui est incrémentée.
8. Quand on appelle b(), ON crée M3 dont le parent est L2. Donc c'est une autre instance de la variable n qui est incrémentée. Tout va bien !

Là où je m'enbrouille et que je ne vois franchement pas que faire, c'est la dualité entre objet fonction en cours d'exécution ou capturé qui a un environnement bien défini, et un objet fonction qui est déjà compilé / bytecode chargé mais avec environnement pas encore vraiment défini vu qu'elle n'est pas encore exécutée ou référencée; et surtout comment et quand attribuer un environnement à un objet fonction pour que ça soit correct. C'est là que doit être le noeud du problème, probablement.

JE pense que vous n'avez pas dû comprendre grand chose à mes explications hasardeuse, je m'en excuse… ce n'est pas évident à conceptualiser.

Je ressuscite le sujet.

Bien qu'hyper chargé en ce moment, j'ai un peu bossé sur le sujet (ceux qui me connaissent bien verront qu'il n'y a que les idiots qui ne changent pas d'avis) :

• J'ai laissé tomber l'idée de coder une VM en Rust. Ce langage ne m'amuse clairement pas assez pour que j'aie envie de me former dessus sur mon temps libre. Sur le papier c'est sûrement un excellent langage, mais le prix du ticket d'entrée est absolument rédhibitoire pour une pratique en dilettante.

• Je me suis donc tourné vers mon langage candidat numéro 2, et ai démarré l'implémentation d'une VM en Go, que je publierai bientôt sous le nom de goyave. J'accroche bien avec Go. Les premiers resultats des benches sur ma stack montrent un facteur 1000 en perfs par rapport à Python. Et je suis certain qu'il y a des trucs cools à faire sur la vm en tirant parti de son modèle de concurrence.

Niveau spec, je préfère faire des expérimentations et avoir un truc qui marche avant de le rétro-spécifier. En particulier je compte développer un mini-langage de test pour ma VM, et si je dois passer du temps en même temps à attendre des consensus, vu mon peu de temps libre dispo en ce moment, je j'aboutirai à rien. Je vous propose donc d'en faire de même. Comme ça on pourra se piquer des idées les uns aux autres.

Sur le papier c'est sûrement un excellent langage, mais le prix du ticket d'entrée est absolument rédhibitoire pour une pratique en dilettante.

Ah ? Je sais que c’est un peu HS, mais si tu as un peu de temps, tu saurais m’expliquer ce qui te fait dire ça ?

Je vous propose donc d'en faire de même. Comme ça on pourra se piquer des idées les uns aux autres.

Génial ! On va bien rigoler…

Je pense que c'est une question de profil, ou d'inclinaison personnelle.

En fait, quitte à apprendre un nouveau langage, j'ai vraiment la volonté dès de départ de coder en respectant les idiomes du langage. Le problème avec Rust, c'est qu'il apporte au développeur un jeu de contraintes avec lesquelles il n'est pas immédiatement facile de raisonner (les règles sur la mutabilité des références, et l'emprunt, pour ne citer que ces deux là). En soi, je comprends parfaitement la sécurité que cela peut apporter sur des programmes sérieux, et c'est d'ailleurs la raison pour laquelle on a déjà parlé de l'utiliser sur des projets au boulot, mais ça demande un effort et un apprentissage coûteux en temps.

Le problème, c'est que hors du travail, je n'ai pas envie de me prendre la tête comme si j'étais au bureau. En particulier, je ne veux pas avoir à perdre des heures sur un bout de programme dont la conception est déjà évidente dans ma tête. Au contraire, sur mon temps libre, j'ai besoin de m'amuser, et de m'amuser rapidement parce que je n'ai pas plusieurs heures d'affilée à passer dessus.

Avec Go, en comparaison, ça a été le cas. En deux heures j'avais acquis les bases du langage (parce qu'il est assez immédiat à prendre en main, surtout quand on connaît déjà C et Python dont il est une sorte de juste milieu), suffisamment pour avoir codé un petit programme concurrent pour piger la façon dont fonctionnent les goroutines, les canaux et la structure select (les trois éléments typiques de Go) et en deux heures de plus, j'avais développé mon premier objet, ses tests unitaires et même quelques petites fonctions de benchmark en me servant du module natif testing (tout en ayant lu des kilomètres d'une documentation très fournie et de bonne qualité).

Au final, je n'ai rien à reprocher à Rust, au contraire, et j'y reviendrai sûrement à l'avenir. C'est juste que je le trouve pas assez marrant pour continuer à faire l'effort de l'apprendre en ce moment.

D’accord, je comprends tout à fait ce que tu veux dire. Pour la bonne et simple raison que ce que tu as ressenti vis-à-vis de Go, je l’ai ressenti vis-à-vis de Rust : la plupart des concepts un peu « haut niveau » sont présents en Haskell, et la marche d’apprentissage s’est, pour moi, largement réduite aux différentes sortes de passage par référence (et à ces saloperies de macro…). Du coup, j’ai pu très vite m’amuser avec le langage.

Petit test complètement innocent, pour me faire une idée de la façon dont les maps sont implémentés en Go et pour savoir dans quoi j'allais stocker mes opcodes pour dispatcher lors de l'exécution (un mapping byte -> opcode, ou bien un tableau de 256 opcodes). À la réflexion je dois être un peu fatigué pour me poser ce genre de questions dont la réponse semble évidente après coup, mais le test en lui-même a le mérite d'être sans appel :

 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
30
31

package bytecode_test

import (
    "testing"
)

var oparray [256]int
var opmap map[byte]int

func init() {
    var b byte
    var i int
    opmap = make(map[byte]int)

    for i, b = 0, 0; i < 256; i, b = i+1, b+1 {
        oparray[b] = i
        opmap[b] = i
    }
}

func BenchmarkLookupByteMap(b *testing.B) {
    for i, key := 0, byte(0); i < b.N; i, key = i+1, key+1 {
        _ = opmap[key]
    }
}

func BenchmarkLookupArray(b *testing.B) {
    for i, key := 0, byte(0); i < b.N; i, key = i+1, key+1 {
        _ = oparray[key]
    }
}

Le résultat :

1
2

BenchmarkLookupByteMap-4        50000000                35.4 ns/op
BenchmarkLookupArray-4          2000000000               0.91 ns/op

… au moins c'est clair ! J'en déduis également, vu la différence, que les mappings de Go ne sont probablement pas des tables de hachage, mais plutôt des arbres.

(Mon objectif secret sur ce projet, c'est de réussir à faire une VM et un langage dynamique qui mettent un bon x10 dans la tronche de Python. Vu mes tests jusqu'à maintenant, ça semble très jouable ! Pour comparaison, une opération de base en Python se compte en µs.)

J'en déduis également, vu la différence, que les mappings de Go ne sont probablement pas des tables de hachage, mais plutôt des arbres.

Non, ce sont bien des hashtables : https://golang.org/src/runtime/hashmap.go

Au temps pour moi dans ce cas. Du coup le résultat de mon test est intéressant puisque la table utilise des hashes sur 8 bits et que mes clés sont précisément des octets, on se rend compte que l'overhead de la recherche dans un map représente 30 bonnes nanosecondes.

À l'échelle d'une VM il y a de bonnes chances que ça joue, quand on voit qu'un push ou un pop sur la stack est de l'ordre de 5 à 10ns.

Ou alors ces considérations seront rendues caduques à cause de la force de friction que représente la détection des erreurs… Je n'ai pas encore assez avancé pour le savoir.

Si je pouvais obtenir un let a = 42 qui soit aux alentours de 100ns je serais content en fait.

PS : Malgré le.peu de progrès visibles sur mon code, j'ai déjà commencé à réfléchir à pas mal de sujets, comme la façon dont j'implémenterais la concurrence pour rendre la VM compatible avec le parallélisme tout en restant threadsafe, et sans GIL.

Je suis de retour de vacances, je vais donc pouvoir bosser à fond sur le projet dans les semaines qui suivent et je vais rentrer en MPSI dans une semaine.

J'essaierai tout de même de suivre le projet et d'y participer dans la mesure du possible.

Hello tout le monde !

Je déterre un peu le sujet, mais je m'y suis intéressé récemment et je me suis lancé dans la création d'un compilateur (en Vala, forcement ). Pour le moment j'utilise une syntaxe personnelle, pas Seventh ou Acid, mais peut être que ça changera dans le futur.

La seule chose qu'on peut compiler pour le moment est l'addition de deux entiers, avec la commande pulpc fichier.pulp -o sortie (oui, j'ai pris pulpc comme nom et l'extension .pulp pour les fichiers source, même si ça ne veut pas dire grand chose).

J'ai aussi mis à jour la spec avec ce qui a été dit ici. Vous pouvez retrouver la nouvelle version ici. Je ferai sûrement une PR pour que tout ça soit intégré dans le dépôt de nohar.

Par contre j'ai une petite question : le timestamp dans l'entête du fichier ne devrait pas être sur 8 octets au lieu de 4 ? Sinon, en 2038 on risque d'avoir des problèmes non ? Si il reste des gens qui utilisent encore pulp à ce moment.