Brainfuck
De Viquipèdia
brainfuck és un llenguatge de programació esotèric. Es distingeix pel baix nombre de instruccions que fa servir, només en té 8. No obstant això és Turing complet.
Taula de continguts |
[edita] Disseny
Urban Müller va crear brainfuck en 1993 amb la intenció de dissenyar un llenguatge que pugués ser implementat amb el compilador més petit possible. Es va inspirar en el compilador de 1024 bytes per el 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).
[edita] Instruccions
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 a on apunta el punter. |
- |
decrement (decrementar per 1) el byte a 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. |
[edita] Traducció a llenguatge C
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) { |
] |
} |
[edita] Exemples
[edita] Trivials
[edita] Netejar posició
[-]
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ó.
[edita] Bucle simple
,[.,]
Això és un bucle continuu, 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:
,----------[++++++++++.,----------]
[edita] 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.
[edita] Afegir
[->+<]
Això afegeix la posició actual (destructivament, la deixa a zero) a la propera.
[edita] 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 'enter' la instrucció condicional [ saltarà a la posició just després de ] perque 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.
[edita] 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 al 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:
[->+>+<<]>>[-<<+>>]<<
[edita] No trivials
[edita] Hola Món!
Vegeu la secció Brainfuck de Hola món
[edita] Suma
,>++++++[<-------->-],[<+>-],<.>.
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 son 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.
[edita] 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.
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].
[edita] Divisió
,>,>++++++[-<--------<-------->>] 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.
[edita] Implementacions
- BFF(anglès) intèrpret optimitzat escrit en C portable
- Also Written In Brainfuck (awib)(anglès) compilador escrit en brainfuck per GNU/Linux en i386.
- Brainfucked(anglès) compilador amb validació de sintaxi i optimització per Microsoft Windows/DOS
