Unnikked - Esperienze personali in campo informatico

Un interprete per Brainfuck scritto in Java

Sin da ragazzino mi sono sempre chiesto come si facesse a comandare un computer tramite un linguaggio di programmazione.

Che sia Java, C, Python, PHP o altri, mi ha sempre affascinato il modo in cui un file di testo scritto con un’ opportuna sintassi e una buona dose di coscienza si possa tramutare, quasi per magia, in azioni che un dispositivo elettronico è in grado di eseguire.

Alcuni linguaggi di programmazione sono facili da usare, per la loro proprietà di essere compresi quasi quanto il linguaggio naturale, ma esistono altri, invece, che pur avendo lo stesso potere di espressività alla pari di un qualsiasi linguaggio di alto livello, sono molto difficili da utilizzare. Uno tra questi linguaggi, così detti esoterici, è il Brainfuck .

Brainfuck è stato creato intorno il 1993 da Urban Müller con lo scopo di essere un linguaggio di programmazione adatto per una macchina di Turing che potesse disporre di un compilatore molto piccolo.

Il linguaggio dispone di otto istruzioni elementari, di cui due usate per l’I/O.

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

Data la specifica del linguaggio scrivere il relativo interprete per Brainfuck è banale.

import java.util.*;
public class Brainfuck {
    private Scanner sc = new Scanner(System.in);
    private final int LENGTH = 65535;
    private byte[] mem = new byte[LENGTH];
    private int dataPointer;

    public void interpret(String code) {
        int l = 0;
        for(int i = 0; i &lt; code.length(); i++) {
            if(code.charAt(i) == '&gt;') {
                dataPointer = (dataPointer == LENGTH-1) ? 0 : dataPointer + 1;
            } else if(code.charAt(i) == '&lt;') {
                dataPointer = (dataPointer == 0) ? LENGTH-1 : dataPointer - 1;
            } else if(code.charAt(i) == '+') {
                mem[dataPointer]++;
            } else if(code.charAt(i) == '-') {
                mem[dataPointer]--;
            } else if(code.charAt(i) == '.') {
                System.out.print((char) mem[dataPointer]);
            } else if(code.charAt(i) == ',') {
                mem[dataPointer] = (byte) sc.next().charAt(0);
            } else if(code.charAt(i) == '[') {
                if(mem[dataPointer] == 0) {
                    i++;
                    while(l &gt; 0 || code.charAt(i) != ']') {
                        if(code.charAt(i) == '[') l++;
                        if(code.charAt(i) == ']') l--;
                        i++;
                    }
                }
            } else if(code.charAt(i) == ']') {
                if(mem[dataPointer] != 0) {
                    i--;
                    while(l &gt; 0 || code.charAt(i) != '[') {
                        if(code.charAt(i) == ']') l++;
                        if(code.charAt(i) == '[') l--;
                        i--;
                    }
                    i--;
                }
            }
        }
    }

    public static void main(String[] args) {
        new Brainfuck().interpret(args[0]);
    }
}

Il codice sorgente proposto assume che il programma dato in input sia corretto sintatticamente. La memoria è rappresentato da un array di byte come richiesto dalla specifica. La variabile di istanza dataPointer memorizza la cella di memoria puntata (manipolata dalle istruzioni + – > <).

Bisogna prestare attenzione alle istruzioni di salto (branching) [ e ].

Ogni qualvolta si incontra l’istruzione [ bisogna trovare la corrispondente istruzione di chiusura ]

Da Brainfuck a Java

Tradurre un codice sorgente in Brainfuck in un codice sorgente Java è anche un procedimento molto facile da eseguire.

Ogni istruzione Brainfuck corrisponde ad un istruzione di un linguaggio ad alto livello, come Java, secondo lo schema:

Brainfuck Java
> ptr++;
< ptr–;
+ mem[ptr]++;
mem[ptr]–;
. System.out.print((char) mem[ptr]);
, mem[ptr] = (byte) in.next().charAt(0);
[ while(mem[ptr] != 0) {
] }

Anche in questo caso il codice Java è molto semplice

public class BrainfuckToJava {
	private StringBuilder source;
	private int ident;
	
	public BrainfuckToJava(String code) {
		source = new StringBuilder();
		source.append("import java.util.Scanner;\n");
		source.append("public class BFConverted {\n");
		source.append("\tprivate static int ptr;\n");
		source.append("\tprivate static byte[] mem = new byte[65535];\n");
		source.append("\tprivate static Scanner in = new Scanner(System.in);\n");
		source.append("\tpublic static void main(String[] args) {\n");
		convert(code, source);
		source.append("\t}\n");
		source.append("}\n");
		System.out.println(source.toString());
	}
	
	private void convert(String code, StringBuilder source) {
		for(int i = 0; i &lt; code.length(); i++) {
			for(int t = 0; t &lt; ident; t++) source.append('\t');
			switch(code.charAt(i)) {
				case '&gt;': source.append("\t\tptr++;\n"); break;
				case '&lt;': source.append("\t\tptr--;\n"); break;
				case '+': source.append("\t\tmem[ptr]++;\n"); break;
				case '-': source.append("\t\tmem[ptr]--;\n"); break;
				case '.': source.append("\t\tSystem.out.print((char) mem[ptr]);\n"); break;
				case ',': source.append("\t\tmem[ptr] = (byte) in.next().charAt(0);\n"); break;
				case '[': source.append("\t\twhile(mem[ptr] != 0) {\n"); ident++; break;
				case ']': source.append("\t\t}\n"); break;
				default: continue;
			}
			if(i+1 &lt; code.length() && code.charAt(i+1) == ']') ident--;
		}
	}
	
	public static void main(String[] args) {
		new BrainfuckToJava(args[0]);
	}
}

Bisogna prestare attenzione che la Java Virtual Machine non permette metodi che abbiano una dimensione maggiore di 64KB per tanto, lunghissimi programmi scritti in Brainfuck potrebbero non essere eseguiti dalla JVM, sebbene la traduzione sia corretta.