Brainfuck - Brainfuck

Brainfuck est un langage de programmation ésotérique créé en 1993 par Urban Müller.

Remarquable par son extrême minimalisme, le langage se compose de seulement huit commandes simples, d'un pointeur de données et d'un pointeur d'instructions . Bien qu'il soit entièrement Turing complet , il n'est pas destiné à une utilisation pratique, mais à défier et amuser les programmeurs . Brainfuck nécessite simplement de diviser les commandes en étapes microscopiques.

Le nom de la langue est une référence au terme d'argot brainfuck , qui fait référence à des choses si compliquées ou inhabituelles qu'elles dépassent les limites de la compréhension.

Histoire

En 1992, Urban Müller, un étudiant suisse en physique, a repris une petite archive en ligne pour le logiciel Amiga . Les archives sont devenues plus populaires et ont rapidement été diffusées dans le monde entier. Aujourd'hui, il s'agit de la plus grande archive Amiga au monde, connue sous le nom d' Aminet .

Müller a conçu Brainfuck dans le but d'implémenter le plus petit compilateur possible , inspiré du compilateur 1024 octets pour le langage de programmation FALSE . Le compilateur original de Müller a été implémenté en langage machine et compilé en un binaire d'une taille de 296 octets. Il a téléchargé le premier compilateur Brainfuck sur Aminet en 1993. Le programme était accompagné d'un fichier "Lisez-moi", qui décrivait brièvement le langage, et défiait le lecteur "Qui peut programmer quelque chose d'utile avec ? :) ". Müller a également inclus un interprète et quelques exemples assez élaborés. Une deuxième version du compilateur n'utilisait que 240 octets.

Au fur et à mesure que Aminet grandissait, le compilateur est devenu populaire parmi la communauté Amiga, et avec le temps, il a été implémenté pour d'autres plates-formes.

P′′: La "langue parentale" formelle de Brainfuck

À l'exception de ses deux commandes d'E/S, Brainfuck est une variante mineure du langage de programmation formel P′′ créé par Corrado Böhm en 1964, qui à son tour est explicitement basé sur la machine de Turing . En fait, en utilisant six symboles équivalents aux commandes Brainfuck respectives +, -, <, >, [, ], Böhm a fourni un programme explicite pour chacune des fonctions de base qui, ensemble, servent à calculer toute fonction calculable . Ainsi, les premiers programmes "Brainfuck" apparaissent dans l'article de Böhm de 1964 - et ils étaient suffisants pour prouver l'exhaustivité de Turing.

The Infinite Abacus : le langage "grand-parent" de Brainfuck

Une version avec adressage mémoire explicite plutôt sans pile et saut conditionnel a été introduite par Joachim Lambek en 1961 sous le nom d'Infinite Abacus, constituée d'un nombre infini de cellules et de deux instructions :

