Acid, le lisp-like de la communauté !

Ça me plairait de te donner un coup de main, ça me ferait la main avec Python.

Peut-être un point de convergence avec Seventh ?

Si on peut avoir rapidement un truc fonctionnel je vais essayer de dev quelques chose ce soir si possible.

OK, je comptais partir dessus en Rust à la base, mais va pour ça, lançons un sujet pour écrire une VM avec Python.

Comme tu veux, je ne veux rien t'imposer. J'ai encore de quoi m'occuper avec mon implémentation du langage impératif, donc si tu veux le faire en rust, vas-y.

J'ai essayé d'imaginer un ensemble d'instruction. En gros on aurai ça:

• PUSH_INT <value>: Ajoute un entier au haut de la pile
• LOAD_GLOBAL <id>: Ajoute la valeur de id en haut de la pile
• LOAD_LOCAL <n>: Ajoute le n-ième argument en haut de la pile
• POP: Enlève l'élément en haut de la pile
• APPLY <n>: Applique à l'élément en haut de pile les n éléments précédents
• PROC [<instructions> ...]: Ajoute en haut de la pile une procédure avec les instructions données
• STORE <id>: Assigne à id l'élément en haut de pile

Avec ça on peut traduire du Acid facilement. Si on prend l'exemple suivant:

1
2
3
4
5
6
7

(define foo (lambda (x y)
  (* x (+ y 2))
))

(define main (lambda ()
  (print ((foo 1 2)))
))

… on obtiendrait le bytecode suivant:

 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

INSTRUCTION                     STACK                  LOCAL               ENVIRONMENT

                                []                     []                  {}
PROC [
  LOAD_LOCAL 1                    [x]                  [x, y]                {}
  LOAD_LOCAL 2                    [x, y]               [x, y]                {}
  PUSH_INT 2                      [x, y, 2]            [x, y]                {}
  LOAD_GLOBAL +                   [x, y, 2, +]         [x, y]                {}
  APPLY 2                         [x, (+ y 2)]         [x, y]                {}
  LOAD_GLOBAL *                   [x, (+ y 2), *]      [x, y]                {}
  APPLY 2                         [(* x (+ y 2))]      [x, y]                {}
]                               [<proc>]                                   {}
STORE foo                       [<proc>]                                   {foo: <proc>}
POP                             []                                         {foo: <proc>}
PROC [
  PUSH_INT 1                      [1]                  []                    {foo: <proc>}
  PUSH_INT 2                      [1, 2]               []                    {foo: <proc>}
  LOAD_GLOBAL foo                 [1, 2, foo]          []                    {foo: <proc>}
  APPLY 2                         [(foo 1 2)]          []                    {foo: <proc>}
  LOAD_GLOBAL print               [(foo 1 2), print]   []                    {foo: <proc>}
  APPLY 1                         [(print (foo 1 2))]  []                    {foo: <proc>}
]                               [<proc>]                                   {foo: <proc>}
STORE main                      [<proc>]                                   {foo: <proc>, main: <proc>}
APPLY 0                         [None]                                     {foo: <proc>, main: <proc>}
POP                             []                                         {foo: <proc>, main: <proc>}

L'instruction PROC ressemble à la définition d'une fonction mais en fait c'est juste un PUSH de bytecode ordinaire (donc le code reste "linéaire").

La sémantique habituelle de ML, qui est la source d'inspiration directe, est de lui donner un sens existentiel

Alors c’est justement là que tu te trompes : la source d’inspiration directe, c’est Haskell. Plus précisément, Haskell sans les classes de types, que je réserve pour plus tard, si besoin.

Et sans un tas d'autres choses, mais Haskell est un ML (qui est plus une famille de langages et de systèmes de types qu'un dialecte précis - d'ailleurs, même dans les langages qui s'appellent « ML », il y a plusieurs implémentations différentes). Désolé si ce n'était pas clair.

Donc les contraintes sont de type forall : une fonction sur des listes qui utiliserait dans son traitement une fonction qui ne porte que sur les entiers ne pourrait avoir le type (lambda (List a) (List a)).

Ce n'est écrit nulle part dans ta spécification, et c'est très important. En fait, ta spécification ne parle même nulle part des variables de types, il y a seulement une vague ligne « les types peuvent prendre des paramètres » : sans connaître à l'avance un langage fonctionnel typé (ce qui n'est le cas d'à peu près personne dans cet atelier), aucune chance de comprendre comment ça marche (et même en ayant l'habitude, comme tu peux le constater, ce n'est pas suffisamment bien défini).

Ceci étant dit, forcer un typage explicite des fonctions du top-level ne te permettra pas de faire l'économie d'un typeur qui fasse un minimum d'inférence (en fait, ça ne changera même pas grand chose). Tu n'y arriveras pas avec une vérification « à la C » qui se contente de s'assurer que « les types sont compatibles » là où c'est pertinent de se poser la question.

