Langage Malbolge

Malbolge est un langage de programmation esotérique, conçu en 1998 par Ben Olmstead. Son objectif était de créer un langage aussi difficile à utiliser que possible.

Malbolge est réputé pour sa difficulté extrême, car plusieurs mécanismes se combinent pour rendre la programmation presque imprévisible :

— Architecture ternaire et mémoire unique : le langage repose sur une machine virtuelle en base 3, avec une mémoire linéaire de 59049 cellules où données et instructions cohabitent. Toute manipulation peut donc modifier le programme.

— Registres et instructions minimalistes mais contextuels : Malbolge ne propose que trois registres (a, c, d) et seulement huit instructions, dont l'effet dépend de la position mémoire modulo 94. Une même instruction peut se comporter différemment selon son emplacement.

— Auto-modification continue du code : après chaque exécution, l'instruction est transformée via une permutation. Le programme change donc en permanence, rendant impossible une lecture stable.

— Crazy operation et chiffrement des instructions : Une opération dite folle combine les valeurs de manière non intuitive, renforçant le caractère chaotique de l'exécution. Les instructions sont en plus chiffrées sur 94 caractères, obscurcissant davantage le code source.

La création d'un programme à la main est quasiment impossible. Le premier programme fonctionnel en Malbolge (un Hello, World!) n'a été généré qu'en 2000, via un programme en Lisp.

Cependant, il est possible d'écrire un programme avec une séquence d'instructions précise qui, après avoir été automatiquement chiffrée et transformée par la machine virtuelle Malbolge, produit un texte souhaité.

Décoder ou interpréter du Malbolge revient à simuler son exécution :

Chaque instruction est récupérée à l'adresse pointée par le registre c, puis décryptée selon sa position modulo 94 et exécutée. La cellule mémoire est re-cryptée et les registres c et d sont incrémentés.

Les 8 instructions de base du langage Malbolge sont :

Reconnaître du code Malbolge repose sur plusieurs indices :

— Le code source ne contient que des caractères imprimables (ASCII 33–126), sans espaces ni caractères de contrôle.

— Les instructions peuvent former des séquences répétitives, car chaque opcode est lié à une position modulo 94. Un code Malbolge valide suit donc des motifs reconnaissables.

— Le code généré par dCode pourra contenir des suites de caractères ASCII en valeurs décroissantes et donc les lettres ZYXWVUTSRQPONMLKJIHGFEDCBA et zyxwvutsrqponmlkjihgfedcba, ce n'est cependant pas obligatoire.

dCode utilise une recherche en profondeur itérative (IDDFS) pour explorer l'espace d'états chaotique du langage. En conservant l'état des registres par récursivité, cela permet de revenir en arrière lorsqu'il rencontre une impasse (backtracking).

La boucle de recherche principale fonctionne par force brute à profondeur limitée. Elle recherche une séquence d'instructions Malbolge constituée de NOP (68), de rotations (39) ou d'opérations Crazy (62) qui, une fois exécutées, laisseront dans l'accumulateur mémoire une valeur dont les 8 bits de poids faible correspondent à la valeur ASCII du caractère cible actuel. Si aucune solution n'est trouvée, dcode ajoute une instruction de rotation pour modifier l'état de la machine et réessaie à l'étape suivante.

Le langage Malbolge tire son nom du huitième cercle de l'Enfer dans La Divine Comédie de Dante Alighieri, appelé Malebolge (ou Malbolge dans certaines traductions).

Ce cercle est réservé aux fraudeurs et est décrit comme un lieu de souffrance extrême, divisé en dix fosses concentriques où les âmes sont punies de manière particulièrement ingénieuse et cruelle.

Tout comme le Malebolge de Dante est conçu pour tourmenter ses occupants, le langage Malbolge est conçu pour décourager quiconque tente de l'utiliser.