• X+ (incrémenter la cellule X)
• X- else jump T (décrémenter X s'il est positif sinon sauter à T)

Il prouve que l'Abacus Infinite peut calculer n'importe quelle fonction récursive calculable en programmant un ensemble de fonctions μ-récursives de base de Kleene .

Sa machine a été simulée par le calcul de modélisation de la machine de Melzac via l'arithmétique (plutôt que la logique binaire) imitant un opérateur humain déplaçant des cailloux sur un boulier, d'où l'exigence que tous les nombres soient positifs. Melzac, dont un ordinateur à jeu d'instructions équivaut à un boulier infini, donne des programmes de multiplication, pgcd, n ^ième nombre premier, représentation en base b, tri par magnitude, et montre comment simuler une machine de Turing arbitraire.

Conception du langage

Le langage se compose de huit commandes , répertoriées ci-dessous. Un programme brainfuck est une séquence de ces commandes, éventuellement entrecoupées d'autres caractères (qui sont ignorés). Les commandes sont exécutées séquentiellement, à quelques exceptions près : un pointeur d'instruction commence à la première commande et chaque commande vers laquelle il pointe est exécutée, après quoi il passe normalement à la commande suivante. Le programme se termine lorsque le pointeur d'instruction dépasse la dernière commande.

Le langage brainfuck utilise un modèle de machine simple composé du pointeur de programme et d'instruction, ainsi qu'un tableau unidimensionnel d'au moins 30 000 cellules d' octets initialisées à zéro ; un pointeur de données mobile (initialisé pour pointer sur l'octet le plus à gauche du tableau) ; et deux flux d'octets pour l'entrée et la sortie (le plus souvent connectés respectivement à un clavier et à un moniteur, et utilisant l' encodage de caractères ASCII ).

Commandes

Les huit commandes de langue se composent chacune d'un seul caractère :

(Alternativement, la ]commande peut à la place être traduite par un saut inconditionnel vers la [commande correspondante , ou vice versa ; les programmes se comporteront de la même manière mais s'exécuteront plus lentement, en raison d'une double recherche inutile.)

[et ]correspondent comme le font habituellement les parenthèses : chacun [correspond exactement à un ]et vice versa, le [premier vient en premier, et il ne peut y avoir aucun sans correspondance [ou ]entre les deux.

Les programmes Brainfuck peuvent être traduits en C en utilisant les substitutions suivantes, en supposant qu'il ptrest de type char*et qu'il a été initialisé pour pointer vers un tableau d'octets mis à zéro :

Comme leur nom l'indique, les programmes Brainfuck ont ​​tendance à être difficiles à comprendre. C'est en partie parce que toute tâche légèrement complexe nécessite une longue séquence de commandes et en partie parce que le texte du programme ne donne aucune indication directe sur l' état du programme . Ceci, ainsi que l'inefficacité de Brainfuck et ses capacités d'entrée/sortie limitées, sont quelques-unes des raisons pour lesquelles il n'est pas utilisé pour une programmation sérieuse. Néanmoins, comme tout langage complet de Turing, Brainfuck est théoriquement capable de calculer n'importe quelle fonction calculable ou de simuler tout autre modèle de calcul, s'il a accès à une quantité illimitée de mémoire. Une variété de programmes Brainfuck ont ​​été écrits. Bien que les programmes Brainfuck, en particulier les programmes compliqués, soient difficiles à écrire, il est assez trivial d'écrire un interpréteur pour Brainfuck dans un langage plus typique tel que C en raison de sa simplicité. Il existe même des interprètes Brainfuck écrits dans le langage Brainfuck lui-même.

Brainfuck est un exemple de ce qu'on appelle un tarpit de Turing : il peut être utilisé pour écrire n'importe quel programme, mais ce n'est pas pratique de le faire, car Brainfuck fournit si peu d'abstraction que les programmes deviennent très longs ou compliqués.

Exemples

Ajouter deux valeurs

Comme premier exemple simple, l'extrait de code suivant ajoutera la valeur de la cellule actuelle à la cellule suivante : chaque fois que la boucle est exécutée, la cellule actuelle est décrémentée, le pointeur de données se déplace vers la droite, cette cellule suivante est incrémentée, et le pointeur de données se déplace à nouveau vers la gauche. Cette séquence est répétée jusqu'à ce que la cellule de départ soit 0.

[->+<]

Ceci peut être incorporé dans un programme d'addition simple comme suit :

++       Cell c0 = 2
> +++++  Cell c1 = 5

[        Start your loops with your cell pointer on the loop counter (c1 in our case)
< +      Add 1 to c0
> -      Subtract 1 from c1
]        End your loops with the cell pointer on the loop counter

At this point our program has added 5 to 2 leaving 7 in c0 and 0 in c1
but we cannot output this value to the terminal since it is not ASCII encoded.

To display the ASCII character "7" we must add 48 to the value 7.
We use a loop to compute 48 = 6 * 8.

++++ ++++  c1 = 8 and this will be our loop counter again
[
< +++ +++  Add 6 to c0
> -        Subtract 1 from c1
]
< .        Print out c0 which has the value 55 which translates to "7"!

Bonjour le monde!

Le programme suivant affiche "Hello World!" et une nouvelle ligne à l'écran :

[ This program prints "Hello World!" and a newline to the screen, its
  length is 106 active command characters. [It is not the shortest.]

  This loop is an "initial comment loop", a simple way of adding a comment
  to a BF program such that you don't have to worry about any command
  characters. Any ".", ",", "+", "-", "<" and ">" characters are simply
  ignored, the "[" and "]" characters just have to be balanced. This
  loop and the commands it contains are ignored because the current cell
  defaults to a value of 0; the 0 value causes this loop to be skipped.
]
++++++++               Set Cell #0 to 8
[
    >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
    [                   as the cell will be cleared by the loop
        >++             Add 2 to Cell #2
        >+++            Add 3 to Cell #3
        >+++            Add 3 to Cell #4
        >+              Add 1 to Cell #5
        <<<<-           Decrement the loop counter in Cell #1
    ]                   Loop until Cell #1 is zero; number of iterations is 4
    >+                  Add 1 to Cell #2
    >+                  Add 1 to Cell #3
    >-                  Subtract 1 from Cell #4
    >>+                 Add 1 to Cell #6
    [<]                 Move back to the first zero cell you find; this will
                        be Cell #1 which was cleared by the previous loop
    <-                  Decrement the loop Counter in Cell #0
]                       Loop until Cell #0 is zero; number of iterations is 8

The result of this is:
Cell no :   0   1   2   3   4   5   6
Contents:   0   0  72 104  88  32   8
Pointer :   ^

>>.                     Cell #2 has value 72 which is 'H'
>---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
+++++++..+++.           Likewise for 'llo' from Cell #3
>>.                     Cell #5 is 32 for the space
<-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
<.                      Cell #3 was set to 'o' from the end of 'Hello'
+++.------.--------.    Cell #3 for 'rl' and 'd'
>>+.                    Add 1 to Cell #5 gives us an exclamation point
>++.                    And finally a newline from Cell #6

Pour la "lisibilité", ce code a été réparti sur de nombreuses lignes, et des blancs et des commentaires ont été ajoutés. Brainfuck ignore tous les caractères à l'exception des huit commandes, +-<>[],.donc aucune syntaxe spéciale pour les commentaires n'est nécessaire (tant que les commentaires ne contiennent pas les caractères de la commande). Le code aurait tout aussi bien pu être écrit comme :

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

ROT13

Ce programme chiffre son entrée avec le chiffrement ROT13 . Pour ce faire, il doit mapper les caractères AM ( ASCII 65-77) vers NZ (78-90), et vice versa. Il doit également mapper am (97-109) à nz (110-122) et vice versa. Il doit mapper tous les autres caractères sur eux-mêmes ; il lit les caractères un par un et sort leurs équivalents chiffrés jusqu'à ce qu'il lise un EOF (ici supposé être représenté par -1 ou "pas de changement"), auquel point le programme se termine.

L'approche de base utilisée est la suivante. En appelant le caractère d'entrée x , divisez x -1 par 32, en gardant le quotient et le reste. À moins que le quotient soit 2 ou 3, il suffit de sortir x , en en ayant conservé une copie lors de la division. Si le quotient est 2 ou 3, diviser le reste (( x -1) modulo 32) par 13 ; si le quotient ici est 0, sortie x +13 ; si 1, sortie x -13 ; si 2, sortie x .

En ce qui concerne l'algorithme de division, lors de la division de y par z pour obtenir un quotient q et un reste r , il existe une boucle externe qui définit q et r d' abord sur le quotient et le reste de 1/ z , puis sur ceux de 2/ z , et ainsi au; après y avoir exécuté y fois, cette boucle externe se termine, laissant q et r définis sur le quotient et le reste de y / z . (Le dividende y est utilisé comme un compteur décroissant qui contrôle le nombre de fois que cette boucle est exécutée.) Dans la boucle, il y a du code pour incrémenter r et décrémenter y , ce qui est généralement suffisant ; cependant, à chaque z ième passage dans la boucle externe, il est nécessaire de remettre à zéro r et d'incrémenter q . Cela se fait avec un compteur décroissant fixé au diviseur z ; à chaque passage dans la boucle externe, ce compteur est décrémenté et lorsqu'il atteint zéro, il est rechargé en déplaçant la valeur de r dans celui-ci.

-,+[                         Read first character and start outer character reading loop
    -[                       Skip forward if character is 0
        >>++++[>++++++++<-]  Set up divisor (32) for division loop
                               (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero)
        <+<-[                Set up dividend (x minus 1) and enter division loop
            >+>+>-[>>>]      Increase copy and remainder / reduce divisor / Normal case: skip forward
            <[[>+<-]>>+>]    Special case: move remainder back to divisor and increase quotient
            <<<<<-           Decrement dividend
        ]                    End division loop
    ]>>>[-]+                 End skip loop; zero former divisor and reuse space for a flag
    >--[-[<->+++[-]]]<[         Zero that flag unless quotient was 2 or 3; zero quotient; check flag
        ++++++++++++<[       If flag then set up divisor (13) for second division loop
                               (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero)
            >-[>+>>]         Reduce divisor; Normal case: increase remainder
            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient
            <<<<<-           Decrease dividend
        ]                    End division loop
        >>[<+>-]             Add remainder back to divisor to get a useful 13
        >[                   Skip forward if quotient was 0
            -[               Decrement quotient and skip forward if quotient was 1
                -<<[-]>>     Zero quotient and divisor if quotient was 2
            ]<<[<<->>-]>>    Zero divisor and subtract 13 from copy if quotient was 1
        ]<<[<<+>>-]          Zero divisor and add 13 to copy if quotient was 0
    ]                        End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3)
    <[-]                     Clear remainder from first division if second division was skipped
    <.[-]                    Output ROT13ed character from copy and clear it
    <-,+                     Read next character
]                            End character reading loop

Problèmes de portabilité

En partie parce qu'Urban Müller n'a pas écrit de spécification de langage approfondie, les nombreux interprètes et compilateurs de brainfuck ultérieurs ont implémenté des dialectes légèrement différents de brainfuck.

Taille de la cellule

Dans la distribution classique, les cellules sont de taille 8 bits (les cellules sont des octets), et c'est encore la taille la plus courante. Cependant, pour lire des données non textuelles, un programme brainfuck peut avoir besoin de distinguer une condition de fin de fichier de toute valeur d'octet possible ; ainsi, des cellules de 16 bits ont également été utilisées. Certaines implémentations ont utilisé des cellules 32 bits, des cellules 64 bits ou des cellules bignum avec une plage pratiquement illimitée, mais les programmes qui utilisent cette plage supplémentaire sont susceptibles d'être lents, car le stockage de la valeur dans une cellule prend du temps car la valeur d'une cellule peut seulement être modifié par incrémentation et décrémentation. ${\style d'affichage n}$${\style d'affichage O(n)}$

Dans toutes ces variantes, les ,et .commandes lisent encore et les données d'écriture en octets. Dans la plupart d'entre eux, les cellules s'enroulent, c'est-à-dire qu'incrémenter une cellule qui contient sa valeur maximale (avec la +commande) l'amènera à sa valeur minimale et vice versa. Les exceptions sont les implémentations éloignées du matériel sous-jacent, les implémentations qui utilisent des bignums et les implémentations qui tentent d'imposer la portabilité.

Il est généralement facile d'écrire des programmes brainfuck qui ne provoquent jamais de bouclage ou de débordement d'entiers, et donc ne dépendent pas de la taille des cellules. En général, cela signifie éviter l'incrément de +255 (boucle 8 bits non signé), ou éviter de dépasser les limites de [-128, +127] (boucle 8 bits signé) (puisqu'il n'y a pas d'opérateurs de comparaison, un programme ne peut pas faire la distinction entre un cellule de taille binaire fixe du complément à deux signé et non signé et la négativité des nombres est une question d'interprétation). Pour plus de détails sur le bouclage d'entier, consultez l' article sur le débordement d'entier .

Taille du tableau

Dans la distribution classique, le tableau a 30 000 cellules et le pointeur commence à la cellule la plus à gauche. Encore plus de cellules sont nécessaires pour stocker des choses comme le millionième nombre de Fibonacci , et le moyen le plus simple de compléter le langage Turing est de rendre le tableau illimité sur la droite.

Quelques implémentations étendent également le tableau vers la gauche ; c'est une caractéristique rare, et donc les programmes portables de brainfuck n'en dépendent pas.

Lorsque le pointeur se déplace en dehors des limites du tableau, certaines implémentations donneront un message d'erreur, certaines essaieront d'étendre le tableau dynamiquement, certaines ne le remarqueront pas et produiront un comportement indéfini , et quelques-unes déplaceront le pointeur vers l'extrémité opposée de le tableau. Certains compromis sont impliqués : étendre le tableau dynamiquement vers la droite est l'approche la plus conviviale et est bonne pour les programmes gourmands en mémoire, mais cela entraîne une pénalité de vitesse. Si un tableau de taille fixe est utilisé, il est utile de le rendre très grand ou, mieux encore, de laisser l'utilisateur définir la taille. Donner un message d'erreur pour les violations de limites est très utile pour le débogage, mais même cela entraîne une pénalité de vitesse à moins qu'il ne puisse être géré par les protections de la mémoire du système d'exploitation.

Code de fin de ligne

Différents systèmes d'exploitation (et parfois différents environnements de programmation) utilisent des versions subtilement différentes d'ASCII. La différence la plus importante réside dans le code utilisé pour la fin d'une ligne de texte. MS-DOS et Microsoft Windows utilisent un CRLF , c'est-à-dire un 13 suivi d'un 10, dans la plupart des contextes. UNIX et ses descendants (y compris Linux et macOS) et Amigas n'en utilisent que 10, et les Mac plus anciens n'en utilisent que 13. Ce serait difficile si les programmes brainfuck devaient être réécrits pour différents systèmes d'exploitation. Cependant, une norme unifiée était facile à créer. Le compilateur d'Urban Müller et ses exemples de programmes utilisent 10, à la fois en entrée et en sortie ; il en va de même pour la grande majorité des programmes de brainfuck existants ; et 10 est également plus pratique à utiliser que CRLF. Ainsi, les implémentations brainfuck devraient s'assurer que les programmes brainfuck qui supposent une nouvelle ligne = 10 fonctionneront correctement ; beaucoup le font, mais d'autres non.

Cette hypothèse est également cohérente avec la plupart des exemples de code du monde pour C et d'autres langages, en ce sens qu'ils utilisent "\n", ou 10, pour leurs nouvelles lignes. Sur les systèmes qui utilisent les fins de ligne CRLF, la bibliothèque standard C remappe de manière transparente "\n" en "\r\n" en sortie et "\r\n" en "\n" en entrée pour les flux non ouverts en mode binaire.

Comportement de fin de fichier

Le comportement de la ,commande lorsqu'une condition de fin de fichier a été rencontrée varie. Certaines implémentations définissent la cellule au pointeur sur 0, certaines la définissent sur la constante C EOF (en pratique, c'est généralement -1), certaines laissent la valeur de la cellule inchangée. Il n'y a pas de véritable consensus; Les arguments pour les trois comportements sont les suivants.