Si vous voulez des types […] prenez un système déjà spécifié, sans essayer de faire des modifications au petit bonheur la chance pour le simplifier.

C’est largement le cas. Comme dit plus haut, j’ai repris le système de types de Haskell, en remplaçant une manière de surcharger des fonctions (les classes de types) par une autre (les modules homonymes des types), a priori plus aisée à mettre en place, car plus explicite.

Le système de namespaces n'a rien à voir avec les typeclasses (parce que, précisément, il n'y a aucune surcharge). Mais indépendamment de ça, ce n'est pas à moi qu'il faut le dire ici, c'est dans tes spécifications qu'il faut l'écrire (et l'écrire explicitement : tu ne peux pas compter sur le lecteur pour deviner où tu penses que les quantifications se font, et pour le coup ce n'est pas quelque chose que tu peux laisser au choix de l'implémentation).

Il y a aussi quelques défauts de moindre importance, ou qui dans l'absolu n'en sont pas vraiment mais se trouvent être des mauvaises idées dans le cadre actuel : les trouzmille types d'entier, l'ajout inutile des flottants et des caractères, les tuples qui n'apportent rien… en fait, des points qui vont dans une tendance à laquelle il faut faire attention qui consiste à insister beaucoup sur une surspécification des détails (vous vous rappelez de « est-ce qu'on écrit -> ou lambda ? » ?) en négligeant les fondations (du bikeshedding, en somme.)

Bon, c’est dommage, tu retombes dans le travers de « laissez tomber, c’est trop compliqué pour vous »…

Où est-ce que j'ai écrit dans le message que tu cites la moindre phrase qui te fasse penser ça ?

En toute sincérité, qu’est-ce que cela change ? Y a-t-il une différence fondamentale de fonctionnement entre l’utilisation d’entiers signés sur 16 bits et d’entiers non signés sur 32 bits, sachant que toutes les machines modernes gèrent les uns et les autres nativement, et que a fortiori, la plupart des langages d’implémentation sauront les gérer aussi sans qu’on ait rien à faire ?

Ce que ça change, c'est des complications complètement inutiles à développer et à maintenir alors qu'il y a déjà largement assez à côté. Honnêtement, qu'est-ce que ça change que le langage soit capable de faire la différence entre des entiers signés ou non-signés sur 32 ou 64 bits ?

Je répète, y a-t-il quoi que ce soit de réellement plus difficile à gérer 8 types d’entiers bornés plutôt qu’un seul ? Ou est-ce que ce sera juste un chouïa plus long à taper le code ? Idem pour les tuples, ce ne sont jamais que des plages de mémoire adjacentes / tuples / structures de langage impératif : où se trouve la difficulté supplémentaire ?

Il y a quoi de réellement plus limitant à se restreindre à un seul type d'entiers ? Encore une fois, vous ne codez pas un langage pour qu'il soit utilisable, mais pour apprendre. Dans ce cadre, une fonctionnalité qui complique votre tâche sans apport pédagogique concret est à jeter à la poubelle. C'est le cas ici.

Il y a effectivement deux difficultés dans ces types natifs. Les entiers non bornés, tout d’abord. Ceux-là ont été explicitement demandés un peu plus haut dans la discussion. Et la solution sera très certainement de faire appel à une bibliothèque tierce, comme la plupart des langages qui en ont.

Mais alors ça n'a aucun intérêt : ça devient une fonctionnalité « pour l'utilisation » au lieu d'être une fonctionnalité « pour l'apprentissage ». Soit vous voulez comprendre comment on implémente des entiers à taille variable, et il faut le faire vous-mêmes, soit vous considérez (mon avis personnel est que c'est le bon choix) que c'est quelque chose d'indépendant à l'implémentation d'un langage et qu'il vaudrait mieux faire ça sous forme de lib dans un autre projet, et vous pouvez oublier.

Les caractères Unicode, ensuite. Là, de fait, rien à dire, ça risque d’être un peu plus compliqué qu’un simple char de C. Encore une fois, la solution viendra certainement d’une bibliothèque tierce ou d’un langage d’implémentation qui gère nativement ce genre de caractères (comme Rust ou Haskell, par exemple).

Pareil que pour les entiers non bornés, sauf que pour le coup, vous n'avez vraiment pas envie d'implémenter ça vous-mêmes. Soit votre langage le gère nativement (coup de bol, Python le fait) et vous n'avez pas besoin de vous en préoccuper, soit vous ne devriez pas vous en préoccuper parce que c'est totalement orthogonal aux problématiques d'interprétation et de compilation.

Maintenant, si vraiment vous y tenez, je le redis : je n'empêche personne de le faire. Vous avez un avis et des conseils qui cherchent à vous faire avancer le plus possible dans la direction « apprendre à implémenter un langage », libre à vous de les suivre ou pas.

Je laisse ça là entre les contradictions et inepties de certains si vous vous posez toujours la question du back-end: Malfunction