Réecriture des mécanismes avec un petit nombre de mécanisme de base

[johangirod]

Dans la lignée de ce qui a été discuté dans #6 et un peu partout sur les différentes issues liées au la formalisation de publicode, je propose de définir un certains nombre de mécanisme "brique de base" avec lesquels tous les mécanismes "dérivés" serait réecrit.

Je vois pour l'instant les mécanismes de base suivants :

• Opération binaire (+, -, /, ×, <, >, =, ≤, ≥, !=, et, ou)
• Variation ternaire (si a alors b sinon c)
• Par défaut
• Unité
• Nom (affectation d'une valeur en tant que règle)

Tous les autres mécanisme doivent pouvoir être implémenté comme une réécriture d'une expression avec ces mécanismes de base, autrement dit, du sucre syntaxique. C'est déjà le cas de composante dans betagouv/mon-entreprise#1191.

Voici ce que cela donnerait les transformations statiques. Les réecritures sont en javascript. L'objet v correspond à l'objet yaml sous le nom du mécanisme

Plafond

`
variations:
 si: ${v.plafond} != non ET ${v.valeur} > ${v.plafond}
 alors:  ${v.plafond}
 sinon: ${v.valeur}
`

Applicable si

`
variations:
  si: ${v.condition} != non
  alors: ${v.valeur}
  sinon: non
`

Produit

`
operation ×:
   - valeur: ${v.assiette}
     plafond: ${v.plafond ?? 'non'}
   - operation ×:
       - ${taux ?? '100%'}
       - ${facteur ?? '1'}
`

Somme

v.reduce((somme, terme) => `
operation +:
  - ${terme}
  - ${somme}
`, '0')

Variations

v.reduce((variations, terme ) => `
variation:
  si: ${terme.si}
  alors: ${terme.alors}
  sinon: ${variations}
`, 'non')

Grille

`
variations:
  ${v.tranches.map(t => `
  - si: ${v.assiette} × $[v.multiplicateur} <= ${t.plafond}
    alors: ${t.valeur}
`).join('\n')}
 

Barème

`
somme:
  ${v.tranches.map(t => `
  - produit:
      assiette: ${v.assiette}  - ${v.plancher}
      plafond: ${v.plancher} - ${v.plafond}
      taux: ${v.taux}
`).join('\n')}

...etc.

Avantages

L'utilisation d'un nombre limité de mécanisme de base a le gros avantage de réduire le périmètre du langage publicode "core". Cela veut dire limiter les implémentations de l'inférence de type et de l'évaluation (avec la logique des missings, ou des variables temporelles) a un petit nombre de mécanisme.

Les gros mécanisme étant définis comme une combinaison de petit mécanisme, ils héritent des propriétés du langage sans que l'on ait à les réimplémenter. Cela permet d'être d'avantage rassuré quand à la validité de l'implémentation des gros mécanisme.

Lien avec les fonctions

Ce principe de gros mécanisme vs petit ressemble au principe des fonctions dans n'importe quel langage. C'est effectivement l'idée. Les gros mécanisme étant en fait des fonctions définie avec des opérations de base. Si on ajoute pas directement cette abstraction dans publicodes, c'est pour deux raisons principales.

1. Cette proposition est une étape intermédiaire et demande donc moins de modifications que l'ajout des fonctions
2. Pour réecrire les mécanisme de barème et somme sous forme de fonction publicode, il faudrait ajouter l'abstraction des listes, qui n'existe pas encore

Mais il est encouragé de considérer les gros mécanisme comme une fonction.

Considération sur les performance :

On voit ici que cette réecriture peut être couteuse en terme de performance. Par exemple, la réecriture du mécanisme plafond :

`
variations:
 si: ${v.plafond} != non ET ${v.valeur} > ${v.plafond}
 alors:  ${v.plafond}
 sinon: ${v.valeur}
`

revient à évaluer l'expression v.plafond trois fois de suite. C'est beaucoup, surtout si c'est une expression compliquée, avec des inversions dedans par exemple.

Je propose d'ajouter un nouveau mécanisme permettant de spécifier lorsque que des valeurs sont les même : cache. On aurait ici :

const plafond = `
valeur: ${plafond}
cache: ${new uuid()}
`;
const valeur = `
valeur: ${valeur}
cache: ${new uuid()}
`;
`
variations:
 si: ${plafond} != non ET ${valeur} > ${plafond}
 alors:  ${plafond}
 sinon: ${valeur}
`

Lors de l'évaluation ou lors de la vérification de type, c'est une valeur cachée qui serait utilisée.

Mécanisme intermédiaires

Certains mécanismes ne peuvent pas être réecrit via des mécanismes de base sans pour autant en faire parti. C'est le cas de inversion, recalcul ou encore synchronisation

Il doivent être définit complètement (évaluation, inférence de type et missing variables), de la même manière que les mécanismes de base. Mais ils n'en font pas parti car on interdit leur utilisation pour l'écriture de gros mécanisme.

Pourquoi ? Principalement parce qu'il ne sont pas aussi 'solide' que ceux si. En attendant de comprendre mieux les enjeux formels qui leurs sont associés, je propose de les mettre de côté.

Visualisations

Tous les mécanismes ont une visualisation spécifique. Les gros mécanisme peuvent ainsi "écraser" la visualisation de leur enfant en définissant une qui leur correspond mieux (et qui est plus simple à comprendre). C'est déjà le cas pour composantes dans betagouv/mon-entreprise#1191

Questions et prochaines étapes

L'AST serait donc composé uniquement de mécanisme de base et intermédiaire. Mais il faudrait qu'il garde la trace des mécanismes avant la réecriture pour l'affichage. Je ne sais pas encore quelle forme cela prendrait. Je pense que le mieux, c'est de commencer avec un mécanisme à réecrire (par exemple produit) et expérimenter un peu sur quelle implémentation marcherait bien.

Qu'en pensez vous ?

Reliée à betagouv/mon-entreprise#1015

[denismerigoux]

Salut, tout ça m'a l'air super ! En fait, ces mécanismes "brique de base" qui permettent de réimplementer tous les autres c'est la base du design des langages de programmation.

La liste que tu fais @johangirod correspond à un langage fonctionnel primitif. Il ne manque plus que les fonctions et on retombe sur un lambda calcul.

Par contre concernant vos soucis de performance, ça me semble bizarre qu'évaluer une même variable plusieurs fois vous pose problème. Pour gérer les variables dans un interpréteur classique, on a une structure de données qu'on appelle un contexte d'exécution, et qui est une map (implémentée par une hash table ou un arbre auto-balançant) dont les clés sont les uuid des variables et les valeurs sont les valeurs de ces variables. L'accès au contexte se fait en O(1) ou en O(log(n)).

Par contre attention pour les variables, le jour où vous rajouterez des fonctions faudra décider si vous faites du call-by-name ou du call-by-value ; en fonction de la stratégie d'évaluation que vous choisissez ça va compliquer votre contexte d'exécution. Pour l'instant, toutes vos variables sont "libres" mais c'est notoirement très casse-gueule de gérer les variables "liées" par des fonctions. Il y a des bonnes pratiques pour ça, dites moi quand vous en serez là et je vous donnerai plus de détail.

[mquandalle]

Bonne idée d'ouvrir un ticket dédié ! Je me concentre sur mes points de désaccord, mais c'est seulement pour faire avancer la discussion, je suis hyper favorable à l'écriture des mécanismes comme une composition de briques de base.

En fait j'ai l'impression que la proposition mélange des choses qui doivent être faites au moment du parsage et d'autres qui doivent être faites au moment de l'évaluation, et qu'il faut clarifier les "briques de base" qui relèvent d'une étape et de l'autre. Par exemple "unité" ou "par défaut" ne sont pas des briques de bases de l'évaluation, "unité" peut-être évalué comme un produit et "par défaut" comme une variation / branchement conditionnel.

De même je pense que ces transformations ne doivent pas être faites dans l'AST serialisable que l'on envoie au client (ce que tu sembles proposer), mais lors du chargement du code dans l’interpréteur. On peut ainsi utiliser des références "natives" de JavaScript, que l'on compare simplement avec node1 === node2, plutôt que d'insérer des uuid dans un attribut "cache". L'utilisation de références native est déjà ce que l'on fait dans l'évaluation aujourd'hui et est utile pour betagouv/mon-entreprise#1259. Pour la généraliser il faudrait néanmoins ajouter une étape load entre le parsage et l'évaluation. L'étape parse donne une description statique et serialisable du code, et le load fait les remplacements en mécanismes de base et utilise des références natives.

Pour gérer les variables dans un interpréteur classique, on a une structure de données qu'on appelle un contexte d'exécution, et qui est une map (implémentée par une hash table ou un arbre auto-balançant) dont les clés sont les uuid des variables et les valeurs sont les valeurs de ces variables. L'accès au contexte se fait en O(1) ou en O(log(n)).

D'accord avec ça, mais vu que interpréteur est exécuté dans une machine virtuelle JavaScript il est plus logique et efficace d'utiliser les objets du langage (qui sont des hashmaps) et des références natives plutôt que de réimplémenter un contexte d'exécution avec des uuid au dessus de la machine virtuelle Javascript. Ça sera pour quand on ré-écrira l'interpréteur publicodes en Rust pour l’exécuter en Webassembly ;)

