Corewar.rs — Guide

L'article d'août 1984 de Dewdney dans Scientific American révèle l'origine historique de l'instruction fork. David Menconi, game designer chez Atari, a proposé de faire de l'interaction entre programmes une caractéristique régulière du jeu en permettant à chaque programme de s'exécuter à deux endroits simultanément : « allowing each battle program to execute in two places at once. Thus even if a program loses one 'self,' a second self might be able to repair the damage. » Cette proposition de 1984 préfigure exactement l'instruction fork du Corewar 42 : le fork n'est pas un choix de design arbitraire — il est né de l'observation communautaire que les programmes multi-instances survivent mieux aux dommages. Edsel Worrell a ensuite généralisé en proposant n copies du même programme à des adresses différentes — l'ancêtre direct de la stratégie « fork bomb ».

Le même article rapporte des discussions sur des « programmes de type Creeper habitant des systèmes réels (dont des vers dans les Apple) » et des « programmes comme gènes ». Creeper (1971) fut le premier ver informatique, créé à BBN — le lien entre Core War et les programmes auto-réplicants réels n'était pas une métaphore mais une constatation. La discussion « programmes comme gènes » préfigure le champ de la vie artificielle (Tierra de Tom Ray, 1991, directement inspiré de Core War). Pour l'étudiant 42, cela signifie que les principes du Corewar — auto-réplication, compétition pour les ressources, mutation — sont les fondements de la biologie computationnelle et de l'évolution artificielle.

L'informaticien John von Neumann a théorisé dès 1949 les fondements des « automates auto-réplicateurs » — une construction mathématique posant les bases formelles de programmes capables de se dupliquer, bien avant l'existence matérielle des réseaux informatiques. Ses travaux, publiés à titre posthume dans Theory of Self-Reproducing Automata (1966), démontrent qu'un système formel minimal peut contenir les instructions nécessaires à sa propre reproduction. Corewar constitue l'une des premières matérialisations de cette théorie : chaque champion fonctionne comme un organisme autonome cherchant à maximiser sa reproduction et sa survie dans un environnement mémoire fortement contraint.

Ce comportement préfigure les mécanismes d'infection des véritables virus et vers informatiques, où le self-modifying code est devenu une signature classique des malwares. L'Imp (MOV 0, 1) est l'automate auto-réplicateur de von Neumann réduit à son expression la plus minimale — une seule instruction qui se copie indéfiniment. Les guerriers de type Silk ou Paper sont des réalisations plus sophistiquées du même principe, intégrant la copie de leur propre corps + le fork d'un nouveau processus sur la copie — exactement le schéma décrit par von Neumann : un « constructeur universel » qui copie sa propre description puis l'exécute.

Étudier les dynamiques d'une arène Corewar ne relève donc pas du simple jeu : cela revient à observer l'évolution virale en laboratoire, faisant de cette machine virtuelle un modèle fondamental de l'analyse en sécurité informatique. Les mêmes mécanismes qui rendent les virus dangereux — auto-réplication, code polymorphe, détournement de pointeurs — sont les outils stratégiques du jeu, et les comprendre dans le cadre ludique de Corewar prépare à les reconnaître et à les combattre dans les systèmes réels.

Face au succès phénoménal de la rubrique de Dewdney en 1984, la communauté s'est structurée autour de l'International Core Wars Society (ICWS) pour unifier les règles et organiser des championnats mondiaux. Cette organisation a produit des spécifications historiques majeures : l'ICWS'86 (première standardisation), l'ICWS'88 (enrichissement des modes d'adressage), puis la célèbre révision ICWS'94 (« 94draft ») qui a considérablement enrichi le langage Redcode en introduisant de nouveaux modificateurs et des modes d'adressage complexes. Ce draft de 1994, bien que techniquement jamais finalisé en raison de la dissolution de l'ICWS, est devenu le standard de facto de la communauté.

Pour arbitrer ces tournois avec une équité parfaite, le simulateur pMARS (Portable Memory Array Redcode Simulator), développé en C, s'est imposé comme la machine virtuelle de référence incontestée. Sa précision au cycle près garantit que deux exécutions du même combat produisent toujours le même résultat — une exigence de déterminisme absolu comparable à celle des simulateurs de processeurs réels. Les serveurs automatisés comme le Koenigstuhl (King of the Hill) s'appuient sur ces standards stricts pour évaluer en continu la robustesse des champions codés par des passionnés du monde entier.

L'évolution des standards ICWS illustre un principe d'ingénierie fondamental : la tension entre stabilité (garder les règles simples et prévisibles) et expressivité (enrichir le langage pour permettre de nouvelles stratégies). Chaque révision a élargi l'espace des stratégies possibles, mais a aussi complexifié la VM — un compromis que tout concepteur d'ISA rencontre. Pour l'étudiant 42, la norme ICWS'94 est celle implémentée par le sujet, et comprendre son histoire aide à comprendre pourquoi certaines instructions semblent « étranges » (elles sont le fruit de compromis communautaires).

Les premiers programmes de Core War, décrits par A.K. Dewdney dans Scientific American (mai 1984), ont posé les fondations de toute stratégie moderne. En Redcode original :

• Imp — MOV 0 1 : le programme le plus simple jamais écrit. Il se copie une position en avant, indéfiniment. Une seule instruction, impossible à tuer en le bombardant (il se reconstitue au passage), mais incapable d'attaquer.
• Dwarf — ADD #5 -1 / MOV #0 @-2 / JMP -2 : le premier bomber. Il incrémente un pointeur de 5 à chaque itération et largue un DAT 0 (code invalide qui tue tout processus qui tente de l'exécuter) à l'adresse pointée. Simple, efficace, primitif.
• Mortar (Michael Mauldin, Carnegie-Mellon) : un bomber Fibonacci qui attaque aux adresses 1, 1, 2, 3, 5, 8, 13... Ce pattern de bombing est beaucoup plus difficile à esquiver que le bombing régulier de Dwarf car les intervalles sont imprévisibles.
• Voter : un programme auto-réparateur en trois parties qui utilise un vote majoritaire pour détecter et réparer les corruptions. Si une de ses trois copies est endommagée, les deux autres « votent » pour la restaurer.

L'analyse stratégique de Goetsch, Mauldin et Milazzo (Carnegie-Mellon / Rice) a démontré un résultat fondamental : aucun programme de plus de 10 instructions ne peut battre Mortar sans être auto-réparateur, et aucun programme de plus de 14 instructions ne peut se réparer assez vite pour survivre à Mortar. Ce résultat établit une tension permanente entre complexité (plus de fonctionnalités) et vulnérabilité (plus de surface d'attaque) — le même compromis qu'en ingénierie logicielle réelle.

Les interactions entre ces programmes forment un équilibre de Nash de type pierre-papier-ciseaux : Dwarf bat Mortar 60% du temps (ses bombes régulières touchent Mortar avant que les bombes Fibonacci ne le couvrent), Mortar tue Voter (les bombes Fibonacci sont trop denses pour la réparation), mais Voter bat Dwarf (la réparation résiste au bombing régulier clairsemé). Il n'existe pas de stratégie dominante — c'est ce qui rend le jeu intéressant et compétitif.

Note : Cette section décrit des techniques du Redcode ICWS'94 historique. Les instructions CMP, SLT, SEQ et JMZ n'existent pas dans l'ISA de l'École 42. Le concept du quickscanner (balayer la mémoire pour détecter l'adversaire) reste applicable en 42 via ld/ldi + comparaison par code, mais les techniques spécifiques ci-dessous sont propres au Redcode ICWS.

Les scanners modernes n'utilisent presque jamais de simples sauts conditionnels (JMZ) pour détecter leurs ennemis. Ils exploitent des instructions de comparaison comme CMP (pas d'équivalent direct en 42 ; ld + comparaison) (Compare) ou SLT (Skip if Less Than) combinées à des modificateurs d'auto-incrémentation. Cette technique permet de comparer de larges blocs de mémoire en quelques cycles, créant des boucles de balayage très compactes appelées quickscanners.

Le principe est élégant : au lieu de charger une valeur, de la comparer avec une constante, puis de sauter conditionnellement (3 instructions, 6+ cycles), un quickscanner utilise CMP (pas d'équivalent direct en 42 ; ld + comparaison) avec un mode d'adressage qui incrémente automatiquement le pointeur de balayage. Chaque itération ne coûte qu'un seul cycle de comparaison. Quand CMP détecte une différence avec le DAT 0 attendu, le scanner sait qu'un guerrier ennemi est présent à cette adresse et peut lancer son attaque.

Cette optimisation s'apparente à la fusion de boucles (loop fusion) décrite par le Dragon Book (p.550) : plutôt que de séparer la lecture mémoire, la comparaison et le branchement en instructions distinctes, on les combine en une seule opération qui fait tout en un cycle. C'est aussi un exemple de code golf — l'art de minimiser le nombre d'instructions pour réduire la surface d'attaque du guerrier. Un scanner compact de 5 instructions est beaucoup plus difficile à bomber qu'un scanner naïf de 15 instructions.

L'architecture de la VM Corewar engendre des stratégies de code golf d'une technicité inouïe, où le moindre octet et chaque comportement de l'ordonnanceur sont utilisés comme des armes. L'ordonnanceur round-robin de la machine virtuelle ouvre notamment la porte à la création de « bombes à processus » : au lieu d'utiliser une instruction qui tue instantanément (comme DAT en ICWS, ou un opcode invalide 0x00 en 42), un champion Scanner force souvent l'ennemi à exécuter des instructions de division de processus (SPL 0 en Redcode ICWS, équivalent conceptuel d'un fork vers l'adresse courante en 42). Cette technique sature la file d'attente d'exécution ennemie de processus tournant à vide, ce qui dilue drastiquement le temps de calcul alloué aux fonctions vitales du champion adverse — chaque processus inutile « vole » un cycle au round-robin.

Pour contrer les algorithmes de recherche extrêmement véloces de ces Scanners (qui utilisent des combinaisons CMP/SLT en ICWS pour balayer la mémoire en un minimum de cycles — en 42, le scanning utilise ld/ldi + logique de comparaison), les créateurs intègrent des decoys (leurres). Ce sont des blocs de code obfusqués et factices déployés dans l'arène pour tromper l'analyse ennemie, forçant l'attaquant à gaspiller un temps précieux à attaquer des mirages. Un decoy typique ressemble à du code de guerrier valide mais ne contient que des instructions mortelles (DAT en ICWS, opcode 0x00 en 42) ou des boucles sans effet — le scanner le détecte comme « anormal », lance son attaque, et rate sa cible réelle.

Ces tactiques illustrent un principe fondamental de la guerre de l'information : la désinformation est aussi importante que l'attaque directe. En sécurité informatique réelle, les honeypots (pot de miel) jouent exactement le rôle des decoys — des systèmes factices conçus pour attirer et piéger les attaquants, leur faisant croire qu'ils ont trouvé une cible valide. La saturation par SPL (fork/lfork en 42) est l'analogue d'une attaque par déni de service (DoS) : submerger les ressources de l'adversaire pour le rendre inopérant. Corewar, encore une fois, modélise en miniature les tactiques de la cybersécurité moderne.

Le Vampire est l'un des guerriers les plus fascinants de l'histoire de Corewar. Sa stratégie est fondamentalement différente du bomber ou du réplicateur : au lieu de détruire l'adversaire, il le capture. Le Vampire dissémine des instructions JMP dans l'arène (en ICWS ; en 42, l'équivalent serait un zjmp précédé d'une manipulation garantissant carry=1), chacune pointant vers un « pit » (fosse) — une zone de code sous son contrôle. Quand un processus ennemi exécute accidentellement l'un de ces JMP (zjmp en 42, si carry=1) parasites, il est détourné vers le pit et se retrouve à exécuter du code au profit du Vampire.

Ce mécanisme est l'analogue exact du stack smashing en sécurité informatique : un attaquant écrase l'adresse de retour sur la pile pour détourner le flux d'exécution du programme victime vers du code malveillant qu'il a injecté (shellcode). Van der Linden (Expert C Programming, Ch.4 & 6) décrit en détail comment les manipulations de pointeurs en C peuvent conduire à des corruptions similaires. En Corewar, le Vampire pousse ce concept à l'extrême : il ne se contente pas de détourner un processus — il vole le temps CPU de l'adversaire, car chaque processus capturé exécute les instructions du Vampire, accélérant son propre code au détriment de l'ennemi.

La contre-mesure contre les Vampires est le Imp : un processus qui ne fait que MOV 0, 1 avance d'une case par cycle en se dupliquant. L'Imp est immunisé contre la capture car son code se reconstitue à chaque cycle — si un JMP vampire écrase son MOV (st/sti en 42), le processus suivant le réécrit immédiatement. C'est un exemple frappant de la dynamique pierre-papier-ciseaux : le Vampire bat les guerriers « intelligents » (scanners, bombers complexes), mais perd contre le plus simple de tous les programmes.

Hyde (The Art of Assembly Language, §2.11) introduit les bit fields et les données compressées (packed data) à travers l'exemple d'une date : 4 bits pour le mois, 5 pour le jour, 7 pour l'année = 16 bits au lieu de 24. Il explique : « Although packed values are space efficient [...], they are computationally inefficient (slow!). The reason? It takes extra instructions to unpack the data packed into the various bit fields. These extra instructions take additional time to execute [...]; hence, you must carefully consider whether packed data fields will save you anything. » C'est exactement le compromis de l'OCP Corewar.

L'OCP (Octet de Code Paramètre) est un bit field de 8 bits : 2 bits pour le paramètre 1 (bits 7-6), 2 bits pour le paramètre 2 (bits 5-4), 2 bits pour le paramètre 3 (bits 3-2), et 2 bits de padding (bits 1-0). Comme la date compressée de Hyde, l'OCP économise de l'espace — au lieu d'utiliser un octet par type d'opérande (3 octets), on en utilise un seul. Mais comme Hyde le prévient, cette compression a un coût : le décodage nécessite des opérations de masquage et de décalage ((ocp >> 6) & 0x03 pour le premier paramètre, (ocp >> 4) & 0x03 pour le second). C'est le prix de la compacité — et dans une arène de 4096 octets où chaque octet compte, ce prix est un investissement rentable. Le format .cor pousse cette logique jusqu'à l'extrême : là où un format « unpacké » utiliserait 1 octet par opérande pour le type + 4 octets pour la valeur, l'encodage Corewar compresse les types en 1 octet et utilise des tailles variables (2 ou 4 octets) pour les valeurs. L'OCP est la preuve vivante du principe de Hyde : dans un monde où la mémoire est la ressource rare, la compression bit field est toujours gagnante, même au prix de quelques shifts.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.9, §9.2) introduisent l'analyse de réaching definitions : « A definition d of a variable v reaches a point p if there is a path from the point immediately following d to p such that v is not redefined along that path. » Autrement dit, une définition « atteint » un point si la valeur qu'elle a écrite pourrait encore être présente à ce point — aucune autre écriture ne l'a écrasée en cours de route.

Ce concept est directement applicable au bombing en Corewar. Quand un guerrier bombe l'arène avec un opcode 0x00 à l'adresse A, cette « définition » (l’opcode 0x00) atteint un point futur P si et seulement si aucun autre guerrier n'a écrit à l'adresse A entre le bombing et P. Le bombing adverse est une « redéfinition » qui tue la reaching definition — l’opcode 0x00 n’atteint plus P car il a été écrasé. Un scanner qui comprend les reaching definitions sait que certaines zones bombardées ne sont plus sûres (elles ont pu être écrasées entre-temps) et doit les re-scanner.

Cooper & Torczon (§9.2.2) montrent que les réaching definitions sont un problème forward (l'information va de l'entrée vers la sortie), tandis que la vivacité est backward (de la sortie vers l'entrée). Le bombing est forward : on écrit maintenant, l'effet se propage vers le futur. La détection de corruption est backward : on vérifie maintenant si une valeur passée a survécu. Les deux analyses forment un couple — l'une pour attaquer (forward : où mes bombes atteignent-elles ?), l'autre pour défendre (backward : mes valeurs sont-elles encore vivantes ?).

Le Dragon Book (Compilers, Ch.9) définit le dominateur : « We say node d of a flow graph dominates node n, written d dom n, if every path from the entry node of the flow graph to n goes through d. » L'arbre de dominateurs qui en résulte révèle la structure hiérarchique du flot de contrôle — chaque nœud est dominé par son parent dans l'arbre. Pour un guerrier Corewar, l'arbre de dominateurs montre quels blocs sont obligatoires avant d'atteindre un point donné.

Les boucles naturelles (Ch.9) sont définies par deux propriétés : « 1. It must have a single-entry node, called the header. 2. There must be a back edge that enters the loop header. » La boucle de bombardement d'un Dwarf ou la boucle de scan d'un Scanner sont des boucles naturelles parfaites — un seul point d'entrée (le header), un back edge (le zjmp ou djn de retour). Les guerriers bien structurés produisent des graphes de flot réductibles (p.158-160) : tous les retreating edges sont aussi des back edges, ce qui permet une analyse efficace. À l'inverse, un zjmp qui saute au milieu d'une boucle crée un graphe non réductible — plus difficile à analyser, mais aussi plus résistant au désassemblage par l'adversaire.

Levine (Linkers and Loaders, Ch.1, p.2) rappelle le problème historique que résout la relocation : « The relocating loader allowed the authors and users of the subprograms to write each subprogram as though it would start at location zero and to defer the actual address binding until the subprograms were linked with a particular main program. » Autrement dit, traditionnellement, un chargeur doit modifier les adresses d'un programme pour qu'il s'exécute correctement là où il est placé en mémoire. Corewar résout ce problème de manière élégante : le Redcode est par nature du Position-Independent Code (PIC). Puisque chaque adresse est relative au pointeur d'instruction (PC), le chargeur de la VM n’a besoin de faire aucune relocalisation — le guerrier est injecté à une adresse aléatoire et fonctionne instantanément, comme si le monde tournait autour de lui.

Van der Linden (Expert C Programming, p.103-104) explique le code indépendant de la position (PIC) : « Position-independent code means that the generated code makes sure that every global data access is done through an extra indirection. This makes it easy to relocate the data simply by changing one value in the table of global offsets. » Chaque champion Corewar est intrinsèquement du code indépendant de la position : toutes les adresses sont relatives au PC (décalages), donc le champion peut être chargé à n'importe quelle adresse dans l'arène sans modification. C'est pourquoi le format .cor n'a pas de table de relocalisation — le bytecode est déjà PIC par design.

Levine (Linkers and Loaders, p.154-155) confirme : « Call and jump instructions use relative addressing, so the value in the instruction is the difference between the target address and the address of the byte following the instruction itself. For calls and jumps within the same segment, no relocation is required because the relative positions of addresses within a single segment never change. » C'est la raison technique précise : toutes les instructions Corewar utilisent l'adressage relatif au PC pour leurs paramètres, et le « segment » (le code du champion) se déplace comme un bloc — aucune relocalisation intra-segment n'est jamais nécessaire.

Levine (p.49) identifie aussi le format DOS COM comme le plus proche analogie réelle du .cor : « A COM file literally consists of nothing other than binary code. When the operating system runs a COM file, it merely loads the contents of the file into a block of free memory starting at offset 0x100… and jumps to the beginning of the loaded program. » Comme le format COM, .cor est un « format objet nul » — bytecode pur, pas de header complexe, pas de relocalisation, chargé à un offset connu et exécuté directement. C'est plus précis que la comparaison avec a.out/ELF déjà dans le guide.

L'arène est modifiée en permanence par des lectures et des écritures qui se chevauchent potentiellement. En C, le mot-clé restrict indique au compilateur que deux pointeurs qualifiés restrict ne peuvent pas pointer vers la même zone mémoire (pas d'aliasing). Cela permet des optimisations SIMD automatiques et la réorganisation des lectures/écritures.

Dans les boucles critiques de la VM, déclarez : unsigned char * restrict arena = vm->arena; et int * restrict reg = process->reg;. GCC/Clang peut alors vectoriser les store_at et les load_from sans insérer de barrières de cohérence. Attention : si les pointeurs se chevauchent réellement (ce qui arrive quand une instruction modifie une zone lue par un autre opérande), le comportement est indéfini. Utilisez restrict uniquement dans les fonctions où vous êtes certain de l'absence d'aliasing — typiquement, les fonctions d'encodage/décodage où l'entrée et la sortie sont des buffers séparés.

Van der Linden (Expert C Programming: Deep C Secrets, p.19) définit le comportement indéfini comme : « The behavior for something incorrect, on which the standard does not impose any requirements. Anything is allowed to happen, from nothing, to a warning message to program termination, to CPU meltdown. » Cette définition prend tout son sens dans le contexte de la VM Corewar en C : le débordement d'entier signé, l'accès hors limites du tableau arena[], et le type punning (*(int*)&bytes[0]) sont tous des comportements indéfinis.

Van der Linden documente un cas célèbre : un bug de 20 millions de dollars causé par un simple x==2; au lieu de x=2; (p.3) — une erreur de frappe que le compilateur accepte silencieusement car la comparaison est syntaxiquement valide. Ce type d'erreur est précisément celui que le système de types de Rust élimine : les expressions qui ne produisent pas de résultat utile génèrent un avertissement, et les opérations à risque (débordement, accès hors limites) sont soit interceptées à la compilation, soit remplacées par des versions sûres (wrapping_add, get() au lieu de []).

Le tableau de comparaison C/Rust de ce guide illustre concrètement ces différences : là où le C utilise *(int*)&bytes[0] (type punning, comportement indéfini selon la norme C), le Rust utilise i32::from_be_bytes() (sûr, défini, portable). Là où le C a un débordement d'entier silencieux (UB), le Rust utilise wrapping_add() qui définit explicitement le comportement modulo 2³². Comme le dit Van der Linden : « Performance Is (almost) Everything — if you don't get accurate results, then it's immaterial how fast you get them. » (p.9)

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.4, Problème 5.28) énonce le Théorème de Rice : toute propriété non-triviale des langages récursivement énumérables est indécidable. « Non-triviale » signifie que la propriété est vraie pour au moins un langage RE et fausse pour au moins un autre. Ce théorème généralise le Problème de l'Arrêt : il ne s'agit plus seulement de savoir si un programme s'arrête, mais de toute question sémantique sur son comportement.

En Corewar, les applications sont nombreuses et profondes. Déterminer si un guerrier « gagne toujours » est indécidable. Déterminer si un guerrier « est un bomber » est indécidable. Déterminer si un guerrier « utilise plus de 3 registres » est indécidable. Déterminer si un guerrier « finit par s'auto-détruire » est indécidable. Chacune de ces propriétés est non-triviale — vraie pour certains guerriers, fausse pour d'autres — et donc frappée par le Théorème de Rice. La conséquence pratique est que aucune analyse statique d'un guerrier ne peut garantir ses propriétés dynamiques. On ne peut pas prouver, en examinant le bytecode seul, qu'un guerrier va se comporter d'une certaine manière dans l'arène. Seule l'exécution (la simulation) révèle le comportement — et même la simulation ne garantit pas le comportement futur. Le Théorème de Rice est la raison fondamentale pour laquelle les tournois Corewar existent : si on pouvait prouver qui gagne, il n'y aurait pas besoin de jouer. Corewar est le terrain de jeu du Théorème de Rice — chaque match est une preuve par l'exécution que l'indécidabilité n'est pas qu'un concept abstrait.

Crafting Interpreters introduit le concept de call frame (cadre d'appel) : chaque fonction en cours d'exécution possède une « fenêtre » dans la pile de valeurs, avec son propre IP et ses propres variables locales. Les fenêtres du caller et du callee se chevauchent — les arguments sont déjà à la bonne place. Dans Corewar, chaque processus a également une « fenêtre d'exécution » : son PC, ses 16 registres et son carry forment un contexte indépendant. Mais contrairement à clox où les fenêtres sont imbriquées hiérarchiquement (caller → callee), les fenêtres Corewar sont plates et concurrentes — tous les processus partagent la même arène et sont ordonnancés en round-robin. Le SPL crée un nouveau contexte qui partage la mémoire mais diverge dans son exécution, une structure impossible dans un langage classique mais naturelle pour un jeu de guerre de programmes.

Smith et Nair (Virtual Machines, p.70-73) décrivent une optimisation fondamentale pour les codes de condition : « It turns out, however, that although the condition code values are set frequently, they are seldom used. To make condition code emulation more efficient, a common technique is to perform lazy evaluation, where the operands and operation that set the condition code, rather than the condition code settings themselves, are saved. » Le carry de Corewar est l'analogue direct d'un code de condition — positionné par certaines instructions (and, sub, ld), testé par zjmp. L'évaluation paresseuse serait possible : au lieu de calculer le carry immédiatement après chaque instruction, on pourrait stocker l'opération et ses opérandes, et ne calculer le carry que quand zjmp le lit réellement. En pratique, la VM Corewar calcule le carry immédiatement — mais le principe de Smith et Nair explique pourquoi cette valeur est rarement lue, rendant l'optimisation envisageable.

Van der Linden (Expert C Programming, p.126-130) décrit le segment de pile et ses trois usages : stockage des variables locales, information de gestion des appels de fonction (enregistrement d'activation), et zone de travail temporaire. Il note que « A stack would not be needed except for recursive calls. If not for these, a fixed amount of space for local variables, parameters, and return addresses would be known at compile time and could be allocated in the BSS. » Le processus Corewar est un enregistrement d'activation simplifié : le PC (adresse de retour), le carry (statut), et les registres (variables locales). Sans fork (sans récurrence/branchement), une seule structure fixe suffirait — comme les premiers BASIC/COBOL/FORTRAN n'avaient pas de pile car ils ne permettaient pas la récursion.

Van der Linden (p.132) fait aussi le lien avec les threads : « It should now be clear how different threads of control can be supported within a process. Simply have a different stack dedicated to each thread of control. » Les processus Corewar sont exactement des threads légers — chacun avec son propre PC et ses registres (sa propre « pile »), la VM les ordonnanceant en round-robin. La liste des processus est une liste chaînée d'enregistrements d'activation stockés sur le tas, PAS sur la pile d'appels C. L'instruction zjmp est l'équivalent d'un longjmp (p.132-134) — elle transfère le contrôle à un PC différent. L'instruction fork est comme setjmp + longjmp combinés — elle sauve l'état courant et crée un duplicat à un nouveau PC.

Van der Linden (p.132-134) met en garde sur un piège critique : « The only reliable way to ensure that a local variable retains the value that it had at the time of the longjmp is to declare it volatile. » Ce conseil s'applique directement à la VM Corewar : l'arène est un tableau partagé modifié par plusieurs processus concurrents. Si le compilateur C optimise la boucle d'exécution en mettant en cache les lectures de arena[] dans des registres (pensant que la mémoire n'a pas changé depuis la lecture précédente), la VM lira des valeurs périmées. Le mot-clé volatile sur le pointeur d'arène — ou l'utilisation de fonctions d'accès mémoire qui forcent une relecture — est essentiel pour garantir que chaque instruction lit l'état réel de la mémoire, pas une copie obsolète en registre.

Van der Linden (p.129) explique aussi pourquoi l'état d'un processus Corewar peut être si compact (juste PC + carry + 16 registres) : « C does not allow functions to be nested this way. All functions in C are at the top lexical level. » Puisque C n'a pas de fonctions imbriquées, il n'a pas besoin de static link (pointeur vers l'enregistrement d'activation de la fonction englobante). Chaque fonction C est une entité plate et indépendante — exactement comme chaque processus Corewar. L'absence de contexte lexical englobant permet à l'état du processus d'être un bloc mémoire fixe et auto-suffisant, sans référence à une pile d'appels parente. C'est ce qui rend le fork si élégant : il suffit de dupliquer ce bloc fixe, sans avoir à recréer une hiérarchie de portées.

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.6, Theorem 6.2) démontre le théorème de récursion : pour toute fonction calculable f, il existe une machine de Turing qui produit sa propre description comme partie de son calcul. C'est le fondement théorique des quines (programmes qui impriment leur propre source) et des programmes auto-répliquants.

Un guerrier « vampire » de Corewar (qui écrit son propre code dans le chemin d'exécution de l'adversaire) est une application directe du théorème de récursion. Le guerrier doit pouvoir reconstruire son propre code — ou au moins un payload — à une adresse cible. Le théorème garantit que c'est toujours possible : il existe un guerrier qui, comme partie de sa stratégie de bombing, écrit une copie encodée de lui-même. L'instruction fork/lfork est la manifestation opérationnelle de l'auto-réplication : elle crée un nouveau PC exécutant le même code. Le théorème de récursion prouve que l'auto-réplication en Corewar n'est pas un hack mais une capacité computationnelle fondamentale — tout système Turing-complet peut contenir des quines, et l'arène Corewar n'y fait pas exception.

Le Dragon Book (Compilers, Ch.8, p.525) définit les blocs de base (basic blocks) comme : « Partition the intermediate code into basic blocks, which are maximal sequences of consecutive three-address instructions with the properties that (a) The flow of control can only enter the basic block through the first instruction… (b) Control will leave the block without halting or branching, except possibly at the last instruction. » Autrement dit, un bloc de base est une séquence d'instructions qui s'exécute toujours du début à la fin sans saut intermédiaire — une unité atomique de flot de contrôle.

En Corewar, lire et désassembler un guerrier ennemi nécessite d'identifier ses blocs de base. Les instructions séquentielles (live, ld, add, st, etc.) forment des blocs qui sont brisés par les instructions de branchement (zjmp, sti indirect). Le graphe de flot de contrôle (Control Flow Graph) qui en résulte révèle la structure du programme : boucles d'attaque, routines de copie, leurres. Les compilateurs modernes utilisent ce graphe pour optimiser le code ; en Corewar, un programme comme pMARS pourrait construire un CFG pour analyser la vulnérabilité d'un guerrier. Comprendre les points d'entrée et de sortie des blocs est crucial pour concevoir un guerrier résistant aux scanners ennemis : un bloc de base compact, sans point d'entrée intermédiaire, est beaucoup plus difficile à corrompre partiellement.

Hyde (The Art of Assembly Language, Ch.5.13, pp.293-294) décrit l'enregistrement d'activation (stack frame) : adresse de retour, registres sauvegardés, paramètres, variables locales, stockage temporaire. Le pointeur de base (EBP/RBP) pointe au milieu de cette structure pour un accès bidirectionnel. C'est la structure de données fondamentale permettant les appels de procédure.

Corewar n'a pas de pile, pas de EBP, pas d'enregistrement d'activation. Chaque « appel de sous-routine » dans un guerrier doit sauvegarder manuellement l'adresse de retour dans un registre ou une cellule connue de l'arène — et doit prier que cette cellule ne soit pas bombardée avant le retour. L'enregistrement d'activation rend explicite tout ce que le guerrier doit réimplémenter de zéro, ou faire sans. Un guerrier qui veut implémenter des « sous-routines » doit : (1) réserver des registres pour les adresses de retour, (2) manuellement empiler/dépiler les variables locales dans l'arène, (3) gérer les appels imbriqués avec un compteur de profondeur. Tout ce que la pile matérielle offre gratuitement, le guerrier doit le reconstruire dans l'arène — sachant que chaque cellule de « pile » est une cible potentielle pour le bombing adverse.

Le Dragon Book (Aho et al., Compilers, 2e éd., mentionné dans §12.2.1) et la littérature sur la compilation Just-In-Time (Ayers, Jung & Whaley, 1997; IPoPP) décrivent comment les JIT traduisent le bytecode en code natif au runtime, profilant d'abord l'exécution puis optimisant les chemins chauds. Les JIT Java profilent les invocations de méthodes et inlinent les cibles les plus fréquentes.

Une implémentation MARS en C ou Rust est essentiellement un interpréteur pour le bytecode Redcode. Un MARS basé sur JIT compilerait la boucle chaude de chaque guerrier (la boucle de bombing/scan) en code natif x86 ou ARM après avoir profilé quelques itérations. Le profil révélerait : quelles instructions sont les plus fréquemment exécutées (la boucle de bombing), quelles sont les valeurs typiques des opérandes (le pas dans un registre), et si les branchements sont pris ou non. Le JIT pourrait alors remplacer la boucle générique decode-execute par du code natif spécialisé pour la séquence d'instructions spécifique de chaque guerrier. Un MARS JIT traiterait chaque guerrier comme une méthode Java et compilerait sa boucle chaude en code natif — la boucle de bombing est le « hot path » par excellence.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.5, §5.4.2 et Ch.9, §9.3) décrivent la Static Single Assignment (SSA) comme la représentation IR dominante des compilateurs modernes : « a property of an IR that requires each value to be defined by exactly one instruction ». En SSA, chaque variable n'est définie qu'une seule fois — si un registre r1 est assigné à deux endroits, on le renomme en r1₁ et r1₂, et aux points de convergence (join points) on insère une φ-fonction qui « choisit » la bonne version selon le chemin d'exécution.

Le Redcode/Corewar 42 ne respecte pas SSA par construction. Un registre comme r2 peut être réécrit par ld, add, sub à n'importe quel point du programme. La conséquence est que l'analyse de flot de données d'un guerrier — déterminer quelle valeur un registre contient à un point donné — est beaucoup plus difficile que sur un programme en forme SSA. Cooper & Torczon montrent que SSA simplifie radicalement les optimisations : la propagation de constantes, l'élimination de code mort, et la détection de redondances deviennent des algorithmes linéaires au lieu de quadratiques. Sans SSA, chaque optimisation doit faire sa propre analyse de réaching definitions.

L'équivalent « manuel » de SSA en Corewar est la discipline de nommage strict : un programmeur qui n'utilise chaque registre qu'une seule fois comme destination simplifie son propre raisonnement et facilite l'analyse manuelle du code. Mais cette discipline est rarement suivie car les 16 registres sont une ressource trop rare pour se permettre le luxe du single-assignment. Cooper & Torczon notent d'ailleurs que la construction de SSA nécessite un nombre de noms proportionnel au nombre de définitions — dans un guerrier avec 16 registres et des dizaines d'instructions, le nombre de versions SSA exploserait bien au-delà de la capacité matérielle. Corewar illustre le compromis fondamental entre la facilité d'analyse (SSA) et l'économie de ressources (réutilisation de registres) — les 16 registres forcent le non-SSA par nécessité.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.11, §11.1-11.3) décrivent la sélection d'instructions comme le problème de choisir la séquence d'instructions machine la plus efficace pour implémenter une opération de haut niveau. Le compilateur dispose d'un ensemble de patterns (motifs d'instructions) et doit choisir la couverture optimale — celle qui minimise un coût (cycles, taille, énergie). La technique du tree-pattern matching (§11.3) décompose l'AST en tuiles (tiles), chaque tuile correspondant à une instruction machine.

En Corewar, la sélection d'instructions est le choix entre séquences équivalentes pour implémenter une même opération. Par exemple, pour copier la valeur de r1 vers l'adresse pointée par r2 : le novice écrit ld r1, r3 / sti r3, r2, %0 (2 instructions), l'expert écrit sti r1, r2, %0 (1 instruction). De même, pour incrémenter r2 de 50 et bomber : add r2, %50, r2 / sti r1, r2, %0 (2 instructions) vs. utiliser l'adressage pour fusionner l'incrémentation dans l'opération. Cooper & Torczon (§11.4) décrivent le DAG-based instruction selection qui traite les opérations communes une seule fois — l'équivalent manuel est de repérer les sous-expressions communes et de les calculer une seule fois dans un registre. En Corewar, chaque instruction économisée est un cycle gagné — la sélection d'instructions n'est pas un détail, c'est l'optimisation fondamentale.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.6) consacrent un chapitre entier à l'abstraction procédurale — la mécanique par laquelle un programme appelle une fonction, lui passe des paramètres, récupère son résultat, et reprend l'exécution. Cette mécanique repose sur quatre piliers : (1) la pile d'exécution (call stack) qui empile les activation records (AR) ; (2) le registre de lien (return address) qui permet de revenir à l'appelant ; (3) les conventions d'appel (calling conventions) qui définissent comment passer les paramètres et les valeurs de retour ; (4) l'allocation de l'AR qui réserve l'espace pour les variables locales, les paramètres, et le bookkeeping.

