Compiler notre langage pour CHIP-8

En AP3, nous avons produit du bytecode pour une machine à pile. Pouvons-nous changer de machine cible et voir notre programme s’exécuter dans une petite console existante ? CHIP-8 est une machine virtuelle très simple, née dans les années 1970, dont les programmes s’ouvrent dans un émulateur du navigateur. Un tel programme s’appelle une ROM : un fichier d’octets que la console lit comme son programme. Ce projet construit un second backend : vous traduisez les arbres d’AP2–AP3 vers CHIP-8, puis vous produisez une scène commandée au clavier. Un palier avancé, facultatif, ajoute les appels de fonctions et la récursion terminale pour compiler le Sokoban complet présenté en cours.

Le projet noté commence en semi-autonomie pendant AP9 et se poursuit à la maison. Nous pouvons démarrer ensemble le premier calcul avant d’aborder les liaisons, les branches et le graphisme. Les modalités de notation et l’échéance seront précisées avant le lancement ; les paliers organisent le travail, ce ne sont pas des niveaux de note. La machine qui exécute votre ROM existe déjà : le travail porte sur la traduction du langage et ses garanties.

Téléchargez le squelette backend-chip8. Le README contient le parcours complet, les contrats, la table d’instructions, les indices et les commandes. Vous n’avez aucun HTML, CSS ou JavaScript à écrire. Le projet Mix n’a pas de dépendance externe et ne demande pas un parser AP2 terminé.

Le schéma résume la chaîne. Votre code parcourt l’arbre et produit des instructions symboliques ; l’assembleur fourni les transforme en octets et calcule les adresses ; l’émulateur exécute enfin la ROM. Le socle suit les paliers 1 à 4, puis la démonstration personnelle du palier 6 ; le palier 5 est un prolongement.

Commencer avec une ROM qui fonctionne

Dans le dossier extrait, lancez :

mix compile
mix test --only provided

Les quatorze tests de l’infrastructure doivent être verts. Ouvrez ensuite Octo, utilisez Open pour charger priv/witness.ch8, puis Run. La ROM fournie dessine un carré creux de 4 × 4 pixels à la position (12, 8), place 42 dans V0, puis boucle sur place à l’adresse 0x20C. Vous pouvez inspecter les registres dans le débogueur. Cette première expérience distingue l’ouverture de l’émulateur du travail sur le backend.

Cadmium est une seconde possibilité : glissez la ROM dans sa fenêtre, avec un profil CHIP-8 classique. Le README du squelette explique les réglages du sujet. Les tests Elixir restent utilisables hors ligne ; ils comportent une petite machine fournie, limitée aux instructions utilisées, que vous n’avez pas à programmer.

Si les mots registre ou PC restent abstraits, reprenez les slides 7 à 11 d’AP3. Un registre est une case de calcul du processeur, lue et écrite directement par les instructions : V0 contient une valeur, I une adresse de données et le PC l’adresse de la prochaine instruction. Les seize registres V0 à VF contiennent des octets ; VF sert aussi de drapeau après une opération.

Fixer ce que le programme signifie

Notre interpréteur AP2 manipulait des flottants. Cette console travaille avec des entiers de huit bits : nous choisissons donc un profil u8 explicite. Les littéraux doivent être entiers et compris entre 0 et 255. 12.0 est accepté, mais 12.5 est refusé. Addition, soustraction et moins unaire calculent modulo 256 : 255 + 1 vaut zéro, et 0 - 1 vaut 255.

Les booléens restent distincts des nombres dans le langage source ; les registres les représentent par zéro et un. Les comparaisons < et == prennent deux nombres. Les let restent immuables et lexicaux. Un case exécute une seule de ses deux branches. Les fonctions générales, les boucles, la multiplication et la division restent hors du socle.

Le validateur et l’évaluateur de référence sont fournis. Vous pouvez ainsi comparer le sens de l’arbre au résultat de sa ROM, sans utiliser l’ancien interpréteur Float pour un calcul dont la sémantique a changé.

ast = {:binary, :-, {:number, 40},
       {:binary, :+, {:number, 8}, {:number, 3}}}
{:ok, result} = BackendChip8.Source.evaluate(ast)
29 = result.value

