orga -- stack machine virtuelle de puant
Posté le 14/04/2023 02:24
Yo les gens ! Je viens ici pour présenter
orga, une petite stack machine que j'ai design, accompagné d'un assembleur et un émulateur. Ce post initial est assez sec et inaccessible à première vue si vous n'avez jamais touché à ce genre de projet, n'hésitez pas à poser des questions.
dépot git d'orga
Disposition mémoire
L'unité mémoire d'orga est le short (uint16_t).
La mémoire addressable d'orga fait
0x10000 (65536) shorts. Elle est parcourue par le program counter à l'exécution.
Les stacks (stack principal et return stack) peuvent contenir jusqu'à 65536 shorts également.
Écran
Dimensions de 128x128.
Le framebuffer d'orga est placé de
0xbfff à
0xffff dans la mémoire addressable.
Le layout est séquentiel, chaque pixel de gauche à droite, ligne par ligne de haut en bas.
Les pixels eux mêmes sont stockés en R5G6B5.
L'écran et les events sont raffraichis à l'appel de l'instruction
SLP.
Entrée utilisateur
À l'addresse mémoire
0xbffe se trouvera les entrées utilisateur, dans la même disposition que les
controlleurs NES.
Et comment ça s'utilise ?
$ git clone https://kdx.re/cgit/orga
Cloning into 'orga'...
Fetching objects: 110, done.
$ cd orga/
$ ./build.sh
orgaasm
orgaemu
$ ./orgaasm samples/screen.orgaasm screen.rom
$ ./orgaemu screen.rom
À quoi ressemble un programme ?
La syntaxe est largement inspirée par uxntal d'100r.
LIT ,hellostr ( shorthand: -hellostr )
JRT ,putstr ( shorthand: /putstr )
RET
@putstr ( str -- )
DUP LDA WRT ( write )
INC ( increment pointer )
DUP LDA ( loop until end of string )
JNZ ,putstr
POP
RET
( "hello world" )
@hellostr 0068 0065 006c 006c 006f 0020 0077 006f 0072 006c 0064 000a 0000
LIT ,Screen
@loop
DUP DUP STA ( draw pixel )
INC DUP ( overflow check )
JNZ ,loop
@infinite
SLP
JMP ,infinite
D'autres exemples sont disponibles dans
le dossier samples/ du git.
Pourquoi ce topic ?
Je suis en capacité de porter l'émulateur naivement sur 90+E en très peu de temps, mais je m'attend à devoir faire diverses optimisation pour tenir à 30FPS sans overclock sur calto. Je prépare le terrain avec ce topic pour archiver mes questions (la shout part trop vite ça me fatigue).
dépot git d'orga
Fichier joint
Citer : Posté le 14/04/2023 08:02 | #
Classe, j'approuve tout langage ! Je sais que tu t'attends à la question, mais en termes de sémantique (= aspects/fonctions du langage) est-ce qu'il y a des trucs inhabituels ou tu restes sur de l'assembleur / VM à pile classique ?
Citer : Posté le 14/04/2023 14:39 | #
Eye, merci !
Je sais que tu t'attends à la question, mais en termes de sémantique (= aspects/fonctions du langage) est-ce qu'il y a des trucs inhabituels ou tu restes sur de l'assembleur / VM à pile classique ?
Sur l'aspect technique, l'assembleur et la VM font respectivement 260 et 400 lignes et sont, à mes yeux, plutot bien rédigés et faciles à modifier.
Niveau syntaxe, j'ai implémenté dans l'assembleur quelques shorthands pour rendre la rédaction manuelle plus simple (assez classique pour un assembleur) et il est très facile d'en ajouter d'autres.
Par exemple :
Je précise que le bytecode généré est exactement le même avec ou sans shorthand.
J'ai aussi choisi d'utiliser une simple instruction SLP pour redonner le controle à la machine (pour raffraichir l'écran et poll le clavier), alors que d'autres machines virtuelles que j'ai utilisé mettent ces valeurs à jour en parallèle ou utilisent des interruptions ce qui est logique pour une machine physique mais peu pratique pour une VM.
Je profite de ne pas avoir des restrictions physiques et fais quelques tradeoffs sur la mémoire au nom de la simplicité. En dehors de ça, je pense que c'est assez standard pour une stack machine.
flemme de lire ? skip here
Quelque chose d'intéressant cela dit, j'ai écrit un parser et un lexer pour un petit langage impératif (un B avec des soupçons de syntaxe Lisp) il y a un mois. Je vais essayer de lui faire output du (relativement mauvais) code orga, et après ça j'aurai une toolchain de l'angoisse que j'aurai design de A à Z.
C'est très artisanal, et je me suis amusé à tout faire sans copie de string pour les perfs et satisfaire ma paranoia -- quand je vois un malloc non protégé je pète un cable fr fr.
Moins stable et plus complexe que orga (pour des raisons évidentes), le compileur en question se trouve > ici <.
Citer : Posté le 14/04/2023 14:59 | #
Aha ! J'avais vu passer golem. Je veux dire j'ai traîné une fois sur ta forge et "compiler something something" a immédiatement attiré mon attention haha.
Ah voilà les détails juteux de sémantique. Bonne idée à mon humble avis, ça esquive tous les problèmes de synchronisation x)
Suggestion stupide : as-tu envisagé d'accepter les symbols dans les identifieurs ? Vu que tu n'as pas d'expressions compliquées et principalement du Lisp-like tu pourrais accepter eg. < et > dans les identifieurs et ainsi avoir des notations à la (>= x 2) (et créer des fonctions opérateurs à la demande !).
Est-ce que des commentaires sur l'implémentation t'intéressent ou je te laisse tranquille ?
Citer : Posté le 14/04/2023 15:10 | #
Suggestion stupide : as-tu envisagé d'accepter les symbols dans les identifieurs ? Vu que tu n'as pas d'expressions compliquées et principalement du Lisp-like tu pourrais accepter eg. < et > dans les identifieurs et ainsi avoir des notations à la (>= x 2) (et créer des fonctions opérateurs à la demande !).
Les symboles sont traités de la même manière que tous les autres caractères ASCII. Je vois mal comment du FORTH-like se traduirait en Lisp-like comme tu l'as écrit, en tout cas dans l'assembleur que j'ai écrit. Un compileur Lisp-like devrait être rapide à écrire cela dit. Est-ce que je rate quelque chose dans ce que tu décris ? Je me demande si je comprend bien ce que tu voulais exprimer.
Est-ce que des commentaires sur l'implémentation t'intéressent ou je te laisse tranquille ?
Vas-y ça m'intéresse !
Citer : Posté le 14/04/2023 15:47 | #
L'histoire des symboles c'est pour Golem ! Tu écris des choses comme (lesseq x 2) et je me faisais la remarque qu'écrire (>= x 2) serait possible si >= était traité comme un identifieur. Un truc marrant c'est que ça te permettrait aussi de définir des opérateurs custom genre la concaténation ou que sais-je :
let cat;
cat = (alloc (+ (+ [str1 0] [str2 0]) 1));
[cat 0] = (+ [str1 0] [str2 0]);
[cat 1] = '\0';
(strcat cat str1);
(strcat cat str2);
return cat;
}
Du coup des trucs sur l'implémentation... généralement le parser lit la séquence de tokens de gauche à droite et du coup il appelle le lexer quand il a besoin d'un token. (Ça dépend des types de parsers mais en C c'est plutôt des parses de ce type.) Du coup normalement y'a pas besoin de matérialiser la séquence de tokens en mémoire et en liste doublement chaînée car les tokens sont générés à la volée.
En lisant ton parser je comprends pourquoi du coup. Tu prends ta série de tokens et tu fais des groupements en live au milieu de la liste doublement chaînée. C'est raisonnable mais tu passes beaucoup d'efforts à identifier les structures, chercher les parenthèses fermantes, etc. Pour ta culture il existe des méthodes plus systématiques (par là j'entends très streamlined et le code est une traduction directe de la syntaxe au papier).
L'intuition c'est que ton langage est bien foutu et du coup durant le parsing quand tu sais dans quel contexte tu es et quel est le prochain token tu sais tout de suite quelle structure syntaxique est employée. Par exemple quand tu es au milieu d'une fonction et que tu attends un statement, "if" introduit un bloc if, "(" une expression, "let" une déclaration de variable, un nom de variable un assignement, etc - et il n'y a pas d'ambiguïté. Du coup tu peux écrire un "parser prédictif" et éviter d'avoir à chercher quoi que ce soit. Le parser prédictif lit les tokens une fois de gauche à droite et construit l'arbre de syntaxe d'une façon très guidée.
Bref, le mot-clé est "recursive descent parser" si tu n'as jamais vu. Je me permets de te glisser ce fichier Python à titre d'illustration (en haut la grammaire, en bas les fonctions récursives, tu noteras la traduction très directe).
Le plus fun c'est une fois que t'as fini le parsing ! T'as le droite à l'analyse sémantique, genre vérifier que les appels de fonctions ont le bon nombre d'arguments (les types quand il y en a), trouver quelles variables sont mentionnées (locales/globales/etc), et tu peux même faire des optimisations. Enjoy !
Citer : Posté le 14/04/2023 16:07 | #
aaaan tu parlais de golem j'avais pas tilté. Oui bien sur c'est raisonnable pour l'histoire de symboles, j'ai fait ce changement à l'envers pour rendre le prototype plus rapide à écrire.
J'ai déjà lu à propos des recursive descent parser, j'avais pensé la syntaxe de golem autour de ça avant de passer sur ma méthode barbare. Après ton rappel et ton explication, en plus du fait que je considère maintenant que la syntaxe de golem est à peu près stable, j'ai bien envie de tout réécrire (si ça prend pas trop longtemps, et au pire j'ai toujours mon code actuel) pour avoir une base plus saine. Merci bien !
et tu peux même faire des optimisations
Citer : Posté le 14/04/2023 20:00 | #
Piou piou piou...
Mais que vois-je, un topic de costauds dirait-on
Je trouve ton idée super intéressante.
Il nous manque peut être un peu de contexte : pourquoi ce projet ? pourquoi maintenant ?
Ce qui pourrait être intéressant (de mon point de vue de novice), ce serait d'avoir une espèce d'IDE dans laquelle on pourrait voir le code et l'état de la pile étape par étape afin de bien voir comment tout cela fonctionne (une espèce de mode "Debug" en gros). Mais je sais que c'est un truc chiant, notamment pour la partie SLP avec scan des inputs.
Joli boulot KikooDX.
Citer : Posté le 14/04/2023 21:36 | #
Cher SlyVTT, as-tu connu l'époque des topics "--" de KikooDX ? :3
Citer : Posté le 14/04/2023 21:39 | #
No, j'ai du louper qq chose alors
Citer : Posté le 14/04/2023 21:40 | #
T'as un lien pour voir ?
Citer : Posté le 14/04/2023 21:40 | #
Cherche les topics contenant "--" sur la page de profil de KikooDX
Citer : Posté le 14/04/2023 21:45 | #
C'est bon je vois
D'ailleurs j'ai trouvé un fil sur ABLE qui est utilisé dans hyperultra, et je ne voyais pas à quoi ça faisait référence.
Je vais me coucher un peu moins bête
Citer : Posté le 15/04/2023 06:39 | #
Merci Sly !
Il nous manque peut être un peu de contexte : pourquoi ce projet ? pourquoi maintenant ?
Lephé a mieux répondu que j'aurais pu moi-même eheh.
Ce qui pourrait être intéressant (de mon point de vue de novice), ce serait d'avoir une espèce d'IDE dans laquelle on pourrait voir le code et l'état de la pile étape par étape afin de bien voir comment tout cela fonctionne (une espèce de mode "Debug" en gros). Mais je sais que c'est un truc chiant, notamment pour la partie SLP avec scan des inputs.
Modifier orgaemu pour ajouter une fonctionnalité de stepping devrait être relativement trivial, c'est peut-être quelque chose que j'ajouterai long terme si le besoin se fait sentir.
Et même si il n'y a encore rien de proche à ce que tu décris pour le moment, l'opcode DBG imprime la stack entière dans stderr (le terminal), c'est pratique pour faire du "printf debugging" avec orga
Citer : Posté le 15/04/2023 13:44 | # |
Fichier joint
Pour éviter la répétition dans les samples, je me suis mis à utiliser des macros m4. Il faut donc passer par l'étape supplémentaire qu'est lancer m4 avant l'assemblage. Le script run.sh à la racine du dépot se charge de tout ça. Deux nouveaux scripts, embed.sh et embed_win.sh permettent d'embarquer une ROM avec orgaemu pour la rendre standalone.
J'ai passé un petit moment à me casser la tête contre un mur pour écrire la routine de dessin de sprites 8x8 en assembleur sans que ce soit trop mauvais (c'est pas parfait non plus), je doute fortement que ce soit suffisant pour quand je ferai le port calto mais je verrai bien.
Grace à ces avancées, j'ai pu créer le premier programme à peu près substanciel pour orga, samples/move.orgaasm (screenshot ci-dessous). Je vous invite à l'essayer en clonant le dépot et en lançant ./run.sh samples/move.orgaasm
Citer : Posté le 15/04/2023 13:46 | #
Salut !
Je voulais savoir, j'ai déjà entendu ce mot, mais c'est quoi stack ?
Pour moi, ça sonne avec internet...
Donc je comprends pas trop
Et sinon, quel est l'intérêt ? Je demande d'avance au cas où je ne comprendrai pas.
Salut
Citer : Posté le 15/04/2023 13:50 | #
Une pile : En gros tu push des données dessus et tu les pop plus tard.
Citer : Posté le 15/04/2023 13:55 | #
Je voulais savoir, j'ai déjà entendu ce mot, mais c'est quoi stack ?
Une stack -- pile en français -- est une structure de données où des valeurs peuvent être "poussées" en haut de la pile, et "sorties" dans l'ordre dernier arrivé, dernier sorti. Je te redirige vers la page Wikipédia dédiée pour plus de détails.
orga a un processeur qui utilise une pile pour ses calculs en lieu et place de registres, ce qui en fait un processeur à pile.
Et sinon, quel est l'intérêt ? Je demande d'avance au cas où je ne comprendrai pas.
https://justforfunnoreally.dev/
Citer : Posté le 15/04/2023 14:04 | #
Ok, merci, je comprends mieux
Je vais me coucher moins bête.
Nann, pas à 2h de l'aprèm, quand même...
Citer : Posté le 15/04/2023 17:23 | #
Hello ! C'est excellent comme projet... j'adore !
Quand j'essaie de le build j'ai quelques erreurs :
./build.sh: 3: [: unexpected operator
orgaasm
./build.sh: 5: -std=c99: not found
orgaemu
./build.sh: 7: -std=c99: not found
... une idée ?
Citer : Posté le 15/04/2023 17:25 | #
Sérieux KikooDX mais le nom quoi