Journal TapTempo en brainfuck

Posté par (page perso) . Licence CC by-sa
47
3
mar.
2018

Sommaire

TapTempo est disponible en version BrainFuck

C'est un portage partiel (faut pas pousser ;), donc :

  • Pas d'options
  • Pas de localisation
  • Pas de remise à zéro des samples
  • Que deux samples
  • N'importe quelle touche fonctionne (Pas seulement <Return>)

Mais c'est tout de même une version Brainfuck qui fait son boulot :

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

(Ce n'est pas du beau brainfuck, pas mal de duplication de code, pas vraiment réutilisable et non testé… J'ai honte)

Subtilités de la machine brainfuck

Pour faire tourne ce code il faut une machine virtuelle brainfuck un peu particulière pour intégrer la gestion d'un compteur hardware de temps. Ma machine est équipée d'une mémoire infinie à droite et à gauche, cellules de 16 bits.

Le registre -1 est particulier, en effet, toute écriture sur celui-ci va provoque l'écriture sur le registre 0 d'un timer qui représente 5 fois le temps passé depuis la dernière écriture sur -1 avec un minimum de 1. Le facteur cinq étant pour avoir un peu de précision, mais pas trop, car le temps d'exécution est proportionnelle à la précision du compteur ;) Le minimum de 1 sert à éviter des divisions par 0 dans le code brainfuck.

Implémentation de la VM

La machine virtuelle est écrite en Haskell dans le fichier Bf.hs que nous allons détailler maintenant.

Parsing du brainfuck

Création d'un AST représentant les instructions brainfuck. J'ai juste ajouté une instruction Debug qui permet d'afficher l'état de la VM quand le code contient le caractère ! :

data BrainFuck = Add
               | Sub
               | MemoryLeft
               | MemoryRight
               | Put
               | Read
               | Loop [BrainFuck]
               | Comment Char
               | Debug
               deriving (Show)

Le parseur est le suivant :

parseBf :: Parser BrainFuck
parseBf = choice
  [ Add <$ char '+'
  , Sub <$ char '-'
  , MemoryLeft <$ char '<'
  , MemoryRight <$ char '>'
  , Put <$ char '.'
  , Read <$ char ','
  , Loop <$> (char '[' *> many parseBf <* char ']')
  , Debug <$ char '!'
  , Comment <$> noneOf "+-<>.,[]"
  ]

parseProgram :: Parser Program
parseProgram = Program <$> many parseBf

Si une opération de parsing, comme char '+' réussie, le parseur renvoie Add. Je ne vous détaille pas trop, mais sachez que <{mathjax} et<> sont tellement habituels en Haskell que cela ne fait peur à personne, il s'agit "simplement" d'opérateurs représentant la fonction map.

Bandeau de mémoire infinie

La mémoire est représentée par deux listes chaînées de Word16 (int sur 16 bits), l'état actuelle des listes chaînées représentant la position actuelle sur le bandeau :

data Memory = Memory [Word16] [Word16]
  deriving (Show)

S'en suit un ensemble de fonction servant à aller à droite, à gauche,
à écrire et lire la mémoire, rien de bien intéressant, c'est de
l'analyse de cas. Pour aller à droite :

memoryToRight :: Memory -> Memory
memoryToRight (Memory l r) = case r of
  (x:xs) -> Memory (x:l) xs
  [] -> Memory (0:l) []

On prend un élément de la liste de droite pour le mettre dans la liste de gauche, mais si la liste de droite est vide, on met un 0 à la place. On aurait pu s'affranchir de ce cas en générant initialement une liste infinie de 0. C'est amusant ;)

La Machine

Celle-ci contient une mémoire, un indice pour représenter la position et le compteur de temps :

data Machine = Machine Memory Int (Maybe TimeSpec)
  deriving (Show)

Suivit de quelques fonctions pour aller à gauche / droite / modifier la mémoire. La fonction de modification contient un cas particulier pour le registre -1 :