Corewar supprime ces quatre piliers. Pas de pile d'exécution (un processus a un PC linéaire, pas de call stack). Pas de registre de lien (pas d'instruction call/ret, pas de jal MIPS ou BLK x86). Pas de convention d'appel (pas de fonctions, pas de paramètres formels). Pas d'activation record (les 16 registres et le carry sont le seul « contexte » d'un processus). Cooper & Torczon (§6.3) décrivent comment l'AR est alloué sur la pile à chaque appel — en Corewar, le seul « allocation » est le fork/lfork qui crée un nouveau processus (un nouveau PC) sans AR ni pile. Le fork est à l'appel de procédure ce que le clonage est à la reproduction sexuée — au lieu de combiner deux moitiés (appelant + appelé) dans un cadre partagé, le fork crée une copie complète et indépendante.

Cooper & Torczon (§6.4.1) décrivent aussi les mécanismes de passage de paramètres — call by value, call by reference, call by name. En Corewar, le seul mécanisme de communication entre processus est la mémoire partagée — l'arène elle-même. C'est un call by sharing implicite : tous les processus d'un même guerrier partagent les mêmes cellules mémoire et peuvent y lire et écrire, mais n'ont pas de registres partagés. La coordination se fait par « side effect » sur l'arène — le seul canal de communication. Corewar pousse la programmation à son stade pré-procédural : pas d'abstraction, pas d'encapsulation, seulement des processus indépendants qui communiquent par écriture dans un espace partagé.

Hyde (The Art of Assembly Language, §8.1.2, p.481-484) décrit l'addition multiprécision avec adc (add with carry) : « the only difference between the add and adc instructions is that the adc instruction adds in the value of the carry flag along with the source and destination operands. » En x86, pour additionner deux entiers de 64 bits sur une machine 32-bit, on ajoute les mots bas avec add, puis les mots hauts avec adc qui propage la retenue. Le carry est le canal de communication entre les deux additions — il relie le résultat partiel du mot bas à l'addition du mot haut.

Ce modèle de carry-chaîne s'applique à la VM Corewar de façon surprenante. Bien que Corewar n'ait pas d'instruction adc, le carry persiste entre les instructions d'un même processus — il est positionné par une instruction et lu par la suivante. Cette persistance est exactement le mécanisme de l'addition multiprécision : le carry de l'instruction N est l'entrée implicite de l'instruction N+1. Quand un guerrier enchaîne ld %val, r1 (positionne carry si val = 0) puis zjmp %label (saute si carry = 1), le carry est le canal de communication entre le calcul et la décision — exactement comme adc chaîne les additions. Hyde montre aussi que sbb (subtract with borrow) est la version soustraction de adc : « At the end of the extended-precision addition sequence, the carry flag indicates unsigned overflow (if set). » En Corewar, le carry après add/sub indique si le résultat a débordé — la même sémantique que dans l'addition multiprécision. Le carry Corewar est le maillon d'une chaîne multiprécision implicite : chaque instruction hérite de l'état de la précédente, exactement comme adc hérite du carry de add.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.6.2, pp.272-274) décrivent la convention d'appel (linkage convention) : un accord entre compilateur et OS définissant comment appeler une procédure — où placer les paramètres, comment retourner les valeurs, qui sauvegarde/restaure les registres. Sans elle, le code compilé séparément ne peut pas interopérer.

Corewar n'a aucune convention d'appel. Même si deux processus voulaient coopérer comme appelant/appelé, ils ne pourraient pas s'entendre sur la façon de passer des données. SPL partage l'arène, pas des paramètres. Il n'y a pas de registre dédié pour le retour (rax en x86, v0 en MIPS), pas de pile pour les arguments, pas de registre sauvé par l'appelant vs l'appelé. Deux processus qui veulent communiquer doivent inventer leur propre protocole ad hoc — un « contrat social » que chaque guerrier doit réinventer seul. L'absence de convention d'appel est à la fois la liberté du guerrier (aucune contrainte) et sa limitation (aucune infrastructure de coopération).

Le Dragon Book (Aho et al., Compilers, 2e éd., Ch.7, §7.7.4) décrit le ramasse-miettes générationnel : les objets sont partitionnés par âge, les jeunes étant collectés plus fréquemment car ils meurent tôt (« weak generational hypothesis »). Les objets matures sont collectés rarement. Cette approche exploite l'observation empirique que la plupart des objets ont des durées de vie courtes.

Le mécanisme CYCLE_TO_DIE est une forme de GC générationnel pour les processus. Chaque processus commence « jeune » (aucun live_count), et doit prouver sa viabilité en appelant live avant le prochain check. Les processus qui ne se signalent pas sont « collectés » (tués) — exactement comme la collection de la jeune génération. À mesure que CYCLE_TO_DIE décroît (chaque NBR_LIVE décrémente de 50), la collection devient plus agressive, reflétant la pression GC quand la mémoire se raréfie. Les processus qui survivent à plusieurs vérifications sont « matures » — ils ont démontré leur robustesse. CYCLE_TO_DIE implémente un collecteur générationnel où chaque vérification est une GC mineure, et la décroissance du seuil mime le passage de la collection jeune à la collection complète.

Hyde (The Art of Assembly Language, §10.3) décrit le carry flag comme un accumulateur 1-bit : « Because these instructions place their 'bit result' in the carry flag, it is often convenient to think of the carry flag as a 1-bit register or accumulator for bit operations. » En x86, le carry flag est un accumulateur universel — les instructions bt, shift et rotate y placent leur résultat, puis jc/jnc le testent, adc/sbb l'intègrent dans une arithmétique, et rcl/rcr le fusionnent dans un registre. C'est un pipeline bit-à-bit : calculer dans le carry, puis utiliser le carry comme entrée de l'opération suivante.

Le carry de Corewar est la réduction minimaliste de ce concept. Là où l'x86 possède 6 flags (CF, ZF, SF, OF, PF, AF) et le Y86-64 en a 3 (ZF, SF, OF), Corewar n'en garde qu'un seul : le carry, qui vaut 1 quand le résultat d'une opération arithmétique ou logique est nul. Cette réduction à un seul flag est à la fois une contrainte et une élégance : le seul branchement conditionnel (zjmp) teste exclusivement le carry, et les seules instructions qui le modifient sont and, or, xor, add, sub, ld, lld, ldi, lldi. Pas de flag de signe (SF), pas de flag de débordement (OF) — si un guerrier veut tester si un résultat est négatif, il doit le déduire du carry combiné avec la connaissance du bit de poids fort. Hyde montre que le carry est suffisant pour implémenter n'importe quelle logique binaire — il suffit de composer les opérations. Corewar démontre qu'un seul accumulateur 1-bit est Turing-suffisant pour le contrôle de flux : toute décision se réduit à « le résultat est-il nul ? ».

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.1, §1.2) établit que tout langage régulier a un DFA minimal unique (à isomorphisme près). L'algorithme de minimisation fusionne les états indistinguables — ceux qui produisent la même sortie pour toute continuation possible.

Un bomber avec un pas S visite les adresses S, 2S, 3S, ... modulo 4096. Cela peut se modéliser comme un DFA sur l'arène. La minimisation de ce DFA révèle le nombre essentiel d'états distincts — qui est 4096/PGCD(S, 4096). Un pas de 4 a 1024 états distincts ; un pas de 3 en a 4096 (couverture complète). La minimisation dit au programmeur la redondance exacte de son pattern de bombing : si PGCD(S, 4096) > 1, le bomber n'atteint jamais certaines cellules, et son DFA a des états redondants éliminables — mais les états éliminés représentent des adresses que le bomber ne touchera jamais, une faille fatale. Le choix du pas de bombing est donc un choix de taille de DFA : un pas qui produit un DFA minimal de 4096 états couvre toute l'arène, tandis qu'un pas avec un DFA de 1024 états laisse 3/4 de l'arène inviolée.

Dans clox (la VM bytecode de Crafting Interpreters), chaque chunk de bytecode est accompagné d'un pool de constantes — un tableau séparé contenant les littéraux (nombres, chaînes) référencés par index dans les instructions OP_CONSTANT. Le header .cor joue exactement ce rôle : il contient le nom du champion (une constante chaîne) et la taille du code (une constante numérique), stockés séparément du bytecode lui-même. Nystrom explique que ce découplage est crucial : mettre les données volumineuses directement dans le flux d'instructions ruinerait la densité et la localité spatiale. Le Corewar pousse cette logique encore plus loin — le header est totalement séparé du corps, et l'arène ne contient que des instructions brutes, sans métadonnées. C'est l'ultimate expression du principe « le bytecode ne doit contenir que ce que la VM exécute ».

Le Dragon Book (Aho et al., Compilers, 2e éd., Ch.6, §6.5) établit que le type checking garantit que les opérateurs reçoivent des opérandes de types compatibles. Un système de types sound élimine le besoin de vérification de types au runtime. Le Dragon Book note : « A language in which the type of any data component can be determined is said to be type safe. »

L'octet ACP (Argument Code Byte) dans le format .cor est un type tag runtime pour chaque opérande d'instruction : 01 = registre, 10 = direct, 11 = indirect. MARS utilise cette information de type pour décoder comment interpréter chaque opérande — exactement comme un langage dynamiquement typé utilise des type tags au runtime. L'ACP rend chaque instruction Corewar type-safe par construction : il n'y a pas de type d'opérande indéfini, et la VM peut toujours déterminer comment lire chaque argument. C'est un système de types minimal — trois types seulement — mais il est complet au sens où toute instruction valide a un typage non ambigu. L'ACP est le système de types de Corewar — un type tag par instruction, par opérande, garantissant la sécurité du décodage. Sans l'ACP, la VM devrait déduire le type de chaque opérande depuis l'opcode seul (comme le fait l'ICWS'94), ce qui est possible mais moins extensible et moins sûr.

Crafting Interpreters implémente un compilateur single-pass (une seule passe) où le parsing et la génération de code sont entrelacés. Nystrom explique que ce design est possible parce que Lox est un langage dynamiquement typé où « on n'a pas besoin de beaucoup de contexte environnant pour comprendre un bout de syntaxe ». L'assembleur Corewar, lui, ne peut PAS être single-pass à cause des labels en référence avant : jmp :label où :label est défini plus bas. C'est exactement le problème que rencontraient les compilateurs C historiques : C exige les forward declarations (void foo();) précisément parce qu'il a été conçu pour un compilateur single-pass sur des machines avec très peu de mémoire. La solution de l'assembleur Corewar — deux passes — est le même compromis que Pascal : la première passe collecte les adresses, la seconde génère le code résolu.

Levine (Linkers and Loaders, Ch.7) détaille les mécanismes de relocation : sur SPARC et MIPS, les instructions n'ont pas la place pour stocker une adresse 32-bit complète, donc un champ addend dans l'entrée de relocation porte la valeur complémentaire. Le linker combine l'addend avec la base du segment pour calculer l'adresse finale. Corewar évite entièrement ce problème : chaque champ opérande stocke directement le décalage relatif (modulo la taille du core), et la VM calcule l'adresse effective au runtime par (PC + offset) % CORE_SIZE. Pas d'addend, pas de table de relocation, pas de fixup au chargement. Levine décrit aussi les références chaînées : les entrées de relocation forment une liste chaînée dans le code objet, chaque entrée pointant vers la suivante. L'adressage indirect @ de Corewar est l'équivalent runtime : au lieu que le linker suive la chaîne de fixups à l'édition des liens, la VM suit la chaîne de pointeurs à l'exécution. Le .cor élimine la relocation à la compilation, l'addend à l'encodage, et le fixup au chargement — trois problèmes résolus par un seul choix : l'adressage relatif.

Levine (Ch.7, §7.2) distingue deux phases de relocation : la link-time relocation (combinaison des segments de différents fichiers objet en une image unique) et la load-time relocation (ajustement de l'image finale pour son adresse réelle en mémoire). Corewar n'a ni l'une ni l'autre. Il n'y a pas de link-time car il n'y a qu'un seul fichier source (.s → .cor) sans combinaison de modules. Il n'y a pas de load-time car tous les adressages sont relatifs — le loader se réduit à un simple memcpy vers l'arène. C'est le cas le plus trivial décrit par Levine : « no load-time relocation is needed ». Mais Corewar pousse la simplification encore plus loin : même la relocation à l'édition des liens (résolution des labels en offsets) est faite par l'assembleur en une seule passe, pas par un linker séparé. Le .cor est le format objet ultime pour un monde sans linker : la compilation est la dernière étape, et le chargement est un copié-collé.

Le Dragon Book (Ch.2.2, p.42-44) définit la forme de Backus-Naur (BNF) comme la notation standard pour décrire la syntaxe d'un langage de programmation : une grammaire hors-contexte (Context-Free Grammar) où chaque règle de production spécifie comment un symbole non-terminal peut être remplacé par une séquence de terminaux et de non-terminaux. Avant de coder l'assembleur, il est essentiel de modéliser le langage mathématiquement. Voici un extrait de la grammaire BNF de l'assembleur Corewar 42 :

<program> ::= <line>*
<line> ::= <label_def>* <instruction>? <comment>? NEWLINE
<label_def> ::= IDENTIFIER ":"
<instruction> ::= OPCODE <params>
<params> ::= <param> ("," <param>)*
<param> ::= REGISTER | DIRECT | INDIRECT
<DIRECT> ::= "%" (INTEGER | ":" IDENTIFIER)
<INDIRECT> ::= INTEGER | ":" IDENTIFIER
<REGISTER> ::= "r" DIGIT{1,2}
<comment> ::= "#" CHAR*

Cette grammaire est hors-contexte (le Dragon Book les appelle « Type-2 » dans la hiérarchie de Chomsky) car chaque règle de production a un seul symbole non-terminal à gauche — la substitution ne dépend pas du contexte environnant. C'est ce qui permet l'analyse par descente récursive : chaque fonction de parsing correspond à un non-terminal. La fonction parse_line() appelle parse_label_def() puis parse_instruction(), qui appelle parse_params(), qui appelle parse_param() — un arbre d'appels qui reflète exactement l'arbre de dérivation BNF.

La propriété LL(1) de cette grammaire se vérifie directement : après avoir lu l'opcode, le parseur sait exactement combien de <param> attendre et quels types sont légaux (le sujet 42 spécifie pour chaque opcode les types autorisés via op.h). Un seul token de lookahead suffit pour désambiguïser : % annonce un DIRECT, r un REGISTER, un chiffre ou : un INDIRECT. Modéliser en BNF avant de coder garantit que la grammaire est non-ambiguë et que le parseur sera correct par construction.

Levine (Linkers and Loaders, 2000, Ch.3, p.46-50) et Saloman (Assemblers and Loaders, 1993, Ch.4) décrivent les macros d'assembleur comme un mécanisme de substitution textuelle : une macro définit un template (nom + paramètres → corps), et chaque invocation est remplacée par le corps instancié. Les macros permettent d'abstraire des patterns répétitifs sans le coût d'un appel de fonction. Les directives conditionnelles (#ifdef, #if) permettent de sélectionner du code à l'assemblage selon des conditions — par exemple, compiler du code de débogage uniquement en mode test. Levine montre que ces mécanismes sont traités dans une phase de préprocessing avant l'assemblage proprement dit : le préprocesseur expanded les macros, évalue les conditions, puis l'assembleur voit uniquement du code « plat » sans macros ni conditionnelles.

L'assembleur Corewar ne supporte ni macros ni assemblage conditionnel — et ce n'est pas un accident. Le format .s est délibérément minimal : chaque instruction correspond à exactement un encodage binaire, sans couches d'abstraction. L'absence de macros signifie que les patterns répétitifs doivent être dupliqués manuellement — un guerrier qui bombe à trois adresses différentes doit écrire trois fois la séquence sti / add / zjmp avec des paramètres différents. L'absence de conditionnelles signifie qu'on ne peut pas avoir un code qui s'adapte au nombre de joueurs ou à la taille de l'arène — le guerrier est figé dans sa stratégie. Saloman (Ch.4, §4.3) note que les macros introduisent une phase de compilation supplémentaire et augmentent la surface de bugs (expansion infinie, portée des labels, effets de bord dans les paramètres). En Corewar, cette complexité est évitée par choix — le langage .s est un assembleur de bas niveau sans sucre syntaxique. Mais rien n'empêche un programmeur d'écrire un méta-assembleur externe qui génère du .s à partir d'un langage de plus haut niveau avec macros et conditions — puis de passer le résultat à l'assembleur standard. L'absence de macros est une restriction du langage, pas de la machine — le bytecode .cor ne connaît pas la différence entre du code écrit à la main et du code généré.

Cooper et Torczon (Engineering a Compiler, 2e éd., Ch.10, §10.3.1) décrivent le Loop-Invariant Code Motion (LICM) : identifier les calculs à l'intérieur d'une boucle qui produisent le même résultat à chaque itération et les déplacer avant la boucle. L'optimisation est formellement : si une expression e dans la boucle L ne dépend d'aucune définition variant à chaque itération de L, alors e est « loop-invariant » et peut être calculé une seule fois avant L.

En Corewar, le LICM est l'optimisation manuelle la plus importante. Considérez un bomber naïf : ld %DAT_val, r1 / sti r1, r2, %0 / add %step, r2, r2 / zjmp %-4. La première instruction ld %DAT_val, r1 charge la même valeur de DAT à chaque itération — elle est loop-invariant. L'optimisation est de la sortir du loop : ld %DAT_val, r1 / sti r1, r2, %0 / add %step, r2, r2 / zjmp %-3. Le loop passe de 4 à 3 instructions, économisant 25% des cycles. De même, charger la constante de step dans un registre avant la boucle plutôt que d'utiliser un immédiat à chaque ADD est du LICM : ld %step, r3 avant la boucle, puis add r3, r2, r2 dans la boucle — l'immédiat coûte un encodage plus long et parfois un décodage plus complexe. Cooper et Torczon notent que le LICM est souvent combiné avec la réduction de force (déjà traitée) : après avoir sorti les invariants, les calculs restants dans la boucle peuvent être remplacés par des opérations plus simples. En Corewar, chaque instruction sortie de la boucle est un cycle gagné par itération — et sur des milliers d'itérations, un seul cycle economies fait la différence entre la victoire et la défaite.

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.8, Theorem 8.5) démontre le théorème de Savitch : PSPACE = NPSPACE. Tout problème résoluble en espace polynomial nondéterministement l'est aussi en espace polynomial déterministement, au coût d'un carré sur l'espace.

Un match Corewar entre guerriers déterministes est dans PSPACE. Avec des stratégies randomisées (scanners à pas aléatoire), on entre dans NPSPACE. Le théorème de Savitch garantit que ces classes sont identiques en espace. Cela signifie qu'un scanner déterministe peut explorer le même espace d'états qu'un scanner aléatoire — il a juste besoin de quadratiquement plus d'espace (irrelevant dans 4096 octets). La randomisation en Corewar est une heuristique de vitesse, pas une nécessité théorique — Savitch dit que le déterminisme rattrape toujours le hasard, si on lui donne assez de patience.

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.4, Theorems 4.1 et 4.5) établit que le problème de l'emptiness et de l'équivalence pour les langages réguliers sont tous deux décidables. Pour les langages algébriques (CFL), l'emptiness est décidable mais l'équivalence est indécidable.

Un scanner warrior en pattern fixe est essentiellement un DFA sur l'arène. La décidabilité de l'équivalence pour les langages réguliers signifie qu'il existe un algorithme pour vérifier si deux scanners sont stratégiquement identiques. Pour des guerriers plus complexes (avec branching conditionnel), l'équivalence devient indécidable — comparer les stratégies de deux guerriers est algorithmiquement infaisable dans le cas général. La hiérarchie de décidabilité reflète la hiérarchie de complexité des guerriers : scanners décidables, vampires indécidables.

Le Dragon Book (Aho et al., Compilers, 2e éd., Ch.11, §11.2) décrit le cache tiling (blocking) : restructurer les boucles imbriquées pour opérer sur des sous-blocs qui tiennent en cache, réduisant les misses de O(n³/c) à O(n²/c).

Un vampire ou « pit-trapper » qui écrit des pièges multi-instructions à intervalles réguliers est une boucle à deux niveaux. Le principe du tiling s'applique : en réordonnant quel piège est écrit en premier (localité spatiale entre pièges) vs. quelle instruction est écrite en premier (localité temporelle dans un piège), le guerrier minimise les accès éloignés. Dans l'arène, « cache » signifie la fenêtre IDX_MOD — les accès au-delà de ±512 sont plus coûteux. Le tiling de la boucle de pièges pour rester dans les fenêtres IDX_MOD réduit le coût effectif de chaque piège.

Bryant & O'Hallaron (Computer Systems: A Programmer's Perspective, 3e éd., Ch.3, §3.7) décrivent la convention d'appel System V AMD64 ABI : 6 registres arguments (rdi, rsi, rdx, rcx, r8, r9), registre retour rax, caller-saved vs callee-saved, alignement de la pile à 16 octets, shadow space. La convention d'appel est le contrat social du logiciel — sans elle, les fonctions ne peuvent pas cooperer car elles ne savent pas où trouver leurs arguments ni où laisser leurs résultats.

En Corewar, il n'y a aucune convention d'appel — et pour cause : il n'y a pas d'appel. Pas de CALL, pas de RET, pas de pile, pas de frame pointer. Les 16 registres n'ont aucune sémantique prédéfinie — seul r1 est initialisé avec le numéro du joueur au boot, et c'est la seule « convention » existante. Un guerrier peut utiliser r2 comme pointeur de bombing, r3 comme compteur de pas, r4 comme valeur de l’opcode 0x00 — mais ces choix sont entièrement arbitraires. L'absence de convention signifie qu'il n'y a pas d'interface standard entre « composants » d'un guerrier — chaque programmeur invente sa propre organisation des registres. C'est l'état de nature hobbesien du logiciel : pas de loi, pas de contrat, seulement la survie. En Corewar, la convention d'appel n'existe pas — chaque guerrier est une loi à lui-même, et r1 est le seul citoyen connu.

Sipser (Introduction to the Theory of Computation, 3e éd., Ch.4, §4.2) démontre par la diagonalisation de Cantor que l'ensemble des langages sur {0,1} est non dénombrable, tandis que l'ensemble des machines de Turing est dénombrable. Donc la plupart des langages sont indécidables. La diagonalisation construit explicitement un langage qui diffère de chaque machine de Turing énumérée sur sa propre diagonale.

L'ensemble de tous les guerriers Corewar possibles (programmes de jusqu'à CHAMP_MAX_SIZE octets) est fini (au plus 256^682 possibilités), donc dénombrable. Mais l'ensemble de toutes les stratégies possibles (les mappings du comportement adverse vers la réponse) est non dénombrable. Ce gap explique pourquoi aucun ensemble fini de guerriers ne peut être universellement optimal — l'espace stratégique est infiniment plus riche que l'espace programmatique. La diagonalisation prouve que pour chaque champion, il existe un anti-champion construit en diagonalisant contre son comportement. C'est la formalisation mathématique de l'intuition Corewar : il n'y a pas de guerrier invincible, car l'espace des contre-stratégies est infiniment plus vaste que l'espace des programmes.

Le Dragon Book (Compilers, Ch.9, p.104-106) définit l'analyse de vivacité (live-variable analysis) : « In live-variable analysis we wish to know for variable x and point p whether the value of x at p could be used along some path in the flow graph starting at p. If so, we say x is live at p; otherwise, x is dead at p. » Cette analyse est rétrograde (backward) : l'information remonte du point de sortie vers le point d'entrée, car on veut savoir si une utilisation future existe.

En Corewar, l'analyse de vivacité est l'outil qui permet de répondre à la question : cette instruction est-elle vraiment nécessaire ? Si un registre est mort après un bloc (sa valeur ne sera jamais lue), toute instruction qui y écrit est du code mort. Si un registre est vivant à la sortie d'un bloc, il doit être préservé — ce qui détermine si un st (spill) est nécessaire avant un saut. L'information de prochaine utilisation (next-use, Ch.8 p.24) est la version locale de cette analyse : « Knowing when the value of a variable will be used next is essential for generating good code. If the value of a variable that is currently in a register will never be referenced subsequently, then that register can be assigned to another variable. » En pratique Corewar, si vous chargez un registre et ne le relisez jamais, l'instruction de chargement est morte — supprimez-la et gagnez un cycle.

Le Dragon Book (Compilers, Ch.9, p.86-87) décrit la propagation de copies : « The idea behind the copy-propagation transformation is to use v for u, wherever possible after the copy statement u = v. » En Corewar, après un ld r1, r2 (copie), toutes les utilisations suivantes de r2 peuvent être remplacées par r1 — et si r2 n'est plus jamais utilisé différemment de r1, la copie elle-même peut être éliminée. C'est un nettoyage systématique des registres redondants.

L'élimination globale des sous-expressions communes (p.84-85) étend ce principe au-delà d'un bloc : « An occurrence of an expression E is called a common subexpression if E was previously computed and the values of the variables in E have not changed since the previous computation. » Si deux blocs différents du guerrier calculent le même offset de bombe avec les mêmes valeurs d'entrée, un seul calcul suffit — le résultat est réutilisé. La propagation de copies et la disponibilité d'expressions (p.106-110) travaillent ensemble : une expression est « disponible » si elle a été calculée sur tous les chemins menant à ce point sans que ses opérandes n'aient été modifiés. Ne pas recalculer une expression disponible est l'équivalent Corewar du cache hit — zéro cycle au lieu d'un.

Le Dragon Book (Compilers, p.133) définit le rôle du lexer : « As the first phase of a compiler, the main task of the lexical analyzer is to read the input characters of the source program, group them into lexemes, and produce as output a sequence of tokens for each lexeme in the source program. » Dans Corewar, l'assembleur doit tokeniser six types de lexèmes : les labels (suite alphanumérique se terminant par :), les mnémoniques d'instructions (mots-clés comme live, ld, sti), les références de registre (r1–r16), les valeurs directes (%42 ou %:label), les valeurs indirectes (42 ou :label), et les commentaires (#...).

Le Dragon Book (p.134) distingue trois concepts clés : le token (la catégorie abstraite, comme « registre »), le pattern (la règle qui définit la forme, comme « r suivi de 1-2 chiffres de 1 à 16 »), et le lexème (la séquence concrète de caractères, comme « r14 »). Un lexer Corewar doit aussi distinguer les mnémoniques d'instructions des labels — le Dragon Book (p.102) appelle cela la keyword identification : « Most languages use fixed character strings such as for, do, and if, as punctuation marks or to identify constructs. Such character strings are called keywords. Keywords generally satisfy the rules for forming identifiers, so a mechanism is needed for deciding when a lexeme forms a keyword and when it forms an identifier. »

Le Dragon Book recommande aussi de séparer le lexer en deux sous-processus (p.133) : le scanning (suppression des commentaires et espaces) et l'analyse lexicale proprement dite (tokenisation). C'est exactement ce que fait votre assembleur quand il ignore les lignes vides et les commentaires avant de parser les tokens. Enfin, le livre souligne l'importance du numéro de ligne dans les messages d'erreur (p.133) : « The lexical analyzer may keep track of the number of newline characters seen, so it can associate a line number with each error message. » — une pratique essentielle pour que l'utilisateur puisse localiser rapidement l'erreur dans son fichier .s.

Le Dragon Book (Compilers, p.111) établit la triade fondamentale de l'analyse lexicale : « A token is a pair consisting of a token name and an optional attribute value. [...] A pattern is a description of the form that the lexemes of a token may take. [...] A lexeme is a sequence of characters in the source program that matches the pattern for a token. » L'assembleur Corewar distingue les tokens : noms d'opcodes (live, ld, sti), références de registres (r1–r16), labels, nombres, séparateurs (,, %). Chaque catégorie a un pattern (ex: r[0-9]+ pour les registres, [a-zA-Z_][a-zA-Z0-9_]*: pour les labels) et un lexème (le texte concret matché).

Le Dragon Book (p.79, p.132) décrit la stratégie pour les mots réservés : « Keywords generally satisfy the rules for forming identifiers, so a mechanism is needed for deciding when a lexeme forms a keyword and when it forms an identifier. The problem is easier to resolve if keywords are reserved. [...] Install the reserved words in the symbol table initially. » Les 16 opcodes Corewar sont des mots réservés : live, ld, st, etc. ne peuvent pas être utilisés comme noms de labels. La stratégie « pré-semer la table des symboles » est exactement ce que l'assembleur doit faire : initialiser une table de hachage avec les noms d'opcodes mappés à leurs types de tokens, pour distinguer immédiatement un opcode d'un label.

Le Dragon Book (p.219-222) identifie l'assembleur Corewar comme un parseur LL(1) naturel : « Predictive parsers, that is, recursive-descent parsers needing no backtracking, can be constructed for a class of grammars called LL(1). The first 'L' stands for scanning the input from left to right, the second 'L' for producing a leftmost derivation, and the '1' for using one input symbol of lookahead. » Le format .s est naturellement LL(1) : le token opcode détermine univoquement le format de l'instruction (combien de paramètres, quels types). Un seul token de lookahead — l'opcode — suffit pour choisir la bonne règle de production. Pas de backtrack nécessaire.

Pour la table des symboles, le Dragon Book (p.86-89) décrit les tables chaînées par portée : « The most-closely nested rule for blocks can be implemented by chaining symbol tables. That is, the table for a nested block points to the table for its enclosing block. » En Corewar, les labels locaux (préfixés par un point) ont une portée délimitée par les labels non-pointés — exactement le modèle des blocs imbriqués avec la règle du « plus proche englobant ». La table des labels est un dictionnaire {nom → offset}, et les labels locaux créent une nouvelle portée à chaque label non-point, comme les tables de symboles chaînées du Dragon Book.

Aho, Lam, Sethi & Ullman (Compilers: Principles, Techniques, and Tools, 2e éd., « Dragon Book », §4.4, p.258-263) décrivent les stratégies de récupération d'erreurs dans les compilateurs : panic-mode (sauter les tokens jusqu'à un synchronisation token), phrase-level (remplacer le token erroné), error productions (étendre la grammaire pour capturer les erreurs communes), et global correction (trouver la correction minimale). Le défi est de détecter assez d'erreurs en un seul passage pour guider le programmeur, sans que les messages d'erreur en cascade ne submergent l'utilisateur.

L'assembleur Corewar (le programme asm qui convertit .s en .cor) doit implémenter une récupération d'erreurs robuste. Les erreurs possibles sont : label non défini, registre hors limites (r17), paramètre de type incorrect (T_IND où T_REG est attendu), opcode inconnu, doublon de label, et déclaration .name/.comment manquante. La stratégie panic-mode est la plus appropriée : quand une erreur est détectée, l'assembleur saute jusqu'au prochain point de synchronisation (la prochaine instruction ou le prochain label) et continue l'analyse. Cela permet de signaler plusieurs erreurs en une seule compilation plutôt que de s'arrêter à la première. Le Dragon Book (§4.4.3) note que les erreurs en cascade sont le principal danger : une seule erreur réelle peut générer des dizaines de faux messages si la récupération est mal conçue. En Corewar, une instruction mal encodée peut décaler l'interprétation de toutes les suivantes — c'est exactement le problème de synchronisation que le panic-mode résout. Un bon assembleur Corewar est un compilateur avec error recovery — pas juste un validateur qui s'arrête au premier problème.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.8, §8.5, p.474-479) décrivent le Dead Code Elimination (DCE) : identifier et supprimer les calculs dont le résultat n'est jamais utilisé. Le DCE repose sur l'analyse de liveness : une valeur est vivante si elle sera lue avant d'être réécrite. Un calcul qui produit une valeur morte peut être éliminé sans affecter le comportement du programme. Cooper & Torczon distinguent le DCE syntactique (supprimer le code inaccessible — après un return ou un zjmp inconditionnel) du DCE sémantique (supprimer les calculs dont le résultat n'est jamais lu, même s'ils sont atteignables).

En Corewar, le DCE sémantique est un outil de diagnostic précieux. Un guerrier qui charge une valeur dans r3 sans jamais lire r3 fait du calcul mort — gaspillant un cycle et un registre. Un guerrier qui add deux registres mais n'utilise jamais le résultat gaspille des cycles. L'assembleur Corewar ne fait pas de DCE automatique (il assemble littéralement ce qu'on lui donne), mais un désassembleur ou un analyseur statique pourrait détecter ces calculs morts. Cooper & Torczon (§8.5.2) décrivent l'algorithme itératif de DCE : itérer sur les instructions en ordre inverse, marquer les résultats utilisés, et supprimer les instructions non marquées. En Corewar, le CFG d'un guerrier est suffisamment simple (boucle de boot + boucle principale) pour que cette analyse soit faisable à la main. Chaque instruction qui produit un résultat non utilisé est un cycle volé au guerrier — le DCE est l'optimisation la plus sous-estimée en Corewar.

Le Dragon Book (Compilers, Ch.8, p.32) définit le constant folding : « Here we evaluate constant expressions at compile time and replace the constant expressions by their values. Thus the expression 2 * 3.14 would be replaced by 6.28. » En Corewar, cela signifie que tout calcul dont les opérandes sont connus à l'assemblage (offsets de bombe, pas de balayage, adresses de saut) doit être pré-calculé par le macro-assembleur et non par le guerrier à l'exécution. Chaque add ou sub calculant une constante est un cycle volé à l'attaque.

Le Dragon Book (Ch.9, p.128-132) étend cela à la propagation de constantes : suivre le flux de données pour déterminer si un registre contient une valeur constante à chaque point du programme. Si r1 contient toujours 5 après le boot, toute instruction add r1, r2 peut être remplacée par add #5, r2 — voire supprimée si le résultat est immédiatement écrasé. Le Dragon Book note que la propagation de constantes est monotone mais non distributive (p.131) : l'algorithme itératif donne une solution sûre mais potentiellement sous-optimale. Pour le guerrier Corewar, cela signifie que certaines optimisations de constantes seront manquées par une analyse automatisée — l'œil humain reste irremplaçable.

Crafting Interpreters distingue deux métriques fondamentales pour évaluer un ramasse-miettes : le débit (throughput — fraction du temps passé à exécuter le code utilisateur vs le GC) et la latence (temps de pause maximal pendant une collection). Ce compromis s'applique directement à l'ordonnancement MARS : un ordonnanceur qui donne beaucoup de cycles par tour à chaque processus maximise le débit (moins de changements de contexte) mais augmente la latence (un processus peut monopoliser le CPU). À l'inverse, le round-robin strict de MARS (1 instruction par processus par cycle) minimise la latence mais paie un coût en débit (changement de contexte constant). Nystrom compare ça à une boulangerie : le débit, c'est le nombre de baguettes par jour ; la latence, c'est le temps d'attente du client le plus malchanceux. Corewar choisit la faible latence — chaque processus est servi équitablement, un cycle à la fois.

Smith et Nair (Virtual Machines, p.107-110) décrivent le problème du code auto-modifiant dans les machines virtuelles : « Occasionally, an application program either refers to itself or attempts to modify itself by writing into the code region. This poses potential problems when binary translation is used. » Leur solution est de maintenir une image mémoire fidèle du code invité et de toujours lire/écrire depuis cette image source. Dans Corewar, le code auto-modifiant n'est pas un problème — c'est une fonctionnalité. Les champions écrivent couramment dans l'arène (sti, st), potentiellement en écrasant le code que d'autres processus exécuteront. L'arène est simultanément code et données. Le principe de Smith et Nair — maintenir une image mémoire unique et cohérente — est exactement ce que fait la VM Corewar : il n'y a pas de cache de code séparé ; l'arène est à la fois la source d'instructions et l'espace de données inscriptible. Le code auto-modifiant fonctionne « gratuitement » dans Corewar.

Ce « gratuitement » a une contrepartie architecturale profonde : les processeurs pipelinés considèrent le code auto-modifiant comme un hazard. CSAPP (§4.5.5, p.463) documente ce conflit : dans un pipeline, l'étage Fetch lit les instructions en même temps que l'étage Memory les modifie — créant une incohérence. Certains processeurs interdisent le code auto-modifiant, d'autres implémentent des mécanismes complexes de détection. Le modèle mono-cycle de Corewar élimine ce problème : l'écriture est complète avant la lecture suivante. C'est la raison architecturale pour laquelle Corewar ne peut pas être pipeliné — le code auto-modifiant, mécanisme central du jeu, serait un hazard insoluble dans un pipeline (voir l'encart « Le code auto-modifiant comme hazard de pipeline » au §5).

Levine (Linkers and Loaders, Ch.1, p.2-3) rappelle le contexte historique : « Before there were operating systems, each program had the machine's entire memory at its disposal... Programs quickly became larger than available memory, so linkers provided overlays, a technique that let programmers arrange for different parts of a program to share the same memory. » Corewar nous ramène aux contraintes matérielles brutes des années 1960 : la mémoire d'un ordinateur moderne est gérée virtuellement pour paraître infinie, mais le « Core » est un espace fixe, partagé et fini. Les techniques d'attaque dans Corewar (comme les replicators qui copient leur code dans de nouveaux espaces) sont des formes agressives et hostiles de ce que Levine décrit historiquement comme des « overlays » : partager et écraser le même espace mémoire pour survivre face à l'étroitesse des ressources.

