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

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

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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.