Brainfuck

Brainfuck

Tipus	llenguatge de programació esotèric, turing tarpit i llenguatge de programació
Data de creació	1993
Desenvolupador	Urban Müller
Epònim	cervell i fuck
Paradigma de programació	programació esotèrica i llenguatge imperatiu
Dialecte de	P′′
Influenciat per	P′′ i FALSE
Extensió dels fitxers	b i bf
Etiqueta d'Stack Exchange	Etiqueta
Pàgina web	brainfuck.org

Brainfuck és un llenguatge de programació esotèric creat l'any 1993 per Urban Müller.^[1]

Destacat per la seva mínima expressió, el llenguatge consta només de vuit instruccions simples, un punter de dades i un punter d'instruccions (comptador). Tot i que és completament Turing complet, no està pensat per a un ús pràctic, sinó per desafiar i divertir els programadors. Brainfuck només requereix un per dividir les ordres en passos microscòpics.

El nom del llenguatge és una referència al terme argot anglès brainfuck, que fa referència a coses tan complicades o inusuals que superen els límits de la comprensió, ja que no estava pensat ni fet per dissenyar programari real sinó per desafiar els límits de la programació informàtica.

Història

L'any 1992, Urban Müller, un estudiant de física suís, es va fer càrrec d'un petit arxiu en línia per al programari Amiga.^[2] L'arxiu es va fer més popular i aviat es va copiar arreu del món. Actualment, és l'arxiu Amiga més gran del món, conegut com Aminet.

Müller va dissenyar Brainfuck amb l'objectiu d'implementar el compilador més petit possible,^[3] inspirat en el compilador de 1024 bytes per al llenguatge de programació FALSE.^[4] El compilador original de Müller es va implementar en llenguatge màquina i es va compilar en binari amb una mida de 296 bytes. Va carregar el primer compilador de Brainfuck a Aminet l'any 1993. El programa venia amb un fitxer Readme, que descrivia breument el llenguatge, i desafiava el lector «Who can program anything useful with it? :)» (Qui pot programar alguna cosa útil amb ell? :)). Müller també va incloure un intèrpret i alguns exemples força elaborats. Una segona versió del compilador utilitzava només 240 bytes.^[5] Actualment hi ha molts compiladors Brainfuck a la xarxa.

A mesura que Aminet va créixer, el compilador es va fer popular entre la comunitat Amiga, i amb el temps es va implementar per a altres plataformes.

P′′: el «llenguatge pare» formal de Brainfuck

Excepte les seves dues instruccions d'E/S, Brainfuck és una variació menor del llenguatge de programació formal P′′ creat per Corrado Böhm el 1964, que al seu torn es basa explícitament en la màquina de Turing. De fet, utilitzant sis símbols equivalents a les respectives ordres de Brainfuck +, -, <, >, [, ], Böhm va proporcionar un programa explícit per a cadascuna de les funcions bàsiques que juntes serveixen per calcular qualsevol funció computable. Així que els primers programes «Brainfuck» apareixen al document de Böhm de 1964, i eren suficients per demostrar el Turing complet.

Infinite Abacus: el llenguatge «avi» de Brainfuck

Joachim Lambek va introduir una versió amb adreça de memòria explícita (en lloc de moviments relatius en una pila), i un salt condicional (en lloc de bucles), el 1961 amb el nom d'Infinite Abacus (Àbac Infinit),^[6] que consta d'un nombre infinit de cel·les i dues instruccions:

• X+ (incrementa la cel·la X)
• X- else jump T (disminueix X si és positiu, sinó salta a T)

Ell demostra que Infinite Abacus pot calcular qualsevol funció recursiva computable programant el conjunt de Kleene de la funció μ-recursiva bàsica.

La seva màquina va ser simulada pel càlcul de modelatge de màquines de Melzac^[7] mitjançant l'aritmètica (en lloc de la lògica binària) imitant un operador humà movent còdols sobre un àbac, d'aquí el requisit que tots els nombres han de ser positius. L'ordinador de Melzac, amb instruccions equivalents a les de l'Infinite Abacus, ofereix programes per a la multiplicació, m.c.d., enèsim nombre primer, representació en base b, ordenació per magnitud, i mostra com simular una màquina de Turing arbitrària.

Disseny del llenguatge