Levine (p.177-183) développe techniquement les overlays : « Overlay programs divide the code into a tree of segments. Sibling segments in the overlay tree share the same memory. » L'arène Corewar est conceptuellement une région d'overlay : plusieurs champions partagent le même espace d'adressage, chacun chargé dans une région spécifique. Levine mentionne que « In environments like DSPs that have constrained program address spaces, overlay techniques can be a good way to squeeze programs in » — exactement la situation Corewar (4096 octets). Le manager d'overlay OS/360 ne faisait que 500 octets ; certains pour des DSPs à espace d'adressage de 512 mots tenaient en une douzaine de mots. La contrainte mémoire de Corewar est du même ordre.

Van der Linden (Expert C Programming, p.157) utilise le terme « arena » pour décrire la région mémoire gérée par un allocateur : « Some people use the term arena to describe the set of blocks managed by a memory allocator. » Ce n'est pas une coïncidence si le Corewar utilise le même terme : les deux désignent une région mémoire contiguë gérée par un allocateur. Dans Corewar, l'arène est un tampon circulaire de taille fixe (pas de fragmentation possible grâce au modulo). En programmation système, une arena peut se fragmenter. Le lien étymologique enrichit la compréhension de pourquoi la mémoire Corewar s'appelle une « arène ».

Dans clox, la table d'internement des chaînes pose un problème délicat : elle référence chaque chaîne du tas, mais ne doit PAS empêcher le GC de les collecter. La solution est la référence faible : un pointeur qui ne compte pas comme racine pour le GC, et qui est automatiquement nettoyé si l'objet est collecté. L'arène Corewar pose un problème analogue : un processus peut écrire du code n'importe où dans l'arène, mais la simple existence de code dans l'arène ne signifie pas qu'il est « vivant ». Le code d'un processus mort est comme une chaîne orpheline dans la table d'internement — il occupe de l'espace mais n'est plus atteignable. La différence est que Corewar n'a PAS de références faibles : l'arène est un tableau brut, et le code mort reste jusqu'à ce qu'il soit écrasé. C'est exactement ce que les bombes exploitent — écraser le code « blanc » (non atteignable) des adversaires.

L'algorithme mark-sweep de McCarthy, tel qu'expliqué dans Crafting Interpreters, utilise l'abstraction tricolore : BLANC (non atteint), GRIS (atteint mais pas encore tracé), NOIR (entièrement tracé). Le ramasse-miettes progresse comme un front d'onde gris à travers le graphe d'objets. Transposé à Corewar : les cellules de l'arène sont BLANCHES par défaut (personne ne les référence), deviennent GRISES quand un processus vivant pointe vers elles (le PC les atteint), puis NOIRES une fois exécutées. Le CYCLE_TO_DIE est essentiellement un seuil de déclenchement du GC : quand un processus ne s'est pas manifesté (n'a pas exécuté de live) dans les N cycles, il est « sweepé » — éliminé. Le « tas auto-ajustable » de clox (où le seuil de GC s'adapte à la taille du tas vivant) est l'analogue exact de la façon dont CYCLE_TO_DIE diminue progressivement, s'ajustant au nombre de processus survivants.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.5, §5.2-5.3) distinguent trois grandes familles de représentations intermédiaires (IR) : les IR graphiques (AST, DAG, CFG), les IR linéaires (code à trois adresses, ILOC), et les IR hybrides (CFG + opérations linéaires). Le format .cor de Corewar est un IR linéaire de bas niveau — l'équivalent exact de l'ILOC décrit par Cooper & Torczon : une séquence d'opérations avec des opérandes registre/mémoire/immédiat, où chaque instruction a un coût d'exécution fixe. La comparaison est éclairante :

Cooper & Torczon (§5.2.2) introduisent le Control-Flow Graph (CFG) comme un IR complémentaire : chaque nœud est un bloc de base (séquence maximale d'instructions sans branchement), et chaque arête représente un transfert de contrôle possible. Le CFG d'un guerrier Corewar est particulièrement simple : la séquence de boot (bloc d'entrée), la boucle de bombardement (cycle), et éventuellement un bloc de fin. Cooper & Torczon définissent le bloc de base comme : « a maximal-length sequence of branch-free code » — en Corewar, c'est la séquence entre deux zjmp consécutifs. Le CFG révèle la structure cachée du guerrier : un guerrier bien structuré a un CFG réductible (facile à analyser), un guerrier avec des sauts erratiques a un CFG non réductible (résistant au désassemblage). Le CFG est le premier outil d'analyse d'un guerrier — il révèle la stratégie derrière le bytecode.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.7, §7.2.3) distinguent les valeurs non ambiguës (accessibles par un seul nom) des valeurs ambiguës (accessibles par plusieurs noms) : « a value that can be accessed with just one name is unambiguous. Any value that can be accessed by multiple names is ambiguous. » L'aliasing est la situation où deux noms différents désignent le même emplacement mémoire. Cooper & Torczon préviennent : « The compiler cannot keep an ambiguous value in a register across either a definition or a use of another ambiguous value unless it can prove that the set of locations to which the two names can refer are disjoint. »

L'arène Corewar est le pire cas d'aliasing pour un compilateur : toute cellule est accessible par n'importe quel guerrier à n'importe quel moment. Après un sti r1, r2, %0 qui écrit à l'adresse A, la valeur en A est ambiguë car un guerrier adverse peut l'écraser au cycle suivant. Le compilateur ne peut PAS supposer que la valeur écrite est encore présente au prochain accès — il doit la recharger. C'est l'équivalent du mot-clé volatile en C : Cooper & Torczon notent que « the volatile keyword lets the programmer declare that the contents of a variable may change arbitrarily and without notice » — exactement la condition de chaque cellule de l'arène. Le restrict de C ANSI, qui promet l'absence d'aliasing, n'a aucun équivalent possible en Corewar car la mémoire est partagée par définition. L'arène est un monde entièrement volatile — le compilateur ne peut rien supposer, le programmeur doit tout vérifier.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.9, §9.2.3, p.487+) décrivent l'analyse d'alias : déterminer si deux références mémoire peuvent pointer vers la même location. Sans elle, le compilateur doit supposer conservativement que tout store via pointeur peut modifier n'importe quelle variable, empêchant virtuellement toute optimisation des données accédées par pointeur. Cooper montre que l'analyse d'alias avec arithmétique de pointeurs explicite est indécidable en général.

Dans l'arène Corewar, chaque MOV avec adressage indirect est un alias potentiel pour toute autre cellule. L'arène n'est pas seulement « difficile à analyser » — elle est le cas pathologique prouvé de l'analyse d'alias. Un compilateur pour Redcode devrait supposer que toute écriture sti peut modifier n'importe quelle cellule de l'arène, y compris la prochaine instruction du guerrier lui-même. Cela rend impossibles l'élimination des sous-expressions communes, la propagation de constantes, et la réorganisation des lectures/écritures — les trois optimisations les plus fondamentales. L'arène est la preuve par l'absurde de l'analyse d'alias : quand tout peut aliaser tout, rien ne peut être optimisé.

H&P (6e éd., §3.3) et Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.13) décrivent le renommage de registres (register renaming) : mapper les registres architecturaux (r1-r16) vers un banc de registres physiques plus grand (P0-P127), éliminant les fausses dépendances WAR (Write After Read) et WAW (Write After Write). Seules les dépendances RAW (Read After Write) sont de « vraies » dépendances de données — WAR et WAW sont des artefacts de la réutilisation des noms de registres. Le renommage permet à des instructions avec des WAR/WAW de s'exécuter en parallèle.

En Corewar, les 16 registres sont une ressource si rare que les faux conflits sont inévitables. Un guerrier qui fait ld %42, r2 / sti r2, r3, %0 / ld %99, r2 crée une dépendance WAR sur r2 : la troisième instruction veut écrire dans r2, mais la deuxième n'a pas encore lu l'ancienne valeur de r2. Sur un processeur avec register renaming, r2 serait mappé à deux registres physiques différents, permettant l'exécution en parallèle. En Corewar, l'exécution séquentielle (pipeline de profondeur 1) rend le renommage inutile — chaque instruction termine avant que la suivante ne commence, donc les WAR et WAW ne causent jamais de stall. Mais le concept reste pertinent : un programmeur qui utilise des registres différents pour des valeurs différentes (discipline de nommage strict, proche du SSA) réduit les conflits de noms et facilite l'analyse manuelle du code. Avec 16 registres, le renommage est un luxe qu'on ne peut pas se permettre — mais la discipline de nommage est un outil gratuit que chaque programmeur devrait utiliser.

Hyde (The Art of Assembly Language, §2.8, p.73) donne l'algorithme fondamental de la négation en complément à deux : « To convert a positive number to its negative, two's complement form, you use the following algorithm: 1. Invert all the bits in the number; that is, apply the logical not function. 2. Add 1 to the inverted result and ignore any overflow out of the H.O. bit. » Cet algorithme est la raison pour laquelle sub peut être synthétisé à partir de add et not : A − B = A + (NOT B + 1). En termes matériels, un seul additionneur suffit pour implémenter à la fois l'addition et la soustraction — c'est l'économie architecturale fondamentale de la représentation en complément à deux.

En Corewar, cette équivalence a des conséquences directes sur la sémantique du carry. Quand la VM exécute sub r1, r2, r3, elle calcule en réalité r3 = r1 + (NOT r2 + 1). Le « +1 » final est ce qui fait que la soustraction de zéro d'elle-même produit un carry (car NOT(0) + 1 = 0xFFFFFFFF + 1 = overflow, et le carry est positionné). Cette anomalie apparente — sub 0, 0 met le carry à 1 alors que le résultat est nul — est la conséquence directe de l'algorithme de Hyde. La règle « ignore any overflow out of the H.O. bit » correspond au comportement modulaire de l'arène : les valeurs Corewar sont stockées sur REG_SIZE bits et le débordement est silencieusement ignoré, exactement comme le prescrit Hyde. Le complément à deux n'est pas une convention d'encodage — c'est un choix architectural qui unifie addition et soustraction en un seul circuit, et Corewar en hérite intégralement.

Hyde (The Art of Assembly Language, Ch.6.4.1, pp.377-379) montre que la multiplication par constante peut se faire via décalages et additions : x*10 = (x<<3) + (x<<1). De même, x*7 = (x<<3) - x. Cela évite l'instruction MUL coûteuse.

Corewar n'a pas d'instruction MUL. Toute multiplication doit se faire via des séquences d'additions, et l'absence d'instructions de décalage (SHL/SHR) signifie que même la technique shift-and-add de Hyde doit être implémentée via des boucles d'ADD. Pour multiplier par 10, un guerrier doit : ADD 10 fois, ou implémenter une boucle de comptage. Cette limitation fondamentale façonne le type d'arithmétique que les guerriers peuvent faire efficacement — tout ce qui nécessite une multiplication (adresses calculées complexes, patterns de bombing Fibonacci, etc.) doit être précalculé dans le boot ou implémenté via des tables de lookup dans l'arène. L'absence de MUL et de SHIFT contraint l'arithmétique du guerrier à l'addition et à la soustraction — l'ordinateur le plus primitif possible, un compteur de poche.

Hyde (The Art of Assembly Language, Ch.6.4.2, p.379) décrit la division par multiplication réciproque : x/10 ≈ (x * 6554) >> 16. Cela remplace une DIV lente par une MUL + shift — un gain substantiel sur les processeurs sans diviseur matériel.

Corewar n'a ni DIV ni MUL, rendant cette technique doublement impossible. Mais le principe — remplacer une opération coûteuse par des équivalents algébriques moins chers — est exactement ce que font les auteurs de guerriers quand ils remplacent une boucle de scan par une paire CMP/SLT, ou utilisent ADD au lieu d'une boucle multiply-by-constant. La division réciproque illustre le principe général de l'optimisation : transformer le problème pour le rendre résolvable par les instructions disponibles. En Corewar, les « instructions disponibles » sont ADD, SUB, et les opérations bit à bit (AND, OR, XOR) — tout le reste doit être construit à partir de ces briques fondamentales. L'ingéniosité du guerrier est mesurée par sa capacité à exprimer des algorithmes complexes avec cet ensemble minimal.

Hyde (The Art of Assembly Language, §2.9, p.76-77) distingue deux méthodes d'élargissement d'un entier : « To extend a signed value from some number of bits to a greater number of bits is easy; just copy the sign bit into all the additional bits in the new format. » C'est l'extension de signe. À l'inverse : « To extend an unsigned value to a larger one, you must zero extend the value. Zero extension is very easy—just store a 0 into the H.O. byte(s) of the larger operand. » C'est l'extension de zéro. Le choix entre les deux est crucial : un offset négatif étendu par zéro devient un nombre positif géant — et vice versa.

Dans le format .cor, ce choix se pose à chaque décodage d'opérande. Les opérandes directs (T_DIR) sont encodés sur 2 ou 4 octets selon l'instruction — quand un opérande 2 octets est chargé dans un registre 4 octets, la VM doit décider : extension de signe (l'offset −1 devient 0xFFFFFFFF) ou extension de zéro (l'offset −1 devient 0x0000FFFF). Le sujet Corewar 42 spécifie que les offsets d'adressage indirect sont signés — la VM utilise l'extension de signe pour les T_IND et les T_DIR de 2 octets (permettant des offsets négatifs, c'est-à-dire des références « en arrière » par rapport au PC). Les T_DIR de 4 octets sont déjà pleine taille et ne nécessitent pas d'extension. Hyde met en garde : une erreur entre extension de signe et extension de zéro est l'un des bugs les plus subtils en programmation bas niveau — le programme « marche » pour les petites valeurs positives mais échoue silencieusement pour les valeurs négatives ou les grands offsets. En Corewar, confondre signe et zéro extension signifie qu'un guerrier qui recule de 3 cellules se retrouve projeté à l'adresse 65533 — un bug qui ne se manifeste qu'avec des offsets négatifs.

Hyde (The Art of Assembly Language, §10.4, p.609-612) décrit l'algorithme général d'insertion et d'extraction de bit strings : « A common bit operation is inserting a bit string into an operand or extracting a bit string from an operand. » L'algorithme se déroule en trois étapes : (1) masquer (clear) les bits correspondants dans la destination, (2) décaler le bit string source pour l'aligner à la bonne position, (3) OU logique du résultat décalé avec la destination. L'extraction inverse le processus : masquer → décaler → résultat. C'est le canevas algorithmique universel de toute opération sur des bit fields.

L'encodeur .cor est une application directe de cet algorithme. Prenons l'encodage d'une instruction sti r1, %:live, %1 : l'OCP doit contenir 01 (registre) aux bits 7-6, 10 (direct) aux bits 5-4, 10 (direct) aux bits 3-2. En suivant Hyde : (1) on part de 0x00, (2) on OR (01 << 6) = 0x40, (3) on OR (10 << 4) = 0x60, (4) on OR (10 << 2) = 0x68. Le décodage inverse : (ocp >> 6) & 0x03 pour le paramètre 1, (ocp >> 4) & 0x03 pour le 2, (ocp >> 2) & 0x03 pour le 3 — exactement le masquage puis décalage de Hyde. La même technique s'applique à l'encodage du numéro de registre (4 bits) dans un opérande registre, et à l'extraction de l'opcode (8 bits) depuis le premier octet. Hyde fournit aussi une table de masques précalculés (MaskByLen, p.611) pour extraire des bit strings de n'importe quelle longueur — un outil directement réutilisable dans le décodeur de la VM. Chaque octet du .cor est construit par l'algorithme de Hyde : masquer, décaler, OR — les trois coups de l'encodage binaire.

Le CSAPP §7.6.1 décrit comment l'éditeur de liens résout les conflits entre symboles globaux dupliqués grâce à une hiérarchie fort/faible : les fonctions et variables initialisées sont « fortes », les variables non initialisées sont « faibles ». En cas de conflit, le symbole fort l'emporte silencieusement sur le faible — un mécanisme qui peut introduire des bugs subtils (p. 708-709 : un int x et un double x dans deux modules différents, et le double écrase les 8 bytes adjacents en mémoire). Le format .cor n'a aucun espace de noms : le seul « symbole » est le nom du champion dans le header, qui sert exclusivement à l'affichage. Il n'existe ni symboles globaux ni locaux, ni mécanisme de résolution, ni risque de conflit. L'assembleur Corewar est un compilateur pour un programme à un seul module — la question de la visibilité inter-modules ne se pose tout simplement pas. Là où l'éditeur de liens traditionnel doit arbitrer entre des définitions concurrentes, l'assembleur Corewar opère dans un monde où chaque label est privé par construction.

Le CSAPP §7.6.2-7.6.3 explique comment les archives .a permettent l'édition de liens sélective : parmi des centaines de modules objet dans libc.a, le lieur n'extrait que ceux qui sont effectivement référencés. Ce mécanisme résout le problème de l'encombrement — au lieu d'embarquer toute la bibliothèque, on n'inclut que ce qu'on utilise. Dans l'univers Corewar, ce concept est totalement absent : un champion est un fichier unique et autosuffisant, sans possibilité d'importer des routines depuis une bibliothèque. On ne peut pas écrire un fork_bomb.o et le lier à plusieurs champions. Cette limitation est à la fois une contrainte (pas de réutilisation de code entre champions) et une garantie d'indépendance (aucune dépendance externe, aucun conflit de version, aucun problème d'ordre sur la ligne de commande). Le concept d'archive fait néanmoins apparaître une piste intéressante pour une variante de Corewar : que se passerait-il si les champions pouvaient appeler des « bibliothèques standards » de routines de combat, avec un lieur qui sélectionne uniquement les fonctions référencées ?

Le CSAPP §7.10-7.12 détaille l'architecture de la liaison dynamique : le PLT (Procedure Linkage Table) et le GOT (Global Offset Table) permettent à un programme d'appeler des fonctions dont l'adresse n'est connue qu'au moment de l'exécution, via un mécanisme de résolution paresseuse (lazy binding). Le GOT contient les adresses absolues résolues par le lieur dynamique, tandis que le PLT fournit des stubs de code qui dirigent l'exécution vers le lieur dynamique lors du premier appel. Chez Corewar, rien de tout cela n'existe : chaque champion est chargé dans l'arène comme une image isolée, sans possibilité d'appeler du code externe. Là où le PLT/GOT est un mécanisme d'ouverture (permettre à un binaire de s'interface avec un monde extérieur inconnu au moment de la compilation), .cor est un format de fermeture totale — le champion est son propre univers. Cette isolation a un coût (pas de partage de code entre processus en mémoire) et un bénéfice (aucune surface d'attaque par interposition de bibliothèque, pas de LD_PRELOAD possible). En termes CSAPP, .cor est au format objet ce qu'un programme en mémoire privée est à un processus qui charge des .so — une décision d'isolation radicale qui élimine toute la complexité du lieur dynamique.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.9.3.2, pp.498-500) définissent la frontière de dominance DF(n) : l'ensemble des nœuds où la dominance de n « s'arrête » — les premiers nœuds atteignables depuis n que n ne domine pas. Cela détermine précisément où les φ-fonctions doivent être insérées dans la forme SSA.

Dans le graphe de flot de contrôle d'un guerrier, la frontière de dominance identifie les points exacts où des chemins d'exécution distincts se rejoignent — où les deux branches d'un scanner se réunissent, ou où le chemin conditionnel et le chemin par défaut d'un bomber fusionnent. Comprendre DF révélerait où une « instruction de fusion » (comme une φ-fonction) serait nécessaire pour tracer le flot de données. Mais en Corewar, l'auto-modification de l'arène rend cette analyse impossible : la frontière de dominance change à chaque cycle car les instructions sont réécrites. La frontière de dominance est un concept parfait pour l'analyse statique — et parfaitement inapplicable à un guerrier qui se modifie en temps réel.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.13, §13.4.2, p.697+) décrivent le spill code : quand l'allocation de registres échoue (plus de valeurs vivantes que de registres), le compilateur génère du code de déchargement — stockage puis rechargement des valeurs en mémoire. Le spill code est le facteur principal dégradant la performance dans le code contraint par les registres.

Avec seulement 16 registres, un guerrier complexe fait face à la pression de registres. L'arène sert de « mémoire » pour les valeurs déchargées, mais chaque spill est un sti vers une location partagée, mutable et visible — contrairement à la pile privée d'une machine réelle. Décharger dans l'arène est un acte de foi : votre valeur déchargée peut être écrasée par l'adversaire avant que vous n'ayez le temps de la relire. C'est la différence entre décharger sur une pile privée (sûr mais coûteux) et décharger sur une arène publique (rapide mais mortel). En Corewar, le spill code n'est pas seulement lent — il est dangereux. Chaque valeur déchargée est une cible potentielle pour le bombing adverse.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.10.2.1, pp.544-546) définissent la postdominance : le dual de la dominance. Un nœud j postdomine i si tout chemin de i à la sortie passe par j. L'algorithme Dead utilise les frontières de dominance inverse (de la postdominance) pour déterminer quelles branches sont utiles.

Un guerrier Corewar n'a pas de nœud de sortie — il s'exécute jusqu'à ce qu'il soit tué. Cela signifie que la postdominance est indéfinie pour la plupart du CFG du guerrier. Dans un programme réel, l'élimination du code mort utilise la postdominance pour trouver les branches inutiles ; en Corewar, chaque branchement pourrait théoriquement être « utile » car le programme ne se termine jamais normalement. C'est une différence structurelle entre les guerriers et les programmes conventionnels : un programme a un début et une fin, un guerrier n'a qu'un début. Sans nœud de sortie, la postdominance s'effondre — et avec elle, tout un pan de l'optimisation compilatrice qui suppose que le code a une fin.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.13, p.706+) décrivent la coalescence de copies : éliminer les copies registre-à-registre inutiles en fusionnant la source et la destination dans une seule classe d'allocation. Un MOV r1, r2 où r1 est mort après est du pur overhead.

Chaque mov r1, r2 dans un guerrier coûte un précieux cycle d'instruction. Si r1 n'est plus utilisé ensuite, la copie est gaspillée. Contrairement à un vrai compilateur qui peut coalescer les copies, l'assembleur Corewar n'a aucune passe d'optimisation — l'auteur du guerrier doit coalescer manuellement. Un guerrier bien écrit minimise les copies registre-à-registre : au lieu de ld r1, %42; mov r1, r2; sti r2, ..., on écrit directement ld r2, %42; sti r2, .... En Corewar, la coalescence n'est pas une optimisation optionnelle — c'est une discipline de programmation. Chaque MOV inutile est un cycle que l'adversaire utilise pour vous bombarder.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.10.3.1, pp.551-559) décrivent le Lazy Code Motion (LCM) : quatre analyses de flot de données (disponibilité, anticipabilité, placement au plus tôt, placement au plus tard) pour éliminer simultanément les calculs redondants ET sortir le code invariant des boucles. LCM est strictement plus puissant que le simple loop-invariant code motion.

Le boot d'un guerrier est une forme manuelle de LCM — déplacer le setup invariant hors de la boucle principale. Mais LCM gère aussi les redondances partielles (calculs redondants sur certains chemins mais pas tous), un concept qu'aucun guerrier ne peut exploiter car il nécessiterait de savoir quel chemin sera pris au runtime. LCM montre ce que le guerrier pourrait optimiser s'il pouvait prédire l'avenir — et pourquoi il doit se contenter de la version simplifiée : sortir les constantes de la boucle et prier pour le reste.

Hyde (The Art of Assembly Language, Ch.7.7.4-5, pp.433-436) distingue l'évaluation court-circuit (stop dès que le résultat est connu — A && B saute B si A est faux) de l'évaluation complète (calculer toutes les sous-expressions). Le court-circuit peut avoir un comportement différent quand les sous-expressions ont des effets de bord.

Un scanner warrior utilise naturellement la logique court-circuit : CMP; JMP-if-not-equal saute le bombing si rien n'est trouvé. Si le CMP ne détecte rien, il saute immédiatement — aucun cycle gaspillé. La différence d'effets de bord est cruciale en Corewar : chaque instruction exécutée modifie l'état (avance le PC, modifie potentiellement le carry), donc le choix entre court-circuit et évaluation complète affecte l'empreinte du guerrier. Le scanner est l'incarnation du court-circuit : ne calculer que ce qui est nécessaire, et s'échapper dès que possible — la frugalité comme stratégie de survie.

Aho, Lam, Sethi & Ullman (Compilers: Principles, Techniques, and Tools, 2e éd., Ch.9, §9.3) et Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.9, §9.3) décrivent la propagation de constantes : si un registre est toujours chargé avec une valeur connue à la compilation, remplacer chaque usage de ce registre par la constante elle-même. L'analyse interprocédurale de constantes étend cette optimisation au-delà des frontières des fonctions.

En Corewar, la propagation de constantes est l'optimisation la plus intuitive et la plus impactante. Si r2 est toujours %50 (chargé au boot et jamais modifié), chaque ld r2, r3 peut être remplacé par ld %50, r3 — ou mieux, chaque usage de r2 peut être remplacé par %50 directement. Mais il y a un piège : si l'adversaire écrase la cellule contenant ld %50, r2, r2 ne contient plus 50 — la « constante » est devenue variable. En Corewar, toute constante est potentiellement corrompue par le bombing adverse. Le programmeur doit distinguer les constantes vraies (valeurs encodées dans l'instruction immédiate, impossibles à corrompre) des constantes fausses (registres chargés une fois mais vulnérables au bombing). En Corewar, la propagation de constantes est un pari sur l'intégrité du code — chaque constante propagée est une hypothèse que l'adversaire ne touchera pas cette instruction.

Aho, Lam, Sethi & Ullman (Compilers: Principles, Techniques, and Tools, 2e éd., Ch.9, §9.3) et Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.8, §8.4) décrivent l'élimination des sous-expressions communes (CSE) : si deux instructions calculent la même expression (par exemple a+b à deux endroits différents), stocker le résultat du premier calcul et le réutiliser. L'analyse des expressions disponibles (available expressions) détermine quelles expressions sont déjà calculées à chaque point du programme.

En Corewar, la CSE est une optimisation manuelle critique. Si un guerrier calcule la même adresse effective à deux endroits (par exemple ldi r2, %10, r3 suivi plus tard du même calcul), stocker le résultat dans un registre et le réutiliser économise une instruction et un cycle. La difficulté est que l'arène est mutable — une expression « disponible » au point A peut ne plus l'être au point B si l'adversaire a modifié la cellule source entre temps. C'est le problème de l'aliasing que les compilateurs réels gèrent via le mot-clé restrict : en Corewar, tout est alias par définition. En Corewar, la CSE est possible mais risquée — la réutilisation d'un calcul suppose que l'arène n'a pas changé, une hypothèse toujours fausse en présence d'un adversaire.

Aho, Lam, Sethi & Ullman (Compilers: Principles, Techniques, and Tools, 2e éd., Ch.9, §9.3) et Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.11, §11.5) décrivent l'optimisation peephole : examiner une fenêtre glissante de 2-3 instructions pour trouver des patterns remplaçables. Exemples classiques : ld r1, r2 / st r2, r1 → st r1, r2 (suppression de la copie inverse), ADD %0, r1, r1 → nop (identité additive), AND %0xFFFFFFFF, r1, r1 → nop (identité bit-à-bit).

En Corewar, l'optimisation peephole est l'arme secrète du programmeur de guerrier. Chaque économie d'une instruction est un cycle gagné — et un cycle, c'est un tour de round-robin qui ne sera pas utilisé par l'adversaire. Exemples concrets : ld r1, r3 / sti r3, %0, r2 → sti r1, %0, r2 (élimination de la copie via r3) ; add %0, r2, r2 / zjmp %:loop → zjmp %:loop (l'addition nulle est un nop) ; sub r1, r2, r3 / add r3, r4, r4 → sub r1, r2, r4 / add r2, r4, r4 (si r3 est mort après). Le peephole est l'optimisation que tout programmeur de guerrier applique instinctivement — car dans l'arène, chaque octet est une cible et chaque cycle est une ressource. En Corewar, le peephole n'est pas une optimisation optionnelle — c'est une question de survie.

Aho, Lam, Sethi & Ullman (Compilers: Principles, Techniques, and Tools, 2e éd., Ch.4, §4.5-4.7) décrivent l'analyse LR/LALR : la technique de parsing standard pour les grammaires hors-contexte. Un analyseur LR utilise une pile d'états et une table d'action (shift/reduce) pour reconnaître les productions de la grammaire. Les conflits shift/reduce et reduce/reduce indiquent des ambiguïtés. Yacc/Bison génèrent des analyseurs LALR(1) automatiquement.

L'assembleur Corewar implémente un analyseur syntaxique pour le langage .s. La grammaire de ce langage est suffisamment simple pour ne pas nécessiter un analyseur LALR complet — chaque ligne commence par un opcode qui détermine immédiatement la production attendue. Les « tokens » sont : opcode, registre (r1-r16), direct (%value), indirect (value), label (:name). Les conflits shift/reduce sont inexistants car la grammaire est LL(1) — le premier token (opcode) détermine tout le reste de la ligne. Le parsing de l'assembleur Corewar est un cas d'étude du cas trivial de l'analyse syntaxique : là où un compilateur C nécessite un analyseur LALR complexe, l'assembleur se contente d'un tokenizer + dispatch par opcode. L'assembleur Corewar est le parser le plus simple qui mérite encore ce nom — l'antithèse de la complexité LALR.

Bryant & O'Hallaron (Computer Systems: A Programmer's Perspective, 3e éd., Ch.7, §7.1-7.3) décrivent le format ELF (Executable and Linkable Format) : un format binaire structuré avec un header (magic number, type, architecture), des program headers (segments loadables), des section headers (.text, .data, .bss, .rodata, .symtab, .rela.text, .strtab), des tables de symboles, et des tables de relocation. ELF supporte la compilation séparée, l'édition de liens, le chargement dynamique, et le debugging.

Le format .cor est l'anti-ELF : un header minimal (magic number 0xEA83F3, taille du programme, point d'entrée) suivi d'un bloc plat de bytecode. Pas de segments, pas de sections, pas de symboles, pas de relocation, pas de debugging info, pas de dynamic linking. Tout ce qu'ELF sépare (.text vs .data vs .bss), le .cor le fusionne en un seul flux. La compilation séparée est impossible — un champion est un seul fichier. L'édition de liens est inutile — pas de références externes. Le chargement est trivial — copier le bloc à l'offset du champion. Si ELF est la cathédrale du linking moderne, le .cor est la cabane du survivant — pas de fenêtres, pas de portes, juste un toit et un plancher.

La spécification ultime de Corewar est le standard ICWS'94 (International Core Wars Society, draft 1994). Bien que ce standard n'ait techniquement jamais été formellement adopté — l'ICWS s'est dissoute avant la finalisation — il est devenu le standard de facto de la communauté. Son implémentation de référence est pMARS (Portable Memory Array Redcode Simulator), écrite en C, qui reste à ce jour le simulateur le plus utilisé pour les tournois.

L'écosystème s'est modernisé au fil des décennies. Corewar.io propose une interface web permettant de coder et tester des guerriers directement dans le navigateur. npmars est un portage de pMARS en TypeScript, rendant le simulateur accessible dans l'écosystème JavaScript/Node.js. La recherche d'optimisation absolue a aussi poussé la création de simulateurs hyper-performants comme Exhaust et hMARS, conçus pour surpasser la vitesse de pMARS. Ces moteurs dépouillés sont utilisés comme coeurs d'exécution au sein d'algorithmes génétiques : ils permettent de faire évoluer des millions de champions par mutations aléatoires en un temps record, prouvant que cette architecture inventée dans les années 80 demeure un terrain de jeu inépuisable pour la recherche computationnelle.

Cette longévité est remarquable pour un concept né en 1984. Elle s'explique par la richesse stratégique du jeu — l'équilibre pierre-papier-ciseaux garantit qu'il n'existe pas de stratégie dominante — et par la précision technique requise : un simulateur Corewar doit être exact au cycle près, car le résultat d'un combat peut dépendre d'un seul cycle d'avance. Cette exigence de déterminisme absolu est la même que celle des simulateurs de processeurs réels décrits par Smith et Nair, et elle explique pourquoi pMARS, malgré son âge, reste la référence incontestée.

Clarke, Grumberg & Peled (Model Checking, 1999, MIT Press, Ch.1-3) définissent le model checking comme une technique de vérification automatique : étant donné un modèle du système (un automate fini) et une propriété temporelle (une formule CTL/LTL), le model checker explore exhaustivement tous les états du modèle pour vérifier si la propriété est satisfaite. Si la propriété est violée, le model checker produit un contre-exemple — une trace d'exécution qui mène à la violation. Clarke et al. (Ch.2, §2.1) montrent que le model checking est particulièrement adapté aux protocoles et aux systèmes réactifs, où le nombre d'états est fini mais exponentiel.

La VM Corewar est un candidat idéal pour le model checking pour deux raisons. Premièrement, l'espace d'états est fini : l'arène a 4096 cellules à 256 valeurs possibles (2^32768 états d'arène), les processus ont un nombre borné de registres à valeurs bornées (r1 = numéro du joueur, les autres dans [-2^31, 2^31-1]), et le nombre de processus est borné par CYCLE_TO_DIE. Deuxièmement, les propriétés à vérifier sont des propriétés de sûreté (safety) : « la VM ne crash jamais », « chaque processus vivant exécute au moins une instruction par cycle de vérification », « le round-robin est équitable ». Ces propriétés s'expriment en LTL (Linear Temporal Logic) : G(not crash), G(process_alive → F(executes)), G(fair_scheduling). Clarke et al. (Ch.4, §4.2) notent que l'explosion d'états est le défi principal — avec 4096 cellules, l'espace d'états est astronomique. Mais les propriétés structurelles de la VM (déterminisme, pas d'I/O, pas de concurrence) réduisent considérablement l'espace exploré. Le model checking de la VM Corewar est un projet réalisable — et chaque bug trouvé est un bug qui ne se produira jamais en production.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.8, §8.5.1 et Ch.10, §10.3) décrivent le value numbering comme une optimisation qui détecte les calculs redondants : « The algorithm assigns a distinct number to each distinct value computed by the program. If two expressions compute the same value, they receive the same number. » Le superlocal value numbering étend cette analyse au-delà d'un bloc de base, en propageant les numéros à travers les arcs du CFG.

En Corewar, le value numbering répond à la question : ce guerrier calcule-t-il la même adresse deux fois ? Un bomber naïf peut recalculer la même adresse cible dans deux branches différentes de son code — un value numbering révèle cette redondance et permet de factoriser le calcul. Par exemple, si add r2, %step, r2 apparaît dans deux branches qui convergent, le value numbering détecte que le résultat est le même et permet de le déplacer avant la bifurcation (code motion). Cooper & Torczon (§10.3.2) décrivent aussi le global value numbering basé sur les dominateurs : deux expressions dans des blocs dominés par le même prédécesseur calculent la même valeur si leurs opérandes ont les mêmes numéros. Chaque expression redondante éliminée raccourcit le guerrier — moins de code, moins de cibles, plus de vitesse.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.10, §10.4) décrivent la Profile-Guided Optimization (PGO) : compiler le programme avec instrumentation, l'exécuter sur des données représentatives, collecter les profils d'exécution (branches prises/non prises, fréquences de boucles, chemins chauds), puis recompiler en utilisant ces profils pour guider les optimisations. Les optimiseurs utilisent le profil pour le layout de code (placer les blocs de base chauds séquentiellement), la prédiction de branchement, et l'inlining sélectif. GCC et LLVM supportent PGO depuis des années, et Google rapporte des speedups de 5-15% sur des workloads réels (Google, 2020, « AutoFDO »).

