Brainfuck

De Viquipèdia
Dreceres ràpides: navegació, cerca

Brainfuck és un llenguatge de programació esotèric. Es distingeix pel baix nombre d'instruccions que fa servir, només en té 8. No obstant això és Turing complet.

Disseny[modifica | modifica el codi]

Urban Müller va crear brainfuck el 1993 amb la intenció de dissenyar un llenguatge que pogués ser implementat amb el compilador més petit possible. Es va inspirar en el compilador de 1024 bytes pel llenguatge FALSE. Existeixen diversos compiladors de brainfuck més petits que 200 bytes.

El llenguatge consisteix de 8 instruccions. Un programa de brainfuck és una seqüència d'aquestes instruccions, possiblement intercalades amb altres caràcters (que són ignorats). Les instruccions s'executen seqüencialment, excepte les dues de salt condicional.

El llenguatge es basa en un model d'execució simple que consisteix, a més del programa en una llista de 30.000 posicions, d'un byte de grandària cadascuna, inicialitzades a zero; un punter mòbil a la llista (inicialitzat a la primera posició, a l'esquerra), i dos 'streams' de bytes per entrada/sortida (sovint connectats al teclat i al monitor respectivament, i fent servir ASCII per codificar els caràcters).

Instruccions[modifica | modifica el codi]

Les 8 instruccions del llenguatge, cada una consistint en un simple caràcter, són les següents:

Caràcter 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.
.
fer sortir el valor del byte a la posició del punter.
,
acceptar un byte d'entrada, desant el seu valor al byte on sigui el punter.
[
salta l'execució a la instrucció posterior al corresponent ] si el byte del punter és zero.
]
salta a la instrucció posterior al corresponent [ si el byte del punter no és zero.

Traducció a llenguatge C[modifica | modifica el codi]

Els programes de brainfuck es poden traduir al llenguatge de programació C fent servir les següents substitucions, assumint que ptr és de tipus unsigned char* i ha estat inicialitzat per apuntar a una llista de bytes inicialitzats a zero:

instrucció brainfuck equivalent C
>
++ptr;
<
--ptr;
+
++*ptr;
-
--*ptr;
.
putchar(*ptr);
,
*ptr=getchar();
[
while (*ptr) {
]
}

Exemples[modifica | modifica el codi]

Trivials[modifica | modifica el codi]

Netejar posició[modifica | modifica el codi]

[-]

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

Bucle simple[modifica | modifica el codi]

,[.,]

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 'enter' (ASCII 10) al teclat:

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

Movent el punter[modifica | modifica el codi]

>,[.>,]

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

Afegir[modifica | modifica el codi]

[->+<]

Això afegeix la posició actual (destructivament, la deixa a zero) a la propera.

Instruccions condicionals[modifica | modifica el codi]

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

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 '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 '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 'enter' perque no hi ha més instruccions després.

Copiant un byte[modifica | modifica el codi]

(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 la 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:

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

No trivials[modifica | modifica el codi]

Hola Món![modifica | modifica el codi]

Vegeu la secció Brainfuck de Hola món

Suma[modifica | modifica el codi]

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

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'enter'

sortida: 7

El primer nombre entra a [0] i li restem 48 per corregir-lo (ha entrat el codi ASCII, i aquests codis per els 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 cops (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 un '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 el 'enter' i es fa sortir, el programa acaba.

Multiplicació[modifica | modifica el codi]

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

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.

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 un 'enter' en [3], surt el producte en ASCII i deprès el retorn que havia entrat en [3].

Divisió[modifica | modifica el codi]

,>,>++++++[-<--------<-------->>] entren 2 nombres 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)
<<<<++++++[-<++++++++>]<. afegir 48 i mostrar el resultat
>>>>>>++++++++++. surt 'enter' al final

Quan l'usuari entra dos nombres, aquest codi els divideix, ignorant la resta, i mostra el quocient a la pantalla.

Implementacions[modifica | modifica el codi]