Les fichiers examples/*.exs contiennent directement des arbres Elixir, comme dans AP3. Leur lecture est fournie ; ce projet ne vous demande pas de construire un nouveau parser.

Palier 1 : traduire les expressions imbriquées

Dans lib/backend_chip8/codegen.ex, emit/3 traite déjà les nombres et les booléens. Vous complétez binary/5 pour les opérations et les comparaisons. La convention est simple : chaque expression doit laisser son résultat dans V0.

Prédisez d’abord ce que donne 40 - (8 + 3) si l’on compile la gauche puis la droite sans rien sauvegarder : où est passé le 40 ? Calculer la droite a remplacé le contenu de V0. Il faut donc sauvegarder la gauche dans une case mémoire, puis la recharger. L’allocateur de cases est fourni ; vous choisissez quand réserver, sauver et recharger. La soustraction doit conserver l’ordre de ses opérandes. Les tests font également apparaître débordements, égalité et emprunt.

mix test --only palier_1
mix chip8 examples/arithmetic.exs out/arithmetic.ch8

Au départ, quatre tests de ce palier échouent avec « à compléter : binary/5 » ; le littéral seul fonctionne déjà. Une fois le palier terminé, ouvrez la ROM produite et comparez V0 à votre prédiction. La commande indique l’adresse à laquelle le programme boucle après le calcul.

Palier 2 : conserver la portée des noms

Complétez variable/3 et binding/5. L’environnement de compilation associe chaque nom à une étiquette de case mémoire. Il ne contient pas la valeur que la console calculera plus tard.

Pour let x = 20; (let x = 3; x) - x, l’occurrence intérieure désigne 3, puis la dernière retrouve 20. Le profil u8 donne donc 239. Un let étend l’environnement de son corps sans changer celui des expressions voisines. L’état des réservations, lui, circule entre les appels pour ne pas attribuer la même case à deux valeurs encore utiles.

mix test --include palier_2

Gardez une trace avec les deux liaisons de x, leurs cases et leurs valeurs. Une image correcte ne révélerait pas à elle seule une erreur de portée.

Palier 3 : construire les sauts

Complétez branch/5. Un label est un nom symbolique d’adresse, comme les étiquettes d’AP3 : l’assembleur calcule les adresses en deux passes, et vous produisez des labels uniques, les sauts et le point où les deux chemins rejoignent la suite. Attention, un skip CHIP-8 ne saute que l’instruction suivante : il faut le combiner avec un jump pour éviter un bloc entier.

mix test --include palier_2 --include palier_3

Dessinez le trajet du PC pour chaque valeur de la condition. Les deux branches sont présentes dans la ROM, mais une seule doit s’exécuter. Un case imbriqué et une opération après le choix permettent de vérifier la jonction.

Palier 4 : retrouver les pixels et le clavier

Complétez enfin primitive/4 pour les trois appels réservés :

Le numéro de tuile est un littéral entier 0..6. Les coordonnées peuvent être des expressions. Un case permet de choisir entre deux dessins. Une tuile est un sprite : un petit dessin de quelques octets, ici 4 × 4 pixels, que l’instruction de dessin copie à l’écran à partir de l’adresse contenue dans I. La table de sprites et les instructions d’affichage sont fournies ; votre backend préserve les arguments, les place dans les registres et produit les instructions.

Le dessin CHIP-8 fait un XOR : dessiner deux fois les mêmes pixels peut les éteindre. Les sept tuiles représentent directement mur, sol, cible, caisse, caisse sur cible, joueur et joueur sur cible. Le profil utilise un écran 64 × 32 avec clipping aux bords, c-à-d. que les pixels qui dépasseraient l’écran sont coupés ; les réglages sont expliqués dans le README.

mix test --include palier_2 --include palier_3 --include palier_4
mix chip8 examples/keyboard.exs out/keyboard.ch8
mix chip8 examples/sokoban.exs out/sokoban.ch8

La première ROM attend une touche une fois, puis choisit un dessin. La seconde affiche le niveau 1 du sujet Sokoban PE. Le lecteur XSB et la construction de l’arbre sont fournis côté Elixir ; la console n’a pas besoin de comprendre des chaînes ou des tableaux. Le niveau affiché est statique. Un moteur Sokoban jouable est fourni dans le palier suivant, où vous travaillez sa compilation.

Palier 5, prolongement : faire boucler le jeu avec un appel terminal

Ce palier est facultatif : le socle passe directement du palier 4 au palier 6. Retrouvons une notion d’AP1 : un appel récursif est terminal lorsqu’aucun calcul ne reste à faire après son retour. n + sum(n - 1.0) attend encore une addition ; sum(n - 1.0, total + n) calcule ses arguments, puis transmet directement le résultat de l’appel.

Un appel CHIP-8 CALL empile une adresse de retour, que RET dépile. La pile n’accepte que seize retours : empiler à chaque tour de main ferait déborder le jeu. L’auto-appel terminal remplace les paramètres puis utilise un saut JP, sans empiler de nouveau retour.

Le fichier examples/sokoban.ap contient le jeu complet : carte, fonctions de dessin, déplacements, poussées, victoire, initialisation et boucle main. Le parser, la vérification des fonctions, les primitives de mémoire et les sprites sont fournis. Les expressions ordinaires utilisent toujours votre génération des paliers précédents.

Dans lib/backend_chip8/functions.ex, vous complétez deux fonctions :

• prepare/4 calcule et sauvegarde tous les arguments avant d’affecter les paramètres. Tracez loop(b, a, n - 1.0) : écrire le nouveau a trop tôt empêcherait de retrouver l’ancien pour calculer le nouveau b.
• transfer/2 choisit un appel ordinaire ou un saut pour l’auto-appel terminal. Le validateur fourni refuse les appels récursifs en position non terminale.

mix test --include palier_2 --include palier_3 --include palier_4 --include palier_5
mix chip8.game examples/sokoban.ap out/sokoban-game.ch8

Les tests avancés sont exclus au départ. Ils vérifient les appels imbriqués, la permutation des arguments, plus de cent tours avec une pile bornée, puis la solution du Sokoban. La ROM se joue dans un émulateur existant, sans écrire son interface. Les touches CHIP-8 4, 6, 2, 8 correspondent à gauche, droite, haut, bas ; le README explique les touches physiques.

Ce profil accepte des fonctions fermées de premier ordre : elles appellent les fonctions déjà définies ou elles-mêmes en position terminale. Il n’ajoute ni fermetures ni récursion mutuelle. Le README précise les types, la mémoire, les opérations fournies et le profil graphique avancé. Notez enfin qu’une pile bornée ne garantit pas la terminaison : main attend volontairement les touches et continue tant que l’on joue.

Palier 6 : produire votre démonstration et vos vérifications

Créez votre propre arbre dans examples/my_scene.exs. Il doit combiner un calcul de coordonnées, une liaison réutilisée et un choix visible. Vous pouvez réutiliser la lecture du clavier ou partir d’un petit niveau XSB. Le programme, les sprites et les cases doivent tenir ensemble dans 3 Kio ; l’assembleur refuse une ROM qui dépasse cette limite.

Ajoutez des tests personnels dans test/personal_test.exs, qui détecteraient une erreur plausible : soustraction inversée, temporaire réutilisé trop tôt, nom masqué qui fuit dans la suite ou branche inactive exécutée. Comparez valeurs, pixels et touches restantes à l’évaluateur fourni, puis ouvrez la ROM dans l’émulateur.

Conservez le code, les tests, une ROM et COMPTE-RENDU.md. Le compte rendu contient les commandes réellement exécutées, une trace prédite puis observée, l’explication d’une portée et d’un saut, une capture de la scène avec le profil de l’émulateur, ainsi qu’une limite du backend. Pour le palier avancé, ajoutez une trace des arguments et de la pile, et expliquez le saut de main. Le README donne la liste précise des éléments à garder et les fichiers à exclure du rendu.

Pour poursuivre, vous pouvez mesurer une optimisation : réutilisation de cases mortes, suppression de sauvegardes inutiles ou réduction du code. Vérifiez le même comportement avant de comparer la taille des ROMs. Le manuel Octo et la référence des instructions permettent d’explorer d’autres opérations après le socle. Quand un bout de syntaxe Elixir vous manque, le poly le reprend : le langage aux chapitres 1 à 4, les octets et la compilation au chapitre 6.

Pour toute question sur le sujet ou le point de départ, vous pouvez me contacter par email, comme pour les autres séances.