En Corewar, le PGO est une pratique naturelle mais entièrement manuelle. Le programmeur compile son guerrier, le teste contre un pool d'adversaires, analyse les résultats (win rate, causes de défaite, cycles gaspillés), puis modifie le code source en conséquence. C'est exactement le cycle PGO : instrument (tester) → profiler (analyser) → optimiser (modifier). La différence est que le compilateur Corewar (l'assembleur) ne fait aucune optimisation automatique — le PGO est entièrement à la charge du programmeur. Cooper & Torczon (§10.4.2) montrent que l'information de profil la plus précieuse est la fréquence des arêtes du CFG — en Corewar, l'équivalent est de savoir quelles boucles s'exécutent le plus souvent, quelles branches sont prises, et combien de cycles sont gaspillés dans les chemins froids. En Corewar, chaque programmeur fait du PGO à la main — et la qualité de son profilage détermine la qualité de son guerrier.

Kernighan et Ritchie (The C Programming Language, p.41) documentent le piège de la promotion signée : « There is one subtle point about the conversion of characters to integers. [...] When a char is converted to an int, can it ever produce a negative integer? The answer varies from machine to machine. » Quand la VM lit un octet de l'arène avec le bit 7 à 1 (valeur ≥ 128), le stocker dans un char signé et le convertir en int produit un nombre négatif sur les plateformes où char est signé. Cela corrompt silencieusement les opcodes et les valeurs d'arguments. L'arène DOIT être unsigned char. En Rust, ce problème n'existe pas : u8 est toujours non signé.

K&R (p.98-100) décrivent les pointeurs de fonction pour la table de dispatch des opcodes : « In C, a function itself is not a variable, but it is possible to define pointers to functions, which can be assigned, placed in arrays, passed to functions, returned by functions, and so on. » La VM Corewar utilise typiquement void (*op_table[16])(vm_t*, process_t*) — un tableau de 16 pointeurs de fonction. K&R mettent en garde sur les parenthèses critiques : int (*comp)() est un pointeur vers fonction, mais int *comp() est une fonction retournant un pointeur — une confusion silencieuse qui change le type. Van der Linden (p.188-189) confirme que cette table de dispatch est un automate fini : « A finite state machine (FSM) is a mathematical concept that can be very useful when embodied in a program. Most of them are based on an array of pointers to functions. » En Rust, les enums et match rendent ce pattern plus sûr et plus lisible.

Van der Linden (p.27-28) démontre que const n'est PAS une vraie constante : « The keyword const doesn't turn a variable into a constant! A symbol with the const qualifier merely means that the symbol cannot be used for assignment. » Et Ken Thompson de rajouter : « The const keyword only confuses library interfaces with the hope of catching some rare errors. » En Rust, const est une vraie constante de compilation — elle peut être utilisée dans les tableaux de taille et les match. Cette différence est fondamentale pour la sécurité du code de la VM.

Newsome & Song (Dynamic Taint Analysis for Automatic Detection, Analysis, and Signature Generation of Exploits, NDSS 2005) et Schwartz et al. (All You Ever Wanted to Know about Dynamic Taint Analysis, FETS 2010) définissent le taint tracking : marquer les données provenant de sources non fiables et propager ces marques à travers les opérations. Si une valeur tainted atteint un « point sensible » (appel système, saut indirect), une alerte est déclenchée. L'outil TaintCheck implémente cette analyse pour détecter les exploits.

En Corewar, chaque octet lu dans l'arène est potentiellement tainted — écrit par l'adversaire. Un ldi qui lit une cellule adverse charge une valeur tainted dans un registre ; un zjmp qui dépend de cette valeur est un « taint-controlled branch » — exactement la vulnérabilité que TaintCheck détecte. La totalité de l'arène est une tainted data source. Le taux de contamination est de 100% : chaque cellule peut avoir été modifiée par l'ennemi. La seule donnée « untainted » est le code que le guerrier vient lui-même d'écrire — et encore, si l'adversaire a pu écrire entre-temps, même cette donnée est tainted. En Corewar, le taint tracking est inutile car tout est tainted — la paranoia est la rationalité.

Dans un ramasse-miettes, les racines (roots) sont les objets que la VM peut atteindre directement sans passer par d'autres objets : variables globales, pile d'exécution, call frames. Tout objet atteignable depuis une racine est vivant ; tout le reste est collectable. Dans Corewar, les racines sont les processus vivants : chaque PC de processus vivant est une racine, chaque registre pointant vers une adresse est un chemin d'accessibilité. Le code chargé au démarrage est aussi une racine (bien que le code puisse être écrasé). Cette formalisation est puissante : elle permet de définir précisément quelles zones de l'arène sont « sûres » à bomber (blanches — non atteignables depuis aucune racine) et lesquelles risquent de tuer un processus (noires — sur le chemin d'exécution d'un processus vivant). Un champion qui comprend les racines de ses adversaires peut les bombarder chirurgicalement.

Cormen et al. (Introduction to Algorithms, 3e éd., CLRS, Ch.2-3) introduisent la notation Big-O comme cadre d'analyse des algorithmes : exprimer le temps d'exécution en fonction de la taille de l'entrée, en ignorant les constantes. Cette analyse est omniprésente en algorithmique mais absente de la plupart des guides Corewar — une lacune que cette section comble.

Les opérations fondamentales de la VM ont des complexités bien définies : mem_mod() est O(1) — un simple modulo arithmétique. store_at() / load_from() sont O(1) — écriture/lecture de 4 octets à une adresse calculée. Le dispatch d'opcodes est O(1) — indexation dans une table de 16 entrées. Le scheduling round-robin est O(P) par cycle complet — on visite chaque processus une fois, où P est le nombre de processus vivants. Le garbage collection des zombies (kill_zombies) est O(P) en Rust (retain_mut parcourt le Vec une fois) mais O(P²) en C (parcours de liste + suppression de nœud, chaque suppression nécessitant un parcours). La vérification des lives est O(P) — parcours de tous les processus. La résolution de labels est O(I) avec table de hachage ou O(I·L) avec liste chaînée, où I est le nombre d'instructions et L le nombre de labels. Un cycle complet de la VM est donc O(P) — le coût est dominé par le parcours des processus, pas par l'exécution individuelle des instructions.

La conséquence la plus importante est la complexité d'une partie complète. Soit T = CYCLE_TO_DIE initial, D = CYCLE_DELTA, et N le nombre de vérifications avant que CTD ne devienne négatif. Le nombre total de cycles est Σ(i=0..N) T - i·D ≈ N·T - D·N²/2. À chaque cycle, O(P) opérations. La croissance du nombre de processus P est exponentielle au début d'une fork bomb (chaque fork double P), mais elle est bornée par les constantes du système : CYCLE_TO_DIE tue les processus qui ne déclarent pas live, la mémoire hôte est finie, et la plupart des implémentations plafonnent le nombre de processus. La croissance converge donc vers un équilibre où P est une constante P_max dépendant des paramètres du jeu. La complexité asymptotique réelle est O(P_max · C) où C est le nombre total de cycles — polynomial, pas exponentiel. Le Big-O de la VM est borné — l'explosion exponentielle est un phénomène transitoire, pas un état asymptotique.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.11.4, pp.610-618) décrivent la sélection d'instructions par motifs arborescents : des règles de réécriture avec coûts associés servent à « carreler » un AST avec des arbres d'opérations, choisissant les pavages de coût minimal. Une seule opération haut-niveau peut correspondre à plusieurs patterns machine (ex: addI vs add+loadI). Le problème est NP-dur en général.

Le travail de l'assembleur Corewar — traduire sti r1, %42, r2 en bytes OCP — est une forme triviale de pattern matching. Le système sophistiqué de Cooper montre pourquoi la sélection d'instructions réelle est NP-dure — et pourquoi les 16 opcodes fixes de Corewar sans encodages alternatifs est une simplification radicale qui élimine tout le problème de sélection. Il n'y a qu'une seule façon d'encoder chaque instruction — pas de trade-off entre encodage court et encodage rapide, pas de choix entre registre et immédiat pour le même opération. Le format .cor élimine la sélection d'instructions par décret : chaque mnémonique a exactement un encodage, et le « coût » est toujours 1.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.12, §12.2-12.4) décrivent le list scheduling comme l'algorithme classique pour réordonner les instructions dans un bloc de base : « The algorithm operates on a dependence graph for a basic block. It prioritizes instructions by their latency and places them in the earliest cycle where all their operands are available. » Le scheduler construit un graphe de dépendances (data-dependence graph) où chaque nœud est une instruction et chaque arête est une contrainte de précédence (une valeur doit être calculée avant d'être utilisée).

En Corewar, le list scheduling s'applique au boot d'un guerrier — la séquence d'initialisation avant la boucle principale. Les dépendances déterminent l'ordre obligatoire : ld %0, r2 doit précéder sti r1, r2, %offset car r2 doit être initialisé. Mais entre deux instructions indépendantes, l'ordre est libre — et le choix optimal est celui qui minimise le chemin critique vers la première instruction de la boucle. Cooper & Torczon (§12.4) distinguent le forward list scheduling (planifier du début vers la fin) du backward list scheduling (planifier de la fin vers le début) — le backward donne souvent de meilleurs résultats car il priorise les instructions critiques pour la terminaison. En Corewar, le backward scheduling du boot signifie : commencer par la dernière instruction avant la boucle et remonter, en s'assurant que chaque instruction prépare exactement ce dont la suivante a besoin. Un boot bien ordonnancé atteint la boucle de bombardement plus vite — chaque cycle gagné dans le boot est un cycle de bombing en plus avant l'adversaire.

Robert Nystrom (Crafting Interpreters) décrit trois représentations possibles du code : le tree-walk (parcours d'AST — simple, portable, mais lent), le bytecode (compromis idéal), et le code natif (rapide mais complexe et non portable). Le format .cor du Corewar est du bytecode au sens strict : une séquence dense d'opcodes et d'opérandes, exécutée par une VM (MARS). L'histoire du p-code de Niklaus Wirth (Pascal) est frappante : dans les années 60-70, de nouvelles architectures apparaissaient chaque jour, et la portabilité du bytecode valait plus que la performance native. Corewar suit exactement cette philosophie — le format .cor est portable entre toutes les implémentations de MARS, indépendamment de l'architecture hôte.

Pierce (Types and Programming Languages, 2002, Ch.4, §4.2-4.5) décrit le pattern matching comme un mécanisme de dispatch structural : chaque cas d'une somme (type algébrique) est associé à un pattern, et le compilateur vérifie que l'ensemble des patterns est exhaustif (tous les cas sont couverts). Le pattern matching structurel est le fondement du dispatch dans les langages fonctionnels (ML, Haskell) et dans les compilateurs modernes : l'AST est un type algébrique, et chaque phase du compilateur pattern-match sur les nœuds.

L'assembleur Corewar utilise implicitement du pattern matching : le dispatch des opcodes est une table de 16 entrées, chaque entrée correspondant à un pattern (opcode + types d'opérandes acceptés). La propriété critique est l'exhaustivité : les 16 opcodes définissent un ensemble fini et fermé, et le dispatch doit couvrir chaque cas possible. Pierce (§4.5) montre que la non-exhaustivité est une source de bugs silencieux : si un cas n'est pas traité, le programme a un comportement indéfini. En Corewar, un opcode non reconnu (en dehors de 1-16) est une erreur — l'assembleur doit la détecter, et la VM doit la rejeter. La correspondance avec les types d'opérandes est aussi un pattern matching : chaque opcode accepte un sous-ensemble de {T_REG, T_DIR, T_IND} pour chaque paramètre, et l'assembleur doit vérifier que le pattern d'opérandes correspond à un pattern autorisé. Le dispatch d'opcodes de l'assembleur est un pattern matching exhaustif sur un type somme à 16 constructeurs — et la vérification d'exhaustivité est la garantie de correction.

Le Dragon Book (Aho et al., Compilers, 2e éd., Ch.12, §12.1-12.2) décrit l'analyse interprocédurale : faire circuler l'information à travers les frontières de procédures. Sans elle, le compilateur doit supposer conservativement que toute procédure appelée peut modifier tout état visible. Avec elle, le compilateur peut déterminer exactement quelles variables sont affectées.

Dans un guerrier Corewar multi-processus, chaque processus est comme une « procédure » qui peut modifier l'arène partagée. Sans analyse interprocédurale, un désassembleur doit supposer que n'importe quel processus peut modifier n'importe quelle cellule. Avec une analyse interprocédurale (suivi des adresses lues/écrites par chaque processus), on pourrait déterminer l'ensemble exact de cellules qu'un guerrier peut affecter. Mais l'adressage indirect de Corewar (ldi, sti avec adresses calculées par registres) rend cette analyse aussi difficile que l'analyse d'alias de pointeurs en C — le Dragon Book note que c'est le problème le plus dur de l'analyse interprocédurale. Désassembler un guerrier Corewar est de l'analyse interprocédurale avec un aliasing maximal — chaque cellule est potentiellement aliasée par chaque processus.

Le Rust Book (Ch.10, §10.3) et le Rustonomicon (Ch.3) décrivent les lifetimes (durées de vie) : des annotations qui garantissent que toute référence est valide aussi longtemps qu'elle est utilisée. Le borrow checker utilise les lifetimes pour rejeter les programmes où une référence pourrait survivre à la donnée qu'elle pointe — par exemple, un pointeur vers une variable locale qui serait utilisé après le retour de la fonction. Les lifetimes sont l'extension temporelle du borrow checker : là où les règles d'ownership garantissent la validité spatiale (un seul propriétaire), les lifetimes garantissent la validité temporelle (pas de dangling reference).

Dans l'implémentation d'une VM Corewar, les lifetimes résolvent un problème récurrent de la version C : le dangling pointer vers un processus tué. En C, quand un processus est retiré de la liste et libéré, tout pointeur qui référençait ce PCB est un dangling pointer — utiliser ce pointeur est un comportement indéfini (use-after-free). En Rust, le système de lifetimes garantit qu'aucune référence à un PCB ne peut survivre à la suppression du PCB du Vec<Process>. L'itérateur sur les processus est annoté avec une lifetime qui ne permet pas de modifier la structure des processus pendant l'itération — empêchant la suppression d'un processus en plein parcours. C'est l'équivalent du check borrowing en temps de compilation : les lifetimes transforment le use-after-free d'un bug runtime silencieux (C) en une erreur de compilation explicite (Rust).

Pierce (Types and Programming Languages, 2002, Ch.1, §1.3-1.4) et le Rust Book (Ch.6, §6.2) décrivent le pattern matching structurel : un mécanisme qui décompose une valeur selon sa structure et vérifie l'exhaustivité des cas. En Rust, le match sur un enum est exhaustif par construction — le compilateur rejette tout match qui ne couvre pas toutes les variantes. En C, le switch n'impose pas l'exhaustivité — un case manquant silencieusement tombe dans le default (s'il existe) ou ne fait rien.

La table de dispatch des opcodes Corewar illustre la différence entre ces deux approches. En C : switch(opcode) { case 1: op_live(); break; case 2: op_ld(); break; ... case 16: op_aff(); break; default: /* silencieux */ break; } — si l'opcode est 0 ou 17, le default est atteint et l'instruction est ignorée silencieusement. En Rust : match opcode { 1 => op_live(), 2 => op_ld(), ... 16 => op_aff(), _ => panic!("invalid opcode") } — tout opcode non prévu cause un panic, détectant immédiatement le bug. Le match exhaustif de Rust transforme un bug silencieux (C) en une erreur bruyante (Rust). C'est un exemple concret de la sûreté par construction que Pierce théorise : le système de types rejette les programmes incomplets, éliminant une classe entière de bugs à la compilation. Le match Rust est un invariant de compilation — le dispatch ne peut jamais « oublier » un opcode sans que le compilateur ne le signale.

Plotkin (A Structural Approach to Operational Semantics, 1981, DAIMI FN-19, University of Aarhus, §1-3) fonde la sémantique opérationnelle structurelle (SOS) : au lieu de décrire le comportement d'un programme par une fonction mathématique (sémantique dénotationnelle) ou par des assertions logiques (sémantique axiomatique), on spécifie le comportement par des règles d'inférence de la forme ⟨état, instruction⟩ → ⟨état'⟩. Chaque règle décrit une transition atomique du système — une étape d'exécution. L'ensemble des règles définit le comportement complet de la machine. Plotkin montre que cette approche est naturelle pour les langages impératifs car elle suit la structure syntaxique du programme (d'où « structurelle »).

La VM Corewar est un candidat idéal pour une spécification SOS. L'état du système est un tuple σ = (A, P, c, δ) où A est l'arène (tableau de 4096 cellules), P est la file de processus (liste de context blocks), c est le compteur de cycles, et δ est la valeur de CYCLE_TO_DIE. Les règles de transition pour chaque instruction sont directes : par exemple, ⟨σ, sti r_i, r_j, r_k⟩_p → ⟨σ[A ← σ.A[addr..addr+3] := σ.p.reg[i]], P', c+1, δ⟩_p où p est le processus courant, addr est calculé selon IDX_MOD, et P' reflète l'avancement du PC. De même, ⟨σ, fork %N⟩_p → ⟨σ, P ∪ {clone(p, new_pc)}, c+1, δ⟩_p. Ces règles rendent explicite ce que le code C/Rust implémente implicitement : chaque instruction est une fonction pure de l'état courant vers l'état suivant.

L'intérêt pratique est considérable. Plotkin (§4) montre que la SOS permet de prouver la déterminisme : si pour chaque état et chaque instruction, il existe au plus une règle applicable, alors le système est déterministe. En Corewar, cette propriété est triviale — chaque opcode déclenche exactement une règle — mais sa preuve formelle nécessite la SOS. Sans elle, la reproductibilité de la VM reste empirique : on constate que deux exécutions donnent le même résultat, mais on ne l'a pas prouvé. La SOS permet aussi de vérifier la conformité d'une implémentation : si l'implémentation C/Rust produit les mêmes transitions que les règles SOS, elle est correcte par construction. La SOS transforme la spécification informelle « la VM fait ceci » en théorème prouvable « la VM ne peut faire que ceci » — de l'empirisme au formalisme.

DeMillo, Lipton et Sayward (Hints on Test Data Selection: Help for the Practicing Programmer, 1978, IEEE Computer, vol. 11, no. 4, p.34-41) et Jia et Harman (An Analysis and Survey of the Development of Mutation Testing, 2011, IEEE TSE, vol. 37, no. 5, p.649-678) décrivent le mutation testing : créer des variantes (« mutants ») du programme en introduisant des fautes systématiques (opérateurs arithmétiques modifiés, conditions inversées, constantes décalées), puis vérifier que les tests détectent chaque mutant. Un mutant non détecté (« équivalent ») révèle une lacune de la suite de tests.

Le mutation testing de la VM Corewar consiste à générer des champions pathologiques qui testent les cas limites de l'implémentation : (1) Opcodes corrompus : un .cor avec un opcode 0x00 ou 0x11 (en dehors de 1-16) teste la robustesse du dispatch. (2) OCP invalides : un bytecode avec un OCP demandant T_REG pour un paramètre qui n'accepte que T_DIR teste la validation des types. (3) Labels circulaires : un .s avec zjmp %:a / a: zjmp %:b / b: zjmp %:a teste la résolution de labels et la détection de boucles infinies. (4) Débordement de mémoire : un champion dont PROG_SIZE dépasse MEM_SIZE teste la vérification des bornes. (5) Registres hors limites : un bytecode référençant r0 ou r17 teste la validation des index de registres. (6) Endianness inversé : un .cor avec les valeurs en Little Endian au lieu de Big Endian teste l'encodage correct.

Chaque mutant est un test d'un cas limite que le programmeur normalement ne testerait pas. Jia et Harman montrent que le mutation testing est la technique de test la plus puissante pour révéler les fautes — plus que la couverture de code ou le fuzzing aléatoire. En Corewar, les champions pathologiques sont les « mutants » de la VM : ils ne cherchent pas à gagner, mais à faire crasher ou mal se comporter l'implémentation. Fuzzer la VM, c'est la tester comme un guerrier teste l'arène — par bombardement. Mais muter les champions, c'est la tester comme un chercheur teste une hypothèse — par variation systématique de chaque paramètre.

Dans un processeur réel, le traitement d'une instruction suit un pipeline matériel. Le Y86-64 de CSAPP (§4.3) décompose l'exécution en 6 étages : Fetch → Decode → Execute → Memory → Writeback → PC Update. Chaque étage accomplit une tâche précise :

• Fetch : lire les octets d'instruction depuis la mémoire à l'adresse du PC, extraire l'opcode et les champs de registre
• Decode : lire les opérandes depuis le fichier de registres
• Execute : l'ALU effectue l'opération, calcule les adresses effectives, met à jour les codes de condition
• Memory : lire ou écrire dans la mémoire de données
• Writeback : écrire les résultats dans les registres
• PC Update : avancer le PC à l'instruction suivante

Le Corewar simplifie ce pipeline en 4 phases : Fetch → Decode/Wait → Validate → Execute. Les étages Memory et Writeback sont fusionnés dans Execute, et l'étage Decode est étiré en une attente de plusieurs cycles (simulant la latence variable des instructions). C'est un choix de design qui rend le jeu plus tactique : les instructions longues comme fork (800 cycles) créent des fenêtres de vulnérabilité pendant lesquelles le processus ne peut pas réagir.

Smith et Nair (Virtual Machines, pp.29-32) décrivent le modèle d'interprétation le plus fondamental : le decode-and-dispatch interpreter. Leur pseudocode est un miroir quasi-exact de la boucle principale de la VM Corewar :

// D'après Smith & Nair, Figure 2.3 (adapté à Corewar)
while (!halt) {
    inst = arena[PC];                    // FETCH
    opcode = extract(inst, 7, 4);        // DECODE (4 bits de poids fort)
    switch(opcode) {
        case 1:  op_live(vm, process);   // DISPATCH
        case 2:  op_ld(vm, process);
        case 6:  op_and(vm, process);
        case 9:  op_zjmp(vm, process);
        case 12: op_fork(vm, process);
        // ... 16 instructions
    }
}

Ils soulignent que « the process of interpretation is quite straightforward, the performance cost of interpretation can be quite high. Even if the interpreter code were written directly in assembly language, interpreting a single instruction [...] could involve the execution of tens of instructions in the target ISA. » (p.32) C'est précisément pourquoi la VM Corewar est plus lente qu'un programme natif : chaque instruction Corewar nécessite des dizaines d'instructions machine hôte pour le fetch, le decode, la validation des paramètres, et l'exécution.

Smith et Nair décrivent aussi des techniques d'optimisation : l'interprétation threaded (p.32-34) qui élimine la boucle centrale en chaînant directement les routines d'instruction, et le predecoding (p.34-38) qui analyse les instructions une fois pour toutes plutôt qu'à chaque exécution. Ces optimisations pourraient être appliquées à la VM Corewar pour améliorer les performances — le prédecoding serait particulièrement efficace car les instructions dans l'arène changent peu entre les cycles.

Erickson (Hacking: The Art of Exploitation, p.29-30) décrit la boucle d'exécution fondamentale du processeur x86 : « 1. Reads the instruction that EIP is pointing to. 2. Adds the byte length of the instruction to EIP. 3. Executes the instruction that was read in step 1. 4. Goes back to step 1. » Ce cycle fetch-decode-execute est exactement celui de la VM Corewar — le PC joue le rôle de l'EIP, l'opcode est lu à l'adresse pointée, le PC avance de la taille de l'instruction, puis l'instruction est exécutée. La différence majeure : en x86, l'étape 2 est automatique et immédiate (le processeur avance EIP de lui-même), tandis qu'en Corewar, le PC n'avance qu'après l'exécution de l'instruction, ce qui permet au code de se modifier lui-même avant que le PC ne soit mis à jour.

Erickson note aussi que les instructions jump et call changent l'EIP de façon non linéaire : « Sometimes the instruction will be a jump or a call instruction, which changes the EIP to a different address of memory. The processor doesn't care about the change, because it's expecting the execution to be nonlinear anyway. » En Corewar, zjmp est exactement ce type d'instruction — il détourne le PC vers une autre adresse, et la VM continue comme si de rien n'était. Le fork est encore plus radical : il crée un nouveau PC, un nouveau flux d'exécution indépendant, quelque chose que l'x86 ne fait pas nativement (un processeur n'a qu'un seul EIP par cœur).

Hyde (The Art of Assembly Language, §7.8) décrit les state machines implémentées par saut indirect : « A common implementation of a state machine in assembly language is to use an indirect jump. Rather than having a state variable that contains a value like 0, 1, 2, or 3, we could load the state variable with the address of the code to execute upon entry into the procedure. By simply jumping to that address, the state machine could save the tests needed to select the proper code fragment. » Au lieu de tester séquentiellement l'état (cmp(state, 0); jne ...; cmp(state, 1); jne ...), on charge l'adresse du handler directement et on saute — O(1) au lieu de O(n).

La boucle de dispatch de la VM Corewar est précisément une state machine par saut indirect. L'opcode lu à l'adresse PC est l'état courant, et la table de dispatch (le switch en C ou le match en Rust) est la table de transition. Chaque handler d'opcode est un état de la machine : il exécute l'opération, met à jour le PC, puis rend le contrôle au dispatcher qui lit le prochain « état » (l'opcode suivant). C'est un modèle fondamental partagé par tous les interpréteurs — Smith et Nair l'appellent « decode-and-dispatch », Hyde l'appelle « state machine par saut indirect », et la communauté des VM l'appelle « threaded code ».

Hyde met en garde contre le danger du saut indirect : « If pointers and gotos are bad, then the indirect jump must be the worst construct of all because it involves both gotos and pointers! » Un jmp *dispatch_table[opcode] peut théoriquement sauter n'importe où — si la table est corrompue, le comportement est indéfini. En Corewar, ce risque est matériellement impossible : l'opcode est un entier entre 1 et 16, et la table est statique. Mais dans un guerrier qui s'automodifie, le concept de « saut indirect vers du code injecté » est précisément la stratégie d'exploitation — un guerrier qui écrase le code adverse avec ses propres instructions détourne le flux d'exécution de la VM. Le saut indirect est à la fois le mécanisme de la VM (dispatch) et l'arme du guerrier (détournement) — la même primitive vue des deux côtés de l'arène.

Le principe Aliasing XOR Mutability (AXM) est le fondement du système d'emprunts de Rust. Formulé à l'origine par Niko Matsakis dans son article fondateur de novembre 2012 (« Imagine never hearing the phrase 'aliasable, mutable' again »), puis formalisé dans les papiers académiques RustBelt et GhostCell, ce principe énonce : à tout instant, pour une zone mémoire donnée, on peut avoir soit plusieurs références de lecture (&T), soit une seule référence d'écriture (&mut T), mais jamais les deux en même temps. Le Rust Programming Language Book (Ch.4 — Understanding Ownership) reformule cette règle en termes accessibles : « At any given time, you can have either one mutable reference or any number of immutable references. » C'est cette règle qui permet au compilateur Rust de garantir l'absence de data races à la compilation, sans coût runtime.