Définir la cellule sur 0 évite l'utilisation de nombres négatifs et rend légèrement plus concis l'écriture d'une boucle qui lit les caractères jusqu'à ce que EOF se produise. Il s'agit d'une extension de langage conçue par Panu Kalliokoski.

Définir la cellule sur -1 permet à EOF d'être distingué de toute valeur d'octet (si les cellules sont plus grandes que des octets), ce qui est nécessaire pour lire des données non textuelles ; aussi, c'est le comportement de la traduction C de ,donnée dans le fichier readme de Müller. Cependant, il n'est pas évident que ces traductions en C doivent être considérées comme normatives.

Laisser la valeur de la cellule inchangée est le comportement du compilateur brainfuck d'Urban Müller. Ce comportement peut facilement coexister avec l'un ou l'autre des autres ; par exemple, un programme qui suppose EOF = 0 peut définir la cellule sur 0 avant chaque ,commande, et fonctionnera alors correctement sur les implémentations qui font soit EOF = 0 soit EOF = "pas de changement". Il est si facile de s'adapter au comportement "pas de changement" que tout programmeur brainfuck intéressé par la portabilité devrait le faire.

Implémentations

Bien qu'il soit trivial de faire un interpréteur naïf de brainfuck, écrire un compilateur ou un interpréteur d' optimisation devient plus un défi et un amusement tout comme l'écriture de programmes dans brainfuck lui-même est : pour produire des résultats raisonnablement rapides, le compilateur doit reconstituer les instructions fragmentaires forcées par la langue. Les optimisations possibles vont de simples optimisations de judas de longueur d'exécution sur des commandes répétées et des modèles de boucle communs comme [-], à des optimisations plus compliquées comme l' élimination du code mort et le pliage constant .

