[pipe] Brainfuck

BF- è una versione semplificata di Brainfuck, un linguaggio di programmazione esoterico creato nel 1993. Il modello di computazione in BF- è estremamente semplice. La memoria è modellata come un vettore di byte (di dimensione limitata) dove tutte le celle sono inizializzate a 0. È inoltre presente un data pointer, essenzialmente un indice del vettore, che permette di selezionare la variabile su cui i comandi del linguaggio devono operare.

Un comando in Brainfuck consiste di un singolo carattere. BF- supporta il seguente sottoinsieme di comandi Brainfuck:

  • + incrementa di 1 la variabile puntata dal data pointer;
  • - decrementa di 1 la variabile puntata dal data pointer;
  • > incrementa di 1 (modulo dimensione della memoria) il data pointer, in modo che faccia riferimento alla successiva cella di memoria;
  • < decrementa di 1 (modulo dimensione della memoria) il data pointer, in modo che faccia riferimento alla precedente cella di memoria;
  • . stampa il contenuto della variabile puntata dal data pointer sotto forma di carattere.

Nell’archivio (link) trovate il programma bf che ripete per un numero casuale di volte le seguenti operazioni:

  • invia su una pipe una parola terminata dal carattere #;
  • legge da una seconda pipe un programmi BF- (terminato dal carattere #);
  • interpreta il programma BF- ricevuto e stampa a video l’output.

I nomi delle pipe da cui leggere e scrivere sono passati al programma bf come argomenti da riga di comando usando rispettivamente le opzioni -i e -o. Se l’opzione -o non viene specificata, il programma scrive su standard output; se l’opzione -i non viene specificata, il programma legge da standard input.

L’obiettivo della verifica è di realizzare un programma che, usando le pipe, legge la stringa inviata nella pipe da bf, genera un programma BF- che stampa a video la stringa letta (senza il #) e lo invia sulla pipe a bf, in modo che questo possa interpretarlo. Questa sequenza di operazioni deve essere ripetuta per tutte le stringhe inviate sulla pipe da bf. Ogni programma BF- inviato deve essere terminato da #.

Il programma supporta altre opzioni:

  • -s permette di impostare la dimensione della memoria;
  • -v attiva la modalità verbosa dove, per ogni comando inviato, viene mostrato lo stato della memoria e la dimensione del data pointer;
  • -h mostra le opzioni supportate.

Segue un esempio di esecuzione verbosa dove l’interazione avviene tramite standard input e standard output e i comandi BF- sono mostrati in rosso:

> ./bf -v
forte#+
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
>
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
-
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+---+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
<
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|  2|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
...
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|102|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
.
Value: 102, Char: 'f'
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|102|  1|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|  0|
+@@@+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
...

Per usare le pipe, il programma può essere invocato come segue:

> ./bf -i /tmp/pipeIn -o /tmp/pipeOut
Visualizza la soluzione

Soluzione

Ecco una possibile soluzione commentata della verifica:

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/stat.h>

#define PIPEIN  "/tmp/pipeIn"
#define PIPEOUT "/tmp/pipeOut"

/*
 * La verifica consiste nell'implementazione di un programma in C che interagisca
 * tramite pipe con il programma 'bf' che ci è stato fornito. Il programma 'bf'
 * invia su PIPEOUT una parola terminata dal carattere '#' e si aspetta su PIPEIN
 * un programma in BF- che stampi la parola inviata. Questa interazione deve
 * essere ripetuta per tutte le parole ricevute su PIPEOUT.
 *
 * La soluzione realizzata utilizza esclusivamente i comandi '+', '-' e '.',
 * pertanto è sufficiente utilizzare una memoria di dimensione pari a 1 per
 * eseguirlo. Il programma legge un carattere della parola da stampare e calcola
 * il numero di comandi '+' o '-' da inviare in base al carattere stampato
 * all'iterazione precedente del ciclo. Quando viene letto il carattere '#',
 * viene inviato sulla pipe per segnalare che il programma BF- è terminato.
 *
 * Dopo aver avviato questo programma, il programma di test va eseguito come
 * segue:
 *
 *     ./bf -i /tmp/pipeIn -o /tmp/pipeOut -s 1
 */

int main() {
	int i, fr, fw, ncmd;
	char c, prev, cmd;

	/* Crea le due pipe se non esistono già. */
	mkfifo(PIPEIN, 0666);
	mkfifo(PIPEOUT, 0666);

	/* Apri PIPEIN in scrittura e PIPEOUT in lettura. Stampa un messaggio e
	 * termina se si verifica un errore durante l'apertura. */
	fw = open(PIPEIN, O_WRONLY);
	if (fw < 0) {
		fprintf(stderr, "Errore nell'apertura della pipe '%s' in scrittura.\n", PIPEIN);
		return EXIT_FAILURE;
	}
	fr = open(PIPEOUT,O_RDONLY);
	if (fr < 0) {
		fprintf(stderr, "Errore nell'apertura della pipe '%s' in lettura.\n", PIPEOUT);
		return EXIT_FAILURE;
	}

	/* La variabile 'prev' tiene traccia dell'ultimo carattere stampato.
	 * All'inizio non è stato stampato nulla e la memoria è inizializzata a
	 * zero. */
	prev = 0;
	/* Leggi un carattere per volta. Il ciclo termina quando la funzione 'read'
	 * restituisce zero, ovvero PIPEOUT è vuota ed è stata chiusa in scrittura
	 * dal programma 'bf'. */
	while(read(fr, &c, sizeof(char))) {
		if (c == '#') {
			/* Se il carattere letto è il cancelletto, invialo sulla pipe per
			 * segnalare che il programma BF- è terminato. */
			write(fw, "#", sizeof(char));
			prev = 0;
		} else {
			/* Se il carattere stampato al ciclo precedente ha codice ASCII
			 * inferiore al carattere da stampare, dobbiamo usare il comando '+'
			 * per incrementare la cella di memoria su cui stiamo lavorando.
			 * Altrimenti la dobbiamo decrementare con il comando '-'. */
			cmd = (prev < c) ? '+' : '-';
			/* Il numero di comandi da inviare è pari al valore assoluto della
			 * differenza tra il carattere precedente e quello corrente. */
			ncmd = abs(prev - c);
			/* Invia i comandi di incremento/decremento seguiti dal '.' per
			 * stampare il carattere. Infine aggiorna 'prev' con il carattere
			 * stampato in questa iterazione */
			for (i = 0; i < ncmd; i++) {
				write(fw, &cmd, sizeof(char));
			}
			write(fw, ".", sizeof(char));
			prev = c;
		}
	}	

	/* Chiudi le pipe e rimuovile dal filesystem. */
	close(fr);
	close(fw);
	unlink(PIPEIN);
	unlink(PIPEOUT);

	return EXIT_SUCCESS;
}

7 thoughts on “[pipe] Brainfuck”

  1. Buongionro, non riesco a fare funzionare il programma. Provo a lanciare il programma bf e quello della soluzione compilato con nome ‘brain’ da due terminali diversi e mi dà segmentation fault. Il commando usato è quello specificato nella soluzione, ossia ./bf -i /tmp/pipeIn -o /tmp/pipeOut -s 1
    Inoltre devo sempre prima lanciare brain e successivamente bf, altrimenti bf mi da ‘No such file o directory’
    Se provo a lanciarli in parallelo con ‘&’ delle volte mi da segmentation fault.

    1. Se non posti il sorgente non posso capire cosa hai sbagliato…. ti dice no such file or directory perché non trova le pipe con nome.

      1. Buongiorno,
        mi scusi, il sorgente è proprio quello della soluzione da lei proposta. Ho anche provato a modificare i nomi delle pipe in ‘./pipeIn’ e ‘./pipeOut’ pensando che forse c’erano problemi accedendo a ‘/tmp’ ma niente.
        la ringrazio.

        1. sto usando bf-x86, proverò più tardi con bf-x86-64 su un’altra macchina. Ho anche notato che nel .zip c’è un txt chiamato ‘words’, bisogna fare qualcosa con quel file?

  2. Non devi lanciarli con & perché se parte prima bf le pipe non esistono. Lancia prima la soluzione e poi bf da due terminali diversi. Comunque ho aggiornato gli eseguibili e ora bf crea le pipe quindi dovrebbe funzionare anche se li lanci con &.

  3. Salve professore,
    ho notato che nella sua soluzioni non scrive mai nel pipe in ‘>’ e ‘<',quindi il programma che ha fornito continuerà a incrementare o , eventualmente , decrementare il valore contenuto nella stessa cella ,nonchè la prima cella .
    Potrebbe darmi delle delucidazioni su questo dubbio che mi affligge

    La ringrazio .

    cordiali saluti

    1. Non è obbligatorio usare ‘<' e '>‘. Utilizzando ‘>’ puoi semplicemente spostarti alla cella successiva e incrementare il byte fino a raggiungere il codice del char che vuoi stampare. Se invece resti sulla stessa cella devi sommare o sottrarre in base al valore precedente. Spostandoti a destra il programma è leggermente più semplice ma potresti arrivare alla fine della memoria, quindi devi essere certo che la parola più lunga non superi il numero di celle. L’altra soluzione (senza ‘>’) non ha questo problema.

Comments are closed.