modify :: (Word16 -> Word16) -> Machine -> IO (Machine)
modify f (Machine mem (-1) tM) = do
  t' <- getTime Monotonic
  let reg0Val = case tM of
        Nothing -> 0
        Just t -> fromIntegral ((fromIntegral precision * toNanoSecs (diffTimeSpec t t')) `div` (10 ^ (9 :: Integer)))
      -- value is bounded to 1 to avoid divid by zero
  pure (Machine (memoryModify f (memoryToLeft (memoryModify (const (max 1 reg0Val)) (memoryToRight mem)))) (-1) (Just t'))
modify f (Machine mem idx tM) = pure (Machine (memoryModify f mem) idx

(Ce code est vraiment degeux, je n'ai fais aucun effort). Mais en gros, dans le cas -1, on calcul le delta de temps, on va un coup à droite pour le stocker, puis on revient à gauche.

Exécution du programme

Cette partie est jolie car il s'agit simplement d'appeler la bonne fonction en fonction de l'instruction à exécuter :

evalInstr :: Machine -> BrainFuck -> IO Machine
evalInstr m Add = modify (+1) m
evalInstr m Sub = modify (subtract 1) m
evalInstr m MemoryRight = pure (toRight m)
evalInstr m MemoryLeft = pure (toLeft m)
evalInstr m Read = do
  c <- getChar
  modify (const (fromIntegral (ord c))) m
evalInstr m Put = do
  putChar (chr (fromIntegral (get m)))
  pure m
evalInstr m loop@(Loop subInstrs)
  | get m == 0 = pure m
  | otherwise = do
      m' <- evalInstrs subInstrs m
      evalInstr m' loop
evalInstr m (Comment _) = pure m
evalInstr m Debug = print m >> pure m

Et voila. Ouf.

Le programme brainfuck

Comment je l'ai écris, et bien à la main, mais avec quelques fonctions utilitaires contenues dans TapTempoBf.hs. D'ailleurs ce programme Haskell écrit le programme brainfuck sur sa sortie standard.

Un exemple d'exécution ?

Appuyer sur une touche en cadence (q pour quitter).
Tempo : 300 bpm.
Tempo : 100 bpm.
Tempo : 100 bpm.
Tempo : 150 bpm.
Tempo : 50 bpm.
Tempo : 37 bpm.
Tempo : 25 bpm.
Tempo : 60 bpm.
Tempo : 300 bpm.
Tempo : 300 bpm.
Tempo : 300 bpm.
Tempo : 300 bpm.
Tempo : 300 bpm.
Tempo : 18 bpm.
qAu revoir

Conclusion

C'était un défi, je l'ai fais, c'était amusant. Bon, je commence à avoir quelques notions de brainfuck (mon premier journal linuxfr datant d'il y a quelques centaines d'année parlait déja de brainfuck), donc voila, c'était marrant ;)

Ce qui serait bien c'est de faire une VM brainfuck un peu plus intelligente, car là c'est vraiment trop lent. En remplaçant les séries de "------" pour une unique opération, en détectant des motifs connus (comme l'affichage d'un caractère ou la division). C'est un travail que j'ai commencé il y a quelques temps et sur lequel je compte me remettre quand j'aurais du temps puisque mon but ultime c'est de réaliser un lancer de rayon en brainfuck ;)

  • # Excellent

    Posté par (page perso) . Évalué à 4.

    Excellent d'avoir tenté l'expérience, et bravo pour le résultat !

    Si je comprends bien, le code brainfuck ne comprend que le calcul du tempo puisque d'après le fichier TapTempoBF.hs les chaînes de caractère de début et de fin ne sont pas dans le programme proprement dit ?

    • [^] # Re: Excellent

      Posté par (page perso) . Évalué à 5.

      le code brainfuck ne comprend que le calcul du tempo puisque d'après le fichier TapTempoBF.hs les chaînes de caractère de début et de fin ne sont pas dans le programme proprement dit ?

      Si, le fichier TapTempoBF.hs ne fait que "générer" le code brainfuck. À vrai dire l'affichage de caractères statiques est ce qu'il y a de plus simple en brainfuck ;)

      Ce que fait réellement le code brainfuck :

      • Affichage des chaines
      • "Stimulation" du registre matériel pour avoir le temps
      • Lecture du delta de temps, division pour avoir le rythme en bpm, affichage.
      • Gestion des entrées, de la boucle, de quitter avec 'q'

      Le seul truc spéciale que fait la VM brainfuck c'est le registre hardware pour le temps (là je ne vois pas d'autre solution) et il calcul le delta de temps tout seul. J'aurais clairement pu juste mettre le temps actuel dans un registre et faire la soustraction en brainfuck, mais les soustraction de grandes valeurs prennent un temps linéaire, ce qui aurait été catastrophique.

      • [^] # Re: Excellent

        Posté par (page perso) . Évalué à 1.

        Ah ok, je n'avais pas compris que le displayString avant les chaînes de caractères était un appel à une fonction.
        Merci pour cette précision !

  • # Oh my God !!

    Posté par (page perso) . Évalué à 10.

    Bravo, ça faisait quelques jours que tu en parlais mais alors là, chapeau bas !!!!

    Cette version, même si elle n'intègre pas tout, est impressionnante.

    Alors oui, on va dire que j'ai deux discours mais clairement, là, faire l'internationalisation et la gestion d'options en BrainFuck serait vraiment trop demandé :D

  • # Il faudrai faire une version hardware

    Posté par . Évalué à -5.

    J'ai incrusté un micro dans mon fauteuil de bureau comme ça je peux mesurer l'interval de temps entre deux pets bruyants, j'envoie tout ça dans le cloud et je loue les services d'un big datanaliste géorgien pour avoir des stats, c'est beau le XXI siècle.

  • # Prochain défi ?

    Posté par . Évalué à 5.

    Quelqu'un veux tenté le coup en emojicode ?

    • [^] # Re: Prochain défi ?

      Posté par . Évalué à 2.

      Je demande le port en Malboge !

    • [^] # Re: Prochain défi ?

      Posté par (page perso) . Évalué à 2.

      Et en LOLCODE \o/

    • [^] # Re: Prochain défi ?

      Posté par (page perso) . Évalué à 4.

      Et comme nous sommes sur DaLFP, il me semble essentiel qu'une tentative soit faite en GOTO++, puisque ce langage semble être une spécialité locale. Je n'ai pas le temps de mon coté, parce que je révise mes fondamentaux en vrai programmation.

      En tout cas, un grand merci à tous ceux qui ont donnés de leur temps de cerveau disponible pour ces portages très instructifs, et je les invite à proposer une conférence éclair pour le prochain THSF

      * Ils vendront Usenet^W les boites noires quand on aura fini de les remplir.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.