Brainfuck

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da BrainFuck)
Vai alla navigazione Vai alla ricerca
Brainfuck
linguaggio di programmazione
Programma "Hello, World!" in Brainfuck
AutoreUrban Müller
Data di origineSettembre 1993
Paradigmiesoterico, imperativo, strutturato
TipizzazioneNon tipizzato
Estensioni comuni.b e .bf
Influenzato daP′′, FALSE
Ha influenzatoMalbolge, Whitespace
Modifica dati su Wikidata · Manuale

Brainfuck (lett. "fottere il cervello") è un linguaggio di programmazione esoterico per computer, creato da Urban Müller intorno al 1993. Il linguaggio viene in taluni casi denominato Brainf*ck, Brainf*** o anche soltanto BF per evitare di offendere la sensibilità altrui.

Struttura del linguaggio[modifica | modifica wikitesto]

L'obiettivo di Müller era di creare un semplice linguaggio di programmazione completo per una macchina di Turing che potesse essere implementato con il compilatore più piccolo possibile. Il linguaggio consiste di otto istruzioni. La versione 2 del compilatore originale, scritta per il 68000 dell'Amiga, occupa soltanto 240 byte. È stato ispirato dal linguaggio FALSE, un altro linguaggio di programmazione esoterico, il cui compilatore occupava 1024 byte.

Come il nome suggerisce, i programmi scritti in Brainfuck tendono ad essere difficili da comprendere. Tuttavia Brainfuck è un linguaggio Turing-completo, e si può utilizzare per implementare qualunque algoritmo eseguibile con una macchina di Turing. Trascurando l'enorme difficoltà nella programmazione di certi algoritmi con Brainfuck, è certamente possibile scrivere il relativo codice.

Il linguaggio è basato su un modello molto semplice consistente in un array di byte inizializzato a zero, un puntatore all'array (inizializzato per puntare al primo byte dell'array) e due stream di byte per l'input e l'output.

Istruzioni[modifica | modifica wikitesto]

Le istruzioni del linguaggio sono otto, ciascuna consiste in un singolo carattere e sono:

Carattere Significato
> incrementa il puntatore
< decrementa il puntatore
+ incrementa il byte indirizzato dal puntatore
- decrementa il byte indirizzato dal puntatore
. output dal byte indirizzato dal puntatore (ASCII)
, input al byte indirizzato dal puntatore (ASCII)
[ salta in avanti all'istruzione dopo il corrispondente ] se il byte indirizzato dal puntatore è zero
] salta indietro all'istruzione dopo il corrispondente [ se il byte indirizzato dal puntatore non è zero

In alternativa, ] può essere inteso come "salta indietro alla corrispondente [". In tal modo è più breve, ma meno simmetrico e meno efficiente in termini di tempo. Le due versioni producono comunque un comportamento equivalente di ciascun programma Brainfuck.

Una terza versione equivalente, scarsamente considerata, è: [ significa "salta in avanti al corrispondente ]", e ] significa "salta indietro all'istruzione che segue il corrispondente [ se il byte al puntatore non è zero".

I sorgenti per Brainfuck possono essere transcodificati in C utilizzando la seguente tabella di sostituzione, assumendo che ptr sia di tipo unsigned char*:

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

Esempi[modifica | modifica wikitesto]

Hello world![modifica | modifica wikitesto]

Il seguente codice mostra "Hello World!" sullo schermo e manda a capo il cursore 

++++++++++
[
>+++++++>++++++++++>+++>+<<<<-
]
>++. Loop iniziale (dopo viene stampata una H)
>+. e
+++++++. l
. l
+++. o
>++.
<<+++++++++++++++.
>.
+++.
------.
--------.
>+.
>.

Per mantenere leggibile il listato, viene iniziata una nuova linea dopo ciascun punto, che rappresenta il comando di output. Le lettere H, e, l, l e o sono state inserite nel codice esclusivamente come commenti. Il Brainfuck considera tutti i caratteri ad eccezione di +-<>[],. come dei commenti, cosicché non è necessaria una sintassi particolare per indicare un commento.

