blog

Le langage BrainFuck est un langage ésotérique (comprendre par la qu’il ne sert pas a grand chose), minimaliste.

Il suppose une machine avec un ruban de mémoire, un pointeur sur une cellule de cette mémoire, et ne contient que 8 opérations, chacune représentée par un caractère dans le code source :

En résumé, > et < font bouger un pointeur, + et - modifient la valeur de la cellule courante, . et , servent d'entrées-sorties, et [ ] fait une boucle.

A titre d’exemple, ce programme affiche “Hello World!” : hello.bf

Voici le code complet de l’interpréteur que cet article vise a expliquer.

Interpréteur basique, sans optimisations

Représentation des opérations basiques de BrainFuck

La première chose à faire, c’est de décider de la représentation interne des opérations. J’ai choisi de regrouper les opérations de déplacement et de modification, et de représenter [..] comme une sous liste d’opération.

  type operation =
    | Move of int 
    | Add of int
    | Output
    | Input
    | Loop of operation list

Conversion du code BF en arbre d’opérations

Maintenant, il nous faut un moyen de convertir le source BrainFuck en un arbre d’opérations, en utilisant le type que nous venons de définir. En dehors des boucles, la conversion est assez directe.

  let rec build_ast tokens =
    let rec loop tokens acc =
      match tokens with
      | [] -> acc
      | '>' :: rest -> loop rest (Move 1 :: acc)
      | '<' :: rest -> loop rest (Move (-1) :: acc)
      | '+' :: rest -> loop rest (Add 1 :: acc)
      | '-' :: rest -> loop rest (Add (-1) :: acc)
      | '.' :: rest -> loop rest (Output :: acc)
      | ',' :: rest -> loop rest (Input :: acc)
      | '[' :: rest ->
          let sublist, rest = build_loop tokens in
          let cond = build_ast sublist in
          loop rest ((Loop cond) :: acc)
      | ']' :: rest -> failwith "Close should have been consumed by build_loop"
      | _ :: rest -> loop rest acc
    in
    List.rev (loop tokens [])

Je n’ai pas cité la fonction build_loop pour des raisons de place, mais elle est disponible dans le source complet.

Interprétation dans une machine virtuelle basique, avec sa mémoire fixe et son unique pointeur

Voilà notre arbre d’opérations, il nous reste à l’exécuter.

On utilise une “machine virtuelle”, avec sa mémoire et son pointeur :

  let memory = Array.make 30_000 0
  let pointer = ref 0

Par simplification, la mémoire est limitée a 30000 cellules, sous forme de tableau plutôt que de ruban.

Les fonctions de base, qui correspondent aux opérations de BF :

  let move i = pointer := !pointer + i
 
  let add i = memory.(!pointer) <- memory.(!pointer) + i
 
  let output () = Printf.printf "%c%!" (char_of_int memory.(!pointer))
 
  let input () =
    let c = input_char stdin in
    memory.(!pointer) <- int_of_char c

Et enfin, l’exécution d’une liste d’opérations, obtenue à partir du source BF.

  let rec exec ast =
    let exec_node = function
      | Move i -> move i
      | Add i -> add i
      | Output -> output ()
      | Input -> input ()
      | Loop nodes ->
          while memory.(!pointer) <> 0 do
            exec nodes;
          done
    in
    List.iter exec_node ast

L’interprete basique est terminé. Il n’est pas particulièrement rapide, mais il fonctionne.

Voyons comment améliorer tout ca.

Optimisations simples

Il est possible de faire une optimisation simple, sans changer notre type opération et en conservant la structure du programme a l’identique.

Regroupement d’opérations similaires
Avec une traduction simple, “+++” devient [Add(1);Add(1),Add(1)]. En les regroupant, on peut n’avoir qu’une seule instruction, Add(3). La même chose est possible pour les instructions Move.

  let rec group = function
    | Move a :: Move b :: rest ->
        let lst = if a + b <> 0 then Move (a + b) :: rest else rest in
        group lst
    | Add a :: Add b :: rest ->
        let lst = if a + b <> 0 then Add (a + b) :: rest else rest in
        group lst
    | Loop a :: rest -> (Loop (group a)) :: (group rest)
    | other :: rest -> other :: (group rest)
    | [] -> []

