Vai al contenuto

Brainfuck

Aggiungi collegamenti
Da Wikiversità, l'apprendimento libero.
lezione
lezione
Brainfuck
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi di programmazione

Brainfuck è un linguaggio di programmazione per computer, di tipo minimalista, 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]

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 l'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]

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 al puntatore
- decrementa il byte al puntatore
. output dal byte al puntatore (ASCII)
, input al byte al puntatore (ASCII)
[ salta in avanti all'istruzione dopo il corrispondente ] se il byte al puntatore è zero
] salta indietro all'istruzione dopo il corrispondente [ se il byte al 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 trascodificati nel linguaggio 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]

Hello world!

[modifica]

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]

Loop semplice

[modifica]
,[.,]

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]
>,[.>,]

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

Sommare

[modifica]
[->+<]

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

Istruzioni condizionali

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

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

In primo luogo, inseriamo il primo carattere usando il comando , e immediatamente sottriaiamo 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]

Brainfuck non include nessuna operazione per copiare bytes. Questo deve essere fatto con i costrutti di ciclo e gli operatori aritmetici. Muovere un byte è semplice abbastanza; 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]

Somma

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

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

4+3

7

(Ora le cose iniziano a diventare un po' più complicate. Noi possiamo riferirci ai bytes 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]
,>,,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-],<.>.

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 prissimo 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]

Poiché ogni locazione di array è specificata come un byte, il comando - è superfluo e potrebbe essere rimpiazzato con 255 comandi +. Similarmente, se l'elemento dell'array fosse finito e circolare, < potrebbe essere sostituito con (dimensione array - 1) comandi >. Tuttavia, sia la dimensione dell'array che la capacità delle celle devono essere illimitate se il linguaggio vuole essere Turing-conforme. (È precisamente per questa ragione che anche un PC moderno non è Turing-conforme in senso stretto).

Vedere anche

[modifica]

Collegamenti esterni

[modifica]
Estratto da "https://it.wikiversity.org/w/index.php?title=Brainfuck&oldid=226012"