L'arène Corewar est littéralement un état mutable partagé globalement (Shared Mutable State) — l'antipathe absolu du modèle Rust. Plusieurs processus modifient le même tableau de 4096 octets en même temps : chaque sti écrit dans l'arène, chaque ldi lit depuis l'arène, et ces opérations peuvent se chevaucher (un processus écrit à l'adresse 42 pendant qu'un autre lit à l'adresse 40). En C, c'est l'anarchie : on écrit où on veut, quand on veut, avec des pointeurs nus. En Rust, le borrow checker interdit par construction de prendre &mut arena[42] et &arena[40] simultanément si le compilateur ne peut pas prouver qu'ils ne se chevauchent pas.

La solution architecturale pour implémenter la VM Corewar en Rust est de passer une référence mutable unique &mut [u8; 4096] à la fonction d'exécution, et d'utiliser des index (des entiers usize) plutôt que des pointeurs nus pour représenter le PC des processus. Les index ne sont pas des références — le borrow checker ne les traite pas comme des emprunts. On peut avoir autant d'index qu'on veut en même temps ; ce n'est qu'au moment de l'accès effectif (arena[pc]) que l'emprunt a lieu, et il est de durée infinitésimale (une instruction à la fois). De plus, l'utilisation de split_at_mut() permet de diviser l'arène en tranches non-chevauchantes pour écrire et lire simultanément des zones distinctes — satisfaisant le compilateur tout en préservant la sémantique Corewar.

Une alternative encore plus idiomatique est le pattern Entity-Component-System (ECS), populaire dans les moteurs de jeux (Legion, Bevy). L'ECS résout le problème de l'état mutable partagé en séparant le stockage des données de la logique qui les manipule : l'arène, les processus, et les métadonnées de propriété sont des composants stockés dans des tableaux contigus, et les systèmes (dispatch, exécution, vérification) accèdent à chaque composant séparément via des références disjointes. Le borrow checker est satisfait par construction car chaque système ne prend que les emprunts dont il a besoin, sans chevauchement. L'ECS est la solution standard au problème « beaucoup d'entités partagent un état global mutable » — et l'arène Corewar est exactement ce problème. En pratique, même sans framework ECS, l'indexation (utiliser des usize au lieu de références) suffit à résoudre le problème de l'AXM pour la VM Corewar, car chaque instruction ne touche qu'une à quatre cellules à la fois. L'AXM n'est pas l'ennemi de la modélisation de l'arène — c'est le guide qui mène aux patterns d'indexation et d'ECS qui rendent le code Rust à la fois sûr et performant.

Jung et al. (RustBelt: Securing the Foundations of the Rust Programming Language, 2018, POPL) formalisent le modèle d'ownership de Rust et prouvent sa sûreté mémoire. Le Rust Book (Ch.4, §4.1) énonce la règle fondamentale : « Each value in Rust has a variable that's called its owner. There can only be one owner at a time. When the owner goes out of scope, the value will be dropped. » Et la règle d'emprunt : « At any given time, you can have either one mutable reference or any number of immutable references. References must always be valid. »

L'implémentation d'une VM Corewar en C est un catalogue de violations de ces règles. Le bug n°1 est le use-after-free : quand un processus est tué, son PCB est retiré de la liste chaînée et libéré — mais si un autre pointeur référençait encore ce PCB (par exemple dans une boucle de parcours), l'accès suivant est un use-after-free. Le bug n°2 est le double-free : un processus tué par DAT puis éliminé par kill_zombies() peut être libéré deux fois si les deux chemins de nettoyage ne se coordonnent pas. Le bug n°3 est la data race : dans l'arène partagée, deux processus du même guerrier écrivent la même cellule dans le même cycle (impossible en round-robin, mais concevable dans une implémentation parallèle).

L'implémentation Rust élimine ces trois classes de bugs à la compilation. Le borrow checker garantit qu'un PCB libéré ne peut plus être référencé (la lifetime de la référence ne survit pas au drop). Le système d'ownership garantit qu'un PCB ne peut pas être libéré deux fois (un seul owner). Et les règles d'emprunt (une référence mutable OU plusieurs références immuables, jamais les deux) garantissent l'absence de data races. Le borrow checker est le static analysis tool que les implémenteurs C rêvent d'avoir — sauf qu'il est intégré au compilateur et refuse le code dangereux plutôt que de l'avertir.

Levine (Linkers and Loaders, pp.20-21) raconte l'origine du terme : « In a nod to Gulliver's Travels, the IBM/Motorola byte order scheme is known as 'big-endian' while the DEC/Intel scheme is called 'little-endian.' » Dans Les Voyages de Gulliver de Jonathan Swift (1726), les Lilliputiens se déchirent sur la question de savoir par quel bout il faut ouvrir un œuf à la coque — par le gros bout (Big-Endians) ou par le petit bout (Little-Endians). Le débat informatique est tout aussi ancien et tout aussi vigoureux.

Dans la pratique, le choix de l'endianness est déterminé par la compatibilité avec les systèmes existants : « In practice the major issue determining the choice of byte order is compatibility with older systems, since it is considerably easier to port programs and data between two machines with the same byte order than between machines with different byte orders. » (Levine, p.21) Le format .cor de Corewar a opté pour le Big Endian, comme les architectures IBM/Motorola et la plupart des protocoles réseau (TCP/IP utilise le Big Endian, appelé « network byte order »). Le format ELF va même jusqu'à encoder explicitement l'endianness dans son header (champ byteorder, Levine p.63) pour que le chargeur puisse détecter et compenser les différences — une sophistication dont le format .cor n'a pas besoin puisqu'il est toujours en Big Endian.

En C, la conséquence pratique est immédiate : sur une machine x86 (Little Endian), on ne peut PAS faire *(int*)&bytes[0] pour lire un entier 4 octets depuis l'arène. Il faut construire la valeur explicitement, octet par octet : (b[0] << 24) | (b[1] << 16) | (b[2] << 8) | b[3]. Cette technique de déconstruction/reconstruction est exactement celle décrite par Kernighan et Ritchie (The C Programming Language, §2.9) : « The bitwise AND operator & is often used to mask off some set of bits » et les opérateurs de décalage << et >> permettent de positionner chaque octet à sa place dans le mot 32 bits.

Sagan (Space-Filling Curves, 1994, Ch.1-2) décrit les courbes de remplissage (space-filling curves) comme des fonctions continues qui mappent l'intervalle [0,1] vers un espace de dimension supérieure [0,1]^n. La courbe de Hilbert (1891) et la courbe de Peano (1890) sont les exemples classiques. La propriété clé est la localité : des points proches dans [0,1] restent proches dans [0,1]^n. Cette localité est exploitée en informatique pour optimiser les accès mémoire — les bases de données utilisent les courbes de Hilbert pour indexer des données multidimensionnelles (Lawder & King, VLDB Journal 2001, vol. 10, p.35-53), et les GPU utilisent le Morton code (Z-order curve) pour le stockage des textures.

En Corewar, l'arène est unidimensionnelle (4096 cellules linéaires avec wrap-around), donc la question du balayage spatial se réduit à : quel pas de bombing couvre l'arène le plus efficacement ? Un bomber avec pas 1 couvre chaque cellule séquentiellement (linéairement optimal mais lent). Un bomber avec pas grand (comme IDX_MOD/2 = 256) couvre l'arène par grands sauts, puis revient remplir les trous — c'est l'équivalent d'une courbe de remplissage discrète en 1D. Le Dwarf classique bombe toutes les 4 cellules — un balayage grossier qui sacrifie la couverture pour la vitesse. L'analogie avec les courbes de remplissage est directe : tout comme la courbe de Hilbert préserve la localité en 2D tout en couvrant tout l'espace, un bon pattern de bombing en Corewar doit couvrir l'arène de manière uniforme tout en restant localisé (pour ne pas « sauter » par-dessus le code adverse). Le pattern de bombing optimal est l'équivalent 1D d'une courbe de Hilbert — une séquence qui couvre l'espace uniformément avec la meilleure localité possible.

Sweller (Cognitive Load During Problem Solving: Effects on Learning, 1988, Cognitive Science, vol. 12, p.257-285) et Sweller, Ayres et Kalyuga (Cognitive Load Theory, 2011, Springer, Ch.1-3) fondent la théorie de la charge cognitive (CLT) : la mémoire de travail humaine est limitée à environ 7±2 éléments (Miller, 1956) ou 4±1 chunks (Cowan, 2001), et l'apprentissage est optimal quand la charge cognitive est gérée. Sweller distingue trois types de charge : (1) Charge intrinsèque — la complexité inhérente au sujet, déterminée par le nombre d'éléments qui doivent être traités simultanément (l'interactivité des éléments). (2) Charge extrinsèque — la complexité ajoutée par la présentation, qui ne contribue pas à l'apprentissage (formatage confus, jargon non défini, structure désorganisée). (3) Charge germane — l'effort cognitif consacré à la construction de schémas mentaux, qui est le moteur réel de l'apprentissage.

Le projet Corewar est un cas extrême de charge cognitive élevée. La charge intrinsèque est massive : pour comprendre une seule instruction sti r1, %5, %3, l'étudiant doit simultanément connaître l'opcode (0x0B), l'OCP (0x68), le calcul d'adresse avec IDX_MOD, le Big Endian, le store_at avec +3, et les durées d'exécution. Ce sont au moins 6 éléments interdépendants — au-delà de la limite de la mémoire de travail. La charge extrinsèque est amplifiée par la confusion ICWS vs 42 : deux vocabulaires pour les mêmes concepts, des mnémoniques différents, des sémantiques subtiles. La charge germane — le véritable apprentissage — est comprimée par les deux autres charges.

Sweller recommande le principe de segmentation (segmenting principle, Ch.7) : décomposer le contenu en segments présentés séquentiellement, chaque segment maîtrisé avant de passer au suivant. Il recommande aussi le pré-entraînement (pre-training principle, Ch.8) : enseigner les concepts clés (carry, IDX_MOD, mem_mod) avant de les intégrer dans des explications complexes. Ce guide applique ces principes : les sections sont ordonnées du simple (arène) au complexe (optimisation), chaque concept est défini avant d'être utilisé, et les insight-boxes séparent le contenu normatif (ce qu'il faut savoir) du contenu enrichissant (les connexions académiques). La théorie de Sweller nous enseigne que la densité du guide n'est pas une qualité — c'est un défi à gérer par segmentation, pré-entraînement, et séparation des niveaux de complexité.

Patterson et Hennessy (Computer Organization and Design, 5e éd., §4.5-4.7) identifient trois types de hazards de pipeline qui empêchent l'exécution fluide des instructions : (1) les hazards structurels (conflit de ressources — deux instructions veulent accéder à la même unité fonctionnelle) ; (2) les hazards de données (dépendances RAW — Read After Write, WAR — Write After Read, WAW — Write After Write) ; (3) les hazards de contrôle (les branchements conditionnels dont l'issue n'est pas encore connue). Chaque type de hazard impose un stall (attente) ou requiert un mécanisme de contournement (forwarding, prédiction, spéculation).

Corewar élimine les trois hazards en choisissant le pipeline de profondeur 1 (mono-cycle). Un pipeline de profondeur 1 ne peut pas avoir de hazard structurel (une seule instruction à la fois, une seule unité fonctionnelle). Il ne peut pas avoir de hazard de données (l'instruction précédente est complètement terminée avant que la suivante ne commence — le forwarding est trivial). Il ne peut pas avoir de hazard de contrôle (le branchement est résolu avant que la prochaine instruction ne commence). Ce choix est radical : au lieu de gérer les hazards, Corewar les rend structurellement impossibles. Le coût est un CPI de 1 (au mieux) et l'impossibilité d'exploiter le parallélisme d'instructions. Mais la simplicité est immense : pas de logique de détection de hazard, pas de forwarding path, pas de prédicteur de branchement, pas de reorder buffer. Le processeur Corewar est le plus simple possible — un pipeline de profondeur 1. Corewar n'a pas de hazards parce qu'il n'a pas de pipeline — et c'est le pipeline lui-même qui est le hazard.

Hyde (The Art of Assembly Language, Ch.6.4.3, p.379) explique que pour un compteur cyclant de 0 à 2^n - 1, on peut utiliser INC counter; AND mask, counter au lieu du modulo coûteux. Le masque AND implémente le modulo pour les tailles puissance de 2. Pour une taille non puissance de 2, le modulo reste nécessaire.

C'est exactement le fonctionnement de l'adressage circulaire de Corewar : CORE_SIZE = 4096 = 2^12, donc address % 4096 se réduit à address & 0xFFF — une seule opération bitwise au lieu d'une division matérielle. Si CORE_SIZE avait été fixé à 4000 (nombre rond mais pas puissance de 2), chaque calcul d'adresse nécessiterait un véritable modulo, ce qui serait désastreux pour la performance : un modulo matériel coûte 20-40 cycles contre 1 cycle pour un AND. Le choix de 4096 n'est pas arbitraire — c'est une optimisation de performance fondamentale qui rend l'arène circulaire gratuite en termes de calcul. CORE_SIZE = 4096 transforme la circularité d'un coût en une feature gratuite — la puissance de 2 est le secret de la vitesse de la VM.

Hennessy et Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §3.3, p.200-210) décrivent le prédicteur de branchement des processeurs modernes : un ensemble de structures hardware (Branch Target Buffer, Pattern History Table, Return Stack Buffer) qui prédisent la cible et l'issue (pris/non pris) de chaque branchement. Le taux de misprediction typique est de 5-10% sur du code général, mais peut atteindre 30%+ sur les branchements indirects (switch, pointeurs de fonction) car le prédicteur doit deviner parmi plusieurs cibles. H&P montrent que chaque misprediction coûte 15-20 cycles (pipeline flush), ce qui se traduit en une pénalité de CPI de 0.5-1.0 par branchement mal prédit.

Le dispatch d'opcodes de la VM Corewar est un branchement indirect massif : à chaque cycle, le switch/match saute vers l'un des 16 handlers d'instructions. Sur une VM qui exécute des millions de cycles, le taux de misprediction de ce branchement est le facteur déterminant de la performance. Trois stratégies existent, par ordre croissant d'efficacité : (1) Jump table (switch/match standard) : le compilateur génère une table d'adresses indexée par l'opcode. Le CPU doit prédire la cible parmi 16 possibilités. Le taux de misprediction dépend du pattern d'opcodes — un guerrier en boucle de bombing (sti / add / zjmp / sti / add / zjmp...) est hautement prévisible, mais un guerrier polymorphe avec des chemins diversifiés l'est beaucoup moins. (2) Computed gotos (GCC) : chaque handler se termine par goto *dispatch_table[next_opcode], permettant au BTB de mémoriser le pattern. Ertl et Gregg (The Structure and Performance of Efficient Interpreters, 2003, JIVM) mesurent un speedup de 15-25% par rapport au switch. (3) Threaded code (direct threading) : chaque instruction contient l'adresse de l'instruction suivante, éliminant complètement le dispatch central. C'est la technique utilisée par FORTH et par certaines VMs hautement optimisées.

Pour Corewar, le zjmp est le branchement le plus difficile à prédire : sa cible dépend du carry, qui est positionné par l'instruction précédente. Si le pattern est régulier (carry toujours à 1 dans une boucle), la prédiction est bonne ; si le carry est imprévisible (dépend du résultat de ld sur des données variables), le prédicteur rate systématiquement. Le CPI hôte de la VM est dominé par la misprediction du dispatch d'opcodes — et le pattern du guerrier détermine si la VM sera rapide ou lente.

Hennessy et Patterson énoncent la Loi d'Amdahl : Speedup = 1 / [(1 − Fraction_améliorée) + Fraction_améliorée / Speedup_améliorée]. Le corollaire crucial est que l'amélioration incrémentale diminue à mesure qu'on ajoute des optimisations — c'est la loi des rendements décroissants. H&P illustrent cela avec un exemple frappant : accélérer le FPSQR par 10× (20% du temps) donne un speedup de 1.22, tandis qu'accélérer toutes les instructions FP par 1.6× (50% du temps) donne 1.23 — la fraction compte plus que le facteur d'accélération. Pour un guerrier Corewar, la boucle de bombardement (main loop) représente typiquement 95%+ des cycles, tandis que la séquence de boot s'exécute une seule fois. Optimiser le boot pour gagner 2 cycles est futile si la boucle en consomme des milliers. Le §1.11 renforce ce point avec le Pitfall : « Falling prey to Amdahl's heartbreaking law » — presque tous les architectes déploient un effort énorme sur une feature avant d'en mesurer l'usage réel, pour découvrir un speedup décevant. En Corewar : profilez d'abord, optimisez ensuite.

H&P décomposent le temps CPU en la formule fondamentale : CPU time = Instruction Count × CPI × Clock cycle time, ou de façon plus fine : CPU time = Σ(IC_i × CPI_i) × T_clock. Cette équation est « the Iron Law of Processor Performance » — les trois leviers sont interdépendants (ISA affecte IC et CPI, organisation affecte CPI et T_clock, technologie affecte T_clock). Pour la VM Corewar, T_clock est fixe (déterminé par l'implémentation de la machine virtuelle), donc la performance d'un guerrier se réduit à : Total_Cycles = Σ(IC_opcode × CPI_opcode). Deux leviers seulement : réduire le nombre d'instructions (code plus compact, moins de NOP), ou choisir des opcodes à CPI plus faible. H&P note que « CPI_i should be measured and not just calculated from a table in the back of a reference manual since it must include pipeline effects, cache misses, and any other memory system inefficiencies » — en Corewar, l'équivalent est que le CPI effectif dépend du contexte d'exécution (adresse dans l'arène, état des processus concurrents).

H&P : « Perhaps the most important and pervasive principle of computer design is to focus on the common case : favor the frequent case over the infrequent case. This principle applies when determining how to spend resources, since the impact of the improvement is higher if the occurrence is frequent. » H&P ajoutent un point subtil : « the frequent case is often simpler and can be done faster than the infrequent case » — par exemple, l'addition sans overflow est le cas commun et se fait plus vite qu'avec overflow. En Corewar, ce principe dicte la structure même d'un guerrier compétitif : la boucle de scan/bombardement est le cas fréquent (exécuté des milliers de fois), le boot est le cas rare (exécuté une fois). Un guerrier qui optimise sa boucle principale — en minimisant les instructions, en choisissant les opcodes les plus rapides, en maximisant les DAT-kills par cycle — applique exactement ce principe. Inversement, un guerrier sophistiqué avec un boot complexe mais une boucle sous-optimale viole ce principe. Investissez vos cycles proportionnellement au temps passé.

H&P documentent l'arrêt brutal de la croissance des fréquences d'horloge en 2003 : « Since 2003, single-processor performance improvement has dropped to less than 22% per year due to the twin hurdles of maximum power dissipation of air-cooled chips and the lack of more instruction-level parallelism to exploit efficiently. » La puissance dynamique ∝ Capacitance × Voltage² × Frequency signifie que monter en fréquence coûte quadratiquement en énergie. H&P notent que « In low-end applications, such as cell phones, the cost in power and silicon area of the x86-translation overhead helped lead to a RISC architecture, ARM, becoming dominant » — ARM a expédié 6.1 milliards de puces en 2010, 20× plus que x86. La leçon pour Corewar est profonde : les ISA simples et réguliers (comme le Redcode) ne sont pas des vestiges pédagogiques, mais l'aboutissement logique d'une trajectoire architecturale. Le VM Corewar est un processeur in-order single-issue — exactement le type d'architecture qui domine quand la complexité coûte plus qu'elle ne rapporte. Le §1.11 enfonce le clou : « The La-Z-Boy programmer era of relying on hardware designers to make their programs go faster without lifting a finger is officially over. » En Corewar, il n'y a pas de hardware pour vous sauver — l'optimisation est entièrement à la charge du programmeur.

Le §1.11 des Fallacies énonce : « Peak performance tracks observed performance » est une fallacie. H&P montrent que le pourcentage de performance de pointe réellement atteint varie de 5% à 58% selon le programme et le processeur. La définition cinglante : « The only universally true definition of peak performance is the performance level a computer is guaranteed not to exceed. » En Corewar, la « performance de pointe » d'un guerrier est son taux de bombardement théorique dans l'arène vide — par exemple, un scanner qui bomb chaque cycle. Mais contre un adversaire réel, ce taux chute à cause des collisions, des interruptions de processus (SPL), et de la pression de CYCLE_TO_DIE. Un guerrier qui paraît optimal sur papier peut perdre systématiquement car sa performance de pointe n'est jamais atteinte en conditions réelles. La performance mesurée contre un pool représentatif est le seul indicateur fiable.

Le §1.7 (6e édition) définit les métriques fondamentales de fiabilité : le MTTF (Mean Time To Failure, en heures), le FIT (Failures In Time = défaillances par milliard d'heures — un MTTF de 106 heures = 1000 FIT), le MTTR (Mean Time To Repair), et la disponibilité = MTTF / (MTTF + MTTR). H&P illustrent avec un sous-système disque : 10 disques à 106 h de MTTF + contrôleur + alimentation + ventilateur = 23 000 FIT système, soit un MTTF système de 43 500 heures (~5 ans). L'ajout d'une alimentation redondante améliore le MTTF de l'alimentation de 200 000 h à 830 millions d'heures — facteur 4150× ! En Corewar, chaque processus a un MTTF mesuré en cycles avant qu'un MOV adverse ne l'écrase. Un processus unique (single-process warrior) a un MTTF faible — n'importe quel DAT le tue. Un guerrier avec N processus via SPL a un MTTF système bien plus élevé, car la « panne » (tous les processus tués) nécessite N frappes réussies. La redondance de processus est l'équivalent exact de la redondance matérielle : MTTF_système augmente quadratiquement avec le nombre de copies redondantes. C'est la justification quantitative de la stratégie « forker pour survivre ».

Le §3.13 (6e édition) identifie un Pitfall surprenant : « Sometimes bigger and dumber is better ». Les processeurs agressifs des années 2000 (Pentium 4 à 20+ étages, Itanium au peak issue rate le plus élevé) n'ont jamais atteint leur performance de pointe car « the main limitation in exploiting ILP often turned out to be the memory system ». La solution ? Construire de plus grands caches au lieu de pipelines plus profonds. L'Itanium 2 et l'i7 utilisent des caches trois niveaux (8-9 Mio en L3) contre seulement 2 Mio en L2 pour le Pentium 4 — et cette approche « plus simple et plus grosse » s'est révélée plus efficace. En Corewar, le parallèle est frappant : il n'y a pas de cache du tout, mais le principe s'applique à la stratégie de guerrier. Un guerrier avec une boucle de bombardement simple et une grande couverture spatiale (bigger) bat souvent un guerrier avec un code sophistiqué mais une couverture étroite (smarter but smaller). Quand le goulot d'étranglement est l'accès aux données, investir dans la couverture plutôt que dans la complexité calculatoire.

L'architecture des processeurs se divise historiquement en deux philosophies : CISC (Complex Instruction Set Computer) et RISC (Reduced Instruction Set Computer). Comme l'expliquent Bryant et O'Hallaron (CSAPP §4.1), les ISA CISC comme l'x86-64 possèdent un grand nombre d'instructions (le manuel Intel dépasse 1200 pages), des encodages de longueur variable (1 à 15 octets), et permettent des opérations arithmétiques directement en mémoire. Les ISA RISC, à l'inverse, ont moins de 100 instructions, des encodages de longueur fixe (typiquement 4 octets), et adoptent une architecture load/store : seules les instructions load et store accèdent à la mémoire, toutes les opérations arithmétiques se font entre registres.

L'ISA de Corewar se situe entre les deux, comme le Y86-64 pédagogique de CSAPP :

Le Corewar est du côté RISC pour l'architecture load/store et le petit nombre d'instructions, mais du côté CISC pour l'encodage variable et les codes de condition. Comme le note CSAPP : « Y86-64 includes attributes of both CISC and RISC instruction sets. On the CISC side, it has condition codes and variable-length instructions. On the RISC side, it uses a load/store architecture and a regular instruction encoding. » Le Corewar suit exactement le même modèle hybride.

Le Dragon Book (Compilers, Ch.8, p.507) souligne un aspect supplémentaire qui rapproche Corewar du CISC : « A CISC machine typically has few registers, two-address instructions, a variety of addressing modes. » Contrairement aux architectures RISC qui utilisent un code à trois adresses (ex: ADD r1, r2, r3 pour r1 = r2 + r3), le Redcode est fondamentalement un langage à deux adresses (champ A et champ B). Une instruction comme ADD.AB 4, 5 lit la valeur à l'adresse relative +4, l'ajoute à celle située à +5, et stocke le résultat directement en +5 — la destination est aussi la deuxième source. Cette conception oblige le joueur à penser la mémoire à la fois comme source et destination, une caractéristique typique des anciennes architectures CISC très denses. Le mode d'adressage indirect (@) et les modificateurs de pré-décrément/post-incrément ajoutent encore à cette complexité CISC, offrant une variété de modes d'adressage que le Dragon Book identifie comme un défi classique pour les générateurs de code.

H&P §A.2 classent les ISA en quatre familles : stack, accumulator, register-memory (1 opérande mémoire par instruction ALU), et load-store (0 opérande mémoire). Or, Corewar est souvent présenté comme « RISC-like », mais il permet à une instruction ALU comme add de prendre un opérande T_IND — c'est-à-dire une lecture mémoire directe sans load préalable. Dans la taxonomie de H&P (Figure A.3), Corewar tombe donc dans la catégorie register-memory, au même titre que l'IBM 360 ou le 80x86, et non dans la catégorie load-store de MIPS ou ARM. C'est un paradoxe fondamental : un ISA à 16 instructions, philosophiquement minimaliste, adopte structurellement le modèle que H&P associent au CISC. La conséquence pratique est que chaque instruction Corewar peut cacher un accès mémoire, ce qui rend la taille d'instruction variable et le décodage plus complexe — exactement le trade-off que H&P identifient : « Clocks per instruction vary by operand location ».

H&P §A.8 recommandent « provide primitives, not solutions » et « less is more in the design of an instruction set ». La Figure A.13 montre que 10 instructions simples comptent pour 96% des exécutions sur 80x86 : load, conditional branch, compare, store, add, and, sub, move, call, return. Corewar pousse cette logique à son terme : avec seulement 16 instructions, il couvre tout ce qui est nécessaire pour un jeu de programmation compétitif. Pas de multiplication, pas de division, pas de floating-point, pas d'opérations sur chaînes — et pourtant, les guerriers Corewar réalisent des algorithmes de recherche, de bombardement et de copie avec ces seules primitives. C'est la validation extrême du principe H&P : un ISA minimaliste, orthogonal, avec des primitives composables, bat un ISA riche en instructions spécialisées. Les 16 opcodes de Corewar sont les « primitives, not solutions » que H&P appellent de leurs vœux.

La note de design dans Crafting Interpreters compare les VM stack-based (JVM, CPython — les opérandes sont empilés/dépilés) aux VM register-based (Lua 5.0+ — les instructions lisent/écrivent directement dans des slots). Lua a switché de stack à register en 5.0 et a mesuré un gain de vitesse significatif. Le Corewar est un cas fascinant : il est ni stack ni register pur. Il possède 16 registres (r1-r16) comme une machine à registres, mais ses modes d'adressage indirect (T_IND) ajoutent un niveau d'indirection similaire à une pile. De plus, l'absence de pile d'exécution signifie que les « temporaires » doivent vivre dans des registres ou en mémoire — il n'y a pas de push/pop. Cette hybridité est unique et reflète les contraintes d'un jeu où chaque instruction coûte un cycle.

Hennessy & Patterson (6e éd., §3.2-3.3, p.168-182) décrivent les deux techniques historiques d'exécution out-of-order : le scoreboarding (CDC 6600, Thornton 1964) et l'algorithme de Tomasulo (IBM 360/91, 1967). Le scoreboarding permet l'exécution out-of-order en surveillant les conflits de ressources : chaque instruction vérifie une « scoreboard » avant de s'exécuter, et ne procède que si ses opérandes sont disponibles et son unité fonctionnelle libre. Tomasulo améliore le scoreboarding en ajoutant le register renaming via des reservation stations — chaque instruction copie ses opérandes dans une station et attend là, libérant les registres pour d'autres instructions.

MARS implémente ni scoreboarding ni Tomasulo. L'exécution est strictement in-order : fetch → decode → wait → execute, et l'instruction suivante ne commence qu'après la fin de la précédente. Le pipeline est de profondeur 1 (ou plus précisément, de profondeur variable avec un seul bulletin en vol). H&P (§3.2, p.169) montrent que le scoreboarding du CDC 6600 obtenait un speedup de 1.7× sur du code vectoriel — en Corewar, ce speedup est impossible car il n'y a pas d'unités fonctionnelles multiples. Un guerrier qui exécute add ne peut pas « overlap » avec un ld du même processus — les deux sont séquentiels. Le scoreboarding nécessite des unités fonctionnelles multiples (ALU, FPU, load/store unit) ; MARS n'en a qu'une seule qui fait tout. MARS est le CDC 6600 sans scoreboard, l'IBM 360/91 sans Tomasulo — un processeur in-order pur, par nécessité et par design.

H&P §3.12 décrivent le multithreading à grain fin : commutation de thread à chaque cycle d'horloge, en round-robin, en sautant les threads bloqués. C'est exactement le scheduler MARS. Le Sun T1 (Niagara), processeur emblématique de cette approche, utilisait un pipeline simple 6 étages mono-émission avec 4 threads par cœur. H&P notent : « fine-grained multithreading works perfectly for a single issue processor, and SMT would make no sense » — l'hyper-threading n'a de sens que sur un superscalaire. Corewar, mono-émission par construction, incarne ce principe à l'état pur : chaque processus prend exactement un cycle, puis cède la place. Le T1 affichait un CPI par thread de 7.2 mais un CPI par cœur de 1.80 (4 threads) — la lenteur individuelle est le prix de la survie collective. En Corewar, SPL crée exactement ce modèle : un guerrier à N threads progresse N fois plus lentement par thread, mais occupe N fois plus de cycles d'arène. La stratégie est la même que celle du T1 : sacrifier la latence individuelle pour maximiser le débit global.

H&P §5.9 racontent l'histoire de SGI en 2000 : l'OS protégeait la table des pages avec un seul verrou, présumant que les allocations de pages étaient rares. Sur uniprocesseur, aucun problème. Sur multiprocesseur, ce verrou unique sérialisait toutes les initialisations parallèles — détruisant le parallélisme par un goulot d'étranglement inattendu. Le piège : un logiciel conçu pour l'uniprocesseur, adapté au multiprocesseur sans repenser les structures de données partagées. Corewar illustre le problème inverse et plus fondamental : les warriors sont des programmes conçus pour un modèle sans synchronisation, s'exécutant dans un environnement multiprocessus. La « table des pages » de Corewar, c'est l'arène elle-même. Chaque processus écrit sans verrou, sans coordination, sans protocole de cohérence. H&P notent que la solution SGI fut de placer des verrous sur des portions plus fines de la table. Dans Corewar, il n'y a pas de verrou possible — la seule « protection » est la distance spatiale (écrire loin de son propre code) ou la redondance (copier son code critique). C'est le paradigme de la programmation sans filet : là où un système réel offre des mécanismes de plus en plus fins (MESI → directory → LL/SC → locks → barriers), Corewar n'offre rien.

Le §3.11 (NOUVEAU dans la 6e édition) rapporte les mesures d'Esmaeilzadeh et al. (2011) sur l'i7 : le SMT (2 threads/cœur) offre un speedup moyen de 1.28× sur les benchmarks Java et 1.31× sur PARSEC — bien loin des 2× théoriques. Deux benchmarks avec peu de parallélisme ne gagnent presque rien. H&P attribuent cette modestie au fait que « existing implementations of SMT offer only two to four contexts with fetching and issue from only one [thread], and up to four issues per clock ». En Corewar, la leçon est double : (1) ajouter des processus via SPL n'accélère pas linéairement — chaque thread dilue le temps CPU, et (2) si le travail par thread est trivial (un SPL suivi d'un DAT), le « parallélisme » est illusoire. Le speedup SMT de 1.28× est le plafond réaliste du multithreading matériel quand les threads partagent des ressources — MARS obtient le même type de compromis par construction : plus de processus = plus de couverture, mais chaque processus progresse plus lentement.

Le §3.12 (6e édition) décrit l'ARM Cortex-A53, processeur dual-issue in-order pour tablettes et smartphones. Son CPI idéal est de 0.5 (deux instructions par cycle), mais en pratique sur SPECint2006, le CPI varie de 1.0 à 8.6 — les stalls dégradent le CPI d'un facteur 2× à 17×. Trois sources de stalls : hazards fonctionnels (deux instructions veulent la même unité), hazards de données (dépendances RAW), hazards de contrôle (misprediction = 8 cycles de penalty). L'A53 consomme ~1/200ème de la puissance d'un i7 pour un processeur quadricœur. MARS est un A53 encore plus simple : mono-issue (CPI idéal = 1, pas 0.5), pas de prédiction de branchement (donc pas de misprediction penalty), pas de cache (donc pas de cache miss stalls). Si l'A53 est un « RISC pour mobile », MARS est un « RISC pour arène » — la même philosophie de simplicité, poussée à l'extrême. Le CPI de MARS est exactement 1.0, sans variance — la régularité absolue que l'A53 ne peut qu'approcher.

Le §3.11 (NOUVEAU dans la 6e édition) distingue trois formes de multithreading : à grain grossier (coarse-grained, commute uniquement sur les stalls coûteux), à grain fin (fine-grained, commute chaque cycle en round-robin), et simultané (SMT, sur superscalaire). H&P notent que le coarse-grained souffre d'un « pipeline start-up cost » : quand un thread prend la relève après un stall, le pipeline doit se remplir, créant des bulles. Le fine-grained élimine ce coût en intercalant systématiquement, mais « it slows down the execution of an individual thread because a thread that is ready to execute without stalls will be delayed by instructions from other threads ». MARS est du grain fin pur : chaque processus prend exactement une instruction, puis cède — exactement le modèle du Sun T1. H&P précisent que « fine-grained multithreading works perfectly for a single issue processor, and SMT would make no sense » — l'hyper-threading n'est pertinent que sur un superscalaire, ce que Corewar n'est pas et ne peut pas être. Le grain fin est l'unique modèle de multithreading qui ait du sens pour MARS.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., Ch.4, §4.2-4.3) décrivent les architectures vectorielles/SIMD : une seule instruction opère sur multiples données. Le strip mining gère les vecteurs plus longs que la longueur maximale hardware (MVL) en les découpant en morceaux de taille MVL.

L'instruction sti (store indirect) en Corewar est une forme primitive de SIMD : elle écrit une valeur à une adresse calculée en une instruction, effectuant simultanément le calcul d'adresse et l'écriture mémoire. Plus profondément, fork/lfork est une opération parallèle à instruction unique : une instruction crée un contexte d'exécution entièrement nouveau, analogue à la façon dont une instruction vectorielle crée des opérations concurrentes multiples. Le strip mining s'applique au bombing multi-processus : si l'arène est « trop grande » pour un seul processus (comme un vecteur plus long que le MVL), le guerrier « strip mine » en créant N processus, chacun couvrant une bande de 4096/N cellules. fork est l'instruction SIMD de Corewar — une instruction lance du travail parallèle, et le strip mining détermine combien de processus sont nécessaires pour couvrir l'arène entière.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §5.5, p.414) décrivent le couple Load-Linked/Store-Conditional (LL/SC) : LL lit une valeur et crée une « réservation » ; SC écrit seulement si la réservation est encore valide (aucune écriture intervening d'un autre processeur). Si le SC échoue, le programme réessaie. LL/SC est le mécanisme atomique fondamental des architectures RISC modernes (MIPS, ARM, RISC-V).

Dans un guerrier Corewar multi-processus, deux processus peuvent se disputer la même cellule — un problème classique de lost-update. Le jeu d'instructions Redcode ne fournit aucune primitive atomique de lecture-modification-écriture. Il n'y a pas de LL/SC, pas de compare-and-swap, pas de fetch-and-add. Deux processus qui ld une cellule, la modifient, puis sti peuvent perdre une modification — exactement le problème que LL/SC résout. Cela force les concepteurs de guerriers à l'une de deux stratégies : (1) partitionner — chaque processus écrit dans un ensemble disjoint de cellules (pas de partage, pas de conflits), ou (2) communiquer via l'arène — un processus écrit une cellule drapeau, l'autre la lit et cède. L'absence de LL/SC en Redcode signifie que la coordination inter-processus doit reposer sur la communication, pas sur l'atomicité — l'arène est le seul mécanisme de synchronisation.

Nystrom affirme que la fonction run() de clox — une boucle infinie avec un switch géant sur les opcodes — est « la fonction la plus importante de tout clox, de loin. L'interpréteur passe quelque chose comme 90% de son temps à l'intérieur de run() ». La boucle principale de MARS est exactement la même chose : un switch/case sur les 16 opcodes Redcode. Les techniques d'optimisation mentionnées — direct threaded code, computed goto, jump tables — s'appliquent toutes à MARS. GCC et Clang optimisent souvent les grands switch/case en tables de saut natives, ce qui élimine la cascade de comparaisons. Pour une VM Corewar en C, s'assurer que le compilateur C génère une jump table plutôt qu'une cascade de if est l'optimisation single la plus impactante. En Rust, le match sur un enum a le même comportement.

H&P §3.10 définissent le processeur idéal par 5 hypothèses : (1) renommage infini de registres, (2) prédiction de branchement parfaite, (3) prédiction de saut parfaite, (4) analyse parfaite d'alias mémoire, (5) caches parfaites. Muni de ces cinq conditions, le parallélisme disponible plafonne à ~18-150 instructions/cycle selon les programmes (SPEC92). Corewar viole toutes ces hypothèses : zéro renommage, zéro prédiction de branchement, zéro analyse d'alias, et mémoire directe sans cache. Mais le constat frappant de H&P est que même avec l'idéal, les programmes entiers (type li, un interpréteur LISP) plafonnent à ~18 IPC — car leurs chaînes de dépendances courtes et leurs branchements fréquents limitent fondamentalement le parallélisme. Les guerriers Corewar, avec leurs blocs de base de 3-6 instructions et leur auto-modification constante, ressemblent à li : leur ILP intrinsèque est si faible que l'absence de support matériel les pénalise bien moins qu'on ne le croirait. Le plafond est bas, et Corewar est déjà proche du sol.

H&P §3.9 consacrent un développement à la prédiction de valeur : prédire la valeur produite par une instruction pour briser les chaînes de dépendance. Le verdict est sans appel : « over 100 papers on the subject has achieved a significant enhancement in ILP when using a realistic prediction scheme ». La prédiction de valeur matérielle échoue car les valeurs sont intrinsèquement imprévisibles dans un programme général. Mais en Corewar, la prédiction de valeur prend une forme radicalement différente : un guerrier prédit ce que l'adversaire va écrire dans l'arène. Un bomber prédit que les cases cibles contiendront du code adverse. Un scanner prédit le motif d'instructions ennemi. H&P distinguent la prédiction de valeur (échoue) de la prédiction d'alias d'adresse (réussit partiellement) — en Corewar, c'est l'alias qui intéresse le guerrier : « mon MOV va-t-il écraser une case occupée par l'adversaire ? ». Cette prédiction d'alias stratégique est précisément ce que font les scanners : sonder l'arène pour prédire les conflits d'adresse avant de bombarder. Le hardware n'a pas su exploiter la prédiction de valeur ; le guerrier Corewar l'exploite par conception.

H&P §3.10 (Figure 3.27) montrent la relation entre taille de fenêtre d'instructions et parallélisme exploitable. Pour les programmes entiers, passer d'une fenêtre infinie à 64 entrées fait chuter l'IPC de ~55 à ~15 (pour gcc) ; à 32 entrées, on tombe à ~10. En Corewar, la « fenêtre d'instructions » d'un guerrier est dictée par la portée de ses MOV : il ne peut « voir » et affecter que les cases dans son rayon d'écriture. Un guerrier agressif avec des MOV longue portée a une grande fenêtre mais un cycle d'exécution plus long (plus de terrain à couvrir). Un guerrier compact (paper) a une fenêtre minuscule mais se replie vite. Le trade-off est le même que H&P identifient pour les processeurs réels : élargir la fenêtre coûte exponentiellement plus en ressources pour un gain marginal décroissant. Le guerrier optimal se situe au point où le coût d'élargissement de la fenêtre égale le gain en couverture — exactement le compromis que les architectes de processeurs ont dû faire quand ils ont abandonné les fenêtres de 128+ entrées pour se limiter à 40-50 instructions.

H&P App.C donnent la formule fondamentale de performance pipeline : CPI_pipelined = Ideal_CPI + Pipeline_stall_cycles_per_instruction, où Stall_cycles = Branch_stalls + Data_stalls + Structural_stalls. Pour le R4000, H&P montrent que ces stalls dégradent le CPI de 1 (idéal) à 1.2–2.8 en pratique. Pour Corewar, les trois termes sont zéro par construction : pas de pipeline → pas de hazards de données (RAW, WAR, WAW impossibles), pas de hazards de contrôle (pas de prédiction de branchement, zjmp est résolu dans le même cycle), pas de hazards structurels (une seule instruction par cycle, une seule unité fonctionnelle). La formule se réduit à CPI = 1 + 0 = 1, l'idéal théorique. Ce n'est pas une optimisation — c'est une élimination par conception. Le mono-cycle de Corewar est le seul design où la formule de H&P donne son résultat minimal sans aucune ingénierie de forwarding, de prédiction ou de scheduling.

H&P §A.7 distinguent trois styles d'encodage : variable (80x86, VAX), fixe (MIPS, ARM), et hybride (IBM 360, Thumb). Le format .cor de Corewar est un cas hybride particulier : l'opcode détermine le format (comme en fixe), mais l'OCP (Octet de Code Paramètre) spécifie le mode d'adressage de chaque opérande (comme en variable), et la taille totale varie de 1 à 5 octets selon les types d'opérandes. H&P disent : « the architect more interested in code size than performance will pick variable encoding, and the one more interested in performance than code size will pick fixed encoding ». Corewar choisit la compacité : l'arène fait MEM_SIZE octets, et chaque octet compte. L'OCP est le compromis élégant — un seul octet qui encode jusqu'à 3 types d'opérandes, évitant les address specifiers séparés du VAX tout en restant plus compact que le fixe 32-bit de MIPS. C'est l'encodage hybride poussé à son minimum : un octet de contrôle, pas plus.

L'Appendice C §C.2 (6e édition) décrit le delayed branch : dans les premiers RISC (MIPS, SPARC), l'instruction suivant un branchement est toujours exécutée (le « branch delay slot »), que le branchement soit pris ou non. Le compilateur doit trouver une instruction utile à y placer. RISC-V a explicitement supprimé cette feature : « RISC-V appropriately omitted delayed branches » car elle « complicates implementation when there is dynamic branch prediction ». Corewar n'a jamais eu de branch delay slot : zjmp (le seul branchement conditionnel) prend effet immédiatement. C'est un choix de simplicité cohérent avec RISC-V : dans un modèle sans prédiction de branchement (comme MARS), le delayed branch n'apporterait rien — il n'y a pas de « bubble » à remplir car il n'y a pas de pipeline. L'absence de delay slot en Corewar est doublement justifiée : pas de pipeline à optimiser, pas de prédiction à compliquer. C'est un exemple où Corewar, par sa simplicité, a anticipé une décision que RISC-V a prise 30 ans plus tard.

L'Appendice C §C.2 (6e édition) décrit l'évolution des prédicteurs de branchement : le prédicteur 1-bit a un défaut — même si un branchement est pris 99% du temps, il sera mal préduit deux fois à chaque changement (une fois quand il change, une fois quand il revient). Le prédicteur 2-bits (saturating counter) résout ce problème en exigeant deux mauvaises prédictions consécutives avant de changer de prédiction — c'est de l'hystérésis. Les taux de misprédiction sur SPEC89 varient de 1% à 18% selon les programmes (integer toujours pire que FP). En Corewar, l'équivalent est la prédiction du comportement adverse : un guerrier qui « prédit » que l'adversaire va bomber à gauche puis change de prédiction dès la première déviation est un prédicteur 1-bit — instable. Un guerrier qui maintient sa prédiction malgré quelques déviations est un prédicteur 2-bit — plus robuste au bruit. La leçon des prédicteurs 2-bits : il faut deux preuves de changement avant d'inverser sa stratégie.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §3.3, Fig. 3.4) décrivent le prédicteur gshare : il combine l'adresse du branchement et l'historique global des branchements via XOR pour indexer une table de prédiction. Ce prédicteur fonctionne « remarquablement bien pour un prédicteur simple » et sert de base de comparaison pour les prédicteurs plus avancés.

L'instruction zjmp (saut si carry=1) est le seul branchement conditionnel de Corewar. Un adversaire qui tente de prédire le comportement de branchement d'un guerrier pourrait utiliser un schéma de type gshare : XOR le PC courant du guerrier avec l'historique récent des résultats de zjmp pour prédire le prochain résultat. C'est exactement ce qu'un counter-warrior fait implicitement : il observe le pattern de vérification d'un scanner et en déduit où le scanner va sauter. Le prédicteur gshare formalise l'intuition qu'un historique de branchements, XORé avec la position, révèle la stratégie — meilleure est la prédiction, plus ciblée est la contre-attaque. En Corewar, lire les cellules autour du PC adverse pour inférer son historique de sauts est l'équivalent logiciel du prédicteur matériel.

H&P §5.2 détaillent le protocole MESI (Modified, Exclusive, Shared, Invalid) qui garantit que, quand un cœur écrit un bloc, toutes les autres copies sont invalidées avant que l'écriture ne soit considérée complète. Dans un système réel, cette invalidation coûte 50-170 cycles selon le nombre de cœurs partageant le bloc. Corewar n'a aucun protocole de cohérence — et n'en a pas besoin. L'arène est un espace mémoire unique sans cache : chaque STI écrit directement dans la mémoire partagée, chaque LD lit la valeur actuelle. Il n'y a jamais de copie périmée, jamais de coherence miss, jamais de false sharing. Cette absence est une feature : là où MESI doit arbitrer des invalidations broadcast sur un bus, Corewar obtient la cohérence trivialement. Mais le prix à payer est l'absence de cache — chaque accès mémoire est un « miss » au sens H&P. Quand un warrior exécute un code auto-modifiant (un processus réécrit les instructions d'un autre), c'est la violation ultime du modèle MESI : dans un système réel, le cache d'instructions du processus cible serait stale et l'invalidation devrait se propager. Dans Corewar, l'instruction modifiée est simplement lue telle quelle au prochain cycle — pas de cache d'instructions à invalider, pas de pénalité.

H&P §5.6 définissent la consistance séquentielle (SC) : le résultat de toute exécution doit être équivalent à celui obtenu si les accès mémoire de chaque processeur gardaient leur ordre programme et les accès entre processeurs étaient arbitrairement entrelacés. C'est le modèle le plus fort — et le plus coûteux à implémenter. H&P montrent qu'en SC, un processeur doit attendre que toutes les invalidations d'une écriture soient complètes avant de poursuivre, ce qui peut bloquer un cœur pendant 170 cycles sur un write miss. Corewar implémente SC trivialement par le round-robin déterministe : chaque processus exécute exactement une instruction à son tour, dans un ordre fixe et cyclique. Il n'y a pas de réordonnancement possible, pas de write buffer, pas de spéculation. SC est « gratuit » parce qu'il n'y a qu'un seul chemin d'exécution à chaque instant. C'est en réalité une propriété encore plus forte que la SC de Lamport : non seulement les résultats sont équivalents à un ordre séquentiel, mais l'ordre est séquentiel. Cette garantie est ce qui rend les guerriers prévisibles et permet le bombing pattern déterministe.

Le paradoxe de l'anniversaire (Ball, The Art of Coding, 1964 ; popularisé par Mosteller, Journal of the American Statistical Association, 1962, vol. 57, p.230) énonce que dans un groupe de 23 personnes, il y a plus de 50% de chances que deux partagent le même anniversaire. La formule pour n personnes et d jours : P(collision) ≈ 1 - e^(-n²/2d). Pour l'arène Corewar : avec d = 4096 cellules, la probabilité que deux instructions (choisies uniformément) tombent sur la même cellule dépasse 50% dès que n ≈ √(2 × 4096 × ln2) ≈ 75 instructions. Pour 4 guerriers de 20 instructions chacun (80 instructions totales), la probabilité de collision est déjà significative.

Ce paradoxe explique un phénomène sous-estimé en Corewar : les collisions accidentelles entre guerriers sont beaucoup plus probables que l'intuition ne le suggère. Deux bombers qui balayent l'arène avec des pas différents finiront par écrire sur les mêmes cellules par pur hasard statistique. Un guerrier qui pose du code en plusieurs endroits via SPL/fork a de bonnes chances de chevaucher le code d'un adversaire — pas par visée délibérée mais par le hasard des adresses relatives. La leçon du paradoxe de l'anniversaire est que dans un espace de 4096 cellules, la « sécurité par l'obscurité positionnelle » est une illusion : avec suffisamment de code dispersé, les collisions deviennent inévitables. L'espace de 4096 cellules est bien plus petit qu'il n'en a l'air — le paradoxe de l'anniversaire garantit que les chemins se croiseront toujours.

Dans un processeur pipeliné, le code auto-modifiant crée un hazard mémoire fondamental : l'étage Fetch lit des instructions que l'étage Memory pourrait être en train de modifier simultanément. CSAPP (§4.5.5, p.463) documente ce problème : « There can be interference between instructions writing data in the memory stage and the reading of instructions in the fetch stage, since the instruction and data memories reference a single address space. This can only happen with programs containing self-modifying code. Some systems have complex mechanisms to detect and avoid such hazards, while others simply mandate that programs should not use self-modifying code. »

Cette citation révèle la raison architecturale profonde pour laquelle Corewar utilise un modèle d'exécution mono-cycle. Le code auto-modifiant n'est pas un cas limite dans Corewar — c'est le mécanisme d'attaque principal. Les bombers écrivent des DAT (opcode 0x00 en 42) dans le code ennemi, les vampires y placent des JMP (zjmp en 42, si carry=1), les scanners modifient leurs propres instructions pour s'adapter. Si la VM était pipelinée, chaque écriture dans l'arène pourrait créer un hazard mémoire entre l'étage Fetch d'un processus et l'étage Memory d'un autre. Le modèle mono-cycle élimine cette classe entière de problèmes : l'écriture est complète avant que la prochaine instruction ne soit lue.

CSAPP documente aussi les conséquences du pipelining sur les hazards de données (p.460) : « A data hazard can arise for an instruction when one of its operands is updated by any of the three preceding instructions. » Le processeur doit alors insérer des bulles (NOP forcés, p.461-462) ou implémenter du forwarding (court-circuitage, p.464-466) — 5 sources vers 2 destinations. La VM Corewar n'a ni bulles ni forwarding : chaque instruction voit l'état exact de l'arène au moment de son exécution. Le CPI (Cycles Per Instruction) du processeur Y86-64 pipeliné de CSAPP est de 1.27 (p.495) — 27% de surcoût dû aux hazards — tandis que la VM Corewar atteint CPI = 1.0 systématiquement. Ce n'est pas un accident, c'est le choix de design qui rend le code auto-modifiant triviallement correct.

Le Dragon Book (Aho et al., Compilers, 2e éd., Ch.10, §10.5) décrit le software pipelining : chevaucher les itérations successives d'une boucle en créant un prolog, un noyau en régime permanent, et un epilog. L'intervalle d'initiation du noyau peut être plus petit que la latence d'une seule itération, atteignant un débit supérieur à 1/latence.

La boucle de bombing d'un guerrier (sti → add pas → zjmp retour) prend 3+ cycles par itération. Chez un guerrier mono-processus, ces cycles ne peuvent pas se chevaucher. Mais chez un guerrier multi-processus créé par fork, chaque processus exécute la même boucle mais décalé en phase — le processus 1 exécute sti pendant que le processus 2 exécute add, et le processus 3 exécute zjmp. C'est exactement le software pipelining par parallélisme de processus : l'instruction SPL crée le « prolog », et le régime permanent a N processus en vol, chacun à un étage différent du pipeline. SPL est l'équivalent Corewar du prolog du software pipelining — il remplit le « pipeline » d'opérations de bombing concurrentes, et chaque processus est un étage du pipeline logiciel.

Cormen et al. (Introduction to Algorithms, 3e éd., CLRS, Ch.11) et Cooper et Torczon (Engineering a Compiler, 2e éd., Ch.5) analysent les structures de données optimales pour chaque phase d'un compilateur. La résolution de symboles (labels en Corewar) est un cas d'école qui mérite une analyse de complexité précise.

L'assembleur Corewar effectue deux passes sur le code source. La première passe collecte les labels et leur position : on parcourt les instructions séquentiellement, chaque instruction ajoute sa taille au compteur de position, et chaque label est enregistré avec la position courante. Avec une table de hachage (CLRS Ch.11, temps moyen O(1) par insertion/recherche), la complexité totale de la première passe est O(n) où n est le nombre d'instructions. Avec un arbre binaire de recherche équilibré (CLRS Ch.12, O(log L) par opération où L est le nombre de labels), la complexité serait O(n · log L). Avec une liste chaînée (le code C original parcours linéairement la liste pour chaque recherche), la complexité grimpe à O(n · L) — potentiellement O(n²) dans le pire cas.

La deuxième passe génère le bytecode : on reparcourt les instructions, et pour chaque référence à un label, on consulte la table des labels pour obtenir sa position et calculer l'offset. Ici aussi, la structure de données est déterminante. Avec une table de hachage, chaque consultation est O(1), et la passe totale est O(n). Avec un arbre équilibré, O(n · log L). Avec une liste chaînée, O(n · L). Le choix de la structure de données est donc le facteur déterminant de la performance de l'assembleur. Cooper et Torczon (Ch.5) recommandent les tables de hachage pour les tables de symboles : « hash tables provide expected O(1) access time, making them the data structure of choice for symbol tables in most compilers. » L'implémentation Rust (HashMap) suit cette recommandation ; l'implémentation C (liste chaînée linéaire) ne la suit pas — et la différence est mesurable sur les fichiers .s avec beaucoup de labels. Le choix de la structure de données pour la table des labels détermine la complexité de l'assembleur : O(n) avec HashMap, O(n · log L) avec un B-tree, O(n · L) avec une liste chaînée — et c'est la différence entre un assembleur instantané et un assembleur qui ralentit avec la taille du code.

Kirk et Hwu (Programming Massively Parallel Processors, 4e éd., 2022, Ch.1-3) et Owens et al. (A Survey of General-Purpose Computation on Graphics Hardware, 2007, Computer Graphics Forum, vol. 26, p.80-113) décrivent l'architecture GPU : des milliers de cœurs simples organisés en warps (32 threads sur NVIDIA), exécutant en lockstep (même instruction, données différentes — SIMT). Le modèle de programmation CUDA organise les threads en grilles de blocs, chaque bloc partageant une mémoire rapide (shared memory). La performance GPU dépend de la régularité : tous les threads d'un warp doivent idéalement exécuter le même code (pas de divergence), et les accès mémoire doivent être coalescents (contigus).

Simuler l'arène Corewar sur GPU est un défi fascinant. L'approche naïve — un thread par processus — se heurte à la divergence de warp : dans un warp de 32 threads, chaque processus exécute une instruction différente, rendant le lockstep impossible. Les threads « divergents » sont masqués (un seul chemin est exécuté à la fois), dégradant la performance d'un facteur égal au nombre de chemins divergents. Pour un guerrier typique avec 3-4 types d'instructions dans sa boucle, la divergence est de 3-4× — un speedup GPU reste possible si le nombre de processus est suffisamment grand (des milliers) pour saturer le GPU malgré la divergence.

L'approche relaxée est plus prometteuse : au lieu de simuler le round-robin strict, on exécute tous les processus d'un cycle en parallèle sur le GPU, en relâchant l'ordre d'exécution. Le résultat est non déterministe au cycle près mais statistiquement similaire au round-robin sur de nombreuses parties. Cette relaxation est comparable au passage de la consistance séquentielle à un modèle relâché (TSO ou PSO) en architecture — les résultats diffèrent mais les statistiques convergent. Kirk et Hwu (Ch.5) décrivent les techniques de résolution de conflits (atomiques, réduction) qui permettent de gérer les écritures concurrentes dans l'arène. L'accélération GPU de Corewar est possible, mais elle exige de sacrifier le déterminisme cycle-par-cycle sur l'autel du parallélisme massif — un compromis entre reproductibilité et performance que la communauté Corewar n'a jamais accepté.

Van der Linden (Expert C Programming, p.169-171) raconte l'allégorie du « Paging Game » : « Each player gets several million 'things.' Things are kept in crates that hold 4096 things each. » Les « choses » sont des octets, les « caisses » sont des pages mémoire, et chaque page fait exactement 4096 octets sur la quasi-totalité des architectures modernes (x86, x86-64, ARM, RISC-V). L'arène Corewar fait 4096 octets — soit exactement une page. Ce n'est pas une coïncidence fortuite, c'est un choix de design délibéré : A. K. Dewdney, créateur de Corewar, a choisi 4096 car c'est la taille d'une page mémoire standard x86 (4 KB), garantissant que l'arène entière tient dans une seule page physique et ne sera jamais évincée du cache TLB. Contrairement à un programme qui accède à des données dispersées sur des centaines de pages (déclenchant des TLB misses coûteux), la VM Corewar balaie une zone mémoire parfaitement alignée sur une frontière de page — un avantage de performance silencieux mais réel.

Bryant & O'Hallaron (Computer Systems: A Programmer's Perspective, 3e éd., Ch.4, §4.1-4.3) présentent le Y86-64 : un ISA pédagogique simplifié du x86-64, conçu pour enseigner l'architecture processeur. Le Y86-64 a 15 registres (rax...r14 + rsp), un encodage variable (1-6 octets), 3 modes d'adressage (immédiat, registre, mémoire), et un jeu d'instructions réduit (halt, nop, cmovXX, opq, rrmovq, irmovq, rmmovq, mrmovq, call, ret, pushq, popq, jXX). Il supprime les instructions flottantes, les modes d'adressage complexes, et les préfixes x86.

Le ISA Corewar 42 est un jumeau spirituel du Y86-64 — mais encore plus minimaliste. Où le Y86-64 a 15 registres, Corewar en a 16. Où le Y86-64 a un encodage variable (1-6 octets), Corewar a aussi un encodage variable (1-5 octets via l'ACB). Où le Y86-64 supprime le flottant et les modes complexes, Corewar supprime aussi la pile, les appels, les interruptions, et le mode noyau. Les deux ISA partagent la même philosophie : réduire au minimum nécessaire pour enseigner les concepts fondamentaux. La différence est que le Y86-64 est conçu pour être implémenté par l'étudiant (pipeline SEQ puis PIPE), tandis que le Corewar ISA est conçu pour être programmé par l'étudiant (écriture de guerriers). Le Y86-64 enseigne comment construire un processeur ; le Corewar ISA enseigne comment programmer une machine minimale — les deux sont des ISA pédagogiques, mais l'un regarde vers le hardware, l'autre vers le software.

H&P §3.15 racontent l'histoire de la transition historique de 2000-2005 : l'industrie a réalisé que l'exploitation agressive de l'ILP était « simply too inefficient both from the viewpoint of silicon utilization and power efficiency ». Le Pentium 4 (20+ étages de pipeline, 7 unités fonctionnelles) a été abandonné. L'Itanium (approche VLIW logicielle) a échoué. L'industrie s'est tournée vers le multicœur et le TLP. Corewar a toujours fait ce choix : zéro ILP, TLP pur via fork. Chaque fork crée un thread indépendant avec son propre PC et ses propres registres — il n'y a aucune dépendance nominale entre threads (pas de registres partagés), seulement la mémoire partagée. Le T1 de Sun, qui a « abandoned the intense focus on ILP, returned to a simple pipeline strategy, and focused on exploiting TLP », est l'ancêtre spirituel de la VM. L'histoire de l'architecture des processeurs valide a posteriori le design de Corewar : quand même Intel a capitulé face aux limites de l'ILP, le modèle mono-émission multi-thread de Corewar n'était pas en retard sur son temps — il était en avance.

Patterson (Microprogramming, 1983, Scientific American) explique que les processeurs historiques utilisaient une mémoire de contrôle (microcode store) pour implémenter le jeu d'instructions : chaque instruction ISA était traduite en une séquence de micro-opérations élémentaires (transferts de registre, activation d'ALU, lecture/écriture mémoire). Le microcode est une couche d'indirection entre l'ISA visible par le programmeur et les signaux de contrôle du hardware. H&P (§A.9) notent que certains processeurs autorisaient même le writable microcode store, permettant de modifier le comportement des instructions en cours d'exécution.

La table de dispatch de la VM Corewar — le switch(opcode) qui traduit chaque opcode en actions C/Rust — est du microcode logiciel. Chaque case du switch est une micro-instruction qui décompose l'opcode de l’ISA 42 en opérations élémentaires : lire les opérandes, calculer l'adresse effective, exécuter l'opération ALU, écrire le résultat. La différence est que le microcode hardware s'exécute en quelques nanosecondes (accès à une ROM rapide), tandis que le dispatch logiciel s'exécute en dizaines de nanosecondes (indirection via la table de branchement du processeur hôte). La connexion avec le concept de computed goto (déjà traité dans ce guide) est directe : le computed goto est l'optimisation qui transforme le dispatch interprété en quelque chose qui ressemble au microcode natif — une table de saut directe sans le niveau d'indirection du switch. Le switch sur l'opcode EST le microcode — et l'optimiser, c'est rapprocher la VM du hardware.

L'ISA (Instruction Set Architecture) est l'abstraction centrale de l'architecture des ordinateurs. Elle définit trois choses : l'état du processeur (registres, PC, codes de condition, mémoire), le format des instructions (comment les octets sont organisés), et l'effet de chaque instruction sur l'état (sémantique). Le Y86-64, un ISA pédagogique présenté dans CSAPP (Chapitre 4), est un sous-ensemble simplifié de l'x86-64 — tout comme le Redcode de Corewar est un ISA simplifié pour le jeu.

Les parallèles sont frappants : le Y86-64 possède 15 registres, un PC, 3 codes de condition (ZF, SF, OF), un statut (AOK, HLT, ADR, INS), et un jeu d'instructions réduit (halt, nop, mov, OP, jump, call/ret, push/pop). Le Corewar possède 16 registres, un PC, un code de condition (carry), et 16 instructions. Les deux partagent un principe fondamental : les encodages d'instructions doivent avoir une interprétation unique. Toute séquence d'octets encode soit une séquence d'instructions unique, soit n'est pas une séquence légale. C'est ce qui permet au processeur de décoder le bytecode sans ambiguïté.

Hyde (The Art of Assembly Language, Ch.7.7.7, pp.442-445) décrit la table de saut : implémenter un switch/case en utilisant la valeur du case comme index dans un tableau d'adresses de code, puis sauter indirectement. C'est O(1) quel que soit le nombre de cases, contrairement à une chaîne de comparaisons if-else.

Le dispatch d'opcodes de la VM est exactement une table de saut — la valeur de l'opcode (0-15) indexe dans une table de 16 adresses de handlers. C'est le mécanisme de dispatch le plus efficace possible pour un espace d'opcodes fixe et dense, et c'est pourquoi les 16 opcodes consécutifs de Corewar sont idéaux pour le dispatch par table de saut. Si les opcodes étaient éparpillés (0, 17, 42, 255...), la table de saut nécessiterait soit un tableau immense avec des trous, soit une étape de traduction préalable. Les 16 opcodes consécutifs de Corewar créent la table de saut parfaite : compacte, dense, O(1) — le choix d'encodage optimal pour le dispatch.

Hennessy et Patterson (Computer Architecture: A Quantitative Approach, 6e éd., Ch.4, §4.1-4.3) décrivent les extensions SIMD (Single Instruction Multiple Data) des processeurs modernes : AVX2 (256 bits, 8 × i32 en parallèle) et AVX-512 (512 bits, 16 × i32 en parallèle) permettent d'exécuter la même opération sur plusieurs données simultanément. H&P montrent que la vectorisation automatique par le compilateur est la source de speedup la plus importante sur les workloads réguliers (image processing, algèbre linéaire), mais qu'elle est limitée par les dépendances de contrôle (les branchements conditionnels brisent le flux SIMD uniforme) et les dépendances de données (les lectures/écritures qui se chevauchent empêchent la réorganisation).

La VM Corewar est a priori hostile à la vectorisation SIMD : le déterminisme impose un ordre séquentiel strict sur l'exécution des processus, et chaque instruction peut modifier l'état global (l'arène) de manière imprévisible. Cependant, certaines opérations sont parallélisables si on isole leurs préconditions : (1) Vérification des lives : parcourir tous les processus pour vérifier live_count est un map SIMD — on peut charger 8 processus, comparer leurs live_count à 0 en une instruction AVX2, et générer le masque de survie. (2) Mise à zéro de scrb[] : le tableau de 4096 octets peut être effacé en 128 instructions AVX-512 (vmovdqa64) au lieu de 4096 écritures scalaires — un speedup de 32× sur cette opération. (3) Copie de champions : charger le bytecode d'un champion dans l'arène est un memcpy vectorisable. (4) Dump mémoire : la sortie de l'état de l'arène pour le débogage est un parcours séquentiel vectorisable.

La limite fondamentale est que le dispatch d'opcodes ne peut pas être vectorisé : chaque processus exécute une instruction différente, avec des opérandes différents, sur des données différentes — c'est la définition même de la divergence SIMD (« warp divergence » en terminologie GPU). Les architectures GPU résolvent ce problème par le lockstep execution (tous les threads d'un warp exécutent la même instruction) et le masquage (les threads qui ne prennent pas le branchement sont désactivés), mais cela détruirait le déterminisme cycle-par-cycle de MARS. La vectorisation SIMD en Corewar est donc possible uniquement pour les opérations en dehors de la boucle d'exécution principale — le cœur du simulateur reste séquentiel. La vectorisation accélère le ménage, pas la bataille — les opérations annexes bénéficient du SIMD, mais le dispatch d'opcodes est irréductiblement séquentiel.

Sagan (Space-Filling Curves, 1994, Springer) et Knuth (TAOCP, Vol. 4A, §7.1.3) étudient les courbes de remplissage d'espace : des fonctions continues qui « visitent » chaque point d'un espace de dimension n. Les exemples classiques sont la courbe de Hilbert (qui visite les points d'un plan en préservant la localité spatiale) et la courbe de Z-order (Morton order, utilisée dans les bases de données géospatiales). La propriété clé est que les points proches dans la courbe sont aussi proches dans l'espace — ce qui minimise les « sauts » et maximise la couverture locale.

Les patterns de bombing Corewar sont des courbes de remplissage d'espace 1D sur un anneau de 4096 cellules. Le Dwarf (pas de 5) est un échantillonnage uniforme — il visite les adresses 0, 5, 10, 15..., couvrant l'arène de manière régulière. Le Mortar (Fibonacci) est un échantillonnage quasi-aléatoire — les nombres de Fibonacci (1, 1, 2, 3, 5, 8, 13, 21...) forment une séquence à faible discrépance (low-discrepancy sequence), qui couvre l'espace plus uniformément que l'échantillonnage régulier quand la taille de l'arène n'est pas un multiple du pas. Knuth (TAOCP Vol. 2, §3.4.2) montre que les séquences à faible discrépance minimisent l'écart maximal entre points couverts et non couverts — exactement la métrique qui compte en Corewar : le temps maximum avant qu'une cellule ennemie ne soit touchée. Le bombing optimal est donc la courbe de remplissage qui minimise la discrépance sur un anneau de taille MEM_SIZE — un problème que la théorie des nombres étudie sous le nom de « distribution uniforme modulo 1 ». Le meilleur bomber est un nombre irrationnel bien choisi — et les nombres de Fibonacci approchent le nombre d'or, le plus irrationnel des irrationnels.

Jung et al. (RustBelt: Securing the Foundations of the Rust Programming Language, POPL 2018, Proc. ACM Program. Lang. 2, Article 66) formalisent le système de lifetimes de Rust et prouvent que le borrow checker garantit la sécurité mémoire (absence de use-after-free, double-free, data races) pour les programmes Rust « safe ». Le RustBelt framework montre que même les abstractions unsafe (comme Vec, Rc, Arc) sont sûres si elles respectent le contrat de leurs spécifications logiques. Le système de lifetimes est le mécanisme central : chaque référence a une lifetime qui contraint sa durée de validité, et le compilateur rejette tout programme où une référence pourrait survivre à la donnée qu'elle pointe.

L'implémentation Rust de la VM Corewar bénéficie directement des lifetimes. L'arène (Vec<u8>) est un propriétaire unique, et les références aux cellules de l'arène sont bornées par la lifetime de la VM — empêchant tout accès après la destruction de l'arène. Les processus (Vec<Process>) sont aussi un propriétaire unique, et les itérateurs sur la file de processus ont des lifetimes qui empêchent la modification de la file pendant l'itération (le problème classique du ConcurrentModificationException en Java). En C, ces garanties n'existent pas — un pointeur vers l'arène peut devenir dangling si l'arène est réallouée, et un pointeur vers un processus peut devenir invalide si la liste chaînée est modifiée pendant le parcours. Le borrow checker transforme ces bugs potentiels en erreurs de compilation. Les lifetimes ne sont pas une contrainte — c'est un système de preuve intégré au compilateur qui garantit que la VM Rust ne peut pas corrompre la mémoire, même dans les cas limites.

Wolfram (A New Kind of Science, 2002, Ch.1-3) établit que les automates cellulaires (CA) — grilles de cellules discrètes évoluant selon des règles locales — peuvent produire une complexité émergente étonnante à partir de règles triviales. Le Game of Life de Conway (1970) en est l'exemple canonique : 4 règles simples (naissance si 3 voisins, survie si 2-3 voisins, mort sinon) génèrent des structures auto-réplicantes, des oscillateurs et même des machines de Turing universelles. Wolfram (Ch.6, p.317-369) classe les CA en quatre classes : I (homogène), II (périodique), III (chaotique), et IV (complexe, au bord du chaos).

L'arène Corewar est un automate cellulaire de classe IV. Chaque cellule a un état (opcode + opérandes), les règles de transition sont les 16 instructions Redcode, et l'évolution est déterministe mais imprévisible à long terme — exactement comme le Game of Life. La circularité de l'arène est l'équivalent de la topologie toroïdale des CA classiques. Mitchell, Crutchfield et Hraber (Evolutionary Computation, 1993, vol. 4, p.493-523) ont étudié la computation émergente dans les CA : comment des règles locales simples peuvent résoudre des problèmes globaux (densité, parité). En Corewar, la computation émergente est le guerre elle-même — chaque cellule exécute localement, mais le pattern global (attaque, défense, réplication) émerge de l'interaction. Wolfram (Principle of Computational Equivalence, Ch.12) affirme que tout système au-dessus d'un seuil de complexité est computationnellement universel — Corewar confirme que 16 instructions et 4096 cellules suffisent amplement. L'arène est un automate cellulaire dont les règles sont les instructions d'un jeu de guerre — le Game of Life armé.

Wolfram (A New Kind of Science, 2002, Ch.1-3) étudie les automates cellulaires (CA) : des grilles de cellules où chaque cellule a un état fini et évolue selon une règle locale qui dépend de l'état de ses voisines. Le Game of Life de Conway (Gardner, Scientific American, 1970) est l'exemple canonique : un CA 2D où chaque cellule vit ou meurt selon le nombre de voisins vivants. Wolfram montre que même les CA 1D les plus simples (règle 110) sont Turing-complets.

L'arène Corewar est structurellement un automate cellulaire 1D à 256 états (chaque cellule est un octet) — avec des règles de transition non-locales et non-synchrones. Contrairement à un CA classique où toutes les cellules se mettent à jour simultanément (synchronous update), l'arène Corewar est mise à jour séquentiellement par les processus en round-robin. Ce modèle « asynchrone » est plus chaotique que le modèle synchrone : les résultats dépendent de l'ordre d'exécution, et une simple permutation de l'ordre des processus peut changer l'issue du combat. La connexion avec les CA est aussi conceptuelle : les guerriers Corewar sont des « patterns » dans le CA de l'arène, et le combat entre guerriers est la compétition entre patterns pour l'espace cellulaire — exactement comme les gliders du Game of Life se disputent l'espace 2D. L'arène est un automate cellulaire asynchrone où les patterns sont des guerriers, et la règle de transition est le code de l'adversaire.

Dans le match des opcodes en Rust, le compilateur insère des vérifications de bornes par défaut : si l'opcode est en dehors de 1-16, le bras _ => panique. Mais cette vérification empêche LLVM de générer une jump table parfaite (sans overhead de vérification).

Si l'on a déjà validé que l'opcode est entre 1 et 16 (ce que fait le décodeur en amont), utiliser std::hint::unreachable_unchecked() sur le bras _ => permet à LLVM d'éliminer la vérification de bornes et de générer une table de saut native. Le gain est de 5-10% sur la boucle principale, car chaque instruction économise une comparaison et un branchement conditionnel.

⚠️ Sécurité : unreachable_unchecked() est un unsafe — si l'opcode n'est effectivement pas dans les bornes, c'est un comportement indéfini (UB en Rust, comme en C). Ne l'utilisez que si vous avez une garantie absolue, par exemple après un if opcode >= 1 && opcode <= 16 vérifié plus tôt.

Crafting Interpreters explique pourquoi le bytecode est plus rapide que le tree-walk : les nœuds d'AST sont éparpillés dans le tas (heap), chaque pointeur pouvant causer un cache miss. Les CPUs modernes sont jusqu'à 100× plus rapides quand les données sont déjà dans le cache L1/L2. Le bytecode, en revanche, est une séquence linéaire dense qui épouse parfaitement le comportement de préchargement du cache : quand le CPU lit un octet, il charge tout le bloc voisin. L'arène Corewar bénéficie du même avantage — les 4096 octets forment un bloc contigu en mémoire, et le PC avance séquentiellement. Quand la VM exécute une instruction après l'autre, le cache CPU précharge naturellement les instructions suivantes. C'est pourquoi un simple tableau d'octets en C battra toujours un arbre d'objets en Java pour implémenter l'arène.

H&P ouvrent leur chapitre en déclarant : « At the core is a quantitative approach to computer design and analysis that uses empirical observations of programs, experimentation, and simulation as its tools. » Le §1.8 insiste : « the only consistent and reliable measure of performance is the execution time of real programs, and that all proposed alternatives to time as the metric or to real programs as the items measured have eventually led to misleading claims or even mistakes in computer design. » H&P documentent l'échec répété des benchmarks synthétiques (Dhrystone), des toy programs, et des kernels isolés — le benchmark matrix300 de SPEC89 passait 99% de son temps dans une seule ligne, et une optimisation du compilateur a multiplié la performance par 9 sans refléter la performance réelle. En Corewar, l'équivalent est clair : tester un guerrier contre un seul adversaire ou dans l'arène vide est aussi trompeur que Dhrystone. La win rate contre un pool diversifié d'adversaires est le seul métrique fiable — l'équivalent Corewar du benchmark suite SPEC. Et comme pour SPEC, la moyenne géométrique (pas arithmétique) est la bonne façon de résumer les performances.

Le CSAPP §6.4.5 oppose deux politiques d'écriture : le write-through (écriture immédiate vers le niveau inférieur) et le write-back (écriture différée jusqu'à l'éviction, via un dirty bit). Les caches modernes utilisent massivement le write-back. Pour Corewar, c'est crucial : quand un guerrier écrit dans l'arène (code auto-modifiant), la modification reste dans le L1 et n'est répercutée en DRAM que si la ligne est évictée — ce qui, comme on vient de le voir, n'arrive pratiquement jamais puisque l'arène tient entière en L1. Conséquence : l'auto-modification est « gratuite » en termes de bande passante mémoire. En round-robin mono-cœur, le guerrier B voit immédiatement les modifications du guerrier A car ils partagent le même L1. Mais sur un simulateur multi-cœurs, il faudrait des protocoles de cohérence cache (MESI) — un angle de complexité souvent sous-estimé dans les implémentations parallèles de Corewar.

Hyde (The Art of Assembly Language, Ch.7.7.6.4, pp.441-442) montre que sur les CPUs x86 modernes, les branchements sont coûteux (pipeline flush, pénalité de mauvaise prédiction). Calculer abs(eax) sans branchement via cdq/xor/add (4 instructions, 0 branchement) est plus rapide que test/jns/neg (3 instructions, 1 branchement) sur beaucoup de processeurs.

En Corewar, cette relation est inversée : les branchements coûtent exactement 1 cycle (pas de pipeline, pas de prédiction), et chaque instruction arithmétique coûte aussi 1 cycle. Le abs() branchless en 4 instructions est pire que la version branchée en 3 instructions (2 si le cas positif est fréquent). Corewar est l'anti-CPU-moderne où le branchement n'est jamais pénalisé. Cette inversion est une leçon de design : l'optimisation branchless est une réponse à un problème matériel spécifique (le pipeline profond) que Corewar n'a pas. Optimiser pour Corewar signifie penser en cycles, pas en branchements.

L'extension GCC des Computed Gotos est la technique utilisée par la VM de CPython (CEval) pour détruire l'overhead de la prédiction de branchement. Au lieu d'un switch(opcode) généré en cascade de comparaisons, les computed gotos utilisent une table de pointeurs de fonctions : goto *dispatch_table[opcode];. Chaque case se termine par goto *dispatch_table[next_opcode]; pour enchaîner directement sur l'instruction suivante sans repasser par le dispatcher.

Pourquoi c'est plus rapide ? Le switch traditionnel force le CPU à prédire un branchement indirect parmi 16 cibles possibles — le prédicteur de branchement rate souvent. Avec les computed gotos, le pattern de saut est mémorisé par le BTB (Branch Target Buffer), et GCC peut même insérer l'opcode suivant comme hint. Benchmark typique : 15-25% d'accélération sur la boucle principale de la VM.

En Rust, le match sur un enum est déjà optimisé en jump table par LLVM — les computed gotos sont donc un avantage spécifique au C. Mais en C, si vous ne les utilisez pas, votre switch sera probablement compilé en cascade de if (si les opcodes ne sont pas consécutifs) plutôt qu'en table de saut.

Hennessy et Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §5.2, p.382-385) décrivent le false sharing : deux variables indépendantes qui résident dans la même ligne de cache (64 octets sur x86-64) voient leurs accès interférer. Quand un cœur modifie l'une, toute la ligne de cache est invalidée pour les autres cœurs — même s'ils n'accèdent qu'à l'autre variable. H&P montrent que le false sharing peut dégrader les performances d'un facteur 2-10× sur les workloads multi-cœurs, et que la solution est le padding : aligner chaque variable sur une ligne de cache distincte avec alignas(64) en C ou #[repr(align(64))] en Rust.

Si l'on implémente la VM Corewar de manière parallèle (un thread par processus, ou un groupe de processus par thread), les structures Process et les tableaux owner[]/scrb[] sont vulnérables au false sharing. Deux processus adjacents dans le Vec<Process> partagent la même ligne de cache si leur taille combinée est inférieure à 64 octets (ce qui est le cas : 16 registres × 4 octets + PC + carry ≈ 72 octets — juste au-dessus). Chaque sti modifie l'arène, invalidant potentiellement la ligne de cache d'un autre thread qui lit la même zone. Les tableaux owner[] et scrb[] (un octet par cellule, 4096 octets au total = exactement 64 lignes de cache) sont un pire cas : chaque écriture dans owner[i] invalide la ligne contenant owner[i] pour tous les cœurs, même s'ils accèdent à des cellules adjacentes.

La solution est le padding stratégique : insérer 56 octets de padding après chaque Process pour que chaque processus réside sur sa propre ligne de cache, et découper owner[] en sous-tableaux par thread. Drepper (What Every Programmer Should Know About Memory, 2007, §3.3.4) confirme : « False sharing can only be avoided by separating the variables which can be accessed concurrently by different processors. » En Rust, #[repr(C, align(64))] sur la structure Process garantit l'alignement. Le false sharing est l'ennemi silencieux des VMs parallèles — un bug de performance invisible dans le code mais mesurable au profileur.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §3.3, Fig. 3.5) décrivent les prédicteurs tournament : plusieurs prédicteurs (local + global) et un sélecteur qui choisit le meilleur par branchement.

Un méta-guerrier qui commute entre stratégies est un prédicteur tournament dans le domaine Corewar. Il possède plusieurs « prédicteurs » (mode scanning, bombing, défensif) et un sélecteur qui choisit lequel activer. Le prédicteur tournament est le modèle architectural de la stratégie adaptative — des sous-guerriers spécialisés avec un sélecteur dynamique. La difficulté en Corewar est que le sélecteur lui-même consomme des cycles — le tournament a un coût que le guerrier doit absorber.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., §2.3, 8e optimisation) décrivent le préfetching matériel : le processeur charge la prochaine ligne de cache avant qu'elle ne soit demandée, réduisant la pénalité de miss. Le Pentium 4 a atteint 2× d'accélération sur SPEC.

Un scanner warrior « préfetch » en sondant des adresses en avant de la position courante. L'insight de H&P sur le préfetching inutile s'applique : scanner des cellules DAT (espace vide) gaspille des cycles. Un scanner efficace est un préfetcher qui ne « fetch » que les adresses susceptibles de contenir du code adverse — la qualité de la prédiction de localité distingue le bon scanner du mauvais.

Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., Ch.2, §2.7) et Chou & Berger (MLP is not ILP, 2003) distinguent le parallélisme au niveau instruction (ILP — exécuter plusieurs instructions simultanément) du parallélisme au niveau mémoire (MLP — avoir plusieurs défauts de cache en vol simultanément). Un processeur peut avoir un ILP faible mais un MLP élevé : les GPU atteignent MLP = des milliers avec des threads individuellement lents. Les MSHRs (Miss Status Holding Registers, Kroft 1981) permettent à un processeur out-of-order d'avoir plusieurs misses en vol, masquant la latence mémoire.

En Corewar, chaque processus a ILP = 1 (une instruction par cycle) et MLP = 1 (un accès mémoire par cycle). Il n'y a pas de MSHRs, pas de miss en vol, pas de prefetching matériel. Mais un guerrier multi-processus via fork atteint un MLP = N au niveau du guerrier : N processus lisant N zones différentes de l'arène, chacun avec son propre PC. C'est exactement le modèle GPU — des milliers de threads lents mais un MLP massif. Un guerrier avec 8 processus scanne 8 positions indépendantes par tour, découvrant l'adversaire 8× plus vite qu'un guerrier mono-processus. En Corewar, fork/lfork est le seul chemin vers le MLP — chaque fork ajoute un « thread GPU » à l'armée du guerrier.

Cooper & Torczon (Engineering a Compiler, 2e éd., Ch.7, §7.2.2) décrivent les règles d'alignement comme une contrainte fondamentale du stockage en mémoire : « a typical set of constraints might specify that 32-bit integers and 32-bit floating-point numbers begin on word (32-bit) boundaries, that 64-bit integer and floating-point data begin on doubleword (64-bit) boundaries. » Le compilateur doit insérer du padding entre les variables pour respecter ces contraintes, et pour minimiser le gaspillage, il doit ordonner les variables de la plus restrictive à la moins restrictive.

L'arène Corewar a un alignement uniforme : chaque instruction occupe un nombre fixe d'octets (1 octet pour l'opcode, 1 octet pour l'OCP, puis les paramètres). Il n'y a pas de padding entre instructions car toutes ont la même granularité d'alignement. Cette uniformité est un luxe que les vrais ISA n'ont pas — Cooper & Torczon décrivent comment les ISA réels imposent des tailles d'instruction variables et des contraintes d'alignement qui compliquent le décodage. En Corewar, l'absence de padding est une simplification délibérée : chaque instruction commence juste après la précédente, sans trou.

Cependant, Cooper & Torczon (§7.2.2) soulèvent un point subtil sur les offsets relatifs et la performance cache : « If two values are used in proximity in the code, the compiler would like to ensure that they can reside in the cache at the same time. This can be accomplished in two ways: sharing a single cache block, or ensuring that the two variables map to different cache lines. » En Corewar, cette observation s'applique au placement du code du guerrier : les instructions fréquemment exécutées ensemble (la boucle de bombardement) devraient être contiguës en mémoire pour maximiser la localité spatiale dans le cache de l'hôte qui exécute la VM. Un guerrier dont le boot est éloigné de sa boucle principale crée des « cache misses » dans l'implémentation de la VM, ralentissant l'interprétation. L'alignement de Corewar est simple, mais le placement des blocs de code est aussi critique que l'alignement des variables dans un compilateur.

Le CSAPP §6.1.1 détaille : SRAM (6 transistors/bit, ~4 cycles d'accès, coûte 1000× plus cher) vs DRAM (1 transistor/bit, ~200 cycles, needs refresh). Le tableau Figure 6.2 cristallise la différence. Pour Corewar, la « mémoire » de l'arène n'est ni de la SRAM ni de la DRAM — c'est une abstraction logicielle. Mais l'implémentation du simulateur détermine dans quel niveau de la hiérarchie elle réside réellement. Un tableau uint8_t arena[4096] en C sera alloué sur le tas (DRAM) mais migrera vers le L1 (SRAM) après les premiers accès grâce au caching matériel. L'insight : le simulateur Corewar bénéficie gratuitement de 3 niveaux de la hiérarchie — la RAM pour le stockage permanent, le L1 pour l'exécution rapide, les registres pour les variables locales du simulateur. Les données CSAPP (Figure 6.15) montrent que le coût du SRAM est 100× celui du DRAM par MB — Corewar obtient les performances du SRAM au prix du DRAM, exactement comme la hiérarchie mémoire est conçue pour le permettre.

Le CSAPP présente l'exemple frappant de sumarrayrows vs sumarraycols (§6.5) : deux fonctions calculant la même somme, mais l'une parcourt en row-major (stride-1) et l'autre en column-major (stride-N). Résultat mesuré : 25× de différence de temps d'exécution. L'analyse cache explique pourquoi : la version stride-N a un miss rate quasi-100 % (chaque accès tombe dans une ligne de cache différente), tandis que la version stride-1 a 25 % (1 miss par bloc de 4 mots). Pour Corewar, l'analogie est directe : un guerrier qui exécute ses instructions séquentiellement (PC += taille_instruction) bénéficie du stride-1, tandis qu'un guerrier qui saute de 128 en 128 octets (stride élevé) gaspille la majorité de chaque ligne de cache de 64 B. La leçon quantitative du CSAPP : le miss rate est un meilleur prédicteur de performance que le nombre total d'accès mémoire (§6.6.2, Figure 6.45) — un guerrier avec peu d'accès mais un miss rate élevé peut être plus lent qu'un guerrier avec plus d'accès mais un miss rate faible.

Le §5.6 (mis à jour pour RISC-V dans la 6e édition) classe cinq modèles de consistance mémoire du plus strict au plus relâché : consistance séquentielle (SC) → TSO/processor consistency (relaxe W→R) → PSO (relaxe W→R et W→W) → weak ordering (relaxe tout) → release consistency (RISC-V, ARMv8, C/C++ — ne préserve que l'ordre autour des opérations de synchronisation). H&P donnent l'exemple frappant de deux processeurs P1 et P2 : P1 écrit A=1 puis lit B, P2 écrit B=1 puis lit A. En SC, il est impossible que les deux lectures voient 0. En modèle relâché, c'est possible car les écritures peuvent être retardées. MARS implémente SC « pour free » car il n'y a pas de réordonnancement possible — chaque instruction s'exécute complètement avant la suivante. C'est un luxe que les vrais multiprocesseurs paient cher, mais que Corewar obtient gratuitement par sa simplicité. Le modèle le plus coûteux en hardware est le modèle par défaut en interprétation séquentielle.

Le CSAPP §6.2 distingue rigoureusement la localité temporelle (revisiter les mêmes adresses) de la localité spatiale (accéder à des adresses proches). §6.2.3 résume : « Les programmes qui référencent répétitivement les mêmes variables bénéficient d'une bonne localité temporelle. Les patterns stride-1 ont la meilleure localité spatiale. » Dans Corewar, les guerriers se divisent en deux archétypes : les boucleurs (forte localité temporelle — le PC revisite les mêmes instructions, le working set est minuscule) et les scanners (forte localité spatiale — le PC avance séquentiellement à travers l'arène, stride-1). Le CSAPP montre que la localité temporelle est plus précieuse car elle maintient les données dans les niveaux les plus rapides de la hiérarchie. Pour Corewar, cela signifie qu'un guerrier-boucle tire davantage du cache L1 qu'un guerrier-scan — non pas en misses (les deux tiennent en L1), mais en prédiction de branchement et prefetching matériel : le processeur détecte et précharge les patterns stride-1 (CSAPP note le « flat ridge line » du Core i7 pour stride=1, Figure 6.41), mais les boucles serrées bénéficient aussi de la prédiction de branchement parfaite.

Le CSAPP introduit la memory mountain (Figure 6.41) : un graphique 3D du débit de lecture en fonction de la taille du working set (localité temporelle) et du stride (localité spatiale). Le pic L1 atteint 14 GB/s, la vallée DRAM tombe à 900 MB/s — un facteur 15×. Appliqué aux patterns d'exécution des guerriers : un guerrier en boucle serrée (imp, bomber à petit pas) a un working set minuscule et un stride-1 — il vit sur la crête L1 à débit maximal. Un guerrier qui scanne toute l'arène avec des sauts aléatoires a un working set de 4 KB (encore < 32 KB) mais un stride élevé — il descend la pente de localité spatiale. L'insight surprenant : puisque l'arène tient en L1, même les scanners aléatoires restent dans la région L1 (4 KB < 32 KB) — la pénalité n'est pas des miss DRAM mais des miss L1→L2 occasionnels si le scanner crée des conflits de sets. La montagne mémoire de Corewar est essentiellement plate au sommet, ce qui rend les guerriers moins sensibles aux patterns d'accès que dans des programmes réels.

Le §3.13 (6e édition) démontre une fallacie frappante : « It is easy to predict the performance and energy efficiency of two different versions of the same instruction set architecture, if we hold the technology constant ». L'Intel Core i7 920 et l'Atom 230, tous deux en 45 nm et exécutant x86, présentent des performances 4× à 10× différentes — le i7 est au moins 4 fois plus rapide, et jusqu'à 10× sur certains benchmarks FP. Pourtant, l'Atom consomme seulement 4.2 W contre 43 W pour le i7, et son efficacité énergétique est 1.5× à 2× meilleure ! Le ratio de fréquence d'horloge n'est que de 1.6×, donc la différence vient principalement du CPI : facteur 2.8× à 4.3× selon les workloads. La leçon pour Corewar : deux guerriers avec le même « ISA » (même ensemble d'opcodes) peuvent avoir des performances radicalement différentes selon leur microarchitecture interne — la structure du code (boucle serrée vs. code dispersé, processus multiples vs. processus unique) est le véritable déterminant, pas le vocabulaire d'instructions.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.96, §2.1.7, Fig.2-6) formalise l'utilisation du CPU en fonction du degré de multiprogrammation : « Suppose that a process spends a fraction p of its time waiting for I/O to complete. With n processes in memory at once, the probability that all n processes are waiting for I/O (in which case the CPU will be idle) is p^n. The CPU utilization is then given by the formula: CPU utilization = 1 − p^n. » Avec p = 0.8 (80% du temps en attente I/O), un seul processus donne 20% d'utilisation, mais 4 processus montent à 1 − 0.8⁴ = 59%, et 12 processus atteignent 93%.

En Corewar, il n'y a pas d'I/O — les processus ne sont jamais en attente de disque ou de terminal. Donc p ≈ 0, et l'utilisation CPU = 1 − 0ⁿ = 100% quel que soit n. Cette formule confirme que MARS est un système purement CPU-bound. Mais la formule s'inverse de façon fascinante si l'on définit p comme la probabilité qu'une instruction donnée soit improductive (exécuter un DAT, reproduire un code déjà bombardé, scanner une zone vide). Avec cette définition, l'utilisation utile du CPU devient 1 − pⁿ, où n est le nombre de processus productifs. La leçon est double : premièrement, un guerrier avec plus de processus a plus de chances d'avoir au moins un processus productif à chaque cycle (la « défense multiprogrammation ») ; deuxièmement, quand p → 1 (l'arène est majoritairement détruite), même un SPL massif ne sauve plus — 1 − 1ⁿ = 0 pour tout n. La multiprogrammation protège contre l'aléa, mais pas contre la destruction totale.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.10, §10.3.1, p.733) décrit le daemon cron de Linux : il se réveille périodiquement pour vérifier s'il y a du travail à faire, exécute les tâches planifiées à leur heure, puis se rendort. La granularité est d'une minute.

Le mécanisme CYCLE_TO_DIE de MARS est un « daemon cron inversé » : au lieu de réveiller des processus à des moments précis, il endort (tue) les processus qui ne se sont pas signalés via live dans l'intervalle. La différence est que cron est un scheduler d'activation (réveil), tandis que CYCLE_TO_DIE est un scheduler de désactivation (mort). Le rapprochement est fécond : tout comme cron a une granularité d'une minute, MARS a une granularité de CYCLE_TO_DIE cycles. Et tout comme les tâches cron doivent se terminer avant le prochain tick, les live doivent être émis avant le prochain check de CYCLE_TO_DIE. L'inversion est totale : cron dit « réveille-toi ou tu manqueras ton tour » ; CYCLE_TO_DIE dit « signale-toi ou tu mourras ». Corewar est un cron qui tue au lieu de réveiller — l'anti-ordonnanceur, le scheduler de la mort.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.4, §4.3.2, p.286-287) décrit l'i-node UNIX : une structure contenant toutes les métadonnées d'un fichier (propriété, permissions, horodatage, pointeurs de blocs disque) stockée séparément du nom du fichier. La superblock contient le magic number et les paramètres du système de fichiers. Cette séparation nom/métadonnées est un pilier de la conception UNIX.

Le header .cor est un « micro-i-node » : il contient les métadonnées du champion (magic number, nom, taille, commentaire) séparément du code lui-même. Mais là où l'i-node UNIX sépare complètement le nom du fichier (stocké dans le directory) de ses métadonnées, le .cor embarque le nom dans le header — une confusion des couches que Tanenbaum éviterait. La superblock analogy s'applique aussi : le magic number 0x00EA83F3 dans le .cor est l'équivalent exact du magic number dans la superblock UNIX — un contrat de reconnaissance entre le lecteur et le format. Sans ce magic, la VM ne peut pas distinguer un fichier .cor valide d'un fichier arbitraire, exactement comme fsck utilise la superblock pour identifier un système de fichiers valide. Le .cor est un système de fichiers à un seul fichier — le magic number est la superblock, le header est l'i-node, le code est le contenu.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.4, §4.3.2, p.282-285) compare l'allocation contiguë (fichiers stockés comme blocs disque consécutifs — simple, lectures rapides, mais fragmentation) à l'allocation chaînée (blocs liés par des pointeurs — pas de fragmentation, mais accès aléatoire lent). Il note que l'allocation contiguë est encore utilisée sur les CD-ROM où la taille des fichiers est connue à l'avance.

Le chargement d'un champion .cor est une allocation contiguë pure — le code est placé séquentiellement dans l'arène à partir d'un point de départ, exactement comme un fichier sur CD-ROM. La taille est connue à l'avance (header), il n'y a pas de fragmentation possible au chargement, et la lecture est optimisée car le code est contigu. Cette simplicité est un avantage : un guerrier Corewar n'a jamais besoin de « chercher le bloc suivant » car tout son code est contigu — contrairement à un système de fichiers chaîné où chaque accès peut être un seek. C'est pourquoi le déplacement d'instructions (auto-modification par offset) est un O(1) en Corewar : l'adresse est toujours PC + offset, sans indirection. L'allocation contiguë du .cor élimine la fragmentation et l'indirection — le code est un bloc monolithique, comme un programme sur ROM.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.3, §3.6.6, p.239-240) décrit le external pager de Mach : le noyau gère la MMU et les page faults, mais un pager externe en espace utilisateur décide quelle page évicter. Cette séparation de la politique (quel page évicter) et du mécanisme (comment gérer les page faults) augmente la modularité au coût de traversées de frontières supplémentaires.

MARS fusionne politique et mécanisme pour la mémoire — il n'y a pas d'external pager car il n'y a pas de mémoire virtuelle. Mais la leçon de Mach est profonde pour l'implémentation d'une VM Corewar en Rust : on pourrait séparer le mécanisme d'exécution (le dispatch d'instructions) de la politique de gestion mémoire (quelle cellule « appartient » à qui, comment afficher les modifications). Un « external pager » pour l'arène serait un module qui décide, par exemple, quelles cellules sont mises en évidence pour le débogage ou la visualisation. L'architecture modulaire de Mach suggère que la VM Corewar devrait être structurée en couches : une couche mécanisme (exécution, accès mémoire, gestion des processus) et une couche politique (règles du jeu, affichage, vérification). Le design Mach recommande : séparez toujours le « comment » du « pourquoi » — même quand la séparation semble inutile, elle facilite l'évolution future.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.3, §3.4.7, p.214-215) décrit l'algorithme de vieillissement (aging) : un compteur par page est décalé d'un bit vers la droite à chaque tick, et le bit R (référence) est inséré à gauche. Cela produit une décroissance exponentielle : les références récentes pèsent plus que les anciennes.

La valeur tactique d'une cellule de l'arène décline exponentiellement avec le temps depuis son dernier accès. Une cellule que l'adversaire vient de lire/écrire a une valeur tactique maximale (high-value target) ; une cellule non accédée depuis 100 cycles a une valeur décroissante. Le vieillissement explique pourquoi le bombing incrémental (balayer l'arène séquentiellement à pas constant) est sous-optimal : il traite toutes les cellules avec la même priorité, ignorant que les cellules récemment accédées sont plus « chaudes ». Un scanner qui mémorise les adresses récemment modifiées peut implémenter un vieillissement logiciel et concentrer son bombing sur les zones les plus actives. Le vieillissement est la formalisation mathématique de l'intuition tactique : frapper là où l'adversaire vient de passer, pas là où il était il y a longtemps.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.7, §7.4.1, p.482) décrit le world switch dans un hyperviseur Type 2 : la transition entre la configuration hôte et la configuration invité. L'hyperviseur doit sauvegarder et restaurer tout le contexte processeur. La métaphore de Tanenbaum est fameuse : « des adolescents qui font la fête pendant que les parents sont absents, remettant tout exactement comme ils l'ont trouvé ».