Et tant qu’a faire, on se débrouille pour ne pas conserver de Add(0), ce qui serait un peu dommage.

Optimisations avancées

On a besoin d’ajouter un type macro, et un constructeur Macro au type “operation” défini précédemment

  type macro =
    | Set of int * int
    | AddMultToCell of int * int
    | AddMultToCell2 of int * int * int
    | CopyMultToCell of int * int
    | AddTo of int * int
 
  type operation =
     ...
     | Macro of macro

Voici ce qu’elles représentent :

Les programmes BrainFuck contiennent fréquemment des séquences similaires, que nous allons remplacer par ces macros.

Remplacement de boucles courantes par des macros

Commençons par les boucles. Celles-ci sont :

Passer de la boucle a sa signification sémantique, puis sa macro, n’est pas forcément évident.
Si vous ne voyez pas le lien entre la boucle et sa description, ca peut valoir le coup de creuser.

Une fois la relation entre les opération brainfuck et ce que le programme essaye d’accomplir établie, on peut enfin les remplacer par nos macros.

  let rec unroll ast =
    let replace = function
      | [Add (-1)] -> Macro (Set (0, 0))
      | [Move a; Add n; Move b; Add (-1)]
      when a = - b -> Macro (AddMultToCell (n, a))
      | [Move a; Add n1; Move b; Add n2; Move c; Add (-1)]
      when a + b = - c && n1 = n2 -> Macro (AddMultToCell2 (n1, a, a + b))
      | [Macro (Set (n, i)); Add (-1)] -> Loop [Macro (Set (n, i)); Macro (Set (0, 0))]
      | other -> Loop (unroll other)
    in
    match ast with
    | Loop ops :: rest -> replace ops :: unroll rest
    | other :: rest -> other :: (unroll rest)
    | [] -> []

Exécution directe, sans déplacement préalable
C’est bon pour les boucles, mais il reste d’autres séquences qu’on peut réduire.

On retrouve souvent la séquence [Move i, Action, Move -i]. Si on peut le remplacer par une action distante, on gagne deux déplacements.

  let in_place ast =
    let rec loop = function
      | Move i :: Add n :: Move j :: rest
        when i = - j -> Macro (AddTo (n, i)) :: loop rest
      | Move i :: Add n :: Move j :: rest -> 
        Macro (AddTo (n, i)) :: loop (Move (i+j) :: rest)
      | Move i :: Macro (Set (n, j)) :: Move k :: rest 
        when i = -k -> Macro (Set (n, i)) :: loop rest
      | Loop ops :: rest -> Loop (loop ops) :: loop rest
      | other :: rest -> other :: loop rest
      | [] -> []
    in loop ast

Et voila le travail.

Retour sur les regroupements
On avait déjà regroupé les Add et Move (c’était notre première optimisation).
Il est aussi possible de regrouper les opérations impliquant nos macros, dans une deuxième passe.

  let rec group = function
    ...
    | Add a :: Macro (Set (n, 0)) :: rest -> group (Macro (Set (n, 0)) :: rest)
    | Macro (Set (_, i)) :: Macro (Set (n, j)) :: rest 
      when i = j -> group (Macro (Set (n, j)) :: rest)
    | Macro (Set (n, 0)) :: Add a :: rest -> group (Macro (Set (n+a, 0)) :: rest)
    ...

Et notre optimisation va s’arreter ici. Il reste possible de faire d’autres macros pour d’autres séquences communes, mais cela n’apporterait pas grand chose d’un point de vue pédagogique.

Le résultat

Le code complet de l’interpreteur.
Le programme benchmark, qui calcule des nombres premiers : prime.bf

Sans optimisation

$ time (echo 99 | ./brainfuck.native prime.bf)
Primes up to: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

real	0m1.871s
user	0m1.868s
sys	0m0.000s

Avec optimisations

$ time (echo 99 | ./brainfuck.native -optimize prime.bf)
Primes up to: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

real	0m0.064s
user	0m0.056s
sys	0m0.004s

En gros, ca va 30x plus vite. Si seulement tout pouvait s’optimiser aussi facilement !

A vous de jouer

Grace au projet js_of_ocaml, j’ai pu porter le compilateur en javascript. Il est utilisable ici.

Développement brainfuck, ocaml