Brainfuck

[fran.b]

Allez, voilà de la programmation qui estune bonne initiation au perl , Que font les programmes suivants en brainfuck? (PS: pas la peine de chercher sur google, c’est de la production perso…)

et

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

[ricardo]

[fran.b]

[quote=“ricardo”]0[/quote]Non, non… http://fr.wikipedia.org/wiki/Brainfuck sinon, c’est amusant, Wikipedia donne des macros pour programmer classiquement via des variables numérotées alors que je me suis plutôt orienté sur des manipulations de pile type Forth ou langage HP48…

[mattotop]

Je suis flemmard.
Alors j’ai bêtement suivi le lien vers un compiateur fourni dans la page wikipedia:
savannah.nongnu.org/projects/libbf/
Sauf que:
download.savannah.nongnu.org/releases/libbf/
donc j’ai cherché un peu moins loin (toujours la flemme)

[code]roc@roc:~/.wine/drive_c/windows/system32$ aptitude search libbf
v libbfd-dev -
roc@roc:~/.wine/drive_c/windows/system32$ aptitude show libbfd-dev
Pas de version courante ou candidate trouvée pour libbfd-dev
Paquet : libbfd-dev
État: n’est pas un paquet réel
Fourni par : binutils-dev
roc@roc:~/.wine/drive_c/windows/system32$ aptitude search fuck
v libacme-brainfuck-perl -
roc@roc:~/.wine/drive_c/windows/system32$ aptitude show libacme-brainfuck-perl
Pas de version courante ou candidate trouvée pour libacme-brainfuck-perl
Paquet : libacme-brainfuck-perl
État: n’est pas un paquet réel
Fourni par : libacme-brainfck-perl
roc@roc:~/.wine/drive_c/windows/system32$ aptitude show libacme-brainfck-perl
Paquet : libacme-brainfck-perl
État: non installé
Version : 1.1.1
Priorité : optionnel
Section : interpreters
Responsable : Jaldhar H. Vyas jaldhar@debian.org
Taille décompressée : 94,2k
Dépend: perl (>= 5.6.0-16)
Fournit: libacme-brainfuck-perl
Description : Embed Brainfck in your perl code
Brainfck (yes, there is a u there.) is about the tiniest Turing-complete programming language you can get. A language is Turing-complete if it can model
the operations of a Turing machine–an abstract model of a computer defined by the British mathematician Alan Turing in 1936. A Turing machine consists
only of an endless sequence of memory cells and a pointer to one particular memory cell. Yet it is theoretically capable of performing any computation.
This module will allow you to mix Brainf*ck with your perl code.

Marqueurs: devel::lang:perl, devel::library, implemented-in::perl, role::app-data, role::devel-lib
[/code]Donc maintenant, je laisse à un mongueur nous faire ça en une ligne (toujours ma flemme).

[Yoko]

J’ai adoré programmer sur machine de Turing (mais sur papier helas)
Je trouve tout de même bizarre de voir du code pour Turing en procédurale.

[fran.b]

Machine Brainfuck en Caml

[code]type mot = BD | BG | Bp | Bm | Bifnotzero | Belse | Bget | Bput;;

let rec cherche_fi = function
| Belse::suite -> suite
| _::suite -> cherche_fi suite;;

let rec etape ruban_gauche mot ruban_droit pile instruction =
match ruban_gauche,mot,ruban_droit,pile,instruction with
| ,,,,[] -> (ruban_gauche,mot,ruban_droit)
(* décalage à droite )
| ,a,[],,(BD::suite) -> etape (a::ruban_gauche) 0 [] pile suite
| ,a,(b::p),,(BD::suite) -> etape (a::ruban_gauche) b p pile suite
( décalage à gauche )
| [],a,,,(BG::suite) -> etape [] 0 (a::ruban_droit) pile suite
| (b::p),a,,,(BG::suite) -> etape p b (a::ruban_droit) pile suite
( addition et soustraction )
| ,,,,(Bp::suite) -> etape ruban_gauche (mot+1) ruban_droit pile suite
| ,,,,(Bm::suite) -> etape ruban_gauche (mot-1) ruban_droit pile suite
( Impression )
| ,,,,(Bput::suite) -> ((print_int mot);print_newline ();(etape ruban_gauche mot ruban_droit pile suite))
( Lecture )
| ,,,,(Bget::suite) -> etape ruban_gauche ((print_string “->”); read_int ()) ruban_droit pile suite
( Crochet ouvrant )
| ,0,,,(Bifnotzero::suite) -> etape ruban_gauche mot ruban_droit pile (cherche_fi suite)
| ,,,_,(Bifnotzero::suite) -> etape ruban_gauche mot ruban_droit (suite::pile) suite
( crochet fermant *)
| ,0,,,(Belse::suite) -> etape ruban_gauche mot ruban_droit (tl pile) suite
| ,,,,(Belse::) -> etape ruban_gauche mot ruban_droit pile (hd pile)

;;

let transfo = function
| > -> BD
| < -> BG
| + -> Bp
| - -> Bm
| , -> Bget
| . -> Bput
| [ -> Bifnotzero
| ] -> Belse;;