[denismerigoux]

D'accord avec ça, mais vu que interpréteur est exécuté dans une machine virtuelle JavaScript il est plus logique et efficace d'utiliser les objets du langage (qui sont des hashmaps) et des références natives plutôt que de réimplémenter un contexte d'exécution avec des uuid au dessus de la machine virtuelle Javascript. Ça sera pour quand on ré-écrira l'interpréteur publicodes en Rust pour l’exécuter en Webassembly ;)

La manière dont vous implémentez votre interpréteur actuellement avec de l'état mutable et des comparaisons de références est assez casse-gueule et difficile à débugguer. D'habitude on a deux architecture classiques pour un interpréteur. Le plus simple est d'avoir des AST immutable où l'information sur les variables, etc. est stockée dans l'AST. C'est ce qui permet de moins se tromper dans l'implémentation mais de cette manière, le pattern d'utilisation de la mémoire est une "sea of pointers" ce qui optimise pas beaucoup le cache processeur. L'autre architecture classique est justement de tout faire à base d'uuid et de stocker toutes les informations relatives aux nœuds dans des grands tableaux dont les indices sont justement les uudi. Comme ça, le pattern d'accès mémoire est plus compact, surtout si vous utilisez des tableaux Javascript natifs (Uint8Array, etc.).

C'est cette deuxième architecture qui avait été choisie pour le compilateur sur lequel j'avais travaillé quand j'étais chez Mozilla, Cranelift. Cranelift est écrit en Rust et grâce à ces histoires d'uuid il est super rapide, il va être utilisé comme JIT par Firefox je crois pour le WebAssembly.

Rust est pas un super langage pour écrire des compilateurs/interpréteurs. Je parle d'expérience parce que je suis en train de faire exactement ça en ce moment : https://github.com/hacspec/hacspec. L'absence de GC rend la définition des structures de données pénibles, et on peut pas pattern-matcher très profond avec Box. Avant de réécrire votre interpréteur en Rust vous feriez mieux de le réécrire en OCaml puis de compiler vers JS avec https://github.com/ocsigen/js_of_ocaml/.

[mquandalle]

@johangirod fermé par #217 ?

[johangirod]

En partie. Il manque encore l'implémentation des mécanismes suivants :

• Barème
• Grille
• TauxProgressif
• Variation

Mais je pense qu'il faudra attendre d'avoir un vrai type liste et peut-être même des fonctions native ?

En attendant, on peut fermer cette issue, et en rouvrir une autre plus restreinte sur ces mécanismes restants avec la problématique particulière des listes.