En plus de l'optimisation, d'autres types d'interpréteurs de brainfuck inhabituels ont également été écrits. Plusieurs compilateurs brainfuck ont ​​été rendus inférieurs à 200 octets – l'un n'est que de 100 octets dans le code machine x86.

Dérivés

De nombreuses personnes ont créé des équivalents brainfuck (langages avec des commandes qui correspondent directement à brainfuck) ou des dérivés brainfuck (langages qui étendent son comportement ou modifient sa sémantique).

Quelques exemples:

• Pi , qui mappe le brainfuck en erreurs dans les chiffres individuels de Pi .
• VerboseFuck , qui ressemble à un langage de programmation traditionnel, seul ce qui apparaît comme paramètres ou expressions fait en réalité partie de commandes plus longues qui ne peuvent pas être modifiées.
• DerpPlusPlus , dans lequel les commandes sont remplacées par des mots tels que 'HERP', 'DERP', 'GIGITY', etc.
• D'accord ! , Qui associe huit commandes de brainfuck à des combinaisons de deux mots de « Ook. », « Ook? » Et « Ook! », En plaisantant conçu pour être « inscriptible et lisible par les orangs-outans » , selon son créateur, une référence à la Bibliothécaire orang-outan dans les romans de Terry Pratchett .
• Ternaire , concept similaire à Ook ! mais au lieu de cela consistant en des permutations des caractères ASCII 0, 1 et 2.
• BodyFuck , une implémentation BrainFuck basée sur un système de contrôle gestuel afin que les mouvements du programmeur soient capturés par une caméra vidéo et convertis en les 8 caractères possibles.
• OooWee , les commandes sont des variantes de OooWee (par exemple ooo,ooe,wee etc.). Inspiré du personnage de Rick et Morty , M. PoopyButthole.
• I Use Arch btw , qui mappe le brainfuck dans les mots trouvés dans la phrase "I Use Arch btw". Inspiré d'une phrase inventée par la communauté Arch Linux .
• Brainfunk , mappe brainfuck à des échantillons de voix, qui sont utilisés dans une piste de danse, dont les mots encodent un programme de brainfuck.

Voir également

• JSFuck - un langage de programmation JavaScript ésotérique avec un ensemble très limité de caractères

Les références

Liens externes

• Brainfuck à Curlie
• Interpréteur Brainfuck en ligne en JavaScript avec collection de programmes
• Brainfuck IDE – Un environnement de développement brainfuck avec débogueur interactif
• Générateur Brainfuck - Un générateur de texte pour brainfuck
• Brainfuck collection d'interprètes et de scripts
• Brainfuck au compilateur COBOL, C, ASM, PL/1, ...
• Brainfuck Assembler traduisant le code d'assemblage x86 (ensemble réduit) en code brainfuck
• Aire de jeux Brainfuck sur tio.run