Il loop sulla prima linea imposta il valore iniziale dell'array: a[1] = 70 (vicino al valore ASCII per il carattere 'H', 72), a[2] = 100 (vicino alla 'e', 101), a[3] = 30 (vicino a ' ', 32) e a[4] = 10 (new line, a capo). Il loop funziona moltiplicando il valore di a[0], 10, salvando il risultato nelle altre celle. Al termine del loop, il puntatore all'array è zero. >++ incrementa di uno il puntatore, indicando a[1] che è 70, poi aggiunge due a tale valore, con il risultato di 72 che è il valore per il carattere ASCII della lettera H maiuscola. Il punto al termine della linea indica l'output, causandone la visualizzazione.

La linea successiva sposta il puntatore all'array in alto di una posizione, poi aggiunge uno. a[2] è ora 101, una 'e' minuscola, che viene poi mostrata con l'istruzione di output.

Dal momento che la lettera 'l' è la settima lettera dopo la 'e', per mostrare la 'l'aggiungiamo sette (+++++++) al puntatore corrente e mostriamo l'output due volte.

'o' è la terza lettera dopo la 'l', quindi incrementiamo tre volte il valore dell'array e mandiamo in output il risultato.

La parte rimanente del programma prosegue esattamente come illustrato finora. Per lo spazio e la lettera maiuscola, vengono selezionati diversi puntatori, che sono poi incrementati o decrementati secondo necessità.

Semplici[modifica | modifica wikitesto]

Loop semplice[modifica | modifica wikitesto]

,[.,]

Un ciclo continuo che prende del testo in input dalla tastiera e lo scrive sullo schermo. Da notare che si assume che la cella sia impostata a 0 quando un comando ',' viene eseguito dopo la fine dell'input (alle volte chiamata end-of-file o "EOF"); le implementazioni differiscono in questo punto. Per implementazioni che impostano la cella a -1 o EOF, oppure che non modificano il valore della cella, questo programma andrebbe scritto rispettivamente ",+[-.,+]" o ",[.[-],]"

Manipolazione dei puntatori[modifica | modifica wikitesto]

>,[.>,]

Una versione dell'ultimo esempio che salva anche tutto l'input in un array per uso futuro, muovendo il puntatore ogni volta.

Sommare[modifica | modifica wikitesto]

[->+<]

Questo somma la locazione corrente (distruttivamente, essa viene messa a zero) alla locazione successiva.

Istruzioni condizionali[modifica | modifica wikitesto]

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

Questo esempio prenderà input scritti in minuscolo dalla tastiera e li farà diventare maiuscoli. Per uscire, premere il tasto invio.