Chaque changement de processus en Corewar est un micro-world-switch : sauvegarder PC/registres/carry du processus sortant, restaurer ceux du processus entrant. La métaphore est parfaite : « remettre les meubles exactement comme on les a trouvés ». Le round-robin garantit que ce world-switch se produit à chaque instruction. Mais contrairement à VMware où le world switch est coûteux (reconfiguration complète du processeur, TLB flush), le world switch de MARS est trivial : sauvegarder PC + 16 registres + carry + duration. C'est pourquoi le quantum de 1 instruction est viable en Corewar alors qu'il serait désastreux dans un OS réel : le coût du world switch est O(1), rendant la commutation par instruction non seulement possible mais essentiellement gratuite.

OSTEP (Ch.39-43) décrit les systèmes de fichiers comme fournissant du stockage persistant et nommé. Ils utilisent des inodes pour suivre les métadonnées et les localisations des blocs de données, et une superblock pour la structure globale du système de fichiers. Le système de fichiers est le mécanisme par lequel l'OS fait survivre les données entre les exécutions de processus.

Le format .cor est un système de fichiers dégénéré : un seul « inode » (le header avec nom et taille), un seul « bloc de données » contigu (les instructions du champion), pas de structure de répertoire, pas de gestion de blocs libres. Comprendre la pleine complexité des systèmes de fichiers réels met en relief à quel point le format .cor est minimal — et pourquoi cela fonctionne : un champion n'a besoin que d'un accès séquentiel à un seul « fichier » de taille fixe. Le .cor est le système de fichiers le plus simple possible : un inode, un bloc, pas de répertoire — la persistance minimale pour un programme qui ne vit qu'une partie.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.12, p.985-986) cite Antoine de Saint-Exupéry : « Perfection is reached not when there is no longer anything to add, but when there is no longer anything to take away. » Et ajoute : « This principle says that less is better than more, at least in the operating system itself. Another way to say this is the KISS principle: Keep It Simple, Stupid. »