let b_to_list s =
let rec boucle l = function
| (-1) -> l
| i -> (boucle ((transfo s.[i])::l) (i-1))
in (boucle [] ((string_length s)-1));;

let execute pg pd s = let rbg,m,rbd = etape (tl (rev pg)) (hd (rev pg)) pd [] (b_to_list s) in (rev (m::rbg)),rbd;;[/code]

Un exemple:

[quote]#execute [6;7] [] “[->+>+<<]>>[-<<+>>]<”;;

• : int list * int list = [6; 7; 7], [0]
  #[/quote]
  execute prend le ruban à gauche, à droite et le programme. Ainsi, ici, le ruban est

…,0,0,0,6,7,0,0,0… avec le pointeur sur 7 et la sortie est
…,0,0,0,6,7,7,0,0,0… avec le pointeur sur 7 (le programme double le sommet de la «pile»). Plus simple que Perl, ça

[usinagaz]

waouah (rien compris) ça porte bien son nom ce truc là

[ymer]

C’est clair!

Tu sais vraiment te servir de ça fran ??? J’avais encore jamais entendu parler de ce langage avant de lire le topic que mattotop m’a donné, où tu en parles d’ailleur.

Je crois pas avoir utilisé un seul programme codé en “brainfuck”.

[mattotop]

c’est parceque c’est ce qu’on appelle une “preuve de concept”: un truc qui ne sert à rien d’autre qu’à montrer qu’on peut faire en vrai un truc théorique qu’on a imaginé.

[Yoko]

Je dirais que c’est une manière de programmer comme si on était sur l’ancestrale machine de Turing juste pour le fun

[fran.b]

Ça a également un intérêt en terme de complexité: Par exemple, pour le tri, on suppose souvent que pour une liste de longueur n, les listes sont équiprobables -chaque liste a autant de chances d’arriver qu’une autre liste- et un tri comme le tri par pivot paraît très efficace (coût en O(ln(n)) par élément trié soit O(n.ln(n))). Dans la pratique, ce tri est souvent mauvais (coût en O(n) par élément soit O(n²)) car la plupart des listes à triées sont quasiment triées d’emblée et dans ce cas, ce tri est mauvais. Si on définit le poids d’une liste comme la longueur du plus petit programme en brainfuck capable de fabriquer la liste et que la probabilité d’apparition d’une liste est inversement proportionnel à son poids, le coût du tri par pivot devient en O(n²).

Dans la pratique, pour trouver le poids d’un ensemble de données, on regarde la taille de ces données une fois compressée par gzip, c’est une excellente approximation.

Pour programmer en brainfuck, il suffit de refaire les opérations élemtaires d’une pile:

[code](* …,A -> …,0,A,A *)
let du0 = “[->+>+<<]>>”;;

(* …,0,A,A -> …,A,A *)
let ho0 = “[-<<+>>]<”;;

(* …,A -> …,A,A )
let dup = du0^ho0;;
( du = “[->+>+<<]>>[-<<+>>]<” *)

(* …,B,A -> …,B *)
let drop = “[-]<”;;

(* …,A,B -> …,A,B,A *)
let dup2 = “<[->>+>+<<<]>>>[-<<<+>>>]<”;;

(* pop *)
let pop = “[-]<”;;

(* …,A,B -> …,B *)
let pop2 = “<[-]>[-<+>]<”;;

(* …,A,B,C -> …,B,C *)
let pop3 = “<<[-]>[-<+>]>[-<+>]<”;;

(* …,A,B -> …,B,A )
let swap = dup2^pop3;;
( swap="<[->>+>+<<<]>>>[-<<<+>>>]<<<[-]>[-<+>]>[-<+>]<" *)

(* …,A,B -> …,A+B *)

let sum = “[-<+>]<”;;

(* …,A,B -> …,A*B )
let mult = “>”^"<<[->>"^dup2^sum^"<<]>>"^pop2^pop2;;
( mult = “><<[->><[->>+>+<<<]>>>[-<<<+>>>]<[-<+>]<<<]>><[-]>[-<+>]<<[-]>[-<+>]<” *)

…
[/code]

etc… Avec ça, en faisant comme sur une HP48 ou comme en Forth, on fait un programme très facilement. Le premier calcule factoriel et le second est la suite de Fibonacci. On peut même faire un compilateur Langage élémentaire -> Brainfuck (ça aurait de la gueule )

[mattotop]

quote=“fran.b” Langage élémentaire (…)[/quote]C’est quoi ?

[fran.b]

quote=“fran.b” Langage élémentaire (…)[/quote]C’est quoi ?

Langage basique genre BASIC justement, typiquement ce qu’on utilise pour écrie un algorithme sommaire: variables, tableaux, controle de flux, c’ets tout.

[mattotop]

Ah, ben dans ce cas, il y a les briques de transcodeur brainfuck -> c, sur le site wikipedia, qui sont données pour la comprehension.

[fran.b]

Oui, je m’en suis aperçu quand j’ai donné le lien. C’est étonnant parce que par réflexe, je me suis plutôt orienté sur un langage type manipulation de pile plus adapté à mon avis à une transformation en Brainfuck (leur macro to() est catastrophique en terme de longueur…)