coucou747

programmez en brainfuck grace a ocaml

Le brainfuck

Le brainfuck est un langage de programmation (oui oui !) qui est _vraiment_ minimaliste. Ce langage ne comporte que huit instructions. Elles permettent chacune de faire une operation tres limitee. Le nombre d'instruction etait peu eleve, il est normal que les instructions soient de bas niveau pour qu'on puisse quand meme realiser plein de choses avec.

Ce langage est turing complet, c'est donc un langage de programmation qui permet de tout faire (ce qui n'est pas evident quand on regarde la tete du langage.)

Notre langage est constitue des 8 instructions suivantes :
< > + - [ ] . ,

ces instructions agissent sur la memoire ou sur le flot d'instructions. la memoire est un immense ruban infini, et deroulable dans les deux sens.

    --|----|----|----|----|----|----|----|----|----|--
      | -4 | -3 | -2 | -1 | 0  | 1  | 2  | 3  | 4  |
    --|----|----|----|----|----|----|----|----|----|--
                                 ^

ici, la memoire avec les indices (puisqu'on deroule dans les deux sens, ils peuvent etre negatifs.)

dans chaque case, on a une valeur comprise entre 0 et 255

on a aussi un "pointeur" vers une case, nous nommerons alors cette case, la case courrante. Dans l'exemple, le pointeur etait sur le 1.

Les instructions "<" et ">" permettent de pointer sur la case suivante ou precedente.
Les instructions "+" et "-" permettent d'incrementer ou de decrementer la valeur d'une case. Les valeurs. Comme les valeurs vont de 0 a 255, lorsque l'on tente d'incrementer 255, on retombe sur 0 ; inversement, decrementer 0 nous donne 255.

les deux instructions "[" et "]" marquent une boucle : tant que la ou on pointe est non null, effectuer les operations contenues dans la boucle.

Il nous reste deux instructions : "." et ",", qui sont toutes deux les operations d'entrees sorties elementaires. "." affiche le caractere ascii qui correspond a la valeur de la case courrante. "," demande un caractere au clavier, et inscrit son code ascii dans la case courrante.

Vous remarquerez qu'il est tres difficile d'effectuer un programme ave aussi peu d'instructions, c'est pourquoi, si des humains ont du mal a ecrire du brainfuck, on peut se poser la question suivante :

Comment faire un programme qui ecrit un code brainfuck ?

En ocaml, on peut representer un code brainfuck sous forme d'une liste de "brainfuck", avec "brainfuck" defini comme ci dessous :

type brainfuck =
  Inc | Dec |
  Next | Prev |
  While of brainfuck list |
  Input | Print;;

On peut alors faire un brainfuck etendu pour "compresser" certaines instructions. C'est juste une question de facilite d'ecriture, ce nouveau type ne permet rien d'extra-ordinaire.

type extendedBrainfuck =
  W of extendedBrainfuck list |
  Bf of brainfuck |
  Add of int |
  Sub of int |
  Jmp of int;;

Ce nouveau type nous permet de compresser : [Next;Next;Next;Next] en [Jmp(4)], ce qui est deja plus pratique a ecrire. W permet de faire une boucle. Bien evidement, cette structure ne suffit pas pour effectuer des operations interessantes, je vous propose celle-ci :

type lang =
  WhileVar of string * (lang list) |
  AddVar of string * int |
  SubVar of string * int |
  PrintVar of string|
  InputVar of string|
  Call of fonction * string list
and fonction = string list * string list * lang list;;

En fait, on devrait dire procedure et pas fonction, mais c'est un detail. Le systeme de variables est simple : on affecte un nom par "case memoire". Nous verrons plus loin la distribution des variables.

•   Pour ajouter un nombre (pour l'exemple, ajoutons 42) a une variable, que nous nommerons "foo", on fait : AddVar("foo", 42)
•   Pour soustraire un nombre a une variable, on fait : SubVar("foo", 42)
•   Pour afficher le contenu du variable "foo", on fait : PrintVar("foo")
•   Pour l'input sur la variable "foo" : InputVar("foo")
•   Pour faire une boucle : tant que la variable "foo" est non nulle, on execute le code : "code" : While ("foo", code)
•   Pour appeller une fonction, on fait Call (fonction, parametres)

Les fonctions sont en fait "inlinees" dans le code (comme des macros en C.), ce qui veut dire qu'on ne peut pas faire de fonctions recursives.

Pour definir une variable a 0 en brainfuck, on fait :

[-]

Notre premiere macro sera celle qui definit un nombre a 0 :

let zerofunc = ( ["x"], [], (*x=0*)
  (WhileVar ("x", [SubVar ("x", 1)] ))::[]);;

le ["x"], correspond a la liste des parametres que l'on peut passer a la fonction zerofunc. Bien evidement, ces parametres sont passes par reference. le [] correspond a la liste des variables locales. le reste, c'est le code de la fonction zerofunc : (WhileVar ("x", [SubVar ("x", 1)] ))::[])

Comme vous pouvez l'appercevoir, en ocaml, zerofunc n'est en fait pas une fonction, c'est une valeur comme les autres... de type : string list * string list * lang list

De la meme facon, on peut definir les fonctions suivantes :

let plusEgalZero = ( ["x";"y"], [], (* x+=y; y=0*) ...
let copy = ( ["x";"y"], ["z"], (*y=x*) ...
let plus = ( ["x";"y"], ["z"], (*x=x+y*) ...
let switch = ( ["x";"y"], ["z"], (*x=x+y*) ...
let affChiffre = (["x"], [], ...

Pour commencer, nous nous arreterons la pour les fonctions "simples"

Comme je le disais plus haut, pour ocaml, ce ne sont pas des fonctions, mais des valeurs, il semble donc "possible", voir meme interessant de faire des fonctions qui renverraient ce type de valeur (un tout petit semblant de curyfication) Un exemple simple : j'aimerais bien pouvoir effectuer l'operation : Call ( afficher_char '\n', []) qui m'afficherait un retour a la ligne.

pour faire ca, on fait une fonction qui prend en parametre "c", et qui renvoie une macro qui ne prend aucun parametre, qui utilise "x" comme variable temporaire, ensuite, le code consiste a mettre x a : int_of_char c, et a afficher x.

let printchar c = ([], ["x"],
  (Call (zerofunc, ["x"]))::(AddVar("x", int_of_char c))::(PrintVar "x")::[]
);;

de la meme facon, on peut faire un "set"

let setVal v = (["x"], [],
  (Call (zerofunc, ["x"]))::(AddVar("x", v))::[]
);;

Bon, on commence a pouvoir faire generer du brainfuck :)

Exemple : le code suivant nous renvoie une fonction qui calcule les 5 premiers nombres de la suite de fibonaci.

let funcmain = ( [], ["n";"a";"b"],
  (AddVar("n", 5))
  ::(AddVar("b", 1))
  ::(WhileVar ("n",
    SubVar ("n", 1)
    ::(Call (plus, ["a";"b"]) )
    ::(Call (switch, ["a";"b"]) )
    ::(Call (affChiffre, ["a"]))
    ::(Call (printchar '\n', []))
    ::[] ))
  ::[]
);;

Autre Exemple : le code suivant nous renvoie une fonction qui calcule les 4 premiers nombres triangulaires.

let funcmain = ( [], ["n";"a";"b"],
  AddVar("n", 4)
  ::AddVar("b", 1)
  ::WhileVar ("n",
    SubVar ("n", 1)
    ::AddVar ("b", 1)
    ::Call (plus, ["a";"b"])
    ::Call (affChiffre, ["a"])
    ::Call (printchar '\n', [])
    ::[] )
  ::[]
);;

Dans les deux exemples precedents, on se limite a 4 ou 5 nombres, parce-que si on cherche plus loin, alors les resultats font plus de deux chiffres, et gerer des nombres a plusieurs chiffres, c'est pas un probleme trivial en brainfuck.

On va tenter de faire une fonction pour faire un "if variable=constante then ... else ...", notre fonction prendra trois parametres : la constante, le code a executer "si egal", et le code a executer "si different". On appellera ces variables : valeur, statement_if, statement_else. Ensuite, la macro prendra la variable en parametre, elle verifiera si la variable est egal a la valeur, et executera les statement, selon les choix.

Le principe est simple : on prend trois variables temporaires : "tmp", "e", et "ne". Au debut, on definit tmp=x, ensuite, on soustrait valeur a tmp. Si x = valeur, alors a ce moment la, on obtient : tmp=0, sinon, on a tmp != 0. Au debut, on doit alors faire ceci : ne = 1, e=0, lancer une boucle sur tmp n'exexute le contenu de la boucle que si x = valeur. on effectue alors la boucle suivante :

WhileVar("tmp",
  Call(zerofunc, ["tmp"])
  ::AddVar("e", 1)
  ::SubVar("ne", 0)
  ::[]
)

le zerofunc permet de ne faire "qu'un tour" de boucle. Ensuite, mes definitions de "e" et "ne" permettent d'avoir :

Si x = valeur
 e = 1
 ne = 0
Sinon
 e = 0
 ne = 1
FinSi

ce qui permet de faire une boucle sur la variable "e", et executer dedans : SubVar("e", 1) et statement_if, puis une boucle sur la variable "ne", et effectuer dedans SubVar("ne", 1) et statement_else.

C'est le principe simplifie de la fonction que j'ai dans mon code. Au final, on a des parametres a passer a statement_if, et statement_else.

au final, ca donne ca :

let ifEqual valeur params statement_if statement_else = ("x"::params, ["tmp";"e";"ne"],
  Call (copy, ["x";"tmp"])
  ::SubVar("tmp", valeur)
  ::Call( setVal 1, ["e"])
  ::Call( setVal 0, ["ne"])
  ::WhileVar ("tmp", (* not egal *)
    Call (zerofunc, ["tmp"])
    ::SubVar("e", 1)
    ::AddVar("ne", 1)
    ::[] )
  ::WhileVar ("e",
    SubVar("e", 1) :: statement_if )
  ::WhileVar ("ne",
    SubVar("ne", 1) :: statement_else )
  ::[]
);;

Bon... Pour continuer on peut tenter de faire des operations sur plusieurs octets. Pour ca, on balade des listes en parametres.

implementer une gestion des listes, c'est malheureusement trop complique, heureusement, ocaml a deja ses listes, alors contentons nous d'appeller nos variables avec un prefixe et un indice.
le nom du n-eme element d'une liste sera donne ainsi :

let input prefix n = prefix^(string_of_int n);;

voici la fonction qui nous donne la liste :

let liste_input prefix i =
  let rec f li n =
    if n = i then li
    else f ((input prefix (i-n-1)) :: li) (n+1)
  in f [] 0;;

parfois, on voudra passer un, deux, trois, etc... gros nombres a une fonction, et on aura donc besoin d'une fonction qui nous renvoie :

["a_0";"a_1";..."a_5"..."b_0"..."c_0"..."d_5"]

la voici :

let paramListe i li = List.flatten (List.map (fun x -> liste_input x i) li );;

vous pouvez la tester avec le code suivant :

paramListe 4 ["a_";"b_"];;

On a plusieurs fonctions a faire du meme type : tout mettre a 0 ou afficher un gros nombre, ce sont deux operations du meme type : on effectue une operation simple sur chaque chiffre ; switch et copy aussi sont du meme type : on effectue une operation simple (Call(switch, ["a";"b"]) ou bien Call(zerofunc, ["a"])) sur chaque couple de chiffre (en formant les couples ainsi : le premier chiffre de a, avec le premier chiffre de b, etc...)

On definit ces fonctions assez facilement :

type 'a transfo = ('a -> lang) -> ('a list) -> lang list;;
let multi_param_each_ (map:(string transfo)) f i =
  let liste = liste_input "a_" i
  in ( liste, [], map f liste );;

let multi_param_each_rev = multi_param_each_ List.rev_map;;
let multi_param_each = multi_param_each_ List.map;;

let deux_multi_param_each_ (map:((string*string) transfo)) f i =
  let lista = liste_input "a_" i and listb = liste_input "b_" i
  in ( (List.append lista listb), [], map f (List.combine lista listb) );;

let deux_multi_param_each_rev = deux_multi_param_each_ List.rev_map;;
let deux_multi_param_each = deux_multi_param_each_ List.map;;

let big_int_switch = deux_multi_param_each (fun (a, b) -> Call (switch, [a;b]) );; (* a <=> b*)
let big_int_copy = deux_multi_param_each (fun (a, b) -> Call (copy, [a;b]) );; (* b = a *)
let big_int_aff = multi_param_each_rev (fun (a) -> Call (affChiffre, ) );; (* aff a *)
let big_int_zero = multi_param_each (fun (a) -> Call (zerofunc, ) );; (* a = 0 *)

Pour la suite, on ajoutera une fonction big_int_plus_un, et une fonction big_int_plus, je vais les detailler plus bas. Nos nombres ont une taille fixee a la compilation. voici cette taille :

let size_big_int = 15;;

pour plus de simplicite, on applique nos fonctions, on peut ensuite coder plus facilement.

let big_int_switch = big_int_switch size_big_int;;
let paramListe = paramListe size_big_int;;
let big_num_plus_un = big_num_plus_un size_big_int;;
let big_num_plus = big_num_plus size_big_int;;
let big_int_aff = big_int_aff size_big_int;;

En brainfuck, ajouter un est une operation non triviale sur un nombre a plusieurs chiffres. Le principe est le suivant : on ajoute 1 au dernier chiffre ; si le dernier chiffre est egal a 10, alors on le met a 0, et on appelle +1 sur une sous-partie du nombre. Notre fonction est donc recursive, mais il est quand meme possible de l'inliner (paradoxallement) c'est comme si on definissait : "big_num_plus_un_taillenombre=4", puis "big_num_plus_un_taillenombre=3", puis "big_num_plus_un_taillenombre=2" puis "big_num_plus_un_taillenombre=1", puis "big_num_plus_un_taillenombre=0"

voici le code de la fonction +1

(* a = a + 1 *)
let rec big_num_plus_un i =
  if i=0 then ( [], [], [] ) else
  let liste = liste_input "a_" i
  in let code =
  AddVar("a_0", 1)
  ::Call (ifEqual 10 liste (
    SubVar("a_0", 10)
    :: Call (big_num_plus_un (i-1), List.tl liste)
    ::[]
    ) [], "a_0"::liste)
  ::[]
  in ( liste, [], code );;

et un exemple d'application : compter jusqu'a 15

let funcmain = ( [], "n"::(paramListe ["a_"]),
  (AddVar("n", 15))
  ::(WhileVar ("n",
    SubVar ("n", 1)
    ::(Call (big_num_plus_un , paramListe ["a_"]) )
    ::(Call (big_int_aff, paramListe ["a_"]))
    ::(Call (printchar '\n', []))
    ::[] ))
  ::[]
);;

la fonction plus repose sur le meme principe, je ne la detaillerais pas.

let rec big_num_plus i = (* a = a+b*)
  if i=0 then ( [], [], [] ) else
  let lista = liste_input "a_" i and listb = liste_input "b_" i and listc = liste_input "c_" i
  in let code =
  Call (big_int_copy i, List.append listb listc)
  ::WhileVar ("c_0",
    SubVar("c_0", 1)
    ::Call (big_num_plus_un i, lista)
    ::[] )
  ::Call (big_num_plus (i-1), List.append (List.tl lista) (List.tl listb))
  ::[]
  in ( List.append lista listb, listc, code );;

voici un fibonaci.

let funcmain = ( [], "n"::(paramListe ["a_";"b_"]),
  (AddVar("n", 100))
  ::(AddVar("b_0", 1))
  ::(WhileVar ("n",
    SubVar ("n", 1)
    ::(Call (big_num_plus, paramListe ["a_";"b_"]) )
    ::(Call (big_int_switch, paramListe ["a_";"b_"]) )
    ::(Call (big_int_aff, paramListe ["a_"]))
    ::(Call (printchar '\n', []))
    ::[] ))
  ::[]
);;

avec des nombres de 15 chiffres, on arrive a 1.2 mo de code brainfuck, pour 3700 lignes de code... En modifiant legerement le "compilateur" pour qu'il allege le code brainfuck, on arrive a 200 ko de code, et toujours 3700 lignes. Le temps de compilation se trouve par contre largement augmente.

max@max-laptop:~$ time OCAMLRUNPARAM="b" ./a.out > fibonaci.bf

real    3m51.838s
user    1m54.143s
sys     0m0.620s

ca commence a faire beaucoup pour un simple fibonaci.