In primo luogo, inseriamo il primo carattere usando il comando , e immediatamente sottraiamo 10 da esso. (Molti, ma non tutti, i programmi Brainfuck usano 10 per indicare il tasto di ritorno a capo.) Se l'utente preme invio, l'istruzione di ciclo ([) salterà dopo la fine del ciclo, perché setteremo il primo byte a zero. Se il carattere inserito non era 10, assumeremo che esso fosse una lettera minuscola, ed entreremo nel ciclo, nel quale sottrarremo un altro 22 da esso, per un totale di 32, il quale è la differenza tra una lettera ASCII minuscola e la corrispondente lettera maiuscola.

Successivamente lo visualizzeremo. Ora inseriamo il prossimo carattere, ed ancora sottraiamo 10. Se questo carattere fosse un linefeed, usciamo dal ciclo; altrimenti, ritorneremo all'inizio del ciclo, sottrarremo un altro 22, lo visualizzeremo, e così via. Quando usciamo dal ciclo, il programma termina, siccome non ci sono più comandi.

Copiare un byte[modifica | modifica wikitesto]

Brainfuck non include nessuna operazione per copiare byte. Questo deve essere fatto con i costrutti di ciclo e gli operatori aritmetici. Muovere un byte è abbastanza semplice; muovere il valore di [0] a [1] può essere fatto come segue: 

[->+<]

Comunque, questo resetta il valore di [0] a 0. Possiamo ripristinare il valore di [0] dopo la copia prendendo vantaggio dell'abilità di copiare un valore in due posti alla volta. Per copiare il valore di [0] in entrambi [1] e [2] è semplice: 

[->+>+<<]

Possiamo prendere vantaggio di questo per ripristinare il valore [0]. Quindi, possiamo non distruttivamente copiare [0] a [1] (usando [2] come variabile temporanea) così come segue: 

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

Complessi[modifica | modifica wikitesto]

Somma[modifica | modifica wikitesto]

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

Questo programma aggiunge due numeri a singola cifra e visualizza il risultato correttamente se anch'esso è composto da una sola cifra: 

4+3

7

(Ora le cose iniziano a diventare un po' più complicate. Noi possiamo riferirci ai byte nell'array come [0], [1], [2], e così via.)

Il primo numero è inserito in [0], e gli si sottrae 48 per ottenere la cifra corrispondente (i codici ASCII per i numeri da 0 a 9 sono infatti quelli da 48 a 57). Questo è fatto mettendo un 6 in [1] ed usando un ciclo per sottrarre 8 da [0] il numero corrispondente di volte. (Questo è un metodo comune di sommare o sottrarre grandi numeri) Successivamente, si inserisce il segno di somma in [1]; si inserisce infine il secondo numero, sovrascrivendo il simbolo di somma.

Il ciclo successivo [<+>-] fa il vero lavoro, muovendo il secondo numero sopra il primo, sommandoli insieme ed azzerando [1]. A ogni loop, esso aggiunge uno a [0] e sottrae uno da 1; così [1] viene alla fine azzerato, e la quantità aggiunta a [0] è esattamente quella rimossa da [1]. Viene quindi inserito un valore di ritorno in [1]. (Non stiamo controllando possibili errori sull'input.)

Poi il puntatore viene spostato indietro a [0], che viene visualizzato. ([0] è ora a + (b + 48), siccome non abbiamo corretto b; questo valore è identico ad (a + b) + 48, che è ciò che vogliamo.) Ora il puntatore è spostato a [1], il quale contiene il risultato; esso viene infine visualizzato, terminando l'algoritmo

Moltiplicazione[modifica | modifica wikitesto]

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

Come il precedente esempio, ma esegue la moltiplicazione, non l'addizione.

Il primo numero è inserito in [0], l'asterisco e poi il secondo numero sono inseriti in [1], ed entrambi i numeri sono corretti sottraendo da essi 48.

Ora entriamo nel ciclo principale della moltiplicazione. L'idea base è che ogni volta attraverso esso noi sottraiamo uno da [0] ed aggiungiamo [1] al totale corrente tenuto in [2]. In particolare: il primo ciclo interno sposta [1] su entrambi [2] e [3], mentre azzera [1]. (Questo è il metodo base per moltiplicare un numero.) Il primissimo ciclo interno sposta [3] indietro all'interno di [1], azzerando [3]. Poi uno è sottratto da [0], e il ciclo esterno viene terminato. Uscendo da questo ciclo, [0] è zero, [1] continua a contenere il secondo numero, e [2] contiene il prodotto dei due numeri. (Abbiamo fatto attenzione tenendo il primo numero, potevamo aggiungere uno a [4] ogni volta attraverso il ciclo esterno, poi spostare il valore da [4] indietro ad [1] in seguito.)

Ora aggiungiamo 48 al prodotto, inseriamo un risultato in [3], visualizziamo il prodotto usando i caratteri ASCII, e poi visualizziamo il risultato che abbiamo memorizzato.

Commento[modifica | modifica wikitesto]

Poiché ogni locazione di array è specificata come un byte, il comando - è superfluo e potrebbe essere rimpiazzato con 255 comandi +. Similarmente, se l'array fosse finito e circolare, < potrebbe essere sostituito con (dimensione array - 1) comandi >. Tuttavia, la dimensione dell'array deve essere illimitata se il linguaggio vuole essere Turing-completo, altrimenti avrebbe un numero finito di stati. (È precisamente per questa ragione che anche un PC moderno non è Turing-completo in senso stretto).

Linguaggi di programmazione simili[modifica | modifica wikitesto]

Una lista di linguaggi simili:

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica
Estratto da "https://it.wikipedia.org/w/index.php?title=Brainfuck&oldid=136250456"