Le design de Corewar incarne ce principe plus purement que tout système d'exploitation. L'arène est aussi simple que possible : un tableau plat de cellules, pas de pages, pas de segments, pas de protection. Le scheduler est le plus simple possible : round-robin, une instruction par processus par tour. Ce minimalisme n'est pas de la paresse — c'est un choix de design délibéré qui garde le jeu juste, compréhensible, et stratégiquement profond. Chaque élément qui aurait pu être ajouté (scheduling par priorité, protection mémoire, mémoire virtuelle, I/O) ne l'a pas été car il ajouterait de la complexité sans enrichir la profondeur stratégique. Corewar prouve que la richesse émerge de la simplicité — quelques instructions suffisent à engendrer une infinité de stratégies.

Tanenbaum énonce aussi sa Première Loi du Logiciel (Ch.12, p.992) : « Adding more code adds more bugs. Adding more features adds more code and thus adds more bugs. Programmers who believe adding new features does not add new bugs either are new to computers or believe the tooth fairy is out there watching over them. » En Corewar, cette loi opère avec des conséquences létales : chaque instruction supplémentaire dans un champion est une cellule vulnérable — un point d'attaque pour le bomber adverse. Plus votre champion est long, plus votre surface d'attaque est grande. Un champion compact (un survivant minimal, un scanner court) a moins de cellules qu'un sti adverse peut atteindre ; un champion étalé avec une logique complexe a de nombreux points de défaillance. En 42, la Première Loi devient : ajouter du code, c'est ajouter des cibles.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.1, p.3-6) identifie deux fonctions « essentially unrelated » de tout système d'exploitation : la Machine Étendue (vue top-down — abstraire le hardware laid en interfaces propres) et le Gestionnaire de Ressources (vue bottom-up — allouer ordonnancément processeur, mémoire et I/O). « Part of the problem is that operating systems perform two essentially unrelated functions: providing application programmers a clean abstract set of resources instead of the messy hardware ones and managing these hardware resources. »

MARS incarne les deux rôles simultanément, et cette dualité explique sa nature hybride de VM et d'OS. Comme Machine Étendue, MARS abstrait l'ISA hôte (x86, ARM) en un jeu d'instructions propre — le Redcode avec ses 16 opcodes, 5 modes d'adressage et son arène circulaire de 4096 cellules. Les pipelines, caches, interruptions et pagetables disparaissent entièrement derrière cette abstraction. Comme Gestionnaire de Ressources, MARS gère deux ressources : les cellules de l'arène (espace — allouées équitablement au chargement) et les cycles d'exécution (temps — alloués équitablement par round-robin). La tension entre ces deux rôles est palpable : la Machine Étendue voudrait offrir des abstractions riches (pages, segments, priorités), mais le Gestionnaire de Ressources impose le minimalisme (tableau plat, scheduler fixe). C'est cette tension qui donne à Corewar sa simplicité architecturale et sa profondeur stratégique — MARS est un OS complet dans ses deux fonctions, mais minimal dans chaque.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.1, p.2-3, §1.1) établit la distinction fondamentale entre mode noyau (kernel mode) et mode utilisateur (user mode) : « The rest of the software runs in user mode, in which only a subset of the machine instructions is available. In particular, those instructions that affect control of the machine or do I/O are forbidden to user-mode programs. » Le mode noyau donne accès à l'instruction set complet ; le mode utilisateur restreint les instructions sensibles — I/O, manipulation du MMU, accès aux registres de contrôle. Tanenbaum note aussi que cette distinction peut être brouillée : « This distinction, however, is sometimes blurred in embedded systems (which may not have kernel mode) or interpreted systems (such as Java-based systems that use interpretation, not hardware, to separate the components). »

MARS est précisément un de ces systèmes interprétés où la distinction mode noyau/utilisateur n'existe pas. Chaque guerrier exécute dans un niveau de privilège unique — il n'y a pas de ring 0, pas de ring 3, pas de porte d'appel système, pas de TRAP. Chaque instruction du Redcode est également disponible pour chaque processus. Cette absence de dual mode est ce qui rend le MOV-bombing possible : dans un OS réel, le MMU et les niveaux de privilège empêchent un processus d'écrire dans l'espace d'adressage d'un autre. En Corewar, toute l'arène est un seul niveau de privilège — le mode noyau universel. Le corollaire direct est l'absence d'appel système : il n'y a pas de TRAP, pas de syscall, pas de porte contrôlée vers des services privilégiés. L'instruction LIVE est le seul mécanisme qui ressemble à un appel système (le guerrier signale sa survie à la VM), mais ce n'est pas une transition de privilège — c'est simplement une déclaration dans le même mode d'exécution. L'arène est une machine sans anneaux de protection — chaque guerrier est root, ou plutôt, chaque guerrier est sur le seul niveau qui existe.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.7, p.477-478) distingue deux types d'hyperviseurs : « A type 1 hypervisor is illustrated in Fig.7-1(a). Technically, it is like an operating system... In contrast, a type 2 hypervisor, shown in Fig.7-1(b), is a different kind of animal... it is really just a user process running on top of a host operating system. »