El llenguatge consta de vuit instruccions, que s'enumeren a continuació. Un programa de brainfuck és una seqüència d'aquestes instruccions, possiblement intercalades amb altres caràcters (que s'ignoren). Les instruccions s'executen seqüencialment, amb algunes excepcions: un punter d'instrucció comença a la primera instrucció, executa la instrucció que apunta, i després normalment avança a la següent instrucció. El programa finalitza quan el punter d'instrucció passa més enllà de l'última instrucció.

El llenguatge brainfuck utilitza un model de màquina senzill que consisteix en el programa i el punter d'instruccions, així com una matriu unidimensional d'almenys 30.000 cel·les de bytes inicialitzades a zero; un punter de dades mòbil (inicialitzat per apuntar al byte més a l'esquerra de la matriu); i dos fluxos de bytes per a l'entrada i la sortida (la majoria de vegades connectats a un teclat i un monitor respectivament, i utilitzant la codificació de caràcters ASCII).

Instruccions

Les vuit instruccions del llenguatge consten cadascuna d'un sol caracter:

Caracter	Significat
>	incrementar el punter (per apuntar a la següent posició de la llista, a la dreta).
<	decrementar el punter (per apuntar a la següent posició de la llista, a l'esquerra).
+	increment (incrementar per 1) el byte on apunta el punter.
-	decrement (decrementar per 1) el byte on apunta el punter.
.	Escriu el byte apuntat al flux de sortida.
,	Llegeix un byte del flux d'entrada i l'emmagatzema al byte apuntat.
[	Avança a la instrucció immediatament posterior al ] corresponent si el byte actualment apuntat és nul (si és 0).
]	Retrocedeix a la instrucció immediatament posterior al [ corresponent si el byte actualment apuntat no és nul (si és diferent de 0).

(Alternativament, la instrucció ] es pot traduir com un salt incondicional cap a l'instrucció [ corresponent, o viceversa; els programes es comportaran igual però s'executaran més lentament, a causa d'una doble cerca innecessària).

[ i ] coincideixen com solen fer els parèntesis: cada [ coincideix exactament amb un ] i viceversa, el [ arriba primer, i no hi pot haver cap [ o ] incomparable entre els dos.

Els programes de Brainfuck es poden traduir a C i Perl amb aquestes instruccions, suposant que ptr sigui unsigned char*. No obstant, tenen els seus propis traductors.

• 
  Codi font del traductor Brainfuck a C escrit en el dialecte Unix del compilador-compilador TMG (McIlroy, 1972). Visualitzat a Vim amb ressaltat de sintaxi.

En el cas de Lua, utilitza una variable i per indicar el punter i c és una taula com a representació de les cel·les; la inicialització d'aquestes variables seria: i, c = 0, {}.

Brainfuck	C	Perl	Lua
(inici de programa)	char array[30000] = {0}; char *ptr = array;		i, c = 0, {}
>	++ptr;	$pointer++;	i = i + 1
<	--ptr;	$pointer--;	i = i - 1
+	++*ptr;	$tape[$pointer]++;	c[i] = (c[i] or 0) + 1
-	--*ptr;	$tape[$pointer]--;	c[i] = (c[i] or 0) - 1
.	putchar(*ptr);	print chr$tape[$pointer];	io.write(string.char(c[i] or 0))
,	*ptr=getchar();	$tape[$pointer]=ord(<>);	c[i] = io.read():byte()
[	while (*ptr) {	while($tape[$pointer]){	while (c[i] or 0) ~= 0 do
]	}	}	end

Com el seu nom indica (fotedor de cervell), els programes Brainfuck solen ser difícils d'entendre. Això és en part perquè qualsevol tasca lleugerament complexa requereix una llarga seqüència d'ordres i en part perquè el text del programa no dona indicacions directes de l'estat del programa. Aquestes, així com la ineficiència de Brainfuck i les seves limitades capacitats d'entrada/sortida, són algunes de les raons per les quals no s'utilitza per a una programació seriosa. No obstant això, com qualsevol llenguatge complet de Turing, Brainfuck és teòricament capaç de calcular qualsevol funció computable o simular qualsevol altre model computacional, si se li dona accés a una quantitat il·limitada de memòria.^[8] S'han escrit una varietat de programes Brainfuck.^[9] Tot i que els programes Brainfuck, especialment els complicats, són difícils d'escriure, és bastant trivial escriure un intèrpret per a Brainfuck en un llenguatge més típic com el C per la seva senzillesa. Fins i tot existeixen intèrprets de Brainfuck escrits en el propi llenguatge Brainfuck.^[10][11]

Brainfuck és un exemple de l'anomenada tarpit de Turing: es pot utilitzar per escriure qualsevol programa, però no és pràctic fer-ho, perquè Brainfuck ofereix tan poca abstracció que els programes es fan molt llargs o complicats.

Exemples

Netejar posició

[-]

Aquesta simple porció de programa neteja la posició actual a zero, iterativament disminueix el seu valor fins que és zero, llavors surt del bucle i continua l'execució.

Bucle simple

,[.,]

Això és un bucle continu, pren text d'entrada (del teclat) i el copia a la sortida (la pantalla). Modifica la posició actual del punter. Només surt quan el valor ASCII zero entra pel teclat.

Aquesta versió fa el mateix però surt quan es prem la tecla Enter (ASCII 10) al teclat:

,----------[++++++++++.,----------]

entrada: Viquipèdia
sortida: Viquipèdia

Movent el punter

>,[.>,]

Una versió de l'anterior que mou el punter cada cop per desar tot el text entrat a la llista per ús futur.

Afegir

[->+<]

Això afegeix la posició actual (la deixa a zero, esborrant qualsevol informació anterior) a la propera.

Instruccions condicionals

,----------[----------------------.,----------]

Aquest codi converteix el text entrat en minúscules pel teclat, el converteix en majúscules i el mostra a la pantalla en prémer la tecla Enter.

Primer el caràcter entra fent servir el codi , i immediatament es resta 10 (la majoria d'implementacions de brainfuck, si no totes, fan servir 10 pel retorn) Si l'usuari ha premut la tecla Enter la instrucció condicional [ saltarà a la posició just després de ] perquè haurem tornat el primer byte a zero. El programa acabarà. Si el primer caràcter no era la tecla Enter assumim que és una minúscula i li restem 22, per un total de 32, que és la diferència entre una minúscula i la seva respectiva majúscula en ASCII.

Després mostrem per pantalla . i fem entrar el proper caràcter , restant-li 10 un altre cop, si no era 10 anirem a la primera posició del bucle i restarem altre cop 22. El programa acaba en prémer la tecla Enter perquè no hi ha més instruccions després.

entrada: viquipedia (+ tecla Enter)
sortida: VIQUIPEDIA

entrada: Viquipedia (+ tecla Enter)
sortida: 6IQUIPEDIA

Copiant un byte

(A partir d'aquest punt ens referirem als bytes de la llista com a [0], [1], [2]... successivament)

Brainfuck no inclou una instrucció per copiar bytes. Això ha de fer-se amb les instruccions de bucle. Moure un byte és simple si la destinació és zero (sempre ho és en iniciar el programa) però la posició inicial es perd, com hem vist abans. Així movem [0] a [1]:

[->+<]

Podríem restituir el valor de [0] si l'haguéssim copiat a dues posicions a la vegada. Per copiar [0] a [1] i [2] a la vegada faríem:

[->+>+<<]

Ara podem aprofitar això per restituir [0]. En resum, per copiar [0] a [1] fent servir [2] com espai de treball fem:

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

Hola món!

El programa següent imprimeix Hello World! i una nova línia a la pantalla:

[ Aquest programa imprimeix "Hello World!" i una nova línia a la pantalla. La longitud és de 106 caràcters d'ordres 
 actius. (No és el més curt),

 Aquest bucle és un "bucle de comentaris inicial", una manera senzilla d'afegir un comentari a un programa BF de manera
 que no us haureu de preocupar per cap caracter d'instruccions. Qualsevol caracter ".", ",", "+", "-", "<" i ">" són 
 simplement ignorats, els caràcters "[" i "]" només s'han d'equilibrar. Aquest bucle i les ordres que conté s'ignoren 
 perquè la cel·la actual el valor predeterminat és 0; el valor 0 fa que aquest bucle es salti.
]


++++++++ Estableix la cel·la #0 a 8
[
 >++++ Suma 4 a la cel·la #1; això sempre establirà la cel·la #1 a la 4
 [ ja que la cel·la serà esborrada pel bucle
 >++ Suma 2 a la cel·la #2
 >+++ Suma 3 a la cel·la #3
 >+++ Suma 3 a la cel·la #4
 >+ Suma 1 a la cel·la #5
 <<<<- Disminueix el comptador de bucles a la cel·la #1
 ] Bucle fins que la cel·la #1 sigui zero; el nombre d'iteracions és 4
 >+ Suma 1 a la cel·la #2
 >+ Suma 1 a la cel·la #3
 >- Resta 1 a la cel·la #4
 >>+ Suma 1 a la cel·la #6
 [<] Torna a la primera cel·la zero que trobi; això fa que la cel·la #1 sigui esborrada pel
 bucle anterior
 <- Disminueix el comptador de bucles a la cel·la #0
] Bucle fins que la cel·la #0 sigui zero; el nombre d'iteracions és 8

El resultat d'això és:
Cel·la : 0 1 2 3 4 5 6
Contingut: 0 0 72 104 88 32 8
Punter : ^

>>. La cel·la #2 té el valor 72 que és "H"
>---. Resta 3 de la cel·la #3 per obtenir 101, que és "e"
+++++++..+++. De la mateixa manera per a 'llo' de la cel·la #3
>>. La cel·la número 5 és 32 per a l'espai
<-. Resta 1 de la cel·la #4 per a 87 per donar una "W"
<. La cel·la núm. 3 s'ha establert en "o" des del final de "Hello"
+++.------.--------. Cel·la #3 per a "rl" i "d"
>>+. Suma 1 a la cel·la #5. Ens dona un signe d'exclamació
>++. I finalment una nova línia des de la cel·la #6

entrada: 
sortida: Hello World!

Per a la «llegibilitat», aquest codi s'ha repartit en moltes línies i s'han afegit espais en blanc i comentaris. Brainfuck ignora tots els caracters excepte les vuit instruccions +-<>[],. per tant, no cal una sintaxi especial per als comentaris (sempre que els comentaris no continguin els caràcters d'instrucció). El codi podria haver estat escrit com:

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

Suma de dos valors

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

Aquest programa suma dos nombres d'un sol dígit i el resultat només és correcte si també té un sol dígit:

entrada: 43
sortida: 7 (4 + 3 + 48 = 55; 7 en ASII)

entrada: 68
sortida: > (6 + 8 + 48 = 62; > en ASCII)

El primer nombre entra a [0] i li restem 48 per corregir-lo (ha entrat el codi ASCII, i aquests codis per als dígits 0-9 són 48-57). Això ho fem escrivint 6 en [1] i fent servir el primer bucle per restar-li 8 a [0] 6 vegades (aquest és el mètode normal per sumar o restar nombres llargs.). Després, el segon nombre entra en [1].

El proper bucle [<+>-] mou el segon nombre al primer tot afegint-los, i posat [1] a zero. En cada volta afegeix 1 a [0] i resta 1 a [1], quan [1] és zero el bucle surt. Després la tecla Enter entra a [1].

Es mou el punter altra volta a la posició [0] i es mostra el resultat ([0] és ara a + b + 48 donat que no s'ha corregit b). Es mou el punter a [1] que tenia la tecla Enter i es fa sortir, el programa acaba.

Multiplicació

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

Igual que el programa anterior, però en comptes de sumar, multiplica. Té les mateixes limitacions: 1 dígit per cada valor i resultats d'un dígit.

entrada: 24
sortida: 8 (2 x 4 = 8; 8 + 48 = 56; 8 en ASCII)

entrada: 48
sortida: P (4 x 8 = 32; 32 + 48 = 60; P en ASCII)

El primer nombre entra a [0], el segon a [1], es corregeixen tots dos restant-los 48 (primera línia).

Ara s'entra al bucle principal de la multiplicació. La idea bàsica és que cada cop que el programa hi passa restarà 1 a [0] i afegirà el valor de [1] al total que estarà a [2]. En detall: el primer bucle interior mou [1] a [2] i [3] i deixa [1] a zero (la manera bàsica de duplicar un nombre). El següent bucle intern mou [3] un altre cop a [1], deixant [3] a zero. Llavors es resta 1 de [0], i acaba el bucle exterior. En sortir [0] és zero, [1] encara té el segon nombre i [2] té el producte dels dos nombres inicials.

A la tercera línia afegim 48 al producte, s'introdueix amb la tecla Enter en [3], surt el producte en ASCII i després el retorn que havia entrat en [3].

Divisió

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

,>,>++++++[-<--------<-------->>] Entra un nombre de dos dígits a (0) i (1) i restem 48 als dos
<<[ Bucle fins que el dividend sigui zero
>[->+>+<<] El divisor es mou de (1) a (2) i (3) posant (1) a zero 
>[-<<- Resta 1 al dividend(0) i al divisor(2) fins que (2) sigui zero
[>]>>>[<[>>>-<<<[-]]>>]<<] Si el dividend és zero sortir del bucle
>>>+ Afegir 1 al quocient en (5)
<<[-<<+>>] Es mou el divisor de (3) a (2)
<<<] El punter es mou a (0) i es repeteix el bucle
>[-]>>>>[-<<<<<+>>>>>] El quocient en (5) es mou a (0)
<<<<++++++[-<++++++++>]<. Sumar 48 i mostrar el resultat
>>>>>>++++++++++. Surtir amb 'enter' al final

Quan l'usuari entra un nombre amb dos dígits, aquest codi els divideix, ignorant la resta, i mostra el quocient (un dígit) a la pantalla.

entrada: 63
sortida: 2 (6 / 3 = 2; 2 + 48 = 50; 2 en ASCII)

entrada: 94
sortida: 2 (9 / 4 = 2; 2 + 48 = 50; 2 en ASCII)

entrada: 24
sortida: 0 (2 / 4 = 0; 0 + 48 = 48; 0 en ASCII)

El joc de la vida

Vegeu també: Joc de la vida

 Linus Akesson presents:
 The Game Of Life implemented in Brainfuck

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

 Escriviu, per exemple, «fg» per canviar la cel·la a la fila f i la columna g
 Premeu Intro per calcular la propera generació
 Escriviu q per sortir

Triangle de Sierpinski

Vegeu també: Triangle de Sierpinski

Aquest programa imprimeix el triangle de Sierpinski amb asterics (*) en una pantalla de 80 columnes.

 >
 + +
 + +
 [ < + +
 + +
 + + + +
 > - ] >
 + + + + + + + +
 [ >
 + + + +
 < - ] >
 > + + > > > + >
 > > + <
 < < < < < < < <
 < [ - [ - > + <
 ] > [ - < + > > > . < < ] > > >
 [ [
 - > + +
 + + + +
 + + [ > + + + +
 < - ] >
 . < < [ - > + <
 ] + > [ - > + +
 + + + + + + + + < < + > ] > . [
 - ] > ]
 ] + < < < [ - [
 - > + < ] + > [
 - < + > > > - [ - > + < ] + + >
 [ - < - > ] < <
 < ] < < < < ] + + + + + + + + +
 + . + + + . [ - ] < ] + + + + +
 * * * * * M a d e * B y : * N Y Y R I K K I * 2 0 0 2 * * * * *

ROT13

Vegeu també: ROT13

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

Aquest programa xifra la seva entrada amb el xifrat ROT13. Per fer-ho, ha de mapejar caràcters d' A-M (ASCII 65-77) fins a N-Z (78-90), i viceversa. També ha de mapejar a-m (97-109) fins a n-z (110-122) i viceversa. Ha de mapejar tots els altres caracters a ells mateixos; llegeix els caràcters d'un en un i emet els seus equivalents xifrats fins que llegeix un EOF (aquí se suposa que es representa com -1 o «sense canvi»), moment en què el programa finalitza.

L'enfocament bàsic utilitzat és el següent. Cridant el caràcter d'entrada x, dividir x-1 per 32, mantenint el quocient i el residu. A menys que el quocient sigui 2 o 3, només ha de sortir x, havent-ne conservat una còpia durant la divisió. Si el quocient és 2 o 3, ha dividir la resta ((x-1) mòd 32) per 13; si el quocient aquí és 0, la sortida és x+13; si 1, sortida és x-13; si 2, surt x.

Pel que fa a l'algorisme de divisió, quan es divideix y per z per obtenir un quocient q i la resta r, hi ha un bucle exterior que estableix q i r primer al quocient i la resta d'1/z, després als de 2/z, i així successivament; després d'haver executat y vegades, aquest bucle exterior s'acaba, deixant q i r establerts en el quocient i la resta de y/z; (el dividend y s'utilitza com a comptador decreixent que controla quantes vegades s'executa aquest bucle). Dins del bucle, hi ha codi per incrementar r i disminuir y, que normalment és suficient; tanmateix, cada z vegada a través del bucle exterior, cal posar a zero r i incrementar q. Això es fa amb un comptador decreixent posat al divisor z; cada vegada que passa pel bucle exterior, aquest comptador es disminueix i, quan arriba a zero, es torna a omplir movent el valor de r de nou a ell.

-,+[ Llegeix el primer caracter i s'inicia el bucle de lectura del caracter exterior
 -[ Salta endavant si el caracter és 0
 >>++++[>++++++++<-] Configurar el divisor (32) per al bucle de divisió
 (DISPOSICIÓ DE LA MEMÒRIA: dividend còpia resta divisor quocient zero zero)
 <+<-[ Configurar el dividend (x-1) i introduir el bucle de divisió
 >+>+>-[>>>] Incrementa la còpia i la resta / redueix el divisor / Cas normal: saltar endavant
 <[[>+<-]>>+>] Cas especial: moure la resta al divisor i augmentar el quocient
 <<<<<- Disminuir el dividend
 ] Final del bucle de la divisió
 ]>>>[-]+ Finalitzar el bucle de salt; zero antic divisor i reutilitza l'espai per a una bandera
 >--[-[<->+++[-]]]<[ Posar a zero aquesta bandera tret que el quocient sigui 2 o 3; quocient zero; bandera de 
 verificació
 ++++++++++++<[ Si hi ha bandera, configurar el divisor (13) per al bucle de segona divisió
 (DISPOSICIÓ DE LA MEMÒRIA: zero còpia dividend divisor quocient de resta zero zero)
 >-[>+>>] Reduir el divisor; Cas normal: augment de la resta
 >[+[<+>-]>+>>] Cas especial: augmentar el residu / tornar-lo al divisor / augmentar el quocient
 <<<<<- Disminuir el dividend
 ] Bucle de divisió final
 >>[<+>-] Afegir la resta al divisor per obtenir un 13 útil
 >[ Saltar endavant si el quocient és 0
 -[ Disminuir el quocient i saltar endavant si el quocient és 1
 -<<[-]>> Quocient zero i divisor si el quocient és 2
 ]<<[<<->>-]>> Divisor zero i restar 13 de la còpia si el quocient és 1
 ]<<[<<+>>-] Divisor zero i afegir 13 per copiar si el quocient és 0
 ] Finalitza el bucle de salt exterior (salta aquí si ((caràcter - 1)/32) no és 2 o 3)
 <[-] Esborra la resta de la primera divisió si es va saltar la segona divisió
 <.[-] Sortir el caràcter ROT13 de la còpia i esborrar-lo
 <-,+ Llegir el següent caracter
] Finalitzar el bucle de lectura de caràcters

entrada: viquipedia
sortida: ivdhvcrqvn

entrada: VIQUIPEDIA
sortida: IVDHVCRQVN

Problemes de portabilitat

En part perquè Urban Müller no va escriure una especificació completa del llenguatge, els nombrosos intèrprets i compiladors posteriors de brainfuck han implementat dialectes de brainfuck lleugerament diferents.

Mida de la cel·la

En la distribució clàssica, les cel·les són de mida de 8 bits (les cel·les són 1 byte), i aquesta encara és la mida més habitual. Tanmateix, per llegir dades no textuals, un programa de brainfuck pot necessitar distingir una condició de final de fitxer (EOF) de qualsevol valor de byte possible; així també s'han utilitzat cel·les de 16 bits (2 bytes). Algunes implementacions han utilitzat cel·les de 32 bits (4 bytes), cel·les de 64 bits (8 bytes) o cel·les amb un rang teòricament il·limitat. Les implementacions que utilitzen aquest rang addicional són més lentes, ja que les instruccions + i - només actualitzen el valor en ±1, i emmagatzemar el valor ${\displaystyle n}$ en una cèl·lula requereix un temps ${\displaystyle O(n)}$.

En totes aquestes variants, les instruccions , i . encara llegeixen i escriuen dades en bytes. En la majoria d'elles, les cel·les s'emboliquen, és a dir, augmentar una cel·la que manté el seu valor màxim (amb l'instrucció +) la portarà al seu valor mínim i viceversa. Les excepcions són les implementacions que estan allunyades del maquinari subjacent, les implementacions que utilitzen bignums i les implementacions que intenten fer complir la portabilitat.

En general, és fàcil escriure programes de brainfuck que no provoquen mai cap embolicament^{[Nota 1]} o desbordament d'enters,^{[Nota 2]} i per tant no depenen de la mida de la cel·la. En general, això significa evitar l'increment de +255 (embolicament de 8 bits sense signe), o evitar sobrepassar els límits de [-128, +127] (embolicament de 8 bits amb signe); com que no hi ha operadors de comparació, un programa no pot distingir entre un la cel·la de mida de bit fixa del complement a dos amb signe i sense signe i la negabilitat dels nombres és una qüestió d'interpretació).

Mida de la matriu

En la distribució clàssica, la matriu té 30.000 cel·les, i el punter comença a la cel·la més esquerra. Fins i tot es necessiten més cel·les per emmagatzemar coses com el milió nombre de Fibonacci, i la manera més senzilla de completar el llenguatge Turing és fer que la matriu sigui il·limitada a la dreta.

Algunes implementacions també estenen la matriu a l'esquerra;^[12] aquesta és una característica poc comuna i, per tant, els programes brainfuck portàbles no depenen d'això.

Quan el punter es mou fora dels límits de la matriu, algunes implementacions donaran un missatge d'error, algunes intentaran estendre la matriu de manera dinàmica, algunes no se n'adonaran i produiran un comportament indefinit, i unes quantes mouran el punter al sentit contrari del final de la matriu. Hi ha alguns inconvenients: expandir la matriu de manera dinàmica cap a la dreta és l'enfocament més fàcil d'utilitzar i és bo per a programes amb fam de memòria, però comporta una penalització de velocitat. Si s'utilitza una matriu de mida fixa, és útil fer-la molt gran, o millor encara deixar que l'usuari estableixi la mida. Donar un missatge d'error per a infraccions de límits és molt útil per a la depuració, però fins i tot això comporta una penalització de velocitat tret que pugui ser gestionat per les proteccions de memòria del sistema operatiu.

Codi de final de línia (EOL)

Els diferents sistemes operatius (i de vegades diferents entorns de programació) utilitzen versions subtilment diferents d'ASCII. La diferència més important està en el codi utilitzat per al final d'una línia de text. MS-DOS i Microsoft Windows utilitzen un CRLF, és a dir, un 13 seguit d'un 10 (0D 0A en hexadecimal), en la majoria de contextos. UNIX i els seus descendents (inclosos Linux i macOS) i Amiga només en fan servir 10, i els Mac més antics només en fan servir 13. Seria difícil que els programes brainfuck s'haguessin de reescriure per a diferents sistemes operatius. Tanmateix, era fàcil crear un estàndard unificat. El compilador d'Urban Müller i els seus exemples de programes utilitzen 10, tant a l'entrada com a la sortida; també ho fan una gran majoria dels programes de brainfuck existents; i 10 també és més còmode d'utilitzar que CRLF. Per tant, les implementacions de brainfuck haurien d'assegurar-se que els programes brainfuck que assumeixen una nova línia = 10 s'executaran correctament; molts ho fan, però alguns no.

Aquesta suposició també és coherent amb la majoria del codi d'exemple del món per a C i altres llenguatges, ja que utilitzen «\n», o «10», per a les seves noves línies. En els sistemes que utilitzen les terminacions de línia CRLF, la biblioteca estàndard C reassigna de manera transparent «\n» a «\r\n» a la sortida i «\r\n» a «\n» a l'entrada per a fluxos no oberts en mode binari.

Comportament al final del fitxer (EOF)

El comportament de la instrucció , quan s'ha trobat una condició de final de fitxer (EOF) varia. Algunes implementacions posen la cel·la al punter a 0, algunes l'estableixen a la constant C EOF (a la pràctica normalment és -1), algunes deixen el valor de la cel·la sense canvis. No hi ha un consens real. Els arguments dels tres comportaments són els següents:

• Establir la cel·la a 0 evita l'ús de nombres negatius i fa que sigui lleugerament més concís escriure un bucle que llegeix caràcters fins que es produeix l'EOF. Aquesta és una extensió lingüística ideada per Panu Kalliokoski.

• Establir la cel·la a -1 permet distingir l'EOF de qualsevol valor de byte (si les cel·les són més grans que bytes), que és necessari per llegir dades no textuals; també, és el comportament de la traducció C de , donada al fitxer README de Müller. Tanmateix, no és obvi que aquestes traduccions C s'hagin de prendre com a normatives.

• Deixar el valor de la cèl·lula sense canvis és el comportament del compilador brainfuck d'Urban Müller. Aquest comportament pot coexistir fàcilment amb qualsevol dels altres; per exemple, un programa que assumeix EOF = 0 pot establir la cel·la a 0 abans de cada comanda, i després funcionarà correctament en implementacions que facin EOF = 0 o EOF = «cap canvi». És tan fàcil adaptar-se al comportament de «sense canvis» que qualsevol programador que estigui interessat en la portabilitat ho hauria de fer.

Aritmetització

Cada instrucció de brainfuck canvia l'estat de l'execució del seu programa de maneres que es poden descriure mitjançant equacions polinomials. Per exemple, quan + augmenta el valor de la cel·la actual en 1, això es pot descriure amb una equació com ${\displaystyle v_{t}+1=v_{t+1}}$, on la variable ${\displaystyle v_{t}}$ representa el valor de memòria actual al pas ${\displaystyle t}$, i ${\displaystyle v_{t+1}}$ al següent pas d'execució. I quan > augmenta quina cel·la de memòria és la corrent en 1, això es pot descriure amb l'equació similar ${\displaystyle p_{t}+1=p_{t+1}}$, on ${\displaystyle p_{t}}$ i ${\displaystyle p_{t+1}}$ és el punter de memòria als passos posteriors de l'execució del programa.

Amb cada transició d'estat de programa vàlida expressada com una equació polinòmica, on cada variable representa una part de l'estat, es pot compilar una taula que descriu cada transició d'estat en una prova criptogràfica d'execució correcta, sense revelar la taula en si. Les proves de coneixement zero de la correcta execució dels programes són un camp actiu de recerca en criptografia. Brainfuck va ser el 2022 el primer llenguatge de Turing complet ja existent que es va aritmetitzar d'aquesta manera.^[13]

Implementacions

Tot i que és trivial fer un intèrpret de brainfuck ingenu, escriure un compilador optimitzador o intèrpret esdevé més un repte i una diversió com escriure programes en brainfuck en si. Per produir resultats raonablement ràpids, el compilador ha de reunir les instruccions fragmentàries forçat pel llenguatge. Les optimitzacions possibles van des d'optimitzacions simples de mirilla de longitud d'execució en ordres repetides i patrons de bucle habituals com [-], fins a altres més complicades com l'eliminació de codi mort i el plegat constant.^[14]

A més de fer compiladors brainfuck ràpids, també s'han escrit altres tipus d'intèrprets de brainfuck:

• Diversos compiladors brainfuck s'han fet més petits de 200 bytes: un només té 100 bytes en codi de màquina x86.^[15]

• Un motor zk-STARK que demostra criptogràficament l'execució d'un programa Brainfuck. Com que cada constructe de llenguatge ha de ser aritmetitzat (és a dir, descrit en termes d'equacions), Brainfuck és un bon llenguatge per a un sistema de prova de concepte, perquè les instruccions de brainfuck són poques i senzilles.

Llenguatges equivalents i derivats

Molta gent ha creat brainfuck equivalents (llenguatges amb ordres que mapegen directament amb brainfuck) o derivats brainfuck (llenguatges que amplien el seu comportament o alteren la seva semàntica).

Alguns exemples són:

• Pi, que mapeja brainfuck amb els errors en els dígits individuals del nombre π.^[16]
• VerboseFuck, que sembla un llenguatge de programació tradicional, només el que apareix com a paràmetres o expressions són en realitat parts d'ordres més llargues que no es poden alterar.^[17]
• DerpPlusPlus, en què les ordres es substitueixen per paraules com ara 'HERP', 'DERP', 'GIGITY', etc.^[18]
• Ook!, que mapeja les vuit ordres de brainfuck amb combinacions de dues paraules de «Ok.», «Ook?» i «Ook!», dissenyades en broma per ser «escrites i llegibles pels orangutans», segons el seu creador, una referència a the orang-utan Librarian que apareix a les novel·les de Terry Pratchett.^[19][20]
• Ternary, similar en concepte a Ook! que consisteix en permutacions dels caràcters ASCII 0, 1 i 2.^[21]
• BodyFuck, una implementació de brainfuck basada en un sistema controlat per gestos perquè els moviments del programador siguin captats per una càmera de vídeo i convertits en els 8 caràcters possibles.^[22]
• OooWee, les instruccions són variacions de OooWee (per exemple, ooo, ooe, wee, etc.), inspirat en el personatge Mr. PoopyButthole de la sèrie d'animació Rick i Morty.^[23]
• I Use Arch btw, que mapeja brainfuck amb les paraules que es troben a la frase «I Use Arch btw» (jo utilitzo Arch, per cert). Inspirat en una frase encunyada per la comunitat Arch Linux.^[24]
• Brainfunk, mapeja brainfuck amb mostres de veu, que s'utilitzen en una pista de ball, les paraules de la qual codifiquen un programa de brainfuck.^[25]
• DNA# és un superconjunt basat en molècules d'ADN, amb ordres substituïdes per les seves quatre nucleobases: adenina (A), timina (T), citosina (C) i guanina (G). Una forma utilitza la representació en hèlix de la molècula d'ADN.^[26]
• Brainfuck², «un derivat de brainfuck excepte que aquesta vegada és realment divertit». Cada terme del llenguatge és el nom d'un altre derivat de brainfuck.^[27]
• Fuckscript, un derivat del brainfuck amb «paraules clau més intuïtives», amb la paraula «fuck» al principi. Desenvolupat per l'adolescent Josh Schiavone.^[28]
• Motherf, un derivat del brainfuck amb varietat d'ordres i principis útils com macros, piles, funcions, E/S convenients, booleans i altres tipus de simulació. Desenvolupat per Pavel Voronin.^[29]

Notes

1. Una instal·lació mitjançant la qual una seqüència lineal d'ubicacions de memòria o posicions de pantalla es tracta com una sèrie circular contínua.
2. En programació, el desbordament d'enters és una condició que es produeix quan una operació aritmètica intenta crear un valor numèric que està fora de l'interval que es pot representar amb un nombre determinat de dígits.

Referències

1. Easter, Brandee «Fully Human, Fully Machine: Rhetorics of Digital Disembodiment in Programming» (en anglès). Rhetoric Review, 39(2), 02-04-2020, pàg. 202-215. DOI: 10.1080/07350198.2020.1727096. ISSN: 0735-0198.
2. «Aminet hits 5000 files» (en anglès). Urban Müller, 24-09-1993.
3. «The Brainfuck Programming Language» (en anglès). Muppetlabs. Arxivat de l'original el 2007-09-30. [Consulta: 27 març 2023].
4. «Wouter's Wiki : False Language» (en anglès). Strlen, 03-08-2013.
5. «dev/lang/brainfuck-2.lha» (en anglès). Aminet. Arxivat de l'original el 2005-11-06. [Consulta: 27 març 2023].
6. Lambek, 1961, p. 295-302.
7. Melzak, 1961, p. 279-293.
8. «BF is Turing-complete» (en anglès). Iwriteiam.
9. «Index of /brainfuck/bf-source/prog» (en anglès). Esoteric.sange, 22-01-2002.
10. «BF interpreter written in BF» (en anglès). Iwriteiam.
11. Cristofani, Daniel B. «Brainfuck interpreter» (en anglès). Hevanet.
12. Bolognani, Andrea. «Beef –» (en anglès). Kiyuko.
13. «BrainSTARK» (en anglès). Github.
14. Hughes, Wilfred. «Wilfred/bfc: An industrial-grade brainfuck compiler» (en anglès). GitHub, 05-08-2020.
15. «Brainfuck in 100 Bytes!» (en anglès). GitHub.
16. «Pi» (en anglès). Esolang.
17. «VerboseFuck» (en anglès). Esolang.
18. «TheRaz/DerpPlusPlus» (en anglès). GitHub.
19. Morgan-Mar, David. «Ook!» (en anglès). DM's Esoteric Programming Languages, 21-03-2009.
20. Paloque-Bergès, 2009, p. 73.
21. «Ternary Programming Language» (en anglès). GitHub.
22. Hanselmann, Nik. «There is no hardware.» (en anglès).
23. «omkarjc27/OooWee» (en anglès). GitHub.
24. «OverMighty/I Use Arch btw» (en anglès). GitHub.
25. «brainfunk (get with the program)» (en anglès). Sound Cloud.
26. «DNA-Sharp» (en anglès). Esolang.
27. «Brainfuck² - Esolang» (en anglès). esolangs.
28. «Fuckscript» (en anglès). Esolang.
29. «Motherf» (en anglès). Esolang.

Bibliografia

• Lambek, J. «How to program an infinite abacus» (en anglès). Canadian Mathematical Bulletin, 4(3), 1961. DOI: 10.4153/CMB-1961-032-6.
• Melzak, Z. A. «An informal arithmetical approach to computability and computation» (en anglès). Canadian Mathematical Bulletin, 4(3), 1961, pàg. 279–293. DOI: 10.4153/CMB-1961-031-9.
• Paloque-Bergès, Camille. Poétique des codes sur le réseau informatique (en francés). París: Éditions des archives contemporaines, 2009. ISBN 978-2-914610-70-4. 

Enllaços externs

• Brainfuck – intèrpret en línia en JavaScript amb col·lecció de programes (anglès)
• Brainfuck IDE – un entorn de desenvolupament brainfuck amb un depurador interactiu (anglès)
• Brainfuck collection – d'intèrprets i scripts (anglès)
• Brainfuck Assembler – traductor del codi d'assemblador x86 (conjunt reduït) a codi de brainfuck (anglès)
• «Parc infantil Brainfuck» a tio.run (anglès)