MARS est, dans la taxonomie de Tanenbaum, un hyperviseur de Type 2. Il s'exécute comme un processus utilisateur sur un OS hôte (Linux, Windows), et il virtualise une machine — l'arène Corewar avec son jeu d'instructions, ses registres, et son scheduler. Les « OS invités » sont les guerriers eux-mêmes, qui croient avoir un accès exclusif à la mémoire et au CPU de l'arène. Comme VMware Workstation, MARS dépend de l'OS hôte pour les I/O (afficher l'arène, lire les fichiers guerriers) et gère directement les ressources virtualisées (mémoire de l'arène, exécution des instructions, ordonnancement des processus). Cette classification clarifie pourquoi MARS peut exister comme un programme simple plutôt que de nécessiter un accès bare-metal : il ne virtualise qu'une machine trivialement simple. Et comme le note Tanenbaum (p.478-479) à propos du trap-and-emulate, when the guest operating system executes a sensitive instruction, a trap to the hypervisor does occur MARS implémente la forme extrême du trap-and-emulate : 100% des instructions sont émulées, aucune ne s'exécute nativement — car le Redcode n'est pas le jeu d'instructions de l'hôte. C'est pourquoi MARS est plus lent que du code natif, mais aussi parfaitement sûr : il n'existe aucune instruction « sensible » qui pourrait s'échapper de la machine virtuelle.

Cependant, il convient d'apporter une nuance académique essentielle. Si, d'un point de vue systémique, MARS agit comme un Hyperviseur de Type 2 (processus utilisateur virtualisant une machine pour des invités), techniquement, il opère par pure émulation logicielle (ISA Interpreter) et non par virtualisation matérielle. Smith et Nair (Virtual Machines, Ch.1) font une distinction très stricte entre ISA Emulation (simuler un jeu d'instructions par logiciel, comme QEMU ou Bochs) et Virtualization (exécuter la majorité des instructions nativement sur le processeur physique via VT-x/AMD-V). Un véritable hyperviseur (Type 1 ou 2) fait exécuter au CPU hôte les instructions non-sensibles de l'invité directement en mode natif — seul le petit sous-ensemble d'instructions sensibles est intercepté. MARS, lui, interprète chaque instruction via son dispatch loop en C/Rust : zéro exécution native. Au sens strict de Smith et Nair, MARS est un émulateur ISA complet (comme QEMU en mode TCG, sans KVM), pas un hyperviseur. La classification « Hyperviseur de Type 2 » reste conceptuellement éclairante pour comprendre le rôle de MARS (un processus hôte gérant des invités), mais la précision technique impose de dire : MARS est un émulateur ISA qui se comporte, du point de vue de l'invité, comme un hyperviseur de Type 2.

James E. Smith et Ravi Nair, dans Virtual Machines: Versatile Platforms for Systems and Processes, distinguent deux grands types de machines virtuelles : les system VMs, qui virtualisent une machine complète incluant le système d'exploitation, et les process VMs, qui supportent un processus individuel. Ils définissent une process VM comme suit : « A process virtual machine is capable of supporting an individual process. [...] In process VMs, the virtualizing software is placed at the ABI interface, on top of the OS/hardware combination. The virtualizing software emulates both user-level instructions and operating system calls. » (p.10-11)

La VM Corewar est un cas paradigmatique de process VM. Chaque champion est un processus invité (guest) supporté par le runtime (la VM elle-même). Le runtime émule les instructions utilisateur (les 16 opcodes), gère la mémoire (l'arène circulaire), et ordonnance les processus. Smith et Nair soulignent un parallèle fondamental : « Most operating systems can simultaneously support multiple user processes through multiprogramming, where each user process is given the illusion of having a complete machine to itself. The operating system time-shares the hardware and manages underlying resources to make this possible. » (p.13) La VM Corewar fait exactement cela — elle donne à chaque champion l'illusion de posséder un processeur complet, alors qu'elle entrelace l'exécution de tous les processus par ordonnancement round-robin.

Le concept de virtualisation comme isomorphisme (Smith & Nair, p.10) est aussi éclairant : la virtualisation consiste en deux opérations — (1) le mappage des ressources virtuelles (registres, mémoire, PC) vers les ressources réelles du processus hôte, et (2) l'émulation des instructions de la machine virtuelle par des instructions de la machine hôte. Dans Corewar, le mappage est direct : les 16 registres du champion sont des champs dans une structure C/Rust, le PC est un entier, et l'arène est un tableau d'octets en mémoire hôte. L'émulation est le loop principal de la VM — le fameux fetch-decode-execute.

Smith et Nair (Virtual Machines, p.383-389) présentent le théorème de Popek et Goldberg (1974), qui énonce les conditions formelles sous lesquelles une architecture peut être virtualisée : « For any conventional third-generation computer, a virtual machine monitor may be constructed if the set of sensitive instructions for that computer is a subset of the set of privileged instructions. » Selon Popek et Goldberg, un véritable moniteur de machine virtuelle doit satisfaire trois propriétés :

• Efficacité : toutes les instructions inoffensives doivent s'exécuter nativement sur le matériel, sans intervention du VMM.
• Contrôle des ressources : un programme invité ne peut pas directement modifier la configuration des ressources système.
• Équivalence : tout programme s'exécutant sur la machine virtuelle doit se comporter de manière identique à son exécution sur le matériel natif.

La VM Corewar satisfait les trois : efficacité (les instructions simples s'exécutent directement via interprétation), contrôle des ressources (aucun champion ne peut accéder à l'état interne de la VM ou aux registres d'autres processus), et équivalence (un champion produit les mêmes résultats quel que soit le nombre d'autres champions dans l'arène). L'ISA de Corewar (les 16 opcodes) est par construction « efficacement virtualisable » : toutes les opérations sensibles (accès mémoire, création de processus via fork) passent par la VM. C'est un design radicalement différent de l'x86-64 original, qui n'était PAS virtualisable selon Popek-Goldberg — ce qui a nécessité l'invention de la paravirtualisation (Xen) et du matériel VT-x par Intel.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.7, p.475-476, §7.2) complète cette analyse avec les trois dimensions d'évaluation d'un hyperviseur : sécurité (le VMM doit avoir le contrôle total des ressources virtualisées), fidelité (le comportement sur VM doit être identique au bare metal), et efficacité (la majorité du code invité doit s'exécuter sans intervention). Le critère Popek-Goldberg est précisément : les instructions sensibles (qui affectent le comportement du système) doivent être un sous-ensemble des instructions privilégiées (qui trappent en mode utilisateur). L'x86 original violait ce critère avec 17 instructions sensibles non privilégiées (comme POPF qui modifie le flag d'interruption en mode utilisateur sans trap) — rendant la virtualisation « par logiciel pur » impossible. Corewar évite ce piège par construction : toutes les instructions sont sensibles ET toutes trappent (car elles sont interprétées). MARS atteint la fidelité parfaite (l'interprétation garantit l'équivalence) et l'efficacité raisonnable (un dispatch par instruction), mais sacrifie la sécurité — car la « sensibilité » des instructions Redcode (MOV peut écrire n'importe où) n'est pas contrôlée. MARS est le VMM parfait en fidélité et efficacité, mais délibérément imparfait en sécurité — car la sécurité détruirait le jeu.

Silberschatz (Operating System Concepts, 10e éd., Ch.1, §1.2.2) identifie l'I/O comme l'un des trois sous-systèmes fondamentaux d'un OS, avec le CPU et la mémoire : « The operating system must control all I/O devices, issuing commands to the devices, catching interrupts, and handling errors. » Tanenbaum (Modern Operating Systems, 4e éd., Ch.5, §5.2) renchérit : « Input/output is one of the most important and complex aspects of computer systems. I/O devices vary wildly in their speed, interface, and control requirements. »

Corewar est un système sans I/O. Pas de clavier, pas d'écran, pas de disque, pas de réseau — zéro périphérique. Un guerrier ne peut pas lire un fichier, afficher un message, ou recevoir une entrée utilisateur. Le seul « output » est l'instruction live (signaler son existence à la VM), et le seul « input » est la lecture de l'arène (lire le code et les données des autres guerriers). Cette absence d'I/O est une simplification radicale : l'OS le plus simple de Tanenbaum (Ch.5, Fig.5-1) a déjà des pilotes de périphériques, des gestionnaires d'interruption, et des tampons d'I/O — MARS n'a rien de tout cela. La conséquence est que le scheduler MARS n'a jamais à gérer de processus bloqué en attente d'I/O — chaque processus est toujours prêt à s'exécuter. C'est pourquoi le round-robin pur suffit : il n'y a pas de décision à prendre sur « quel processus est prêt ? » car la réponse est toujours « tous ». En Corewar, l'absence d'I/O est la simplification ultime — pas de pilotes, pas d'interruptions, pas de buffers, pas de DMA. Juste la mémoire et le CPU.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.12, p.992) cite le slogan de Lampson (1984) : « Don't hide power. If the hardware has an extremely efficient way of doing something, it should be exposed to the programmers in a simple way and not buried inside some other abstraction. The purpose of abstractions is to hide undesirable properties, not hide desirable ones. »

Redcode incarne ce principe plus purement que tout ISA réel. MOV (st/sti en 42) copie des instructions entières — opcode + deux opérandes + deux modes d'adressage en un seul cycle. Cette puissance est exposée directement, pas enfouie derrière une abstraction « copie seulement les données ». L'adressage indirect (@ et <) donne le déréférencement de pointeur comme concept de première classe — pas besoin de séquences load-then-add-then-load. SPL (fork/lfork en 42) crée du parallélisme en une seule instruction — pas de bibliothèque de threads, pas d'appel système, pas de setup. La puissance de la concurrence est nue. Le contraste avec un design « hidden power » est frappant : imaginez si MOV ne copiait que le champ B par défaut (MOV.AB). La puissance de la copie complète serait enfouie, et les guerriers auraient besoin de contournements. Au lieu de cela, MOV utilise par défaut le comportement le plus puissant (.F copie tout), et les variantes moins puissantes sont explicitement sélectionnées. Redcode ne cache rien — chaque instruction révèle sa pleine puissance dès la première utilisation.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.1, p.73, §1.7.6 (partitioning) et Ch.12, p.995, §12.3.1 (end-to-end argument)) décrit l'exokernel, une architecture OS radicale : « Rather than cloning the actual machine, as is done with virtual machines, another strategy is partitioning it, in other words, giving each user a subset of the resources. » Et le principe end-to-end : « It argues for not having the operating system do anything that the user program can do itself. [...] All the operating system should do is securely allocate resources among the competing users. The Exokernel is an operating system built according to the end-to-end argument. »

MARS est un exokernel — ou plutôt, c'est ce qui arrive quand on prend l'idée de l'exokernel et qu'on retire la protection. L'exokernel d'Engler et Kaashoek (1995) partitionne les ressources entre les VM et vérifie que chaque VM n'utilise que les ressources qui lui sont allouées. MARS partitionne l'arène (placement équidistant des champions) mais ne vérifie rien — un guerrier peut écrire n'importe où. La philosophie exokernel est « expose, don't abstract » ; MARS va plus loin : « expose, don't abstract, don't protect ». Le principe end-to-end (« the OS should not do anything the user program can do itself ») est poussé à sa limite : MARS ne fait rien que le guerrier ne pourrait faire lui-même, à l'exception de l'ordonnancement (round-robin) et de la vérification de survie (LIVE). L'auto-réparation, la défense, le scanning, le bombing — tout est laissé au guerrier. MARS est un exokernel dark mirror : tout le minimalisme, aucune des sécurités.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.124) définit le spin lock : « Continuously testing a variable until some value appears is called busy waiting. It should usually be avoided, since it wastes CPU time. Only when there is a reasonable expectation that the wait will be short is busy waiting used. A lock that uses busy waiting is called a spin lock. »

En Corewar, SPL 0 est le générateur ultime de spin-locks. Quand un guerrier exécute SPL 0, il crée une copie du processus courant à la même adresse — les deux processus exécuteront le même SPL au cycle suivant, doublant encore. Chaque processus de spin-lock consomme un cycle à ne rien faire de productif (juste exister et se diviser), ce qui est littéralement du busy waiting en attente de la mort de l'adversaire. L'insight stratégique de Tanenbaum est crucial : les spin-locks ne sont justifiés que quand l'attente est courte. En Corewar, un guerrier qui SPL aveuglément gaspille des cycles qui pourraient servir au bombing ou au scanning. La stratégie optimale équilibre le travail productif (MOV-bombing, CMP-scanning) contre le SPL défensif (processus spin-lock servant de « leurres » pour absorber les attaques ennemies). Le SPL est une arme, pas une stratégie — utilisez-le avec parcimonie et intention.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.158-159, §2.4.2) analyse le compromis du quantum : « Switching from one process to another requires a certain amount of time for doing all the administration—saving and loading registers and memory maps, updating various tables and lists, flushing and reloading the memory cache, and so on. Suppose that this process switch or context switch takes 1 msec. Also suppose that the quantum is set at 4 msec. [...] Thus 20% of the CPU time will be thrown away on administrative overhead. [...] Setting the quantum too short causes too many process switches and lowers the CPU efficiency, but setting it too long may cause poor response to short interactive requests. »

En Corewar, le quantum est de exactement une instruction par processus par cycle — le quantum le plus court concevable. Tanenbaum met en garde contre cette configuration : le coût du changement de contexte (sauvegarde/restauration des registres, mise à jour de la file d'exécution) consomme une proportion significative du temps CPU si le quantum est trop petit. Mais MARS contourne ce problème par la simplicité radicale de son contexte : chaque processus ne possède qu'un PC, 16 registres, un carry et un compteur de cycles — le coût du context switch est O(1), quasi nul. Pas de cache à flusher (l'arène est le seul objet mémoire), pas de TLB à invalider (pas de mémoire virtuelle), pas de page table à mettre à jour. Le « coût administratif » que Tanenbaum redoute se réduit à avancer un pointeur dans la file de processus. Cependant, il existe un coût invisible : quand un guerrier SPL massivement (créant des centaines de processus), chaque processus ne reçoit que 1/N du CPU. Ce n'est pas un coût de context switch, mais une dilution du quantum utile — chaque processus attend N-1 cycles entre deux exécutions, et ce temps d'attente est du « CPU gaspillé » du point de vue de ce processus. La « taxe SPL » est le prix à payer pour le quantum extrême : plus de processus = plus de temps d'attente par processus = moins de travail utile par cycle alloué.

Smith et Nair (Virtual Machines, p.377-379) décrivent le modèle d'ordonnancement par minuteur : « the interval timer [...] after being loaded with a value by the operating system, counts down clock ticks and triggers an interrupt when the value it holds becomes zero. [...] the operating system uses the timer to keep control of the processor by ensuring that no user application can run for an indefinite length of time. » C'est exactement le modèle de CYCLE_TO_DIE dans Corewar : chaque processus dispose d'un quantum d'exécution, après quoi la VM reprend le contrôle. Le compte à rebours est cycle_to_die, et « l'interruption » est la vérification de la VM à chaque cycle.

Tanenbaum (Modern Operating Systems, Ch.2) formalise l'ordonnanceur Round-Robin qui sous-tend MARS : « Round Robin… The key parameter is the quantum size q. When a process is put into the running state a timer is set to q. If the timer goes off and the process is still running, the OS preempts the process… and it is placed at the rear of the ready list (a queue). » Dans Corewar, le quantum est de 1 cycle — le plus petit possible. Chaque processus reçoit exactement un cycle avant d'être replacé en fin de file. Si un guerrier de type Paper se réplique en créant 10 processus, chacun ne tournera qu'à 10 % de la vitesse globale. La maîtrise de cette file d'attente est une arme redoutable : des stratégies comme le Brainwash consistent à forcer l'adversaire à exécuter des SPL (fork/lfork en 42) inutiles, noyant sa file sous des processus zombies pour le paralyser complètement.

Smith et Nair soulignent aussi le compromis de granularité : « A fair scheme for allocating hardware resources to virtual machines is one in which the virtual machines get ownership of the resources in turn for roughly equal amounts of time. If the time allocated to each virtual machine is large, there is the possibility that the resources are not optimally utilized. On the other hand, if the time allocated is small, the overhead incurred in switching between the virtual machines begins to degrade performance. » Ce compromis existe aussi dans Corewar : un CYCLE_TO_DIE trop grand permet à un champion de dominer sans vérification, un trop petit ajoute un overhead excessif à chaque vérification de survie.

La taxonomie des sources de dégradation de performance dans les VMs (p.415-416) s'applique directement à Corewar : Setup = initialisation d'un processus (fork), Emulation = overhead de décodage et dispatch des instructions, Interrupt handling = vérification de cycle_to_die, State saving = commutation de contexte entre processus, Bookkeeping = comptage des live et suivi de NBR_LIVE, Time elongation = coût de l'adressage circulaire et de l'arithmétique modulo. Cette taxonomie est une checklist pour optimiser une implémentation de VM Corewar.

Arpaci-Dusseau (OSTEP, Ch.4) énonce un principe de design fondamental des systèmes d'exploitation : « Separate policy and mechanism. You can think of the mechanism as providing the answer to a how question about a system; for example, how does an operating system perform a context switch? The policy provides the answer to a which question; for example, which process should the operating system run right now? Separating the two allows one easily to change policies without having to rethink the mechanism. » Ce principe, issu du système Hydra (Levin et al., SOSP 1975), est omniprésent dans les OS modernes : le mécanisme de context switch est indépendant de la politique de scheduling, le mécanisme de pagination est indépendant de la politique de remplacement, etc.

MARS (Memory Array Redcode Simulator) illustre le cas extrême où mécanisme et politique sont fusionnés. Le mécanisme d'exécution (round-robin strict, une instruction par processus) est aussi la politique — il n'y a pas de séparation possible. Un guerrier ne peut pas déclarer sa priorité, demander un quantum plus grand, ou influencer l'ordonnanceur. Cette fusion est intentionnelle : elle garantit que le comportement de la VM est complètement déterministe et reproductible, une exigence absolue pour un jeu compétitif. Mais elle vient avec un coût — là où un OS peut ajuster sa politique de scheduling selon la charge (SJF pour le batch, RR pour l'interactif, MLFQ pour mélanger les deux), MARS applique le même RR à tous les processus, qu'ils soient des bombers CPU-intensifs ou des scanners interactifs. En Corewar, la politique est le mécanisme — et cette rigidité est une feature, pas un bug.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.94-95) décrit la process table (ou Process Control Block) comme le cœur du système : « To implement the process model, the operating system maintains a table (an array of structures), called the process table, with one entry per process. This entry contains important information about the process' state, including its program counter, stack pointer, memory allocation, the status of its open files, its accounting and scheduling information, and everything else about the process that must be saved when the process is switched from running to ready or blocked state so that it can be restarted later as if it had never been stopped. »

C'est littéralement la structure de données de la file de processus MARS. Chaque entrée dans la file MARS contient : le Program Counter (adresse de la prochaine instruction Redcode), l'état du processus (vivant/mort), le propriétaire (quel champion a créé ce processus via SPL), les 16 registres, le carry flag, et le compteur de cycles (duration). La leçon de design de Tanenbaum est que la process table entry EST le processus — le code du champion dans l'arène n'est que des données inanimées ; c'est le PCB qui lui donne vie. Un champion dont tous les PCB sont détruits (tous les processus tués) est mort, même si son code est intact dans l'arène. Inversement, un champion dont les PCB sont intacts mais dont le code a été bombardé meurt dès que ses processus tentent d'exécuter les instructions écrasées. Cette dualité PCB/code est fondamentale : en Corewar, on peut tuer un adversaire soit en détruisant ses PCB (éliminer ses processus), soit en corrompant son code (écraser ses instructions avec des DAT).

OSTEP (Ch.4) définit trois états fondamentaux pour un processus : Running (en cours d'exécution sur le processeur), Ready (prêt à s'exécuter mais en attente de son tour), et Blocked (en attente d'un événement externe, typiquement une opération d'I/O). Le diagramme de transition est simple : un processus passe de Ready à Running quand il est scheduled, de Running à Ready quand il est descheduled, et de Running à Blocked quand il initie un I/O. L'état Blocked est crucial dans un OS car il permet au scheduler de donner le CPU à un autre processus pendant que l'I/O se complète, maximisant ainsi l'utilisation du processeur.

Dans Corewar, seuls deux états existent : Running (le processus dont c'est le tour) et Ready (tous les autres dans la file d'exécution). L'état Blocked n'existe pas — et pour cause : il n'y a pas d'I/O dans Corewar. Aucun processus ne demande une lecture disque, n'attend une entrée clavier, ni ne lance une opération réseau. Chaque instruction s'exécute en un nombre fixe de cycles, sans exception ni suspension. Cette absence de Blocked simplifie radicalement le scheduler : il n'a jamais à décider si un processus doit perdre le CPU pour cause d'attente I/O. Le round-robin pur suffit — chaque processus prend exactement une instruction, puis passe la main. Corewar est un OS sans I/O, et donc sans Blocked — la simplification maximale du modèle d'états.

L'absence d'état Blocked signifie aussi que l'ordonnancement de MARS est purement préemptif. Tanenbaum (Ch.2, p.152-153) distingue le scheduling non préemptif (cooperatif — un processus garde le CPU jusqu'à ce qu'il le rende volontairement ou se bloque sur un I/O) du préemptif (le scheduler reprend le CPU de force après le quantum). En Corewar, il n'y a aucune option coopérative : après exactement une instruction, le scheduler retire le CPU au processus courant et le donne au suivant. Un processus ne peut pas « rendre » le CPU (pas de yield()), ne peut pas le garder plus longtemps (pas de boucle occupée), et ne peut pas le bloquer (pas d'I/O). Même le SPL, qui crée un nouveau processus, ne « rend » pas le CPU — il le duplique. Le processus parent continue à la prochaine instruction, et le processus enfant attend son tour dans la file. C'est la préemption la plus stricte imaginable : un cycle, un processus, sans exception ni échappatoire.

Il existe cependant un état additionnel que OSTEP mentionne et qui est présent en Corewar : l'état Zombie. OSTEP le décrit comme un processus qui a terminé mais n'a pas encore été nettoyé par son parent via wait(). En Corewar, entre le moment où un processus rate son live et le moment où kill_zombies() l'élimine de la liste, il est fonctionnellement un zombie — encore présent dans la structure de données mais déjà condamné.

OSTEP (Ch.4, §4.3 « Context Switch") et Hennessy & Patterson (Computer Architecture: A Quantitative Approach, 6e éd., Appendix B) insistent sur un coût souvent sous-estimé du context switch : la perte de localité cache. Quand un OS passe du processus A au processus B, le cache L1 (données + instructions) est rempli des données de A. Le processus B subit alors une avalanche de cache misses jusqu'à ce que ses propres données y soient chargées — c'est le cache warm-up cost. Hennessy & Patterson estiment ce coût entre 100 et 10 000 cycles selon la taille du working set et le niveau de cache touché. OSTEP le résume ainsi : « The context switch cost is not trivial ; it requires saving and restoring registers, switching address spaces (which can be particularly expensive due to TLB flushes), and dealing with cache and TLB pollution. »

Le round-robin de MARS échappe presque entièrement à ce coût, et ce pour deux raisons architecturales. Premièrement, l'arène de MARS fait MEM_SIZE = 4096 octets (soit 4 KB) — c'est plus petit qu'une ligne de cache L2 typique (256 KB à 1 MB) et même plus petit que la moitié d'un cache L1 de données (32 KB). Résultat : l'intégralité de l'arène tient dans le cache L1 du processeur hôte. Il n'y a jamais de cache miss sur les accès mémoire à l'arène — chaque lecture/écriture d'une cellule est un hit L1 garanti. Le context switch MARS ne provoque aucun cache warm-up sur l'espace d'adressage principal du jeu.

Deuxièmement, la structure de données des processus elle-même détermine la localité. Une implémentation C classique utilise une liste chaînée (t_list*) où chaque processus est alloué séparément sur le tas — les PCB sont éparpillés en mémoire, provoquant des cache misses lors du parcours séquentiel de la file. Une implémentation Rust utilise un Vec<Process> — un tableau contigu où les PCB se suivent en mémoire. Ce choix a un impact direct mesurable : le parcours séquentiel d'un Vec bénéficie du préfetching matériel du CPU (les lignes de cache sont chargées en avance), tandis qu'une liste chaînée provoque des accès essentiellement aléatoires qui stallent le pipeline. Dans les benchmarks du projet, cette différence de localité cache se traduit par un avantage de 5 à 21× pour l'implémentation Rust sur les parties à fort nombre de processus.

La leçon est que le round-robin de MARS est structurellement immunisé contre le principal coût du context switch OS (la perte de localité sur l'espace d'adressage), mais que le coût résiduel dépend entièrement du choix d'implémentation de la file de processus. L'arène de 4 KB est le cache killer de Corewar — mais la structure de données des processus est le vrai goulot d'étranglement.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.97-99) distingue rigoureusement processus (espace d'adressage séparé) et threads (espace d'adressage partagé) : « In many situations, it is desirable to have multiple threads of control in the same address space running in quasi-parallel, as though they were (almost) separate processes (except for the shared address space). » Il note aussi que les threads sont créés 10 à 100 fois plus vite que les processus car ils n'ont pas à dupliquer l'espace d'adressage.

Les « processus » de Corewar sont des threads par la définition de Tanenbaum. Tous les processus créés par SPL (fork/lfork en 42) partagent la même arène — il n'y a aucune isolation d'espace d'adressage entre eux. Quand le processus #1 du champion A écrit à la cellule 500, le processus #2 voit immédiatement la modification. C'est exactement le modèle thread : espace d'adressage partagé, exécution concurrente, aucune protection mémoire entre frères. L'implication stratégique est double : les threads peuvent coopérer (un processus répare le code qu'un autre exécute, un processus scout prépare les cibles qu'un autre bombarde) mais aussi interférer (un processus écrase accidentellement les données de travail d'un autre). Il n'y a pas de frontières mmap, pas d'isolation fork()-style — juste la mémoire brute partagée. Le SPL crée des threads, pas des processus — et cette distinction est la clé des stratégies multi-processus coopératives.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.12, p.1009, §12.3.9) définit la réentrance : « Reentrancy refers to the ability of code to be executed two or more times simultaneously. On a multiprocessor, there is always the danger than while one CPU is executing some procedure, another CPU will start executing it as well, before the first one has finished. » Un code réentrant ne modifie ni son propre code ni des données globales — il peut être exécuté en toute sécurité par plusieurs threads simultanément.

Quand un guerrier SPL, le nouveau processus partage le même code que le parent. Plusieurs processus exécutent les mêmes instructions dans l'arène, intercalés par le round-robin. C'est précisément l'exécution réentrante. Mais en Corewar, le « code » est aussi la « donnée » — il n'y a pas d'espace d'instructions séparé. Quand un processus modifie une cellule (via MOV, ADD, etc.), il change le code que d'autres processus de la même zone exécuteront. Cela rend la réentrance dangereuse : un processus qui modifie son propre code pendant que d'autres l'exécutent crée l'équivalent d'une fonction non réentrante modifiant des données statiques. Le guerrier doit soit garantir que son code est pur (jamais auto-modifiant, véritablement réentrant), soit coordonner soigneusement l'auto-modification pour qu'aucun processus ne soit en train d'exécuter la cellule modifiée. Ce paradoxe — le code partagé qui se modifie lui-même — est unique à Corewar et n'a pas d'équivalent direct dans la théorie OS classique, où le code est en lecture seule et les données sont séparées. En Corewar, la réentrance est le luxe qu'aucun guerrier ne peut se permettre totalement — l'auto-modification est trop puissante pour y renoncer.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.90-91) classe les causes de terminaison des processus en quatre catégories. Les deux involontaires sont : (3) erreur fatale (instruction illégale, référence mémoire invalide) et (4) tué par un autre processus (UNIX kill, Win32 TerminateProcess).

Corewar implémente les deux modes de mort involontaire avec une élégance brutale : l'erreur fatale correspond à l'exécution d'un DAT (opcode 0x00 en 42) — le processus trébuche sur une cellule bombardée et meurt instantanément, comme un segfault. L'assassinat par un autre processus correspond au MOV-bombing — le bomber écrase le code adverse avec des DAT, empoisonnant la mémoire pour que la victime meure au prochain cycle. Mais la subtilité Corewar est que le bombing est toujours un assassinat indirect : le bomber ne tue pas le processus directement (il n'y a pas d'équivalent de kill -9), il empoisonne la mémoire et attend que la victime s'exécute elle-même sur le poison. C'est la différence entre un sniper (mort instantanée) et un empoisonneur (la victime se tue elle-même). Cette indirection explique pourquoi la vitesse relative des processus est cruciale : un processus rapide peut traverser la zone empoisonnée avant que le bomber n'ait fini de la miner, tandis qu'un processus lent marche inévitablement sur les DAT. En Corewar, on ne tue pas — on empoisonne et on attend. La victime meurt de ses propres pas.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.114-115) décrit les pop-up threads : « A completely different approach is also possible, in which the arrival of a message causes the system to create a new thread to handle the message. Such a thread is called a pop-up thread. [...] A key advantage of pop-up threads is that since they are brand new, they do not have any history—registers, stack, whatever—that must be restored. Each one starts out fresh and each one is identical to all the others. This makes it possible to create such a thread quickly. »

L'instruction SPL (fork/lfork en 42) de Corewar est le mécanisme de pop-up thread par excellence. Quand un guerrier exécute SPL label, un nouveau processus est créé à l'adresse label — il est neuf, sans historique (juste un PC frais), et commence immédiatement. Comme les pop-up threads, les processus créés par SPL sont légers : pas d'état de registres à sauvegarder au-delà de la copie du parent, pas de pile à monter, juste un compteur programme. La différence cruciale est que le « message » déclencheur n'est pas externe mais l'exécution de l'instruction SPL elle-même. L'implication stratégique reflète l'observation de Tanenbaum : les pop-up threads (processus SPL) peuvent être créés rapidement mais n'ont aucun contexte — ils démarrent de zéro. Un réplicateur Corewar doit donc garantir que chaque copie est autonome dès sa première instruction, sans dépendre d'un setup qui aurait pu s'exécuter avant le SPL. Chaque processus doit être une unité complète et auto-suffisante dès sa naissance.

OSTEP (Ch.13) énonce le Principe d'Isolation comme fondement de la construction de systèmes fiables : « Isolation is a key principle in building reliable systems. If two entities are properly isolated from one another, this implies that one can fail without affecting the other. Operating systems strive to isolate processes from each other and in this way prevent one from harming the other. By using memory isolation, the OS further ensures that running programs cannot affect the operation of the underlying OS. » Les trois buts de la mémoire virtuelle — transparence (le programme ne sait pas que sa mémoire est virtuelle), efficacité (la virtualisation ne ralentit pas significativement), et protection (un processus ne peut pas accéder à la mémoire d'un autre) — sont les piliers de tout système moderne.

Corewar viole délibérément ces trois buts. La transparence n'existe pas : chaque processus sait que l'arène est partagée et peut lire les instructions de ses adversaires. L'efficacité est triviale : il n'y a pas de traduction d'adresse, pas de TLB, pas de page table — l'arène est un tableau C brut. Et la protection est absolument absente : un processus peut écrire n'importe où dans l'arène, y compris sur le code d'un adversaire. Là où un OS investit des méga-octets de structures (page tables, TLBs, segmentation) pour garantir l'isolation, Corewar investit exactement zéro octet. Corewar est le système où l'isolation est l'anti-objectif — la destruction du code adverse est le but du jeu. Cette inversion n'est pas un accident mais une choice architecturale qui transforme chaque concept d'OS en son contraire : la protection devient vulnérabilité, l'isolation devient faiblesse, et la shared memory devient une arme.

Silberschatz (Operating System Concepts, 10e éd., Ch.6, §6.5) et Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.142-143) décrivent l'inversion de priorité : un processus à haute priorité est bloqué en attente d'une ressource détenue par un processus à basse priorité, qui ne peut pas s'exécuter car un processus à priorité moyenne monopolise le CPU. Le cas historique le plus célèbre est le Pathfinder Mars (1997) : le bus de données VxWorks était partagé entre une tâche de navigation (haute priorité) et une tâche météo (basse priorité), et l'inversion de priorité a causé des réinitialisations système répétées. La solution est le priority inheritance protocol (Sha, Rajkumar & Lehoczky, 1990, Real-Time Systems Symposium) : la priorité du processus bas est temporairement élevée au niveau de celle du processus haut qui attend.

MARS est immunisé contre l'inversion de priorité par construction — car il n'a pas de priorités. Le round-robin strict traite tous les processus équitablement, sans distinction de priorité. Un processus de bomber n'a pas plus de droit CPU qu'un processus de scanner ou de réplicateur. Cette absence de priorités élimine complètement le problème de l'inversion — mais elle élimine aussi la possibilité pour un guerrier de « privilégier » un processus critique. Si un guerrier a 10 processus et que l'un d'eux est vital (il maintient le live), ce processus ne reçoit que 1/10 du CPU, exactement comme les 9 autres. Le trade-off est clair : pas d'inversion de priorité, mais aussi pas de garantie de service pour les processus critiques. Le round-robin de MARS est l'antidote absolu à l'inversion de priorité — au prix de l'impossibilité de prioriser l'essentiel.

Silberschatz (Operating System Concepts, 10e éd., Ch.6, §6.4) et Tanenbaum (Modern Operating Systems, 4e éd., Ch.3, p.241-242) décrivent le mécanisme Copy-on-Write (COW) : après un fork() UNIX, le noyau ne copie pas les pages mémoire du parent vers l'enfant — il les marque en lecture seule et partage les mêmes frames physiques. Ce n'est que quand l'un des deux processus tente d'écrire qu'une copie est effectuée (page fault → duplication → rétablissement de l'écriture). COW rend le fork() virtuellement gratuit en mémoire : le coût réel est différé jusqu'à la première écriture.

Le fork/lfork de Corewar est un fork sans COW. Quand un processus fork, la VM copie immédiatement et intégralement l'état du parent : PC, 16 registres, carry — tout est dupliqué. Mais il y a une asymétrie cruciale : les registres et le carry sont copiés, mais l'arène n'est pas copiée — les deux processus partagent le même espace mémoire. C'est le meilleur des deux mondes : le fork est immédiat (pas de COW nécessaire car les registres sont petits), et la mémoire est partagée par définition (pas de page tables à dupliquer). En UNIX, le fork() avec COW coûte O(1) en mémoire mais peut déclencher des milliers de page faults lors de la première écriture ; en Corewar, le fork coûte O(1) en mémoire et zéro page fault car il n'y a pas de mémoire à copier — seulement 16 registres et un carry. Le fork Corewar est plus efficace que le fork UNIX avec COW — car il n'y a rien à copier-on-write quand tout est déjà partagé.

Hewitt, Bishop et Steiger (1973, IJCAI, p.235-241) ont proposé le modèle acteur : chaque acteur est une entité autonome avec un état privé, communiquant exclusivement par envoi asynchrone de messages. Agha (Actors: A Model of Concurrent Computation in Distributed Systems, 1986, MIT Press) formalise le modèle : un acteur reçoit un message, peut créer de nouveaux acteurs, envoyer des messages, et changer son état interne. La propriété fondamentale est l'encapsulation de l'état — un acteur ne peut pas modifier l'état d'un autre acteur directement.

Corewar est l'exact opposé du modèle acteur. Les processus (qui seraient les « acteurs ») n'ont pas d'état privé partagé — l'arène est entièrement publique. Il n'y a pas de messages : la communication se fait par effet de bord sur la mémoire partagée. Un processus ne peut pas « envoyer un message » à un autre — il écrit dans une cellule que l'autre lira peut-être. Cette absence de canal de communication structuré est à la fois la faiblesse (pas de protocole, pas de type, pas de garantie de livraison) et la force (pas de overhead de sérialisation, pas de file de messages, pas de deadlock de boîte aux lettres) du modèle Corewar. Le modèle acteur évite les data races par encapsulation ; Corewar les cherche par conception. Agha (Ch.3) montre que le modèle acteur est équivalent en puissance de calcul à n'importe quel autre modèle de concurrence — mais il est plus sûr car il élimine les courses critiques par construction. Corewar rejette la sécurité du modèle acteur pour la puissance brute de la mémoire partagée — et chaque data race est une opportunité stratégique.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.12, §12.3.3, p.998-999) définit l'orthogonalité : des concepts séparés qui se combinent indépendamment. Il cite clone() de Linux comme exemple d'orthogonalité supérieure à fork() : clone() permet le partage indépendant de l'espace d'adressage, des descripteurs de fichiers, du répertoire de travail et des signaux via un paramètre bitmap. fork() n'est que clone() avec tout copié.

SPL (fork/lfork en 42) est l'instruction la plus orthogonale de Corewar : elle crée un nouveau processus qui partage TOUT avec le parent (espace d'adressage, registres, carry) — sauf le PC. C'est un clone() où le seul paramètre modifié est le PC du fils. Contrairement à fork() qui est déjà moins orthogonal (copie tout), SPL partage tout — il n'y a pas de bitmap de partage car il n'y a qu'un seul choix : tout partager. L'orthogonalité extrême de SPL explique pourquoi le fork bombing est si efficace : chaque copie est un clone parfait, et la seule différenciation vient du PC différent. SPL est clone() avec un bitmap réduit à un seul bit — le bit du PC. C'est l'orthogonalité minimale : une seule dimension de variation.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.2, p.121) définit la condition de course : « Situations like this, where two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions. » Il consacre tout le Ch.2.3 à les prévenir — régions critiques, exclusion mutuelle, sémaphores, moniteurs.

Corewar prend le cauchemar du concepteur d'OS et en fait la mécanique de jeu fondamentale. Chaque écriture dans l'arène partagée est une race condition potentielle : deux bombers ciblant la même cellule — le dernier à écrire « gagne » ; un scanner lisant une cellule qu'un bomber s'apprête à écraser — le résultat du scan dépend de l'ordre exact ; un guerrier auto-réparateur en course contre le bomber adverse — chaque cycle compte. Le round-robin avec quantum=1 rend ces races déterministes (même entrée = même résultat) mais sensibles aux conditions initiales (1 cellule de décalage change toute la dynamique). C'est pourquoi Corewar est infiniment rejouable et pourquoi des différences stratégiques minuscules ont des effets massifs. Frappant : Corewar fournit zéro primitives de synchronisation — pas de mutex, pas de sémaphores, pas de moniteurs. Tout le Ch.2.3 de Tanenbaum est sur la prévention des races ; Corewar est sur leur exploitation. Là où l'OS élimine les race conditions, Corewar les élève au rang d'art stratégique.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.3, p.228) décrit le copy-on-write : « This approach, called copy on write, improves performance by reducing copying... All the data pages are mapped into both processes as READ ONLY. As soon as either process updates a memory word, the violation of the read-only protection causes a trap to the operating system. A copy is then made of the offending page so that each process now has its own private copy. »

L'instruction SPL de Redcode est l'équivalent Corewar du fork() UNIX, et elle implémente une forme de copy-on-write... mais sans la copie. Quand SPL s'exécute, il crée un nouveau processus avec son propre PC, mais le parent et l'enfant partagent le même espace de code — les mêmes cellules de l'arène. Aucun processus ne reçoit de copie privée du code. La « copie » arrive implicitement et paresseusement : quand un processus MOV des données dans une cellule partagée, l'autre processus voit la modification — il n'y a pas de protection copy-on-write. C'est du copy-on-write sans la copie : tous les processus voient toujours la dernière version de chaque cellule. Dans un OS conventionnel, ce serait un bug (violation de l'isolation des processus) ; en Corewar, c'est une feature — cela permet le code auto-modifiant et les stratégies multi-processus coopératives où un processus répare le code qu'un autre exécute. Là où l'OS copie pour protéger, Corewar partage pour permettre — l'anti-COW par conception.

Dijkstra (1965, Cooperating Sequential Processes, in Programming Languages, Academic Press) a inventé les sémaphores — la première primitive de synchronisation formelle pour la programmation concurrente : « It is assumed that the operations P and V are indivisible (i.e. non-interruptible) operations. » L'opération P(s) (proberen — tester) décrémente le sémaphore : si s > 0, le processus continue ; si s = 0, le processus est bloqué jusqu'à ce que s devienne > 0. L'opération V(s) (verhogen — incrémenter) incrémente le sémaphore et réveille un processus en attente. Dijkstra a conçu ces primitives précisément pour résoudre le type de problèmes de coordination que les processus Corewar affrontent : exclusion mutuelle, producteur-consommateur, lecteurs-rédacteurs.

Corewar n'a aucune primitive de synchronisation — ni sémaphore, ni mutex, ni barrier, ni condition variable. La seule communication entre processus est l'écriture dans l'arène (mémoire partagée sans protocole). Les conséquences sont profondes : deux processus du même guerrier ne peuvent pas se coordonner de manière fiable. Si le processus A écrit un drapeau en cellule 1000 pour signaler au processus B qu'il a terminé son initialisation, le processus B ne peut pas « attendre » ce drapeau — il doit le poller (vérifier périodiquement), gaspillant des cycles. Et même ce polling est vulnérable aux data races : si un guerrier adverse écrase la cellule 1000 entre l'écriture de A et la lecture de B, la coordination est corrompue. Dijkstra a inventé les sémaphores précisément pour éliminer ces busy-waiting et ces races — Corewar les réintroduit par conception. Les processus Corewar sont des « cooperating sequential processes » sans les outils de la coopération — chaque synchronisation est un acte de foi dans un monde hostile.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.1, p.58-60) expose le débat entre noyau monolithique (Linux) et micro-noyau (MINIX) : « The microkernel approach was the subject of much debate already in the 1990s, with proponents arguing it was the way of the future and opponents arguing that it was too slow. » Le micro-noyau ne fournit que les services minimaux : communication inter-processus (IPC), ordonnancement, et gestion de la mémoire. Tout le reste (pilotes, systèmes de fichiers, pile réseau) s'exécute en espace utilisateur comme des serveurs.

MARS est un micro-noyau pur dans la taxonomie de Tanenbaum. Ses seuls services : (1) ordonnancement (round-robin des processus), (2) gestion mémoire (allocation équidistante au chargement), et (3) IPC (l'arène elle-même — mémoire partagée sans abstraction). Il n'y a pas de pilotes, pas de système de fichiers, pas de pile réseau, pas de gestionnaire d'interruptions. La comparaison avec MINIX 3 (12 000 lignes de code, 6 appels système) est éclairante : MARS fait encore plus minimal avec 0 appels système (pas de syscall, juste LIVE comme déclaration passive). Le débat Tanenbaum-Torvalds est tranché dans le cas de MARS : le micro-noyau est le bon choix car la simplicité garantit la reproductibilité et la correction — un monolithe introduirait des bugs qui fausseraient les résultats compétitifs. MARS est un micro-noyau qui pousse le minimalisme jusqu'à l'extrême — zéro abstraction, zéro service, zéro appel système.

Silberschatz (OS Concepts, 9e éd., Ch.5, p.211-213) décrit l'inversion de priorité : un processus de basse priorité détient une ressource dont un processus de haute priorité a besoin, et un processus de moyenne priorité empêche le processus de basse priorité de libérer la ressource. L'incident le plus célèbre est le Mars Pathfinder (1997) : le rover sur Mars se réinitialisait en boucle car un thread de basse priorité (collecte de données météo) détenait un mutex partagé avec un thread de haute priorité (bus de communication), et un thread de moyenne priorité (tâches scientifiques) empêchait le thread basse de terminer. La solution fut le priority inheritance protocol (héritage de priorité) : le thread basse priorité hérite temporairement de la priorité du thread haute priorité qui attend la ressource.

Corewar élimine l'inversion de priorité en éliminant les priorités elles-mêmes. Le round-robin strict ne reconnaît aucune hiérarchie entre processus — chaque processus reçoit exactement un cycle, que ce soit le processus de bombing (critique) ou un processus de leurre (dispensable). C'est la stratégie « nucléaire » contre l'inversion : si personne n'a de priorité, personne ne peut souffrir d'une inversion. Mais le coût est que le processus de bombing — qui devrait être le plus prioritaire — ne reçoit pas plus de CPU que les processus parasites créés par SPL. Corewar résout l'inversion de priorité en supprimant les priorités — efficace contre le bug, fatal à l'optimisation.

Agha (Actors: A Model of Concurrent Computation in Distributed Systems, 1986, MIT Press) et Armstrong (Making Reliable Distributed Systems, 2003, Phil. Thesis) définissent le modèle acteur : chaque acteur est une unité de calcul isolée avec un état privé, qui communique exclusivement par passage de messages asynchrones. Un acteur traite un message à la fois, peut créer de nouveaux acteurs, et peut envoyer des messages à d'autres acteurs. Erlang est le langage qui implémente ce modèle le plus fidèlement — chaque processus Erlang est un acteur avec sa propre mailbox.

Les guerriers Corewar sont des acteurs brisés : ils possèdent un état privé (les registres et le carry) mais n'ont pas de mailbox — ils ne peuvent pas envoyer ou recevoir de messages typés. La seule communication est l'écriture brutale dans la mémoire partagée — l'équivalent d'un acteur qui modifierait directement l'état interne d'un autre acteur, violant le principe d'isolation fondamental du modèle. La conséquence est que les guerriers souffrent de toutes les pathologies que le modèle acteur est conçu pour éviter : data races (deux processus écrivant la même cellule), corruption (un adversaire modifiant l'état d'un autre), et absence de garantie d'ordonnancement (les « messages » dans l'arène sont traités dans l'ordre du round-robin, pas dans l'ordre d'envoi). Armstrong dit : « Let it crash » — en Erlang, un acteur qui échoue est remplacé par un superviseur. En Corewar, un processus qui échoue est simplement mort. Les guerriers sont des acteurs sans isolation ni supervision — la version la plus dangereuse du modèle acteur.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.6, §6.2.2, p.440-441) présente les graphes d'allocation de ressources de Holt (1972) : des processus (cercles) et des ressources (carrés) reliés par des arcs orientés. Un arc ressource→processus signifie « détenu par » ; un arc processus→ressource signifie « en attente de ». Un cycle dans le graphe = interblocage potentiel.

On peut modéliser les conflits de l'arène comme un graphe d'allocation de ressources. Les processus (cercles) sont les PC des guerriers ; les ressources (carrés) sont les cellules mémoire disputées. Un arc « détenu par » relie une cellule au processus qui l'a écrite en dernier ; un arc « en attente de » relie un processus à la cellule qu'il veut lire/modifier. Deux guerriers qui se bombardent mutuellement créent un cycle : A tient la cellule X et veut Y, B tient Y et veut X — un deadlock de ressources. Ce graphe explique pourquoi les scanners « passifs » (qui lisent sans écrire) ne créent pas de cycles et sont donc plus sûrs mais moins offensifs. Le graphe d'allocation de Holt visualise la guerre de territoire : chaque cycle est un front de bataille, chaque arc est une revendication.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.12, p.986-987) cite Fernando Corbató : « My definition of elegance is the achievement of a given functionality with a minimum of mechanism and a maximum of clarity. » Et (p.998-999) : « The ability to combine separate concepts independently is called orthogonality. It is a direct consequence of the simplicity and completeness principles. As a general rule, having a small number of orthogonal elements that can be combined in many ways leads to a small, simple, and elegant system. »

Le format d'instruction Redcode est l'incarnation de l'orthogonalité. Chaque instruction a trois dimensions indépendantes : (1) l'opcode (MOV, ADD, CMP, SPL, etc.), (2) le modificateur (.A, .B, .AB, .F, .I, etc. — quels champs opérer), (3) les modes d'adressage des opérandes A et B (immédiat #, direct $, indirect @, pré-décrément <, post-incrément >). Ces trois dimensions se combinent indépendamment : n'importe quel opcode peut utiliser n'importe quel modificateur avec n'importe quelle combinaison de modes d'adressage. C'est cette orthogonalité qui donne à Redcode son expressivité malgré seulement 16 opcodes. Un MOV.AB avec adressage pré-décrément fait quelque chose de complètement différent d'un MOV.FI avec post-incrément, les deux étant des compositions valides des mêmes éléments orthogonaux. Le « minimum de mécanisme » de Corbaté explique aussi pourquoi MARS lui-même est petit : quelques milliers de lignes de C, contre des millions pour un OS réel.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.3, §3.4.1, p.209) décrit l'algorithme optimal de remplacement de pages (OPT/MIN) de Belady (1966) : évicter la page qui ne sera pas utilisée pendant le plus longtemps dans le futur. Cet algorithme est impossible à implémenter en pratique — il nécessite la connaissance parfaite des accès futurs — mais il sert de borne théorique pour évaluer tout autre algorithme. Tout algorithme réel est mesuré par sa « distance à l'optimal ».

Le bombing optimal en Corewar suit exactement cet algorithme : on devrait écraser la cellule que l'adversaire n'utilisera pas avant le plus longtemps. Un scanner qui identifie les cellules « froides » de l'adversaire (code de boot déjà exécuté, données inertes) approche l'optimal de Belady. Mais comme dans les OS réels, cette information est impossible à obtenir à l'avance — le guerrier ne peut pas prédire les accès futurs de l'adversaire. La conséquence est que tout algorithme de bombing est une approximation de l'optimal, et la mesure de la « distance à l'optimal » est le vrai métrique de qualité d'un scanner. Les bombers séquentiels (step constant) sont les plus éloignés de l'optimal ; les scanners adaptatifs (qui détectent et ciblent le code actif) s'en rapprochent. L'algorithme de Belady prouve que le bombing parfait existe en théorie mais reste à jamais hors de portée — le meilleur guerrier est celui qui s'en approche le plus.

Tanenbaum (Modern Operating Systems, 4e éd., Ch.6, p.462) : « Clearly, no process is blocked and we could even say that things are happening, so this is not a deadlock. Still, no progress is possible, so we do have something equivalent: a livelock. »

Le livelock est la pathologie Corewar la plus courante. Deux guerriers qui se bombardent mutuellement sans jamais toucher le pointeur d'instruction adverse sont en livelock : les deux sont actifs, les deux « progressent » (exécutent des instructions), mais aucun ne progresse vers la victoire. La communauté Corewar appelle cela un « nul par épuisement » — la partie se termine à la limite de cycles avec les deux guerriers encore vivants. L'observation de Tanenbaum que « Most operating systems, including UNIX and Windows, basically just ignore the problem » (p.463) est exactement ce que fait MARS : le scheduler laisse la partie continuer jusqu'à la limite de cycles plutôt que d'essayer de détecter ou résoudre le livelock. C'est aussi pourquoi la stratégie optimale doit viser à tuer les processus adverses et non simplement à les endommager — endommager sans tuer mène au livelock, tuer mène à la victoire.